Algorithm Alley

Peering beneath the surface of a Windows bitmap (you don't need a snorkel, just a debugger) reveals several interesting facts about bitmap files and the algorithms for compressing them. The techniques are briefly described in the Microsoft Windows Programmer's Reference, Volume 4: Resources, but to my knowledge, they have never been expressed in algorithm form. Because I had only that book's sketchy descriptions to guide me, my first attempts to lay down the steps failed. Finally, I cracked the puzzle by devising a suite of test programs to compress and decompress make-believe pixel values stored in plain text files. This approach made debugging easier, and because my sample test files were in ASCII, I could easily create and modify them with a text editor--far easier than creating real bitmap files using a drawing program. It also was no trouble to write another program for creating sample bitmaps at random--part of a "Monte Carlo" test that I'll describe next month. All of this advance work paid off in the final compression utility, which successfully packed a bitmap on the program's maiden voyage. (Okay, maybe I got lucky, but anyway, it's a real ego booster to write code that works on the first try.)

This month, I'll describe the Windows bitmap compression and decompression algorithms and list two of the programs in the test suite. Next month, I'll list the remaining test programs and the final bitmap compressor. Although in past columns, I've used pseudocode for algorithms and Pascal for sample listings, this time I'll present the algorithms in Pascal and the programs in C++ (which for other reasons, this project required). The sample programs are not object oriented, so it shouldn't be difficult to convert them to other languages.

A device-independent bitmap (DIB) file begins with various headers that describe the image and its colors. Following this information is an array of pixels in one of several formats. Monochrome bitmaps are stored one bit per pixel; 16-color bitmaps take four bits per pixel; 256-color bitmaps use one 8-bit byte per pixel; and so-called "true-color" bitmaps use a whopping 24 bits for each pixel. Most pixel values are actually indexes into the bitmap's color table--a pixel p's color equals colorTable[p]. In a true-color image, which lacks a color table, pixels directly represent red-green-blue (RGB) colors.

You can find more information on bitmap file formats in many Windows programming books. I'll focus here on a bitmap's array of pixels and ignore the other information in the DIB file. I'll describe the compression method for 8-bit, 256-color images, but the techniques are very nearly the same for 4-bit, 16-color files.

Bitmap pixels are compressed using a combination of three modes. In run-length-encoded mode (RLE), 2-byte "compression units" represent from 1 to 255 runs of pixels, all of the same color. The unit 04 07, for example, packs 4 pixels of color 07. In escape mode, the first byte is 0 and the next byte signifies one of three special instructions: 0 to mark the end of the scan line (the proper term for a horizontal row of pixels), 1 for the end of the bitmap, or 2 for a delta command, sometimes called a "move instruction." Delta commands are followed by two more bytes that represent horizontal and vertical offsets to where the next pixel should appear. For example, the delta unit 00 02 05 08 indicates that the next pixel is to be drawn five positions to the right and eight down from the current location. Deltas are useful for compressing foreground images to be drawn on a fixed background (an important animation technique), but they aren't that valuable for compressing run-of-the-mill bitmaps.

In the third and final compression unit, called absolute mode, the first byte is 0 and the next byte is 3 or greater, representing the number of uncompressed pixels that follow. For instance, the absolute-mode unit 00 03 09 08 07 encodes the three pixel values 09, 08, and 07. Because absolute-mode runs must have three or more pixels--just one of several undocumented quirks in the algorithms--different-color runs of one or two pixels must be expanded using RLE pairs. For example, an absolute run of two adjacent pixels 09 and 07 must be encoded as 01 09 01 07 (one 09 and one 07). This means that compressed files with few same-color runs might actually grow in size. Obviously, in such cases, there would be nothing to gain from compressing the file.

I wrote the sample programs in this column for DOS in order to keep the listings short. If anyone cares to rewrite the programs for Windows, I'd be interested in receiving them in care of DDJ. Or, you can upload files (compressed text only, please) to my CompuServe ID, 73627,3241. Next month, I'll list the rest of the programs in the test suite along with the final utility that can compress real Windows bitmap files.

Meanwhile, I wonder where that sea turtle is right now and whether she noticed my panicked race back to the boat. Call me paranoid, but I can't shake the image of a smart-aleck turtle going around harbors, pulling up anchors, and watching the fun. You don't suppose that's possible, do you? Nah.

0A 04
01 01 01 02 02 02 02 02 03 03
01 02 03 04 05 06 07 08 09 0A
01 02 03 04 04 04 01 02 03 04
01 02 01 02 01 02 01 02 01 02

<a name="0248_000c">
{ bpack.txt -- Algorithm #10: Pack 8-bit Windows bitmap by Tom Swan }

const
  READING = 0;
  ENCODING = 1;
  ABSMODE = 2;
  SINGLE = 3;
  ENDOFLINE = 4;
  NOSTATE = 999;

procedure PackRLE8(
  np: Integer; sl: ScanLine);
var
  slx: Integer;
  state: Integer;
  pixel: Integer;
  count: Integer;
  done: Boolean;
  oldcount: Integer;
  oldslx: Integer;
begin
  slx := 0; { Scan line index }
  state := READING;
  done := False;
  while not done do begin
    case state of

    READING:
  (* Input:
     np = # pixels in scan line
     sl = scan line
     sl[slx] = next pixel *)
    begin
      if slx >= np then
        state := ENDOFLINE
      else if slx = np - 1 then
      begin
        count := 1; { 1 pixel left }
        state := SINGLE
      end else
      if sl[slx] = sl[slx + 1] then
        state := ENCODING
      else
        state := ABSMODE
    end;

    ENCODING:
  (* Input:
     slx <= np - 2 (Run of 2+ pixels)
     sl[slx] = first pixel of run
     sl[slx] = sl[slx + 1] *)
    begin
      count := 2;
      pixel := sl[slx];
      slx := slx + 2;
      while ((slx < np) and
        (pixel = sl[slx]) and
        (count < 255)) do
      begin
        count := count + 1;
        slx := slx + 1
      end;
      PutByte(count);  { RLE unit }
      PutByte(pixel);
      state := READING
    end;

    ABSMODE:
  (* Input:
     slx <= np - 2 (Run of 2+ pixels)
     sl[slx] = first pixel of run
     sl[slx] <> sl[slx + 1] *)
    begin
      oldslx := slx;  { Save index }
      count := 2;
      slx := slx + 2;
      { Compute # bytes in run }
      while ((slx < np) and
        (sl[slx] <> sl[slx - 1]) and
        (count < 255)) do
      begin
        count := count + 1;
        slx := slx + 1
      end;
      { Back up on same-color run }
      if ((slx < np) and
          (sl[slx] = sl[slx - 1]))
        then if (count > 1)
          then count := count - 1;
      slx := oldslx;
      if (count < 3 ) then
        state := SINGLE {short run}
      else begin  {normal run}
        PutByte(0);
        PutByte(count);
        oldcount := count;
        while (count > 0) do
        begin
          PutByte(sl[slx]);
          slx := slx + 1;
          count := count - 1
        end;
        if Odd(oldcount) then
          PutByte(0);  {word padding}
        state := READING
      end { else }
    end;

    SINGLE:
  (* Input:
     count = # pixels to output
     slx < np
     sl[slx] = first pixel of run
     sl[slx] <> sl[slx + 1] *)
    begin
      while count > 0 do
      begin
        PutByte(01);
        PutByte(sl[slx]);
        slx := slx + 1;
        count := count - 1
      end;
      state := READING
    end;

    ENDOFLINE:
    begin
      PutByte(0);
      PutByte(0);
      done := TRUE;
      state := NOSTATE
    end;
    else
    begin
      Writeln('Unknown state');
      Halt
    end
   end { case state of }
  end { while }
end; { PackRLE8 }

begin
  Read(np);
  Read(ns);
  while (ns > 0) do
  begin
    GetNextScanLine(sl);
    PackRLE8(np, sl);
    ns := ns - 1
  end;
  PutByte(0);  { Mark bitmap end }
  PutByte(1)
end.


(*
// --------------------------------------------------------------
// Copyright (c) 1993 by Tom Swan. All rights reserved
// Revision 1.00    Date: 04/27/1993   Time: 09:00 am
*)

<a name="0248_000d"><a name="0248_000e">

 /* ----------------------------------------------------------- *\<a name="0248_000e">
**  tunpack.cpp -- Test unpacking compressed bitmap data       **
** ----------------------------------------------------------- **
**                                                             **
**  Note: Delta escape-code unpacking is not implemented.      **
**                                                             **
** ----------------------------------------------------------- **
**     Copyright (c) 1993 by Tom Swan. All rights reserved.    **
\* ----------------------------------------------------------- */

#include <iostream.h>
#include <iomanip.h>
#include <fstream.h>
#include <stdlib.h>

typedef unsigned char Byte;

#define FALSE 0
#define TRUE 1

// Compression escape codes
#define ESCAPE 0

#define ENDOFLINE 0
#define ENDOFBITMAP 1
#define DELTA 2

void Error(const char *msg);
void DecompressFile(const char *fname);
int Odd(int v);
int GetByte(ifstream &ifs);
void PutByte(unsigned char b);

int main(int argc, char *argv[])
{
  if (argc <= 1)
    Error("filename missing");
  DecompressFile(argv[1]);
  return 0;
}

// Display error message and halt
void Error(const char *msg)
{
  cerr << endl << "Error: " << msg << endl;
  exit(1);
}

// Decompress fake bitmap file fname
// Write decompressed results to stdout
void DecompressFile(const char *fname)
{
  int endOfBitmap;  // True if 00 01 found at end of input
  int count;        // Used at various locations in function
  int oldCount;     // Copy of count for absolute-mode units
  unsigned byte;    // Input bytes

  ifstream ifs(fname, ios::in);
  if (!ifs)
    Error("unable to open file");
  endOfBitmap = FALSE;
  while (!endOfBitmap && !ifs.eof()) {
    byte = GetByte(ifs);
    if (byte == ESCAPE) {
    // Unpack escape code unit
      byte = GetByte(ifs);
      switch (byte) {
        case ENDOFLINE:
          cout << endl;
          break;
        case ENDOFBITMAP:
          endOfBitmap = TRUE;
          cout << endl;
          break;
        case DELTA:
          Error("Delta escape codes not implemented");
          break;
        default:  // Absolute-mode run
          count = byte;
          oldCount = count;
          while (count > 0) {
            byte = GetByte(ifs);
            PutByte(byte);
            count--;
          }
          if (Odd(oldCount))
            byte = GetByte(ifs);  // Read word-boundary padding byte
          break;
      }
    } else {
    // Unpack run-length-encoded unit
      count = byte;
      byte = GetByte(ifs);
      while (count > 0) {
        PutByte(byte);
        count--;
      }
    }
  }
  if (!endOfBitmap)
    Error("End of bitmap marker (00 01) not found");
}

// Return next byte from input file ifs
// Count number of bytes read
int GetByte(ifstream &ifs)
{
  int b;
  ifs >> hex >> b;
  return b;
}

// Return true if v is odd
int Odd(int v)
{
  return v & 0x01;
}

// Write byte b in hex in 2 columns with leading 0
// plus one blank to cout
void PutByte(unsigned char b)
{
  cout << setiosflags(ios::uppercase);
  cout << setw(2) << setfill('0') << hex << (int)b << ' ';
  cout << setfill(' ') << dec;
  cout << resetiosflags(ios::uppercase);
}


// --------------------------------------------------------------
// Copyright (c) 1993 by Tom Swan. All rights reserved.
// Revision 1.00    Date: 04/27/1993   Time: 08:55 am

<a name="0248_000f"><a name="0248_0010">

<a name="0248_0010">
/* ----------------------------------------------------------- *\
**  tpack.cpp -- Test packing uncompressed bitmap data         **
** ----------------------------------------------------------- **
**                                                             **
**  Data file format (in ASCII hex):                           **
**                                                             **
**  np ns                   # pixels per line; # scan lines    **
**  pp pp pp pp pp ... pp   pixel byte values in hex           **
**  pp pp pp pp pp ... pp      "        "        "             **
**  pp pp pp pp pp ... pp      "        "        "             **
**                                                             **
** ----------------------------------------------------------- **
**     Copyright (c) 1993 by Tom Swan. All rights reserved.    **
\* ----------------------------------------------------------- */

#include <iostream.h>
#include <iomanip.h>
#include <fstream.h>
#include <stdlib.h>

typedef unsigned char Byte;

#define FALSE 0
#define TRUE 1

// State-machine definitions
#define READING 0    // General reading mode
#define ENCODING 1   // Encoding same-color pixel runs
#define ABSMODE 2    // Encoding different-color pixel runs
#define SINGLE 3     // Encoding short absolute-mode runs
#define ENDOFLINE 4  // End of scan line detected

void Error(const char *msg);
void CompressFile(const char *fname);
int Odd(int v);
Byte *NextScanLine(ifstream &ifs, int np);
void PutByte(Byte b);
void PackRLE8(int np, const Byte *sl);

int main(int argc, char *argv[])
{
  if (argc <= 1)
    Error("filename missing");
  CompressFile(argv[1]);
  return 0;
}

// Display error message and halt
void Error(const char *msg)
{
  cerr << endl << "Error: " << msg << endl;
  exit(1);
}

// Compress test bitmap file fname
// Write compressed results to stdout
void CompressFile(const char *fname)
{
  int np, ns;  // Number of pixels per line, number of scan lines
  Byte *sl;    // Pointer to scan line

  ifstream ifs(fname, ios::in);
  if (!ifs)
    Error("unable to open file");
  ifs >> hex >> np >> ns;
  if ((np <= 0) || (ns <= 0))
    Error("bad file format");
  while (ns-- > 0) {
    sl = NextScanLine(ifs, np);
    PackRLE8(np, sl);
    delete sl;
  }
  PutByte(0);  // Mark end of bitmap
  PutByte(1);
  cout << endl;
}

// Return true if v is odd
int Odd(int v)
{
  return v & 0x01;
}

// Read next scan line of np pixels from file ifs
Byte *NextScanLine(ifstream &ifs, int np)
{
  if (np <= 0) Error("np zero or less in NextScanLine()");
  Byte *sl = new Byte[np];   // Allocate scan line
  if (!sl) Error("out of memory");
  int j = 0;
  int k;
  while (np-- > 0) {
    ifs >> hex >> k;
    sl[j++] = k;
  }
  return sl;
}

// Write byte b in hex in 2 columns with leading 0
// plus one blank to cout
void PutByte(Byte b)
{
  cout << setiosflags(ios::uppercase);
  cout << setw(2) << setfill('0') << hex << (int)b << ' ';
  cout << setfill(' ') << dec;
  cout << resetiosflags(ios::uppercase);
}

// Compress np pixels in sl
// Write compressed line to stdout
void PackRLE8(int np, const Byte *sl)
{
  int slx = 0;           // Scan line index
  int state = READING;   // State machine control variable
  int pixel, count;      // Used by various states
  int done = FALSE;      // Ends while loop when true
  int oldcount, oldslx;  // Copies of count and slx

  while (!done) {

    switch (state) {

      case READING:
      // Input:
      // np == number of pixels in scan line
      // sl == scan line
      // sl[slx] == next pixel to process

        if (slx > np) Error("READING in PackRLE8()");

        if (slx >= np)                      // No pixels left
          state = ENDOFLINE;
        else if (slx == np - 1) {           // One pixel left
          count = 1;
          state = SINGLE;
        } else if (sl[slx] == sl[slx + 1])  // Next 2 pixels equal
          state = ENCODING;
        else                                // Next 2 pixels differ
          state = ABSMODE;
        break;

      case ENCODING:
      // Input:
      // slx <= np - 2 (at least 2 pixels in run)
      // sl[slx] == first pixel of run
      // sl[slx] == sl[slx + 1]

        count = 2;
        pixel = sl[slx];
        slx += 2;
        while ((slx < np) && (pixel == sl[slx]) && (count < 255)) {
          count++;
          slx++;
        }
        PutByte(count);  // Output run-length-encoded unit
        PutByte(pixel);
        state = READING;
        break;

      case ABSMODE:
      // Input:
      // slx <= np - 2 (at least 2 pixels in run)
      // sl[slx] == first pixel of run
      // sl[slx] != sl[slx + 1]

        oldslx = slx;
        count = 2;
        slx += 2;
        // Compute number of bytes in run
        while ((slx < np) && (sl[slx] != sl[slx - 1]) && (count < 255)) {
          count++;
          slx++;
        }
        // If same-color run found, back up one byte
        if ((slx < np) && (sl[slx] == sl[slx - 1]))
          if (count > 1) count--;
        slx = oldslx;  // Restore scan-line index
        // Output short absolute runs of less than 3 pixels
        if (count < 3 )
          state = SINGLE;
        else {
          // Output absolute-mode run
          PutByte(0);
          PutByte(count);
          oldcount = count;
          while (count > 0) {
            PutByte(sl[slx]);
            slx++;
            count--;
          }
          if (Odd(oldcount))
            PutByte(0);  // End run on word boundary
          state = READING;
        }
        break;

      case SINGLE:
      // Input:
      // count == number of pixels to output
      // slx < np
      // sl[slx] == first pixel of run
      // sl[slx] != sl[slx + 1]

      while (count > 0) {
        PutByte(01);
        PutByte(sl[slx]);
        slx++;
        count--;
      }
      state = READING;
      break;

      case ENDOFLINE:
        PutByte(0);
        PutByte(0);
        done = TRUE;
        break;

      default:
        Error("unknown state in PackRLE8()");
        break;
    }
  }
}


// --------------------------------------------------------------
// Copyright (c) 1993 by Tom Swan. All rights reserved.
// Revision 1.00    Date: 04/27/1993   Time: 09:07 am

Copyright © 1993, Dr. Dobb's Journal