BMP files

BMP file format is a common way to store images
There are several versions of BMP headers, but we will focus on the most common ones
Each BMP file contains:
- a 14-bytes long file header:
  - 2-byte type (must be equal to BM encoded in ASCII)
  - 4-byte file size
  - 2x 2-byte reserved fields (not used)
  - 4-byte offset to the main data (pixel values)
- a variable size (but with modern system, at least 40-bytes long) info header:
  - 4-byte real size of the header
  - 4-byte width
  - 4-byte height
  - 2-byte number of planes (not used)
  - 2-byte number of bits used to store pixels
  - 4-byte compression type
  - 4-byte image size
  - 4-byte horizontal DPI
  - 4-byte vertical DPI
  - 4-byte number of colors in the palette
  - 4-byte number of important colors (not used)
- an array of pixel data

Project

Write a C program to parse BMP files

You can use the following definitions as a starting point:

#include <stdint.h>

typedef uint16_t WORD;
typedef uint32_t DWORD;
typedef int32_t LONG;

// https://docs.microsoft.com/en-us/windows/win32/api/wingdi/ns-wingdi-bitmapfileheader
typedef struct tagBITMAPFILEHEADER {
  WORD  bfType;
  DWORD bfSize;
  WORD  bfReserved1;
  WORD  bfReserved2;
  DWORD bfOffBits;
} BITMAPFILEHEADER, *LPBITMAPFILEHEADER, *PBITMAPFILEHEADER;

// https://docs.microsoft.com/pl-pl/previous-versions/dd183376(v=vs.85)
typedef struct tagBITMAPINFOHEADER {
  DWORD biSize;
  LONG  biWidth;
  LONG  biHeight;
  WORD  biPlanes;
  WORD  biBitCount;
  DWORD biCompression;
  DWORD biSizeImage;
  LONG  biXPelsPerMeter;
  LONG  biYPelsPerMeter;
  DWORD biClrUsed;
  DWORD biClrImportant;
} BITMAPINFOHEADER, *LPBITMAPINFOHEADER, *PBITMAPINFOHEADER;

Warning! In C, structure members can be separated by padding to optimized access time
If you read a structure from binary file (like BMP), reading it whole in one fread call will most likely fail

There are two solutions:

Read structure members one at a time:

fread(&structure->member1, sizeof(...), 1, file);
fread(&structure->member2, sizeof(...), 1, file);

Add packed attribute to the structure: (this is not portable between compilers!)
```
struct xyz { ... } __attribute((__packed__));
```

Requirements for 3.0

The program should accept one command line parameter in the format:
```
$ ./program PATH-TO-BMP-FILE
```
For example:
```
$ ./program test.bmp
```

Program must print out the parsed values from BITMAPFILEHEADER and BITMAPINFOHEADER e.g.:

BITMAPFILEHEADER:
  bfType:          0x4D42 (BM)
  bfSize:          369738
  bfReserved1:     0x0
  bfReserved2:     0x0
  bfOffBits:       138
BITMAPINFOHEADER:
  biSize:          124
  biWidth:         280
  biHeight:        330
  biPlanes:        1
  biBitCount:      32
  biCompression:   3
  biSizeImage:     369600
  biXPelsPerMeter: 3779
  biYPelsPerMeter: 3779
  biClrUsed:       0
  biClrImportant:  0

Requirements for 3.5

Additionally, program must print out a histogram of RGB colors. For this part, focus only on uncompressed bitmaps with 24-bits, i.e., biCompression = 0 and biBitCount = 24 (for other bitmaps, you can just emit a message that histogram calculation is unsupported)
In the supported bitmaps, each pixel is stored as three bytes representing blue, green and red channels (yes, the byte order is BGR, not RGB)
Pixel array is stored as a sequence of rows. Each row has length equal to: \lfloor \frac{bitCount \cdot width + 31}{32} \rfloor \cdot 4, which ensures that the number of bytes a row has is divisible by 4.
For example, let’s assume there is a 97 pixel wide, 24-bit bitmap (24-bits = 3 bytes):
\begin{array}{ccc} \left\lfloor \dfrac{24 \cdot 97 + 31}{32} \right\rfloor \cdot 4 & = & 292 \\ 97 \cdot 3 & = & 291 \end{array}
The program should read 292 bytes at a time, but process only 291 bytes our of that (the remaining byte is called a padding).

The expected outcome for an uncompressed 24-bit BMP file should look like this:

Blue:
  0-15: 0.00%
  16-31: 0.00%
  32-47: 0.00%
  48-63: 0.00%
  64-79: 0.00%
  80-95: 0.00%
  96-111: 0.00%
  112-127: 0.00%
  128-143: 0.00%
  144-159: 10.07%
  160-175: 9.41%
  176-191: 0.95%
  192-207: 15.43%
  208-223: 0.63%
  224-239: 0.76%
  240-255: 62.75%
Green:
  0-15: 0.00%
  16-31: 0.00%
  32-47: 0.00%
  48-63: 9.79%
  64-79: 9.23%
  80-95: 0.42%
  96-111: 15.10%
  112-127: 0.56%
  128-143: 0.36%
  144-159: 0.37%
  160-175: 0.26%
  176-191: 0.34%
  192-207: 0.42%
  208-223: 0.30%
  224-239: 0.75%
  240-255: 62.09%
Red:
  0-15: 0.00%
  16-31: 0.00%
  32-47: 9.68%
  48-63: 9.30%
  64-79: 0.36%
  80-95: 15.03%
  96-111: 0.61%
  112-127: 0.37%
  128-143: 0.33%
  144-159: 0.22%
  160-175: 0.34%
  176-191: 0.28%
  192-207: 0.36%
  208-223: 0.42%
  224-239: 0.63%
  240-255: 62.09%

Requirements for 4.0

Program must also handle case when it is started with two command line parameters:
```
$ ./program PATH-TO-INPUT-BMP-FILE PATH-TO-OUTPUT-BMP-FILE
```
The output BMP file should have all the headers with exactly the same values as the input BMP, but the pixel array should be modified to make the image grayscale using the simplest formula computed for each pixel: gray = \frac{red + green + blue}{3}. The value gray should be copied to red, green and blue fields for the pixel. For example, a pixel has red=100, green=60, blue=200, therefore gray = \frac{360}{3} = 120 and you should modify the pixel array to have red = green = blue = 120. For this task, you can also assume to support only uncompressed 24-bit BMP files and emit a message for others.

Important! The above method to create grayscale image is a good exercise in manipulating binary data and you can easily see if your code performs as expected (either the output BMP is a grayscale image or not). However, the method is bad for several reasons and you should be aware of that as well. First of all, assigning red, green and blue to the same value in each pixel will make it gray, but is a waste of memory space. One should create a palette of 256 possible gray colors and represent each pixel with a single byte instead of three. But even more severe problem lies in the fact, that converting to grayscale should take into account color recognition by human eye, which is not uniform for all color channels. Recommended reading: http://cadik.posvete.cz/color_to_gray_evaluation/

Requirement for 4.5

Modify your program to use steganography to hide a text inside BMP pixel array
For example, use the least significant bit of the first 8 bytes to encode text length (0-255 characters long). Then use the least significant bit of the next bytes to encode bits of the characters. In this method, the image should look exactly the same for an unsuspecting user, but the message will be there hidden in the bits of pixels.

If the pixel array looked like this:

      00 00 00 00 00 00 00 00
      00 00 00 00 00 00 00 00
      00 00 00 00 00 00 00 00
      00 00 00 00 00 00 00 00
      00 00 00 00 00 00 00 00
      00 00 00 00 00 00 00 00
      00 00 00 00 00 00 00 00

Then after encoding Hello! it would change to:

 6  = 00 01 01 00 00 00 00 00
'H' = 00 00 00 01 00 00 01 00
'e' = 01 00 01 00 00 01 01 00
'l' = 00 00 01 01 00 01 01 00
'l' = 00 00 01 01 00 01 01 00
'o' = 01 01 01 01 00 01 01 00
'!' = 01 00 00 00 00 01 00 00

For this task to be considered, please let your program hide a message in a BMP file, but also let it decode a message and print it out:

$ ./program PATH-TO-INPUT-BMP PATH-TO-ENCODED-BMP "text to be hidden"
$ ./program PATH-TO-ENCODED-BMP
BITMAPFILEHEADER
  ...
BITMAPINFOHEADER
  ...

Decode steganography? [Y/n]

text to be hidden

As previously, you can just support uncompressed 24-bit BMPs

Requirement for 5.0

Create a new program to generate a bitmap of any given size showing the Mandelbrot fractal:
```
$ ./program WIDTH HEIGHT PATH-TO-BMP-FILE
```
The program should prepare headers with the width and height (and file size) correctly set
It should allocate memory for the pixel array data and fill it
To create a Mandelbrot fractal image:
- Process every (x, y) pixel
- Map it into a complex number c with real part between -2 and 1, and imaginary part between -1 and 1
  - Mapping formula:
    
    (value - in_{min}) * (out_{max} - out_{min}) / (in_{max} - in_{min}) + out_{min}
  - For example, in a 1000 pixel wide image, the x=700 pixel will be mapped into [-2, 1] range as follows:
    
    (700 - 0) * (1 - (-2)) / (1000 - 0) + (-2) = 0.1
- Initialize another complex number z with zero
- Iterate z \gets z^2 + c until |z| > 2 or a given number of iterations passes (e.g. MAX_ITERATIONS=100)
- Once it stops, map the number of iterations to a grayscale color between 0 and 255
- Set (x, y) pixel’s color to the value and continue
Expected result:

Useful resources

wxHexEditor and BMP tags file used in the GIF preparation above
BITMAPFILEHEADER
BITMAPINFOHEADER
File input/output, specifically fread(), fwrite() and fseek()

Bitmaps to use for testing (uncompressed, 24-bits, free license)

C logo 96x96:

Source
C logo 97x96:
Tux:

Source