CS61C Fall 2017 Lab 2 - Bitwise Number Manipulation and C Memory Management

Welcome to the THIRD LAB (or Lab #2 since zero-indexing).

This is the first lab in which you can start receiving late penalties for earlier labs. E.G. Lab 0 is now officially late and will be worth a maximum of 1 point! However, Lab 1 can be checked off for full credit still, but make to review course policies! Hope you all have had a great first couple weeks and without further ado... LET'S GO!

Goals

BEFORE YOU ASK FOR CHECKOFF: Have the following open and ready to show the TA or lab assistant. Doing this before asking for checkoff will speed up the checkoff process.

Setup

So remember that there are two ways to do these labs, remotely/on the hive or on your own local computer.

Option 1: The remote approach. Copy the contents of ~cs61c/labs/02 to a suitable location in your home directory ON YOUR CLASS ACCOUNT like so:

$ cp -r ~cs61c/labs/02/ ~/labs/02

This assumes you have logged on to a hive machine OR are ssh'd into a hive machine. From here, if you are also physically on the lab machines, you can edit the files with your favorite text editor on the lab machine. If you are working via ssh, however, you will have to use a command-line text editor such as vim. No vim guide will be provided here, but you can just Google search it.

Option 2: The local approach. Secure-copy (scp) the contents of ~cs61c/labs/02 on the lab machines onto a suitable location on your local machine.

$ scp -r cs61c-xxx@hive10.cs.berkeley.edu:~cs61c/labs/02 ~/YOUR_FILEPATH

WAIT!!! Did you make sure to replace xxx with your 3-letter login?

This will copy the folder containing the lab2 files onto ~/YOUR_FILEPATH on your local machine. From here, you can obviously edit them with your favorite text editor locally, BUT you may or may not be able to run the programs which this lab requires because they may or may not be installed on your computer. For example, most computer do not come with cgdb and Valgrind pre-installed, so you would have to install them to do the labs locally. These programs however are installed on the hive machines, which is why we generally want you to work on them.

Once you're done editing your lab files, you can secure-copy them back on to your lab account with:

$ scp -r ~/YOUR_FILEPATH/2 cs61c-xxx@hive10.cs.berkeley.edu:~/YOUR_LABACCT_FILEPATH

This will copy the folder ~/YOUR_FILEPATH/2 (which should contain the lab2 files) into ~/YOUR_LABACCT_FILEPATH on your class account.

Option 3: The hidden approach.There are some GUI-based solutions to work on the Hive machines remotely like X2Go and Cyberduck, and you can look up these programs and how to set them up online. Not quite sure how to set them up, but I'm sure there is a guide somewhere.

Exercise 1: Bit Operations

For this exercise, you will complete bit_ops.c by implementing the following three bit manipulation functions. You will want to use bitwise operations such as and (&), or (|), xor (^), not (~), left shifts (<<), and right shifts (>>). Avoid using any loops or conditional statements.

NO LOOPS OR CONDITIONAL STATEMENTS!!! That means WHILE you try to work through this exercise with your partner, you do not have the right to type the words if, else, while, for, switch, or anything else of that nature. Please do not try to trick us, all the staff members (hopefully) know what all of these words look like so if we see them, YOU SHALL NOT PASS.

Read this: n should be treated as a 0-indexed index into the bits of x starting from the right. e.g. the right-most bit is bit 0.

// Return the nth bit of x.
// Assume 0 <= n <= 31
unsigned get_bit(unsigned x,
                 unsigned n);

// Set the nth bit of the value of x to v.
// Assume 0 <= n <= 31, and v is 0 or 1
void set_bit(unsigned * x,
             unsigned n,
             unsigned v);

// Flip the nth bit of the value of x.
// Assume 0 <= n <= 31
void flip_bit(unsigned * x,
              unsigned n);

Hint for set_bit: The tricky part is not knowing what the bit is before. However, we do know that 0 | x = x, but can we use this to our advantage? Is it possible to make it zero?

Once you complete these functions, you can compile and run your code using the following commands.

$ make bit_ops
$ ./bit_ops

This will print out the result of a few limited tests.

Checkoff [1/3] We better not see any of those conditionals >:(!

Exercise 2: Linear feedback shift register

In this exercise, you will implement a lfsr_calculate() function to compute the next iteration of a linear feedback shift register (LFSR). Applications that use LFSRs are: Digital TV, CDMA cellphones, Ethernet, USB 3.0, and more! This function will generate pseudo-random numbers using bitwise operators. For some more background, read the Wikipedia article on Linear feedback shift registers. In lfsr.c, fill in the function lfsr_calculate() so that it does the following:

Hardware diagram (see explanation below)

Image photoshopped by Steven Ho.

Explanation of the above diagram

After you have correctly implemented lfsr_calculate(), compile lfsr.c and run it. Your output should be similar to the following:

$ make lfsr
$ ./lfsr
My number is: 1
My number is: 5185
My number is: 38801
My number is: 52819
My number is: 21116
My number is: 54726
My number is: 26552
My number is: 46916
My number is: 41728
My number is: 26004
My number is: 62850
My number is: 40625
My number is: 647
My number is: 12837
My number is: 7043
My number is: 26003
My number is: 35845
My number is: 61398
My number is: 42863
My number is: 57133
My number is: 59156
My number is: 13312
My number is: 16285
 ... etc etc ...
Got 65535 numbers before cycling!
Congratulations! It works!

Checkoff [2/3]

Exercise 3: Memory Management

This exercise uses vector.h, vector-test.c, and vector.c, where we provide you with a framework for implementing a variable-length array. This exercise is designed to help familiarize you with C structs and memory management in C. In other words, don't worry about the real-life practicalities of this wonky data structure. Just don't.

Your task is to fill in the functions vector_new(), vector_get(), vector_delete() and vector_set() in vector.c so that our test code vector-test.c runs without any memory management errors.

Here's how a vector_t works

It's time to look at the code in the vector.c if you haven't already. Here, additional comments in the code also describe how the functions should work. Again, the user of your vector_t data structure should be able to assume that all entries in the vector are 0 unless set by the user. Keep this in mind as malloc() does not zero out the memory it allocates.

Task: Look at the functions bad_vector_new() and also_bad_vector_new(). These creatively named functions are examples of bad ways to initialize structs in C. Be ready to discuss why this is the case.

Task: Complete vector_new(), the good version. There are exactly six (6) places for you to fill in with an expression in C. They are marked with a comment which says, exactly: /* YOUR CODE HERE */. Write an expression in these blanks. That means no more than one line of code. Additional comments describe what should happen in the line of code directly underneath.

Task: Complete vector_get() in the same manner as you completed vector_new(): respectfully, eager to learn, with an open mind, and consciously aware of what you are coding, as this is best practice.

Task: Complete vector_delete(). A sufficient solution to shouldn't take more than 2 lines of code.

Task: Complete vector_set(). This is the more involved one. Welcome to the big leagues. The problem with setting an arbitrary index/location in a vector v is that we might not have malloc'd enough space in v->data for it (yes, that means you should have mallocd space for v->data). Think about how you can allocate enough memory for that index/location, what you need to do with the old data, and what other things you need to do in your new block of data. Hint: recall that all unset indices/locations should be zero. There are a few different ways you can complete this function. Consider the 3 __alloc functions. They could all be useful here...

Using Valgrind

To help you to find memory bugs, we have installed a copy of Valgrind Memcheck. Valgrind is ONLY on the lab machines in the Hive and the Orchard. That means it PROBABLY isn't on your own computer. This program will run an executable while keeping track of what registers and regions of memory contain allocated and/or initialized values. The program will run much slower (by a factor of about 10 to 50) so that this information can be collected, but Valgrind Memcheck can identify many memory errors automatically at the point at which they are produced. You will need to learn the basics of how to parse the Valgrind output.

You can test your code in the following two ways:

// 1) to check functionality:
$ make vector-test
$ ./vector-test

// 2) to check memory management using Valgrind:
$ make vector-memcheck

The Makefile calls Valgrind as follows:

$ valgrind --tool=memcheck --leak-check=full --track-origins=yes [OS SPECIFIC ARGS] ./<executable>

If you look through this icky formatting, you'll realize that the basic format of using Valgrind is the same as how you used CGDB in the previous lab: you run it on the executable created by gcc EXCEPT that you need to also add the dot-slash in front of the executable.

The --track-origins flag attempts to identify the sources of unitialized values. The --leak-check=full option tries to identify memory leaks. [OS SPECIFIC ARGS] are simply a set of arguments to Valgrind that differ across operating systems (in our case, Ubuntu (Linux)). If you are interested in learning more about these, see the Makefile.

The last line in the Valgrind output is the line that will indicate at a glance if things have gone wrong. Here's a sample output from a buggy program:

==47132== ERROR SUMMARY: 1200039 errors from 24 contexts (suppressed: 18 from 18)

If your program has errors, you can scroll up in the command line output to view details for each one. For our purposes, you can safely ignore all output that refers to suppressed errors. In a leak-free program, your output will look like this:

==44144== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 18 from 18)

Again, any number of suppressed errors is fine; they do not affect us.

Feel free to also use a debugger or add printf statements to vector.c and vector-test.c to debug your code.

Checkoff [3/3]

Knowing how to allocate and free your memory is important for coding in C. Think of bad memory management like a parking lot. If cars are parked in the lot and the owners never leave, then you don't have any free spots for incoming cars. Thus, Valgrind is important because we know that we should have a completely unallocated heap by the end of our program.