| Summary | Odds are, if your childhood was like mine, you pulled a secret message out of a cereal box at one point that could only be revealed by holding a red sheet of plastic over it. For this problem set, students are challenged to implement that red sheet of plastic in order to solve a murder mystery! (Spoiler alert: it was Professor Plum in the lounge with the candlestick.) Along the way, students learn that one of the simplest ways to implement an image is with a grid of pixels, each of which can be of a different color. And they're ultimately challenged to resize BMPs, which store images in precisely that manner. |
| Topics | Arithmetic. Loops. Conditions. File I/O. Hexadecimal. Steganography. |
| Audience | CS1 or higher. |
| Difficulty | We provide some skeletal code, and it turns out that students need write only a few lines of code themselves. The problem set is as much about understanding the problem domains as it is about implementing actual solutions. |
| Strengths | Excites students, particularly those interested in graphics and security. Teaches students how to read and write files. Excellent opportunity to learn hexadecimal in a compelling context using an actual hex editor to "see" an image (BMP) underneath its hood. |
| Weaknesses | Depending on how much skeletal code is provided, actual solutions require relatively few lines of code. |
| Dependencies | Exposure to loops, conditions, file I/O. We happen to use C, but any language that provides byte-level access to files could be used. |
next to the layer. (If that window is not present, select Windows > Layers.) You should then be able to see the signal layer's content: a secret message written in cyan (#e0ffff). Double-click the message and edit however you'd like.
.
Welcome to Tudor Mansion. Your host, Mr. John Boddy, has met an untimely end—he's the victim of foul play. To win this game, you must determine the answer to these three questions: Who done it? Where? And with what weapon? Unfortunately for you (though even more unfortunately for Mr. Boddy), the only evidence you have is a 24-bit BMP file called clue.bmp, pictured below, that he whipped up for his estranged granddaughter in his final moments. Hidden among this file's red "noise" is a message from Mr. Boddy.
You long ago threw away that piece of red plastic from childhood that would solve this mystery for you, and so you must attack it as the computer scientist that you almost are. But, first, some background...
Perhaps the simplest way to represent an image is with a grid of pixels (i.e., dots), each of which can be of a different color. For black-and-white images, we thus need 1 bit per pixel, as 0 could represent black and 1 could represent white, as in the below.1
In this sense, then, is an image just a bitmap (i.e., a map of bits). For more colorful images, you simply need more bits per pixel. A file format (like GIF) that supports "8-bit color" uses 8 bits per pixel. A file format (like BMP, JPEG, or PNG) that supports "24-bit color" uses 24 bits per pixel.2
A 24-bit BMP like Mr. Boddy's uses 8 bits to signify the amount of red in a pixel's color, 8 bits to signify the amount of green in a pixel's color, and 8 bits to signify the amount of blue in a pixel's color. If you've ever heard of RGB color, well, there you have it: red, green, blue.
If the R, G, and B values of some pixel in a BMP are, say, 0xff, 0x00, and 0x00 in hexadecimal, that pixel is purely red, as 0xff (otherwise known as 255 in decimal) implies "a lot of red," while 0x00 and 0x00 imply "no green" and "no blue," respectively. Given how red Mr. Boddy's BMP is, it clearly has a lot of pixels with those RGB values. But it also has a few with other values.
Incidentally, HTML and CSS (languages in which webpages can be written) model colors in this same way. In fact, for more RGB "codes," see the URL below.
http://www.w3schools.com/html/html_colors.asp
Now let's get more technical. Recall that a file is just a sequence of bits, arranged in some fashion. A 24-bit BMP file, then, is essentially just a sequence of bits, (almost) every 24 of which happen to represent some pixel's color. But a BMP file also contains some "metadata," information like an image's height and width. That metadata is stored at the beginning of the file in the form of two data structures generally referred to as "headers" (not to be confused with C's header files).3 The first of these headers, called BITMAPFILEHEADER, is 14 bytes long. (Recall that 1 byte equals 8 bits.) The second of these headers, called BITMAPINFOHEADER, is 40 bytes long. Immediately following these headers is the actual bitmap: an array of bytes, triples of which represent a pixel's color.4 However, BMP stores these triples backwards (i.e., as BGR), with 8 bits for blue, followed by 8 bits for green, followed by 8 bits for red.5 In other words, were we to convert the 1-bit smiley above to a 24-bit smiley, substituting red for black, a 24-bit BMP would store this bitmap as follows, where 0000ff signifies red and ffffff signifies white; we've highlighted in red all instances of 0000ff.
ffffff ffffff 0000ff 0000ff 0000ff 0000ff ffffff ffffff
ffffff 0000ff ffffff ffffff ffffff ffffff 0000ff ffffff
0000ff ffffff 0000ff ffffff ffffff 0000ff ffffff 0000ff
0000ff ffffff ffffff ffffff ffffff ffffff ffffff 0000ff
0000ff ffffff 0000ff ffffff ffffff 0000ff ffffff 0000ff
0000ff ffffff ffffff 0000ff 0000ff ffffff ffffff 0000ff
ffffff 0000ff ffffff ffffff ffffff ffffff 0000ff ffffff
ffffff ffffff 0000ff 0000ff 0000ff 0000ff ffffff ffffff
Because we've presented these bits from left to right, top to bottom, in 8 columns, you can actually see the red smiley if you take a step back.
To be clear, recall that a hexadecimal digit represents 4 bits. Accordingly, ffffff in hexadecimal actually signifies 111111111111111111111111 in binary.
Okay, let's transition from theory to practice. Open up smiley.bmp, as by double-clicking it, and you'll see that it resembles the below, albeit much smaller (since it's only 8 pixels by 8 pixels).
Now open that file in xxd, a "hex editor," by executing the command below at a command prompt.
xxd -c 24 -g 3 -s 54 smiley.bmp
You should see the below; we've again highlighted in red all instances of 0000ff.
0000036: ffffff ffffff 0000ff 0000ff 0000ff 0000ff ffffff ffffff ........................
000004e: ffffff 0000ff ffffff ffffff ffffff ffffff 0000ff ffffff ........................
0000066: 0000ff ffffff 0000ff ffffff ffffff 0000ff ffffff 0000ff ........................
000007e: 0000ff ffffff ffffff ffffff ffffff ffffff ffffff 0000ff ........................
0000096: 0000ff ffffff 0000ff ffffff ffffff 0000ff ffffff 0000ff ........................
00000ae: 0000ff ffffff ffffff 0000ff 0000ff ffffff ffffff 0000ff ........................
00000c6: ffffff 0000ff ffffff ffffff ffffff ffffff 0000ff ffffff ........................
00000de: ffffff ffffff 0000ff 0000ff 0000ff 0000ff ffffff ffffff ........................
In the leftmost column above are addresses within the file or, equivalently, offsets from the file's first byte, all of them given in hex. Note that 00000036 in hexadecimal is 54 in decimal. You're thus looking at byte 54 onward of smiley.gif. Recall that a 24-bit BMP's first 14 + 40 = 54 bytes are filled with metadata. If you really want to see that metadata in addition to the bitmap, execute the command below.
xxd -c 24 -g 3 smiley.bmp
If smiley.bmp actually contained ASCII characters, you'd see them in xxd's rightmost column instead of all of those dots.
So, smiley.bmp is 8 pixels wide by 8 pixels tall, and it's a 24-bit BMP (each of whose pixels is represented with 24 ÷ 8 = 3 bytes). Each row (aka "scanline") thus takes up (8 pixels) × (3 bytes per pixel) = 24 bytes, which happens to be a multiple of 4. It turns out that BMPs are stored a bit differently if the number of bytes in a scanline is not, in fact, a multiple of 4. In small.bmp, for instance, is another 24-bit BMP, a green box that's 3 pixels wide by 3 pixels wide. Go ahead and open it, as by double-clicking it, and you'll see that it resembles the below, albeit much smaller.
Each scanline in small.bmp thus takes up (3 pixels) × (3 bytes per pixel) = 9 bytes, which is not a multiple of 4. And so the scanline is "padded" with as many zeroes as it takes to extend the scanline's length to a multiple of 4. In other words, between 0 and 3 bytes of padding are needed for each scanline in a 24-bit BMP. (Understand why?) In the case of small.bmp, 3 bytes' worth of zeroes are needed, since (3 pixels) × (3 bytes per pixel) + (3 bytes of padding) = 12 bytes, which is indeed a multiple of 4.
To "see" this padding, go ahead and run the below.
xxd -c 12 -g 3 -s 54 small.bmp
Note that we're using a different value for -c than we did for smiley.bmp so that xxd outputs only 4 columns this time (3 for the green box and 1 for the padding). You should see output like the below; we've highlighted in green all instances of 00ff00.
0000036: 00ff00 00ff00 00ff00 000000 ............
0000042: 00ff00 ffffff 00ff00 000000 ............
000004e: 00ff00 00ff00 00ff00 000000 ............
For contrast, let's use xxd on large.bmp, which looks identical to small.bmp but, at 12 pixels by 12 pixels, is four times as large. Go ahead and execute the below; you may need to widen your window to avoid wrapping.
xxd -c 36 -g 3 -s 54 large.bmp
You should see output like the below; we've again highlighted in green all instances of 00ff00.
0000036: 00ff00 00ff00 00ff00 00ff00 00ff00 00ff00 00ff00 00ff00 00ff00 00ff00 00ff00 00ff00 ....................................
000005a: 00ff00 00ff00 00ff00 00ff00 00ff00 00ff00 00ff00 00ff00 00ff00 00ff00 00ff00 00ff00 ....................................
000007e: 00ff00 00ff00 00ff00 00ff00 00ff00 00ff00 00ff00 00ff00 00ff00 00ff00 00ff00 00ff00 ....................................
00000a2: 00ff00 00ff00 00ff00 00ff00 00ff00 00ff00 00ff00 00ff00 00ff00 00ff00 00ff00 00ff00 ....................................
00000c6: 00ff00 00ff00 00ff00 00ff00 ffffff ffffff ffffff ffffff 00ff00 00ff00 00ff00 00ff00 ....................................
00000ea: 00ff00 00ff00 00ff00 00ff00 ffffff ffffff ffffff ffffff 00ff00 00ff00 00ff00 00ff00 ....................................
000010e: 00ff00 00ff00 00ff00 00ff00 ffffff ffffff ffffff ffffff 00ff00 00ff00 00ff00 00ff00 ....................................
0000132: 00ff00 00ff00 00ff00 00ff00 ffffff ffffff ffffff ffffff 00ff00 00ff00 00ff00 00ff00 ....................................
0000156: 00ff00 00ff00 00ff00 00ff00 00ff00 00ff00 00ff00 00ff00 00ff00 00ff00 00ff00 00ff00 ....................................
000017a: 00ff00 00ff00 00ff00 00ff00 00ff00 00ff00 00ff00 00ff00 00ff00 00ff00 00ff00 00ff00 ....................................
000019e: 00ff00 00ff00 00ff00 00ff00 00ff00 00ff00 00ff00 00ff00 00ff00 00ff00 00ff00 00ff00 ....................................
00001c2: 00ff00 00ff00 00ff00 00ff00 00ff00 00ff00 00ff00 00ff00 00ff00 00ff00 00ff00 00ff00 ....................................
Okay, xxd only showed you the bytes in these BMPs. How do we actually get at them programmatically? Well, in copy.c is a program whose sole purpose in life is to create a copy of a BMP, piece by piece. Of course, you could just use cp for that. But cp isn't going to help Mr. Boddy. Let's hope that copy.c does!
Go ahead and compile copy.c into a program called copy, as with the command below.
gcc -o copy -std=c99 copy.c
Then execute a command like the below.
./copy smiley.bmp copy.bmp
If you then execute
ls -l
you should see that smiley.bmp and copy.bmp are indeed the same size. Let's double-check that they're actually the same! Execute the below.
diff smiley.bmp copy.bmp
If that command tells you nothing, the files are indeed identical.6 Feel free to SFTP the files to your own desktop to confirm as much visually. But diff does a byte-by-byte comparison, so its eye is probably sharper than yours!
So how now did that copy get made? It turns out that copy.c relies on bmp.h. Let's take a look. Open up bmp.h with a text editor, and you'll see actual definitions of those headers we've mentioned, adapted from Microsoft's own implementations thereof. In addition, that file defines BYTE, DWORD, LONG, and WORD, data types normally found in the world of Win32 (i.e., Windows) programming. Notice how they're just aliases for primitives with which you are (hopefully) already familiar. It appears that BITMAPFILEHEADER and BITMAPINFOHEADER make use of these types. This file also defines a struct called RGBTRIPLE that, quite simply, "encapsulates" three bytes: one blue, one green, and one red (the order, recall, in which we expect to find RGB triples actually on disk).
Why are these structs useful? Well, recall that a file is just a sequence of bytes (or, ultimately, bits) on disk. But those bytes are generally ordered in such a way that the first few represent something, the next few represent something else, and so on. "File formats" exist because the world has standardized what bytes mean what. Now, we could just read a file from disk into RAM as one big array of bytes. And we could just remember that the byte at location [i] represents one thing, while the byte at location [j] represents another. But why not give some of those bytes names so that we can retrieve them from memory more easily? That's precisely what the structs in bmp.h allow us to do. Rather than think of some file as one long sequence of bytes, we can instead think of it as a sequence of structs.
Recall that smiley.bmp is 8 by 8 pixels, and so it should take up 14 + 40 + 8 ⋅ 8 ⋅ 3 = 246 bytes on disk. (Confirm as much if you'd like using ls.) Here's what it thus looks like on disk according to Microsoft:
As this figure suggests, order does matter when it comes to structs' members. Byte 57 is rgbtBlue (and not, say, rgbtRed), because rgbtBlue is defined first in RGBTRIPLE.7
Now go ahead and pull up the URLs to which BITMAPFILEHEADER and BITMAPINFOHEADER are attributed, per the comments in bmp.h. You're about to start using MSDN (Microsoft Developer Network)!
Rather than hold your hand further on a stroll through copy.c, we're instead going to ask you some questions and let you teach yourself how the code therein works. As always, man is your friend, and so, now, is MSDN. If not sure on first glance how to answer some question, do some quick research and figure it out! You might want to turn to the below resource as well.
http://www.cppreference.com/wiki/io/c/
Allow us to suggest that you also run copy within gdb while answering these questions. Set a breakpoint at main and walk through the program. Recall that you can tell gdb to start running the program with a command like the below at gdb's prompt.
run smiley.bmp copy.bmp
If you tell gdb to print the values of bf and bi (once read in from disk), you'll see output like the below, which we daresay you'll find quite useful.
{bfType = 19778, bfSize = 246, bfReserved1 = 0, bfReserved2 = 0,
bfOffBits = 54}
{biSize = 40, biWidth = 8, biHeight = -8, biPlanes = 1, biBitCount = 24,
biCompression = 0, biSizeImage = 192, biXPelsPerMeter = 2834,
biYPelsPerMeter = 2834, biClrUsed = 0, biClrImportant = 0}
Answer each of the following questions in a sentence or more.
Okay, back to Mr. Boddy.
Write a program called whodunit in a file called whodunit.c that reveals Mr. Boddy's final words.
OMG, what? How?
Well, think back to childhood when you held that piece of red plastic over similarly hidden messages.10 Essentially, the plastic turned everything red but somehow revealed those messages. Implement that same idea in whodunit. Like copy, your program should accept exactly two command-line arguments. And if you execute a command like the below, stored in verdict.bmp should be a BMP in which Mr. Boddy's message is actually legible.
whodunit clue.bmp verdict.bmp
Allow us to suggest that you begin tackling this mystery by executing the command below.
cp copy.c whodunit.c
Wink wink. You may be amazed by how few lines of code you actually need to write in order to help Mr. Boddy.
There's nothing hidden in smiley.bmp, but feel free to test your program out on its pixels nonetheless, if only because that BMP is small and you can thus compare it and your own program's output with xxd during development.
Rest assured that more than one solution is possible. So long as your program's output is readable, no matter its color(s), Mr. Boddy will rest in peace.
So, whodunit? And where? And with what?
Well that was fun. Bit late for Mr. Boddy, though.
Let's have you write more than, what, two lines of code? Implement now in resize.c a program called resize that resizes 24-bit uncompressed BMPs by a factor of n. Your program should accept exactly three command-line arguments, per the below usage, whereby the first (n) must be a positive integer less than or equal to 100, the second the name of the file to be resized, and the third the name of the resized version to be written.
Usage: resize n infile outfile
With a program like this, we could have created large.bmp out of small.bmp by resizing the latter by a factor of 4 (i.e., by multiplying both its width and its height by 4), per the below.
./resize 4 small.bmp large.bmp
You're welcome to get started by copying (yet again) copy.c and naming the copy resize.c. But spend some time thinking about what it means to resize a BMP.11 Decide which of the fields in BITMAPFILEHEADER and BITMAPINFOHEADER you might need to modify. Consider whether or not you'll need to add or subtract padding to scanlines. And be thankful that we don't expect you to support fractional n between 0 and 1!12
This is CS50.
Copyright © 2011, David J. Malan, Harvard University
This work is licensed under a Creative Commons Attribution-Noncommercial-Share Alike 3.0 Unported License.
Extra info about this assignment:
