BMP decoder (C)

From LiteratePrograms
Jump to: navigation, search

This program is under development.
Please help to debug it. When debugging
is complete, remove the {{develop}} tag.


Header
Palette
Pixel data

This article describes a portable decoder for BMP image files, a program for converting a BMP file into a raw bitmap of RGB triples. For simplicity, the decoder is monolithic: it reads in its entire input at once sequentially and produces its entire output at once sequentially.

Because version 4 and version 5 BMP files support embedding of very complex JPEG and PNG files, and because most BMP readers do not read these versions, we do not currently support them in this implementation.

The BMP file has 3 main parts as shown to the right: the header, the palette (only present for indexed images), and the bitmap or pixel data, which may or may not be compressed.

Contents

[edit] Endianness

Because BMP files were designed for use on IBM PC-compatible machines, all multibyte values are stored in a little-endian fashion, least significant byte first. In order for this decoder to be portable to big-endian machines, we must ensure that on these machines we perform byte reversal on any multibyte values subsequent to reading them in raw. For the purposes of this article we use a simple in-place algorithm that reinterprets the value as a byte array and swaps each pair of elements equally far from the middle:

<<fix endianness>>=
void fix_endian_func(void* data, int size) {
    if running on a big endian machine {
        unsigned char* cdata = data;
        int i;
        for (i=0; i<size/2; i++) {
            unsigned char temp = cdata[i];
            cdata[i] = cdata[size-1 - i];
            cdata[size-1 - i] = temp;
        }
    }
}

On a machine without byte addressing, other approaches can be more efficient; see Category:Byte reversal. To test if we're running on a big endian machine, we simply place the value "1" in an int and see if the first byte ends up being zero or not:

<<if running on a big endian machine>>=
int endian_test = 1;
unsigned char* endian_test_bytes = (unsigned char *)&endian_test;
if (endian_test_bytes[0] == '\0')

Finally, we add a convenient macro for invoking the function on static-sized objects:

<<fix endianness>>=
#define fix_endian(x)  (fix_endian_func(&(x), sizeof(x)))

[edit] Reading primitives

To be as generic as possible, all of our functions will perform input via a function pointer that behaves similarly to the standard fread():

<<type definitions>>=
/* Reads up to size bytes into the buffer, returning number of bytes read */
typedef int (*read_func)(void* buffer, int size);

[edit] Reading integers

The BMP file format is limited to three types of integer fields: unsigned 1-byte, unsigned 2-byte, unsigned 4-byte, and signed 4-byte integers. We define primitive read functions for each of these, each taking a read_func. We assume any end of file condition is unexpected and exit the program, which simplifies calling code (in C++, exception handling would be used). The C89 standard guarantees that a char is one byte, making the first primitive easy:

<<reading primitives>>=
unsigned char read_u8(read_func read) {
    unsigned char result;
    if (read(&result, 1) < 1) {
        printf("Unexpected end of file");
        exit(-1);
    }
    return result;
}

We add the necessary headers for printf() and exit():

<<header files>>=
#include <stdio.h>
#include <stdlib.h>

For the others, the standard only guarantees that shorts and longs will be at least long enough to hold 2-byte and 4-byte quantities, respectively (ref section 5.2.4.2, Numerical limits). To deal with this, we intialize them to zero; since we're reading in little endian quantities, the most significant bytes are left as zero. We then perform byte reversal if necessary on the entire integer, not just the first 2 or 4 bytes.

<<reading primitives>>=
unsigned short read_u16(read_func read) {
    unsigned short result = 0;
    if (read(&result, 2) < 2) {
        printf("Unexpected end of file");
        exit(-1);
    }
    fix_endian(result);
    return result;
}

unsigned long read_u32(read_func read) {
    unsigned long result = 0;
    if (read(&result, 4) < 4) {
        printf("Unexpected end of file");
        exit(-1);
    }
    fix_endian(result);
    return result;
}

Finally, the signed s32 adds a twist: we must sign extend it if it is negative. We do this by ORing it with a bitmask, where the bitmask is computed by shifting -1 (all 1 bits) left by 32 bits. On a platform with 32-bit longs, this operation has no effect.

<<reading primitives>>=
signed long read_s32(read_func read) {
    unsigned long result = 0;
    if (read(&result, 4) < 4) {
        printf("Unexpected end of file");
        exit(-1);
    }
    fix_endian(result);
    if ((result >> 31) & 1) { /* If it's negative... */
        result |= ((unsigned long)(-1)) << 32;
    }
    return (long)result;
}

While portable, this does introduce a warning in some compilers which see the shift as useless. The next section will demonstrate the use of these functions.

[edit] Reading the header

Field Bytes Signed
Type 2 N
Size 4 N
Reserved 4 N
Bitmap offset 4 N
Header size 4 N
Width 4 Y
Height 4 Y
Planes 2 N
Bits per pixel 2 N
Compression 4 N
Bitmap size 4 N
Horizontal res 4 Y
Vertical res 4 Y
# colors 4 N
# important colors 4 N

Next, we focus on reading the header. The header has a simple fixed layout as shown in the table to the right. The two structures composing it are documented Windows structures called BITMAPFILEHEADER and BITMAPINFOHEADER, both of which are documented at MSDN. On Windows, these are included in Windows header files, but since they're not available on any other platform and we desire uniform presentation, we choose not to use these structures.

We use a single header structure for the whole header with longs, shorts, and chars for the fields. Some of these fields may be larger than in the file, but because we're going to read them field by field this doesn't matter:

<<bitmap header structure>>=
struct bmp_file_header { 
    unsigned short   type; 
    unsigned long    size; 
    unsigned long    reserved; 
    unsigned long    bitmap_offset;
    unsigned long    header_size; 
    signed   long    width; 
    signed   long    height; 
    unsigned short   planes; 
    unsigned short   bits_per_pixel; 
    unsigned long    compression; 
    unsigned long    bitmap_size;
    signed   long    horizontal_resolution;
    signed   long    vertical_resolution;
    unsigned long    num_colors; 
    unsigned long    num_important_colors; 
}; 

We'll explain these fields as we use them later. Reading in this structure field by field with our reading primitives is straightforward. We read field by field partly due to our inability to determine the sizes of integer types and partly to avoid issues with structure element alignment.

<<read bitmap header function>>=
void read_bitmap_header(read_func in, struct bmp_file_header* header) {
    header->type                  = read_u16(in);
    header->size                  = read_u32(in);
    header->reserved              = read_u32(in);
    header->bitmap_offset         = read_u32(in);
    header->header_size           = read_u32(in);
    header->width                 = read_s32(in);
    header->height                = read_s32(in);
    header->planes                = read_u16(in);
    header->bits_per_pixel        = read_u16(in); 
    header->compression           = read_u32(in);
    header->bitmap_size           = read_u32(in);
    header->horizontal_resolution = read_s32(in);
    header->vertical_resolution   = read_u32(in);
    header->num_colors            = read_u32(in);
    header->num_important_colors  = read_u32(in);
}

[edit] Reading the palette

For the palette we'll define a simple static 2-dimensional array data structure containing up to 256 red-green-blue triples:

<<type definitions>>=
enum color_component {
    BLUE,
    GREEN,
    RED
};

#define PALETTE_ENTRY_SIZE   4
#define MAX_PALETTE_SIZE     256

typedef unsigned char palette[MAX_PALETTE_SIZE][PALETTE_ENTRY_SIZE];

Although the header members bits_per_pixel and num_colors are related to the size of the palette, the easiest way to determine its size is to use the bitmap_offset property. This is the offset of the pixel data in the file; if we just subtract the header size, we have the palette size in bytes. We'll need to define a constant for the header size, since the bmp_file_header structure may be larger.

<<constants>>=
#define HEADER_SIZE (2 + 6*4 + 2*2 + 6*4)

<<compute size of palette>>=
int palette_size = header->bitmap_offset - HEADER_SIZE;

To read the palette, we can simply read in a block of bytes, since our array elements are guaranteed to be contiguous and in row-major order. We return the number of palette entries by simply dividing the size by the size of a palette entry:

<<read palette function>>=
int read_palette(read_func in, struct bmp_file_header* header, palette palette) {
    compute size of palette
    if (in(&palette[0][0], palette_size) < palette_size) {
        printf("Unexpected end of file");
        exit(-1);
    }
    return palette_size/PALETTE_ENTRY_SIZE;
}

[edit] Reading pixel data

The encoding of the pixel data depends on the header members bits_per_pixel and compression. The main bitmap reading function will just dispatch based on these values. We will output pixel data in a very simple format: a two-dimensional array with 3 bytes for each pixel, one per RGB component.

<<type definitions>>=
typedef unsigned char raw_pixels[][3];

<<read pixel data function>>=
raw_pixels convert_pixel_data(reader_func in, struct bmp_file_header* header,
                              palette palette)
{
    raw_pixels output = malloc(3 * header->width * header->height;
    dispatch based on bits per pixel and compression
    return output;
}

We'll need an enumeration for values of the compression field:

<<constants>>=
enum compression_values {
    compression field values
};

These will be explained in more detail below. Reading uncompressed BMP files is relatively straightforward, so we begin with this.

[edit] Uncompressed indexed

In the uncompressed format, BMP pixel data simply has a fixed number of bits for each pixel, specified by the bits_per_pixel member of the header. If this is less than 16 (in other words, at most 8), then each value is an index into the palette.

<<compression field values>>=
UNCOMPRESSED = 0,

<<dispatch based on bits per pixel and compression>>=
if (header->compression == UNCOMPRESSED && header->bits_per_pixel < 16) {
    convert_uncompressed_indexed_pixels(in, header, palette, output);
} 

Since each scanline is aligned to the nearest 4 byte boundary, we can determine the number of bytes in a scanline like this:

<<scanline bytes calculation>>=
int scanline_bits = header->width * header->bits_per_pixel;
int scanline_bytes = ((scanline_bits + 31)/32)*4;

The effect of adding 31 and then dividing by 32 is to find the ceiling of scanline_bits divided by 32, which is the smallest number of 4-byte blocks containing that many bits. We then multiply by 4 to get a byte count.

Keeping in mind that BMP files list scanlines from the bottom up, we're now ready to read in the pixel data:

<<convert uncompressed indexed pixels function>>=
void convert_uncompressed_indexed_pixels(
    reader_func in, struct bmp_file_header* header,
    palette palette, raw_pixels output)
{
    scanline bytes calculation
    for(int row = header->height-1; row >= 0; row--) {
        int out_offset = header->width*row*3;
        int column = 0;
        for (int bytenum=0; bytenum < scanline_bytes; bytenum++) {
            read and decode a byte full of pixels
        }
    }
}

Just how we decode each byte depends on the number of bits per pixel. We loop over the pixels in the byte, shifting it left to keep the current pixel in the highest bits so that we can use extract_high_bits() (defined later) to read the index out.

<<read and decode a byte full of pixels>>=
unsigned char pixel_byte = read_u8(in);
for (int pixel_num=0; pixel_num < header->bytes_per_pixel; pixel_num++) {
    int index = extract_high_bits(pixel_byte, header->bytes_per_pixel);
    set output bytes based on palette entry index
    pixel_byte <<= header->bytes_per_pixel;
    break if scanline done
}

Setting the output bytes is a simple matter of calculating the correct position in the output array and filling it with the intensity values from the palette entry indicated by index:

<<read and decode a byte full of pixels>>=
output[out_offset + column*3 + 0] = palette[index][0];
output[out_offset + column*3 + 1] = palette[index][1];
output[out_offset + column*3 + 2] = palette[index][2];

Because it's possible for a scanline to end in the middle of a byte, we break out of the loop if column exceeds the bitmap width:

<<break if scanline done>>=
column++;
if (column > header->width) break;

Finally, we define the helper function extract_high_bits(), which uses a shift to move the highest k bits to the lowest k bits; zeros are left in front of them:

<<extract high bits helper function>>=
unsigned char extract_high_bits(unsigned char x, int bits) {
    return x >> (8 - bits);
}

[edit] Uncompressed RGB

[edit] Bitfields (16- and 32-bit)

[edit] Run-length encoding (4- and 8-bit)

[edit] More to come

<<bmp_decode.c>>=
header files
type definitions
constants
bitmap header structure

fix endianness
reading primitives
read bitmap header function
read palette function

[edit] References

Download code
hijacker
hijacker
hijacker
hijacker