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.

Konami RLE

This format is used in Blades of Steel, the U.S. version of Contra, and the Japanese version of Simon's Quest.

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

Konami RLE can be decoded and encoded with the Python program GraveyardDuck.

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. Compression ratio is identical to Konami RLE.

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

PB53

This codec was conceived by Damian Yerrick as an alternative to PackBits for the Action 53 multicart. Unlike freeform 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. It uses unary coding on the run lengths to save on overhead from switching between literal and run modes. It has a worst case expansion of 12.5%, but it works fairly well on real tile data and OK on nametable data. 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.
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 2000. (Used for pattern tables that share tiles, as seen in several Shiru games.)
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 operates horizontally within a tile. Explained on forum