What about SIGN between TERM1 and TERM3? Again, have a look at Equations 13.3–13.6. To compute the two new coordinates after a rotation, the SIGN toggles from plus to minus and vice versa. The SIGN is initialized with the value of JOYSTICKDELTA ($6D) before calling subroutine ROTATE ($B69B, page 621) and is toggled in every call of this subroutine. The initial value of SIGN should be positive (+, byte value $01) if the rotation is clockwise (the joystick is pushed right or up) and negative (—, byte value $FF) if the rotation is counter-clockwise (the joystick is pushed left or down), respectively. Because SIGN is always toggled in ROTATE ($B69B) before the adding or subtraction operation of TERM1 and TERM3 takes place, you have to pass the already toggled value with the first call.
Unclear still are three instructions starting at address $B6AD. They seem to set the two least significant bits of TERM3 in a random fashion. Could this be some quick hack to avoid messing with exact but potentially lengthy two’s-complement arithmetic?
Dodging Memory Limitations
It is impressing how much functionality was squeezed into STAR RAIDERS. Not surprisingly, the bytes of the 8 KB ROM are used up almost completely. Only a single byte is left unused at the very end of the code. When counting four more bytes from three orphaned entries in the game’s lookup tables, only five bytes in total out of 8,192 bytes are actually not used. ROM memory was extremely precious. Here are some techniques that demonstrate the fierce fight for each spare ROM byte.
Loop Jamming
Loop jamming is the technique of combining two loops into one, reusing the loop index and optionally skipping operations of one loop when the loop index overshoots.
How much bytes are saved by loop jamming? As an example, Figure 13.3 shows an original 19-byte fragment of subroutine INITIALIZE ($B3BA) using loop jamming. The same fragment without loop jamming, shown in Figure 13.4, is 20 bytes long. So loop jamming saved one single byte.
Another example is the loop that is set up at $A165 in INITCOLD ($A14A). A third example is the loop set up at $B413 in INITIALIZE ($B3BA). This loop does not explicitly skip loop indices, thus saving four more bytes (the CMP and BCS instructions) on top of the one byte saved by regular loop jamming. Thus, seven bytes are saved in total by loop jamming.
Figure 13.3: INITIALIZE Subroutine at $B3BA (Excerpt)
Figure 13.4: INITIALIZE Without Loop Jamming (Excerpt)
Sharing Blank Characters
One more technique to save bytes is to let strings share their leading and trailing blank characters. In the game there is a header text line of twenty characters that displays one of the strings “LONG RANGE SCAN,” “AFT VIEW,” or “GALACTIC CHART.” The display hardware directly points to their location in the ROM. They are enclosed in blank characters (bytes of value $00) so that they appear horizontally centered.
A naive implementation would use 3 × 20 = 60 bytes to store these strings in ROM. In the actual implementation, however, the trailing blanks of one header string are reused as leading blanks of the following header, as shown in Figure 13.5. By sharing blank characters the required memory is reduced from 60 bytes to 54 bytes, saving six bytes.
Figure 13.5: Header Texts at $AOFA
Figure 13.6: VBIHNDLR and DLSTHNDLR Handlers Share Exit Code
Reusing Interrupt Exit Code
Yet another, rather traditional technique is to reuse code, of course. Figure 13.6 shows the exit code of the Vertical Blank Interrupt handler VBIHNDLR ($A6D1) at $A715, which jumps into the exit code of the Display List Interrupt handler DLSTHNDLR ($A718) at $A74B, reusing the code that restores the registers that were put on the CPU stack before entering the Vertical Blank Interrupt handler.
This saves another six bytes (PLA, TAY, PLA, TAX, PLA, RTI), but spends three bytes (JMP JUMP004), in total saving three bytes.
Bugs
There are a few bugs, or let’s call them glitches, in STAR RAIDERS. This is quite astonishing, given the complex game and the development tools of 1979, and is a testament to thorough play testing. The interesting thing is that the often intense game play distracts the players’ attention away from these glitches, just like what a skilled parlor magician might do.
A Starbase Without Wings
When a starbase reaches the lower edge of the graphics screen and overlaps with the Control Panel Display, and you nudge the starbase a little bit more downward, its wings suddenly vanish. (Figure 13.7.)
The reason is shown in the insert on the right side of the figure: The starbase is a composite of three Players (sprites). Their bounding boxes are indicated by three white rectangles. If the vertical position of the top border of a Player is larger than a vertical position limit, indicated by the tip of the white arrow, the Player is not displayed. The relevant location of the comparison is at $A534 in GAMELOOP ($A1F3). While the Player of the central part of the starbase does not exceed this vertical limit, the Players that form the starbase’s wings do so, and are thus not rendered.
This glitch is rarely noticed because players do their best to keep the starbase centered on the screen, a prerequisite for a successful docking.
Shuffling Priorities
There are two glitches that are almost impossible to notice, and I admit some twisted kind of pleasure in exposing them. During regular gameplay, the Zylon ships and the photon torpedoes appear in front of the cross hairs, as if the cross hairs were light years away. (Figure 13.8 Left.) During docking, the starbase not only appears behind the stars as if the starbase is light years away, but the transfer vessel moves in front of the cross hairs! (Figure 13.8 Right.)
Figure 13.7: A Starbase’s Wings Vanish
Figure 13.8: Photon torpedo in front of cross hairs and a starbase behind the stars!
The reason is the drawing order or “graphics priority” of the bit-mapped graphics and the Players (sprites). It is controlled by the PRIOR ($D01B) hardware register.
During regular flight, PRIOR ($D01B) has a value of $11. (Figure 13.8 left.) This arranges the displayed elements in the following order, from front to back:
Players 0-4 (photon torpedoes, Zylon ships, . . .)
Bit-mapped graphics (stars, cross hairs)
Background
This arrangement is fine for the stars as they are bit-mapped graphics and need to appear behind the photon torpedoes and the Zylon ships, but this arrangement applies also to the cross hairs, causing the glitch.
During docking, see Figure 13.8 (right), PRIOR ($D01B) has a value of $14. This arranges the displayed elements the following order, from front to back:
Player 4 (transfer vessel)
Bit-mapped graphics (stars, cross hairs)
Players 0-3 (starbase, . . .)
Background
This time the arrangement is fine for the cross hairs as they are bit-mapped graphics and need to appear in front of the starbase, but this arrangement also applies to the stars. In addition, the Player of the white transfer vessel correctly appears in front of the bit-mapped stars, but also in front of the bit-mapped cross hairs.
Fixing these glitches is hardly possible, as the display hardware does not allow for a finer control of graphics priorities for individual Players.
A Mysterious Finding
A simple instruction at location $A175 contained the most mysterious finding in the game’s code. The disassembler reported the following instruction, which is equivalent to STA $0067,X. (ISVBISYNC has a value of $67.)
A175 9D6700 STA ISVBISYNC,X
The object code assembled from this instruction is unusual as its address operand was assembled as a 16-bit address and not as an 8-bit zero-page address. Standard 6502 assemblers would always generate shorter object code, producing 9567 (STA $67,X) instead of 9D6700 and saving a byte.
In my reverse engineered source code, the only way to reproduce the original object code was the following:
I speculated for a long time whether this strange assembler output indicated that the object code of the original ROM cartridge was produced with a non-standard
6502 assembler. I have heard that Atari’s in-house development systems ran on PDP-11 hardware. Luckily, the month after I finished my reverse engineering effort, the original STAR RAIDERS source code re-surfaced.9 To my astonishment it uses exactly the same hack to reproduce the three-byte form of the STA ISVBISYNC,X instruction:
Unfortunately the comments do not give a clue why this pattern was chosen. After quite some time it made click: The instruction STA ISVBISYNC,X is used in a loop which iterates the CPU’s X register from 0 to 255 to clear memory. By using this instruction with a 16-bit address (“indexed” mode operand) memory from $0067 to $0166 is cleared. Had the code been using the same operation with an 8-bit address (“indexed, zero-page” mode operand), memory from $0067 to $00FF would have been cleared, then the indexed address would have wrapped back to $0000 clearing memory $0000 to $0066, effectively overwriting already initialized memory locations.
Documenting Star Raiders
Right from the start of reverse engineering STAR RAIDERS I not only wanted to understand how the game worked, but I also wanted to document the result of my effort. But what would be an appropriate form?
First, I combined the emerging memory map file with the fledgling assembly language source code in order to work with just one file. Then, I switched the source code format to that of MAC/65, a well-known and powerful macro assembler for the Atari 8-bit Home Computer System. I also planned, at some then distant point in the future, to assemble the finished source code with this assembler on an 8-bit Atari.
Another major influence on the emerging documentation was the Atari BASIC Source Book, which I came across by accident.10 It reproduced the complete, commented assembly language source code of the 8 KB Atari BASIC interpreter cartridge, a truly non-trivial piece of software. But what was more: The source code was accompanied by several chapters of text that explained in increasing detail its concepts and architecture, that is, how Atari BASIC actually worked. Deeply impressed, I decided on the spot that my reverse engineered STAR RAIDERS source code should be documented at the same level of detail.
The overall documentation structure for the source code, which I ended up with was fourfold: On the lowest level, end-of-line comments documented the functionality of individual instructions. On the next level, line comments explained groups of instructions. One level higher still, comments composed of several paragraphs introduced each subroutine. These paragraphs provided a summary of the subroutine’s implementation and a description of all input and output parameters, including the valid value ranges, if possible. On the highest level, I added the memory map to the source code as a handy reference. I also planned to add some chapters on the game’s general concepts and overall architecture, just like the Atari BASIC Source Book had done. Unfortunately, I had to drop that idea due to lack of time. I also felt that the detailed subroutine documentation was quite sufficient. However, I did add sections on the 3D coordinate system and the position and velocity vectors to the source code as a tip of the hat to the Atari BASIC Source Book.
After I was well into reverse engineering STAR RAIDERS, slowly adding bits and pieces of information to the raw disassembly of the STAR RAIDERS ROM and fleshing out the ever growing documentation, I started to struggle with establishing a consistent and uniform terminology for the documentation (Is it “asteroid,” “meteorite,” or “meteor?” “Explosion bits,” “explosion debris,” or “explosion fragments?” “Gun sights” or “cross hairs?”) A look into the STAR RAIDERS instruction manual clarified only a painfully small amount of cases. Incidentally, it also contradicted itself as it called the enemies “Cylons” while the game called them “Zylons,” such as in the message “SHIP DESTROYED BY ZYLON FIRE.”
But I was not only after uniform documentation, I also wanted to unify the symbol names of the source code. For example, I had created a hodge-podge of color-related symbol names, which contained fragments such as “COL,” “CLR,” “COLR,” and “COLOR.” To make matters worse, color-related symbol names containing “COL” could be confused with symbol names related to (pixel) columns. The same occurred with symbol names related to Players (sprites), which contained fragments such as “PL,” “PLY,” “PLYR,” “PLAY,” and “PLAYER,” or with symbol names of lookup tables, which ended in “TB,” “TBL,” “TAB,” and “TABLE,” and so on. In addition to inventing uniform symbol names I also did not want to exceed a self-imposed symbol name limit of 15 characters. So I refactored the source code with the search-and-replace functionality of the text editor over and over again.
I noticed that I spent more and more time on refactoring the documentation and the symbol names and less time on adding actual content. In addition, the actual formatting of the emerging documented source code had to be re-adjusted after every refactoring step. Handling the source code became very unwieldy. And worst of all: How could I be sure that the source code still represented the exact binary image of the ROM cartridge?
The solution I found to this problem eventually was to create an automated build pipeline, which dealt with the monotonous chores of formatting and assembling the source code, as well as comparing the produced ROM cartridge image with a reference image. This freed time for me to concentrate on the actual source code content. Yet another incarnation of “separation of form and content,” the automated build pipeline was always a pleasure to watch working its magic. (Mental note: I should have created this pipeline much earlier in the reverse engineering effort.) These are the steps of the automated build pipeline:
The pipeline begins with a raw, documented assembly language source code file. It is already roughly formatted and uses a little proprietary markup, just enough to mark up sections of meta-comments that are to be removed in the output as well as subroutine documentation containing multiple paragraphs, numbered, and unnumbered lists. This source code file is fed to a pre-formatter program, which I implemented in Java. The pre-formatter removes the meta-comments. It also formats the entries of the memory map and the subroutine documentation by wrapping multi-line text at a preset right margin, out- and indenting list items, numbering lists, and vertically aligning parameter descriptions. It also corrects the number of trailing asterisks in line comments, and adjusts the number of asterisks of the box headers that introduce subroutine comments, centering their text content inside the asterisk boxes.
The output of the pre-formatter from step 1 is fed into an Atari 6502 assembler, which I also wrote in Java. It is available as open-source on GitHub.11 Why write an Atari 6502 assembler? There are other 6502 assemblers readily available, but not all produce object code for the Atari 8-bit Home Computer System, not all use the MAC/65 source code format, and not all of them can be easily tweaked when necessary. The output of this step is both an assembler output listing and an object file.
The assembler output listing from step 2 is the finished, formatted, reverse engineered STAR RAIDERS source code, containing the documentation, the source code, and the object code listing.
The assembler output listing from step 2 is fed into a symbol checker program, which I again wrote in Java. It searches the documentation parts of the assembler output listing and checks if every symbol, such as GAMELOOP, is followed by its correct hex value, $A1F3. It reports any symbol with missing or incorrect hex values. This ensures further consistency of the documentation.
The object file of step 2 is converted by yet another program I wrote in Java from the Atari executable format into the final Atari ROM cartridge format.
The output from step 5 is compared with a reference binary image of the original STAR RAIDERS 8 KB ROM cartridge. If both images are the same, then the entire build was successful: The raw assembly language source code really represents the exact image of the STAR RAIDERS 8 KB ROM cartridge
Typical build times on my not-so-recent Windows XP box (512 MB) were fifteen seconds.
For some finishing touches, I ran a spell-checker over the documented assembly language source code file from time to time, which also help
ed to improve documentation quality.
Conclusion
After quite some time, I achieved my goal of creating a complete, reverse engineered, and fully documented assembly language source code of STAR RAIDERS. For final verification, I successfully assembled it with MAC/65 on an Atari 800 XL with 64 KB RAM (emulated with Atari800Win Plus). MAC/65 is able to assemble source code larger than the available RAM by reading the source code as several chained files. So I split the source code (560 KB) into chunks of 32 KB and simply had the emulator point to a hard disk folder containing these files. The resulting assembler output listing and the object file were written back to the same hard disk folder. The object file, after being transformed into the Atari cartridge format, exactly reproduced the original STAR RAIDERS 8 KB ROM cartridge.
Postscript
I finished my reverse engineering effort in September 2015. I was absolutely thrilled to learn that in October 2015 scans of the original STAR RAIDERS source code re-surfaced. To my delight, inspection of the original source code confirmed the findings of my reverse engineered version and caused only a few trivial corrections. Even more, the documentation of my reverse engineered version added a substantial amount of information—from overall theory of operation down to some tricky details—to the understanding of the often sparsely commented original.
PoC or GTFO, Volume 2 Page 34