Objectives

  • Learn coding in MIPS assembly

Preamble

This lab introduces you to programming in the MIPS assembly language. In particular, exercises 1 and 2 below require the re-implementation in the MIPS assembly language of two exercises already encountered in the previous lab.

Begin by downloading the starter file and unzip its content to a directory of your choice.

Modifications/implementations are to be done in impl.s file for each exercise

To test and verify your implementations, you can run the following commands in UN*X environment:

$ cd path/to/lab4
$ chmod +x run_tests.sh     # <-- to do once only (makes sure you can execute the script run_tests.sh)
$ ./run_tests.sh            # <-- execute this script each time you want to test your implementations

Correct execution of the script will display on your screen the results of some validation tests. The bash script run_tests.sh actually launches several commands of the form

java -jar munit.jar "exercise_dir/impl.s" "exercise_dir/TestImpl.class"

  • munit.jar is a java library used to automatically test MIPS programs.

  • To get an idea on what tests are performed for a given exercise, have a look inside the associated file TestImpl.java from the exercise folder. For the curious, these files implement junit unit tests.

Hint:

  • You can use the MARS simulator to implement and test your codes. Here is a quick tutorial on the functionalities of this software. If using MARS, load the exercise/runner.s file into the editor and uncomment the last line to include your implementation in exercise/impl.s.

  • To test your implementations of exercises 3 to 5 in the MARS environment, you will need to implement your own runner.s files. Have a look at the files sum_of_squares/runner.s and strcmp/runner.s in exercises 1 & 2 respectively to get some ideas how this can be done.

  • Read the comments in impl.s files to see which registers you should use for coding.

Exercise 1: (sum of squares)

The sum of squares of N integers is described as follows:

\[sum = \sum_{i=0}^{N-1} n_i^2\]

where \(n_0, n_1, ..., n_{N-1}\) are integer numbers (i.e. of type int).

Implement in MIPS the body of the function SumOfSquares() in sum_of_squares/impl.s. This function must return in the register $v0 the sum of the squares of the elements of an array of words. The size of the array is given in register $a0, and the pointer to the array is given in register $a1.

Hint: Do exercise #1 of the lab “Unstructured programming”, then convert your C code into MIPS using the MIPS reference card .

Exercise 2: (strcmp)

In the standard C library, the strcmp function (see man 3 strcmp) compares, character by character, two strings to establish which character string comes first in the standard lexicographical order -i.e. based on the ASCII values ​​of the characters. Here are some examples:

  • “a” < “b”
  • “abc” < “abcd”
  • “A” < “a”

The strings to compare are represented by contiguous bytes (each byte is an ASCII code) in memory followed by the NUL character (0x00).

Implement in MIPS the body of the function StrCmp(char* str1, char* str2) in strcmp/impl.s. This function must return in the register $v0 the result of the comparison of two character strings. If the first string is less than the second, then $v0 will be negative. If the two strings are similar then $v0 will be null. Finally, if the first string is greater than the second then $v0 will be positive. The pointer to the first (resp. second) string is given in register $a0 (resp. $a1).

Hint: Do exercise #2 of the lab “Unstructured programming”, then convert your C code into MIPS using the MIPS reference card .

Exercice 3: (steps)

Take any positive integer N. If N is even, divide N by 2 to get N / 2. If N is odd, multiply N by 3 and add 1 to get 3N + 1. Repeat the process indefinitely. A mathematical conjecture (i.e. not proven, yet) states that no matter which number you start with, you will always reach 1 eventually.

Given a number N, implement the mips function steps(int N) in steps/impl.s which returns the number of steps required to reach 1.

Example: Starting with N = 12, the steps would be as follows:

\[\begin{aligned} 12 \div 2 &= 6 \\ 6 \div 2 &= 3 \\ 3 \times 3 + 1 &= 10 \\ 10 \div 2 &= 5 \\ 5 \times 3 + 1 &= 16 \\ 16 \div 2 &= 8 \\ 8 \div 2 &= 4 \\ 4 \div 2 &= 2 \\ 2 \div 2 &= 1 \\ \end{aligned}\]

Resulting in 9 steps. So for input N = 12, steps(int N) should return the value 9.

Exercise 4: (ISBN)

The International Standard Book Number (ISBN) is a (unique) numeric commercial book identifier. Up to the end of December 2006, ISBNs were 10 digits in length (ISBN-10 format), but since 1 January 2007 they now consist of 13 digits (ISBN-13 format).

The ISBN-10 format is 9 digits (0 to 9) plus one “check character” (either a digit or an X). In the case the “check character” is an X, this represents the value 10. ISBNs normally contain dashes and look like: 3-598-21507-X.

A string is an ISBN-10 number if it verifies the following formula:

\[\sum_{i=1}^{10} (11-i) \times x_i \equiv 0\; (\mathrm{mod} \; 11)\]

For instance, applying the equation to the ISBN-10 number given above, yields:

\[s = \left( 3 \times 10\right) + \left( 5 \times 9\right) + \left( 9 \times 8\right) + \left( 8 \times 7\right) + \left( 2 \times 6\right) + \left( 1 \times 5\right) + \left( 5 \times 4\right) + \left( 0 \times 3\right) + \left( 7 \times 2\right) + \left( 10 \times 1\right) \equiv 0 \; \left( \mathrm{mod} \; 11\right)\]

Given a string, write in isbn/impl.s a MIPS function that implements the equation described above. The program should be able to verify strings both with and without separating dashes.