Goals
These exercises are intended to give you more practice with function calling (in particular, what goes onto the stack) and with pseudo instructions.
Setup
To obtain the lab06 files, pull from the git repo at ~cs61c/labs/fa13/06
. For example:
$ mkdir ~/lab06 $ cd ~/lab06 $ git init $ git pull ~cs61c/labs/fa13/06 master
You can use MARS to edit/run/test the code in this lab. If you don't remember how to use MARS, take a look at Lab 5.
Exercises
Exercise 1
This exercise uses the file listmanips.s
.
In this exercise, you will complete an implementation of map
in MIPS. Our function will be simplified to mutate the list in-place, rather than creating and returning a new list with the modified values. 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 jalr
(see below) 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 nodes, storing the value returned in that node. In C, this 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, basically it means that f
is a pointer to a function, which in C is used exactly like any other function.
You'll need to use an instruction you might not have learned before to implement this: jalr
. jalr
is to jr
as jal
is to j
. It jumps to the address in the given register and stores the address of the next instruction (i.e., PC+4
) in $ra
. So, if I didn't want to use jal
, I could use jalr
to call a function like this:
# I want to call the function garply, but not use jal. la $t0 garply # so I use la to load the address of garply into a register ($t0) jalr $t0 # and then use jalr to jump and link to it.
There are 7 places (6 in map
and 1 in main
) in the provided code where it says "YOUR_INSTRUCTION_HERE". Replace these with instructions that perform as indicated in the comments to finish the implementation of map
, and to provide a sample call to map
with square
as the function argument. When you've filled in these instructions, running the code should provide you with the following output:
List Before: 9 8 7 6 5 4 3 2 1 0 List After: 81 64 49 36 25 16 9 4 1 0
Checkoff
- Show your TA your test run.
Exercise 2
Add the prologue and epilogue to the code in nchoosek.s
so that it computes "n choose k". the number of combinations of n
distinct elements taken k
at a time. (This is also the (n,k)
entry in Pascal's triangle.)
Checkoff
- Show your TA your code and its test run.
Exercise 3
The following instructions are pseudo instructions. Convert each pseudo instruction into one (or two) real instructions
# load address (addr is a label) la $s0, addr # copy value move $s1, $s0 # set to bitwise inverse not $s1, $s1 # load immediate li $s2, 0xAABBCCDD li $t0, 5 li $t1, 4 # multiply mul $s0, $t0, $t1 # divide div $s0, $t0, $t1 # remainder rem $s0, $t0, $t1 # 0x00000000 operation (does nothing) nop
Checkoff
- Show your TA the converted instructions.
Exercise 4
Write two versions of a function named first1pos
(starting from first1pos.s) that, given a value in $a0, returns in $v0 the position of the leftmost bit in the word in $a0. If $a0 contains 0, store -1 in $v0. You are allowed to modify $a0 in the process of finding this position, but if you modify registers such as $ra, $s0...$s7, etc, make sure to save and restore them. Positions range from 0 (the rightmost bit) to 31 (the sign bit).
One of your solutions should repeatedly shift $a0, checking the sign bit at each shift. The other should start a mask at 0x80000000 and repeatedly shift it right to check each bit in $a0. You can test the code by running it, and it will print the results.
Checkoff
- Show your TA both versions of the function and its test run.