Data Compression

“Many a cracker spent a whole night waiting for the compression program to finish its work,” the C64 coder Antitrack wrote in 1998. A single side of a 1541 floppy held 664 free blocks, about 170K, and a smaller program meant more on the disk and a shorter wait at the loading screen. So crackers and demo coders let their C64s grind through a 230-block program for “up to seven hours” to make it smaller still. Amiga owners watched the screen flash with colour while a crunched program unpacked itself. Cartridge programmers stored their tile graphics compressed to fit a smaller ROM. And demo coders turned compression into a sport, packing a 3D intro and its music into 64K, or into 4K.

Data compression stores data in fewer bytes and restores it when it is needed. It always costs something: a decoder that takes up room of its own, time to run it, and memory to run it in.

Fast facts

• What it does: removes repetition and predictability from data, so the same information takes fewer bytes.
• Common methods: run-length encoding, LZ77-style back-references, Huffman and arithmetic coding, and combinations of them.
• The price: decoder size, unpacking time and working memory.
• Where it mattered most: floppy disks, cartridge ROM, and demo-scene size limits.

The basic ideas

Run-length encoding

Run-length encoding (RLE) replaces a run of identical values with a count and the value:

The decoder is tiny and fast, which is why, as the C64 compression programmer Pasi Ojala wrote in C=Hacking in 1998, it “has been used since day one in C64 compression programs”. The weakness is that it only helps with runs. A scheme that stores every byte as a count and a value doubles the size of data without them, so real RLE formats mark which bytes are runs and which are copied as they are. Ojala noted that on the C64 “only graphics and music data contain large runs of identical bytes. Program code rarely contains more than a couple of successive identical bytes.” See Run-length encoding.

LZ77: pointing back at earlier data

In 1977 Ziv and Lempel proposed replacing repeated data with a reference to an earlier copy of it. Each item in the compressed stream is either a literal byte or a back-reference: go back offset bytes in what you have already decoded and copy length bytes from there.

Input:    ABCABCABCXYZ
Encoded:  A B C (offset=3, length=6) X Y Z

Six literal bytes and one reference stand for twelve bytes. The reference copies more bytes than it reaches back, which works because the decoder copies one byte at a time and each copied byte is then available to copy again. Whether this saves anything depends on how many bits a reference costs. “As long as it takes fewer bits to represent the reference and the phrase length than the phrase itself,” Ojala wrote, “we get compression.”

Many LZ77 variants add a flag to each item to say whether a literal or a reference comes next. The Mega Drive’s Sonic the Hedgehog shows one in 68000 code: its decompressor reads a 16-bit “description field” and takes one bit per item, copying a byte “as-is” when the bit is set and otherwise copying a run from earlier in the output.

A second family, LZ78 and its descendants such as LZW, builds a dictionary of phrases as it goes and sends dictionary numbers instead; Ojala’s example of LZW uses a dictionary of 4,096 entries. Ojala judged LZ78 “not practical for C64, because the decompressor needs to create and update the dictionary”, which would take too much of the machine’s memory and time.

Huffman coding

Huffman coding gives common values short codes and rare values long ones, with no code the start of another, so the decoder always knows where one ends:

This example is the ideal case. Huffman codes are only perfectly efficient when every probability is a half, a quarter, an eighth and so on, because each code has to be a whole number of bits. Arithmetic coding gets around that limit by representing the whole message as a single fraction between 0 and 1, which each symbol narrows according to its probability, so a very likely symbol can cost less than one bit. LZ77 and Huffman work well together, because the literals, lengths and offsets that LZ77 produces are unevenly spread. Zip, LHa and gzip all combine them; the DEFLATE format that gzip uses is defined as “a combination of the LZ77 algorithm and Huffman coding”.

Delta encoding

Delta encoding stores the difference between each value and the one before, which turns slowly changing data into small numbers that other methods compress well:

heights: 100 102 103 105 108 110
deltas:  100  +2  +1  +2  +3  +2

Home computers: packers and crunchers

C64

Compression on the C64 grew up in the cracking and demo scenes. Pontus Berg’s history in C=Hacking 16 (1998) divides the native tools into two families that were usually run one after the other: packers, which run-length encode (the first he used was Flash Packer), and crunchers, which replace repeated byte sequences with references to earlier ones. That is the LZ77 idea, though “several 64 compression authors were not aware of LZ77 when designing their programs!”

The economics were plain: a packer alone gained about 30%, a cruncher another 10–20% on top, and “almost any game or demofile” ended up at 50–60% of its original size. Crunching was slow enough to shape working habits. Time Cruncher took “a few hours”, Cruel Crunch ran overnight, and Antitrack’s 1998 article on speeding up LZ crunching opens with a 230-block file taking “up to seven hours”. REU-based crunchers cut that to minutes. Crackers also used level crunchers, which unpack data as it loads instead of running a depacker afterwards.

The next step was to take the compressor off the C64. Pasi Ojala’s Pucrunch, whose development log in C=Hacking 17 begins in March 1997, is written in ANSI C and produces self-extracting files for the C64, C128, VIC-20 and C16/Plus/4: “a cross-compressor, if you will”. It is a hybrid of LZ77 and RLE with Elias gamma codes for lengths, and its decompressor is about 300 bytes of 6510 code plus 34 bytes of parameters. The cross-crunchers in use since then are compared on Codebase64’s benchmark page (Pearl for Pigs corpus, measured in February 2016, sizes excluding the unpacker):

The table shows the trade-off at work. Exomizer buys its ratio with a decoder two to three times slower than ByteBoozer, Bitfire or Doynamite, which is why Codebase64’s tools page files it as “Slower, better results” and ByteBoozer as “Fast(er), ok results. Made for demos, also integrated decruncher with loader.” These tools travel beyond the C64: César Nicolás González told Retro Gamer in 2012 that squeezing his Amstrad CPC version of Bubble Bobble meant switching “from Mayhem’s MegaLZ to Jorgen Ibsen’s apLib, and then to Magnus Lind’s Exomizer”.

Amiga

In December 1989 Amazing Computing announced that “all Amiga users have access to an executable compressor in the form of Power Packer”, a $15 shareware program by Nico François. A crunched program carries its own decruncher and unpacks itself when run, and PowerPacker offered five levels of compression and would, the magazine said, “in most cases … reduce the size of programs by 50 percent or more”. It could not handle programs that load in parts, called overlays, such as Deluxe Paint.

By 1991 crunchers had multiplied. One public-domain library’s advertisement in Amiga Format that June offered a single disk carrying Byte Killer, Crunch Master, Data Cruncher, DefJam Cruncher, Flash Packer, Mega Crunch, Power Pack, RSI Cruncher, Super Cruncher and more. In Professional Amiga User that August, David Jacobs explained the flashing screens that Amiga owners saw on demo disks: “These programs have been compacted or crunched and the flashing colours tell the user that something is happening.” He compared PowerPacker, by then a commercial product at version 3.0, with Turbo Imploder, a former commercial cruncher he said had been released into the public domain:

Imploder made the smallest files and had the fastest decruncher, but it could only crunch programs and system files. PowerPacker could also crunch data such as text, pictures and animations, which viewers like PPMore and PPShow unpacked as they read them. Jacobs reported average savings of 30–40%, and crunching a Workbench 1.3 boot disk with Imploder freed “about 29% or 240K”.

Cartridges: compression in ROM

NES

An NES cartridge supplies the tile graphics to the video chip in one of two ways. With CHR ROM, the tiles sit in a ROM chip the video hardware reads directly, so they cannot be compressed. With CHR RAM, the game copies tiles into RAM on the cartridge, so it can store them compressed in program ROM and unpack them on the way. The NESdev Wiki says this “is fairly common with tile data in games that use CHR RAM”, and names Blades of Steel, the American Contra, the Japanese Simon’s Quest and Bee 52 as examples. It notes that the graphics in the Konami and Codemasters games it names are run-length encoded. The wiki’s advice to homebrew developers today is to consider compression when a game’s tile data is “just a shade over” a power of two, so that it fits the next size of ROM down.

Level maps are often shrunk without a general-purpose compressor at all, by building them from larger blocks of tiles; see Tile graphics.

Mega Drive

Sonic the Hedgehog (1991) uses three formats, known in the fan-made disassembly of the game as Nemesis, Kosinski and Enigma. Nemesis holds the tile art and unpacks straight into video memory; more than 150 of the game’s art files use it. Kosinski, the LZ77-style format described above, holds the 256-by-256-pixel chunks each zone’s levels are built from. Enigma holds tile maps, such as the 16-by-16 blocks, the title screen and the special stage backgrounds, and adds a starting tile number to each entry as it unpacks.

Demo scene: packing the executable

On the PC the demo scene set size limits for whole programs: 64K intros, 4K intros and smaller. Here the compressor is part of the program, so its decoder counts against the limit too.

kkrunchy, written by Fabian Giesen, ryg of farbrausch, was made for 64K intros. Its first version (2003–2005) used an LZ77 coder with an arithmetic-coding back end and a depacker of about 300 bytes. The second (2006–2008) used context mixing in the style of the PAQ compressors, blending the predictions of several models for every bit, with a 1.5K depacker. It also transforms x86 code before compressing it, sorting each instruction’s bytes into separate streams of similar values. Farbrausch used it from fr-030: Candytron in 2003, and groups including Fairlight, Conspiracy and Equinox used it for their own 64K intros.

Crinkler, by Aske Simon Christensen (Blueberry) and Rune L. H. Stubbe (Mentor), first released in July 2005, was made for 4K intros. It replaces the linker, the program that assembles compiled code into an executable, with “a combined linker and compressor”, which lets it arrange the program’s pieces to compress better. Its compression is “based on context modelling”, which its authors describe as “extremely slow, but this is of little importance when only 4 kilobytes need to be compressed”. Its authors made it open source under the zlib licence in July 2020, and kkrunchy’s source has been in the public domain since farbrausch published its tools in April 2012. A 256-byte intro could not even hold kkrunchy’s smallest depacker, which is about 300 bytes.

The skills crossed back into commercial work. Giesen joined RAD Game Tools in 2010 and works on Oodle, a data compression library licensed by game developers, including those using Unreal Engine.

Trade-offs

See also

• Run-Length Encoding
• Tile Graphics
• Bank Switching
• Size Coding
• Cracking scene
• Demo Scene
• ryg