Run-length encoding

Atari ST - Savage Paint PAC

Single bit plane. The five most common bytes in the image was followed by a run-length byte. It was simpler and gave a higher compression ratio than the run-length algorithm used in the .IFF format on the Amiga. The reason for using the 5 most common bytes was mainly because of the number of free registers in the MC68000 CPU.

Amiga - IFF RLE (PackBits)

One or more bit planes. Runs longer than 2 bytes are encoded as -1 to -127 followed by the byte to be repeated (-n) + 1 times. Runs of different bytes are stored as 0 to 127 followed by n + 1 bytes of data. The byte code -128 is a no operation.

Head-On - BEAR3

Indexed graphics, 8 bits per pixel. The range 0 to n was used by pixel data. The range n + 1 to 255 was the run lengths. Run-length = (byte - n) + 1. The main goals were fast, simple and compressible with ZIP for distribution.

JPEG - RLC

For each value that is not 0, precede it with the count of 0's that went in front of the value. The result is a string of (count, value) pairs. If all the remaining values are 0 the block is terminated with an End Of Block marker (0, 0). The longest possible run is 15 to make sure the following Huffman coding is efficient. If a run is longer than 15 it is extended with pairs of (15, 0) which means 16 0's.

Unnamed

After a run of n symbols a run-length is inserted. That way no space is wasted on areas that do not compress and all symbols can still be used for data.

Stack-run based ideas

Each bit in a number is encoded with two bits, that way it is possible to signal the end of a number so each number can have a variable number of bits and there is no limit to the size of a number. If the number is increased by 1 before encoding, all numbers will have a 1 as the leftmost bit. That means it can be left out and the decompressor can just insert 1 to the left of the last decoded bit in the number.

Alternating runs and incompressible

00 - 0
11 - 1
10 - 0 end
01 - 1 end

Alternating black/white runs

00 - 0
11 - 1
10 - 0 end
01 - 1 end