CS50x Week 7: Forensics (Problem Set)

There are many image file formats such as BMP, JPG, PNG, and GIF. They can be grouped into lossy format and lossless format. Lossy format uses lossy compression that cuts away some data of the image to make an image that appears to be perfect copy, but not a perfect copy. lossless format uses lossless compression that preserves a perfect copy. JPG is a lossy compression while BMP, PNG, and GIF are lossless compression. Since lossless compression retains all data, their file size is bigger than lossy compression file.

Today’s problem set deals with BMP or bitmap. BMP file format is a raster graphic file format, meaning the image is represented by square grid of pixels. The opposite of raster graphic is vector graphic, which uses formula to represent an image.

24×24 pixel image of a smiley face, magnified 10x to demonstrate pixel boundaries by Gringer is licensed under CC0 1.0 Universal (CC0 1.0)

In BMP, each pixel is 24-bit (3 bytes), 8-bit for Blue, 8-bit for Green, and 8-bit for Red (in that order).For example, a pixel with color orange has 255 (in decimal)/ 0xFF (in hexadecimal) Red, 178/ 0xB2 Green, and 0/ 0x00  Blue. Recall that 8-bit can contain digits from 0 to 2^{8} - 1 = 255, 0 is the least intensity of a color, and 255 is the highest intensity of a color. In this case, we have 255 Red, meaning the pixel has highest intensity of Red mixing with 178 intensity of Green and 0 intensity of Blue. Orange can be written hexadecimally as FFB200.

In a BMP file, besides that pixel data, we also have some metadata on top of the file, such as BITMAPFILEHEADER and BITMAPINFOHEADER. BITMAPFILEHEADER is 14 bytes long, and BITMAPINFOHEADER is 40 bytes long. BITMAPFILEHEADER is a structure that contains data about the file such as file type, file size. BITMAPINFOHEADER is a structure that contains width of image, height of image, bits-per-pixel, image size. Each pixel is also in a form of structure containing value for intensity of Blue, Green, and Red.

The file size of 8 pixels x 8 pixels BMP is 14 \mbox{(bytes required for BITMAPFILEHEADER)} + 40 \mbox{(bytes required for BITMAPINFOHEADER)} + 8\times8\times3 \mbox{ bytes for each pixel} = 246 \mbox{bytes}. The image size is 8 \times 8 \times 3 \mbox{ bytes} = 192 \mbox{ bytes}.

There is one thing to take note, the bytes of row of BMP must be a multiple of four. For example in a 8 pixel x 8 pixel BMP, the byte per row is 8 \mbox{ pixel}\times3 \mbox{ bytes per pixel} = 24 \mbox{ bytes}, so this is ok. However, in a 3 pixel x 3 pixel BMP, the byte per row is 3 \mbox{ pixel}\times3\mbox{ bytes per pixel} = 9 \mbox{ bytes}, 9 is not a multiple of 4, so we need to add padding to make it a multiple of 4. The nearest multiple of 4 is 12, so we have to add 3 bytes of padding. One byte of padding is 0x00.

Whodunit?

In this problem, we are given a clue.bmp with some red “noise”. We need to remove the red “noise” to reveal the message hidden in this file. Red “noise” is simply pixels that has the highest intensity of red, 0 intensity of green, and 0 intensity of blue. So to get rid of the red “noise”, we just have to read each pixel of the BMP file (the given copy.c contains codes that teach you how to read each pixel from a BMP file and write to another BMP file), find the pixel with 0000FF and make it into 000000, essentially turning the pixels with only red into white. This will reveals the hidden message.

CS50 previous year’s clue.bmp

Resize

In this problem, we have to resize a BMP file by a given factor, n. where n is a whole positive integer number. We first have to update the BITMAPFILEHEADER and BITMAPINFOHEADER, specifically the bfSize, biHeight, biSizeImage, and biWidth inside the structures. Then we read each row pixel by pixel, resize horizontally, add padding if necessary. Then resize vertically. To resize horizontally, lets say n = 2, we just have to double each pixel horizontally. To resize vertically, we have to double the row. This can be done by going back to the original row of the input file, and repeat the horizontal resizing.

Hacker version of resize requires us to write code that accepts a floating point number as factor, so n can be a floating point value from 0.00 to 100.0. A concept called bilinear interpolation will be used.

Resize image
Resize image

CSI (Computer Science Investigation)

In this problem set, we are given a raw file (“forensic image” of a CompactFlash(CF) card) containing 50 jpg files. Our goal is to extract these jpg files.  CF cards with a FAT file system has a block size of 512 bytes, meaning the data in CF card is stored in blocks of 512 bytes. We just have to read in one block at a time to determine what to do with it.

The first four bytes of JPG file can be either 0xff 0xd8 0xff 0xe0 or 0xff 0xd8 0xff 0xe1. So blocks starting with these bytes will signal us the start of a new JPG. When we detect the start of a JPG, we open a new file, and continue to append next blocks to the file. When another JPG signal is detected, signalling a new file, then close the current file and open another file, and append the next blocks to it.

We need a way to know when we have reached the end of the CF card, this can be done by sscanf(buffer, sizeof(BYTE), 512, inputFile) statement, the statement scan the inputFile (in this case CF card) and stored 512 data of Bytes into buffer, it returns the number of elements successfully read. If the end of card is reached, the number will be less than 512, because not all data are read, since the end of file contains slack space with 0s. So, we can have statement like while (sscanf(buffer, sizeof(BYTE), 512, inputFile) == 512), this will make our program continue reading, until the end of card is reach, the while statement is false, the loop is terminated.

My codes: https://github.com/shaunlgs/CS50x
Other posts in the series: Harvard CS50x 2014

Leave a Reply