BMP RLE (Run Length Encoding) Compression
RLE compression is probably one of the simplest compressions.
This would be a great place for a beginner to start :). RLE4
and RLE8 are used in Microsoft's BMP format. If you've read
enough of my webpages, you'll probably realize I'm not a very
big fan of Microsoft, but I must admit the BMP format (unlike
most Microsoft file formats) is actually not bad. The only
real problems I have with BMP is it stores its images upside down
(unless the height is negative) and things have to be aligned on
4 byte boundaries. Gross. But anyway, the way RLE encoding works
is if you have an image that repeats a color multiple times, you can
save disk space by storing repeated color information in the
Let's say you had a 5x5 pixel image that looks like this
(where R=red pixel, B=blue pixel, Y=yellow pixel):
In an uncomperessed BMP, you would store each color 1 byte at a time
in a file. You'd store the BMP Header Information, a color palette,
and then R,R,R,R,R, B,B,B,B,B, B,R,Y,B,R, R,B,R,B,R, Y,Y,Y,Y,Y.
This means the raw image data would take up 25 bytes. Note: I'm doing
this right side up and not taking into account that data in BMP must
be aligned. Also, note that storing a 3 color image in 8 bit is not
ideal. Anyway, in RLE8 compression, the image data could be written
as: 5,R, 5,B, 0,5,B,R,Y,B,R, 0,5,R,B,R,B,R, 5,Y.
Storing the data like this means: repeat R 5 times, repeat B 5 times,
0,5 means the next section is uncompressed for 5 bytes B,R,Y,B,R,
0,5 again means 5 bytes of uncompressed R,B,R,B,R, and then repeat
Y 5 times. This brings the picture data section down to 20 bytes.
For an example of decompressing RLE8 and RLE4, take a look at the
parse_bmp.c file of
and for an example of compression (I forgot if I used RLE4 or RLE8 here)
take a look at gif2avi from
Related Projects @mikekohn.net
SSE Image Processing,
Copyright 1997-2021 - Michael Kohn