Acquaint you with file I/O.
Get you more comfortable with data structures, hexadecimal, and pointers.
Introduce you to computer scientists across campus.
Help Mr. Boddy.
Hacker Edition challenges you to reduce (and enlarge) BMPs.
This course’s philosophy on academic honesty is best stated as "be reasonable." The course recognizes that interactions with classmates and others can facilitate mastery of the course’s material. However, there remains a line between enlisting the help of another and submitting the work of another. This policy characterizes both sides of that line.
The essence of all work that you submit to this course must be your own. Collaboration on problem sets is not permitted except to the extent that you may ask classmates and others for help so long as that help does not reduce to another doing your work for you. Generally speaking, when asking for help, you may show your code to others, but you may not view theirs, so long as you and they respect this policy’s other constraints. Collaboration on quizzes is not permitted at all. Collaboration on the course’s final project is permitted to the extent prescribed by its specification.
Below are rules of thumb that (inexhaustively) characterize acts that the course considers reasonable and not reasonable. If in doubt as to whether some act is reasonable, do not commit it until you solicit and receive approval in writing from the course’s heads. Acts considered not reasonable by the course are handled harshly. If the course refers some matter to the Administrative Board and the outcome is Admonish, Probation, Requirement to Withdraw, or Recommendation to Dismiss, the course reserves the right to impose local sanctions on top of that outcome that may include an unsatisfactory or failing grade for work submitted or for the course itself.
If you commit some act that is not reasonable but bring it to the attention of the course’s heads within 72 hours, the course may impose local sanctions that may include an unsatisfactory or failing grade for work submitted, but the course will not refer the matter to the Administrative Board.
Communicating with classmates about problem sets' problems in English (or some other spoken language).
Discussing the course’s material with others in order to understand it better.
Helping a classmate identify a bug in his or her code at Office Hours, elsewhere, or even online, as by viewing, compiling, or running his or her code, even on your own computer.
Incorporating snippets of code that you find online or elsewhere into your own code, provided that those snippets are not themselves solutions to assigned problems and that you cite the snippets' origins.
Reviewing past semesters' quizzes and solutions thereto.
Sending or showing code that you’ve written to someone, possibly a classmate, so that he or she might help you identify and fix a bug.
Sharing snippets of your own code online so that others might help you identify and fix a bug.
Turning to the web or elsewhere for instruction beyond the course’s own, for references, and for solutions to technical difficulties, but not for outright solutions to problem set’s problems or your own final project.
Whiteboarding solutions to problem sets with others using diagrams or pseudocode but not actual code.
Working with (and even paying) a tutor to help you with the course, provided the tutor does not do your work for you.
Accessing a solution in CS50 Vault to some problem prior to (re-)submitting your own.
Asking a classmate to see his or her solution to a problem set’s problem before (re-)submitting your own.
Decompiling, deobfuscating, or disassembling the staff’s solutions to problem sets.
Failing to cite (as with comments) the origins of code or techniques that you discover outside of the course’s own lessons and integrate into your own work, even while respecting this policy’s other constraints.
Giving or showing to a classmate a solution to a problem set’s problem when it is he or she, and not you, who is struggling to solve it.
Looking at another individual’s work during a quiz.
Paying or offering to pay an individual for work that you may submit as (part of) your own.
Providing or making available solutions to problem sets to individuals who might take this course in the future.
Searching for, soliciting, or viewing a quiz’s questions or answers prior to taking the quiz.
Searching for or soliciting outright solutions to problem sets online or elsewhere.
Splitting a problem set’s workload with another individual and combining your work.
Submitting (after possibly modifying) the work of another individual beyond allowed snippets.
Submitting the same or similar work to this course that you have submitted or will submit to another.
Submitting work to this course that you intend to use outside of the course (e.g., for a job) without prior approval from the course’s heads.
Using resources during a quiz beyond those explicitly allowed in the quiz’s instructions.
Viewing another’s solution to a problem set’s problem and basing your own solution on it.
Your work on this problem set will be evaluated along four axes primarily.
To what extent does your code implement the features required by our specification?
To what extent is your code consistent with our specifications and free of bugs?
To what extent is your code written well (i.e., clearly, efficiently, elegantly, and/or logically)?
To what extent is your code readable (i.e., commented and indented with variables aptly named)?
All students, whether taking the course SAT/UNS or for a letter grade, must ordinarily submit this and all other problem sets to be eligible for a satisfactory grade unless granted an exception in writing by the course’s heads.
First, curl up with Jason’s short on file I/O and Rob’s short on structs. Just keep in mind that Jason’s short happens to focus on ASCII (i.e., text) files as opposed to binary files (like images). More on those later!
Next, join Nate on a tour of
valgrind, a command-line tool that will help you find "memory leaks": memory that you’ve allocated (i.e., asked the operating system for), as with
malloc, but not freed (i.e., given back to the operating system).
Finally, remind yourself how
gdb works if you’ve forgotten or not yet used!
As always, first open a terminal window and execute
to make sure your appliance is up-to-date.
Like Problem Set 3, this problem set comes with some distribution code that you’ll need to download before getting started. Go ahead and execute
in order to navigate to your
~/Dropbox directory. Then execute
in order to download a ZIP (i.e., compressed version) of this problem set’s distro. If you then execute
you should see that you now have a file called
hacker4.zip in your
~/Dropbox directory. Unzip it by executing the below.
If you again execute
you should see that you now also have a
hacker4 directory. You’re now welcome to delete the ZIP file with the below.
rm -f hacker4.zip
Now dive into that
hacker4 directory by executing the below.
and you should see that the directory contains the below.
bmp/ jpg/ questions.txt
How fun! Two subdirectories and a file. Who knows what could be inside! Let’s get started.
If you ever saw Windows XP’s default wallpaper (think rolling hills and blue skies), then you’ve seen a BMP. If you’ve ever looked at a webpage, you’ve probably seen a GIF. If you’ve ever looked at a digital photo, you’ve probably seen a JPEG. If you’ve ever taken a screenshot on a Mac, you’ve probably seen a PNG. Read up online on the BMP, GIF, JPEG, and PNG file formats. Then, open up
~/Dropbox/hacker4, as with
gedit, and tell us the below.
How many different colors does each format support?
Which of the formats supports animation?
What’s the difference between lossy and lossless compression?
Which of these formats is lossy-compressed?
Next, curl up with the article from MIT at http://cdn.cs50.net/2014/fall/psets/4/garfinkel.pdf.
Though somewhat technical, you should find the article’s language quite accessible. Once you’ve read the article, answer each of the following questions in a sentence or more in
What happens, technically speaking, when a file is deleted on a FAT file system?
What can someone like you do to ensure (with high probability) that files you delete cannot be recovered?
Anyhow, 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
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
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. (Image adapted from http://www.brackeen.com/vga/bitmaps.html.)
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 set only expects that you support version 4.0 (the latest) of Microsoft’s BMP format, 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
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
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, stop! Don’t proceed further until you’re sure you understand why
0000ff represents a red pixel in a 24-bit BMP file.
Okay, let’s transition from theory to practice. Double-click Home on John Harvard’s desktop and you should find yourself in John Harvard’s home directory. Double-click hacker4, double-click bmp, and then double-click smiley.bmp therein. You should see a tiny smiley face that’s only 8 pixels by 8 pixels. Select View > Zoom > Zoom Fit, and you should see a larger, albeit blurrier, version. (So much for "enhance," huh?) Actually, this particular image shouldn’t really be blurry, even when enlarged. The program that launched when you double-clicked smiley.bmp (called Image Viewer) is simply trying to be helpful (CSI-style) by "dithering" the image (i.e., by smoothing out its edges). Below’s what the smiley looks like if you zoom in without dithering. At this zoom level, you can really see the image’s pixels (as big squares).
Okay, go ahead and return your attention to a terminal window, and navigate your way to
~/Dropbox/hacker4/bmp. (Remember how?) Let’s look at the underlying bytes that compose
xxd, a command-line "hex editor." Execute:
xxd -c 24 -g 3 -s 54 smiley.bmp
You should see the below; we’ve again highlighted in red all instances of
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.bmp. 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
smiley.bmp actually contained ASCII characters, you’d see them in
xxd's rightmost column instead of all of those dots.
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 with Image Viewer (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, 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
0000036: 00ff00 00ff00 00ff00 000000 ............ 0000042: 00ff00 ffffff 00ff00 000000 ............ 000004e: 00ff00 00ff00 00ff00 000000 ............
For contrast, let’s use
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
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 ....................................
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!
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
Go ahead and compile
copy.c into a program called
make. (Remember how?) Then execute a command like the below.
./copy smiley.bmp copy.bmp
If you then execute ls (with the appropriate switch), you should see that
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. (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 in Ristretto Image Viewer (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 (as with
gedit), and you’ll see actual definitions of those headers we’ve mentioned, adapted from Microsoft’s own implementations thereof. In addition, that file defines
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
BITMAPINFOHEADER make use of these types. This file also defines a
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
struct`s 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 `struct`s.
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: