| CPSC 220 | Introduction to Computer Architecture | Fall 2008 |
In this lab, you will write a non-trivial program in Larc assembly language. You should review the Larc assembly language handout before starting this lab.
Create a lab09 directory within the ~/cs220 directory that you created in lab 1 for use in this lab. Change to the newly-created lab09 directory. Copy the provided files from the directory /classes/f08/cs220/labs/lab09 to your new lab09 directory. The following commands should work (note: the "-r" in the cp command allows for copying directories as well as files):
bash$ mkdir ~/cs220/lab09 bash$ cd ~/cs220/lab09/ bash$ cp -r /classes/f08/cs220/labs/lab09/* ~/cs220/lab09/
Note: the rest of this lab assumes you are in your lab09 directory.
Your directory should now contain 3 files for assembling, running, and debugging Larc programs: asm, sim, and db. In particular, asm is an assembler for assembling your assembly programs into machine code. For example, to assemble an assembly program called foo.s you would do the following:
bash$ ./asm foo.s
If there were no errors (which would be printed in the shell), this creates a machine code file called foo.out. You can run this assembled program with the following:
bash$ ./sim foo.out
You can also debug your program with db. There are two ways to debug assembly programs: (1) debugging the resulting machine code file or (2) debugging the assembly file directly. You will probably want to debug the assembly file in this lab since you are working in assembly language. Because assembly instructions and datum do not necessarily map one-to-one to machine code instructions and datum, it can be difficult in some places to see how the machine program corresponds to the original assembly program. By debugging the assembly program directly, this is not a problem.
Note: the assembler you will be using in this lab has support for extended instructions. It also allows you to write assembly instructions such as load immediates, branches, and memory instructions with immediates that are too large. In both cases, it maps these to several machine instructions. So feel free to use both of the features.
There is one exercise for this week's lab due next week.
In this exercise, you will write an assembly program for playing the game Nim. The game of Nim is a two-player game, in which some number of beans are laid out and the players alternate turns in which a player can pick up one, two, or three beans. The winner is the player who picks up the last bean. (There are many variations on this game; perhaps you've heard of another version.)
Output from a sample run of the program is shown below. (User input is shown in bold.) Your program's output doesn't have to match this exactly, but your output should be nicely formatted and players should always be referred to by name.
Player 1, enter your name: Arthur Player 2, enter your name: Ford How many beans to start? 21 Arthur, how many beans to pick up? (21 left) 3 Ford, how many beans to pick up? (18 left) 0 number of beans must be 1, 2, or 3 Ford, how many beans to pick up? 2 Arthur, how many beans to pick up? (16 left) 4 number of beans must be 1, 2, or 3 Arthur, how many beans to pick up? 3 Ford, how many beans to pick up? (13 left) 2 Arthur, how many beans to pick up? (11 left) 3 Ford, how many beans to pick up? (8 left) 2 Arthur, how many beans to pick up? (6 left) 2 Ford, how many beans to pick up? (4 left) 2 Arthur, how many beans to pick up? (2 left) 3 can't pick up more beans than are left Arthur, how many beans to pick up? 2 Arthur, you win!
(In Nim, depending on the number of starting beans, either the first player can always win or the second player can always win. Can you figure out why?)
Your task is to write a program called nim.s which allows two players to play Nim.
If you write pseudocode for Nim, you may end up with something like the following:
get player 1's name from the user
get player 2's name from the user
get the number of beans to start with from the user
while there are beans left
display the number of beans remaining
get the number of beans player 1 wants to pick up
while player 1 has picked an invalid number of beans
remind player 1 of the rules for picking up beans
get the number of beans player 1 wants to pick up
if player 1 has won the game
print out a congratulatory message
else
display the number of beans remaining
get the number of beans player 2 wants to pick up
while player 2 has picked an invalid number of beans
remind player 2 of the rules for picking up beans
get the number of beans player 2 wants to pick up
if player 2 has won the game
print out a congratulatory message
Now, you may notice that the pseudocode for player 1's turn is very similar to the pseudocode for player 2's turn - the only thing that is different is which player is playing. As you would probably do if you were writing this in Java, you will create a separate assembly subroutine, which carries out one turn (note: this is a requirement).
Here is the pseudocode for that subroutine:
display the number of beans remaining
get the number of beans the player wants to pick up
while the player has picked an invalid number of beans
remind the player of the rules for picking up beans
get the number of beans the player wants to pick up
Keep in mind that a player can't pick up more beans than are available - picking up two beans when only one is left shouldn't be allowed.
So you will essentially have an assembly program with two subroutines. The first subroutine is your main subroutine (like the main method in Java) that prompts for the initial names and number of beans, then continuously plays the game until it is over, and finally, prints a congratulatory message to the appropriate player. The second subroutine plays a particular turn and returns the number of beans that were picked up.
When you write these two subroutines you will need to be careful in how you place them in the .text section. Unlike high level languages such as Java, you do not have the freedom to place them where ever you would like. In particular, the main subroutine must always be put first in the .text section since it must be executed at the start of the program (the first instruction in .text is the first instruction executed). The turn subroutine will also need a label at the beginning of the subroutine so that it can be called (via a jump instruction) from the main subroutine. The main subroutine does not need a label at its start since it is not called by any other subroutine. You must also be careful that you terminate each subroutine. For the main subroutine, at the end of the subroutine you will probably want to exit the program. For the turn subroutine, you obviously do not want to exit the program. In this case, you will need to use a jump instruction to return back into the main subroutine at the appropriate point. In order to return back to main, you will need to keep the return address stored in some register and make sure that it is not overwritten.
You will also need to think carefully in other ways when writing these two subroutines. First, there are no local variables at the assembly level, there are just registers and memory, which is shared by all subroutines. So, for example, you will need to be careful about which subroutines are using which registers (so that one subroutine doesn't overwrite a value in a register used by the other subroutine). You will also need to think carefully about the parameters and return values for the turn subroutine and how they will be passed from the main subroutine. For example, the turn subroutine needs to know which player's turn it is and how many beans are remaining. You might pass these via registers $2 ($a0) and $3 ($a1). The turn subroutine also has to pass back the number of beans picked up. You might return this value in register $1 ($v0). But feel free to use any approach you would like so long as it works correctly.
In addition, feel free to add other subroutines if you would like. You also do not have to follow the pseudocode shown above explicitly. The two requirements are (1) that it works correctly and (2) you have two subroutines main and turn, which follow the specifications discussed above.
Verify that your lab09 folder contains all of the files you created or modified for this lab (e.g., nim.s), then copy your entire lab09 folder to the handin directory ~mcorliss/handin/cs220/username (where username is replaced with your username). For example, if your working directory is ~/cs220/lab09/ then you could do the following:
cp -r ~/cs220/lab09 ~mcorliss/handin/cs220/username
where username is replaced with your particular username (e.g., mcorliss).