Due Date and Submission Method On or before Monday, March 25, 2024 and upload the source code (no documentation needed) to the section of “COVID-19 Exams, Homeworks, & Programming Exercises” of Blackboard. †Though Exercise II covers parts of Exercise I, you still have to submit both exercises separately. One exercise will not be counted twice. Objective Design and implement a MIPS assembly program, which plays a tic-tac-toe game. The final program is less than 200 lines. The purpose of this exercise is to make students practice assembly language programming including functions, various control instructions, and the runtime stack. |
syscall
of MARS to randomly pick the system (x) or the user (o) to start the game.
syscall
32, sleep, of MARS to slow down the system’s move.
syscall
of MARS to randomly pick the next move for the system and the move has to be valid and shown (1..9).
| | 1|2|3 ----- ----- | | 4|5|6 ----- ----- | | 7|8|9Mark the move by using the index board. For example, if the first move is ‘5’ from the system, the board is displayed as follows:
| | 1|2|3 ----- ----- |x| 4|5|6 ----- ----- | | 7|8|9
| | 1|2|3 ----- ----- | | 4|5|6 ----- ----- | | 7|8|9the instructor uses the following string:
board: .ascii "\n | | 1|2|3\n ----- -----" .ascii "\n | | 4|5|6\n ----- -----" .asciiz "\n | | 7|8|9\n" # (offset) 0 123456789012345678901 23456789012345678901where the numbers are offsets (not assembly code) and the new line, ‘\n’, is one byte long. The offset of the move (1-9),
$a0
, is found by using the following formula:
offset = $a0×2 + 3 + [($a0-1)÷3]×36For example, if the move is 5, the offset is
5×2+3+[(5-1)÷3]×36=13+1×36=49
lw $t0, offset # Load $t0 with the offset. li $t1, 'x' # Load $t1 with the marker 'x'. sb $t1, board($t0) # Store the marker to the location, board+offset.Assuming the game just started, the game board will be as follows after entering the move 5 from the system:
| | 1|2|3 | | 1|2|3 ----- ----- ----- ----- | | 4|5|6 ⇒ |x| 4|5|6 ----- ----- ----- ----- | | 7|8|9 | | 7|8|9
won: .ascii "234759 " # 1 .ascii "1358 " # 2 .ascii "125769 " # 3 .ascii "1756 " # 4 .ascii "19283746" # 5 .ascii "3945 " # 6 .ascii "143589 " # 7 .ascii "2579 " # 8 .ascii "153678 " # 9where each two characters are the other two locations of the three pieces in a line. For example, the move ‘7’ has the following winning combinations “
143589
”:
x| |x 1|2|3 ----- ----- x|x| 4|5|6 ----- ----- x|x|x 7|8|9The following program checks whether the next move wins the game. To make the script simple, the game is fixed and only the move ‘7’ wins the game.
CheckWinning.asm
|
# ############# Checking a Winning Combination of Tic-Tac-Toe Game ############# # .data p1: .asciiz "\n\nEnter your move: (0..z) " p2: .asciiz "\nYou won!\n" board: .ascii "\n | |x 1|2|3\n ----- -----" .ascii "\n |x| 4|5|6\n ----- -----" .asciiz "\n | | 7|8|9\n" won: .ascii "234759 " # 1 .ascii "1358 " # 2 .ascii "125769 " # 3 .ascii "1756 " # 4 .ascii "19283746" # 5 .ascii "3945 " # 6 .ascii "143589 " # 7 .ascii "2579 " # 8 .ascii "153678 " # 9 .text .globl main # ########################## Main Program ####################### # main: la $a0, board li $v0, 4 syscall # Print the game board. la $a0, p1 li $v0, 4 syscall # Print the prompt. # Read the next move. li $v0, 5 # Read a move (1..9). syscall # The syscall 5 is read an integer. move $s0, $v0 move $a0, $v0 # a0: the move in integer jal MarkMove # Call the subroutine MarkMove. # Check the winning combination. move $a0, $s0 # $a0: the current move jal EndGame la $a0, board li $v0, 4 syscall # Closing up li $v0, 10 # Exit. syscall # ######################### Mark a Move ######################### # # Input: $a0 (the move in integer) # Output: the game board marked MarkMove: # Save data in the runtime stack. subu $sp, $sp, 4 # Decrement the $sp to make space for $ra. sw $ra, ($sp) # Push/save the return address, $ra. # Find the offset $v0 = a0x2+3+[(a0-1)/3]x36 jal GetOffset # Mark the board. li $t1, 'x' # Put the piece ‘x’ in $t1. sb $t1, board($v0) # Put the piece at the location, board+offset. # Restore the data from the runtime stack. lw $ra, ($sp) # Pop/restore the return address, $ra. addu $sp, $sp, 4 # Increment the $sp. jr $ra # Return. # ######################### Get the Offset ######################### # # Input: $a0 (the move in integer, 1..9) # Output: $v0 (the offset of the marker in the board) GetOffset: # Save data in the runtime stack. subu $sp, $sp, 4 # Decrement the $sp to make space for $ra. sw $ra, ($sp) # Push/save the return address, $ra. subu $sp, $sp, 4 # Decrement the $sp to make space for $t0. sw $t0, ($sp) # Push/save the $t0. subu $sp, $sp, 4 # Decrement the $sp to make space for $t1. sw $t1, ($sp) # Push/save the $t1. # Find the offset $v0 = a0x2+3+[(a0-1)/3]x36 mul $t0, $a0, 2 add $t0, $t0, 3 move $t1, $a0 sub $t1, $t1, 1 div $t1, $t1, 3 mul $t1, $t1, 36 add $v0, $t0, $t1 # Restore the data from the runtime stack. lw $t1, ($sp) # Pop/restore $t1. addu $sp, $sp, 4 # Increment the $sp. lw $t0, ($sp) # Pop/restore $t0. addu $sp, $sp, 4 # Increment the $sp. lw $ra, ($sp) # Pop/restore the return address, $ra. addu $sp, $sp, 4 # Increment the $sp. jr $ra # Return. # ######################## Check End of game. ############################ # # Input: $a0 (the move in integer, 1 .. 9) # Output: Declare the winning if won. EndGame: subu $sp, $sp, 4 sw $ra, ($sp) # Push the return address, $ra. li $t2, 1 # Count for 4 lines or 8 bytes. li $t3, 2 # 2 more piece in a line sub $a0, $a0, 1 # $a0 = $a0 - 1 mul $t1, $a0, 8 # t1: offset of the winning combination L30: lb $a0, won($t1) beq $a0, ' ', L32 sub $a0, $a0, '0' # Convert to integer. jal GetOffset lb $t4, board($v0) bne $t4, 'x', L31 # Go to L31 if not 'x' sub $t3, $t3, 1 # Check the next location. add $t1, $t1, 1 bge $t3, 1, L30 la $a0, p2 # Won li $v0, 4 syscall j L32 L31: add $t1, $t1, $t3 # Check the next combination. li $t3, 2 add $t2, $t2, 1 ble $t2, 4, L30 L32: lw $ra, ($sp) # Pop the return address, $ra. addu $sp, $sp, 4 jr $ra # Return. |
syscall
of MARS such as:
xor $a0, $a0, $a0 # Set a seed number. li $a1, 8 # random number 0 to 8 li $v0, 42 # random number generator syscall # The random number is in $a0. add $a0, $a0, 1 # The number in 1..9Sample code of generating a random move is given below for your reference:
RandomMove.asm
|
# ###################### Generating a Random Move ###################### # # Input: # Output: $v0 (integer move), $v1 (integer offset) # RandomMove: subu $sp, $sp, 4 # Decrement the $sp to make space for $ra. sw $ra, ($sp) # Push/save the return address, $ra. subu $sp, $sp, 4 # Decrement the $sp to make space for $t0. sw $t0, ($sp) # Push/save the $t0. subu $sp, $sp, 4 # Decrement the $sp to make space for $t1. sw $t1, ($sp) # Push/save the $t1. R1: xor $a0, $a0, $a0 # Set a seed number. li $a1, 9 # random number from 0 to 8 li $v0, 42 # random number generator syscall # The random number is in $a0. add $a0, $a0, 1 # The number in 1..9 move $t0, $a0 jal GetOffset # input: $a0 (move); output: $v1 (offset) lb $t1, board($v1) bne $t1, ' ', R1 # Go to R1 if the cell is not empty. move $v0, $t0 # $v0: the move in integer lw $t1, ($sp) # Pop/restore $t1. addu $sp, $sp, 4 # Increment the $sp. lw $t0, ($sp) # Pop/restore $t0. addu $sp, $sp, 4 # Increment the $sp. lw $ra, ($sp) # Pop the return address, $ra. addu $sp, $sp, 4 # Increment the $sp. jr $ra # Return. |
syscall
32, sleep, to slow down the system’s move.
routine1
is given as follows:
jal routine1 # Jump and link to routine1 next: ...where the label
next
is not required.
The following command in the subroutine routine1
will return the control back to the next
, the next command after the jal routine1
”:routine1: ... jr $ra # Jump to the contents of $rawhere the return address is saved in the register
$31
or $ra
$31
or $ra
, has to be saved before making the call.
The return address is restored after the called subroutine returns.
The instructor uses the runtime stack to save the return addresses, so deep subroutine calls are supported.
Use the following two commands to push the $ra
to the runtime stack:
subu $sp, $sp, 4 # Decrement the $sp to make space for $ra. sw $ra, ($sp) # Push the return address, $ra.and use the following two commands to pop up the
$ra
from the runtime stack:
lw $ra, ($sp) # Pop the return address, $ra. addu $sp, $sp, 4 # Increment the $sp.You may also use the runtime stack to save the register and variable values.
Examples of Exercise 2 Execution |
---|
Start Playing a Tic-tac-toe Game. | | 1|2|3 ----- ----- | | 4|5|6 ----- ----- | | 7|8|9 Enter the next move (1-9): 4 | | 1|2|3 ----- ----- o| | 4|5|6 ----- ----- | | 7|8|9 My turn: 3 | |x 1|2|3 ----- ----- o| | 4|5|6 ----- ----- | | 7|8|9 Enter the next move (1-9): 6 | |x 1|2|3 ----- ----- o| |o 4|5|6 ----- ----- | | 7|8|9 My turn: 8 | |x 1|2|3 ----- ----- o| |o 4|5|6 ----- ----- |x| 7|8|9 Enter the next move (1-9): 5 | |x 1|2|3 ----- ----- o|o|o 4|5|6 ----- ----- |x| 7|8|9 You won! New game? (y/n) y Start Playing a Tic-tac-toe Game. | | 1|2|3 ----- ----- | | 4|5|6 ----- ----- | | 7|8|9 My turn: 5 | | 1|2|3 ----- ----- |x| 4|5|6 ----- ----- | | 7|8|9 Enter the next move (1-9): 3 | |o 1|2|3 ----- ----- |x| 4|5|6 ----- ----- | | 7|8|9 My turn: 1 x| |o 1|2|3 ----- ----- |x| 4|5|6 ----- ----- | | 7|8|9 Enter the next move (1-9): 6 x| |o 1|2|3 ----- ----- |x|o 4|5|6 ----- ----- | | 7|8|9 My turn: 9 x| |o 1|2|3 ----- ----- |x|o 4|5|6 ----- ----- | |x 7|8|9 I (the system) won! New game? (y/n) y Start Playing a Tic-tac-toe Game. | | 1|2|3 ----- ----- | | 4|5|6 ----- ----- | | 7|8|9 My turn: 9 | | 1|2|3 ----- ----- | | 4|5|6 ----- ----- | |x 7|8|9 Enter the next move (1-9): 5 | | 1|2|3 ----- ----- |o| 4|5|6 ----- ----- | |x 7|8|9 My turn: 1 x| | 1|2|3 ----- ----- |o| 4|5|6 ----- ----- | |x 7|8|9 Enter the next move (1-9): 7 x| | 1|2|3 ----- ----- |o| 4|5|6 ----- ----- o| |x 7|8|9 My turn: 3 x| |x 1|2|3 ----- ----- |o| 4|5|6 ----- ----- o| |x 7|8|9 Enter the next move (1-9): 6 x| |x 1|2|3 ----- ----- |o|o 4|5|6 ----- ----- o| |x 7|8|9 My turn: 4 x| |x 1|2|3 ----- ----- x|o|o 4|5|6 ----- ----- o| |x 7|8|9 Enter the next move (1-9): 2 x|o|x 1|2|3 ----- ----- x|o|o 4|5|6 ----- ----- o| |x 7|8|9 My turn: 8 x|o|x 1|2|3 ----- ----- x|o|o 4|5|6 ----- ----- o|x|x 7|8|9 We are tied! New game? (y/n) n -- program is finished running -- |
No. | Directive | Description | |
---|---|---|---|
1 | .ascii "string" |
Allocating space for string | |
2 | .asciiz "string" |
Allocating space for string, NULL terminated | |
3 | .byte |
Allocating space for a byte | |
4 | .data |
Beginning of data section | |
5 | .globl name |
Making the following name be a global symbol | |
6 | .space n |
Allocating n bytes of space |
|
7 | .text |
Beginning of text section | |
No. | Instruction | Operation | Description |
1 | add rd, rs, rt |
rd = rs + rt |
Add;rd : destination register, rs : first source register, and rt : second source register or immediate value.Check MIPS Registers and Usage Convention. |
2 | addu rd, rs, rt |
rd = rs + rt (no overflow) |
Add unsigned |
3 | beq rs, rt, label |
if rs==rt then goto label |
Branch if equal to |
4 | bge rs, rt, label |
if rs≥rt then goto label |
Branch if greater than or equal to |
5 | bgt rs, rt, label |
if rs>rt then goto label |
Branch if greater than |
6 | ble rs, rt, label |
if rs≤rt then goto label |
Branch if less than or equal to |
7 | blt rs, rt, label |
if rs<rt then goto label |
Branch if less than |
8 | bne rs, rt, label |
if rs≠rt then goto label |
Branch if not equal to |
9 | bnez rs, label |
if rs≠0 then goto label |
Branch if not equal to zero |
10 | div rd, rs, rt |
rd = rs ÷ rt |
Divide |
11 | j label |
jump to label |
Jump |
12 | jal label |
jump to label and save the return address in $31 |
Jump and link |
13 | jr rs |
jump to [rs] ; [ ]: contents of |
Jump register |
14 | la rd, mem |
rd = address( mem ) |
Load address |
15 | lb rd, mem |
rd = mem |
Load byte |
16 | li rd, imm |
rd = imm |
Load immediate |
17 | lw rd, mem |
rd = mem |
Load word |
18 | move rd, rs |
rd = rs |
Move register |
19 | mul rd, rs, rt |
rd = rs × rt |
Multiply |
20 | sb rs, mem |
mem = rs |
Store byte |
21 | sub rd, rs, rt |
rd = rs - rt |
Subtract |
22 | subu rd, rs, rt |
rd = rs - rt (no overflow) |
Subtract unsigned |
23 | sw rs, mem |
mem = rs |
Store word |
24 | syscall |
|
System call; check System Services. |
25 | xor rd, rs, rt |
rd = rs xor rt |
Bitwise exclusive or |
Service | Code in $v0 |
Arguments | Result |
---|---|---|---|
print_int | 1 | $a0 = integer to be printed |
|
print_float | 2 | $f12 = float to be printed |
|
print_double | 3 | $f12 = double to be printed |
|
print_string | 4 | $a0 = address of string in memory |
|
read_int | 5 | integer returned in $v0 |
|
read_float | 6 | float returned in $v0 |
|
read_double | 7 | double returned in $v0 |
|
read_string | 8 | $a0 = address of string input buffer$a1 = length of string buffer (n ) |
|
malloc | 9 | $a0 = amount |
address in $v0 |
exit | 10 | ||
print character | 11 | $a0 = character to be printed |
|
read character | 12 | character returned in $v0 |
|
sleep | 32 | $a0 = the length of time to sleep in milliseconds. |
Causes the MARS Java thread to sleep for (at least) the specified number of milliseconds. |
random int range | 42 | $a0 = i.d. of pseudorandom number generator (any int).$a1 = upper bound of range of returned values. |
$a0 contains pseudorandom, uniformly distributed int value
in the range 0 ≤ [int] < [upper bound], drawn from this random number generator’s sequence. |