User Tools

Compression Details

The compression method used in Mario Golf (or one of the methods) is still being looked into, but it's understood enough at this point to deserve a wiki page on how it works. The notes here are a bit unorganized, forgive the mess.

The decompression function starts at 0x80068a50 in RAM. At this point, 3 registers hold the variables involved in the decompression process: A0 - Input pointer (ROM address) A1 - Output pointer (RAM address) A2 - Length of data (not 100% sure yet)

Although the decompression function starts there, the real decompression algorithm is at 0x80068410. Most of the code in 0x80068a50 seems to be copying the compressed data from ROM to RAM and then creating the header information. The header details where the decompression starts, ends, outputs to and whether or not it's continuing from a previous decompression.

The code is a bit convoluted since the whole process is set up so that you can use a limited-size buffer to hold the compressed data while you convert it. The decompression algorithm can pause once it hits the end of the buffer, load up the next set of data, and then continue with the decompression process. Luckily we don't need to follow this limited method of loading up the data, so most of the code in there can be ignored for reverse-engineering purposes.

The algorithm is fairly similar to MIO0, the biggest difference being that all the data is handled in halfwords (2 byte clumps). The bottom line is that it alternates between copying raw data to the output, and then re-using data previously written to the output. Here's how the algorithm works, given a set of compressed data to decompress:

1. Ignore the first two halfwords (advance the pointer by 4).

2. Load up the next halfword. This halfword can be considered a series of bit flags, either on (1) or off (0).

3. Look at the current bit in the flag halfword (starts at the leftmost bit).

3.1. If it's off (0), copy the next halfword to the output.

3.2. If it's on (1), grab the next halfword. This is our copy information.

3.2.1. If the halfword is 0, then that means that we have finished the decompression. Go ahead and quit here!

3.2.2. Otherwise, we will copy (((prevDataInfo & 0x1f) « 1) + 4 bytes of data from ((prevDataInfo » 5) « 1) bytes back from the front of the output data.

4. Advance to the next flag. If you go past the end of the halfword, go back to step 2. if not, go to 3.1.

Mario Golf 64 Compression Tool

C# code for Compression/Decompression