RLE Compression for Bitmaps

• Download binary - 11.01 KB
• Download source - 6.19 KB

Introduction

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 http://en.wikipedia.org/wiki/BMP_file_format for bitmap file format, or go directly to http://en.wikipedia.org/wiki/Run-length_encoding, if you are interested in RLE compression more.

Background

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{
    public:
       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

RLE in BMPs

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) + 
	sizeof(bitmapinfoheader);

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
   else  
      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++)
  free(Output[i]);
free(Output);
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

History

• 29.08.2010 - First publication, comments and class encapsulation