Homework 09: MIPS32 assembly in SPIM

• from Git classroom link
• as ZIP file

This homework is a continuation of the work you did in Lab 09 using spim to execute MIPS32 programs that you write in its assembly language. Follow the instructions there for getting the spim and running the code.

Here I have four exercises, three building from ideas from Lecture 09-2 and Lecture 10-1, namely:

• Working with an array of integers held in memory using LW.
• Working with a linked list of data pairs held in memory using LW and SW at an offset.
• Working with the underlying bits held in a register using SLL, SRL, and ANDI.

I’ve also included several sample programs from these lectures for your reference. In some cases it’ll be best to solve an exercise by using one of these samples as a start.

Here again are some resources you can reference to on MIPS and SPIM:
• the SPIM simulator
• SPIM’s MIPS information links
• the MIPS32 programmer’s guide
For today, you might most benefit by referencing these:
• the MIPS32 quick reference
• this SPIM system call reference
These two, and the instructions and examples below, ought to be enough for you get this work done.

Here also is a summary of the MIPS32 instruction set we’ve learned: * ADD $Rdst, $Rsrc1, $Rsrc2: sum two registers, placing result in a third * ADDI $Rdst, $Rsrc, constant: sum a register with a constant * SUB $Rdst, $Rsrc1, $Rsrc2: subtract two registers, placing result in a third * AND $Rdst, $Rsrc1, $Rsrc2: compute the bitwise AND of two registers, placing result in a third * ANDI $Rdst, $Rsrc, constant: compute the bitwise AND of a register with a constant * SLL $Rdst, $Rsrc, positions: shift a register’s bits left some number of positions, storing the result in another * SRL $Rdst, $Rsrc, positions: shift a register’s bits right some number of positions, storing the result in another * SRA $Rdst, $Rsrc, positions: same as the above, but copying the sign bit * LI $Rdst, constant: set a register to some constant’s value * LA $Rdst, label: load a register with the address of a labelled location in the data segment * MOVE $Rdst, $Rsrc: copy a value from one register into another * LW $Rdst, ($Rtgt): load a register from memory at an address
* SW $Rsrc, ($Rtgt): store a register into memory at an address
* LW $Rdst, offset($Rtgt): load a register from memory at an address at an offset * SW $Rsrc, offset($Rtgt): store a register into memory at an address at an affset * LB $Rdst, ($Rtgt): load a register with a byte in memory at an address
* SB $Rsrc, ($Rtgt): store a byte of a register into memory at an address
* BLT $Rsrc1,$Rsrc2,label: jump to a line if one register’s value is less than another. Also GT, GE, LE, EQ, and NE. * B label: jump to a line if one register’s value is less than another. Also GT, GE, LE, EQ, and NE.

The registers are v0, v1, a0-a3, t0-t9, s0-s7, gp, sp, fp, and ra. You shouldn’t use the last four explicitly, unless you’ve decided to make it an exercise for yourself to write a MIPS32 function using calling conventions.

Exercises

Exercise 1: guessing six

The MIPS32 program guess.s interacts with its user when run in SPIM, helping them guess the hidden number that’s stored in its .data memory segment. Modify this to be a program guess6.s that only allows its user to make at most 6 quesses. It should tell them You ran out of guesses. My number is XX. on a single line, when they fail to guess the number after 6 guesses. (Here XX should be the value of the correct guess.) Also, it should tell them how many guesses they have left with the line You have Y guesses. just before they request the next guess. (Here Y should be the number of guesses that have left.)

It should work with any hidden integer between 1 and 100.

BONUS We’ve chosen a limit of 6 when the number to guess is in the range 1 to 100 because the logarithm of 100 using base 2 is 6. Make the program determine the number of guesses from the .word stored at the label max, and so is calculated from the number stored at that label. I’d think the limit should be chosen such that the probability that they lose the guessing game, assuming they make reasonable guesses, is between 1/4th and 1/2. I’d think they’d want to keep playing if set up that way.

Exercise 2: only smaller values

I’ve included a MIPS32 program output_array.s that scans through the values stored in memory at the address labelled array and prints them out. It learned the number to print by reading the data stored at the label length.

Modify its code as a new program smaller.s that only outputs array entries when they immediately follow a value that’s larger than them. For example, the top of the sample program has this .data declaration

length: .word 10
array:  .word 6, 12, 89, 78, 90, 137, 5, 18, 10, 1000

and so running smaller.s with this should yield the output

78
5
10

It should work correctly when length and array are set differently than the example.

Exercise 3: binary palindromes

The number 92 has the binary representation 1011100 because 92 = 64+16+8+4. And so the number 93 has the binary representation 1011101. That second code for 93 is a palindrome because it reads the same forwards as it does backwards, but the representation for 92 does not. The binary representation of 85 is also a palindrome.

Write a program that takes two integers and outputs only the integers in that range whose bit representations are palindromes. For example, running it should lead to this interaction:

Enter the start: 73
Enter the end: 119
73
85
93
99
107
119

I’ve include bits.s, bitsInReverse.s, and multiply.s from Lecture 10-1 so that you can see the shift operations in use.

Exercise 4: reversing a linked list

The C++ code below does the work of reversing a linked list list:

node* prev = nullptr; 
node* curr = list->first;
while (curr != nullptr) {
    node* next = curr->next;
    curr->next = prev;
    prev = curr;
    curr = next;
}
list->first = prev;

Add a section to the linked list MIPS32 program inorder_llist.s as a new program inorder_reverse.s so that, after it traverses and prints out the contents of a sorted linked list, it then reverses the nodes in that linked list. It should so that be relinking the nodes similar to how the C++ code above does. Finally, have it traverse and print the resulting linked list.

You should be able to just cut and paste the code that outputs the linked list after your reversal code. The second output should show the data to be in reverse sorted order.