- Become more familiar with working and converting numbers in binary.
- Learn how to compile and run a C program on the EECS instructional computers
- Examine different types of control flow in C
- Introduce you to the C debugger
- Gain some practical experience using gdb to debug C programs
- Get more comfortable working with pointers
Checkoffs: Refer to lab0 for checkoff policies. Have the following open and ready to show to the TA or lab assistant. Doing this before asking for a checkoff will speed up the checkoff process.
- The file
The output from running the
- The file
The output from running the
Getting the files
As stated in the last lab, starter code for labs will be distributed through the fa18-lab-starter. If you are cloning your base 61c-student repository, you will need to add the starter code repository again using the following command while in your cloned git repo:
$ git remote add starter https://github.com/61c-teach/fa18-lab-starter.git
If you already have the starter repo remote added or have just set it up, then you will want to grab the new lab files via:
$ git fetch starter $ git merge starter/master
A merge prompter will show up and for those that are unfamiliar with vim, simply type ':wq' and hit enter.
You should now have a file called
lab01 in your personal repository, ready to make changes!
Now, go back to your personal lab repository, and type in the following command:
$ git remote -v
And make sure that you have both origin and starter remotes:
$ origin https://github.com/61c-student/fa18-lab-[username].git (fetch) $ origin https://github.com/61c-student/fa18-lab-[username].git (push) $ starter https://github.com/61c-teach/fa18-lab-starter.git (fetch) $ starter https://github.com/61c-teach/fa18-lab-starter.git (push)
If you would like to work on your local machine (your own computer, without ssh), there are two methods of doing this:
Setting up your git repository locally.
cdinto your desired folder and pull your repository into your local computer, then you can add the starter repo remote as above:
$ git clone [your github respotory url].git
Then, in order to move things from your remote/local machine, you can first commit your changes on whatever machine the changes are on, then run:
$ git push origin master
Then, on the other machine (swap machines) you can run:
$ git pull origin master
Using secure copy protocol (scp)
scpallows you to transfer files/folders via ssh.
From your local machine, type in the following:
$ scp -r cs61c-XXX@hiveYY.cs.berkeley.edu:~/[hive path to lab] ~/[local path to the lab]Replace local path to lab with the path to your
fa18-lab-[username]folder and hive path to the lab with the directory to where you wanna put it, for example:
$ scp -r cs61c-XXX@hiveYY.cs.berkeley.edu:~/labs/fa18-lab-[username] ~/CS61C
Then, if you wanna copy the files back to your remote after you've worked on the lab locally, swapping the arguments:
$ scp -r ~/[local path to the lab] cs61c-XXX@hiveYY.cs.berkeley.edu:~/[hive path to lab]
Exercise 1: Binary Alphabet
Let's take 4-bit numbers. If we stack five 4-bit numbers on top of each other in binary, we can make patterns and pictures! To help visualize this, you can think of 0's and 1's as white and black instead. For example, what does the following bit pattern look like?
- What five decimal digits produce the pattern above? What five hexadecimal digits?
- What letter is drawn with 1,1,9,9,6? 0xF8F88?
- What is the hexadecimal representation you would use to spell the letter 'B'? 'N' (you probably won't want to use 5 hex digits for this one)?
Wait! Before asking for a checkoff, make sure you have completed all FIVE exercises and their checkoff questions before putting your name down!
Compiling and Running a C Program
In this lab, we will be using the command line program
gcc to compile programs in C. The simplest way to
gcc is as follows:
$ gcc program.c
program.c into an executable file
a.out. If you've taken CS61B or have
experience with Java, you can kinda think of
the C equivalent of
javac. This file can be run
with the following command:
The executable file is
a.out, so what is
./? Answer: when you want to execute an
executable, you need to prepend a filepath in order to
distinguish your command from a command like
python3. The dot refers to the "current directory."
Incidentally, double dots (
..) would refer to the
directory one level up.
gcc has various command line options which you are
encouraged to explore. In this lab, however, we will only be
-o, which is used to specify the name of the
executable file that
gcc creates. Using
-o, you would use the following commands to compile
program.c into a program named
and then run it. This is helpful if you don't want all of your
executable files to be named
$ gcc -o program program.c $ ./program
Exercise 2: Simple C Program
In this exercise, we will see an example of preprocessor macro definitions. Macros can be a messy topic, but in general the way they work is that before a C file is compiled, all macro constant names are replaced exactly with the value they refer to.
In the scope of this exercise, we will be using macro
definitions exclusively as global constants. Here we define
CONSTANT_NAME to refer to
(an integer literal). Note that there is only a space
separating name from value.
#define CONSTANT_NAME literal_value
Now, look at the code contained in
Notice the four different examples of basic C control
flow. (What are they?)
First compile and run the program to see what it does. Play
around with the constant values of the four macros:
V3. See how changing
each of them changes the program output.
Your task: Modifying only these four values, make the program produce the following output.
$ gcc -o eccentric eccentric.c $ ./eccentric Berkeley eccentrics: ==================== Happy Happy Happy Yoshua Go BEARS!
There are actually several different combinations of macros
that can give this output. Here's the challenge for you in this
exercise: consider what the minimum number of distinct
V3 can have
such that they still give this exact output. For example, the
theoretical maximum is four, when they are all distinct from
- Explain the changes you made.
- Explain the minimum number of distinct values needed for the preprocessor macros.
- What does the -o flag do with
Exercise 3: Debugger
What is a debugger?
This section is intended for students who aren't familiar with what debuggers are. A debugger, as the name suggests, is a program which is designed specifically to help you find bugs, or logical errors and mistakes in your code (side note: if you want to know why errors are called bugs, look here). Different debuggers have different features, but it is common for all debuggers to be able to do the following things:
- Set a breakpoint in your program. A breakpoint is a specific line in your code where you would like to stop execution of the program so you can take a look at what's going on nearby.
- Step line-by-line through the program. Code only ever executes line by line, but it happens too quickly for us to figure out which lines cause mistakes. Being able to step line-by-line through your code allows you to hone in on exactly what is causing a bug in your program.
For this exercise, you will find the
GDB reference card
useful. GDB stands for "GNU De-Bugger." Compile
the "-g" flag:
$ gcc -g -o hello hello.c
This causes gcc to store information in the executable program for gdb to make sense of it. Now start the debugger, (c)gdb:
$ cgdb hello
Notice what this command does! You are running the program
cgdb on the executable file
hello generated by
gcc. Don't try
running cgdb on the source code in
won't know what to do.
If cgdb does not work, you can also use gdb to complete the
following exercises (start gdb with
The cgdb debugger is only installed on your cs61c-XXX accounts.
Please use the hive machines or one of the computers in 27x Soda
to run cgdb, since our version of cgdb was built for Ubuntu.
Task: step through the whole program by:
- setting a breakpoint at main
- using gdb's run command
- using gdb's single-step command
help from within gdb to find out the commands
to do these things, or use the reference card.
Look here if you see an error message like
printf.c: No such file or directory. You probably
stepped into a
printf function! If you keep
stepping, you'll feel like you're going nowhere! CGDB is
complaining because you don't have the actual file where
printf is defined. To free
yourself, use the command
finish to run the program until the current frame
returns (in this case, until printf is finished). And
NEXT time, use
next to skip over the line
Note: cgdb vs gdb
In this exercise, we use cgdb to debug our programs. cgdb is identical to gdb, except it provides some extra nice features that make it more pleasant to use in practice. All of the commands on the reference sheet work in gdb.
In cgdb, you can press
ESC to go to the code window
i to return to the command window
(bottom) — similar to
vim. The bottom command
window is where you'll enter your gdb commands.
Task: Learn MORE gdb commands
Learning these commands will prove useful for the rest of this lab, and your C programming career in general. Create a text file containing answers to the following questions (or write them down on a piece of paper, or just memorize them if you think you want to become a GDB pro).
- How do you pass command line arguments to a program when using gdb?
- How do you set a breakpoint which only occurs when a set of conditions is true (e.g. when certain variables are a certain value)?
- How do you execute the next line of C code in the program after stopping at a breakpoint?
- If the next line of code is a function call, you'll execute the whole function call at once if you use your answer to #3. (If not, consider a different command for #3!) How do you tell GDB that you want to debug the code inside the function instead? (If you changed your answer to #3, then that answer is most likely now applicable here.)
- How do you resume the program after stopping at a breakpoint?
How can you see the value of a variable (or even
an expression like
1+2) in gdb?
- How do you configure gdb so it prints the value of a variable after every step?
- How do you print a list of all variables and their values in the current function?
- How do you exit out of gdb?
- Set the breakpoint at main, and show your TA how you run up to that breakpoint.
- Show your TA your text document containing the additional gdb commands (or verbally recite them, whatever is easier).
Exercise 4: Debugging a buggy C program with GDB
You will now use your newly acquired gdb knowledge to debug a
short C program! Consider the program
Compile and run the program, and experiment with it. By
default, it will give you the following result:
$ gcc -g -o ll_equal ll_equal.c $ ./ll_equal equal test 1 result = 1 Segmentation fault
Figure out what's causing that segmentation fault!
Start gdb on the program, following the instructions for
compilation in exercise 1. We recommend setting a breakpoint in
ll_equal() function. When the debugger stops at
the breakpoint, try stepping through the program to see if you
can figure out what's causing the error.
Hint 1: run
bt after the program crashes in gdb. It will output the program trace.
Hint 2: pay attention to the values of the pointers
b in the function (print them!).
Are they always pointed to the right address?
Hint 3: Look at the source code in
main to see the
structure of the nodes and what exactly is being passed into
- Explain the bug and your fix to the function.
Exercise 5: "Debugging" a C program that requires user input
Let's see what happens if your program requires user input and
you try to run GDB on it. First, run the program defined by
to talk to an overly friendly program.
$ gcc -g -o int_hello interactive_hello.c $ ./int_hello
Now, we're going to try to debug it (even though there really are no bugs).
$ cgdb int_hello
What happens when you try to run the program to completion?
We'll be learning about a tool to help us avoid this situation. The purpose of this exercise is to make you unafraid of running the debugger even when your program needs user input.
It turns out that you can send text to
the file stream read by the function
fgets in this
program, with some special characters right from the
command line. Take a look at "redirection" on
and see if you can figure out how to send some input to the
program without explicitly providing it while it's running
(which gets you stuck in CGDB).
Look at this stackoverflow post for more inspiration.
Hint 1: If you're creating a text file containing your input, you're on the right track!
Hint 2: Remember you can run things with command line args (including the redirection symbols) from CGDB as well!
Demonstrate how you run CGDB to completion on the
executable created by compiling
interactive_hello.cwithout getting stuck.
Hopefully you appreciate how redirection helped you avoid that nasty situation with CGDB. Don't ever be afraid of the debugger!
Exercise 6: Pointers and Structures in C
Here's one to help you in your interviews. In
complete the function
ll_has_cycle() to implement
the following algorithm for checking if a singly-linked list
has a cycle.
Start with two pointers at the head of the list. We'll
call the first one
tortoiseand the second one
hareby two nodes. If this is not possible because of a null pointer, we have found the end of the list, and therefore the list is acyclic.
tortoiseby one node. (A null pointer check is unnecessary. Why?)
- If tortoise and hare point to the same node, the list is cyclic. Otherwise, go back to step 2.
After you have correctly implemented
the program you get when you compile
will tell you that
ll_has_cycle() agrees with
what the program expected it to output.
Hint: There are two common ways that students usually write this function. They differ in how they choose to encode the stopping criteria. If you do it one way, you'll have to account for a special case in the beginning. If you do it another way, you'll have some extra NULL checks, which is OK. The previous 2 sentences are meant to urge you to not stress over cleanliness. If they don't help you, just ignore them. The point of this exercise is to make sure you know how to use pointers.
Here's a Wikipedia article on the algorithm and why it works. Don't worry about it if you don't completely understand it. We won't test you on this.
By the way, the pointers are called "tortoise" and "hare" because the tortoise pointer is incremented slowly (like a tortoise, which moves slowly) and the hare pointer is incremented quickly (twice as fast as the tortoise; like a hare, which moves quickly).
As a closing note, the story of the tortoise and the hare is always relevant, especially in CS61C. Writing your C programs slowly and steadily, using debugging programs like CGDB, is what will win you the race.
ll_has_cycle()function to the TA.