Sonic Crackers art compression

The Crackers compression is an algorithm used in Sonic Crackers to reduce the size of the "field" and "SEGA" logo art, it is not known to be used in any other game, and is a variation of the LZSS algorithm. In 2003, Nemesis wrote a command-line decompressor for the format, which was released as part of the Nemesis MD Programs collection, while in 2010, MarkeyJester wrote a decompressor and compressor for the format released here.

Compression Theory

The Crackers compression algorithm has two forms of decompression, one is for uncompressed data, and the other uses 1 of 4 different layouts of LZSS for different offsets/lengths, this means there are 4 possible compression sizes that can be generated out of the same data, one of which will be the smallest in size compared to the other 3, this allows for more flexible and precise results. The format is as followed:

SSSS PP AA AA AA AA AA AA AA AA PP AA AA AA AA AA AA AA AA …

The SSSS only occurs at the very beginning of the data, this is the number of sections and determines the offset/length in which the LZSS should decompress. Breaking it up into bits, the two most significant bits is the offset/length, if this is 00, then the offset and length are both 4 bits, if it is 01, then the offset is 5 bits while the length is 3 bits, if it is 10, then the offset is 6 bits while the length is 2 bits, and finally if it is 11, then the offset is 7 bits while the length is only 1 bit, this info is used later during the decompression, the rest of the bits to SSSS is the number of sections to decompress (This can only be at a maximum of 3FFF due to the offset/length bits).

Now each PP AA AA AA AA AA AA AA AA is one section, the AA's are the compressed data bytes which need to be decompressed, the PP byte is what we'll call a "Phase Byte", it determines how the AA data bytes are to be decompressed, this is broken up into bits:

PP =  1  2  3  4  5  6  7  8
      AA AA AA AA AA AA AA AA

Each bit (1 to 8) will determine what the byte below it (The AA's) will do, if the bit is clear (bit 0), then the byte is uncompressed and is sent to the output location (The output location is incremented by 1), if the bit is set (bit 1), then the byte is offset/length data, and is broken into two parts, this size of these parts depends on the two most significant bits of the SSSS we talked about earlier, here's a list:

R = Retrace C = Copy

If the bits were 00, then AA is broken into bits of RRRRCCCC (the offset can move back as far as 0F bytes and can copy 0F bytes). If the bits were 01, then AA is broken into bits of RRRRRCCC (the offset can move back as far as 1F bytes and can copy 07 bytes). If the bits were 10, then AA is broken into bits of RRRRRRCC (the offset can move back as far as 3F bytes and can copy 03 bytes). If the bits were 11, then AA is broken into bits of RRRRRRRC (the offset can move back as far as 7F bytes and can copy 01 bytes).

The R (Retrace) and C (Copy) amounts are incremented by 1. As an example, if the most significant bits of SSSS are 01, and AA is for example 63, then the system will move back D bytes (C + 1) of the current output location and copy 4 bytes (3 + 1) to the output location. Below is an example of a section of compressed data, we're going to decompress the first 4/5 bytes (imagining that the most significant bits of SSSS are 00 for this example):

6A 00 0F F1 11 05 10 E5 66

6A is the "Phase Byte" for this section, in bits:

6A =  0  1  1  0  1  0  1  0
      00 0F F1 11 05 10 E5 66

So, 00 is uncompressed:

00 [??]

0F is "Retrace/Copy", R = 0+1, C = F+1:

[00] ??
(Moving back R bytes)

00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 [??]
(Copying C bytes)

Next F1 "Retrace/Copy" again, R = F+1, C = 1+2:

00 00 00 [00] 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 ??
(Moving back R bytes)

00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 [??]
(Copying C bytes)

Next 11 uncompressed:

00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 11 [??]

Next 05 "Retrace/Copy", R = 0+1, C = 5+1:

00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 [11] ?? 
(Moving back R bytes)

00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 11 11 11 11 11 11 11 [??] 
(Copying C bytes)

The rest should be self explanatory at this point. After one section is done, the next section is read, until the number of sections in SSSS have elapsed, of which would be the end of the data and the decompression.