CS61C $ummer 2017 Lab 2 - Bitwise (nitty-gritty) Number Manipulation and Practices of Good C Memory Management

WELCOME TO LAB 2. This text was bolded for no reason other than to get your attention. As the person in charge of the labs, I want to make you feel like lab is as much of a personalized learning experience as discussion and that we don't just mindlessly toss these exercises together for you. That's why I'm trying to make the tone of voice of the instructions sound more silly and human.

This is the image of the day. Now stop looking at pictures of cats and get to work.

Goals

• Deviously manipulate the internal representation of numbers.
• Practice working with dynamic memory allocation (that malloc thing).
• Introduce you to Valgrind, a utility for checking memory leaks.
• Think about how good heap memory management can make you a better person.

Setup

I heard some of you didn't know how to get the lab files onto your local machine. That was my bad for not explicitly giving you the commands to do so. Here's my rundown on your options to get the lab files. I will repeat these instructions on every single lab until you are literally sick of looking at them.

Option 1: the classic 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. I won't provide a vim guide here, but you can just Google search it.

Option 2: the "I want to do it on my own computer" 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

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. 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/02 cs61c-xxx@hive10.cs.berkeley.edu:~/YOUR_LABACCT_FILEPATH

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

Option 3: the "best of both worlds" 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. Unfortunately I've never used them, but I've heard that people generally like them.

Exercise 0: Bit Operation Basics (Optional)

You may skip this exercise if you're fluent in bit operations. In particular, if you know how the &, |, ^, ~, <<, and ^ operations work, you should skip this exercise.

Task: Look up how the above six operations work in C. Use your favorite search engine. Personally, I like Google, but here is a list of some esoteric ones.

Understanding check:

• Why is 0b1010 & 0b1100 equal to 0b1000?
• Why is 0b1010 | 0b1100 equal to 0b1110?
• Why is 0b1010 ^ 0b1100 equal to 0b0110?
• Why is ~0b1010 equal to 0b0101?
• Why is 0b0001 << 3 equal to 0b1000?
• Why is 0b1100 >> 2 equal to 0b0011?

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.

WHOA does that say no loops or conditional statements? Yes, indeed it does. 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. Sorry! Tell a staff member if you feel that your rights have been violated, and we'll respond not by giving you your rights back, but by giving you a hint to the exercise.

Read this: n should be treated as a 0-indexed index into the bits of x.

// 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: zero it out then shift v in. What is "it?" That's for you to figure out, my friend.

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.

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)

Explanation of the above diagram

• On each call to lfsr_calculate, you will shift the contents of the register 1 bit to the right.
• This shift is neither a logical shift or an arithmetic shift. On the left side, you will shift in a single bit equal to the Exclusive Or (XOR) of the bits originally in position 1, 3, 4, and 6.
• The curved head-light shaped object is an XOR, which takes two inputs (a, b) and outputs a^b.
• Unlike in exercise 1, the bit positions are now 1-indexed.

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!

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 has an int size describing how many components it currently has. In other words, its size is equal to the maximum index of the vector which has been set. For example, if I have a vector whose size is currently 5, and then I set its 200th (0-indexed) element to something, the size of that vector should update to 201. The default size of the vector returned by vector_new is 1.
• It has a int *data, a dynamically sized array of ints which hold the values of its components. If I set the 200th element of a vector v to 8, then the 200th (again 0-indexed) element of v->data should evaluate to 8. The value of the single component of the vector returned by vector_new should be 0.
• The value of any component of a vector that was not explicitly set is 0. If I asked for the 5th entry of a vector, but I had only set its 1st and 2nd entries, you would tell me that it's 0. Additionally, if you had a size 5 vector and I asked for its 7th element, you would tell me it's 0. You would not throw any kind of error.

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.

malloc is a powerful tool which you have at your disposal. You can think of it kinda like this: when you malloc some chunk of memory for yourself, you place a steel cage around it which signals to everyone else that you own it and no one else can touch it. While the steel cage is very helpful for maintaining your structs and arrays, you need to keep in mind that once you're done using it, it needs to be lifted (this is what free does). Otherwise, you'll have steel cages lying around all over your memory, preventing it from being used by anyone. This is wasteful and greedy and why we stress the importance of having no memory leaks in 61C. Likewise in real life, it's important to know how to properly use (and not abuse) our most powerful tools and to clean up after ourselves, whether it be in the environment, in your own home, in your own bed, or whatever. And that's where I'll halt this train of thought.

Exercise 3.5 (lol): How to get a 100% response rate on a survey

Task: Complete the Week 1 Feedback Form.