The intricacies of disassembling RTLink/Plus

Finally, after many years of half-hearted attempts, I've finally rewritten my RTLink decode tool practically from scratch to handle disassembling the RTLink/Plus overlay management used by the later Legend entertainment games. See rtlink_decode for the result. The original version of the tool was pretty dodgy, and pretty much hardcoded to only handle the MADS games (Rex Nebular, Return of the Phantom, and Dragonsphere). In this posting, I'll go into more detail of what RTLink/Plus was for those who may be interested.

In the latter days of DOS gaming, game developers started running into a problem. Namely, that their executables were starting to hit the limits of main memory. Not every game could, or would, take advantage of scripting game content, so having all the game logic in the main executable caused the size to bloat. So what to do if your executable was now too big to fit in memory? This was the problem RTLink/Plus was designed to solve.

RTLink is essentially an overlay manager. It splits a program's compiled code into multiple different segments, and allows them to be loaded in as needed, and then replaced when code in other segments needs to execute. RTLink can handle recursive segments, with individual segments split up into their own set of swappable sub-segments. It also allows for multiple different "loading areas" in memory that can independently have their own set of segments. See this article for more general information about RTLink.

Before I go into more details of the problem this posed for disassembly, let's go over how RTLink implements the overlay manager in code. So far, I've encountered three different variations on RTLink being used in executables. What I'll call variation 1 & 2 seem to be the most common form of RTLink in games I've examined. When a program is compiled with either of these versions of RTLink/Plus, one of the segments in the code will contain the RTLink logic, as well as two main areas: the dynamic segments and the function thunks.

The segment list is a list of the dynamic segments within the application. It contains the following information:

• The segment in memory where the dynamic segment should be loaded
• Whether the segment is stored in the application or a secondary overlay file (Variation 1 only, version 2 only ever uses the executable).
• The file offset and size of the segment
• The number of relocation entries the segment has; Variation 1 only. Variation 2 has it as part of the starting header for the segment pointed to.

When a segment is needed, the above details are used to read the segment's data from file, and load it into the correct place in memory. The data for a segment consists of two parts: an initial header area, and the date/code for the segment. For variation 1, the header area simply consists of a list of relocation entries. Whereas for variation 2, the details of segment size and number of relocations are provided in a header at the start of the segment, before the relocations list.

A segment's relocation entries are used for the same purpose as relocation entries in a standard application - executables can be loaded at different locations within memory, so all segment references need to be relative to the starting point of where the program is loaded. By keeping the relocation entries for each dynamic segment together with the segment data itself, it's easier for RTLink to apply any needed segment adjustments each time a dynamic segment is loaded.

This is fine to handle shifting the segments in and out of memory, and allow them to have valid memory references, but what causes them to be loaded? The answer is the method "thunks" area of the RTLink segment. When dealing with dynamic segments, you can't just do a far call to some offset in the area of memory segments are loaded in.. you couldn't be sure that the segment you want is actually loaded, or still in memory and not unloaded by some other segment. For this purpose, the thunk list is present.

For every method in a dynamic segment that is referenced by any other segment, a thunk/stub method is created. These consist essentially of the following: a call to the RTLink manager to load the correct segment for the method, a far jump to the method in the correct memory location in the loaded segment, and a following 16-bit value specifying which segment the thunk is for. This way, the thunk method acts as a wrapper, ensuring the correct segment is loaded and passing control to the method to execute.

For variations 1 and 2, the thunk methods have some minor differences, such as version 2 using far calls to the RTLink segment loading code, and having an optional word after the segment index. The segment selector in the far jump call is also already loaded with the memory segment in variation 1, whereas in version 2 it's normally 0 initially, and then set to the correct segment when the thunk method is called. This allows variation 2 to dynamically load the segment in different places in memory, whereas variation 1 is limited to a single specific loading point.

The RTLink segment loader method also mucks around with the stack to push a new intermediate return address on the stack for when the method that's jumped to finishes. This return address points to a code fragment that also handles the case where a method in a dynamic segment calls a method in another one.. in that case, it handles reloading the original segment, so that the original caller's code can be safely returned to.

Put altogether, this scheme allows programs of practically any size needed. As the program grows, the code simply needs to be split into more and more dynamic segments which will get loaded only when needed, and remain on disk when not. Great for having big programs, but not so great for those of us interested in reverse engineering the game by disassembling the executable.

There were several problems to be solved for disassembling such games, which I'll go into now.

A standard IDA disassembly doesn't have all the code

Well, it wouldn't. If you try to disassemble an RTLink/Plus compiled game, IDA will give you an error about unused data at the end of the executable. This will be for one or more RTLink segments. Additionally, as previously mentioned, some of the code for the program can also be stored in a separate OVL (Overlay) file.

Well, I could just load the raw data for them into the disassembly, right?

Well, no. That wouldn't help much, because of all the thunk methods. They all have their references to the same area of memory where segments are expected to be loaded. If you were doing things manually, you'd need to get the details of each segment from RTLink, manually load the code and/or data into new IDA segments, and then manually adjust the thunk methods to point to those methods.

You'd also need to worry about the dynamic segment relocation entries. If you manually loaded the code for a segment, you'd have to read the list of relocation entries for the dynamic segment and manually adjust each relocation entry within the segment. Segment selectors may point to code within the segment (or another sub-segment within the loaded overall RTLink segment), to a low memory area of the executable that remains static in memory, or to the data segment (at a higher memory segment). All in all, you'd have to be extraordinarily patient to all that by hand.

So that's why you wrote rtlink_decode, right? That's what it does?

Yes and no. A bit part of what it does is indeed doing the above to create a new executable suitable for disassembly. This includes laying out all the dynamic segments sequentially (without their segment headers and relocation lists), handling relocation fixups, and the thunk methods adjusted to point to their methods in the decoded executable. However, another problem crops up in the handling of the data segment.

In my experience with RTLink, I've come across across two types of data segments:

1. In the case of the later Legend Entertainment games, the executable has a single RTLink segment, with the remainder of the segments coming from an OVL file. The single executable segment is for the main data segment as well as a few other miscellaneous segments.
2. In the case of the MADS games, the data segment isn't an RTLink segment, but all the RTLink segments follow it in the executable.

In both cases, we have a problem doing a proper disassembly. Executables are normally expected to have the data segment at the end of the program, because the data segment may be longer than the end of the executable. For example, a game's data segment may only have 1Kb of pre-set values which are stored in the executable, but it still requires 40Kb of unallocated/uninitialized space. That's why you'll frequently see, when you do a disassembly of a program, areas at the end of a data segment with '?' mark values, indicating the memory isn't part of the executable, so doesn't have any specific value when the program starts.

So if we did just lay the segments end to end, the data segment, coming before other dynamic segments, would end up being shorter than it should be, and a lot of the references to data within it would end up wrapping onto the following dynamic segments in the reworked executable. To avoid this,  the rtlink_decode tool ensures that the data segment falls at the end of the generated executable, after all the other segments. This, however, causes it's own share of problems. All the existing references to the data segment refer to where the data segment was expected to be loaded in memory, not to where the data segment actually is in the new executable. Because of this, all the references to the data segment in the executable have to be adjusted accordingly.

Ouch! Sounds fiddly.

It is. And took a lot of messing around to get right. Even then, that's not the entirety of the picture. For Companions of Xanth, the Legend game I used for testing when rebuilding the tool, the data segment has some extra gotcha's.. It contains segment references into the middle of the memory area RTLink segments are loaded into. Presumably these are used in some special controlled circumstances when a specific segment (or segments) are loaded to access particular data. But it's impossible to know without understanding the game a lot better. 

Worse, the presence of the references were screwing up some of the loaded dynamic segments in the disassembly, causing them to be split in half. To handle this, the tool explicitly looks for such "bad" references in the data segment, and removes the relocation entries for them. This way, the value in the data segment will remain as a static word, and the segments don't get incorrectly split up. The user can always then later manually set up a pointer to an appropriate segment if they wish. This handles the bulk of such errors, but Xanth at least, there are still references in the low part of the executable (that remains static in memory) to locations within the RTLink segments. Since I can't know which particular RTLink segment is meant to be loaded when the code they're in is called, these few remaining references will have to be later manually adjusted as well.

So that's it?

Yep. After all these years, I'm finally able to generate a (mostly valid) "decoded" executable, and produce a clean disassembly of Companions of Xanth. I also, initially, had two separate versions of the the tool, one the old hacky version for MADS games, and the legend variation for Legend-style RTLink usage. I've since updated my tool to properly handle MADS games, so now there's only the single rtlink_decode tool, and it can handle both variations 1 and 2.

Oh, wait.. what about the 3rd variation you mentioned?

Ah, yes, I didn't really get into that, did I. This version seems to be somewhat different than the other two variations. In this case, the RTLink code is stored in a separate rtlinkst.com file, and then loaded into memory. It then shifts part of the program downwards in memory, and uses it's own relocation table to manually process relocation entries on the shifted code. This variation is proving tricky to disassemble, so whilst I have located the segment list, I still need to:

• Figure out how relocation data is encoded. I think I've located the correct data in the executable, but the code RTLink uses to update relocation entries is pretty nasty and overcomplicated.
• How much of the start of the executable to remove so that the produced executable doesn't have any of the old code at the start of the executable that gets overwritten
• Find the thunk methods, and see whether the existing code will handle them.

Hopefully I can quickly figure out the remaining details for the third variation soon. The goal is to have a tool that both myself and others can use in the future to help them disassemble any game that used RTLink/Plus. Then no-one else will have to go through all the frustrations that I did trying to deal with this %#@! thing.

Sherlock Testing Resounding Success

Hi everyone,

It seems like the testing of the Sherlock games has been a success. There were lots of bug reported, and all the ones reported so far have been fixed. The foreign language versions haven't all been fully tested yet, but hopefully now the immediate crashes with conversations and inventory in both Serrated Scalpel and Rose Tattoo foreign language versions have been fixed, and the rest of the games can be tested. I'd like to thank everyone who's tested so far for your efforts, and feel free to post any more bugs you come across. Though hopefully there won't be too many more to find :). And if one else has copies of either game, particularly different foreign versions, any other testers would be appreciated.

Right at the moment I'm at the sweet point where all the outstanding bugs for Sherlock have been resolved, so unless new ones come in, I can turn my attention to other things.

So, whats coming next for me? Several things:

Serrated Scalpel 3DO

Serrated Scalpel 3DO still isn't completable. There are some areas, such as the darts game to fix up, and there are still some differences in sprite positioning that would need to be accounted for. It's somewhat constrained by the fact that we don't have any original source for it, and I don't have any experience with reverse engineering 3DO games. It may simply be a case of do as best we can with hardcoded fixes as necessary.

The 3DO version also has a few missing things compared to the PC version; notably it lacks the journal the PC version has. A "nice to have" for the future would be to reintroduce it, so that the 3DO version could be the definitive version of the game, containing all the PC version functionality as well as the video for all conversations. We'd likely create a tool that extracts necessary graphics for UI buttons and the journal background from the PC version, and produce a Dat file that ScummVM can use automatically when playing the 3DO version.

RTLink Overlay manager

Next, there's the RTLink/Plus overly handling in Companions of Xanth. I'd previously had some luck writing a tool to process Rex Nebular and create a flat executable with all the segments suitable for disassembling, but doing the same for Companions of Xanth proved elusive. Over the years I made several attempts, but none bore fruit. Until now. As of yesterday, I was finally able to write a new version of the tool that successfully generated a flat executable that could be disassembled. So one day, after a great deal of disassembly work, ScummVM may support the game.

My only disappointment is that RTLink/Plus seems to have had quite a number of variations. Rex and Xanth's RTLink mechanism were fundamentally similar, with all the RTLink code, segment list, and method thunks/stubs in the executable and/or overlay file. For several other games with RTLink that I tried, however, they seem to use a bizarre alternate method where a file called 'rtlinkst.com' is loaded, then an '.RTL' file for the game, and finally only then the game executable. Which means that my tool doesn't work with them, and I'd need to figure out this new mechanism from scratch if I want the tool to be general-purpose enough to handle any RTLink game anyone might want to use it on in the future.

Guess that can be another long-term project to muck around with. Hopefully it won't take as long as it did to finally get Xanth properly disassembled. :). I'll probably make another posting in a day or so about RTLink in more detail, for those that are interested.

Might & Magic, World of Xeen

Next there's my work on re-implementing Might & Magic - World of Xeen (and Clouds of Xeen, Dark Side of Xeen, and Swords of Xeen). With some free time last weekend, I finally returned to working on them, and likewise was finally able to properly disassemble the  algorithm the original used for scaling. So as of now, sprites are now correctly scaled, as before I was only using a rough guess scaling code I'd nicked from another game engine. I've also fixed some other drawing bugs for drawing outdoor areas (outside town). So as of now the game scenes now display properly! :)

That's right, you can now walk around, fight monsters, go visit the various buildings in town, and even leave the town! In fact, most of the functionality for the games are already implemented. Apart from lots of testing and minor bugfixes that will be needed, only the following major areas remain to be implemented:

• Introduction/ending sequences for the games
• character management, and title screens.
• Sound. I'm hoping I can simply slot in one of ScummVM's audio decoders without much further work.
• Savegames

At the moment I'm concentrating on getting World of Xeen (which combines Might & Magic 4 and 5 together) working. But then afterwards I'll implement separate support for 4 and 5, as well as for Swords of Xeen. It might even be feasible to handle Might and Magic 3 - Isles of Terra as well, since I'm given to understand the engines are nearly the same.

Those interested in following the progress can see it at the brand-spanking new RogueVM Github account. That's right; after all the years of idle talk, I've finally set up a place to properly store RPG related game engines. No website yet, but at least it's a start. :) I'll likely spend the near-term focusing mostly on finishing support for the game before I move onto any other adventure games, considering how far along the engine is already.

Return of the Phantom

Strangerke has put a lot of work recently into implementing scene logic for Return of Phantom, the next MADS game that was published after Rex Nebular. There are quite a few stubs for missing engine functionality that was added in though. So when I do return to working on adventures, it will likely be to assist him in completing the game.

DreamMaster.

Rex-tacular

What a difference a mere week can make in terms of progress. At the beginning of last week only the basic background from one scene was showing, although there was more code implemented in the engine that wasn't yet working. Now, a week later, behold the progress of Rex Nebular on ScummVM:

That's right, in a rush of effort this week, the Rex Nebular engine has already passed several milestones in development:

• The user interface is now partly implemented. As you can see from the above picture, the user interface background is showing, with the sections for the actions, items, and the animated inventory item showing.
• The scene background is now displaying, along with basic sprite animations within the scene. The fires are burning, and the hamster "auxiliary power" :) is running.
• Basic player display. Rex is in his default position for the scene, facing the door.
• Behind the scenes, we've already completed the logic for a couple of the game scenes, although we're obviously not able to test them properly yet.

The focus for the upcoming week will now be on the beginnings of user interaction and action handling. This means getting walking working, selections in the user interface, and actually being able to execute actions. A lot of the needed code is already in place, but will require some heavy duty debugging and comparison against the original to figure out where things are going wrong. We're somewhat hampered by the complexity of the core engine when doing debugging, but we'll get there eventually. :)

Rexing it Up

Work has been progressing furiously with the MADS engine, and Rex Nebular support. Whilst I was able to us some code from the previously engine version, a lot of it turned out to be more M4 specific than I'd anticipated, and had to be freshly disassembled and/or rewritten. Additionally, with my greater experience writing engines, I've been able to lay out a cleaner separation of methods into classes than previously, particularly keeping in mind extensibility for having separate game logic for the other MADS games. As a result, the new MADS engine is already significantly different from the old M4 engine.

After a great deal of implementation, not to mention debugging of my code and comparison against the original running in DOSBox, I finally have the background of my test scene showing! See below for the first 'new engine' view of Rex Nebular in all it's glory:

Particularly auspicious considering I see that Rex Nebular has just been released for sale on GOG. So presuming that the engine gets finished this time, people will easily be able to obtain a copy. :)

What's next? In order to reach my original milestone of having an animation sequence playing correctly, it meant that I needed to properly implement the entire frame step and rendering logic from the game, which had a great deal of code, and many different secondary methods that I've encapsulated into a multitude of classes for sprite sets, pending sprites, active sequences, text display, and lots of other things. Not to mention a pretty complicated precursor to M4's RGBList, where resources loaded in for both the scene and for sprites are allocated chunks of the palette space.

I'm currently focusing on debugging the standard sprite drawing, which is used by the animation class. I'm hoping with a bit more work, I can it to properly show the animation sequence. Doing so will also help ensure that all the sprite display logic for the scene also works correctly. This will make it easier to start work later on for full blown game scenes, since all the necessary sprite display will already be done, and I can concentrate on things like player movement, action handling, etc.

Explosive decompression

Looking back, despite my earlier promises of posting more regularly, it seems I've been a bit tardy in posting updates, and quite a bit has happened. So lets get up to date with what's been happening with me. Firstly, we finally got some proper bug reports for Return to Ringworld, and have been working to fix them. Well, moreso Strangerke than me, so thanks go to him for his work in fixing bugs when he has the time.  As of right now, the card mini-game still isn't fully functional, but at least the main game is that much more polished now than it was.

Secondly, as of Monday, I finally merged the next game I was working on, Voyeur, into the project's master branch. This is a weird little game that Strangerke put me onto, because the original DOS executable had debug information embedded in it, which made it somewhat easier to implement. Still a lot of work to understand the contents of methods, reimplement them, and get the game in a stable state. But it made a nice change of pace from all the TsAGE work, where we had to disassemble everything from scratch. As of right now, the Voyeur engine only supports the DOS version. Apart from DOS, there were also CDi and Macintosh versions released. The Mac version at least may be supported at some point in the future, although there is some extra complexities we'd have to worry about due to the Mac-specific data in it, such as rasterized fonts that the PC version doesn't have. Adding support for it might make a nice future mini-project for a Mac enthusiast.

So what's next? Apart from further bugfixes for both Return to Ringworld and Voyeur, I'm already onto my next project.. once again tackling the white elephant of Nex Nebular, for the 3rd time. This time, though, things will hopefully be different. Using my experience with disassembling the TsAGE sound system, I tackled the sound system first, which was the major previous remaining stumbling block. And as of last Sunday, I finally got it working! That's right, my new embryonic MADS engine was able to play back the explosive decompression sound you get when you fail the copy protection check. It was a wonderful feeling, after spending a week reverse engineering and then implementing the code, then having spent an afternoon trying to debug my code and compare bytes being written to the ScummVM FM_OPL driver against the port writes in the original running under DosBox, to finally get everything right, and hear the sound coming out of my speakers.

 It turns out that despite some funky assembly tricks in the player that I had to work around, the player itself is actually a fairly compact, simple implementation. I'm no sound expert (as my frequent prior complaints make clear :) ), but I understood enough to give the various methods in my code halfway decent names, and name at least some of the fields. Hopefully a further analysis, now that I have cleaner C++ code, will help me better understand what's going on, and give the rest of the fields more proper names.

Now that the issue of sound support is taken care of, how am I going to proceed from here? I have a lot of code back from the earlier combined m4 engine which had code from both Rex Nebular and Orion Burger. Part of the trouble with the earlier attempts, I think, was that we were overcomplicating matters. As such, I'll only gradually put in code as I need it, and not worry so much about M4. That'll help me keep the focus more on getting Rex Nebular to work. Not that I'm going to just chuck out all M4 code from the engine. I've already started work on making the core classes, such as the previously named 'M4Surface' class, having a cleaner structure more suited for multiple games. For example, it'll now have it's own class factory, which will abstract having a base MSurface class that will have different descendants that implement the various game specific load/display logic. That seems cleaner than littering the code with "if isM4()" checks, and having methods like "rexLoadBackground". As far as a caller is concerned, they'll just initialise a surface, and the factory will take care of giving them the right kind for their game.

With a cleaner separation of game logic into descendent classes, I'll be able to, for example, keep in place special cases we'd already figured out for Riddle of Master Lu, and make it that much easier to implement support for it later. So that should keep a certain team member who shall remain nameless happy.  :)

At the moment, I'm currently aiming for getting all the initial engine setup sorted out, and playing back the animation sequence for when you get the copy protection answer wrong. As I mentioned above, this will involve pulling some code from the old project to save time, but I'm also already doing a fair amount of refactoring and cleanup, such as changing char *'s to Common::String, using Common::Point's, properly commenting the code, and so on. Given the amount of previous work done on the old M4 engine and the mostly complete disassembly I had of Rex Nebular, we can hopefully expect rapid progress in functionality, and eventually enjoy Rex's escapdes as he quests for the vase he's been sent to find.

Rex can now walk about on-screen

Here I was bracing myself for the imagined complexities of movement logic, and it turned out to be a whole lot simpler than I imagined. Probably blame it on the other two engines I've had experience with path-finding for: Lure, and Tinsel, both of which have their share of complicated logic. For Rex Nebular, though, the implementation was a lot more elegant than I'd expected.

What the MADS engine does for walkable areas is to have two parts. The first is a priority/depth surface, which had already been previously implemented. This is a surface which both specifies the walkable areas, and is also used to determine which parts of an object, at a given 'depth', should be drawn on-screen. In the first room, for example, the area comprising the chair has some varying levels so that the player gets drawn behind it.

The other part to the movement functionality is a series of 'scene nodes'. These are a series of points distributed across the scene to represent appropriate intermediate points in movement. If a straight line between the start and end point isn't possible, because of a marked obstruction, then the engine calculates the distance between each node in the scene, including both the start and end points as two extra nodes. It then calculates which series of nodes will take the shortest amount of time to traverse, and uses that as the basis for movement - the actual walking then moves the player from node to node until the destination is reached.

This works well for the game since, unlike in Tinsel or Lure, there aren't ever any moving actors that could interrupt the walking path. The only NPC character movement that ever happens is in cut-scenes, where the player is either not moving, or is being controlled by the computer (such as when Rex is taken to the cells).

Now that I've got Rex moving around on the screen, the next immediate step is to get the hotspot and selection code working. Somewhat ironically, this is turning out to be more complicated than the walking code itself. I'm currently working my way through disassembling the various routines and implementing comparable code. Hopefully, I'll soon have enough implemented that I can properly implement some actual actions in the first room.

MADS/M4 engine now has cutscene support

Well, it's been a very productive month for work on the MADS/M4 engine.

Since the last posting, I started working on the cutscene animation system. This is a separate module to the basic cycled animations that get loaded into a screen.. rather, the game uses an animation manager to handle so-called 'cutscene animations', such as that of Rex waking up in the first room. In this case, the animation manager handles the work of animating the sequence of frames of Rex waking up, looking around, and then getting up. Given that this was the fist major action in the game, it made sense to have that properly implemented first.

Above and beyond that, the animation manager is also used for handling all the full-screen animations done in both the introduction and ending sequences, so once I had Rex properly animated in the first scene, I moved onto implementing proper support for them. With some help from Md5 on the handling of digital voices during the intro, the introduction sequence now plays completely if you press 'F3' from the main game menu. There are only a minor few issues remaining with the introduction, in that:

• The tempo of the intro isn't quite matched to the original yet; I'll need to properly calibrate the timing loops at same stage
• I haven't implemented palette cycling, which is used by some scenes within the introduction sequence to simulate basic animation.

I consider the above minor things, and I'll get to them eventually. For now, I again got distracted from polishing up the remaining issues by making a breakthrough in my understanding of the code that controls the player (you) within the screen. Within the last week I've implemented a great deal of code associated with player control, and now Rex is corrected displayed when the wakeup animation is completed. Not only that, but the idle animations run for Rex, and you can even turn him around by using the Ctrl-T key.

The obvious next stage for me to look into is actually starting to give some movement control for Rex, and have him be able to walk around on-screen. This is where I'll need to worry about figuring out the pathfinding algorithm, and how actual movement is done. I've already identified some of the methods associated with handling Rex's movement but, as I expected, there's a lot of calls to unknown sub-methods that I'll need to figure out the purpose of. Since the MADS engine was designed to be generic for multiple games, there's a lot of complexity in both the movement and pathfinding code that I'll need to figure out.

I'm really looking forward to this. It'll be another major milestone reached when I can move Rex around the room. At that point the game will finally be properly interactive. I'll then be able to work on interacting with objects, which I already understand a lot about, and maybe even moving between rooms and/or teleporting.

MADS engine reaches a milestone

Well, it's been a busy last month at work, but with things starting to settle down, I've finally had some free time to start working on the MADS engine again. And as of this weekend, I've just reached an important milestone in the development of the ScummVM engine implementaiton - the core graphics display framework is now working properly.

That's right.. the game logic for the first screen setup is still hardcoded, but the engine now properly implements all the necessary code to handle the calls to register a sprite sequence animation, and drawing elements on the screen; so animation sequences are now properly animated.

I consider that this reperesents a great step forward, since the entire game is based on the display of graphics - so I finally have a working core from which to build on further functionality with. This includes areas such as the logic for the player character itself.

The graphics core in the MADS engine has been more complicated then I've previously dealt with - the functionality is split between a main sequencing list for scheduling animations, graphics display logic, and various suppport classes, such as for dirty area handling. There's a whole mess of inter-relating code, which meant that I had to disassemble a lot of the code before I was able to implement something that works. There are still some fields that I've yet to figure out that handle certain special cases, such as the ability of dynamic hotspots to move their position, but that'll come in time.

If there's one thing that annoys me about the MADS engine it's the number of data variables that seem to get set everywhere. I'm presuming the original engine was designed to be generic for multiple games, but there seems to be a ridiculously large number of data values being set throughout the engine. It'll be interesting to find out whether the the majority of them are part of the 'core' MADS engine, or represent a whole lot of game-specific hacks for the Rex Nebular game.

I've included a screenshot from the first game room from Rex Nebular below. It may not be obvious from a still picture, but the various status displays now display flashing lights, and bubbles are escaping from the hull into the water.

Roadblocks in the path of tSage

Those of you who have been following the IRC channels will know that I made some real progress in the disassembly of the tSage engine, used by the Ringworld - Revenge of the Patriarch game, as well as several others. I hadn't really gotten into any of the game logic, but I'd made great strides in decoding the image formats and graphics display, so much so that my engine on Scummvm-misc could display test dialogs, as well as the right-click game dialog with proper highlighting and everything. Sample screenshots below:





However, given the perversity of life, I should have known better than to announce on the channel that I was making real progress. :(. Because as I was getting into the game execution logic, I began to realise just how complicated they made the engine. Whilst using C++ has it's advantages from the perspective of RE, since it does group related functions close together with the variables they use, in this case, they seemed to go overboard with it.

A preliminary look at the main event loop of the game shows they implemented a stack of "action objects" - multiple independent event handlers can be registered and control swapped form one to the other. I'm not sure, but I presume that this is to allow for things like cutscenes, where standard game operation is superseded.

For even more complexity, they went with a class hierarchy for the action objects which is at least four levels deep!.
The classes, as far as I've been able to determine, are as follows:

• They have a core 'SavedObject' class, which has some internal logic for registering each object instance in a central list. I presume this is for automating saving and loading.
• A child class which I'll call "SmartPointer". This class seems to encapsulate a pointer to a secondary object, and provides core logic for 'fixing' up the pointer reference. I can't be sure yet, but there's a lot of 'fixup' code in the engine, which I presume handles restoring pointer references between objects when a savegame is loaded, and all the objects are re-constructed. This class also implement a basic virtual table of processing and dispatch methods that automatically defer to the foreign object if one is set
• Yet another child class which introduces basic event manager functionality amongst other things
• A concrete fourth child class which seems to further override some of the event manager functionality, and is what gets added to the game's "action list".
  

As you can imagine, all this makes it somewhat different to understand what the blazes is going on. I've also examined the engine from some other points, such as scene loading, and even that seems to be overly complex, with method calling method - they really went in the direction of generalised/generic functionality, with the result that the code seems to be much more complex than it should otherwise need to be.

</whinge>

In any case, the tSage engine was only meant to be a part-time RE effort for when I needed a break from the MADS engine. I did somewhat get carried away with it for the last few weeks, but that was only because the areas I was looking at proved so easy to reverse engineer. Now that I'm running into more complex code, I've decided that the break's over, and I'm returning to work on the MADS engine again. For that, at least, the code seems somewhat simpler, even if it can be a pain to run in the DOSBOX debugger because the segments keep getting shifted around in memory. ;)

For those of you who are Ringworld fans, don't worry, I'll still be working on the engine. It's just there won't be as rapid a progress on it as I'd recently hoped.

My first posting

Welcome, everyone, to my new blog. I figured that since blogs have been becoming popular in the ScummVM community lately, I might as well start my own as well. My interests lie in disassembling and reverse engineering old adventure games, and then re-implementing them in ScummVM.

For this inaugural blog post, I'd like to talk about one of my latest projects - working on the MADS/M4 engine. I'm concentrating mainly on the MADS side of the engine at the moment, which was the game engine used for the three games - Rex Nebular, Dragonsphere, or Return of the Phantom, what the current status is of the engine.

I've been concentrating primarily on disassembling Rex Nebular - the game itself is split into a series of executables to save space:

• mainmenu.exe - Which contains the logic for the main menu
• animview.exe - Which contains the logic for displaying cutscenes, like the intro and ending animations
• textview.exe - Which contains the logic for displaying scrolling text, as in the credits and quotes.
• nebular.exe - The actual game itself.

So far, I've spent time disassembling the various executables, excluding the game executable, which I'll get onto in a moment, and along with work done by MD5 and others, we've got the main menus showing for Rex Nebular and Dragonsphere, as well as the scrolling credits and partial support for the cut-scene animations.

The next big step now was to start disassembling the main game executables to figure out all the in-game logic. This was when I'd hit a big stumbling block.. In order to properly understand a game, you have to be able to disassemble it in a dissassembler in it's entirety, so you can start identifying methods and variables, and gradually build up an understanding of how the game works. In the case of the actual game executable, though, all three games had been compiled with an overlay manager called RTLink/Plus, which was designed to save memory by swapping parts of the program code in and out of memory on the fly at runtime.

This therefore made the game difficult to disassemble, because:
1) The functions calls and jumps between code in different segments went via an intermediate table which was dynamically filled in at runtime
2) The data segment was in the middle of the program - this posed a problem because programs typically have the data segment at the end of the program, to allow for uninitialised data areas - space for variables which don't have an explicit value set at startup, so don't need to be part of the executable image.

As such, I was forced to write a program, which I've named rtlink_decode to handle these executables. I'm really quite proud of it - it takes in an executable, and presuming that it detects that is was compled with RTLink/Plus, creates a new executable with the following changes:
1) It detects all the dynamic segments and adds in relocation entries to the executable so that all segment references within these segments are treated like normal code segments
2) Processes the table used for inter-segment calls to fix them to go to the correct segment (what RTLink would have done dynamically at runtime wherever it loaded a segment)
3) Shifts the data segment to the end of the executable, and adjusts any data segment references in the executable to point to the new position.

The result is a new executable which was able to be fully disassembled by IDA Free - which I strongly recommend as a wonderful disassembler for anyone who's thinking about experimenting with reverse engineering.

Now that I've got a clean complete disassembly to work with, I can start figuring out the game logic. This time, though, I won't be starting from scratch - there is shared code between the game executables and the menu, credits, and animation executables, so I've already been able to identify a lot of runtime library methods, as well as other MADS methods I'd previously already figured out.

Nevertheless, it's likely still going to be a while before there's enough disassembled that any major functionality can be implemented into ScummVM, so you'll need to be patient.