Lab 1: Bits, Bytes, and Integers

Lab sessions Wed Oct 05 to Mon Oct 10

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, where you'll get a chance to get to know others in your lab. You'll then get into small groups to start working on the first problem together. After each problem, the TA will have everyone come back together to discuss the problem, what you found, and what questions you have. Then you'll return to your groups to work on the next problem.

To track lab participation, we have an online checkoff form for you to fill out as you work. Lab is not a race to find answers to exactly and only the checkoff questions-- the checkoff questions are used only to record attendance and get a read on how far you got. Lab credit is awarded based on your sincere participation for the full lab period. Your other rewards for investing in lab are to further practice your skills, work together to resolve open questions, satisfy your curiosity, and reach a place of understanding and mastery. The combination of active exploration, give and take with your peers, and the guidance of the TA makes lab time awesome. We hope you enjoy it!

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 and Checkoff

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

Next, pull up the online lab checkoff and have it open in a browser so you can jot things down as you go. Only one checkoff needs to submitted for both you and your partner.

Exercises

1) Sharing Unix Joy (5 minutes)

Once you're in your group, introduce yourself! 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!

2) Round Up (25 minutes + 10min all-lab discussion)

Learning Goal: observe how we can use bit operators to manipulate the binary representation of a number, and how a number is a bit pattern that can be manipulated arithmetically or bitwise at your convenience. Bit operators and understanding the connection between binary representation and arithmetic value is key to the first assignment!
Starter code file: round.c

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 (25 minutes + 10min all-lab discussion)

Learning Goal: become more comfortable with using GDB to investigate bugs. GDB is an essential tool to inspect the behavior of programs and narrow in on bugs by stepping through execution and printing out values. Familiarity with GDB will be a huge asset on assignments going forward!
Starter code file: parity.c

Tip: have the team member who is driving open 2 terminal windows and log into myth in each one - use one to run GDB, and another to open parity.c to view it while debugging!

Now it's your turn to write some bitwise code and practice with Unix tools! Before working on this problem, you'll want to read through a few slides, starting right here, about how << and >> operate. In particular, you'll want to quickly read how >> behaves differently when applied to signed integers instead of unsigned ones!

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 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. Run make clean (which removes the compiled progam file) and make (which re-creates a fresh compiled program file) - but you'll see no warnings about anything wrong from gcc. At runtime, the variable will use whatever junk value was leftover in its memory location. 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