Lab 1: Bits, Bytes, and Integers

Lab sessions Tue Apr 06 to Thu Apr 08

Lab written by Julie Zelenski, with modifications by Nick Troccoli

Lab Overview

Your weekly lab is a chance to collaboratively experiment and explore, ask and answer questions, and get hands-on practice in a supported environment. You will work in small groups, and as a whole section, on a set of lab exercises that revisit topics from recent lectures/readings. We are all working together to advance our knowledge of the material! Use the time to further practice your skills, help others, ask questions, and explore. We have also designed labs specifically to prepare you for assignments - the more you put into exploring problems and concepts during labs, the more it will pay off when you start the next assignment!

Lab starts all together in the main lab room, where you'll get a chance to get to know others in your lab. Your TA will then assign you to groups to start working on the first problem together. After each problem, the TA will have everyone return to the main room to discuss the problem, what you found, and what questions you have. Then you'll return to your small group rooms to work on the next problem.

For lab each week, we plan to mine our favorite open-source projects (musl libc, BusyBox unix utilities, Apple, Google and more) for interesting systems code to use as an object of study. We use this code to learn how various programming techniques are used in context, give insight into industry best practices, and provide opportunities for reflection and critique.

Learning Goals

During this lab you will:

  1. practice with bits, bitwise operators and bitmasks
  2. read and analyze C code that manipulates bits/ints
  3. further practice with the edit-compile-test-debug cycle in the Unix environment

Lab Project

Clone the lab starter code by using the command below. This command creates a lab1 directory containing the project files.

git clone /afs/ir/class/cs107/repos/lab1/shared lab1

Exercises

1) Sharing Unix Joy (5 minutes)

Once you're in your assigned group room, introduce yourself to your fellow group-mates! How is everyone doing so far on getting comfortable in the Unix environment? What questions or tips do you have to share? Let's hear it!

In your shared lab document, write down (at least one) Unix/command-line video/resource/tip that your group wants to share with the rest of the lab. Prefix your idea with your group number and a fun name for your group--that way you'll remember it for next week, too!

2) Round Up (25 minutes)

Open the round.c file to review the is_power_of_2 and round_up functions. Try compiling and running the program as you explore it! (you can ignore the warning generated by the parity program for now).

  • is_power_of_2 is the same function we saw in lecture, that takes advantage of a unique bit-level property of powers of two. Review with your group what that property is, and what the relationship is between a power of two and its predecessor (e.g. number - 1) in terms of the bits the two values have in common.

  • The round_up function returns the value of the first argument (value) rounded up to the nearest multiple of the second (multiple). The first (non-power of 2) case works for every number, power of 2 or not, but if the number is a power of 2, we can implement a more efficient alternative, which we've done here.

Q1: For the first case (non-power of 2), how are the arithmetic operations used to round up to the next multiple? Hint: watch out for integer division!

Q2: For the special case (power of 2), how is bitwise manipulation able to take the place of the expensive multiply/divide portion of the first case?

These functions show the advantage of being able to flip between interpretations. A number is just a bit pattern and can be manipulated arithmetically or bitwise at your convenience.

3) Debugging parity.c (20 minutes)

Now it's your turn to write some bitwise code and practice with Unix tools!

The parity program reports the parity of its command-line argument. A value has odd parity if there are an odd number of "on" bits in the value, and even parity otherwise. Confirm your understanding by running the samples/parity_soln program on various arguments.

The code in parity.c was written by your colleague who claimed it is "complete", but on their way out the door they mutter something unintelligible about unfixed bugs. Uh oh... Your task is to test and debug the program using sanitycheck and the gdb debugger.

Let's investigate! Work with your group, but follow the steps individually as well - hands-on practice is the best way to become familiar with GDB!

A helpful GDB reference is the CS107 GDB guide, listed under "Handouts" in the top toolbar.

Open GDB Guide

  1. Compile the program using make (ignore the ominous warning for now...) and run ./parity a few times on various values. Uh oh! It thinks every value has odd parity!
  2. Run it under the debugger. Start gdb parity. We can use the list command to print out parts of the code GDB is examining. Use list compute_parity to print the compute_parity function and note the line number where it updates the result inside the loop.
  3. Set a breakpoint on that line so that when we run the program in GDB, GDB will pause before executing that line and await further instructions. You can add a breakpoint by typing break XXX where XXX is either a function name or line number.
  4. Start the program by entering the run command, followed by a command line argument (for the number to examine). GDB will start running the program and pause when it hits the breakpoint. Note that it pauses before it executes the line the breakpoint is on.
  5. When stopped at the breakpoint, print the value of result by using the p (short for print) command, followed by the name of what we want to print. Huh? The value of result appears to be garbage. D'oh, it was never initialized! Is that even legal? In a safety-conscious language such as Java, the compiler may guard against this.
  6. Do a make clean and make to review the build warnings - luckily in this case (but perhaps not always!), the compiler seems to catch the issue. At runtime, the variable will use whatever junk value was left over in its memory location. But, lesson learned -- you will need to up your own vigilance when working with C.
  7. Add a correct initialization, build, and re-run to test your fix.

Now, run sanitycheck on lab1 to see that your fixed parity passes all included tests. Looks good! However, sanitycheck is only as thorough as its test cases. We should continue testing.

  • Run custom sanitycheck (tools/sanitycheck custom_tests) with the additional test cases in custom_tests. One of these tests fails due to timeout. It's not that the program is horribly inefficient, it is just stuck in an infinite loop.
  • The best way to debug an infinite loop is to run the program under GDB, and once it stalls, stop the program using Control-c. GDB will show you where the program was executing when it was stopped, and you can poke around and see what is going on. Run the parity program in GDB on a negative argument and let it go unresponsive.
  • Type Control-c to interrupt it and return control to gdb. Use the gdb backtrace command to see where the program is executing - this will display the current call stack, meaning what functions are currently executing. step through a few statements as it goes around the loop and gather information to diagnose why the loop is not exiting.
  • Once you know what's gone wrong, edit the code to fix, rebuild, and test under both default and custom sanitycheck to verify you have squashed the bug. Way to go!
  • Discuss with your group; what caused the infinite loop in the parity program? Review your process for narrowing in on this bug.

[Optional] Extra Problems

Finished with lab and itching to further exercise your bitwise skills? Check out our extra problems!

Recap

Nice work during lab1! It's okay if you don't completely finish all of the exercises during lab; your sincere participation for the full lab period is sufficient for credit. However, we highly encourage you to finish on your own whatever is need to solidify your knowledge.

TODO: At this time, if you'd like to make a CS107 study group with your group members, we encourage you to exchange contact info!

Also take a chance to reflect on what you got what from this lab and whether you feel ready for what comes next! The takeaways from lab1 should be proficiency with bitwise operations, constructing and using bitmasks, and a solid grasp on the representation of unsigned values as a binary polynomial and signed values in two's complement. Here are some questions to verify your understanding and get you thinking further about these concepts:

  • Consider rounding the magnitude of an integer up to power of two (e.g. 3 rounds to 4, 4 to 4, 5 to 8, for negative: -3 rounds to -4, -4 to -4, and so on). How does the bit pattern of a positive int differ from the bit pattern of the value after rounding to power of two? What about for a negative int?
  • Give a bitwise expression to zero the upper N bits of an unsigned int V. What does this expression compute numerically?
  • When do you supply the command-line arguments to a program you wish to run under gdb: when starting gdb or from within gdb when running the program?
  • Chapter 2 of B&O has many excellent practice problems presented with solutions - check them out!

Just For Fun