Week 07 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

Set up for the lab by creating a new directory called lab07 and changing to this directory.
mkdir lab07
cd lab07

There are some provided files for this lab which you can fetch with this command:

1521 fetch lab07

If you're not working at CSE, you can download the provided files as a zip file or a tar file.

Exercise — individual:
Create An addi Instruction

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

// return the encoded binary MIPS 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 encoded binary form of the instruction.

The spim documentation guide provides the general bit pattern for an addi instruction, including the opcode and the bits used for each operand.

1521 spim2hex can be used to print the encoded binary form of a particular addi instruction as a hexadecimal, for example:

echo 'addi $17 $19 -3'|1521 spim2hex
2271fffd
./addi 17 19 -3
addi(17, 19, -3) returned 0x2271fffd
echo 'addi $9 $27 42'|1521 spim2hex
2369002a
./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 must submit your work by running give:

give cs1521 lab07_addi addi.c

You must run give before Monday 01 November 21: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.

Exercise — individual:
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
Enter x: 5
Enter y: 8
4
1521 spim -f lookup.s
Enter x: 41
Enter y: 23
2
1521 spim -f lookup.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 must submit your work by running give:

give cs1521 lab07_lookup lookup.s

You must run give before Monday 01 November 21: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.

Exercise — individual:
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
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 must submit your work by running give:

give cs1521 lab07_sieve sieve.s

You must run give before Monday 01 November 21: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.

Exercise — individual:
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
Enter n: 5
5! = 120
1521 spim -f factorial.s
Enter n: 7
7! = 5040
1521 spim -f factorial.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 must submit your work by running give:

give cs1521 lab07_factorial factorial.s

You must run give before Monday 01 November 21: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.

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
Enter n: 42
42! = 1405006117752879898543142606244511569936384000000000
1521 spim -f big_factorial.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 lab07_big_factorial big_factorial.s

You must run give before Monday 01 November 21: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 Week 8 Monday 21: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 running autotest.)

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