CS61C $ummer 2017 Lab 5 - Bitwise Floating Point and more MIPS


Hi everyone, we are going to be trying out the online queue that CS61A uses for their lab checkoffs and office hours and stuff. Please verify that you are able to log in to this website: http://61c-queue.app.cs61a.org. If not, please fill out the form linked at the very bottom of this Piazza post, and raise your hand to request checkoffs today! Thanks!

Hello, gorgeous. Whoa there, when's the last time you had to tell your lab instructions that they were being too forward?

Welcome to Lab 5. It's been a while since you've been here, huh? Since that's the case, why don't we have a look at not one but TWO images of the day! I really hope these make you smile :)

Bonus: Describe, in one sentence, what the similarity between these two images is.


Setup, literally copied and pasted from last time

Copy the lab files from the instructional servers to your lab account with

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

Alternatively, secure-copy (scp) them from the instructional servers to your own laptop with

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

And if you want to secure-copy them back to your class account:

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

Exercise 1: float_bit_ops.c

Recall how single-precision floats are organized on a bitwise level, roughly like this:


There are 8 bits for the exponent, which is in biased notation, 23 bits for the mantissa, and a sign bit. Today, we're going to be doing stuff to floats on a bitwise level using this information.

Task: Complete make_float in float_bit_ops.c.

You should just write an expression to replace the comment, which reads, exactly, /* YOUR CODE HERE */. Here is some useful information about the arguments that you should read:

WARNING: If you look closely at this function, you'll notice that we are trying to create a unsigned variable with some bit manipulations, storing its address inside a float*, and dereferencing this float* to get the value of the desired float. THIS IS VERY BAD PRACTICE IN GENERAL, but you should recognize why this allows us to achieve our goal.

Here's a nontrivial fact which you should try to process: the value of the dereference operation depends on the declared type of what is being dereferenced. Since we need to construct the float as an unsigned type (because bit operations are undefined on floats), to interpret the bits as a floating point number, we need to cast its address as a float* so that dereferencing ptr_to_result gives us a floating point number. This practice should rarely be used in real C code.

Task: Complete lg_step_size in float_bit_ops.c.

Let's define the "step size" of a floating point number to be the answer to the following question: By how much would the value of this float increase if we incremented its mantissa by 1?

Your job is to calculate the base 2 logarithm of the step size of a given float using bit operations. I'll be lenient: for this exercise, you ARE allowed to use the + and - (addition and subtraction) operators, but the core of your function should still be bit operations!

Notice again, that in the skeleton code, I've pulled some shenanigans with casting the address of x to an unsigned*. I highly suggest that you adhere to this (read: don't delete that given line of code).

BIG FAT HINT: The step size is a function of the exponent field. If you don't believe me, check out this link on floating point, fix an exponent field, hit that "+1" button, and check out by how much the value of the float goes up. Now change the exponent field and do the same thing. Yeah, I know. Mindblowing.

Nitpicky hint: What is the step size of denorms?

I'll give you one example: If my number *x is 1.0, that's (-1)^0 * (1.0) * (2^0). If I incremented the mantissa by 1, the float would change to (-1)^0 * (1.000....01) * (2^0) = 1 + 2^-23. So I incremented the value by 2^-23, which is therefore the step size. The base 2 logarithm of this is -23, so lg_step_size(x) should output -23. Are we clear?

To test your implementation, compile and run float_bit_ops.c.

$ gcc -o fbops float_bit_ops.c
$ ./fbops

Checkoff [1/3]

Exercise 2: Debugging megalistmanips.s

A long time ago, your TA Alex was a MIPS rookie, and he wrote his solution to a lab exercise inside megalistmanips.s. You, a MIPS expert, are tasked with fixing Alex's bugs.

Task: Find the mistakes inside the map function in megalistmanips.s. Before you do that, familiarize yourself with what this function is trying to do. It's a little different from last time.

Now, instead of having a linked list of ints, our data structure is a linked list of int arrays. Remember that when dealing with arrays in structs, we need to explicitly store the size of the array. In C code, here's what the data structure looks like:

struct node {
    int *arr;
    int size;
    struct node *next;

Also, here's what the new map function does: it traverses the linked list and for each element in each array of each node, it applies the passed-in function to it, and stores it back into the array.

void map(struct node *head, int (*f)(int)) {
    if (!head) { return; }
    for (int i = 0; i < head->size; i++) {
      head->arr[i] = f(head->arr[i]);
    map(head->next, f);

The task: read all of the commented lines under the map function in megalistmanips.s (before it returns with jr $ra), and make sure that the lines do what the comments say.

Some hints:

Checkoff [2/3]

Thanks for doing that exercise! I'm sure Alex is wondering where you were to help him when he was writing his misguided MIPS way back when...

Exercise 3: Write a function without branches

Consider the discrete-valued function f defined on integers in the set {-3, -2, -1, 0, 1, 2, 3}. Here's the function definition:

I'm not going to lie: this is a pretty dumb function. Nonetheless, your task is to implement it in MIPS, with the condition that your code may NOT use any branch instructions! In case you weren't counting, this is the 3rd consecutive lab in which your rights have been taken away. I wonder when they're going to stop the person in charge of these labs...

Luckily, somebody has randomly left an array of integers in the .data section of discrete_fn.s. How can you use this to your advantage and complete this seemingly impossible task?

Checkoff [3/3]

Obviously, the previous exercise was not something that was actually impossible. But it's the idea of working with what you have to accomplish as much as you can that I hope you can appreciate. I gave you the heavy burden of not using any branch instructions, and unfazed, you squeezed out as much functionality you could with what you had. As a related idea, think about floating-point numbers. Somebody was tasked with representing fractions in computers with 32 bits of information. Who could've imagined that with just these 32 bits, we could encode numbers with the razor-sharp precision of step sizes of very large negative powers of two and also also maintain a huge range of representable numbers? That's called being resourceful.

These are the kinds of situations that I hope you will be unafraid to tackle in your lives. The odds are against you, you're at a disadvantage, things seem impossible. But you can always do your best with what you have. I think that finding yourself in these situations is not misfortune. Rather, it is a blessing. Have you ever thought about why people like to root for the underdog? In my opinion, it's because as humans, we have a deep-seated desire to defy the expectations that we find placed on us. We don't like being told we can't do something, so it gives us joy to see someone go and completely shatter the mold, giving us hope that we can do the same. So, keep in mind that when the going gets tough for you, you have been given a chance to defy expectations, break the mold, whatever you want to call it. And by being the underdog, you will find support and encouragement from, failing all else, me, the CS61C Summer 2017 Lab 5 specifications. The only ones that will ever call you gorgeous.

Exercise 0b01000000011000000000000000000000: CALL pop quiz

Take a look at that function you just wrote, and notice what happens to the la instruction after you hit the assemble button.

Checkoff [3.5/3]