CPS 500 – Lab 3

CPS 500 – Lab 3
William Katsak
Due: 11/3/2019 11:59pm ET
Overview
For this assignment, you will get some additional experience with MIPS assembly language using the MARS MIPS
simulator.
Cheating
Please be sure that all work is your own. Looking up the solution on the Internet to any of these problems counts
as cheating. If caught, you will receive a 0 for the assignment and will be reported to the academic integrity office.
Background and Setup
For this lab you need to installs the MARS MIPS simulator.
You can download MARS from http://courses.missouristate.edu/KenVollmar/mars/index.htm.
You can either install the simulator in your VM, or on your main computer.
This simulator allows you to write and run MIPS assembly language programs. The simulator itself is written
in Java so you will need a JRE (Java runtime environment) which most of you will likely already have. Installation
instructions for running Java can be found here:
https://docs.oracle.com/javase/8/docs/technotes/guides/install/install overview.html
You do not need any knowledge of Java to use this software.
What to turn in
Please submit your assembly language file from MARS.
1
Assignment
Description
1. You will convert the following shell sort program from C into MIPS. Your grade will depend on logical correctness and following the MIPS calling convention as defined as:
2. (a) All named C-variables are required to go into S-registers.
(b) All arguments must be saved in the A-registers.
(c) S-registers must be saved and restored to the stack to preserve any values in the caller function.
(d) Non-leaf functions need to save the $ra register and may need to save the $a-registers.
3. No knowledge about a called functions assembly instructions should be used by the caller function (e.g. which
set of registers are being written to). Therefore, we cannot assume that $t-registers or $a-registers or $vregisters are preserved across JAL function calls.
C Implementation
void swap(int *array, int i1, int i2) {
int temp = array[i1];
array[i1] = array[i2];
array[i2] = temp;
}
int insert_shell(int *array, int n, int gap) {
if (gap == 0) {
return 0;
}
for (int i = gap; i < n; i++) {
for (int j = i; j >= gap && (array[j – gap] > array[j]); j -= gap) {
swap(array, j – gap, j);
}
}
return 1;
}
void shell_sort(int *array, int n) {
int gap = n / 2;
while (insert_shell(array, n, gap) == 1) {
gap = gap / 2;
}
}
2
Main Program (Starting Point)
Begin with the following assembly snippet (this is the main program):

.data
array: .word 0, 5, 15, 3, 18, 7, 20, 2, 16, 1
# Defines variable section of an assembly routine.
# Define a variable named array as a word
# (integer) array.
# After your program has run, the integers in this

# array should be sorted.

.text
.globl main
main:
la $t0, array
addi $a0, $t0, 0
addi $a1, $zero, 10
jal shellSort
li $v0, 10
syscall
# Defines the start of the code section for the program.
# Moves the address of array into register $t0.
# Set argument 1 to the array.
# Set argument 2 to (n = 7).
# Call shellSort (you need to implement this method).
# Terminate program run

3

Leave a Reply

Your email address will not be published. Required fields are marked *