Question 7

Deadline	Friday, December 1, 11:59pm
Name on Marmoset	Q7
To Submit	`height.asm`

MIPS Assembly Programming, Part III

This is the third of several questions that will involve programming in MIPS assembly language. To assemble your program (i.e., convert it into machine code) you can use the course tool cs241.binasm. You can then run the machine code program with one of our MIPS emulators:

mips.twoints, which takes two integers as input and stores them in $1 and $2 before running the program.
mips.stdin, which just runs the program with no setup; this is intended for programs that work by reading from standard input.
mips.array, which asks you to specify the elements of an array, allocates the array in memory after the end of your program, stores the starting address of the array in $1, and stores the number of elements in $2.

MIPS Assembly Language Reference

The following reference sheet describes all the instructions available in our simplified CS 241 dialect of MIPS assembly language.

Height of a Binary Tree

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:

Could be encoded by following array:

A[0]  =
A[1]  =
A[2]  =
A[3]  =
A[4]  =
A[5]  =
A[6]  =
A[7]  =
A[8]  =
A[9]  =
A[10] =
A[11] =
A[12] =
A[13] =
A[14] =

In which:

The root is encoded by the elements A[0], A[1] and A[2].
The root's left child is encoded by the elements A[3], A[4] and A[5].
The root's right child is encoded by the elements A[6], A[7] and A[8].
The root's left-most grandchild is encoded by the elements A[9], A[10] and A[11].
The root's right-most grandchild is encoded by the elements A[12], A[13] and A[14].

This tree has height 3.

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

Clarifications

You may assume every tree has at least one node. In other words, the input array will not be empty (and in fact will have size at least three).
Since you are writing a program in this question, not a procedure, you do not need to preserve any registers, except those that are necessary for your program to function correctly.
Your program is free to use procedures (and you will likely find it difficult to solve this question without using a procedure).
Marmoset will only check the value in $3 to determine if your program is correct.
While this does not occur in the above example, it is allowed for a node to only have one child (for example, a left child but no right child, or the other way around).

The root of the tree will always be encoded in the first three elements of the array (A[0], A[1], and A[2]) but the other nodes can appear in any order, and the array can contain elements which do not correspond to tree nodes. For example, another valid encoding of the tree above is as follows:

A[0]  =
A[1]  =
A[2]  =
A[3]  =
A[4]  =
A[5]  =
A[6]  =
A[7]  =
A[8]  =
A[9]  =
A[10] =
A[11] =
A[12] =
A[13] =
A[14] =
A[15] =
A[16] =
A[17] =

Testing Tips

If working on the Linux environment, it can be tedious to type in the arrays every time you run your program. You can store different test inputs in different files and redirect them into mips.array. For example, you can create a file called array.txt with the following contents:

9
-1
3
-1
-1
6
-1
-1
-1
-1

The first line is the size of the array, and the remaining lines are the elements of the array. This represents the following tree:

  -1
  /
-1
  \
  -1

You can test your program with this input as follows:

mips.array <(cs241.binasm < height.asm) < array.txt

You can create many of these input files to test your program with different inputs.

For debugging, you may find it useful to test your program with the stepper mips.stepper_twoints. Unfortunately, it doesn't support arrays as input, but you can work around this by creating a file that encodes the array in the following format:

beq $0, $0, debugArrayEnd
debugArraySize: .word 9
debugArrayStart: ; list the array elements below
.word 2
.word 3
.word 6
.word 4
.word -1
.word -1
.word 1
.word -1
.word -1
debugArrayEnd:
lis $1
.word debugArrayStart
lis $2
.word debugArraySize
lw $2, 0($2)

If you name this file array.asm, you can run it with the stepper as follows:

mips.stepper_twoints <(cat array.asm height.asm | cs241.binasm)

The program will skip over the array contents, then store the address of the array in $1 and the size of the array in $2, and then your MIPS program will run.

This problem is difficult. When you find a bug, try to find the smallest input that causes the bug so it is easier to trace the flow of the code. Other ideas for debugging include:

Printing certain characters or values at key points in the program to help understand the flow of the code (you could even use your print procedure from Question 6!)
Forcing the program to crash at key points to examine register values (when the MIPS emulator crashes, it shows all values in registers at the point of the crash!)