Friday, February 26, 2010

Optimizing Code For Fun

Introduction

     There are many ways of stimulating the brain; cooking, reading, cross word puzzles, sudoku, etc. In addition, for a handful of nerds myself included, we can add writing small, obfuscated computer programs that hides the logic behind unreadable but artistically constructed source code.

The International Obfuscated C Code Contest

     To facilitate the urge to develop these obscure programs there is of course a solution. The solution is a programming contest that encourages creative developers to show off their programming skills. The contest is known as the International Obfuscated C Code Contest and the entries are judged on how obfuscated they are and how novel the idea behind a program is.

     The goal is to write something clever and somewhat interesting in a small C language program that shadows the intent of the program. Developers use various techniques that typically are not used in normal software development, like abusing some of the C language constructs. The competition has strict rules on how much code an entry can have, and its frankly not much, only 2048 characters. A normal program would only be able to do a couple of very basic operations with these limitations, such as do some string management, or do some simple calculations.

     I’ve had the honor to win the competition three times and in this article I’ll describe my favorite entry which I think also happens to be the easiest to explain. The entry really pushes the limits on the number of features that can be squeezed into 2kB of source code. It is a complete 3-D racing game with multiple tracks, hills, mountains, snow, opponent cars, different traction depending on weather conditions, and a status panel with lap time and speed. The game even includes high scores. The picture below show a screenshot of the game in action.

        

        Obfuscated rally game in action


Technical challenges

     I will try to give some technical details that perhaps give an insight into how it was possible to include all features into only 2048 characters of C code.

     A lot of the obfuscation comes free by just fanatically optimize for source code size. The initial program with fairly readable logic and algorithms was about five times as big as the final version, while still using short variable names etc. It took several hundreds of hours to squeeze the code down to the size limits, and many techniques were used.

     The program uses many temporary variables; more or less all lower and upper case single letter variables are used. Some have multiple purposes, such as representing both a color and the length of a track.

     The C language have some operators that typically aren’t used that much, but they provide a way to create complex expressions in a small amount of code. My favorite operators are the ? operator and the comma operator. In combination, these operators can be used to implement complicated logic that is both hard to read and very compact.

     Formatting is also an important aspect of an obfuscated program. Typically the C source code is indented to improve readability and to group logical blocks of code, but there are no strict rules on how to format a program. Most entries to IOCCC heavily abuses the flexibility of formatting, and so does this entry. By carefully formatting the source code, its possible do hide some of the algorithms and provide something quite impossible to understand.

Conclusion

     It took quite some time to create the rally program, mainly because of the extreme optimization. But back to the opening statement of the article, it is just another way to stimulate the brain. Optimizing code is very much like solving sudoku or a crossword puzzle. It’s a matter of find pieces of the code that can be expressed in less characters. The more optimized the program is, the harder it is to find additional optimizations. Towards the end of the development, I was able to reduce size with only a couple of characters an hour. But in the end it is a quite awarding feeling to reach a point where you proudly can submit the entry to the competition and wait for the judges response.

     For any fellow nerd that want to dig deeper into the source code or perhaps try the game, I provide a link to the source code here.

Enjoy!

No comments:

Post a Comment