Galaxian Part 7 - Preliminary Impressions

Whilst I've been waiting for Miro to digest the previous posts and hopefully develop his framework to the point I have described, I've actually been doing a little bit of the transcode. I'm not going to go into any specifics here as I'd like to document it in some form of ordered fashion, but I will make a few observations, if for no reason other than hinting that I haven't yet abandoned the project.

If there was ever any shadow of a doubt that Scramble was based on the Galaxian codebase (and there really wasn't), it is beyond question in my mind now.

It of course helps that Scott Tunstall reverse-engineered both games - and hence the disassemblies use common terminologies and labels - but there are plenty of instances where those identically-named variables actually share the same address in both games.

Despite having transcoded only a handful of routines thus far, I've already encountered common code. And it's very clear that both games also share the overall architecture of the code. It's an absolute certainty that Scramble code was derived from the Galaxian codebase.

Now that bodes well for the project. Aside from the obvious advantages that a familarity with the architecture presents, I can also say with confidence that the assembler code lends itself very nicely to a higher level implementaion. And that's certainly not true of all assembly code.

And touching on the subject of process I discussed in Part 5, I'm happy so far with how things are turning out when preserving the original assembly code interleaved with the C code. During the course of this blog I'll be posting examples to illustrate various aspects of the transcode, and you can make your own mind up, but I think it adds more than it detracts from, for example, the 'cleanliness' of the higher level source file.

At this stage of the transcode, particularly given the architecture of Galaxian, there is a lot of tedious typing to be done; defining functions and their prototypes, adding variables to the working RAM structure, defining tables etc. I'll likely press on with this aspect of the transcode whilst waiting for Miro, so I can't at this point say when I'll post the next blog entry.

Galaxian Part 6 - Verifying the framework

Before we start on the transcode proper, it would be prudent to test the display output portion of the framework, as this is what we will be using to verify the transcode itself. The purpose is to verify the conversion of the graphics palette, tile and sprite data, the ability to display tiles and sprites, and that the correct output is displayed from the tile memory and attribute areas. Correct output from the sprite registers would also be nice, but is also slightly more complicated and not critical at this point.

First step is to simply dump the tiles and sprites to the display, using the same mechanisms that the ported game will employ. For my Allegro prototype platform, that's copying a region of my sprite sheets for each of the 256 8x8 tiles or 64 16x16 sprites from a memory bitmap to the display. The output for Galaxian looks like this:

Galaxian Tiles and Sprites

Next step is to render a display directly from the Galaxian tile memory (character RAM or CRAM at 5000h) and tile attribute memory (object RAM or OBJRAM at 5800h). Note that the OBJRAM also contains the sprite registers, so these could also be rendered. This is essentially implementing the function that will update the Galaxian display as the game is running, and requires detailed knowledge of the CRAM and OBJRAM structures and mappings; an exercise I'll leave to the reader.

We of course need some (sensible) data in the CRAM and OJBRAM memory blocks, and the easiest way to do this is to run MAME with the debugger enabled, invoke the debugger at an aesthetically interesting point in the game, and SAVE the entire Z80 address space to a file. Then it's simply a matter of reading the binary dump at startup, copying the RAM and OBJRAM areas to suitable buffers if required, and calling the display routine. You should see something like this:

Eye candy before we've even started!

I think the only sprite visible (active) in this dump was the player's laser atop the ship - it's not visible here for reasons unknown at this point. But quite obviously this is pretty close to the actual output, although there will be further enhancements required to the display routine later in the process.

Now we can be reasonably confident that once we implement any code that writes to CRAM and/or OBJRAM, it will be faithfully rendered on the host platform display. Take a good look now, because it's likely going to be quite a few weeks before we see anything like this particular output again!

And that's it for the preliminary work. Next up is to start the actual transcode. No better place to start than the Z80 reset address, 0000h, which we'll implement in the galaxian () function called when the framework has been initialised and we're ready to execute the game.

Galaxian Part 5 - Goals, Aims & Notes on the process

Before we dive into the actual transcode, I wanted to document a few things about the goals and aims of the project, along with some notes about the process.

Goals and Aims

First and foremost, the aim of the project is to document and preserve both the behaviour and the implementation of the original code which, not surprisingly, tend to go hand-in-hand.

Preserving the behaviour means that the transcode will look, sound and play identically to the original. This is pretty much implicit in a transcode, as opposed to a port, since you're translating the code from one language to another. It is in fact the next closest you can get to an emulation.

Documenting & preserving the implementation is also somewhat implicit in a transcode, but not necessarily 100% guaranteed. It is possible to take some liberties with the code, taking advantage of features and/or efficiencies in a higher-level language and more powerful host platform. A transcode that literally mimics Z80 register operations, for example, may be inherently accurate but is not particularly useful; it does little more than the original ASM code in terms of documenting the implementation and also obscures the underlying program design with a tediously verbose reimplementation.

It makes much more sense to make full use of aptly named C variables and data structures, C constructs such as if/else, switch statements and while/for loops, and passing parameters to C functions.

It's important though to avoid any code enhancements that modify the underlying algorithms, even if there are underlying inefficiencies or even bugs! If the ASM code happens to inadvertantly check the same condition twice within some code paths - replicate that in the C code. If the ASM code uses a clumsy sequence of instructions to calculate various conditions - replicate that in the C code. If there's a bug that causes stray pixels on the screen in some cases (Knight Lore on the ZX Spectrum) - replicate that in the C code! We want the authentic experience, not a sanitised one!

The real trick is finding the balance; implementing the original intention as faithfully as possible whilst taking advantage of the higher level language, optimising out the (generally few) insignificant details and preserving the important ones. And this is of course all subjective!

Secondly, another major goal of the project is to produce a high level implementation that is as easily ported to as many (generally more capable) systems as possible. Keep the C code as simple and as platform-independent as possible, avoiding potential data size and endianity issues. As a rule I use integer data types as defined in <stdint.h> and avoid bitfields altogether.

As an aside, the caveats I've encountered tend to be overflow and signed/unsigned nuances of the original CPU and the host platform C implementations. Certain 6502 condition codes for example are particularly mind-bending.

The process

It's worth documenting a few notes about the process that I've found to be useful along the way.

Any relatively complete reverse-engineering (RE) will have labels for all the memory locations in use, and names for all the functions. These labels and names we want to use verbatim in the C transcode.

In the past, and admittedly a legacy of the 6502 zero-page register space, I've created a C structure to contain all the memory variables in a program. This is perhaps a little verbose and can be terribly inefficient on some host platforms if you attempt to use alignment and/or packing to facilitate certain nuances of general assembly programming (eg clearing or copying blocks of memory). Still in two minds about this, but thus far it hasn't caused any insurmountable problems. Regardless, there's a C variable for each and every memory location referenced by the program, named exactly the same as the RE, generally of the same type & size (though sometimes optimised), and in ascending memory address order. This may be an important implementation detail.

Likewise, functions mirror those in the RE and have identical names, and are defined in the same order as in the original code. I even preclude each with a comment containing the ASM address for reference. The main difference is that functions may have arguments - typically but not limited to pointers and data values passed in CPU registers in the ASM code - and sometimes even a return value.

These practices make it easier to reference functionality back to the ASM source, either during development or perhaps at a later date by someone studying the implementation of the original code.

Over the course of the last few projects I've refined the process incrementally. Significantly, I'd start with the RE source file and prepend each and every line with a C++ comment. Effectively, the file would then compile to nothing. I'd then start the transcode by adding C functions at the corresponding lines in the file, just below the ASM routine, referencing the code as I wrote the C equivalent. Once each function was completed and debugged, I'd actually delete the ASM routine from the file. End result is pure C code.

At some point during the Scramble transcode, I found it useful to include snippets of the commented ASM code to document what I'd done and/or why I'd done it that way. Or to preserve unused routines or data for future reference. By the end of the transcode, I was considering that perhaps it would be advantageous to leave all the original ASM code in the file, even interleaved within blocks of code in the functions, to provide a definitive reference. And to possibly assist in identification of bugs in the transcode should they become apparent only some time after the fact.

And so for Galaxian, I think I'll start out on this route. By prepending with a C++ style comment and some obscure but visually subtle sequence of characters, the possibility to completely strip the ASM code from the C code with just a few keystrokes would be retained.

Hopefully what I've described here will become more clear when we get into the transcode and I can provide a few concrete examples of transcoded data variables and functions.

Next up, in what will likely be the last part before we get to the transcode proper, I'll detail the process of testing the framework in readiness to start on the real work.

Galaxian Part 4 - Rounding out the framework for a port/transcode

Some of what I'll discuss is more pertinent to C than it is to Javascript. But there's no reason why you couldn't adopt the same architecture in Javascript anyway. In fact, it may still be a good idea for a couple of reasons, including future porting, or even enhancement much like the 'DX' emulations popular for a brief amount of time a ways back.

The main aim is to produce a C transcode of Galaxian core logic that is completely platform-independent; in this case a single C source file with just two entry points - the main function galaxian (), and the interrupt handler galaxian_nmi () - that can be included verbatim on each and every host platform port, whether that be PC, Neo Geo, Amiga etc. Not unlike the MAME driver, for example.

Coupled with this are a set of functions that are implemented in an OS-dependent file that are called from the core source file above. The functions include hardware I/O for reading dipswitch settings, control panel inputs (joystick, buttons) and miscellaneous hardware such as interrupt enable/disable, sound registers etc and of course graphics (display) output. Again, much like the MAME driver.

Here's a breakdown of the source files in my Galaxian project:

• galaxian.c/h
• galaxian_gfx.c
• debug.c/h
• galaxian_osd.h
• main.cpp

As discussed, galaxian.c/h implements the platform-independent Galaxian core transcode with galaxian () and galaxian_nmi () entry points. The header contains prototypes for these two functions, plus any data structures or defines that are also required in the main.cpp file.

The galaxian_gfx.c file is the output of the graphics conversion utility discussed in Part 2 and referenced by main.cpp only.

The debug.c/h are simply auxiliary files used during development to implement any debug functions that may assist in the process. These may include functions to dump data structures for example.

The galaxian_osd.h header file contains prototypes for functions implemented in main.cpp. There is only one version of this file and is included on all host platforms.

Finally, main.cpp is where all the platform-dependent code is implemented that actually makes things happen on the host platform. Here the environment is initialised, the framework initialised (create timers and threads, for example), inputs like the PC keyboard mapped to Galaxian hardware I/O addresses, outputs like Galaxian hardware I/O addresses controlling sound mapped to host sound functions, and finally memory mapped areas like video attribute & tile data and sprite registers hooked to host graphics functions. This is the one and only file for which each host platform has its own version!

Since main.cpp is where everything is initialised and where the core is connected to inputs and outputs, most of the functionality is likely to be implemented fairly early-on in the transcode. Host platform initialisation aside, the graphics output is going to be the first functionality that is coded, because we want (need) to see what's happening in the Galaxian code as we transcode. Whilst we can ignore, or at least defer, other I/O like sound outputs and dipswitch or control panel inputs, it's likely we'll at least have to implement some stub code to return default (inactive) input values.

So for the bulk of the time (and effort) in this project, the only file we need to work on is galaxian.c.

For the most part, the core code directly interacts with the host platform hardware when it calls into the OS-dependent (osd) functions. For example when reading from the joystick input port, the osd function in main.cpp will read the state from the PC keyboard, translating back to port bits for the core to manipulate. Similarly when muting sound output for example, the osd function may toggle host sound on/off depending on the state of a control bit written by the core.

For the video though, we may not necessarily want to do this. We may wish to, for example, synchronise host video updates with the host VBLANK as provided in host graphics libraries.

As discussed in Part 3, the first thing Galaxian does in the NMI is update tile attribute (colour & scroll) registers and sprite registers. This avoids flickering and tearing as the beam is still in the vertical retrace at the start of the NMI. It does this by a block copy from a memory buffer into the tile attribute and sprite register memory space (aka object RAM or OBJRAM).

Writing to OBJRAM requires osd functions because ultimately it's accessing hardware, but there are a few options for exactly what is implemented in the osd function, and to some extent depends on the host platform and how the framework is implemented. I've chosen to simply store it in an intermediate buffer which is subsequently used to update the tiles and sprites on the screen elsewhere in the NMI handling of the framework, for maximum flexibility.

Similarly, writing to the tilemap (character RAM aka CRAM) also requires an osd function and again I've chosen to write it to an intermediate buffer and update the host display elsewhere. However I would note that Galaxian does not update the CRAM during VBLANK, so it would be perfectly acceptable to have the osd function update the host display then and there. There's no right or wrong solution here.

So that's pretty much all there is to the framework. Ideally we have a single core Galaxian C implementation and just a single cpp file that must be implemented for each host platform that for the most part handles inputs and graphics. Porting to subsequent hosts should be almost trivial!

Next I'll discuss some of the main aims of the transcode and the general architecture of the galaxian.c implementation. I've actually found my transcodes to be an evolving process and as a result of my most recent Scramble project I'll be tweaking again it for this project.

Galaxian Part 3 - Anatomy of an arcade game

Before we can create a framework for the transcoded game, we need to understand the architecture of the original.

Every single arcade game that I have reverse-engineered thus far has been driven by the 60Hz VBLANK interrupt. Not only does this allow the game to update the sprites without any flicker or tear, it also serves as a reliable, periodic timer on which to base the speed of the game. Galaxian is no exception.

So in a game like Galaxian, there are two contexts of code execution; the 60Hz VBLANK interrupt, which is wired to the Z80's NMI and causes the CPU to execute code at address 0066h, and the main code which starts executing at address 0000h when the CPU is reset and runs (continues) after the aforementioned NMI handler routine is finished until it fires again.

Aside from various hardware functions, the NMI handler contains all the processing in the game that affects, and is affected by, the speed that the game is running. This would include things like player movement, enemy AI, player shots and bullets etc. Typically the NMI would also update the physical display, handle in-game timers, control sound and debounce inputs for example.

As for Galaxian specifically, it does the following:

• updates the tilemap attributes (colours and scroll registers) and sprites from a memory buffer
• reads and debounces player control inputs
• updates a system timer variable
• checks for and handles coins
• updates sounds
• scrolls text, and finally
• runs the game state machine(s); handling title screens, attract mode and game mechanics such as AI, movement, bullets, exploding etc and in the process updating the memory buffer with tile attribute and sprite data for the next screen refresh (NMI).

So what is left for the main code to do then? In Galaxian the main code performs functions such as printing text, scores etc on the screen, and also removing aliens from the swarm as they dive, and adding them back to the swarm if they return. The main code does all the updating of the tilemap contents (the actual characters you see on the screen).

In Galaxian there is a command queue, implemented via a circular buffer, that is written by the NMI and read by the main code, which allows the NMI to, well, queue a number of commands to be performed by the main code between interrupts. For example, whenever a player shoots an alien - which is processed by the NMI - the NMI can queue a command to update the player score.

It may be worth noting here that Galaxian assumes that there will always be sufficient time for the main code to empty the command queue before the next interrupt, as there is no concurrency protection around the queue pointer manipulation in the main code. Not so much an issue in a controlled environment such as the Galaxian arcade machine hardware; a different matter perhaps on a modern, mutli-tasking platform.

I could say plenty more about the architecture of the Galaxian code itself, but I've detailed enough to put together a framework for a transcode/port on another platform. Simply put, executing the game should ultimately end up executing the main code, whilst a periodic 60Hz timer/interrupt should execute the NMI code. Ideally, the NMI should (also) suspend execution of the main code just as on the Z80, but it's also possible to minimise (but not eliminate altogether) issues when prototyping by use of a few mutexes for the command queue processing. I learnt this lesson during the Scramble transcode.

For my prototype on the PC, my main function sets up the environment under Allegro, including all the graphics as mentioned in Part 2), and a 60Hz timer with a callback that subsequently calls the NMI code in the transcode, galaxian_nmi(). It then creates a thread that calls the main function in the transcode, galaxian (), and finally starts the timer.

Next I'll round out discussion of the framework, including handling hardware I/O and video updates.

Galaxian Part 2 - Graphics formats

The format of the graphics in an arcade game like Galaxian is optimised for the video circuitry rendering the image as the raster beam scans down the screen.

Specifically for Galaxian, the graphics data for each bitplane is stored in a separate device (ROM chip) so that colour data for each pixel can be accessed in parallel, and data for one line of each (8x8) tile is contained in a single byte from each device. Additionally, Galaxian has a vertical monitor, which means pixel ordering differs from, for example, a PC with a horizontal monitor; a straight dump of the graphics data results in the images rotated 90 degrees and in some cases, also mirrored.

This of course isn't very convenient at all for a machine like a PC that may be emulating the game. Here is a snippet of the macro-filled array that MAME uses to construct tile data from the original graphics ROMS:

static const gfx_layout galaxian_charlayout =
{
8,8,
RGN_FRAC(1,2),
2,
{ RGN_FRAC(0,2), RGN_FRAC(1,2) },
{ STEP8(0,1) },
{ STEP8(0,8) },
8*8
};

There's little point going into an explanation here, but suffice it to say it's not an ideal starting point to convert the graphics into whatever format the host language/environment/platform requires.

Arguably the easiest format to start with is a 1 byte-per-pixel (bpp), pre-rotated, array in C. From there, it is much easier to convert to another format, whether that be rendered directly into memory bitmaps for the Allegro graphics library, or re-arranged into binary ROM images for the Neo Geo.

And so, first order of business was to rip the graphics from the Galaxian ROM images into the abovementioned C array. Once for the 8x8 tiles, once again for the 16x16 sprites - both of which are stored in the same ROM (we have several orders of magnitude more space to work with on modern machines). A small C program that outputs a C source file did the trick. At the same time I also added the colour PROM data, converted to platform-independent RGB values.

Here's what the output for a tile looks like:

uint8_t tile[256][64] =
{
  // $00
  {
    0x00, 0x00, 0x00, 0x03, 0x03, 0x03, 0x00, 0x00,     //    ###  
    0x00, 0x00, 0x03, 0x00, 0x00, 0x03, 0x03, 0x00,     //   #  ## 
    0x00, 0x03, 0x03, 0x00, 0x00, 0x00, 0x03, 0x03,     //  ##   ##
    0x00, 0x03, 0x03, 0x00, 0x00, 0x00, 0x03, 0x03,     //  ##   ##
    0x00, 0x03, 0x03, 0x00, 0x00, 0x00, 0x03, 0x03,     //  ##   ##
    0x00, 0x00, 0x03, 0x03, 0x00, 0x00, 0x03, 0x00,     //   ##  # 
    0x00, 0x00, 0x00, 0x03, 0x03, 0x03, 0x00, 0x00,     //    ###  
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,     //         
  },

Note that I added the 'ASCII art' rendering of the tiles to both serve as documentation, and a sanity check that the conversion was correct.

Since I am prototyping the transcode on the PC using the Allegro graphics library, I need simply to incorporate the output of my conversion utility into the build and the raw, platform-indepedent graphics data is included in the program. And in this particular case, the startup code for the Galaxian port will read the graphics array, initalise the palettes and render the tiles & sprites into memory bitmaps to be blitted to the screen at run time.

I'm hoping that Miro will be able to use a similar technique for Javascript, in which case I'll tweak my utility to (also) output a Javascript source file. If not, Miro should at least be able to write a small utility to convert the same data into something he can use to render the graphics.

For porting to systems that read graphics data directly from ROMS for example, that C file would be included in a small utility that produced the respective ROM file images. This is something I did for Scramble on the Neo Geo.

So now we have all the graphics data in a source file that can be rendered - directly or indirectly - onto the host platform display. Exactly what we need to be able to check the progress of the transcode.

Next step is to get a project and software framework for the game up and running, and I generally write some test code to render all the tiles and sprites as a sanity check.

Galaxian Part 1 - Introduction

A fellow retro enthusiast by the name of Miro expressed interest in the porting (transcoding) of Sean Riddle's Galaxian dissassembly to a higher level language and asked if anyone was willing to collaborate. Given that the codebase is very similar to Scramble, and the hardware identical, I thought I'd be a decent candidate for the job. I know the Scramble starmap isn't finished on the Neo Geo, but I figured since I'd need to do it for Galaxian anyway, there would be no harm starting this new project.

I'm going to try to document more of the process this time around, rather than focus on progress. I'll still write about any interesting aspects of the code, or issues with the transcode, but I'm hoping this will serve as a reference/instruction for Miro and anyone else interested in giving something like this a go.

Miro's expertise is not in Z80 assembler (the point of the exercise for him) or C, so he will be porting/transcoding to Javascript. Given I know very little about Javascript, I'm hoping my process is compatible with what he needs to do. It'll certainly be an interesting experiment.

I'll be able to start with the bones of the Scramble project. In fact, for me it's pretty much a case of renaming a few files and high-level functions, ripping new graphics, and replacing my monolithic transcode of Scramble with that of Galaxian. And tonight I did just that. My makefile now builds both Scramble and Galaxian executables; it's just that Galaxian looks very much like Scramble atm - I'd even go as far as to say identical! ☺

In my next post I'll talk about ripping the graphics and the format I've chosen.