LZSS Compression

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:

Offset	Size	Description
0x0	1	Mode
0x1	3	Unused; always 0
0x4	Compressed data starts

The mode will correspond to one of the following:

ID	Mode
0x0	Uncompressed
0x1	8-bit
0x2	16-bit
0x3	32-bit

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 compressed 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 them varies depending which mode is set:

Mode	Byte Count/Length Calculation
1	count = (byte0 >> 4) + 3; length = (byte0 & 0xF) | byte1;
2	count = (byte0 >> 4) + 2; length = ((byte0 & 0xF) | byte1) << 1;
3	count = (byte0 >> 4) + 1; length = ((byte0 & 0xF) | byte1) << 2;

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

1. bool DecompressLZSS(u8 *src, u32 src_len, u8 *dst, u32 dst_len)

2. {

3.     u8 *src_end = src + src_len;

4.     u8 *dst_end = dst + dst_len;

6.     // Read compressed buffer header

7.     u8 mode = *src++;

8.     src += 3; // Skipping unused bytes

10.     // Check for invalid mode set:

11.     if (mode > 3) return false;

13.     // If mode is 0, then we have uncompressed data.

14.     if (mode == 0) {

15.         memcpy(dst, src, dst_len);

16.         return true;

17.     }

19.     // Otherwise, start preparing for decompression.

20.     u8 header_byte = 0;

21.     u8 group = 0;

23.     while ((src < src_end) && (dst < dst_end))

24.     {

25.         // group will start at 8 and decrease by 1 with each data chunk read.

26.         // When group reaches 0, we read a new header byte and reset it to 8.

27.         if (!group)

28.         {

29.             header_byte = *src++;

30.             group = 8;

31.         }

33.         // header_byte will be shifted left one bit for every data group read, so 0x80 always corresponds to the current data group.

34.         // If 0x80 is set, then we read back from the decompressed buffer.

35.         if (header_byte & 0x80)

36.         {

37.             u8 bytes[2] = { *src++, *src++ };

38.             u32 count, length;

40.             // The exact way to calculate count and length varies depending on which mode is set:

41.             switch (mode) {

42.             case 1:

43.                 count = (bytes[0] >> 4) + 3;

44.                 length = (bytes[0] & 0xF) | bytes[1];

45.                 break;

46.             case 2:

47.                 count = (bytes[0] >> 4) + 2;

48.                 length = ((bytes[0] & 0xF) | bytes[1]) << 1;

49.                 break;

50.             case 3:

51.                 count = (bytes[0] >> 4) + 1;

52.                 length = ((bytes[0] & 0xF) | bytes[1]) << 2;

53.                 break;

54.             }

56.             // With the count and length calculated, we'll set a pointer to where we want to read back data from:

57.             u8 *seek = dst - length;

59.             // count refers to how many byte groups to read back; the size of one byte group varies depending on mode

60.             for (u32 byte = 0; byte < count; byte++)

61.             {

62.                 switch (mode) {

63.                 case 1:

64.                     *dst++ = *seek++;

65.                     break;

66.                 case 2:

67.                     for (u32 b = 0; b < 2; b++)

68.                         *dst++ = *seek++;

69.                     break;

70.                 case 3:

71.                     for (u32 b = 0; b < 4; b++)

72.                         *dst++ = *seek++;

73.                     break;

74.                 }

75.             }

76.         }

78.         // If 0x80 is not set, then we read one byte group directly from the compressed buffer.

79.         else

80.         {

81.             switch (mode) {

82.             case 1:

83.                 *dst++ = *src++;

84.                 break;

85.             case 2:

86.                 for (u32 b = 0; b < 2; b++)

87.                     *dst++ = *src++;

88.                 break;

89.             case 3:

90.                 for (u32 b = 0; b < 4; b++)

91.                     *dst++ = *src++;

92.                 break;

93.             }

94.         }

96.         header_byte <<= 1;

97.         group--;

98.     }

100.     // 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.

101.     return ((src == src_end) && (dst == dst_end));

102. }