Week 04 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 mipsy and mipsy-web

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 lab04 and changing to this directory.

mkdir lab04
cd lab04

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

1521 fetch lab04

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

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>

#define N_ROWS 42
#define N_COLS 24

int array[N_ROWS][N_COLS] = {
    { 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 row, col;
    printf("Enter row: ");
    scanf("%d", &row);
    printf("Enter col: ");
    scanf("%d", &col);

    printf("%d\n", array[row][col]);

    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 mipsy lookup.s
Enter row: 5
Enter col: 8
4
1521 mipsy lookup.s
Enter row: 41
Enter col: 23
2
1521 mipsy lookup.s
Enter row: 0
Enter col: 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 lab04_lookup lookup.s

You must run give before Tuesday 08 October 12:00 (midday) (2024-10-08 12: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.

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 <string.h>

#define ARRAY_LEN 1000

char prime[ARRAY_LEN];

int main(void) {

    // Sets every element in the array to 1.
    // This has already been done for you
    // in the data segment of the provided MIPS code.
    memset(prime, 1, ARRAY_LEN);


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

    return 0;
}

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

1521 mipsy 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 lab04_sieve sieve.s

Exercise — individual:
MIPS Random Mathematics

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

void seed_rand(unsigned int);
int  rand(unsigned int);
int  add_rand(int);
int  sub_rand(int);
int  seq_rand(int);

#include <stdio.h>

int main(void)
{
    int random_seed;
    printf("Enter a random seed: ");
    scanf("%d", &random_seed);

    seed_rand(random_seed);

    int value = rand(100);
    value = add_rand(value);
    value = sub_rand(value);
    value = seq_rand(value);

    printf("The random result is: %d\n", value);

    return 0;
}

int add_rand(int value)
{
    return value + rand(0xFFFF);
}

int sub_rand(int value)
{
    return value - rand(value);
}

int seq_rand(int value)
{
    int limit = rand(100);
    for (int i = 0; i < limit; i++)
    {
        value = add_rand(value);
    }
    return value;
}

//////////////////////// PROVIDED CODE ////////////////////////

#define OFFLINE_SEED 0x7F10FB5B

int random_seed;

// seed the random number generator
// with the given seed value
void seed_rand(unsigned int seed)
{
    const unsigned int offline_seed = OFFLINE_SEED;
    random_seed = seed ^ offline_seed;
}

// return a random number between
// 0 and (n - 1) inclusive.
// *n must be greater than 0*
int rand(unsigned int n)
{
    unsigned int rand = random_seed;
    rand *= 0x5bd1e995;
    rand += 12345;
    random_seed = rand;
    return rand % n;
}

For example:

1521 mipsy mathematics.s
Enter a random seed: 1
The random result is: 1615324
1521 mipsy mathematics.s
Enter a random seed: 44
The random result is: 3601566
1521 mipsy mathematics.s
Enter a random seed: 345
The random result is: 455010

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

1521 autotest mathematics

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

give cs1521 lab04_mathematics mathematics.s

Exercise — individual:
MIPS class management system

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

// A simple program to manage student marks.
#include <stdio.h>

// Constants
#define CLASS_SIZE 6
#define UNKNOWN_MARK -1

struct student {
    int id;
    int mark;
};

struct student students[CLASS_SIZE] = {
    {5123456, UNKNOWN_MARK},
    {5308310, UNKNOWN_MARK},
    {5417087, UNKNOWN_MARK},
    {3456789, UNKNOWN_MARK},
    {5345678, UNKNOWN_MARK},
    {5234567, UNKNOWN_MARK},
};

struct student *find_student_by_id(int id) {
    for (int i = 0; i < CLASS_SIZE; i++) {
        if (students[i].id == id) {
            return &students[i];
        }
    }
    return NULL;
}

void update_student_mark(void) {
    int id;
    printf("Please enter the student ID: ");
    scanf("%d", &id);

    struct student *student = find_student_by_id(id);
    if (student == NULL) {
        printf("Student not found in class!\n");
        return;
    }

    printf("Please enter the student mark: ");
    scanf("%d", &student->mark);
}

void print_report(void) {
    printf("ID\tMark\n");
    for (int i = 0; i < CLASS_SIZE; i++) {
        printf("%d\t", students[i].id);

        if (students[i].mark == UNKNOWN_MARK) {
            printf("?\n");
        } else {
            printf("%d\n", students[i].mark);
        }
    }
}

// Options for selection
#define OPTION_UPDATE_MARK 1
#define OPTION_PRINT_REPORT 2
#define OPTION_EXIT 3

int main(void) {
    printf("=== Welcome to the Class Management System ===\n");
    while (1) {
        printf("Options:\n");
        printf("%d. Update student mark\n", OPTION_UPDATE_MARK);
        printf("%d. Print class report\n", OPTION_PRINT_REPORT);
        printf("%d. Exit\n", OPTION_EXIT);
        printf("Please select an option [1-3]: ");

        int option;
        scanf("%d", &option);

        if (option == OPTION_UPDATE_MARK) {
            update_student_mark();
        } else if (option == OPTION_PRINT_REPORT) {
            print_report();
        } else if (option == OPTION_EXIT) {
            break;
        } else {
            printf("Invalid option!\n");
        }
    }

    printf("=== Exiting cms. Goodbye! ===\n");

    return 0;
}

For example:

1521 mipsy cms.s
=== Welcome to the Class Management System ===
Options:
1. Update student mark
2. Print class report
3. Exit
Please select an option [1-3]: 2
ID      Mark
5123456 ?
5308310 ?
5417087 ?
3456789 ?
5345678 ?
5234567 ?
Options:
1. Update student mark
2. Print class report
3. Exit
Please select an option [1-3]: 1521   
Invalid option!
Options:
1. Update student mark
2. Print class report
3. Exit
Please select an option [1-3]: 1   
Please enter the student ID: 5345678
Please enter the student mark: 86 
Options:
1. Update student mark
2. Print class report
3. Exit
Please select an option [1-3]: 2
ID      Mark
5123456 ?
5308310 ?
5417087 ?
3456789 ?
5345678 86
5234567 ?
Options:
1. Update student mark
2. Print class report
3. Exit
Please select an option [1-3]: 1
Please enter the student ID: 5345678
Please enter the student mark: 94
Options:
1. Update student mark
2. Print class report
3. Exit
Please select an option [1-3]: 2
ID      Mark
5123456 ?
5308310 ?
5417087 ?
3456789 ?
5345678 94
5234567 ?
Options:
1. Update student mark
2. Print class report
3. Exit
Please select an option [1-3]: 1
Please enter the student ID: 9300035 
Student not found in class!
Options:
1. Update student mark
2. Print class report
3. Exit
Please select an option [1-3]: 3
=== Exiting cms. Goodbye! ===

You must implement the code in cms.s as given in cms.c.
You cannot simplify cms.s by removing functions/function calls or modifying function signatures.
The main function has been implemented for you. You must not modify this function.
The find_student_by_id and print_reportfunctions are partially implemented for you, with loop structures provided. You may choose to use the provided partial implementations, or rewrite these from scratch should you wish.
Like assignment 1, functions will be tested individually to ensure that constants are used as provided and the MIPS calling conventions are adhered to.
You may not modify the data segment.

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

1521 autotest cms

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

give cs1521 lab04_cms cms.s

Challenge Exercise — individual:
MIPS Ackermann Function

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

#include <stdio.h>

int ackermann(int, int);

int main(void) {
    int m, n;

    printf("Enter m: ");
    scanf("%d", &m);

    printf("Enter n: ");
    scanf("%d", &n);

    int f = ackermann(m, n);

    printf("Ackermann(%d, %d) = %d\n", m, n, f);

    return 0;
}

int ackermann(int m, int n) {
    if (m == 0) return n + 1;
    if (n == 0) return ackermann(m - 1, 1);
    return ackermann(m - 1, ackermann(m, n - 1));
}

For example:

1521 mipsy ackermann.s
Enter m: 0
Enter n: 0
Ackermann(0, 0) = 1
1521 mipsy ackermann.s
Enter m: 3
Enter n: 1
Ackermann(3, 1) = 13
1521 mipsy ackermann.s
Enter m: 3
Enter n: 5
Ackermann(3, 5) = 253
1521 mipsy ackermann.s
Enter m: 4
Enter n: 0
Ackermann(4, 0) = 13

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

1521 autotest ackermann

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

give cs1521 lab04_ackermann ackermann.s

Challenge Exercise — individual:
Polymipsism (Attempt if you dare!)

Polymorphism is the ability for a program to use a common interface for different underlying forms. This is a powerful feature of many modern programming languages, and is core to most widely used object-oriented programming languages (eg. Java, C#, Python).

As programmers that love a tough challenge, we would like to bring polymorphism to MIPS assembly -- polymipsism! In particular, we would like to implement a simplified model of a specific class of polymorphism: namely, late-binding ad-hoc polymorphism through duck typing. What a mouthful! Let's look at some simple Python code to try to understand how it works:

class Duck:
    def __init__(self, name):
        self.name = name

    def speak(self):
        print(f"{self.name} says quack!")

class Dog:
    def __init__(self, name):
        self.name = name

    def speak(self):
        print(f"{self.name} says woof!")

class Cat:
    def __init__(self, name):
        self.name = name

    def speak(self):
        print(f"{self.name} says meow!")


our_animals = [Duck("Daffy"), Dog("Clifford"), Cat("Scruffles")]

for animal in our_animals:
    animal.speak()

# This program will output:
#   Daffy says quack!
#   Clifford says woof!
#   Scruffles says meow!

The code above defines three animal types: a Duck, a Dog, and a Cat. Each of these types defines a function __init__, which is essentially a special function to say that in order to create something of this type, you are required to provide a name. They each define a function speak, that prints out a specific message. Importantly, the function is named exactly the same: "speak" in each animal. If the functions had even slightly different names, then our polymorphism would not work.

We then create a list of these animal "objects" called our_animals, providing each of the animals a name. We can then iterate over this list, and call speak() on each object. Because each of those animals has a function named speak, we can call that speak function on each object without knowing exactly which type of object it is. This practice was named duck typing from the long-time idiom: "If it walks like a duck and it quacks like a duck, then it must be a duck".

Aside: if learning about these kinds of programming concepts is something you may be interested in, don't hesitate to check out COMP3161!

Unfortunately, we aren't given such convenient language features to use in C (let alone MIPS assembly), so we need to get a bit creative! In particular, we're going to need to make heavy use of function pointers. These can be quite tricky to understand, so make sure you understand the fundamentals before starting on this exercise.

Using our polymipsism library, this is how the equivalent C code looks:

#include <stdio.h>
#include "polymipsism.h"
#include "provided.h"

object make_animal(char *name, void *(*fn_ptr)(void *));

void *duck_speak(void *);
void *dog_speak(void *);
void *cat_speak(void *);

int main(void) {
    object duck = make_animal("Daffy",     duck_speak);
    object dog  = make_animal("Clifford",  dog_speak);
    object cat  = make_animal("Scruffles", cat_speak);

    obj_call(duck, "speak");
    obj_call(dog,  "speak");
    obj_call(cat,  "speak");

    return 0;
}

object make_animal(char *name, void *(*fn_ptr)(void *)) {
    object obj = make_object(name, 1);
    obj_define(obj, "speak", fn_ptr);

    return obj;
}

void *duck_speak(void *data) {
    printf("%s says quack!\n", (char *) data);
    return NULL;
}

void *dog_speak(void *data) {
    printf("%s says woof!\n", (char *) data);
    return NULL;
}

void *cat_speak(void *data) {
    printf("%s says meow!\n", (char *) data);
    return NULL;
}

If you squint a little, you can hopefully see a vague resemblance between the first Python example and our C code's main function. Indeed, running the C code will produce the same output as the Python:

dcc provided.c polymipsism.c main_duck.c -o duck_typing
./duck_typing
Daffy says quack!
Clifford says woof!
Scruffles says meow!

Also provided is main_simple.c (and main_simple.s) which is a simple usage of the polymipsism library, only taking advantage of the dynamic dispatch it provides.

dcc provided.c polymipsism.c main_simple.c -o simple
./simple
10

Your task is to translate the polymipsism library from C to MIPS -- i.e. you do not have to translate any main functions. You are given some provided files to help you with this task:

`polymipsism.c`	the code you will translate to MIPS assembly
`polymipsism.s`	your starter file: your code goes here
`main_duck.c`	a polymorphism example -- the C code seen above
`main_duck.s`	`main_duck.c` translated to MIPS assembly
`main_simple.c`	another polymorphism example
`main_simple.s`	`main_simple.c` translated to MIPS assembly
`provided.c`	C functions that have already been translated for you
`provided.s`	`provided.c` translated to MIPS assembly

There is also a couple of header files to glue everything together:

`polymipsism.h`	the header file for the polymipsism library
`provided.h`	the header file for the provided functions

You should read through all these files before starting on this exercise.

To test your code using mipsy:

1521 mipsy constants.s provided.s main_simple.s polymipsism.s
10
1521 mipsy constants.s provided.s main_duck.s polymipsism.s
Daffy says quack!
Clifford says woof!
Scruffles says meow!

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

1521 autotest polymipsism

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

give cs1521 lab04_polymipsism polymipsism.s

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 5 Tuesday 12:00:00 (midday) to submit your work without receiving a late penalty.

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