PCX

PCX is an image file format that uses a simple form of run-length encoding (a type of lossless compression algorithm). Most PCX files use a color palette, but the format has also been extended to allow 24-bit images. PCX was quite popular on early MS-DOS and Windows systems, but is nowadays rare, having been largely replaced by formats which support better compression, such as GIF, JPEG and PNG.

PCX compresion of 8bpp indexed-color images

Decompression algorithm is very simple. Every byte from range 0x00 to 0xc0 encodes a single pixel of this value. Bytes from range 0xc1 to 0xff mean that the next 1 to 63 pixels have the same color, which is encoded in the next byte. Colors 0xc1 to 0xff are encoded using length 1 prefix followed by their code: 0xc1 COLOR.

Because colors 0x00..0xc0 are compressed better than colors 0xc1..0xff, good palette sorting is important. It's usually (but not always) enough to move the most-common colors into palette positions 0x00..0xc0, and least-used to palette positions 0xc1..0xff. Complete algorithm of sorting pallette is to count how many times a color appears 63N+1 (for nonnegative integer N) times it a row, as only in such cases it's possible to use unprefixed color values to improve compression, and move colors with higher count into indexes 0x00..0xc0, and all other to 0xc1..0xff. This is warranted to produce optimal results.

This compression algorithm is very fast and takes very little memory, but its not very efficient, especially in compressing real-world images.