BMP implementation in C

C is one cool and important language. CPython and Unix are based on it, the Mars Curiosity rover is run by it and even the GCC C compiler itself is written in C. However, as C is some years old by now, it lacks a lot of higher-level features most modern languages possess, being more down to the silicon, as the cool kids say. Concepts like pointer manipulation, bit fiddling and its string implementation — just to name a few — are at times cumbersome, insecure and error-prone; nevertheless is there a certain appeal to writing in C.

Being only one abstraction level away from Assembly — which itself is only one abstraction level above raw byte code — and having access to file manipulation down to the individual bit, I set out to write a Microsoft Bitmap (.bmp) implementation in pure C. As Microsoft’s standard for this image file format is quite feature-rich, I decided to focus on the bar minimum — a bitmap with 24-bit color depth (three colors, one byte per), one color plane, no compression, no palette and 300 DPI.
My Bitmap implementation supports both reading and writing .bmp files, as well as generating some test images — including a Mandelbrot Set fractal renderer, of course. Implementation source code can be downloaded (bmp.c) or seen below.

Mandelbrot Set fractal
A Mandelbrot Set fractal rendering.

Implementing a file format requires knowing its specification. Although it is not the best article I have ever seen, this Wikipedia article gave me some insights. The missing pieces were reverse engineered using Adobe Photoshop CC and the HxD hex editor.
The following is a snippet of the implementation’s savebmp function (full source code listed below). It illustrates the Bitmap file’s byte layout only showing the file header, omitting a lengthy data part concatenated to the header. S, K, W, H and B are all byte arrays of length four (little-endian format) which contain the file’s total size, the bitmap data offset (which is constant, since the header is always exactly 54 bytes large), the image’s dimensions (horizontal and vertical) and the bitmap data’s section’s size, respectively.

/*  bitmap file header  */
0x42, 0x4D,             // BM
S[0], S[1], S[2], S[3], // file size
0x00, 0x00, 0x00, 0x00, // unused
K[0], K[1], K[2], K[3], // bitmap data offset
/*      DIB header      */
0x28, 0x00, 0x00, 0x00, // DIB size
W[0], W[1], W[2], W[3], // pixel width
H[0], H[1], H[2], H[3], // pixel height
0x01, 0x00,             // one color plane
0x18, 0x00,             // 24 bit color depth
0x00, 0x00, 0x00, 0x00, // no compression
B[0], B[1], B[2], B[3], // bitmap data size
0x23, 0x2E, 0x00, 0x00, // 300 DPI (horizontal)
0x23, 0x2E, 0x00, 0x00, // 300 DPI (vertical)
0x00, 0x00, 0x00, 0x00, // no palette
0x00, 0x00, 0x00, 0x00  // color importance
/*  data bytes follow   */

Key bytes to note are the first two identifying the file type (the ASCII-encoded letters BM) and the DPI bytes, 0x23, 0x2E, which indicate 0x00002E23 = 11811 pixels per meter in both the horizontal and vertical direction. Converting from pixels per meter to dots per inch results in 11811 / (1 meter / 1 inch) = 11811 * 127 / 5000 = 300 DPI (roughly).
Most values are represented using four bytes in little-endian format. Translating an 32-bit integer into four little-endian formatted bytes can be achieved as follows.

/* unsigned 32-bit integer */
unsigned int n = 0b10100100010000100000100000010000;
/*                 < m sig><sm sig><sl sig>< l sig> */

/* byte (unsigned char) array of size four */
unsigned char N[4] = {          
	(n & 0xff000000) >>  0, // most significant byte
	(n & 0x00ff0000) >>  8, // second most significant byte
	(n & 0x0000ff00) >> 16, // second least significant byte
	(n & 0x000000ff) >> 24  // least significant byte
};

Other than rendering a fractal, I also implemented three nested loops which output an image containing every possible color exactly once ((2**8)**3 = 16777216 pixels in total).

All sixteen million colors
All sixteen million colors in one image.

An image’s data type is implemented as a struct image which contains three variables — width and height, two integers specifying the image’s dimensions, and *px, a pointer to an one-dimensional integer array of size width*height which holds the entire image data.
Defined functions are listed ahead.

  • image * readbmp(char []);
    • Reads an image specified by a file name. If reading fails, a NULL pointer is returned.
  • void savebmp(image *, char []);
    • Saves given image to a file with specified name.
  • image * newimage (int, int);
    • Returns a pointer to an image struct with specified dimensions (image will be filled with nothing but black pixels).
  • void freeimage (image *);
    • Frees an image struct’s memory.
  • int getpx (image *, int, int);
    • Returns the pixel color at specified coordinates.
  • void setpx (image *, int, int, int);
    • Sets the pixel color at specified coordinates.
  • void fill (image *, int);
    • Fills a given image with a given color (all pixels are set to specified color).
  • int color(byte, byte, byte);
    • Returns a 32-bit integer representing a color specified by three bytes (byte is defined through typedef unsigned char byte;).
  • int hsl (double, double, double);
    • Returns a 32-bit integer representing a color specified by three doubles in the HSL color format.

Images shown in this post were converted to .png files as WordPress does not allow .bmp file uploads; the raw pixel data should, however, be identical.


/* ================================================== *
 *                GENERAL INFORMATION                 *
 * ================================================== *
 * Bitmap file format implementation in C.            *
 * Supported functionality: 24-bit color depth image  *
 *  struct, reading and writing .bmp files and simple *
 *  image manipulation.                               *
 * Supported color formats: RGB and HSL.              *
 * Additional functionality: Mandelbrot Set fractal   *
 *  rendering.                                        *
 *                                                    *
 * Author: Jonathan Frech                             *
 *                                                    *
 * Edit history: 23rd, 24th, 27th, 28th, 29th, 30th   *
 *  of June, 1st, 2nd, 3rd, 10th, 11th, 13th, 14th,   *
 *  15th, 16th, 17th, 18th, 19th, 20th, 25th, 26th,   *
 *  27th, 29th of July, 11th, 16th of August, 17th,   *
 *  18th, 19th of October 2017                        */
 
/* ================================================== *
 *                    COMPILATION                     *
 * ================================================== *
 * $ rm bmp; gcc bmp.c -lm -o bmp; ./bmp              */

/* ======================================= *
 *  INCLUSION, CONSTANTS, TYPE DEFINITION  *
 * ======================================= */

// include header files
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <math.h>

// define the eight full-value color integers
static const int BLACK   = 0x000000, RED   = 0xff0000,
                 GREEN   = 0x00ff00, BLUE  = 0x0000ff,
                 YELLOW  = 0xffff00, CYAN  = 0x00ffff,
                 MAGENTA = 0xff00ff, WHITE = 0xffffff;

// bitmap struct and type definition
typedef struct image { int width; int height; int *px; } image;

// byte type; value range [0, 255]
typedef unsigned char byte;

// color scheme struct used in mandelbrot set fractal rendering
typedef struct ClrSch { int Clr; int *Arr; } ClrSch;





/* ======================= *
 *  FUNCTION DELARACTIONS  * 
 * ======================= */

/* I) color functions             */
int color(byte   , byte   , byte  );
int hsl  (double , double , double);

/* II) image, draw functions              */
image * newimage   (int    , int          );
void    freeimage  (image *               );
int     getpx      (image *, int, int     );
void    setpx      (image *, int, int, int);
void    fill       (image *, int          );

/* III) bitmap file functions */
image * readbmp(char []         );
void    savebmp(image *, char []);

/* IV) fractal functions                                                           */
ClrSch * getClrSch    (int                                                         );
void     mandelbrotset(int, int    , ClrSch * , int, double, double, double, double);





/* =============== *
 *  MAIN FUNCTION  *
 * =============== */
int main() {
	// generate a test image using every color exactly once
	image *img = newimage(4096,4096);
	for(int r=0;r<256;r++){for(int g=0;g<256;g++){for(int b=0;b<256;b++){setpx(img,r+(b%16)*256,g+(b/16)*256,color(r,g,b));}}}
	savebmp(img, "test.bmp");
	
	// render one mandelbrot set fractal frame
	mandelbrotset(500, 500, getClrSch(256), 1, -.7491, .1005, 1, 1e-4 );
}





/* ==================== *
 *  I) COLOR FUNCTIONS  *
 * ==================== */

// concatenate three color bytes to one color integer
int color(byte r, byte g, byte b) { return (r<<16)|(g<<8)|b; }

// return color rgb integer based on hue, saturation and luminosity
// (0 <= h <= 360; 0 <= s, l <= 1)
int hsl(double h, double s, double l) {
	h /= 60;
	double c = s*(1-fabs(      l*2 -1));
	double x = c*(1-fabs(fmod(h, 2)-1));
	double m = l-c/2;
	double r = 0, g = 0, b = 0;
	if (0 <= h && h < 1) r = c, g = x; if (1 <= h && h < 2) r = x, g = c; if (2 <= h && h < 3) g = c, b = x;
	if (3 <= h && h < 4) g = x, b = c; if (4 <= h && h < 5) r = x, b = c; if (5 <= h && h < 6) r = c, b = x;
	return (((byte)((r+m)*255))<<16)|
               (((byte)((g+m)*255))<< 8)|
                ((byte)((b+m)*255))     ;
}





/* =========================== *
 *  II) IMAGE, DRAW FUNCTIONS  *
 * =========================== */

// return image struct pointer with allocated memory and cleared pixel data
image * newimage(int width, int height) {
	image *img = malloc(sizeof(image));         // image pointer
	img->width = width; img->height = height;   // dimensions
	img->px = malloc(width*height*sizeof(int)); // pixel data memory allocation
	fill(img, 0); return img;                   // clear memory, return image pointer
}

// free image struct pointer's allocated memory
void freeimage(image *img) { free(img->px); free(img); }

// get pixel at coordinate (x, y)
int getpx(image *img, int x, int y) {
	if (x < 0 || x >= img->width || y < 0 || y > img->height) return -1; // value range
	return img->px[x+y*img->width];                                      // get pixels
}

// set pixel at cooridinate (x, y)
void setpx(image *img, int x, int y, int c) {
	if (x < 0 || x >= img->width || y < 0 || y > img->height) return; // value range
	img->px[x+y*img->width] = c;                                      // set pixel
}

// fill entire image with a single color
void fill(image *img, int c) {
	int N = img->width*img->height;                 // calculate total number of pixels
	for (int i = 0; i < N; i++) { img->px[i] = c; } // set pixels
}





/* ============================ *
 *  III) BITMAP FILE FUNCTIONS  *
 * ============================ */

// read a bitmap file
image * readbmp(char fn[]) {
	FILE *f = fopen(fn, "r"); if (f == NULL) return NULL;            // file pointer, file read error
	fseek(f, 0, SEEK_END); int s = ftell(f); byte *data = malloc(s); // seek file end, get file size, allocate memory
	fseek(f, 0, SEEK_SET); fread(data, 1, s, f); fclose(f);          // read file contents
	
	int k = 54;                                                                                       // header size
	if (s < k)                                                                           return NULL; // file size missmatch
	int w = (data[21]<<24)|(data[20]<<16)|(data[19]<<8)|data[18];                                     // image pixel width
	int h = (data[25]<<24)|(data[24]<<16)|(data[23]<<8)|data[22];                                     // image pixel height
	int b = (data[37]<<24)|(data[36]<<16)|(data[35]<<8)|data[34];                                     // bitmap data size
	if (!(data[ 0] == 0x42 && data[ 1] == 0x4D                                        )) return NULL; // magic number missmatch
	if (!(data[10] ==    k && data[11] == 0x00 && data[12] == 0x00 && data[13] == 0x00)) return NULL; // bitmap data offset missmatch
	if (!(data[14] == 0x28 && data[15] == 0x00 && data[16] == 0x00 && data[17] == 0x00)) return NULL; // DIB size missmatch
	if (!(data[26] == 0x01 && data[27] == 0x00                                        )) return NULL; // not one color plane
	if (!(data[28] == 0x18 && data[29] == 0x00                                        )) return NULL; // not 24 bit color depth
	if (!(data[30] == 0x00 && data[31] == 0x00 && data[32] == 0x00 && data[33] == 0x00)) return NULL; // compression missmatch
	                                                                                                  // DPI (h and v, 8 bytes) get ignored
	if (!(data[46] == 0x00 && data[47] == 0x00 && data[48] == 0x00 && data[49] == 0x00)) return NULL; // palette missmatch
	if (!(data[50] == 0x00 && data[51] == 0x00 && data[52] == 0x00 && data[53] == 0x00)) return NULL; // color importance missmatch
	if (s != k+b)                                                                        return NULL; // file size missmatch
	
	image *img = newimage(w, h); int i = 0;                                // image pointer, bitmap data pointer
	int pad = (4-(3*w)%4)*((3*w)%4!=0);                                    // number of bytes to pad each pixel line to a multiple of four bytes
	for (int y = h-1; y >= 0; y--) { for (int x = 0; x < w; x++) {         // loop through data, read pixel values
		img->px[x+y*w] = data[k+i]|(data[k+i+1]<<8)|(data[k+i+2]<<16); // read three color bytes
		i += 3; } i += pad; }                                          // advance counter, skip padded bytes
	
	free(data); return img; // free data, return image pointer
}

// save a bitmap file
void savebmp(image *img, char fn[]) {
	int w = img->width, h = img->height; // one-letter variables for image dimensions
	int pad = (4-(3*w)%4)*((3*w)%4!=0);  // number of bytes to pad each pixel line to a multiple of four bytes
	int k = 54;                          // header size (bitmap header size + DIB header size)
	int b = (3*w+pad)*h, s = k+b;        // bitmap data size, file size (complete)
	byte *data = malloc(s);              // data array pointer

	int i = 0; // data index, fill bitmap data portion
	for (int y = h-1; y >= 0; y--) { for (int x = 0; x < w; x++) {
			int p = img->px[x+y*w];         // get pixel integer
			data[k+i  ] = (p&0xff    )    ; // blue byte
			data[k+i+1] = (p&0xff00  )>> 8; // green byte
			data[k+i+2] = (p&0xff0000)>>16; // red byte
			i += 3; }                       // advance counter

		// pad to a multiple of four bytes
		for (int pd = 0; pd < pad; ++pd) { data[k+i] = 0; i++; }
	}

	// file header bytes
	char S[] = {s&0xff, (s&0xff00)>>8, (s&0xff0000)>>16, (s&0xff000000)>>24}; // file size
	char K[] = {k&0xff, (k&0xff00)>>8, (k&0xff0000)>>16, (k&0xff000000)>>24}; // header size (also bitmap data offset)
	char W[] = {w&0xff, (w&0xff00)>>8, (w&0xff0000)>>16, (w&0xff000000)>>24}; // pixel height
	char H[] = {h&0xff, (h&0xff00)>>8, (h&0xff0000)>>16, (h&0xff000000)>>24}; // pixel width
	char B[] = {b&0xff, (b&0xff00)>>8, (b&0xff0000)>>16, (b&0xff000000)>>24}; // bitmap byte size

	// file header
	char header[] = {
		/*  bitmap file header  */
		0x42, 0x4D,             // BM
		S[0], S[1], S[2], S[3], // file size
		0x00, 0x00, 0x00, 0x00, // unused
		K[0], K[1], K[2], K[3], // bitmap data offset
		/*      DIB header      */
		0x28, 0x00, 0x00, 0x00, // DIB size
		W[0], W[1], W[2], W[3], // pixel width
		H[0], H[1], H[2], H[3], // pixel height
		0x01, 0x00,             // one color plane
		0x18, 0x00,             // 24 bit color depth
		0x00, 0x00, 0x00, 0x00, // no compression
		B[0], B[1], B[2], B[3], // bitmap data size
		0x23, 0x2E, 0x00, 0x00, // 300 DPI (horizontal)
		0x23, 0x2E, 0x00, 0x00, // 300 DPI (vertical)
		0x00, 0x00, 0x00, 0x00, // no palette
		0x00, 0x00, 0x00, 0x00  // color importance
	};
	for (int i = 0; i < k; ++i) { data[i] = header[i]; } // put header into file
	FILE *f = fopen(fn, "w"); if (f == NULL) return;     // file pointer, file cannot be written
	fwrite(data, 1, s, f); fclose(f); free(data);        // write file, close file, free memory
}





/* ======================= *
 *  IV) FRACTAL FUNCTIONS  *
 * ======================= */

// returns a color scheme based on color scheme string
ClrSch * getClrSch(int Clr) {
	/* allocate memory for scheme struct */
	ClrSch *sch = malloc(sizeof(ClrSch)); sch->Arr = malloc(Clr*sizeof(int)); sch->Clr = Clr;
	
	// hsl rainbow, full hue range
	double h0 = 0, h1 = 360;
	for (int k = 0; k < Clr; k++) { sch->Arr[k] = hsl(h0+(h1-h0)/(Clr-1)*k, 1, .5); }
	sch->Arr[Clr-1] = BLACK;

	/* return color scheme */
	return sch;
}

// generate a series of vanilla mandelbrot set fractal images
void mandelbrotset(int W, int H, ClrSch *sch, int Frm, double Zre, double Zim, double Zom0, double Zom1) {
	int Pad = (int) ceil(log10(Frm)); if (Pad < 1) Pad = 1;                                         // file name pad length
	image *img = newimage(W, H); clock_t t0 = clock();                                              // image pointer, clock
	for (int f = 0; f < Frm; f++) {                                                                 // loop through frame numbers and render them
		double Zom = Zom0*pow(pow(Zom1/Zom0, 1./(Frm-1)), f);                                   // calculate current frame's zoom
		char fn[3+Pad+4+1]; snprintf(fn, sizeof(fn), "frc%0*d.bmp", Pad, f);                    // determine image's (padded!) file name
		double h = Zom*2, w = h*W/H;                                                            // calculate image's complex width and height
		for (int y = 0; y < H; y++) {                                                           // loop through image pixels
			printf("\33[2K\rRendering frame %*d / %*d at zoom level %e as '%s'. (%5.2f%%)", // print status message
				Pad, f, Pad, Frm-1, Zom, fn, 100.*y/H); fflush(stdout);                 // flush to stdout
			for (int x = 0; x < W; x++) {                                                   // loop through image pixels
			double c = Zre-w/2.+w*x/W, d = -Zim-h/2.+h*y/H;                                 // calculate C = c+di based on current image pixel
			double a = 0, b = 0, asqr = 0, bsqr = 0; int i = -1;                            // initiate Z = a+bi, a^2, b^2, iterations needed
			while (asqr+bsqr <= 4 && i < sch->Clr-1) { b = 2*a*b+d; a = asqr-bsqr+c;        // iterate Z -> Z^2+C
				asqr = a*a; bsqr = b*b; i++; } img->px[x+y*W] = sch->Arr[i];            // set pixels
		}} savebmp(img, fn );                                                                   // save image
	} clock_t t1 = clock(); double t = (double) (t1-t0)/CLOCKS_PER_SEC; free(img);                  // calculate render time, free memory
	printf("\33[2K\rRendered %d frame%c in %.2f seconds.\n", Frm, (Frm == 1 ? '\0' : 's'), t);      // print final status message
}





/* END OF FILE */
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s