CS 11: advanced C track: challenge lab

Material to be covered for this lab

Code maintenance and cleanup
Graphics using X11

Overview of this lab

This lab is a departure from the rest of the labs, which is why it's put at the end. This lab is so hard that it is optional. To reiterate: you do not have to do this lab if you don't want to! This lab is conceptually very simple, but getting it right is going to take you a long time (think 12-16 hours even if everything goes well). Despite the fact that you are not responsible for this lab, I encourage you to try it; you will learn a lot of very important skills even if you don't finish it. Plus it's fun.

The set-up

To introduce this lab, let's look into the future. After you graduate from Caltech with flying colors, superb grades and a fist-full of recommendations from all of your professors, each of whom swears up and down that you are the best programmer they have ever seen, you decide that, before going on to graduate school and setting the research world on fire, you want to work in the Real World (TM) for a few years and build up your bank account. Since you like computer games, you accept a job at a high-powered computer game company. You are eager to start writing the next generation of killer computer games, but your first assignment turns out to be quite different from what you expected. Your boss tells you that the programmer you are replacing (who has decided to go to India and live in a Buddhist temple in order to "find himself") was a brilliant but somewhat mentally unstable individual. He wrote some of the most amazing code anyone had ever seen, but nobody could figure out how it worked. The specific code your boss wants you to work on is code to interactively generate fractals given user input on a mouse. Your boss wants to incorporate the code into a role-playing game they are developing, but they don't want the code to remain the impenetrable mess it currently is, because they won't be able to maintain it. "Just take the code and clean it up," he says. "Give all the functions and variables meaningful names, make it readable, add comments, that kind of thing." OK, you figure. After all, how bad can it be? So you look at the code, which is here.

Suddenly you get a sinking feeling in your stomach. You rush to your boss and ask him if you can just re-write the program from scratch. "No," he says, "we don't have time for that. Just clean up the code. You're a Caltech hot-shot, right? Are you saying you aren't smart enough to just clean up some code?" Humiliated, you vow that you'll show him. So you get to work.

Why am I torturing you like this?

This program is an extreme example of what you will actually find when working in industry. Everyone thinks they're going to go out and write great new programs from scratch, but 90% of the time or more, you're actually going to be extending a program that someone else has written. Furthermore, most of these programs are not written by good programmers, and most have been written very hastily in order to meet a deadline. Most will have few if any comments (or worse, outdated and/or misleading comments), cryptic or meaningless variable names, horrible and inconsistent code formatting, etc. etc. And to maintain such a program, it's often necessary to clean up this code. Very often, the person who wrote it has moved on to another job, and has left no record of how his code worked. So being able to clean up someone else's code while simultaneously figuring out how it works is an important skill. But in order to provide you with a good assignment along these lines, I needed to find some examples of really badly-written code. Since the Microsoft Windows source code is unavailable ;-) I chose the next best thing, which is code from a very special contest.

The IOCCC

There are many programming contests around, but probably the most unique one of all is the International Obfuscated C Code Contest, or IOCCC. This is a contest in which programmers submit very small programs (currently the maximum is 4096 bytes; it has increased as the years have gone by) which are intentionally as obscure, unreadable, and perverse as possible, while simultaneously doing something interesting. The program you'll be cleaning up was one of the winning entries for the 1994 contest. Be afraid, be very afraid...

Program to (re-)write

The program you are to re-write is here. It was written by Teemu Rantanen of the Helsinki University of Technology. Descriptions for how to run it and what it does are here. You will also need an input file, which is here.

What the finished program must be like

The finished program must have the following features:

It must compile without warnings using gcc given the compiler options -Wall -Wstrict-prototypes -ansi -pedantic.
It must be neatly formatted and readable. Use the C style checking program to check for obvious formatting errors.
All the cryptic variable and function names must be replaced with meaningful ones which describe the function of the variables or functions (within reason; loop indices can still be i, j, etc.).
There shouldn't be any global variables.
It's OK (in fact, it's necessary) to replace obscure and cryptic code with code which does the exact same thing but is more readable and clear. However, it's important that the final program do exactly the same thing as the original one.
There should be enough comments that someone who knows nothing about X11 graphics or fractals (but who knows C) can follow the logic of the program.

About X11 graphics

X11 is the name of the graphics libraries used in computers running the Unix operating system (including Linux). The graphics environments you may have heard of (Gnome, KDE etc.) are all built on top of X11. X11 is big, powerful, messy, and ugly, but fortunately you don't have to know much about it in order to do this assignment. Most of the X11 commands that are used in the code are pretty self-explanatory, and reading the man pages on those commands will tell you most of what you need to know.

About fractals

Fractals are self-similar geometrical objects that can be created following simple rules. The fractals generated by the program you're going to work with are called the Mandelbrot set (after Benoit Mandelbrot, who discovered it) and Julia sets (after Gaston Julia, who discovered them). I don't have time to explain how they work here, but a quick web search will dig up loads of information about these sets. Here are some starting points:

Suggestions

Here are a few tricks that will make your job much easier.

Read the hint file carefully to figure out what the program is doing and how to invoke it.
Write a simple Makefile, without any compiler warnings, and make sure you can compile and run the program correctly before changing anything. Add the compiler warnings later, once the code has been cleaned up enough to make that useful.
Save your work regularly! Create a directory called safe and in it create subdirectories called safe1, safe2, etc. Have the original code in safe/safe1. Every time you make some major changes, first check to see that the program still works, and then create a new safeN directory and copy the new version there. It's very easy to break the code if you make a mistake; if you haven't saved a previous version you may have to start over from scratch.
Most obfuscated programs abuse the C preprocessor, and this one is no exception. Fortunately, you can invoke the C preprocessor manually to undo this damage. There are two ways to do this:
1. Call the cpp program with the original program as an argument; it will dump the preprocessed code to standard out, which you should redirect to a file.
2. Call gcc -E with the original program as an argument; this is the same as calling cpp.
Unfortunately, if you do this directly, the header file <X11/Xlib.h> will also be included, which you don't want. I recommend you comment the first line of the program out, run the preprocessor on the program, and then add the first line back (the preprocessor will remove the comment).
This program also abuses the typedef mechanism; therefore, you should get rid of all the typedefs. Be careful when doing this, especially with typedefs that involve pointers (you'll see what I mean).
To fix up the code formatting, the indent program, though not perfect, is very valuable. Do man indent to find out more about this program.
To give variables meaningful names, start with the X11 commands. Use the man pages to find out what their arguments correspond to; this will give you clues on what to name those variables.
Write comments as you go, even for things you don't understand, e.g.
```
     /* I think this creates a window of some kind. */
```
You should update them as your understanding increases.
Get rid of global variables as soon as possible. Some of them can be gotten rid of by passing extra arguments to functions. Only get rid of one at a time.
Give the program a more meaningful name.
There is supposedly a bug in the program. Find it and fix it.

Files

The original program.
The hint file.
The colormap file, which has to be input to the program (see the hint file).
The C style checking program.

Credits

The program we're using was written by Teemu Rantanen of the Helsinki University of Technology. Thanks, Teemu! Awesome code!

The IOCCC is copyrighted 2003 by Landon Curt Noll, Simon Cooper, Peter Seebach and Leonid A. Broukhis. For the 1994 contest it was copyrighted by Landon Curt Noll and Larry Bassel. The program comes with this copyright notice:

Copyright (c) 1994, Landon Curt Noll & Larry Bassel.
All Rights Reserved.  Permission for personal, educational or non-profit use is
granted provided this this copyright and notice are included in its entirety
and remains unaltered.  All other uses must receive prior permission in writing
from both Landon Curt Noll and Larry Bassel.

Thanks, guys! See, I even left in the "this this" part ;-)

References

The IOCCC home page.