Run-Length Encoding

In the mid-1980s anyone with a modem and the right terminal program could call CompuServe and watch a National Weather Service radar map draw itself on their home computer. The map arrived as plain text. The Transactor explained the trick to Commodore owners in 1987: CompuServe’s RLE format described each line of the picture as a count of dark pixels, then a count of light ones, then dark again, each count sent as a printable character with 32 added to it. A line that began with 95 dark pixels went out as character 127 followed by a space, which meant no light pixels before the next dark run. Because every computer could receive text and every screen was made of pixels, the same file could be drawn on many makes of computer. CompuServe went on to publish pictures of the FBI’s ten most wanted and of missing children the same way, and users wrote programs to turn their own drawings into RLE files.

That is run-length encoding (RLE) in its purest form: instead of storing every value, store how many times it repeats. It is the simplest way to compress data, and its decoder fits in a few dozen bytes of machine code and runs almost as fast as a plain copy. Those two facts kept it in use on every machine of the period, usually inside something more elaborate.

The idea, and its weak spot

The simplest scheme stores a count and a value for every run:

Long runs shrink a lot; short ones cost more than they save. Data with no runs at all, such as machine code, doubles in size. As the C64 programmer Pasi Ojala put it in 1998, “only graphics and music data contain large runs of identical bytes. Program code rarely contains more than a couple of successive identical bytes.” So almost every real RLE format is really a way of marking which bytes are runs and which should be copied as they are.

Three ways to mark a run

An escape byte. Pick a byte value that rarely or never occurs in the data and use it to mean “a run follows”. Everything else is copied straight through. Pontus Berg’s history of C64 compression gives the example of AAAAAA becoming x A 6, “where x is a control character to tell the decompressor that the next two bytes represent a run”. C64 packers read the file twice, he wrote, “one for determining the bytes to use as controlbytes and one to create the packed file”.

The Spectrum’s .Z80 snapshot format, devised by Gerton Lunter for his Z80 emulator, uses a two-byte escape. Its compressed memory blocks replace “repetitions of at least five equal bytes by a four-byte code ED ED xx yy”, meaning byte yy repeated xx times. A real ED ED in memory would look like the escape, so the format stores even two EDs in a row as a run: ED ED 02 ED.

A count byte that says which kind of block follows. The Macintosh’s PackBits, adopted by the Amiga’s IFF picture format under the name ByteRun1, reads a signed count byte n. From 0 to 127 it means “copy the next n + 1 bytes as they are”; from −1 to −127 it means “repeat the next byte −n + 1 times”; −128 does nothing. Incompressible data now grows by at most one byte in 128. The IFF specification tells encoders to “always encode 3 byte repeats as replicate runs”, while a 2-byte repeat is worth turning into a run only if it is not sandwiched between literal blocks.

GEOS, the graphical operating system for the C64, used three kinds of block. Its Programmer’s Reference Guide sets out a count byte from 0 to 127 for a repeated byte, 128 to 220 for that many literal bytes (less 128), and 221 to 255 for BIGCOUNT, which repeats a whole multi-byte pattern: four repeats of the 4-byte pattern xxxy take 6 bytes instead of 16.

Alternating counts. For a picture with only two colours there is no value to store at all. CompuServe’s format sends only counts, and the colour alternates between dark and light with each one.

Which way to run

A run is only as long as the data’s layout allows. GEOS’s bitmap format undoes the C64’s character-cell screen layout before compressing, putting bytes in scanline order because “bit-mapped data compacts much better horizontally”. The Amiga’s ILBM format packs each row of each bitplane separately. For animation the other direction can win: the Amiga’s IFF ANIM format, developed at Sparta, came to rely on “the vertical run length encoded byte encoding developed by Jim Kent”, which works down columns of the picture.

The NES helps with either direction. A program writes graphics to the video chip through a single data register, and the chip moves its address on by 1 (“going across”) or by 32 (“going down”) after each write, depending on one control bit. A run can be written down a column of the screen’s tile map as easily as across a row.

A 6502 decoder

This routine decodes the simplest format, count and value pairs ended by a count of 0, from one memory pointer to another. It assembles with ACME and with ca65 to 35 bytes.

; Decode a run-length stream from (src) to (dst).
; Stream format: count, value pairs; a count of 0 ends the stream.
; src and dst are two-byte pointers in zero page.
rle_decode:
        ldy #0              ; Y stays 0: the pointers do the moving
rle_next:
        lda (src),y         ; read the count
        beq rle_done        ; 0 marks the end of the stream
        tax                 ; X = run length, 1 to 255
        inc src             ; step past the count
        bne rle_value
        inc src+1
rle_value:
        lda (src),y         ; read the value to repeat
        inc src             ; step past the value
        bne rle_fill
        inc src+1
rle_fill:
        sta (dst),y         ; write one byte of the run
        inc dst
        bne rle_dst_ok
        inc dst+1
rle_dst_ok:
        dex
        bne rle_fill
        beq rle_next        ; always taken: X is now 0
rle_done:
        rts

Trace a stream of 3 $20 2 $2A 0 and it writes three spaces and two asterisks, then stops. On a C64, decoding a stream of 200-byte runs into screen memory at $0400 fills the screen in bands, and the destination pointer carries cleanly across each 256-byte page. Each byte of a run costs about 19 cycles: 6 for the store, 5 for the pointer increment and 8 for the branches and the counter.

On the NES the destination pointer disappears. With the video address set once beforehand, the inner loop becomes sta $2007 followed by dex and bne, and the video chip advances the address itself. Like any write to video memory, it has to happen during vertical blank or with the screen turned off; the PPU entry explains why.

Where it was used

C64: packers before crunchers

Ojala wrote that RLE “has been used since day one in C64 compression programs because it is very fast and very simple”. Berg’s 1998 history in C= Hacking describes the scene’s packers, the RLE tools that came first (the first he used was Flash Packer), and the crunchers that followed them, which replace repeated sequences of bytes with references to earlier ones. A packer saved “some 30%”. People ran both, one after the other, because “a file packed first would be smaller upon entering the crunching phase which could hence be completed much faster”, and crunching could take hours. A packer could also handle a file of almost any length, “0029 to ffff”.

Later tools built RLE in. Ojala’s cross-platform cruncher Pucrunch adds RLE to an LZ77 scheme because “run-length encoding handles long byte runs better than LZ77 and can have a bigger length limit”: its copies stop at 64, 128 or 256 bytes, but its runs can be up to 32 kilobytes long. The trade-off still shows in Codebase64’s 2016 benchmark of C64 crunchers. Plain RLE left files at 80.9% of their original size, against 48.4% for ByteBoozer 2.0 and 45.1% for Exomizer, but unpacked 47.8 kilobytes a second, against 18.4 and 7.2. See Data compression for the crunchers.

Amiga: pictures, animations and demo modes

The IFF picture standard, ILBM, makes ByteRun1 its compression method. Its standards committee, drawn from Electronic Arts and Commodore-Amiga, included Dan Silva, the author of Deluxe Paint. ANIM files store their first frame the same way and later frames as differences from earlier ones. Games used RLE for smaller jobs too: Chris Sorrell recalled that the demo mode of James Pond 2: Robocod, which replays recorded player input, kept that input “simple (run-length)” compressed “to keep size down”.

NES: tiles in program ROM

An NES cartridge with RAM for its tile graphics, rather than ROM the video chip reads directly, can keep the tiles compressed in program ROM and unpack them at load time. The NESdev Wiki names Konami’s Blades of Steel, the American Contra and the Japanese Simon’s Quest, which use RLE on bytes, and Codemasters’ Bee 52, which uses it on pixels.

ZX Spectrum: snapshots

Spectrum emulators met RLE in the .Z80 snapshot format described above, which uses it to shrink the saved memory of a Spectrum.

See also

• Data compression
• Character graphics
• Tile graphics
• PPU