## EDIT: ONLINE QUEUE

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.

## Goals

- Manipulate the fields of floating point numbers in C.
- Catch Alex's MIPS errors.
- Do something impossible.
- Think about the idea of doing the impossible.

## 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:

|s|exponent|-------mantissa--------|

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:

`sign`is either 0 or 1`exponent`is a value between -127 and 128. If provided -127, assume that we're trying to create a denorm or the value 0. If provided 128, assume we're trying to create an infinity or a NaN. Otherwise, assume that`exponent`is the value which the user wishes to appear in the exponent of the number we're making. For example, if`exponent`is -5, assume that we're trying to create a float whose value is`(-1)^sign * (1.mantissa) * (2^exponent)`.`mantissa`is an unsigned number whose most significant bit is at most its 22nd bit (0-indexed).

__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]

- Explain your implementation of the two functions.
- Display the result of running the executable generated by compiling
`float_bit_ops.c`

## 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 `int`s, our data structure is a linked list of `int` arrays. Remember that
when dealing with arrays in `struct`s, 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**:

- Why do we need to save stuff on the stack before we call
`jal`? - What's the difference between
`addu $t0, $s0, $0`and`lw $t0, 0($s0)`? - Pay attention to the types of attributes in a
`struct node`!

#### Checkoff [2/3]

- Display the result of running the code in
`megalistmanips.s`.

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:

- f(-3) = 6
- f(-2) = 61
- f(-1) = 17
- f(0) = -38
- f(1) = 19
- f(2) = 42
- f(3) = 5

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]

- Display the result of assembling and running the code in
`discrete_fn.s`

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]

- In what part of CALL is the instruction broken down into two separate instructions?
- In what part of CALL are the immediate fields of those two separate instructions filled in?