Click here to Skip to main content
15,798,722 members
Articles / Programming Languages / C++

RLE Compression for Bitmaps

Rate me:
Please Sign up or sign in to vote.
3.67/5 (3 votes)
30 Aug 2010CPOL4 min read 70.6K   3.9K   13   12
RLE compression for bitmaps


BMP file format is among the first ones that were designed for storing digital image bitmap raster (there is also PCX). BMP like PCX can be RLE compressed, which can be useful or not depending on information stored in raster row. If raster contains many horizontal repeats, RLE is useful, in other case, it's just a waste of time & space. See Wiki for bitmap file format, or go directly to, if you are interested in RLE compression more.


The code presented in this article is fully C++, and uses standard I/O operations. To reimplement it into full stream buffer based model, one must deal with the filesize to be written after compression into header, because header is before compressed stream, the size of which is not known before compression. The code deals with 4 and 8 bit bitmaps, because it was defined so, that 1,24 and 32 bit bitmaps cannot be compressed.

The Code

You need to include only rle_bmp_compress.cpp file.

// the file contains only one class
class RLE_Win_Compress{
       bool RLE_Compress(char *input, char *output);

Call only one public function that is here, pass input and output file names in chars.

The compression is really simple and you should find everything needed to understand it from comments in the file(s).

How the Stuff Works


  1. Take input pixel
  2. Determine run length (run of repeats)
  3. Write run length (repeats count)
  4. Write pixel
  5. If End of Scanline, write 0x0000 if not last scanline, else write 0x0001 to mark EOF

Perhaps, it would be a good idea to describe BMP file format here, as I practically verified.

  • Compressed bitmaps contain no padding, but have to contain 0x0000 at the end of each scanline (EOL) and 0x0001 at the end of the file (EOF), where precedence takes EOF marker, so after the last scanline, there is only EOF marker, not EOL.
  • Uncompressed bitmaps, instead, do contain padding bytes, to pad scanlines into nearest 4 bytes boundary. They, however, do not contain any markers EOF nor EOL
  • Compressed bitmaps can be Absolute or encoded mode. (I use absolute mode such: BYTE count BYTE index.
  • 4 bit bitmaps run lengths can be up to 127 and 8 bit up to 255. This is given by the fact, that 4 bit bitmaps are actually 2 indices per byte, but compressed as one byte, thus first 127x and second 127x makes 254 together.

8 Bit BMP Compression Implementation

We need to read headers. There are 2 of them. BITMAPFILEHEADER and BITMAPINFOHEADER. Read them in this order. Then check for BITMAPINFOHEADER's values. They have to be set:

  • biSize = 0x28
  • biBitCount = 8 or 4
  • biCompression = 0

Check BITMAPFILEHEADER for bfType = 0x4d42.

Read bitmap palette:

PALETTEENTRY *paletteentries;
paletteentries = new PALETTEENTRY[ 256 ];
fread(paletteentries, sizeof(PALETTEENTRY), 256, f);

Next set:

  • Line width
  • Input width
  • Padding
int LineWidth = bitmapinfoheader.biWidth;
int InputWidth = LineWidth;
int padding = (bitmapinfoheader.biWidth % 4);

But we are not done with padding yet. We need to set up padding again. When we have 7 pixels wide bitmap, 7 % 4 would return 3. 3+7 = 10. Thus we need to do:

if (padding != 0) padding = 4-padding;

where 4-3 = 1, finally gives 1+7 = 8, which is correct boundary alignment, because 8 is a multiple of 4.

Allocate space for input scanline and for 2D array, to store compressed scanlines lengths:

BYTE *Input = new BYTE[LineWidth];       
int *LineLengths = new int[bitmapinfoheader.biHeight];

Allocate output buffer. This output buffer is 2D array in fact.

BYTE **Output = (BYTE **) malloc( bitmapinfoheader.biHeight * sizeof(BYTE *));
for (int i = 0; i < bitmapinfoheader.biHeight; i++){
    Output[i] = (BYTE *) malloc(((bitmapinfoheader.biWidth*2)+8) * sizeof(BYTE *));
    Output[i][bitmapinfoheader.biWidth+1] = 0; 	// for EOL
    Output[i][bitmapinfoheader.biWidth+2] = 0; 	// or EOF
    Output[i][bitmapinfoheader.biWidth+3] = 0; 	// I am not sure 
                                               	// whether is this necessary
    Output[i][bitmapinfoheader.biWidth+4] = 0;
    Output[i][bitmapinfoheader.biWidth+5] = 0;
    Output[i][bitmapinfoheader.biWidth+6] = 0;
    Output[i][bitmapinfoheader.biWidth+7] = 0;
    LineLengths[i] = 0;

Determine output filesize (for now without compressed stream):

int filesize = (sizeof(PALETTEENTRY)*256) + sizeof(bitmapfileheader) + 

Not too much to say about the compression. Just read each scanline, beware paddings and fill
up our 2D compressed buffer. Write aside line lengths as well:

int headersize = filesize;
register int Y, X;
int j;
int cnt;
bool uncompressed;
BYTE pixel;
for (Y = 0; Y < bitmapinfoheader.biHeight; Y++){
   // read input scanline
   fread(Input, bitmapinfoheader.biWidth, 1, f);
   // skip padding 
   for (X = 0; X < padding; X++)
      fgetc(f);  		// padding bytes, can be 0 or anything, do not test for 0
   // reset compression variables
   uncompressed = true;
   X = 0;
   j = 0;
   LineLengths[Y] =  0;
   while(uncompressed) 	// while end of scanline is reached
     cnt = 0;  		// set repeats to 0
     pixel = Input[j]; 	// 1 pixel
     while ( (j < InputWidth) && (pixel == Input[j]) && (cnt < 255)){
        j++;    		// move forward
        cnt++;  		// increment repeats count (run)
    if (j == InputWidth)
      uncompressed = false;	// if end of scanline is reached, set compressed to true
    Output[Y][X] = cnt;   	// write run length (repeats count)
    X++;   		// move forward
    Output[Y][X] = pixel; 	// write pixel vale (index)
    X++;   // move forward
    LineLengths[Y] = LineLengths[Y] +2; // we've written 2 bytes, incr. line l.
    filesize = filesize +2; 	// we've written 2 bytes, increase output filesize
   Output[Y][X] = 0x00;  		// ESCAPE byte...
   if (Y ==  bitmapinfoheader.biHeight-1)
      Output[Y][X+1] = 0x01;  	// denotes EOF with 0x01, when last scan is reached
      Output[Y][X+1] = 0x00;  	// EOL, else
  LineLengths[Y]+=2; 	// we written a 2 byte marker, increment output line length
  filesize+=2; // we increment filesize as well
bitmapinfoheader.biCompression =1;   //  1 = 8 bit compressed RLE
bitmapfileheader.bfSize = filesize;  // set up filesize
bitmapinfoheader.biSizeImage = filesize - headersize; 	// compressed stream size        
                                                      	// != filesize. headers
                                                      	// size is not included
                                                      	// only scanlines with padd.
// write headers
fwrite(&bitmapfileheader, sizeof(bitmapfileheader), 1, fout);
fwrite(&bitmapinfoheader, sizeof(bitmapinfoheader), 1, fout);

// write palette
fwrite(paletteentries, sizeof(PALETTEENTRY), 256, fout);
// write compressed scanlines according to their line lengths
for (Y = 0; Y < bitmapinfoheader.biHeight; Y++){          
     fwrite(Output[Y], LineLengths[Y], 1, fout); 	// write scanline

// perform cleanup       
for (int i = 0; i < bitmapinfoheader.biHeight; i++)
delete Input;
delete LineLengths;
delete paletteentries;

Points of Interest

Because this is not a very efficient compression (which RLE naturally is not), you may consider it useless. Over PNG and GIF, RLE compression is simple to implement making RLE bitmaps useful for long repeats, such as schemes, diagrams or text pictures.

Perhaps worth consideration, that although original concept of RLE and RLE in 8 bit bitmaps does not allow for longer than 1 byte sequences, 4 bit bitmaps can be of exception. Their pixel data is stored 2 pixels per byte, thus encoded as one byte in RLE.

Why All This?

Few reasons:

  • I knew that I could do it
  • It is relatively easy to understand and to implement
  • The idea, that I code it, and other program can read it and display it


  • 29.08.2010 - First publication, comments and class encapsulation


This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Written By
Software Developer (Junior) SOMI Systems
Slovakia Slovakia
Got 1st and 2nd degree from computer science in 2011 on university of Matej Bel, city of Banska Bystrica. Currently work for computer-oriented company SOMI Systems in Slovakia.
Working for SOMI Systems a.s.,

Comments and Discussions

Question[OT] contact Pin
J0ska17-Jul-11 3:28
J0ska17-Jul-11 3:28 
GeneralDoes Not Work Pin
infinateone26-Jan-11 15:05
infinateone26-Jan-11 15:05 
GeneralRe: Does Not Work Pin
Jan Mojzis30-Mar-11 3:26
Jan Mojzis30-Mar-11 3:26 
GeneralMy vote of 2 Pin
Aescleal6-Sep-10 6:27
Aescleal6-Sep-10 6:27 
GeneralI Think You Are Incorrect. Pin
Rick York30-Aug-10 10:52
mveRick York30-Aug-10 10:52 
GeneralRe: I Think You Are Incorrect. Pin
Rick York30-Aug-10 10:56
mveRick York30-Aug-10 10:56 
GeneralRe: I Think You Are Incorrect. [modified] Pin
Jan Mojzis30-Aug-10 13:46
Jan Mojzis30-Aug-10 13:46 
General[My vote of 2] Needs description of your code Pin
Richard MacCutchan29-Aug-10 11:46
mveRichard MacCutchan29-Aug-10 11:46 
GeneralRe: [My vote of 2] Needs description of your code Pin
Jan Mojzis30-Aug-10 10:11
Jan Mojzis30-Aug-10 10:11 
GeneralRe: [My vote of 2] Needs description of your code Pin
Richard MacCutchan30-Aug-10 10:49
mveRichard MacCutchan30-Aug-10 10:49 
QuestionCode? Pin
Trollslayer29-Aug-10 7:56
mentorTrollslayer29-Aug-10 7:56 
AnswerRe: Code? Pin
Jan Mojzis30-Aug-10 10:12
Jan Mojzis30-Aug-10 10:12 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.