Tile compression

Tile compression refers to techniques that allow fitting more graphics data into a smaller space. Programs using CHR ROM cannot use compressed tiles, as their tile data must be stored in the PPU's native format. But programs using CHR RAM can process tile data while copying it from PRG ROM to CHR RAM, and this processing allows storing more tiles in the same space.

Run-length encoding

Run-length encoding transforms runs of identical bytes into a shorter sequence of bytes that specifies the length of the run.

In NES tile data, byte-level run-length encoding works well when a row of 8 pixels in a tile is identical to the row above it. It also works well for nametable data because a horizontal run of blank tiles becomes a single tile.

Pixel-level run-length encoding is much slower but can achieve impressive results within a tile.

There are several different RLE data formats.

PCX

The PCX image format became popular on PC.

Value	Meaning
00-BF	Write this byte to the output.
C0-FF	Read another byte, and write it to the output n - 192 times.

PackBits

The PackBits format was invented by Apple for MacPaint. It is also used in TIFF files and a few homebrew releases by Damian Yerrick.

Value	Meaning
00-7F	Copy n + 1 bytes from input to output.
80	No operation
81-FF	Read another byte, and write it to the output 257 - n times.

Konami RLE

This format is used in Blades of Steel, the U.S. version of Contra, and the Japanese version of Simon's Quest. It can be decoded and encoded with the Python program GraveyardDuck. Compression ratio is more or less identical to PackBits.

Value	Meaning
00-80	Read another byte, and write it to the output n times.
81-FE	Copy n - 128 bytes from input to output.
FF	End of compressed data

GBA RLUnComp

The BIOS of the Game Boy Advance and Nintendo DS contains a decompressor for an RLE format very similar to PackBits and Konami. As described in GBATEK, it has a 4-byte size header followed by this:

Value	Meaning
00-7F	Copy n + 1 bytes from input to output.
80-FF	Read one byte from input and write it to output n - 125 times.

PB53

This codec was conceived by Damian Yerrick as an alternative to PackBits for the Action 53 multicart. Unlike freeform RLE formats such as Konami and PackBits, PB53 operates on 16-byte units, making it easy to divide the decompressed data into fixed-size packets to be sent to the PPU during vblank while rendering is turned on. Like LZSS, PB53 uses unary coding on the run lengths to save on overhead from switching between literal and run modes. This means that like LZSS, it has a worst case expansion of 12.5%, but it works fairly well on real tile data and OK on nametable data, which have shorter runs than the high-resolution files for which PackBits was designed. It also has a special mode to accommodate the layout of Shiru's NROM games LAN Master, Lawn Mower, and Chase, which have many identical tiles between the two pattern tables to allow tile animation.

Each tile consists of several 8-byte planes. For the first plane in a tile:

Value	Meaning
00-7F	Copy one byte from input to output. Then, for each bit from 6 to 0, if the bit is 1, repeat the previous byte; otherwise, copy another byte from the input. This is somewhat similar to how control bytes are formatted in LZSS.
80	Write eight $00 bytes.
81	Write eight $FF bytes.
82	Copy 16 bytes starting 16 bytes back. (Used for a repeated tile, such as the unused tiles in many games.)
83	Copy 16 bytes starting one segment back, usually 4096 bytes. (Used for pattern tables that share tiles, as seen in several Shiru games. The decoder switches between two instances one segment apart, each with its own input stream and output buffer.)
84	Write sixteen $00 bytes. (Solid color 0)
85	Write eight $FF bytes then eight $00 bytes. (Solid color 1)
86	Write eight $00 bytes then eight $FF bytes. (Solid color 2)
87	Write sixteen $FF bytes. (Solid color 3)

For other planes:

Value	Meaning
00-81	Same as first plane
82	Copy previous 8 bytes. (Used for 1-bit tiles with colors 0 and 3.)
83	Copy previous 8 bytes, bit-inverted. (Used for 1-bit tiles with colors 1 and 2.)

Codemasters

This is a hybrid of RLE and a Markov chain (predictive) algorithm. It works on packets measured in whole tiles, and it largely operates on pixels horizontally within a tile, making it slow. Explained on forum, and with an improvement by tokumaru to reduce the overhead of a frequency table change.

Common byte

Oracle common byte

This codec, used in The Legend of Zelda: Oracle of Seasons and The Legend of Zelda: Oracle of Ages according to Dwedit, is roughly comparable to RLE in complexity. For each 16-byte block, the compressor determines the most common byte in that block. The compressed data for each block starts with a 2-byte mask, then the most common byte, then other bytes in order that aren't the most common.

To decode a block: First read the two-byte mask. If the entire mask is zero, set the bit corresponding to the first byte to true. Then read the most common byte. For each bit in the mask, if the bit is 1, write the most common byte to output; otherwise, copy one byte.

Maximum expansion is 12.5%, if all bytes are distinct, as the most common byte is the first.

LZSS

MUST SHOULD MAY

The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in RFC 2119. (what's this?)

A lot of games on platforms after the NES use LZ77 family compression methods such as LZSS, which generalizes run-length encoding to allow copying data from several bytes ago, not just the previous byte. Few NES games use LZ77 because the NES's limited work RAM and limited access to video memory make it difficult to resolve back references. (Fewer still use LZW or any other LZ78-based method because of patents that subsisted through the NES, Super NES, and Nintendo 64 eras.)

In LZSS, the mask contains 8 commands, each either to copy a literal byte or to copy a back reference. determines whether the next 8 things are literal bytes or back references. Once all commands have been processed, read another mask.

Read a mask byte from input.

For each bit in the mask byte:

If the bit is 0, this is a literal:

Copy one byte from input to output.

Otherwise, this is a back-reference:

Read and decode a length and distance from input. These will be positive integers.

Copy length bytes from the previous output, distance bytes before now, to output.

LZSS flavors vary mainly in how they encode lengths and distances.

LZ77UnComp

The Game Boy Advance BIOS has a built-in decompressor for a straightforward LZSS flavor with 3- to 18-byte references into the previous 4096 bytes of output, as described in Martin Korth's GBATEK. One restriction is that in data intended for decompression directly to video memory, the second byte of a 16-bit word MUST NOT refer to the first byte of the same word. This means the encoder MUST NOT write a distance of 1 if the length of the uncompressed data so far is odd.

Oracle LZ

This flavor of LZSS is used in The Legend of Zelda: Oracle games for Game Boy Color according to Dwedit.

An entire compressed block can be compressed with one of two subtypes of Oracle LZ: short word mode and long word mode. Short words use references of 2 to 8 bytes into the previous 32 bytes of output, and long words use references of 3 to 33 bytes into the previous 2048 bytes. (A length value of 0 means read an additional byte and use that as the length.) Only short words would work very well on NES.

External links

• Ad Hoc Compression Methods: RLE describes various pixel-level RLE methods applied to a drawing of a Pokémon