Objectives

Know how function calling is done/managed in MIPS
Know how to assemble multiple files in MARS

Preamble

Begin by downloading the starter file and unzip its content to a folder of your choice. Once work done as requested in the exercises below, you can check the correctness of your implementations by running the following commands in the UN*X environment. (c.f. the previous lab ):

$ cd path/to/lab5
$ chmod +x run_test.sh     # <-- to do once only (makes sure you can execute the script run_test.sh)
$ ./run_tests.sh           # <-- execute this script each time you want to test your implementations 

Exercise 1 : (n_choose_k)

To comply with the calling convention in MIPS, add the prologue and the epilogue of the nchoosek() function in file nchoosek/impl.s. You only need to edit places in the code indicated with the marker ### YOUR CODE HERE ###. The function nchoosek() should compute the number of combinations of n distinct elements chosen k times. This can be done using factorials, but we will do it by looking for the entry (n, k) in the Pascal triangle.

Exercise 2 : (polynomial)

A translation of C code to the MIPS assembler is given below. Here, the main program calls the poly() function in a repetitive manner for values of i ranging from 2 to 4. The argument of the poly() function is passed in the register $a0 .

#
# Description:  Computes the polynomial x^4 + x^3 + 1, for x in range 2 to 4

# i  <->  $s0

    .text

main:   addi    $s1, $0, 4      # main(){
        addi    $s0, $0, 2      #
m_for:  add     $a0, $s0, $0    #   for (i=2; i<=4; i++) {
        jal     poly            #      result = poly(i);
                                #
        add     $a0, $v0, $0    #      printf("%d\n", result );
        addi    $v0, $0, 1      #        .
        syscall                 #        .
        addi    $a0, $0, '\n'   #        .
        addi    $v0, $0, 11     #        .
        syscall                 #        .
                                #
        addi    $s0, $s0, 1     #      i++;
        ble     $s0, $s1, m_for #  }
                                #
        addi    $v0, $0, 10     #     exit
        syscall                 #}      .

While respecting the MIPS calling convention, write in poly/impl.s the body of the function poly(int x) which computes the polynomial $x^4 + x^3 + 1$.

Hint: Consider defining a function pow(x, n) which will be called by the poly() function to compute $x^n$.

Exercise 3 : (linked list)

Consider a linked list described as below

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

In this exercise, you will complete the implementation of the map() function in map/impl.s. map() modifies the value fields of a linked list given as an argument. Modifications will be made in place (instead of creating and returning a new list with the modified values).

The map() function takes two parameters; the head-of-list pointer (i.e. the address of the first node in the list); and a function pointer which takes an int as argument and returns an int as output.

The map() function recursively traverses the list and applies the function given as a parameter to the value field of each node in the list. A C implementation of the map() function would be as follows:

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

The declaration int (*f)(int) simply means that f is a function pointer which, in C language, is used exactly like any other function (if you’re curious, check out this link to learn more about their use).

For your MIPS assembly implementation of the map() function, you will need to use the jalr instruction. This instruction allows you to jump to the address contained in the register given as a parameter and store the return address (i.e. the address of the instruction after jalr) in register $ra. In fact, the jalr instruction is to jr as jal is to j. For example, we can use the jalr instruction to call a function instead of jal as shown below:

# We would like to call the `garply` function, without using the `jal` instruction.
la $t0, garply 	# we use the `la` pseudo-instruction to load the address of `garply` into a register (here, $t0)
jalr $t0       	# then we use the `jalr` instruction for the function call.

The map/impl.s file contains 12 locations where it says ### YOUR CODE HERE ###. To complete the implementation of the map() function, insert MIPS instructions at these code locations according to the indications given in the adjacent comments.

Once your code is complete, running the program in MARS should produce a result similar to this one:

List Before: 9 8 7 6 5 4 3 2 1 0
List After: 81 64 49 36 25 16 9 4 1 0

Notes:

To run or test your code in MARS,

load the file map/impl_runner.s into MARS and toggle Settings | Assemble all files in directory in the menu,
comment in the code the line indicated by the marker # <<< Comment under MARS

Exercise 4 : (linked list – bis)

In the previous exercise, you completed a MIPS procedure that applied a function to each node in a linked list. Here you will work with a similar but slightly more complex version. That is, instead of having a linked list of ints, our data structure is now a linked list of arrays of ints.

Recall that, when we need to work with a dynamic array in C, we must explicitly store its size in a variable. Here is, in C language, what the structure of our linked list looks like:

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

Here is as well a C implementation that shows what the new map function does: for each node of the linked list, we iterate through each element of the dynamic array and apply a given function. The result of the function is stored in place overwriting the old value.

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);
}

Tasks to do:

Find and fix errors in map2d/impl.s. In this sense, take help from the commented lines in the source file and make sure that the MIPS instructions correspond to the indications given in the comments. Here are some hints:

Why do we need to save information to the stack before executing the jal instruction?
What is the difference between “add $t0, $s0, $0” and “lw $t0, 0($s0)”?
Pay attention to the attribute types in the struct node structure.

For reference, running the “corrected” program in MARS should give the following result:

List before:
2 7 8 1
6 3 8 4
2 7 4 3
2 3 4 7
6 7 8 9

List after:
6 56 72 2
42 12 72 20
6 56 20 12
6 12 20 56
42 56 72 90

Notes:

To run or test your code in MARS,

load the file map2d/impl_runner.s into MARS and toggle Settings | Assemble all files in directory in the menu,
comment in the code the line indicated by the marker # <<< Comment under MARS