Compression in ROM?

[Nadia]

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?

[Dwedit]

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

[Rid]

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

[tepples]

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.