Apple2TC: an Apple II Binary to C Decompiler - Part 5

 This is part 5 in a series of posts describing Apple2TC. 

The start is in Part 1.

Part 4 described the Apple II hacks we had to deal with, in order to get the decompiled version of Applesoft BASIC working.

This part is a quick update on getting two Apple II games to work - Robotron 2084 and Snake Byte.

Robotron 2048

After all the effort we went through for the BASIC ROM, Robotron 2048 was shockingly easy.

First, we ran a2emu to collect runtime data:

a2emu --collect --limit=30000000 robotron.b33 > robotron.json

In the emulator, the game title screen appeared, we eagerly pressed spacebar, getting us to the control selection screen, selected keyboard, and we were off. The game is pretty challenging, but we managed to play a little before dying and closing the emulator.

With the so collected runtime data, first we decompiled the binary to 6502 assembler:

apple2tc --run-data=robotron.json robotron.b33 > robotron.lst

Then to C (with the "simple" backend):

apple2tc --simple-c --run-data=robotron.json robotron.b33 > robotron.c

At that point all we had to do is create a build file, which is pretty simple, build, and run. To our utter shock, it actually worked! The game was fully playable, as can be observed here (yes, this is running the decompiled C code, not the emulator):

It really felt like all prior effort had paid off! We had automatically generated a playable, not emulated (!!!), Apple II game, with just three simple steps! (Of course this is still far from the readable decompiled C that we are aiming for, but it is certainly encouraging). 

After the euphoria wore off and we played the decompiled game a few more times, we found that it would crash, if instead of pressing spacebar right away, we waited for title screen to finish. The real game prints some back story, descriptions of enemies, etc. Our decompiled version just crashed with Unknown code address: $FCA8.

The unknown address $FCA8 is in ROM. The game apparently relies on Apple II ROM routines. In fact the decompiler had already detected it and printed a warning along with another one for $FB1E. We, naturally, had ignored the warnings, because who has time for that...

Looking at our handy Apple II ROM disassembly, these are the routines MON_WAIT and PREAD. Both are quite simple and do not rely on any other code or, more importantly, initialized state.

The first solution we considered was to special-case these addresses, since we know what they do, and then either handle them specially in the Simple C backend, or manually include only those ROM regions in the decompilation. In time we could add more and more routines like that, slowly building a usable subset of the ROM for games.

That unfortunately seemed like a lot of work, and worse, potentially unending manual work, which did not sit well with our ambitions for fully automatic decompilation.

So, we decided to try a simpler, but fully automated, approach first. As soon as the decompiler detects a branch into ROM memory range ($D000-$FFFF), it automatically loads the Apple II ROM and includes it in the decompilation process, as if it was part of the loaded binary. Note that it doesn't decompile the entire ROM, just the entry points that are actually accessed by the game.

That worked amazingly well! Apple2tc detected the missing ROM, loaded it, and decompiled only two needed routines. The resulting game was able to play its full introduction!

All in all, getting Robotron 2084 to work was a very rewarding experience, with the right mix of quick progress, a bit of investigation, and simple coding!

(Note: since then we found that it still crashes with the ESC key during the introduction, but we hope that this is simply because we didn't think to try that key while playing the game. We also have high hopes that with the more advanced decompilation backend will automatically discover unexplored parts of the code by detecting and analyzing jump tables.)

Snake Byte

Snake Byte is another classic Apple II game that we used to play a lot. Decompiling it was quite fun.

After repeating exactly the same steps described above for Robotron 2048 (replacing robotron2084.b33 with snake-byte.b33), we again got a game that was almost working.

The title screen showed correctly and the demo started playing. However the demo was slightly off - the snake behaved erratically, swerved and went through the walls. Pressing spacebar started the actual game, though the snake died almost immediately, as if it had hit a wall, even though it hadn't.

All in all, this still felt like pretty good progress compared to just two weeks ago, when we couldn't run anything. The game was recognizable and felt almost playable.

Looking at the decompiler logs, we noticed that it had auto-loaded the Apple II ROM. We were already benefiting from the improvements brought by running Robotron 2084!

But what to do? Since the game wasn't crashing and was instead just behaving incorrectly, we had to use a brute force approach. 

First, we generated an emulator CPU trace:

a2emu --trace --limit=500000 snake-byte.b33 > goodtrace1.txt

The trace contained instruction names, which we had to strip:

cut -c1..56 goodtrace1.txt > goodtrace.txt

Then we generated a trace from the decompiled game:

snake-byte --trace > badtrace.txt

(By the way, this is where the advantages of the Simple C backend become apparent. Even though the generated code is ugly, verbose and inefficient, its 1-to-1 correspondence to the original 6502 assembly allows us to track down problems like this one.)

Finally, a simple diff to see where the emulator and the decompiled code diverged:

diff -y goodtrace.txt badtrace.txt

The first difference was in register values around PC $F819. This is the BASIC HLINE routine! This game was also calling into BASIC, but this time it looked like the ROM routine was not quite as pure and depended on pre-initialized state in RAM.

So, it looked like we needed the ROM initialization to have happened before we run the game, so the came could then call back into BASIC correctly, relying on the already initialized state.

This took a couple of hours to rig, but was still conceptually simple. We had to extend a2emu with the ability to start collecting data immediately after RESET, and then automatically load a binary and execute it as soon as initialization has completed.

We needed some way to now when initialization finishes. After scanning the Apple II ROM source, we identified the RESTART routine, which gets invoked after BASIC is initialized. We needed to get a notification from the emulator when that happened. 

For that, we added simple breakpoint support to the per-instruction emulator debug handler. It checks a hash table of 16-bit addresses before every instruction and invokes a callback (std::function<>) if a match is hit. 

(The breakpoint check may appear slow, but there is so much performance headroom that it doesn't matter. Plus, the rest of the runtime data collection pipeline is much more complex. Lastly, this is all optional and a2emu doesn't enable it all if not needed.) 

Putting everything together, first we set a break point at RESTART. When the breakpoint is hit, we clear it, then load the binary file in memory. Finally, to start it, we insert the BASIC command "CALL xxxx" in the emulated keyboard buffer, where "xxxx" is the loaded address. As a result, BASIC interprets the CALL as if it was entered from the keyboard and invokes the loaded binary.

This all worked quite well and we obtained runtime data containing both ROM initialization and Snake Byte. When we passed it to the decompiler, it loaded the ROM first thing, because the entry point was in ROM, decompiled parts of the ROM (including parsing of the CALL command) and then finally the game and more parts of the ROM, as the game called back into it.

As a result we had a had a "mixed" decompiled binary containing the ROM initialization, some parts of BASIC, and the entire game. When we started it, we got the normal BASIC prompt. We had to manually type "CALL xxxx" to the game, after which it played correctly and all parts worked!

It was a surreal experience, mixing BASIC and binary, but ultimately it worked exactly as expected. More and more things are starting to come together.

To Be Continued

In Part 6 we introduce the Apple2TC IR, which unlocks much more sophisticated analysis and finally puts us on the road to real decompilation.