LZSS Compression - Revision history

Aruki: /* Example C Decompression Function */ tried to use this function and it didn't work. oops. fixed.

2015-02-07T17:35:54Z

‎Example C Decompression Function: tried to use this function and it didn't work. oops. fixed.

Aruki at 03:54, 26 January 2015

2015-01-26T03:54:14Z

Aruki: /* Structure */ I'm a nitpicker

2015-01-24T18:49:45Z

‎Structure: I'm a nitpicker

Aruki: consistency

2015-01-24T18:47:09Z

consistency

Aruki at 18:44, 24 January 2015

2015-01-24T18:44:16Z

Aruki: /* Structure */

2015-01-24T18:24:24Z

‎Structure

Aruki: /* Example C Decompression Function */

2015-01-24T18:22:33Z

‎Example C Decompression Function

Aruki: Adding syntax highlighting

2015-01-24T18:21:51Z

Adding syntax highlighting

Aruki at 12:33, 24 January 2015

2015-01-24T12:33:15Z

Aruki: Created page with "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 implementat..."

2015-01-24T12:30:55Z

Created page with "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 implementat..."

New page

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.

__TOC__

== Header ==

Every compressed buffer starts with the following header:

{| class="wikitable"
! Offset
! Size
! Description
|-
| 0x0
| 1
| '''Mode'''
|-
| 0x1
| 3
| '''Unused'''; always 0
|}

The mode will correspond to one of the following:

{| class="wikitable"
! 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 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:

{| class="wikitable"
! 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 ==

<pre>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));
}</pre>

@@ Line 21: / Line 21: @@
 |-
 | 0x4
-| colspan=2 | Compressed data starts
+| colspan=2 {{unknown|Compressed data starts}}
 |}

@@ Line 60: / 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 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"

@@ Line 80: / Line 80: @@
 == Example C Decompression Function ==
-<syntaxhighlight lang="c">bool DecompressLZSS(char *src, unsigned long src_len, char *dst, unsigned long dst_len)
+<syntaxhighlight lang="c" line start="1">bool DecompressLZSS(char *src, unsigned long src_len, char *dst, unsigned long dst_len)
+{
      char *src_end = src + src_len;

@@ Line 80: / Line 80: @@
 == Example C Decompression Function ==
-<pre>bool DecompressLZSS(char *src, unsigned long src_len, char *dst, unsigned long dst_len)
+<syntaxhighlight lang="c">bool DecompressLZSS(char *src, unsigned long src_len, char *dst, unsigned long dst_len)
+{
      char *src_end = src + src_len;
@@ Line 181: / Line 181: @@
      // 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));
-}</pre>
+}</syntaxhighlight>
 [[Category:File Formats]]
 [[Category:Donkey Kong Country: Tropical Freeze]]

← Older revision		Revision as of 12:33, 24 January 2015
Line 182:		Line 182:
	return ((src == src_end) && (dst == dst_end));		return ((src == src_end) && (dst == dst_end));
	}</pre>		}</pre>
		+
		+	[[Category:File Formats]]
		+	[[Category:Donkey Kong Country: Tropical Freeze]]

@@ Line 126: / Line 126: @@
              case 1:
                  count = (bytes[0] >> 4) + 3;
-                 length = (bytes[0] & 0xF) | bytes[1];
+                 length = ((bytes[0] & 0xF) << 0x8) | bytes[1];
                  break;
              case 2:
                  count = (bytes[0] >> 4) + 2;
-                 length = ((bytes[0] & 0xF) | bytes[1]) << 1;
+                 length = (((bytes[0] & 0xF) << 0x8) | bytes[1]) << 1;
                  break;
              case 3:
                  count = (bytes[0] >> 4) + 1;
-                 length = ((bytes[0] & 0xF) | bytes[1]) << 2;
+                 length = (((bytes[0] & 0xF) << 0x8) | bytes[1]) << 2;
                  break;
+             }

@@ Line 83: / Line 83: @@
 == 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
@@ Line 139: / Line 139: @@
              // 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

@@ Line 19: / Line 19: @@
 | 3
 | '''Unused'''; always 0
 |}