Compression: Difference between revisions

Revision as of 22:36, 26 October 2016

This article is incomplete.
Please feel free to add missing information and complete the article.

Compression is used in many of the games to decrease the amount of space taken up by files when not loaded into RAM or just not actively being used.

Lempel–Ziv (LZ)

The main set of compression algorithms in GBA-era and later games is Lempel–Ziv compression, commonly shortened to LZ. Algorithms classified under this name use relative references to bytes that have already been processed.

The header for LZ compression is 4 bytes wide:

struct lz_header {
    u32 type : 8;  /* First byte */
    u32 decompressed_size : 24;  /* Other 3 bytes */
}

LZ77

The main variant, LZ77, allows references up to 0xFFF bytes back for up to 0x12 bytes. LZ77's type identifier is 0x10.

LZSS Compression

Another common variant used is LZSS which allows for more controlled decompression. LZSS allows for up to 0xFFF bytes back for up to 0x1110 bytes depending on the mode switch. LZSS has a type of 0x11.

BLZ Compression

BLZ compression is used mainly for data that cannot be copied into an output buffer; usually it must be done in place usually because the block is too large. This was implemented in Diamond and Pearl but was not extensively used until Heart Gold and Soul Silver, where it was used to compress the ARM binaries as well as the overlays.

The magic number 0xDEC0???? indicates the 0x1Cth byte of the compressed region. The end of the compressed region is stored at the 0x14th byte (a u32); note that the end is an absolute location in RAM. If the end RAM address is 0, the file is considered decompressed. Compression starts at the end of the compressed region and fills in from the end of the decompressed region until it reaches the start of the decompressed region.

struct blz_control {
    u32 compressed_size : 24;
    u32 header_size : 8;
    u32 decompressed_increase;
}

@@ Line 1: / Line 1: @@
-{{incomplete | More compressions exist. Content should be verified.}}
+{{incomplete|More compressions exist. Content should be verified.}}
 Compression is used in many of the games to decrease the amount of space taken up by files when not loaded into RAM or just not actively being used.
-==LZ Compression==
+==Lempel–Ziv (LZ)==
-The default compression in NDS and later games is LZ compression. These compression types use references to text that has already been processed. The main variant LZ77 allows references up to 0xFFF bytes back for up to 0x12 bytes.
+The main set of compression algorithms in GBA-era and later games is Lempel–Ziv compression, commonly shortened to '''LZ'''. Algorithms classified under this name use relative references to bytes that have already been processed.
 The header for LZ compression is 4 bytes wide:
+<pre>
+struct lz_header {
+    u32 type : 8;  /* First byte */
+    u32 decompressed_size : 24;  /* Other 3 bytes */
+}
+</pre>
-  struct lz_header {
+===LZ77===
-    uint32_t type : 8;  /* First byte */
+The main variant, ''LZ77,'' allows references up to <code>0xFFF</code> bytes back for up to <code>0x12</code> bytes. LZ77's type identifier is <code>0x10</code>.
-    uint32_t decompressed_size : 24;  /* Other 3 bytes */
-  }
-LZ77 has a type of 0x10. LZSS has a type of 0x11.
 ===LZSS Compression===
-Another common variant used is LZSS which allows for more controlled decompression. LZSS allows for up to 0xFFF bytes back for up to 0x1110 bytes depending on the mode switch.
+Another common variant used is '''LZSS''' which allows for more controlled decompression. LZSS allows for up to <code>0xFFF</code> bytes back for up to <code>0x1110</code> bytes depending on the mode switch. LZSS has a type of 0x11.
 ===BLZ Compression===
-BLZ compression is used mainly for data that cannot be copied into an output buffer (it must be done in place usually because the block is too large). This was implemented in [[Diamond and Pearl]] but was not extensively used until [[Heart Gold and Soul Silver]], where it was used to compress the [[ARM binaries]] as well as the [[overlays]].
+'''BLZ''' compression is used mainly for data that cannot be copied into an output buffer; usually it must be done in place usually because the block is too large. This was implemented in [[Diamond and Pearl]] but was not extensively used until [[Heart Gold and Soul Silver]], where it was used to compress the ARM binaries as well as the overlays.
+The magic number <code>0xDEC0????</code> indicates the <code>0x1C</code>th byte of the compressed region. The end of the compressed region is stored at the <code>0x14</code>th byte (a <code>u32</code>); note that the end is an absolute location in RAM. If the end RAM address is 0, the file is considered decompressed. Compression starts at the end of the compressed region and fills in from the end of the decompressed region until it reaches the start of the decompressed region.
-The magic 0xDEC0xxxx indicates the 0x1Cth byte of the compressed region. The end of the compressed region is stored at the 0x14th byte (uint32_t). It is noting that the end is an absolute location in RAM. If the end RAM address is 0, the file is considered decompressed. Compression starts at the end of the compressed region and fills in from the end of the decompressed region until they meet at the start of the decompressed region.
+<pre>
+struct blz_control {
+    u32 compressed_size : 24;
+    u32 header_size : 8;
+    u32 decompressed_increase;
+}
+</pre>
-  struct blz_control {
+[[Category:Algorithms]]
-    uint32_t compressed_size : 24;
-    uint32_t header_size : 8;
-    uint32_t decompressed_increase;
-  }