Legend Entertainment's Games

[dreammaster]

I've always found the analogy of a jigsaw puzzle pretty accurate when dealing with reverse engineering an executable. The first step is to learn assembly language programming and run a given executable through a decompiler so that you've got a textual version to work with.

Next is to start identifying commonly used routines. A good starting point is to grab a reference (either a book or online) for the DOS 21h interrupts.. it's normalyl fairly easy to locate points which handle file access. From there try to figure out the purpose of the routine that contains it, and give the routine a proper name (like file_open if the routine is just a wrapper for a call to the DOS interrupt). Once the routine has a proper name, you can replace all occurances of calls to that method with that name.

From there, you can start figuring out what the routines that call those ones do. Perhaps it may be a routine for uncompressing screens once the data has been loaded in. Or maybe it sets loaded data to somewhere in memory whose purpose you can guess at by looking elsewhere in the code.

The important thing is to keep gradually replacing method names and data variables from auto-generated names (Like data_819) to properly descriptive names, and make notes of what inputs/outputs each routine produces. Gradually over time you'll understand more and more of what the executable does.

Oh, and a good debugger wouldn't hurt either; even DEBUG will work well in a pinch if you need to see what variables are likely to be passed into a routine.

[Jorpho]

I was thinking about these again recently. I've been wondering: even if a lot of the game logic is hard-coded into the executable, there is libx86 that could, in theory, be used to run bits of machine code, right?

Or would something approaching emulation be, by its very nature, beyond the scope of ScummVM? (Or has something like that already worked its way into ScummVM in the last four years?)

[fingolfin]

That would not really be suitable. You can use DOSBox if you just want to run the game capable of running it via emulation. But for ScummVM, we don't emulate CPUs, we fully reverse engineer the game in question. Blindly executing large blobs of binary code (assuming we could figure out how to extract it) would not work well, esp. if those start to try things like invoking DOS interrupts etc.

[Serious Callers Only]

A question for you that might know: are the cryo games hardcoded, or are they part of some common engine?

It would be fantastic to have Dune 1, Lost Eden, KGB, Captain Blood etc added to scummvm.

[dreammaster]

I was thinking about these again recently. I've been wondering: even if a lot of the game logic is hard-coded into the executable, there is libx86 that could, in theory, be used to run bits of machine code, right?

The problem is still to identify what parts of the game are game-specific logic, and what parts represent core engine functionality, and separating the two. To do so represents a considerable investment of time, so having an x86 simulator doesn't really help all that much.

In case you're interested, this some issue is currently being tackled by the MADS/M4 engine - as part of the disassembly of the Rex Nebular game, I've had to identify which routines are the scripts for the game; in this case, I've actually created a translation program to convert them into a simplified instruction set that will be easier for the ScummVM implementation to interpret. This is still a work in progress, so I haven't yet committed my engine implementation, but it should be completed in the near future.

As far as the Legend game series is concerned, I actually have an in progress disassembly of the Companions of Xanth game, and there has also been some preliminary disassembling of the Death Gate game. Neither were/are very far along, so don't expect any significant progress in the near future.

[bobdevis]

What are the requirements to start learning reverse engineering? Should we have an high education in computer sciences?

Even though a bit of theoretical background helps, it's not really neccessary. You should know a bit about binary/hex number representations, and you should know how to use a hex editor. But theory can never replace actual practice and experience, so just start somewhere and try to get a 'feeling' for the file formats. It's hard to explain
Oh, and you need to have some programming knowledge (doesn't matter much which language) because you will have to write small programs (like gamefile extractors etc.) to test your findings.

There's a (draft) introduction at the REWiki here which you might find useful (there are some further links as well).

I was thinking about writing a small tutorial on RE'ing a simple file format, but I don't know when I might have enough time for that.

As an introduction, I would recommend people to take any programming language they want and, once they are passed the basics, write their own GIF image viewer. GIF is common, simple and well documented. It is also easy to see what is going on since the end result is a picture.

[Risca]

Y0!
I've been working on reverse engineering the Death Gate game about once a year for the past 5 years and now it's time to make some findings public. My notes:
https://gist.github.com/Risca/e83f7e7b2 ... b58dd6ca92

I've also made a program that lets you explore the Death Gate media:

• Still images (still have problems with these)
• Animations
• Music
• Voice and sound effects
• Text

Source and build instructions here (only tested on Linux):
https://github.com/Risca/dgate_resource_manager

However, as previous posters have pointed out, the game engine is hard coded. I've messed with the IDA disassembler to figure stuff out, but my experience is simply not there yet. I believe large parts of the DGATE.EXE binary is just raw data, or maybe my version of IDA is just having problems interpreting the file. I would like your input on what you believe would be the best attack vector on adding Legend Entertainment (Death Gate in particular) to ScummVM:

• Re-invent the game engine since the media formats are now known (mostly)?
• Continue to reverse engineer the DGATE.EXE to extract some kind of script data?
• Other approaches?

Some screenshots of the resource manager


EDIT: formatting

[dreammaster]

You sir, are nothing less that an absolute, awesome, siren I myself spent some time whilst I was out of the country on business recently to take a break from working on Starship Titanic to actually work on further disassembly and implementation of code for the Legend Entertainment games, specifically, Companions of Xanth and Gateway. I've had to temporarily shelve work on it when I came back, though, because I'm getting close to having Starship Titanic completable. And unfortunately, I've got a near complete implementation of Xeen 4 & 5 Clouds/Dark Side/World of Xeen to finish off as well; otherwise I'd be still be working on it. And now you turn up with all this lovely information..

As it stands:

Firstly, I've spent some time creating an engine core that will make it easy for me to implement the multiple different Legend entertainment games. I pinched a lot of code from Starship Titanic ironically enough - it has a really clean, modular design that I fell in love with. I've already got some in progress code for showing parts of the Xanth conversation window, and the Gateway scene view. Not much to look at visually, but still, there's a significant amount of graphics and core code already implemented for it.

If you're interested in perusing my engine further, see my engine branch on Github.

Now onto your question about DGATE.EXE. I hadn't really looked at it's executable before; I concentrated more on Xanth because it was the earlier of the two "fully graphical" Legend games. That actually proved tricky.. the Xanth executable was encoded with RTLink, an overlay manager the let parts of the executable be swapped in and out of memory. I had a hell of time trying to disassemble it in IDA, because none of the method calls actually pointed to code they were calling, and various different data blocks could be loaded in and out of the same area of memory. In the end, I had to write a tool, rtlink_decode, just to do a whole bunch of processing of the executable to produce a dummy executable that had all the code laid out sequentially, and fixed all the method calls so that IDA could properly disassemble it. Well, mostly properly. There's still the occasional incorrect segment references.

Sorry, got a bit long winded there. Returning to point, I had a quick look at the dgate.exe executable, and it looks like it didn't use RTLink. This may be both a good and bad thing. Just dumping the executable IDA into IDA, it gives an error about not being able to load all the file. This could be indicative of some form of manually loading the extra bits into memory. But since it's not using RTLink, I can't say for sure how much of a problem this may be.

If you want to keep working on Death Gate, at least take cheer that you're not the only one interested in the Legend games. And that once my current backlog of games are dealt with, and presuming nothing more interesting comes along, I'll be working on a game, Xanth, that likely shares a lot of code in common with Death Gate. It should make it easier to eventually add support for it as well. And your work done already may just make it that much easier to finish Xanth. So thanks

[Risca]

My work on Death Gate started at a LAN party [1] about 5 years ago when I wanted to learn more about reverse engineering. Since then, I've come back to this LAN party annually to continue the work. Unfortunately, this years' LAN party is nearing its end and my allotted time for Death Gate work will become more limited again. It's almost 4 am and I need some sleep. At least this time I got some code published

I actually got the introduction animation of Death Gate running (no music, no voice) on ScummVM.[2] I will definitely submit a patch to the ScummVM FLIC decoder once I've gotten some more sleep

[1] https://www.birdie.org/nyheter
[2] https://github.com/Risca/scummvm/tree/dgate_engine

[Risca]

There is still some more work to be done on the still images. All larger images come with a 3*256 byte palette prepended, but the smaller images do not. I've sometimes been successful in using the first palette before the image and sometimes the palette of the next big image. The 4 byte header on some (all?) of these small images might be a hint. However, even with a seemingly proper palette, parts of some of the small images are still garbled in color. Could be some form of transparency and the smaller images act as overlays. Any ideas?

I have another tool just for investigating images. This tool allow to open a .PIC file and cycle through the images in it. The tool will print the image flags and also pixel value for individuals pixel when you hover your mouse over the image. I'll upload it to github when I get home.

EDIT: Uploaded to github now: https://github.com/Risca/display_8bit_dgate_data
After fixing some bugs in my program it seems very likely that my initial thought about coordinates and overlay images are correct. Don't know how to handle multiple overlays though. Maybe some kind of Z-order can be found in the image flags?

[dreammaster]

There is still some more work to be done on the still images. All larger images come with a 3*256 byte palette prepended, but the smaller images do not. I've sometimes been successful in using the first palette before the image and sometimes the palette of the next big image.

That's exactly the same in Xanth. There are some methods that explicitly save and restore parts of the palette which are manually called by the code for the various different screens - there are two separate palette areas, one from indexes 16-31, and the other from 32-79. The compendium screen code, for example, first loads the background using picture 31, which sets the palette, and then calls these methods to save parts of it. Then when further images are loaded, which overwrite the palette, it then restores the parts it copied from the background palette.

If you're interested, see the engines/legend/later/screen.cpp methods saveSubPalette1, savedSubPalette2, and restoreSubPalettes methods in my legend branch.

Don't know how to handle multiple overlays though. Maybe some kind of Z-order can be found in the image flags?

I don't think so. More likely if there is any kind of z-indexing, it'll be done in the game code. Since the games don't have a player character that wander about in the scene, it probably just draws a list of scene objects in whatever order the game data specifies, which will be in the correct ordering for "depth".

[Kaminari]

Can't believe I've been following this topic for the past 11 years.

If Death Gate ever gets implemented, I hope all versions (MCGA, VGA, MT-32 and GM) will be supported. See you all back in 2028.

[CaptainJei]

Great work, Risca and dreammaster!

To echo Kaminari, I think MT-32/GM support is always important, but I'm not the one putting the thankless hours into getting these games working.

[Risca]

I did some more experimenting today with overlayed images. Here's what I did:

1. Load a big image and its palette
2. Load a smaller image and use the palette from the big image.
3. The smaller image has the offset into the larger image as 2x2 bytes before the actual image.
4. Set the alpha channel for each green (0x00FF00) and black (0x000000) pixel to 0 (transparent)
5. Paint the small image on top of the big image, respecting the alpha channel.

The result is not quite right:


It is probably as dreammaster says: I'm using the wrong palette for painting the smaller image. However, there also has to be some kind of blending involved since the smaller image does not contain the details of the arc above the door (see the image I attached in my previous post).

EDIT: code pushed to github now.

[Risca]

Okay, I've done some more experiments but I'm still not getting the images right. Here's what I tried:

1. Take a big image
2. Overlay a suitable smaller image
3. Cycle through all images with a palette and see if the colors match

So far I've not managed to create a perfect overlaid image.
Could the sub palette split be different?
Could there be a default palette?

I've updated my tool to allow selecting sub palettes. I also added a zoom slider. Code is on GitHub


EDIT: spelling