Decoding DOOM Picture Files

In my previous post, I described id's WAD format used by classic games such as DOOM and how to read them. While researching the format though, I wasn't 100% sure that I was extracting lumps properly - the only readable file I'd discovered was DMXGUS in DOOM1.WAD, and also LICENSE in DARKWAR.WAD... hardly conclusive.

Armed with the specification from the DOOM FAQ, I decided to take a brief segue into decoding the pictures to verify the lumps I was extracting were valid.

The Format

Like the WAD format, id's picture format is also reasonably straightforward. It is comprised of 3 parts - a header which describes the image size and also positional information used by the DOOM engine. Then there is a column index which points to where the data for a particular column is located. The remainder of the file is comprised of the column data.

Just like a WAD, integer values are in little-endian format.

Header

Note that the X and Y offsets may be negative, this is used to absolutely position the image by the DOOM engine.

Column Index

The column index follows on immediately from the header and is a simple list of 32-bit integers, one entry for each column.

Column Data

Column data is the most tricky part of the file. Each column is divided into "posts" of up to 128 bytes each. Each post starts of with a byte indicating which row drawing will commence with, followed by the height of the post. This is then followed by an dummy byte, a sequence of bytes equal to the post height which represent indexes in a palette, followed by another dummy byte.

If the next byte after this is 255, then that is the end of the column. Otherwise, it is the start of a new post for the same column.

The following diagram shows example data for a column comprised of a single post. The row is 00, so drawing will commence with the first row. The height is 03, so there are three pixels to render. After the dummy byte are the 3 pixels values, all BF in this example. DOOM pictures are 8-bit indexed bitmaps, so these point to the palette index to use. After another dummy byte is the end of column marker FF. If there were multiple posts for this column, then the FF would instead be the new row index.

For backdrop images, multiple posts seem to be used as DOOM's native size is 320x200 and no post seems to be greater than 128 bytes. For sprite images, multiple posts are used to allow for transparency, ending a post at the start of a transparent region, and creating a new post when a solid colour resumes.

A Visual Example

As I don't think I described the format very well above, I'll try a visual example.

This is picture STCFN037 blown up 1000% given the original image is only 9x7. I've highlighted column 8 which is comprised of 5 pixels of one colour, one pixel of another, plus a single transparent pixel.

And here we have the raw data for this picture, highlighted and annotated.

Padding

I noted when examining the data of some files that padding bytes are added to the end of some images. At least one padding byte is always added if the total size of the data is an odd number, but sometimes extra bytes are added to even sizes as well (but still ensuring the final size is even).

Getting the Palette

First things first - remember that DOOM pictures are indexed bitmaps so you need a palette. As all DOOM pictures share the same palette (with numerous variations), they aren't included in the picture data and need to be supplied externally.

The attached demonstration program includes an appropriate palette, but you can also pull one out directly from a WAD file. There is a lump named PLAYPAL which contains multiple palettes in simple RGB triplets. Each palette contains 256 colours and therefore each palette is 768 bytes in length. You can use the waddemo tool from the first article to each manually extract the first 768 bytes of the PLAYPAL data, or use the Extract Palettes command to easily get them all.

private Color[] LoadPalette(string fileName)
{
  Color[] palette;
  byte[] buffer;
  int size;

  buffer = File.ReadAllBytes(fileName);
  size = buffer.Length / 3;
  palette = new Color[size];

  for (int i = 0; i < size; i++)
  {
    int offset;

    offset = i * 3;
    palette[i] = Color.FromArgb(buffer[offset], buffer[offset + 1], buffer[offset + 2]);
  }

  return palette;
}

Although this is a 24-bit palette, it is similar to the 18-bit format I have written about earlier.

Decoding the Picture

With a palette in hand, we can read the data. First we need to get the width and the height of the image. As with the previous article, I am eschewing the BitConverter class in favour of something that won't decide to reverse the bytes on a big-endian system.

As the X and Y offset are used to position the rendered image in the DOOM engine, I'm ignoring them.

Next, I initialize a byte array which will represent our pixel data. I set all the values of this to 255 as this is the colour used for transparency.

Now it's time to read the column data. For each column I set up a loop to read a post - first, get the row to render. If this is 255, I know I'm done for this column so I exit the loop. Otherwise, I get the height, skip a byte, then read the bytes for the post height, which I assign to my pixel data. Read one final byte to account for the second dummy value and back to the start of the loop.

public Bitmap Read(byte[] data)
{
  int width;
  int height;
  byte[] pixelData;

  width = WordHelpers.GetInt16Le(data, 0);
  height = WordHelpers.GetInt16Le(data, 2);

  pixelData = new byte[width * height];

  for (int i = 0; i < pixelData.Length; i++)
  {
    pixelData[i] = 255;
  }

  for (int column = 0; column < width; column++)
  {
    int pointer;

    pointer = WordHelpers.GetInt32Le(data, (column * 4) + 8);

    do
    {
      int row;
      int postHeight;

      row = data[pointer];

      if (row != 255 && (postHeight = data[++pointer]) != 255)
      {
        pointer++; // unused value

        for (int i = 0; i < postHeight; i++)
        {
          if (row + i < height && pointer < data.Length - 1)
          {
            pixelData[((row + i) * width) + column] = data[++pointer];
          }
        }

        pointer++; // unused value
      }
      else
      {
        break;
      }
    } while (pointer < data.Length - 1 && data[++pointer] != 255);
  }

  return this.CreateIndexedBitmap(width, height, pixelData);
}

Decoding the picture is slightly complicated due to the multiple posts feature, but this means the more transparency is used by a given picture, the less data that picture requires.

Getting the Bitmap

I have spoken before about the GetPixel and SetPixel methods of the Bitmap class being not fit for purpose, and so I had no intention of using them with this project either. Instead, I'm going to restort to using unsafe code to directly manipulate the bitmap pixels... this is slightly simplified by the fact that as it is an indexed image, each pixel is only a byte.

private Bitmap CreateIndexedBitmap(int width, int height, byte[] pixelData)
{
  Bitmap bitmap;
  BitmapData bitmapData;
  ColorPalette palette;
  int index;
  int stride;

  bitmap = new Bitmap(width, height, PixelFormat.Format8bppIndexed);
  bitmapData = bitmap.LockBits(new Rectangle(0, 0, width, height), ImageLockMode.WriteOnly, PixelFormat.Format8bppIndexed);

  // can't create brand new palettes
  // so need to rework the existing one
  palette = bitmap.Palette;

  for (int i = 0; i < 256; i++)
  {
    palette.Entries[i] = _palette[i];
  }

  bitmap.Palette = palette;

  // apply palette indexes to the bitmap
  index = 0;
  stride = bitmapData.Stride < 0 ? -bitmapData.Stride : bitmapData.Stride;

  unsafe
  {
    byte* row;

    row = (byte*)bitmapData.Scan0;

    for (int y = 0; y < height; y++)
    {
      for (int x = 0; x < width; x++)
      {
        row[x] = pixelData[index++];
      }

      row += stride;
    }
  }

  bitmap.UnlockBits(bitmapData);

  return bitmap;
}

Syntax Highlighting

After that initial test I was having a spot of bother where some images crashed when loading, and some didn't decode properly. As staring at a bunch of bytes doesn't really help with context, I took the hex viewing code I wrote when ironing out issues writing Adobe Swatch Exchange files, souped it up some and used it to do a syntax highlighted view of picture files. This helped me iron out where I was going wrong.

I'm starting to think that this sort of tool is a actually a good idea so I'll keep refining this in future samples.

Efficiency

Interestingly, in terms of storage at least, DOOM's picture format stands up quite well against modern formats - as long as transparency is involved and even taking into account the palette being stored externally. When not involved, it doesn't hold against formats that involve compression such as PNG (which hadn't been invented yet) or even GIF (which had).

With that said, it's a simple enough format to decode and the others are decidedly less so.

Other formats

From my limited testing, this format was only used for DOOM and DOOM II. I tested the shareware WADs for Heretic and Hexen and the full WAD for Rise of the Triad but all three appear to be using a different image format.

Download

The sample application can be downloaded from our GitHub page.

More Images

I'll end this post with a few more images.

Like what you're reading? Perhaps you like to buy us a coffee?