Whodunit

Answer some questions and then implement a program that reveals a hidden message in a BMP, per the below.

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 whodunit.

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 Mr. Boddy whipped up on his computer in his final moments. Hidden among this file’s red "noise" is a drawing of whodunit.

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 a computer scientist instead.

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. (BMP actually supports 1-, 4-, 8-, 16-, 24-, and 32-bit color.)

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. If curious, see http://en.wikipedia.org/wiki/Web_colors for more details.

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. (Incidentally, these headers have evolved over time. This problem only expects that you support the latest version of Microsoft’s BMP format, 4.0, which debuted with Windows 95.) 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. (In 1-, 4-, and 16-bit BMPs, but not 24- or 32-, there’s an additional header right after BITMAPINFOHEADER called RGBQUAD, an array that defines "intensity values" for each of the colors in a device’s palette.) 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. (Some BMPs also store the entire bitmap backwards, with an image’s top row at the end of the BMP file. But we’ve stored this problem set’s BMPs as described herein, with each bitmap’s top row first and bottom row last.) 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.

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. Within CS50 IDE’s file browser, double-click smiley.bmp, and you should see a tiny smiley face that’s only 8 pixels by 8 pixels. Via the drop-down menu in that file’s newly opened tab, change 100% to 800% to zoom in a bit, and you should see a larger version, a la the below. (If it seems blurry, be sure that Smooth atop the window isn’t checked.) At this zoom level, you can really see the image’s pixels (as big squares).

Okay, let’s now look at the underlying bytes that compose smiley.bmp. Within CS50 IDE’s file browser, right- or control-click smiley.bmp and select Open as hexadecimal in order to view the file’s bytes in hexadecimal (i.e., base-16). In the tab that appears, change Start with byte to 54, change Bytes per row to 24, change Bytes per column to 3. Then click Set. If unable to change these values, try clicking View > Night Mode and try again. You should see the below, byte 54 onward of smiley.bmp. (Recall that a 24-bit BMP’s first 14 + 40 = 54 bytes are filled with metadata, so we’re simply ignoring that for now.) As before, we’ve highlighted in red all instances of 0000ff.

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. If you view it (as by double-clicking it), you’ll see that it resembles the below, albeit much smaller. (Indeed, you might need to zoom in again to see it.)

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, right- or control-click small.bmp in CS50 IDE’s file browser and select Open as hexadecimal. In the tab that appears, change Start with byte to 54, change Bytes per row to 12, and change Bytes per column to 3. Then click Set. You should see output like the below; we’ve highlighted in green all instances of 00ff00.

For contrast, let’s next look at large.bmp, which looks identical to small.bmp but, at 12 pixels by 12 pixels, is four times as large. Right- or control-click it in CS50 IDE’s file browser, then select Open as hexadecimal. You should see output like the below; we’ve again highlighted in green all instances of 00ff00

Worthy of note is that this BMP lacks padding! After all, (12 pixels) × (3 bytes per pixel) = 36 bytes is indeed a multiple of 4.

Knowing all this has got to be useful!

Okay, CS50 IDE 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. 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 using make. (Remember how?) Then execute a command like the below.

If you then execute ls (with the appropriate switch), 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.

If that command tells you nothing, the files are indeed identical. (Note that some programs, like Photoshop, include trailing zeroes at the ends of some BMPs. Our version of copy throws those away, so don’t be too worried if you try to copy a BMP that you’ve downloaded or made only to find that the copy is actually a few bytes smaller than the original.) Feel free to open both files (as by double-clicking each) 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, 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 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. Our use, incidentally, of the attribute called packed ensures that clang does not try to "word-align" members (whereby the address of each member’s first byte is a multiple of 4), lest we end up with "gaps" in our structs that don’t actually exist on disk. No need to worry about that particular implementation detail, though.

Lastly, you may have noticed in copy.c that, whenever we output an error message, we use fprintf (the first argument to which is stderr) instead of the more-familiar printf. It turns out that printf prints messages to "standard output" (aka stdout), the destination of which is typically a user’s terminal window. But "standard error (aka stderr) also exists, the destination of which is also typically (and perhaps confusingly!) a user’s terminal window. But via stdout and stderr can a programmer keep error messages separated from non-error messages so that, if the user wants, one or the other (or both) can be "redirected" (with >) or "piped" (with |) somewhere other than the user’s terminal window.

In other words,

is equivalent to

but the former is more succinct. In order to print an error message to stderr, though, do use fprintf per the below.

Go ahead and pull up the URLs to which BITMAPFILEHEADER and BITMAPINFOHEADER are attributed, per the comments in bmp.h. 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.

Open up README.md and replace every TODO therein (except the last) with your answer to the question above it. That file happens to be written in Markdown, a lightweight format for text files that makes it easy to stylize text. For instance, we’ve prefixed each question with ## so that, when viewed on GitHub, it renders in a larger, bold font. And we’ve surrounded code-related keywords with backticks (\`) so that they render on GitHub in a monospaced (i.e., code-like) font.

No need to write your answers in Markdown; plaintext suffices. But if you’d like to format your answers somehow, see https://guides.github.com/features/mastering-markdown/ for a tutorial.

Implement a program called whodunit that reveals Mr. Boddy’s drawing in such a way that you can recognize whodunit.

Alright, whodunit? Replace the last TODO in README.md with your answer!

Your program should behave per the examples below. Assumed that the underlined text is what some user has typed.

Think back to childhood when you held that piece of red plastic over similarly hidden messages. (If you remember no such piece of plastic, best to ask a classmate about his or her childhood.) 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 drawing is no longer covered with noise.

Allow us to suggest that you begin tackling this mystery by executing the command below.

Then add and/or change just a few lines of code.

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 CS50 IDE’s hex viewer during development.

Rest assured that more than one solution is possible. So long as Mr. Boddy’s drawing is identifiable (by you), no matter its legibility, Mr. Boddy will rest in peace.

Because whodunit can be implemented in several ways, afraid you can’t check your implementation’s correctness with check50!

No solution from the staff, lest it spoil your fun!