Difference between revisions of "LZSS Compression"

From Retro Modding Wiki
Jump to: navigation, search
(→‎Structure)
(→‎Example C Decompression Function: tried to use this function and it didn't work. oops. fixed.)
 
(4 intermediate revisions by the same user not shown)
Line 19: Line 19:
 
| 3
 
| 3
 
| '''Unused'''; always 0
 
| '''Unused'''; always 0
 +
|-
 +
| 0x4
 +
| colspan=2 {{unknown|Compressed data starts}}
 
|}
 
|}
  
Line 57: Line 60:
 
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 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 it varies depending which mode is set:
+
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:
  
 
{| class="wikitable"
 
{| class="wikitable"
Line 80: Line 83:
 
== Example C Decompression Function ==
 
== Example C Decompression Function ==
  
−
<syntaxhighlight lang="c" line start="1">bool DecompressLZSS(char *src, unsigned long src_len, char *dst, unsigned long dst_len)
+
<syntaxhighlight lang="c" line start="1">bool DecompressLZSS(u8 *src, u32 src_len, u8 *dst, u32 dst_len)
 
{
 
{
−
     char *src_end = src + src_len;
+
     u8 *src_end = src + src_len;
−
     char *dst_end = dst + dst_len;
+
     u8 *dst_end = dst + dst_len;
  
 
     // Read compressed buffer header
 
     // Read compressed buffer header
Line 123: Line 126:
 
             case 1:
 
             case 1:
 
                 count = (bytes[0] >> 4) + 3;
 
                 count = (bytes[0] >> 4) + 3;
−
                 length = (bytes[0] & 0xF) | bytes[1];
+
                 length = ((bytes[0] & 0xF) << 0x8) | bytes[1];
 
                 break;
 
                 break;
 
             case 2:
 
             case 2:
 
                 count = (bytes[0] >> 4) + 2;
 
                 count = (bytes[0] >> 4) + 2;
−
                 length = ((bytes[0] & 0xF) | bytes[1]) << 1;
+
                 length = (((bytes[0] & 0xF) << 0x8) | bytes[1]) << 1;
 
                 break;
 
                 break;
 
             case 3:
 
             case 3:
 
                 count = (bytes[0] >> 4) + 1;
 
                 count = (bytes[0] >> 4) + 1;
−
                 length = ((bytes[0] & 0xF) | bytes[1]) << 2;
+
                 length = (((bytes[0] & 0xF) << 0x8) | bytes[1]) << 2;
 
                 break;
 
                 break;
 
             }
 
             }
  
 
             // With the count and length calculated, we'll set a pointer to where we want to read back data from:
 
             // With the count and length calculated, we'll set a pointer to where we want to read back data from:
−
             char *seek = dst - length;
+
             u8 *seek = dst - length;
  
 
             // count refers to how many byte groups to read back; the size of one byte group varies depending on mode
 
             // count refers to how many byte groups to read back; the size of one byte group varies depending on mode

Latest revision as of 11:35, 7 February 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:

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;
  5.  
  6.     // Read compressed buffer header
  7.     u8 mode = *src++;
  8.     src += 3; // Skipping unused bytes
  9.  
  10.     // Check for invalid mode set:
  11.     if (mode > 3) return false;
  12.  
  13.     // If mode is 0, then we have uncompressed data.
  14.     if (mode == 0) {
  15.         memcpy(dst, src, dst_len);
  16.         return true;
  17.     }
  18.  
  19.     // Otherwise, start preparing for decompression.
  20.     u8 header_byte = 0;
  21.     u8 group = 0;
  22.  
  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.         }
  32.  
  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;
  39.  
  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) << 0x8) | bytes[1];
  45.                 break;
  46.             case 2:
  47.                 count = (bytes[0] >> 4) + 2;
  48.                 length = (((bytes[0] & 0xF) << 0x8) | bytes[1]) << 1;
  49.                 break;
  50.             case 3:
  51.                 count = (bytes[0] >> 4) + 1;
  52.                 length = (((bytes[0] & 0xF) << 0x8) | bytes[1]) << 2;
  53.                 break;
  54.             }
  55.  
  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;
  58.  
  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.         }
  77.  
  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.         }
  95.  
  96.         header_byte <<= 1;
  97.         group--;
  98.     }
  99.  
  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. }
Retrieved from "http://www.metroid2002.com/retromodding/index.php?title=LZSS_Compression&oldid=694"