Treasure hunt
In the cs61-exercises/fundamentals1x
directory, you’ll find a program
called treasure.c
.
Type cd fundamentals1x; make
to build the ./treasure
program.
This program is a treasure hunt! By running the program with different options, you can make it print:
- Sixty-one
- An expired cow
- A precious stone
- A golden ratio
- An English word
- A greeting cat
- An infinite loop
- A number that is not a number
- A zero that is less than zero
- Some nasal demons
- A professor
- A Shakespeare play
In fact, there are two or more substantively different ways to produce most of these results. We know of at least 24 command lines that produce treasure.
How many of them can you find?
Skills
- Reading and understanding C code
- Understanding data representation
- Basic properties of C datatypes
- Reverse-engineering inputs for C functions
- Running shell commands
- Researching C library functions and shell commands
- Using
gdb
to explore memory
In-class work
In 45 minutes, try to find the following treasures.
- Find “sixty-one” using
./treasure 6
. (If you run./treasure 6
without arguments, it prints “6”. Can you find other arguments so that it prints something like “sixty-one”?) - Find “sixty-one” using
./treasure 5
. - Find an expired cow using
./treasure 0
. - Find an expired cow using
./treasure 12
. - Find a precious stone using
./treasure 21
. - Find a precious stone using
./treasure 14
. - Find a greeting cat using
./treasure 16
. - Find a greeting cat using
./treasure 2
.
If you have time, search for other treasures too!
How to hunt
We’ve hidden treasure in the program in many different ways. You’ll make progress by looking at the code, by reasoning through its behavior, and, importantly, by running experiments. You can even change the code to see what happens! (But your answers should work on the handout code.) Also use the Web liberally. Don’t understand a term? Search for it!
Don’t be afraid to treat the code like a scientist: run experiments! We often try to understand code by reading it, but that can be difficult, even for simple loops. If you get stuck, try instead to get a feel for a function by observing its behavior. So try running a treasure function with different arguments. What happens? Use the results to develop a hypothesis about its behavior. Then check your hypothesis against the code, and confirm or refute it by running the code with different arguments.
Having trouble getting started? Try using gdb
or lldb
. One
useful technique: Set a breakpoint at printf
and use backtrace
(short version: bt
) to see how printf
got called. gdb treasure
, then b printf
, r 6
(which runs the program with the
argument “6”), bt
.
Mac OS X gdb may report Function "printf" not defined.
This is
because the dynamic library that contains printf
is loaded on
demand. Try running the program first with r
; then you can set the
breakpoint. Or use lldb.
After-class work
Try out the self-check comprehension questions and, optionally, hunt for more treasure.
Self-check comprehension questions
You may have found some treasure by guessing. Go back and try to understand why your command lines generate treasure.
You should also be able to answer these questions, or at least to figure out how they could be answered.
- What is the hexadecimal representation of
ints[0]
? Ofints[1]
? - Can you explain why
./treasure 4 6
and./treasure 4 8
produce different results? You may need to read several manual pages, such asman system
. - What algorithm does
./treasure 9
run? That is, can you give a concise description of the result of./treasure 9 A B
? - What algorithm does
./treasure 10
run? That is, can you give a concise description of the result of./treasure 10 N
? - Use
gdb
or another debugger to explore the contents of memory. Can you predict the result of./treasure 3 1 0 16
usinggdb
? - Use
objdump
(on Mac with Homebrew,brew install binutils
, and call itgobjdump
) to explore the contents of the./treasure
executable. Can you predict the result of./treasure 3 2 0 16
usingobjdump
? (The-d
,-S
, or-s
options might be useful.)
Post-Class Survey
Please complete this survey before leaving class!
In-class Exercise FAQ
Extension students: after class, we will record any common problems that stumped people during the in-class exercises and put them in a FAQ that accompanies the exercises. We recommend that you first try the exercises, and then, if you get stuck, check the FAQ.