Week 06 Laboratory Exercises

Objectives

  • learning how function calls are implemented
  • practicing MIPS memory access
  • practicing calculating array indices
  • practicing using MIPS control instructions (branch)
  • practicing running MIPS programs with spim, xspim or qtspim

Preparation

Before the lab you should re-read the relevant lecture slides and their accompanying examples.

Getting Started

Create a new directory for this lab called lab06, change to this directory, and fetch the provided code for this week by running these commands: 

mkdir lab06
cd lab06
1521 fetch lab06

Or, if you're not working on CSE, you can download the provided code as a zip file or a tar file.

Exercise — in pairs:
Create An addi Instruction

Your task is to add code to this function in addi.c:

// return the MIPS opcode for addi $t,$s, i
uint32_t addi(int t, int s, int i) {

    return 42; // REPLACE WITH YOUR CODE

}

The function addi is given the operands for a MIPS addi instruction . Add code so that it returns the opcode for that instruction.

The assignment 1 specifcation provides the general bit pattern for an addi instruction.

The reference implementation for assignment 1 can be used to print the opcode for a particular addi instruction, for example: 

1521 emu -p 'addi $17 $19 -3'
[00400024] 2271FFFD addi $17, $19, -3
./addi 17 19 -3
addi(17, 19, -3) returned 0x2271fffd
1521 emu -p 'addi $9 $27 42'
[00400024] 2369002A addi $9, $27, 42
./addi 9 27 42
addi(9, 27, 42) returned 0x2369002a

Use make(1) to build your code:

make    # or 'make addi'
Assumptions/Limitations/Clarifications

  • You may define and call your own functions if you wish.

  • You are not permitted to change the main function you have been given, or to change addi' prototype (its return type and argument types).

When you think your program is working, you can use autotest to run some simple automated tests: 

1521 autotest addi

When you are finished working on this exercise, you and your lab partner must both submit your work by running give: 

give cs1521 lab06_addi addi.c

Note, even though this is a pair exercise, you both must run give from your own account before Wednesday 01 January 00:00 to obtain the marks for this lab exercise.

Exercise — in pairs:
MIPS 2d array

In the files for this lab, you have been given lookup.s, a MIPS assembler program that reads 2 numbers and then prints 42.

Add code to lookup.s to make it equivalent to this C program: 

// Read 2 numbers and use them as indices into a 2d-array

#include <stdio.h>

int array[42][24] = {
    { 9, 4, 3, 2, 5, 1, 1, 4, 3, 1, 2, 6, 7, 5, 6, 2, 8, 1, 8, 3, 4, 1, 1, 1 },
    { 7, 3, 9, 6, 6, 2, 4, 8, 6, 8, 1, 9, 8, 2, 9, 5, 9, 8, 9, 9, 2, 3, 1, 1 },
    { 1, 4, 6, 5, 4, 2, 9, 5, 7, 9, 5, 6, 4, 1, 6, 9, 6, 1, 9, 3, 8, 3, 1, 2 },
    { 3, 3, 3, 9, 7, 3, 7, 1, 3, 2, 3, 7, 7, 3, 2, 5, 8, 1, 4, 2, 4, 5, 9, 4 },
    { 5, 7, 6, 9, 4, 2, 4, 9, 4, 7, 9, 2, 8, 1, 6, 2, 7, 4, 9, 7, 1, 9, 3, 5 },
    { 8, 3, 8, 9, 3, 4, 6, 2, 4, 1, 3, 3, 2, 1, 2, 4, 2, 7, 8, 6, 8, 6, 9, 9 },
    { 9, 5, 8, 9, 7, 5, 6, 6, 2, 9, 5, 1, 1, 8, 6, 8, 3, 4, 1, 1, 5, 9, 5, 2 },
    { 3, 2, 4, 1, 4, 8, 2, 8, 7, 6, 7, 8, 8, 3, 8, 2, 6, 5, 5, 5, 5, 9, 5, 3 },
    { 7, 1, 3, 9, 8, 8, 6, 3, 1, 7, 6, 5, 6, 9, 3, 8, 1, 5, 7, 6, 7, 7, 5, 6 },
    { 4, 6, 5, 7, 4, 1, 4, 7, 3, 5, 5, 7, 9, 6, 8, 4, 3, 1, 9, 9, 2, 6, 8, 9 },
    { 2, 3, 8, 5, 8, 8, 7, 1, 8, 1, 1, 8, 2, 2, 3, 9, 7, 6, 7, 9, 3, 2, 6, 5 },
    { 1, 4, 7, 4, 7, 7, 7, 7, 9, 9, 8, 9, 5, 5, 3, 3, 9, 5, 8, 7, 7, 6, 1, 7 },
    { 5, 3, 8, 7, 5, 6, 1, 9, 5, 6, 3, 3, 5, 9, 9, 5, 4, 1, 3, 8, 1, 1, 1, 4 },
    { 9, 8, 1, 7, 5, 1, 7, 4, 9, 7, 4, 8, 2, 5, 9, 3, 6, 3, 6, 3, 2, 7, 3, 2 },
    { 1, 6, 1, 4, 2, 9, 6, 1, 3, 2, 5, 7, 3, 9, 4, 4, 6, 5, 9, 8, 4, 5, 1, 4 },
    { 7, 7, 7, 2, 1, 6, 1, 3, 9, 4, 4, 6, 6, 6, 3, 9, 3, 8, 2, 8, 8, 4, 8, 7 },
    { 7, 8, 7, 9, 3, 5, 7, 1, 1, 4, 1, 4, 9, 6, 7, 3, 8, 5, 1, 7, 9, 2, 2, 2 },
    { 2, 4, 6, 5, 7, 3, 4, 6, 1, 7, 2, 5, 1, 7, 1, 2, 9, 6, 7, 8, 5, 4, 5, 7 },
    { 2, 4, 4, 9, 2, 8, 1, 9, 5, 9, 5, 9, 8, 3, 4, 7, 6, 7, 5, 2, 9, 9, 5, 5 },
    { 8, 4, 2, 6, 3, 8, 8, 3, 6, 3, 2, 4, 5, 1, 8, 6, 6, 4, 5, 8, 4, 6, 8, 5 },
    { 7, 7, 9, 8, 4, 1, 1, 3, 8, 8, 7, 6, 3, 8, 1, 2, 2, 4, 4, 5, 3, 5, 9, 9 },
    { 5, 7, 1, 7, 5, 5, 8, 1, 4, 6, 5, 7, 5, 9, 3, 7, 4, 8, 6, 4, 1, 6, 7, 1 },
    { 4, 5, 3, 3, 1, 2, 5, 3, 1, 5, 7, 6, 6, 2, 8, 8, 8, 3, 6, 3, 1, 2, 6, 3 },
    { 9, 5, 3, 4, 7, 2, 9, 9, 8, 6, 2, 5, 9, 3, 1, 8, 6, 9, 6, 3, 3, 2, 3, 3 },
    { 8, 6, 5, 3, 3, 7, 6, 3, 3, 9, 1, 4, 7, 5, 1, 6, 5, 1, 6, 8, 8, 1, 9, 7 },
    { 4, 7, 5, 9, 1, 7, 6, 9, 5, 2, 3, 7, 3, 8, 8, 3, 9, 8, 5, 6, 1, 6, 6, 9 },
    { 2, 8, 6, 9, 3, 3, 6, 9, 4, 5, 2, 6, 3, 8, 3, 9, 6, 7, 6, 5, 6, 8, 2, 6 },
    { 4, 8, 6, 4, 5, 3, 9, 4, 3, 4, 7, 9, 9, 4, 5, 8, 6, 6, 3, 4, 7, 1, 3, 4 },
    { 7, 4, 6, 7, 1, 9, 6, 2, 8, 4, 5, 6, 7, 6, 4, 1, 6, 3, 1, 2, 5, 9, 2, 1 },
    { 2, 8, 9, 1, 6, 5, 1, 7, 2, 3, 3, 5, 4, 8, 6, 1, 9, 8, 5, 8, 1, 4, 4, 7 },
    { 8, 8, 2, 9, 9, 4, 8, 8, 9, 2, 6, 4, 2, 8, 1, 2, 3, 3, 9, 5, 3, 1, 1, 1 },
    { 3, 9, 5, 7, 7, 9, 7, 3, 4, 2, 1, 8, 6, 3, 6, 9, 3, 3, 4, 2, 5, 1, 2, 3 },
    { 4, 4, 6, 4, 5, 8, 1, 7, 4, 4, 6, 6, 9, 7, 9, 4, 3, 6, 6, 4, 9, 8, 2, 6 },
    { 3, 8, 2, 2, 7, 4, 3, 8, 7, 4, 1, 6, 6, 2, 3, 5, 2, 1, 8, 4, 6, 4, 8, 6 },
    { 5, 2, 5, 6, 5, 9, 3, 3, 8, 1, 3, 8, 2, 9, 2, 8, 9, 7, 2, 7, 5, 5, 7, 7 },
    { 2, 7, 6, 4, 3, 2, 1, 4, 6, 3, 7, 5, 7, 7, 5, 6, 4, 6, 8, 2, 9, 3, 6, 1 },
    { 6, 4, 4, 6, 1, 4, 2, 6, 3, 7, 9, 9, 4, 4, 2, 1, 8, 1, 4, 4, 2, 7, 4, 9 },
    { 3, 8, 5, 2, 3, 9, 2, 4, 8, 9, 3, 3, 6, 2, 3, 3, 1, 8, 5, 8, 8, 5, 1, 9 },
    { 1, 5, 8, 1, 4, 9, 2, 4, 9, 5, 7, 6, 7, 4, 8, 9, 1, 3, 8, 6, 4, 4, 9, 9 },
    { 5, 6, 7, 8, 3, 2, 9, 1, 1, 7, 7, 6, 9, 7, 7, 7, 8, 8, 3, 3, 8, 9, 9, 1 },
    { 8, 2, 5, 9, 1, 1, 7, 6, 3, 6, 7, 7, 7, 2, 4, 5, 5, 2, 1, 1, 1, 7, 4, 3 },
    { 8, 9, 4, 5, 4, 6, 2, 5, 3, 7, 5, 1, 6, 7, 2, 8, 5, 6, 2, 2, 1, 7, 6, 2 },
};

int main(void) {
    int x, y;
    printf("Enter x: ");
    scanf("%d", &x);
    printf("Enter y: ");
    scanf("%d", &y);

    printf("%d\n", array[x][y]);

    return 0;
}

In other words, it should read 2 numbers and use them as array indices to print a value from a 2 dimensional array. For example: 

1521 spim -f lookup.s
Loaded: /home/cs1521/share/spim/exceptions.s
Enter x: 5
Enter y: 8
4
1521 spim -f lookup.s
Loaded: /home/cs1521/share/spim/exceptions.s
Enter x: 41
Enter y: 23
2
1521 spim -f lookup.s
Loaded: /home/cs1521/share/spim/exceptions.s
Enter x: 0
Enter y: 0
9
Assumptions/Limitations/Clarifications

You can assume both numbers read are valid array indices.

When you think your program is working, you can use autotest to run some simple automated tests: 

1521 autotest lookup

When you are finished working on this exercise, you and your lab partner must both submit your work by running give: 

give cs1521 lab06_lookup lookup.s

Note, even though this is a pair exercise, you both must run give from your own account before Wednesday 01 January 00:00 to obtain the marks for this lab exercise.

Exercise — in pairs:
MIPS Sieve

In the files for this lab, you have been given sieve.s.

Add code to sieve.s to make it equivalent to this C program: 

// Sieve of Eratosthenes
// https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
#include <stdio.h>
#include <stdint.h>

uint8_t prime[1000];

int main(void) {
    int i = 0;
    while (i < 1000) {
        prime[i] = 1;
        i++;
    }

    i = 2;
    while (i < 1000) {
        if (prime[i]) {
            printf("%d\n", i);
            int j = 2 * i;
            while (j < 1000) {
                prime[j] = 0;
                j = j + i;
            }
        }
        i++;
    }
    return 0;
}

Use the space in the data area to store the array prime. For example: 

1521 spim -f sieve.s
Loaded: /home/cs1521/share/spim/exceptions.s
2
3
2
3
5
7
11
13
17
19
23
...
971
977
983
991
997

When you think your program is working, you can use autotest to run some simple automated tests: 

1521 autotest sieve

When you are finished working on this exercise, you and your lab partner must both submit your work by running give: 

give cs1521 lab06_sieve sieve.s

Note, even though this is a pair exercise, you both must run give from your own account before Wednesday 01 January 00:00 to obtain the marks for this lab exercise.

Exercise — in pairs:
MIPS factorial

In the files for this lab, you have been given factorial.s. Add code to make it equivalent to this C program: 

// Recursive factorial function
// n < 1 yields n! = 1

#include <stdio.h>

int factorial(int);

int main(void) {
    int n = 0;
    printf("Enter n: ");
    scanf("%d", &n);
    int f = factorial(n);
    printf("%d! = %d\n", n, f);
    return 0;
}

int factorial(int n) {
    int result;
    if (n > 1) {
        result = n * factorial(n - 1);
    } else {
        result = 1;
    }
    return result;
}

For example:

1521 spim -f factorial.s
Loaded: /home/cs1521/share/spim/exceptions.s
Enter n: 5
5! = 120
1521 spim -f factorial.s
Loaded: /home/cs1521/share/spim/exceptions.s
Enter n: 7
7! = 5040
1521 spim -f factorial.s
Loaded: /home/cs1521/share/spim/exceptions.s
Enter n: 1
1! = 1

When you think your program is working, you can use autotest to run some simple automated tests: 

1521 autotest factorial

When you are finished working on this exercise, you and your lab partner must both submit your work by running give: 

give cs1521 lab06_factorial factorial.s

Note, even though this is a pair exercise, you both must run give from your own account before Wednesday 01 January 00:00 to obtain the marks for this lab exercise.

Challenge Exercise — individual:
MIPS Big Factorials

Create a MIPS program big_factorial.s which will calculate arbitrarily large factorials. For example: 

1521 spim -f big_factorial.s
Loaded: /home/cs1521/share/spim/exceptions.s
Enter n: 42
42! = 1405006117752879898543142606244511569936384000000000
1521 spim -f big_factorial.s
Loaded: /home/cs1521/share/spim/exceptions.s
Enter n: 112
112! = 197450685722107402353682037275992488341277868034975337796656295094902858969771811440894224355027779366597957338237853638272334919686385621811850780464277094400000000000000000000000000

When you think your program is working, you can use autotest to run some simple automated tests: 

1521 autotest big_factorial

When you are finished working on this exercise, you must submit your work by running give: 

give cs1521 lab06_big_factorial big_factorial.s

You must run give before Wednesday 01 January 00:00 to obtain the marks for this lab exercise. Note that this is an individual exercise, the work you submit with give must be entirely your own.

Submission

When you are finished each exercises make sure you submit your work by running give.

You can run give multiple times. Only your last submission will be marked.

Don't submit any exercises you haven't attempted.

If you are working at home, you may find it more convenient to upload your work via give's web interface.

Remember you have until Wednesday 01 January 00:00 to submit your work.

You cannot obtain marks by e-mailing your code to tutors or lecturers.

You check the files you have submitted here.

Automarking will be run by the lecturer several days after the submission deadline, using test cases different to those autotest runs for you. (Hint: do your own testing as well as runningautotest.)

After automarking is run by the lecturer you can view your results here. The resulting mark will also be available via give's web interface.

Lab Marks

When all components of a lab are automarked you should be able to view the the marks via give's web interface or by running this command on a CSE machine: 

1521 classrun -sturec