Deadline: End of lab session Thursday, July 11th

- The student will be able to run and debug RISC-V assembly code.
- The student will write RISC-V functions using the right calling procedure.
- The student will get an idea of how to translate C code into RISC-V.

Pull the lab files from the lab starter repository with

```
git pull staff master
```

For this exercise, you will complete `bit_ops.c`

by implementing the bit manipulation functions `get_bit`

, `set_bit`

, and `flip_bit`

(shown below). You may only use bitwise operations such as and (&), or (|), xor (^), not (~), left shifts («), and right shifts (»). You may not use any for/while loops or conditional statements.

```
// 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);
```

**ACTION ITEM**: Finish implementing `get_bit`

, `set_bit`

, and `flip_bit`

.

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.

In this exercise, you will be implementing a function `factorial`

in RISC-V that has a single integer parameter `n`

and returns `n!`

. A stub of this function can be found in the file `factorial.s`

. You can paste its contents into the Venus editor to open it in Venus. You will only need to add instructions under the `factorial`

label, and the arguments that are passed into the function are defined at the top of the file. You may solve this problem using either recursion or iteration.

Implement `factorial`

and make sure that the program correctly outputs `3!`

, `6!`

, `7!`

, and `8!`

. In other words, the output should be

```
6 720 5040 40320
```

Make sure you are comfortable with the following.

- You should understand the structure for calling (and returning from) functions in RISC-V.

`map`

This exercise uses the file `list_map.s`

. You can paste its contents into the Venus editor to open it in Venus.

In this exercise, you will complete an implementation of `map`

on linked-lists in RISC-V. Our function will be simplified to mutate the list in-place, rather than creating and returning a new list with the modified values.

You will find it helpful to refer to the RISC-V green card to complete this exercise. If you encounter any instructions or pseudo-instructions you are unfamiliar with, use this as a resource.

Our `map`

procedure will take two parameters; the first parameter will be the address of the head node of a singly-linked list whose values are 32-bit integers. So, in C, the structure would be defined as:

```
struct node {
int value;
struct node *next;
};
```

Our second parameter will be the **address of a function** that takes one int as an argument and returns an int. We’ll use the `jalr`

RISC-V instruction to call this function on the list node values.

Our `map`

function will recursively go down the list, applying the function to each value of the list and storing the value returned in that corresponding node. In C, the function would be something like this:

```
void map(struct node *head, int (*f)(int))
{
if(!head) { return; }
head->value = f(head->value);
map(head->next,f);
}
```

If you haven’t seen the `int (*f)(int)`

kind of declaration before, don’t worry too much about it. Basically it means that `f`

is a pointer to a function, which, in C, can then be used exactly like any other function.

There are exactly nine (9) comments (8 in `map`

and 1 in `main`

) in the provided code where it says `YOUR CODE HERE`

.

Complete the implementation of `map`

by filling out each of these nine markers with the appropriate code. For the lab, provide a sample call to `map`

with `square`

as the function argument. There are comments in the code that explain what should be accomplished at each marker. When you’ve filled in these instructions, running the code should provide you with the following output:

```
9 8 7 6 5 4 3 2 1 0
81 64 49 36 25 16 9 4 1 0
```

The first line is the original list, and the second line is the modified list after the mapped function (in this case `square`

) is applied.

At this point, you should be comfortable with the following.

- You should know how to write some RISC-V functions without having a corresponding C function as a template.
- You should understand the CALLEE/CALLER conventions for the named registers, and why these conventions exist.

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:

- 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 0, 2, 3, and 5.
- The curved head-light shaped object is an XOR, which takes two inputs (a, b) and outputs a^b.
- If you implemented
`lfsr_calculate()`

correctly, it should output all 65535 positive 16-bit integers before cycling back to the starting number. - Note that the leftmost bit is the MSB and the rightmost bit is the LSB.

**ACTION ITEM**: Implement `lfsr_calculate()`

, compile `lfsr`

and run it. Verify that the output looks like 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 1:

- Show your TA/AI the output of running
`bit_ops`

.

Exercise 2 and 3:

- Make sure your assembly code is saved to the corresponding files in your
`lab03`

folder. Run`make`

in your lab03 folder on the Hive machine and show your TA/AI that it passes both checks (you should see two`Success!`

lines in your output).

Bonus Exercise:

- Show your TA/AI the output of running
`lfsr`

.