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.

External links

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