Part 46: Tales of ROMhacking: Part 5
Sorry folks, but my grad school application is pretty much done, my GMATs are in, my transcripts are sent, and I'm gonna have more time for Policenauts now. So, enjoy another:Tales of ROMhacking!
The LZO Decompressor
In my last one of these, I'd gone over some of Policenauts' graphical compression formats, but I'd left out one: the major one, that most of the game uses.
I was stumped at the game's telops - through the use of the debug log Scarboy found, and tracing out the assembly, we had a rough idea of where the game was reading its graphical data from... but we had no idea how it was drawing pixels from that data. One of the fun things I liked to do in the ROMhack was randomly increment/decrement/zero-out/change a byte or two to see how it affected thngs. Here, though, it strangely ran the risk of crashing the game, which I'd never seen, or completely fouling up the graphics.
One day, we got on Skype and went through the drawing algorithm together. Policenauts on the PSX uses 16-bit color for its graphics - apparently, common in Playstation games - in a bgra 5551 format. (This means the first five bits are the blue channel, the next 5 are green, the next 5 are red, and the last bit is an alpha channel.) However, none of the input data seemed to correspond to any sort of color information, and watching the game draw in disassembly was... confusing.
Here are my notes from Lorraine's telop - don't bother reading these carefully, there's nothing to be gleaned:
code:
00 08 02 61 - it drew 02 88 at 13ee44. Does 61 tell it to draw? (only once?)
(04 02) 01 - draw 1 pixel of 01 88 at 13ee46 (only one)
C0 seemed to tell it to jump ahead one row + 1 pixel and draw a pixel there?
00 seemed to tell it to go back?
(04 00) 0B - draw 11 pixels of [01 80] at 13ee48
C9 - Draw 10 pixels at the next row (-1?). (It used the 0B - 1 to draw that!)
00 - Go back to cursor
(08 00) 03 - draw 3 pixels of [02 80] at 13ee5e
40 - goto next row + 0, draw 3 pixels of 02 08
CA - Draw 1 pixels [02 80] at next row (3rd) (-2?)
40 - goto next row + 0, draw 1 pixels of 02 80
00 - Go back to cursor?
(0C 00) 01 - draw 1 pixel of [03 80]
41 - goto next row, draw 2 pixels of 03 80
E9 - goto next row-1, draw 1 pixel of 03 80
40 - goto next row + 0, draw 1 pixel of 03 80
00 - go back to cursor
(88) 01 - pop last color [02 80] and draw 1 pixel at cursor
C0 - goto next row+1 and draw 1 pixel of [02 80]
00 - go back to cursor
(0C 20) 61 - draw one pixel of [23 80]
(1C 82) 61 - draw one pixel of [87 88]
(10 20) 61 - draw one pixel of [24 80]
Scarboy saw "START DECOMPRESS" in the debug log and figured it out. It wasn't a drawing routine, it was a decompression routine. The graphics were compressed to fit on the game's discs.
Shit.
This was a big problem. It was one thing to figure out how the game was drawing, i.e. understand how it decompressed. But we'd have to figure out how to re-compress it and that was the big problem. We'd have to make new graphics and use this game's proprietary compression to store them and decompress them. And that's to say nothing of the fact that storing bigger graphics would push out all the other stored graphics and we'd have to change a bunch of data pointers.
This could take months. Maybe longer.
"LZO," Scarboy IMed me a week or so later.
"What?"
"LZO decompression," and he linked me to a website that explained it. It required no memory on decompression and claimed to be very fast.
"Okay. So?" And then he told me the plan. And it was brilliant. It works like this.
Scarboy found a MIPS compiler called SPIM, which took the C code for an LZO decompressor and spit out MIPS r3000 assembly. We'd put the decompression routine in the hack, along with our other assembly hacks. Then we prepended modified graphics with a control code.
We hijack the game's decompression routine. If we found our control code, we'd assume we had an LZO-compressed (modified) graphic, and decompress it. If we saw no such control code, we'd abort the hack and return control back to the game to do its proprietary decompression. We bypass the problem altogether.
Even better, since LZO compression tended to do better than Konami's, most of our new graphics fit in the same spot, using even less space than the originals. We could fit in bigger English telops, change graphical flubs, and modify Engrish and badly romanized names like "Hojyo" and "Isida."
The only crummy thing is that there was one manual step: Finding the original game graphic to begin with. Since we knew where the decompression routine was, I basically:
1. Got as close as I could to the graphic appearing onscreen without it happening
2. Set a breakpoint on the game's decompression routine
3. Made the graphic appear to trigger the breakpoint
4. Go to where the decompressor was reading from in memory
5. Copy a big chunk of binary image data
6. Go to the ROM files and search on the binary data
7. Note where that data begins in hex.
Our automated build process did this:
It takes our modified PNGs and references it with a config file that maps the filename to where the original graphic is stored in the ROM. It then uses a Ruby script to compress the graphic into LZO and a Perl script to write the data over the game's original graphic. Then it moves onto the next file until its done writing in our 80 or so modified graphics.
At runtime, it hijacks the decompression routine and works it like that.
Modifying graphics was a tedious process because of the 7-step workflow I'd managed, but I couldn't automate it further. It ended up being laborious whenever Marc found a new graphic to change, which he seemed to on a pretty frequent basis.
It actually led to me considering leaving the project for a second time.