Galaksija: Spaghetti

18.02.2007 1:42

Over-optimization does terrible things to the code...

So far I've disassembled and annotated two large chunks of Galaksija's ROM - the video interrupt handler and cassette loading and saving routines. I had to do that to find out how the original hardware worked. Fortunately these two parts were simple to figure out compared to some other parts of the code that resides in that tiny 4K EPROM.

Some parts are written in a way that I would never otherwise consider possible: you probably heard about parts of code that are also used as ASCII strings, but how about jumps that are no not aligned with opcode boundaries? Apart from a handful of documented ROM functions there is almost no structure in the code. A single RET instruction for example can be used as an exit point for tens of separate functions.

To give you some idea of the complexity involved, here are some call graphs. Each box represents a chunk of machine code. Thin black arrows show jumps and loops, thick black arrows show neighboring blocks of code (where execution goes from one block to the other without a jump), red arrows show function calls and blue arrows show calls by RST instructions.

Circular boxes are entry points (two interrupt vectors and a reset vector), rectangular boxes are code in the first 256 bytes of the ROM that can be accessed by RST instructions. Other boxes represent other parts of the code.

This graph is only approximate of course. Various tricks in the code make it impossible to do an accurate static analysis (especially with my 175 line Perl script). Dynamic jumps and jumps not aligned with opcodes for example are not shown or are shown wrong.

Galaksija ROM call graph

Galaksija ROM call graph (detail)

Galaksija ROM call graph (detail)

Here's the original Postscript file I used to create images above. Make sure you have plenty of swap space and a good Postscript interpreter before you open it.

Posted by Tomaž | Categories: Code

Comments

Hi Avian,

I'm interested in how you generated the diagram associated with this post. The Perl script seems not to be accessible. I'd like to be able to generate a similar diagram to help me visualise the wiring for a flight simulator.

Thanks for posting your investigations online. Very interesting reading!

Regards,

Merlin

The image for this blog post was generated with Graphviz. My script only created a description of the graph in DOT language.

http://www.graphviz.org

The script itself is probably lost now - it didn't turned out to be as helpful in reverse engineering as I hoped. It was very specific to Z80 assembly and the particular style of code used in Galaksija ROM so it probably wouldn't be useful to you anyway.

Posted by Tomaž

That's fantastic, thanks. I've been looking for automatic graphing software like that for a while. Even better that it is open source! It looks a good match for my application.

I have to admit to being curious about the Z80 side of things as I have an interest in that area too - the remains of a Sinclair ZX81 and Spectrum introduction to computing, I suppose. Clearing out the loft recently, I found a robot I built over twenty years ago. It has a built-in ZX81 and has renewed my interest. Amazingly, the computer still works! Not bad for a cheap machine built almost 30 years ago. The rest of the robot needs attention, but still!

Keep up the good work,

Merlin

Posted by Merlin Skinner

"neato" (part of GraphViz) does the trick wonderfully! Thanks for the pointer.

Merlin

Posted by Merlin Skinner

Add a new comment


(No HTML tags allowed. Separate paragraphs with a blank line.)