Gratitude Day 9: Run-Length Encoding / PackBits
Wed 09 September 2026
I'm taking this little detour within my gratitude series because I want to explore some of the very basic algorithms that are an essential part of our daily lives, for which we have little awareness, and to which is given little thought or thanks.
Data Compression has always been a fascination of mine since I was a teenager. You feed some data into a program, wait some minutes, and get a representation of that data that might be half the size of the original. HOW?!?
(Of course, nowadays, it's more like feed a ton of data into a program, wait a couple seconds, and get output that might be a tenth of the size of the original!)
I don't know many details about the actual history of data compression, as it's a very old and in-depth subject that actually crosses several disciplines, but I do know that one of the most basic and earliest forms is Run-Length Encoding.
The basic idea of run-length encoding is to encode the "runs" (repeats) of a symbol, rather than encoding each repeated symbol individually.
So, on a conceptual level, taking input data that looks something like
Helloooooo, McFlyyyyyyyyy!!!!!
Could be encoded in a shorter form as something like:
1H1e2l6o1,1 1M1c1F1l9y5!
which saves two characters/symbols/bytes. Not that great.
But what if you could also record non-runs, by having two modes, one which records how many times to repeat a symbol, and another mode that tells the codec to instead just reproduce the following n bytes as-is?
That's precisely what PackBits (which is the earliest codified example of an RLE computer algorithm I could find) does.
PackBits uses a signed byte as its repeat/reproduce "code," such that a number from 0 to 127 designates how many (unrepeated) bytes to reproduce, and a number from -1 to -127 designates how many times to repeat a byte.
Let's take the above example and follow an algorithm similar to PackBits, but instead of using a signed byte like PackBits does, use numbers to designate repeats (e.g., "4" means repeat the following byte four times), and letters to designate reproducing literal (non-repeating) data (e.g., "d" means just reproduce the following four bytes without any repeats), the above example would look like this instead:
dHell6of, McFl9y5!
We have now saved twelve bytes/symbols, for a savings of 37.5%. Not too bad for such a simple algorithm!!
RLE algorithms similar to PackBits are still used today for some image processing, but also faxes.
While the compression savings isn't astounding, the impressive thing about PackBits is how much it's able to compress very small amounts of data (the example is only 29 bytes!), how fast it is, and how little overhead it has. While some of the very modern compression algorithms like LZMA can require gigabytes of RAM to compress at the highest settings, PackBits could theoretically work in only 256 bytes of RAM.
The speed, low overhead, and acceptable compression savings are probably why Bill Atkinson developed it for MacPaint. In fact, on such humble hardware (an 8 MHz 68000), MacPaint is able to compress images within about two seconds, and decompress them within one second, at least according to testing I've done with an emulator set to 1x speed.
And for such a simple algorithm, the compression savings are nothing to sneeze at.
Given this sample image, which I created in GIMP and saved as a monochrome 576x720 image (the fixed image size that MacPaint used, corresponding to an 8x10 inch page (so, 0.25" borders left and right and 0.5" borders top and bottom to a US Letter page), and then converted to MacPaint format with the macpaint_file utility:
MacPaint sample image, 576x720 monochrome
The image is the following sizes in the following formats:
bytes | format
-------+------------------
51,840 | raw
8,775 | MacPaint/PackBits
4,372 | GIF
2,480 | PNG
Now, don't go comparing MacPaint's PackBits to GIF and PNG's far more advanced (and slower) compression algorithms. The fact that PackBits is able to squeeze a 5.9:1 compression ratio is still incredibly impressive, even if GIF and PNG are able to get 11.9:1 and 20.9:1, respectively. Remember that it's getting that compression within two seconds on an 8MHz processor, compared to the minutes GIF would take on the same CPU (and I don't know if PNG would even run on 4MiB of RAM).
Back to index
Category: Tech
Tags:
ADHD
Computing
Hobbies
Monthly themes
Non-religious post
Personal favorites
Productivity
Retrocomputing
