CS 241 — Spring 2022 — Assignment 2

Due Friday, May 27, 5:00 pm / Out of 10 marks

On this assignment, you will write more complicated MIPS programs than ever before, which will involve memory access, arrays, procedures, and recursion.

You will use a new course tool called mips.array, a MIPS emulator that allows you to provide an array as input to a MIPS program.

Problem 1: The Nettik Utility (filename: nettik.asm) [1 mark]

On the previous assignment, you wrote a utility called kitten, a simplified version of cat that only handles one file.

For this question, you will write a similar utility called nettik. This utility reads bytes from standard input until no more bytes remain. It then outputs the bytes in reverse order. For example, if the input was Meow meow followed by a line feed, the nettik would output a line feed, followed by woem woeM.

Just like the kitten utility, the nettik utility should also store the number of bytes provided on standard input in register 3 before returning.

Testing

The methods used for testing the kitten utility should work just as well here, except that you cannot use diff input.txt output.txt to check the correctness of the output, since the output is reversed.

Ensure that both the contents of standard output and the value in register 3 are correct.

It is perhaps easiest to confirm the correctness visually for this problem. However, there is one pitfall here. You might accidentally print an invisible character (like the null byte, ASCII 0x00) as part of your output. Then your output will look correct, but will actually contain this extra character, and you will fail the Marmoset tests. You can check for extra bytes using cs241.binview:

$ mips.stdin nettik.mips < input.txt > output.txt
...
$ cs241.binview -ba output.txt

The -ba option means "show binary and ASCII output". Look for unexpected character codes in the output (for example, a null byte is displayed as ^NUL).

Note also that most methods of providing input on the Linux environment will implicitly append a line feed to the end of the input. This means there will be a line feed at the start of the nettik utility's output, if it is implemented correctly, which can look a little strange.

Here is an example of correct output, including what it looks like when run through cs241.binview.

$ mips.stdin nettik.mips <<< "Meow meow"
Running MIPS program.

woem woeMMIPS program completed normally.
$01 = 0x00000001   $02 = 0x00000000   $03 = 0x0000000a   $04 = 0x00000004
$05 = 0x0000004d   $06 = 0x0000000a   $07 = 0x00000000   $08 = 0x00000000
$09 = 0x00000000   $10 = 0x00000000   $11 = 0xffffffff   $12 = 0x00000000
$13 = 0x00000000   $14 = 0x00000000   $15 = 0x00000000   $16 = 0x00000000
$17 = 0x00000000   $18 = 0x00000000   $19 = 0x00000000   $20 = 0xffff000c
$21 = 0xffff0004   $22 = 0x00000000   $23 = 0x00000000   $24 = 0x00000000
$25 = 0x00000000   $26 = 0x00000000   $27 = 0x00000000   $28 = 0x00000000
$29 = 0x00000000   $30 = 0x01000000   $31 = 0x8123456c
$ mips.stdin nettik.mips <<< "Meow meow" > output.txt
...
$ cs241.binview -ba output.txt
^LF      w        o        e
00001010 01110111 01101111 01100101

m        (SP)     w        o
01101101 00100000 01110111 01101111

e        M
01100101 01001101

You can see above that the output starts with a newline, but does not end with a newline, so it runs together with the "MIPS program completed normally" message. This is the expected behaviour for the given input. Note also the ^LF (line feed) at the beginning of the cs241.binview output.

Problem 2: Strictly Increasing (filename: increasing.asm) [1 mark]

Write a MIPS program that takes an array as input, where register 1 contains the starting address and register 2 contains the size (number of elements). The program should determine whether the array is strictly increasing with respect to a custom comparison procedure called compare.

That is, suppose we have an array A of length n, and a procedure called compare which takes two array elements as parameters, in registers 1 and 2. The compare procedure returns the value 1 (in register 3) if the first parameter is considered "less than" the second parameter, and otherwise returns the value 0.

Then, your program must determine if compare(A[i], A[i+1]) == 1 for each i such that 0 ≤ in-2. In other words, do the elements "strictly increase" according to the compare procedure? If so, store 1 in register 3. If not, store 0 in register 3. Then return to the loader.

Marmoset will provide the compare procedure and combine it with your program. For testing, you will need to write your own compare procedure, but you should not submit a compare procedure to Marmoset.

Clarifications

Testing

Test your program with mips.array. This tool works similarly to mips.twoints and mips.stdin, but it prompts you to enter the size of the array, followed by each element of the array. It will then place the starting address of the array in $1, and the size in $2.

Ensure the value in register 3 is correct.

Marmoset provides its own compare procedure, and will reject your submission if you include a compare procedure. But you will need a compare procedure to test your program. A simple workaround is to put the compare procedure in a separate file, and combine them with cat before assembling:

$ cat increasing.asm compare.asm | cs241.binasm > increasing.mips

With this setup, you don't need to remember to remove the compare procedure you use for testing before each Marmoset submission.

Problem 3: Printing Integers (filename: print.asm) [3 marks, 1 secret]

Write a MIPS procedure called print that interprets the value in $1 as a two's complement integer, and prints the decimal (base 10) representation of the integer to standard output, followed by a line feed character (ASCII 0x0A).

Clarifications

Testing

The most basic way to test your procedure is to just run it directly with mips.twoints and ensure standard output corresponds to the value entered in $1.

$ mips.twoints print.mips
Enter value for register 1: 241
Enter value for register 2: 0
Running MIPS program.
241
MIPS program completed normally.
$01 = 0x000000f1   $02 = 0x00000000   $03 = 0x00000000   $04 = 0x00000000
$05 = 0x00000000   $06 = 0x00000000   $07 = 0x00000000   $08 = 0x00000000
$09 = 0x00000000   $10 = 0x00000000   $11 = 0x00000000   $12 = 0x00000000
$13 = 0x00000000   $14 = 0x00000000   $15 = 0x00000000   $16 = 0x00000000
$17 = 0x00000000   $18 = 0x00000000   $19 = 0x00000000   $20 = 0x00000000
$21 = 0x00000000   $22 = 0x00000000   $23 = 0x00000000   $24 = 0x00000000
$25 = 0x00000000   $26 = 0x00000000   $27 = 0x00000000   $28 = 0x00000000
$29 = 0x00000000   $30 = 0x01000000   $31 = 0x8123456c

However, testing procedures is more involved than testing standalone programs. In addition to ensuring the procedure functions correctly, you must ensure that it preserves register values, and that it always works regardless of what values are in registers when it is called. Consider these scenarios:

Try writing main programs that call the procedure multiple times with different assortments of register values to test that you have truly written it correctly.

If Marmoset says your output is wrong, but it "looks correct" in your local testing, use cs241.binview or xxd to ensure you did not accidentally print invisible characters, such as the null character (ASCII 0x00).

Problem 4: Stirling Numbers (filename: stirling.asm) [2 marks]

Write a MIPS procedure called stirling that takes as input two 32-bit unsigned integers, n = $1 and k = $2, such that n ≥ k, and stores the value f(n,k) in $3 using the following recursively defined function:

f(0,0) = 1.
f(i,0) = f(0,i) = 0, for integers i > 0.
f(n,k) = (n-1) * f(n-1,k) + f(n-1,k-1), for integers n > 0 and k > 0.

Remark: This function computes what are known as the "unsigned Stirling numbers of the first kind".

You may use the table below to check the correctness of your answers for some small values. If n < k, then f(n,k) is always zero, so these cases are omitted from the table.

n/k 0   1   2   3   4   5   6
0   1
1   0   1
2   0   1   1
3   0   2   3   1
4   0   6   11  6   1
5   0   24  50  35  10  1
6   0   120 274 225 85  15  1

Clarifications

Testing

Test your program with mips.twoints. Ensure the value in register 3 is correct. Since this is a procedure, test it with various main programs that put different values in registers, and ensure general-purpose registers other than $3 are preserved.

Problem 5: Height of a Tree (filename: height.asm) [3 marks, 1 secret]

In this problem, you will write a MIPS program that determines the height of a binary tree.

We use the convention that the height is the number of nodes in a path from the root to a leaf (not the number of edges, which is another common convention). Therefore, a single-node tree has height one.

The tree will be encoded in an array of 32-bit two's complement integers. Each node of the tree is encoded in three consecutive elements (words) of the array: a value stored at the node, a reference to the node's left child, and a reference to the node's right child. Each "reference" is either the array index where the child node is encoded, or -1 if the node is missing that child. For example, the following tree:

     77
    /  \
   22   -8
       /  \
     -36   999

Could be encoded by following array:

A[0] = 77
A[1] = 3
A[2] = 6
A[3] = 22
A[4] = -1
A[5] = -1
A[6] = -8
A[7] = 9
A[8] = 12
A[9] = -36
A[10] = -1
A[11] = -1
A[12] = 999
A[13] = -1
A[14] = -1

In which:

This tree has height 3.

Assume register 1 holds the starting address of the array, and register 2 holds the size of the array. Determine the height of the tree, store it in register 3, and return.

Clarifications

Testing

Test your program with mips.array. Ensure the value in register 3 is correct.