This page is a mirror of Tepples' nesdev forum mirror (URL TBD).
Last updated on Oct-18-2019 Download

Compression in ROM?

Compression in ROM?
by on (#53602)
In a few games compression has been used to fit the data within limits of ROM. e.g in MC kids level maps are stored(I guess in PRG rom!) in a compressed format. What type of compression could it be? run-length ecoding or something else?

by on (#53603)
The programmers said it was huffman. (Also, a few levels are stored in CHR-ROM)

by on (#53605)
Each game has its own compression mode.

It could be :
    1 - Huffman compression
    2 - Run Length Encoding compression
    3 - Dual Tile Encoding compression
    4 - Multiple Tile Encoding compression
    5 - Weird unique compression format that only reverse engineering can understood :)

by on (#53612)
Run Length Encoding has a generalized form, called Lempel-Ziv or LZ77. RLE keeps track of one previous byte,* and a "run" is repeats of L copies of that byte. LZ77 keeps track of a history of more bytes, and a "run" copies starting from any point in the history buffer. This allows an RLE-style run (e.g. start offset = -1, run length = 10), but it also allows repeating a sequence of bytes (e.g. start offset = -5, run length = 10) or repeating a string from the history buffer (e.g. start offset = -35, run length = 5). A lot of games especially on the Super NES and GBA used LZ77, and the .zip and .png formats use LZ77 combined with Huffman coding.

* Here, I use "byte" to refer to code units. These can be larger than 1 octet in some cases, such as compression of high- or true-color images.