| Assignments for CS 241 | ||
|---|---|---|
| ← Assignment 1 | Assignment 2 | Assignment 3 → |
| Friday, June 2nd at 5:00 pm | ||
| P1 • P2 • P3 • P4 • P5 | ||
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.
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.
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.
On the Student Linux server, 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.
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.
compare(A[i], A[i+1]) == 1 for each i such that
0 ≤ i ≤ n-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.
compare procedure will begin with a label compare:compare procedure will preserve all registers except for $3.
compare procedure will be consistent with a certain ordering of the
array elements, but you do not know what this ordering is.
For example, it is possible the procedure will return 1 for a pair of elements
even if, when interpreted as integers, the first element is not
less than the second. The compare procedure might be enforcing a different
order on integers, or it may not be interpreting the values as integers at all!
Thus, you must use the compare procedure to compare
elements, rather than relying on slt or sltu.
Test your program with mips.array. This tool
works similarly to mips.twoints and mips.stdin, but it
prompts you to enter an array. In the web-based version, you can simply
enter the values for the array, one per line. In the command-line version
on the student Linux server, 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.
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).
print:
- (ASCII 0x2D).
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. For
instance, on the Student Linux server:
$ 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).
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
stirling:
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.
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.
A[0] = 77 A[1] = 6 A[2] = 3 A[3] = -8 A[4] = 9 A[5] = 15 A[6] = 22 A[7] = -1 A[8] = -1 A[9] = -36 A[10] = -1 A[11] = -1 A[12] = 241 A[13] = 241 A[14] = 241 A[15] = 999 A[16] = -1 A[17] = -1
Test your program with mips.array. Ensure the value in register 3 is correct.