Difference between revisions of "LZSS Compression"

Revision as of 06:30, 24 January 2015

LZSS compression is used in Tropical Freeze to compress GPU buffer data in models and textures. It's very similar to Nintendo's Yaz0 compression, but it's a custom implementation with a few extra features, including several different possible modes.

Header

Every compressed buffer starts with the following header:

The mode will correspond to one of the following:

The different types relate to how much data can be copied at once; the higher-bit modes will copy more data, which means larger repeated data runs can be copied with less bytes, but requires larger runs to exist to really be useful.

Structure

The compressed data is split into multiple data groups, each of which is defined by one header byte and eight data chunks. The header byte encodes instructions for how each data chunk should be read. Each bit of each header byte defines how one of the following byte groups should be read.

• The most significant bit (MSB), 0x80, refers to the first data chunk.
• The least significant bit (LSB), 0x1, refers to the last data chunk.

Each data chunk can contain one or more byte groups in it. The size of one byte group depends on which mode is set:

• Mode 1 has 8-bit groups
• Mode 2 has 16-bit groups
• Mode 3 has 32-bit groups.

If the bit corresponding to the current data chunk is not set, you read one byte group directly from the compressed buffer; simple.

If the bit is set, then that means you need to read data back from the decompressed buffer, which is where it gets a little more complicated. Read two bytes from the decompressed buffer; these tell you exactly how far back in the decompressed buffer to seek, and how many byte groups to read from it. The exact way to utilize it varies depending which mode is set:

After calculating the count and length, you seek backwards in the decompressed buffer by length bytes, then read count byte groups (not bytes).

Example C Decompression Function

bool DecompressLZSS(char *src, unsigned long src_len, char *dst, unsigned long dst_len)
{
    char *src_end = src + src_len;
    char *dst_end = dst + dst_len;

    // Read compressed buffer header
    u8 mode = *src++;
    src += 3; // Skipping unused bytes

    // Check for invalid mode set:
    if (mode > 3) return false;

    // If mode is 0, then we have uncompressed data.
    if (mode == 0) {
        memcpy(dst, src, dst_len);
        return true;
    }

    // Otherwise, start preparing for decompression.
    u8 header_byte = 0;
    u8 group = 0;

    while ((src < src_end) && (dst < dst_end))
    {
        // group will start at 8 and decrease by 1 with each data chunk read.
        // When group reaches 0, we read a new header byte and reset it to 8.
        if (!group)
        {
            header_byte = *src++;
            group = 8;
        }

        // header_byte will be shifted left one bit for every data group read, so 0x80 always corresponds to the current data group.
        // If 0x80 is set, then we read back from the decompressed buffer.
        if (header_byte & 0x80)
        {
            u8 bytes[2] = { *src++, *src++ };
            u32 count, length;

            // The exact way to calculate count and length varies depending on which mode is set:
            switch (mode) {
            case 1:
                count = (bytes[0] >> 4) + 3;
                length = (bytes[0] & 0xF) | bytes[1];
                break;
            case 2:
                count = (bytes[0] >> 4) + 2;
                length = ((bytes[0] & 0xF) | bytes[1]) << 1;
                break;
            case 3:
                count = (bytes[0] >> 4) + 1;
                length = ((bytes[0] & 0xF) | bytes[1]) << 2;
                break;
            }

            // With the count and length calculated, we'll set a pointer to where we want to read back data from:
            char *seek = dst - length;

            // count refers to how many byte groups to read back; the size of one byte group varies depending on mode
            for (u32 byte = 0; byte < count; byte++)
            {
                switch (mode) {
                case 1:
                    *dst++ = *seek++;
                    break;
                case 2:
                    for (u32 b = 0; b < 2; b++)
                        *dst++ = *seek++;
                    break;
                case 3:
                    for (u32 b = 0; b < 4; b++)
                        *dst++ = *seek++;
                    break;
                }
            }
        }

        // If 0x80 is not set, then we read one byte group directly from the compressed buffer.
        else
        {
            switch (mode) {
            case 1:
                *dst++ = *src++;
                break;
            case 2:
                for (u32 b = 0; b < 2; b++)
                    *dst++ = *src++;
                break;
            case 3:
                for (u32 b = 0; b < 4; b++)
                    *dst++ = *src++;
                break;
            }
        }

        header_byte <<= 1;
        group--;
    }

    // We've finished decompressing; the last thing to do is check that we've reached the end of both buffers, to verify everything has decompressed correctly.
    return ((src == src_end) && (dst == dst_end));
}