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!
- Manipulate the bits of numbers.
- Learn to control your newfound powers.
- Practice working with dynamic memory allocation (that malloc thing).
- Heap on all the extra memory.
- Introduce you to Valgrind, a utility for checking memory leaks.
- L O V E Valgrind.
- Think about how good heap memory management can make you a better person.
- Just kidding. Sorry, but it can only make you a better coder.
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.
- The file bit_ops.c
- The file lfsr.c
- The file vector.c and your TWO explanations for the versions of vector_new()
- Any other answers the checkoffs have you answer in text form or be ready to answer them promptly.
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 email@example.com:~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 firstname.lastname@example.org:~/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 >:(!
- Show and be ready to explain how you implemented get, set, and flip.
- Ensure that you did not use any conditionals.
- Show the output of running the 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)
Image photoshopped by Steven Ho.
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!
- Show and be ready to explain how you implemented your lfsr_calculate function.
- Show the output from running ./lfsr.
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...
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.
- For both of the "bad" versions of vector_new(), explain the flaws of the function.
- Walk through your modifications to vector.c.
- Show the output from running make vector-memcheck.
- How do you run valgrind in general?
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.