LZ16

Note: most of the information on this page is preliminary. It might be somewhat inaccurate.

LZ16 (or LC_LZ16, as named by Lunar Compress) is a lossless data compression format, used by Yoshi's Island for sprite and background graphics (foreground graphics use LZ2). It's notably different than other 'LZ' formats used by SNES games by being a bitstream format with variable width encodings, and only being able to handle multiples of 128 bytes. It appears to be designed specifically for compressing graphics.

Compression

The number of 'rows' of tiles to compress or decompress must be known ahead of time, and must be a multiple of 0x80 (128). The decompression scheme revolves around decompressing a row at a time. The first 3.5 bytes of the compressed data (that is, the first three bytes and the low nybble of the fourth byte) encode a set of seven palette indices (four bits each). Each command has a length associated (comes first in the bitstream; see below). The available commands are as follows:

00    "Copy from previous line until color change: n sections"
      Copy pixels from the previous line until <length> different bytes are seen.
01    "Copy from previous line, plus n pixels"
      Copy pixels from the previous line until a different color is seen, plus <length> pixels.
10    "Run-length encoding"
      Read a color value from the bitstream (described below), then set <length> pixels equal to this color.
11    "Copy from previous line, minus n pixels"
      Copy pixels from the previous line until a different color is seen, minus <length> pixels.

Note that the implementation in Yoshi's Island actually corrupts a value in the previous line buffer when handling commands 01 and 11: it sets the first value copied from in the previous buffer to the last value (?)

These commands can have two different types of associated data: lengths, and color.

• Length
  • Lengths are encoded as a series of set bits, with the highest bit as 0 functioning as a 'stop' bit. This highest bit is ultimately set in the value read. They are packed from least significant bit to most significant bit (e.g. 7 is encoded as 011). Notably this means only powers of two - 1 can be encoded.
• Color
  • Read three bits: they are packed 'in reverse' (that is, the first bit read is the most significant bit, and the last bit read is the least significant). If all three are set, read four more bits in the same fashion and this is your color index. Otherwise, set bit 4 in the value (i.e. 0001 0000) and return that.
  • When color indices are used, if the 4th bit is set, use the low 3 bits as an index into the palette data. Otherwise, use the color index directly as the value.

The logic for decompression after extracting the palette is as follows:

* Read a single bit.
   * If unset, read a length, and perform RLE.
     * Repeat until a row has been decompressed.
   * If set, process bitstream as commands.
     * Read a length, then read two bits as the command.
     * Handle the command as described above.
     * Continue handling commands until a row has been decompressed.