Lab 11: MIPS Assembly Programming (Advanced)
Overview
In this lab, you are going to write a program (in both C and MIPS assembly) that allows a human to play the computer in "Subtract a Square". You may have already played this game or a variation in COMP 51. If so, just adapt your existing solution to meet the unique ECPE 170 requirements described below.
Lab
In this game, you have 2 heaps of marbles. At the beginning, the computer should randomly populate each heap with between 10 and 100 marbles. The human and computer will alternate turns, with the human going first. On each turn, the player removes marbles from one heap. A player must remove at least one marble from the heap, the number of marbles must be a square number (e.g. 1, 4, 9, 16, 25, ...), and the player cannot remove more marbles than exist in the heap. The game continues until no marbles are left in either heap. The player to remove the last marble in the game is the loser.
You should not allow the player to make an illegal move, or to enter invalid input. For example, no player can take ZERO marbles from a heap. That’s cheating!
The computer’s "strategy" for taking a turn should be very simple.
- Randomly select a heap that still contains marbles
- Select a random integer between 1 and the square root of the heap size, then square that integer to get the number of marbles that the computer will remove.
- Remove the selected marbles and print out a message indicating the move performed.
At the end of a game, you should print out a message indicating who won. A example of the game output is shown here. Your output does not have to match this exactly.
Welcome to Subtract-a-SquareVersion 1.0
Implemented by Jeff ShaferEnter two positive numbers to initialize the random number generator.
Number 1: 123
Number 2: 456HeapA HeapB
-------------
76 63What heap would you like to draw from? Enter 'a' or 'b': a
How many marbles do you want to remove from heap a? 36
Computer sected to remove 49 from heap bHeapA HeapB
-------------
40 14What heap would you like to draw from? Enter 'a' or 'b': b
How many marbles do you want to remove from heap b? 9
Computer sected to remove 16 from heap aHeapA HeapB
-------------
24 5What heap would you like to draw from? Enter 'a' or 'b': a
How many marbles do you want to remove from heap a? 16
Computer sected to remove 4 from heap aHeapA HeapB
-------------
4 5What heap would you like to draw from? Enter 'a' or 'b': b
How many marbles do you want to remove from heap b? 4
Computer sected to remove 1 from heap aHeapA HeapB
-------------
3 1What heap would you like to draw from? Enter 'a' or 'b': b
How many marbles do you want to remove from heap b? 1
Computer sected to remove 1 from heap aHeapA HeapB
-------------
2 0What heap would you like to draw from? Enter 'a' or 'b': a
How many marbles do you want to remove from heap a? 1
Computer sected to remove 1 from heap a*** Human wins! ***
Part 1: Implement the Subtract a Square game in C
(1) You cannot use library functions other than printf(), scanf(), and sqrt(). Specifically, you *cannot* use rand(), because there is no analogous function in the MIPS simulator or assembly language.
(2) You must provide a Makefile.
(3) Your game must use at least 3 subroutines -- feel free to use more. For example, you could use: random_in_range(low, high), print_game(), user_input()
There is no "C Standard Library" in MIPS. The simulator provides analogous functions for printf() and scanf(), but nothing to generate random numbers. This snippet code of C code from Wikipedia provides an acceptable random number generator for the project. Note that it produces a random 32-bit number, so if you want a random number in a smaller range, use modular division afterwards. Prompt the user for two random numbers to use as seeds (for m_w and m_z), so your program doesn't produce the same random number sequence each time. The m_w and m_z variables should be global, or at least persist after the function finishes. (Otherwise, your random number generator will always produce the same output).
m_w = <choose-initializer>; /* must not be zero */m_z = <choose-initializer>; /* must not be zero */
uint32_t get_random()
{
m_z = 36969 * (m_z & 65535) + (m_z >> 16);
m_w = 18000 * (m_w & 65535) + (m_w >> 16);
return (m_z << 16) + m_w; /* 32-bit result */
}
For the C implementation, you are allowed to use the sqrt() function provided by math.h. Note that this function is provided in the math library, so we have to explicitly tell the linker to look there when creating the final executable. (If you type man sqrt at the command line, you will see this tersely mentioned in the documentation). Unfortunately, the Makefile used in ECPE 170 does not have a nice pre-defined variable where you can specify flags specifically for the linker. You could create one, or just make the change directly by adding in -lm to the linker line, like this:
$(EXECUTABLE): $(OBJECTS)
$(CC) $(OBJECTS) -lm -o $(EXECUTABLE)
You should completely test and debug your C implementation before moving on to Part 2. Assembly programming is slow and tedious. You DO NOT want to have to fix bugs later that were caused by a sloppy C implementation!
Part 2: Implement the Subtract a Square game in MIPS assembly
(1) **Each line** of assembly code must be documented with a comment!
(2) Each region of assembly code must clearly have a **comment block** documenting the overall purpose of that region, along with what values each register holds. You can use your own judgement for a reasonable region size.
(3) Your game must use at least 3 subroutines -- feel free to use more. For example, you could use: random_in_range(low, high), print_game(), user_input()
To reduce the work involved in the MIPS implementation (part 2), you are permitted to replace the computer player with a second human player. This simplification is only for the MIPS part of the assignment. The C implementation must provide all of the features of the full game.
While the MIPS simulator does not provide a square root syscall, the MIPS processor itself does provide a floating-point square root instruction. You will need to copy the original integer from an integer register to a floating-point register, convert the data format from two's complement to IEEE floating-point, invoke the square root operation, convert the data format back from floating-point to integer (losing any fractional values in the process), and then finally copy the value back to an integer register. The entire operation can be done in 5 MIPS instructions.
Tip: In-class discussion during the time period allotted to Lab 11 will discuss (a) generating a random number in assembly and (b) calculating a square root in assembly in more detail. Sample code will be generated on the whiteboard.
Lab Submission:
(1) There is no lab report for this lab.
(2) All source code must be submitted via Mercurial. Place the source files inside the lab11 folder that was previously created.
Optional Feedback:
(Feel free to include a text file with comments/feedback on the lab)
(1) What was the best aspect of this lab?
(2) What was the worst aspect of this lab?
(3) How would you suggest improving this lab in future semesters?
Resources
The MIPS Instruction Set and MIPS Example Programs will be very useful in this project. Don't forget about the H&P Appendix A PDF in Sakai! (It shows the full list of branch instructions)
