Assignment 3

Type: Individual Assignment
Due: before class on Monday, October 25, 2021

Extended Due Date: Because of fall break, I will not count your assignment late if it is turned in before 11:59 PM on Monday, October 25, 2021.

Prologue

In this assignment, you will implement several simple functions in MIPS assembly. To simulate MIPS programs, we will be using an IDE called Mars, developed by Pete Sanderson and Kenneth Vollmar. To run the IDE, you must have Java installed, so be sure to install the Java JDK if you haven’t already.

You can download the latest version of Mars below:

• Mars4_5.jar

You should be able to launch Mars by simply double clicking the JAR file. Alternatively, you can launch the JAR via a terminal by typing java -jar Mars4_5.jar.

Overview

Your task in this assignment is to convert the three C functions below into MIPS assembly. The function isort is a classical implementation of insertion sort using two helper functions insert_left and swap. In the following section I provide you with starter code and give a suggested process of how to proceed in completing the assignment.

NOTE: In this assignment, you may ONLY use MIPS instructions covered in the readings and in class. If there is an instruction you wish to use other than these, you must explicitly get permission from your instructor.

// Swaps the values of arr at indices i and i-1
void swap(int *arr, int i)
{
    int temp = arr[i];
    arr[i] = arr[i-1];
    arr[i-1] = temp;
}

// Insert the element at i into the sorted region of arr
void insert_left(int *arr, int i)
{
    if (i > 0 && arr[i] < arr[i-1]) {
        swap(arr, i);
        insert_left(arr, i-1);
    }
}

// Sorts array with the given size using insertion sort
void isort(int *arr, int size)
{
    for (int i = 1; i < size; i++) {
        insert_left(arr, i);
    }
}

Getting Started

To complete the assignment, I suggest you do the following:

1. Start by downloading the following C program that uses these functions to sort an array of integers and print off the sorted array. Examine it closely, and make sure you understand why the algorithm works. Your final MIPS program will be an equivalent program. I also suggest compiling it and running it on your local machine.
   • sorting.c
2. Next, download the following MIPS starter code. The main function and the print function are already implemented for you. Your task is to implement the functions isort, insert_left, and swap.
   • sorting.asm
3. Before writing any MIPS code, open the sorting.asm file in Mars, assemble it, and run it. You should see the sequence 721345890 printed in the console; this is the initial unsorted array. After you finish your assignment, it should print 0123456789 when you run the program .
4. Since swap is a leaf function, I suggest you start by implementing it. You should not need to allocate any memory on the stack to write this function. Since words consist of four bytes in MIPS, don’t forget to multiply indices by four with sll before loading the words at arr[i] and arr[i-1] into registers.
5. Before moving on, I suggest you thoroughly test your swap function by editing the main code to call swap on various indices and ensure that the values are swapped in memory appropriately. You can find the array in the Data Segment window of Mars under the .data section.
6. After swap is working properly, I suggest implementing insert_left next. Notice that insert_left is tail recursive which means that recursive calls can be made with j insert_left instead of jal insert_left. This also means that it is possible to implement insert_left with minimal use of the stack $sp (you may still need to use it to save/restore variables when calling the swap function).
7. Test the insert_left function by editing the main code to call it. You might also consider editing the arr array at the top of the sorting.asm file to test it on a variety of arrays.
8. Finally, implement the isort function and thoroughly test it.

Submitting

When you are satisfied with your solution, be sure to restore any starter code other than your implementations of isort, insert_left, and swap, and upload your sorting.asm to Gradescope under Assignment 3.

Grading Criteria

I will evaluate your work based on correctness, formatting, and elegance. Therefore it is important to also ensure that your code is concise, thoroughly commented, and easy to read.