|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
On the previous assignment, you wrote a utility called
a simplified version of
cat that only handles one file.
For this question, you will write a similar utility called
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
Meow meow followed by a line feed, the
would output a line feed, followed by
Just like the
kitten utility, the
should also store the number of bytes provided on standard input in register 3
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
$ mips.stdin nettik.mips < input.txt > output.txt ... $ cs241.binview -ba output.txt
-ba option means "show binary and ASCII output".
Look for unexpected character codes in the output (for example, a null byte is displayed
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
$ 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
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
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.
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]) == 1for each i such that 0 ≤ i ≤ n-2. In other words, do the elements "strictly increase" according to the
compareprocedure? 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
but you should not submit a
compare procedure to Marmoset.
compareprocedure will begin with a label
compareprocedure will preserve all registers except for $3.
compareprocedure 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
compareprocedure 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
compareprocedure to compare elements, rather than relying on
Test your program with
mips.array. This tool
works similarly to
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
The most basic way to test your procedure is to just run it directly with
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,
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
Test your program with
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 = 77 A = 3 A = 6 A = 22 A = -1 A = -1 A = -8 A = 9 A = 12 A = -36 A = -1 A = -1 A = 999 A = -1 A = -1
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 = 77 A = 6 A = 3 A = -8 A = 9 A = 15 A = 22 A = -1 A = -1 A = -36 A = -1 A = -1 A = 241 A = 241 A = 241 A = 999 A = -1 A = -1
Test your program with
mips.array. Ensure the value in register 3 is correct.