Department of Electrical and Computer Engineering
The University of Texas at Austin

EE 306 Fall 2002
Yale Patt, Instructor
TAs: Asad Bawa, Linda Bigelow, Mustafa Erwa, Lester Guillory, Kevin Major,
Moinuddin Qureshi, Paroma Sen, Tanay Shah, Santhosh Srinath,
Matt Starolis, David Thompson, Vikrant Venkateshwar

Programming Assignment 5 (Assembly Language) UPDATED 11.26.2002
Due December 6, 2002 at 11:59pm

1. Introduction
Ever had a couple of minutes to spare? We all have. Chances are, during many such moments as a child, you decided to play a game. One of the most popular such "time filler" games is Tic-Tac-Toe. This simple two-player game has even been used as the basis for a popular television show called Hollywood Squares.

In this assignment, you will use the principles of subroutine call and return. Using the high-level flow chart given in section 3, you will implement an ASCII Tic-Tac-Toe game for the LC-2. In section 4 we provide you with some assembly code to help you get started.

2. Rules
Tic-Tac-Toe is a two-player game with two symbols denoting the two players: X and O. The playing board is a 3x3 square.

The rules are as follows:

• Each player takes a turn placing his character (X or O) into one of the nine squares.
• A player cannot place his symbol in a square that is already occupied by a symbol.
• The game ends when a player creates a winning combination of his symbols or when there are no empty squares remaining.
• Winning combination is defined as three horizontally adjacent, three vertically adjacent, or three diagonally adjacent symbols.
• If neither player creates a winning combination when all nine squares are occupied, the game is a draw, often referred to as a "cat game."

3. Algorithm
In order to design a Tic-Tac-Toe game, or any other software project, we must break the problem into small pieces. To this effect, we have created the following flow chart for Tic-Tac-Toe.

You will use this flowchart as the basis for designing the program. The blocks that you must implement are in bold.

4. What to do
The following starter code provides a general framework for the Tic-Tac-Toe game, plus a single subroutine called EVALBOARD.
Your job is to complete the Tic-Tac-Toe game by writing the following four subroutines

• GETVALIDINPUT
1. Getting input from the user (this input is returned to the caller in register R1)
2. Performing error checking on the input

The only valid input during the Tic-Tac-Toe game is a number 1-9, or the letter 'q'.
You should prompt the player for input with the following prompt:
```     "X - Which square? [1-9] "
"O - Which square? [1-9] "
```
If the player does not enter a valid input, you should print the following message to the screen
```     "Invalid input"
```
and again prompt the player to choose a square.

If the player chooses a square which is already occupied, you should print the message
```     "Space occupied"
```
and again prompt the player to choose a square.

The ASCII code of the valid input character must be returned in register R1.

• UPDATEBOARD
When this subroutine is called, R1 contains the ASCII code for a numeric character 1-9, which you previously have provided in GETVALIDINPUT.
The player, X or O, is defined by the contents of the memory location labeled PLAYER, which is initially set to 1.
```Memory[PLAYER] = 1 for player X
0 for player O
```
You should update the Tic-Tac-Toe board in memory by writing an X or O into the square designated by the value in R1. You must also update the contents of location PLAYER after updating the board.

• DRAWBOARD
This subroutine simply prints the Tic-Tac-Toe board to the screen.

• PRINTOUTCOME
When this subroutine is called, R1 contains a value indicating the outcome of the game. This value is provided by the EVALBOARD subroutine.
1 = X wins
2 = O wins
3 = Cat Game
You should print one of the following messages based on the value in R1.
```     "X wins!"
"O wins!"
"Cat Game!"
```
We have provided for you the EVALBOARD subroutine which evaluates the playing board.
• EVALBOARD
This code examines the nine squares and returns a value in register R1 according to the following:
```      R1 = 0     Game still in progress
1     X wins
2     O wins
3     Cat Game (no winner)
```
It is a very good idea to go through the EVALBOARD subroutine and verify for yourself that it actually works. Doing so will provide some useful hints on how to construct the other subroutines.

5. Guidlines

• The squares on the board are numbered sequentially, starting from the top-left corner as shown below:

• ```        |   |
1 | 2 | 3
|   |
-----------
|   |
4 | 5 | 6
|   |
-----------
|   |
7 | 8 | 9
|   |
```

• X always goes first. This is especially important for grading!

• In each subroutine you write, you should save and restore any registers that you use. This will avoid a major headache during debugging.

6. Page Boundary
The code we have provided you starts at location x3000. You will notice that we have added a .BLKW pseudo-op to add blank space in the program up to address x31FF. Starting at location x3200, we have provided several useful .FILL pseudo-ops for you to use in your solution.

All of your subroutines will be stored in memory on page x19 of memory (page x19 starts with address x3200). Towards the end of page x18 in the code, you'll see a jump table, which is a table of the starting addresses of all the subroutines you must implement. You must populate this table.

Recall that if you attempt to use symbols on one page of memory that were defined on a different page, the LC-2 Editor will not assemble your program. This problem is due to the fact that the LD, ST, BR, and many other instructions only store the 9-bit page offset of the address they are loading from, storing to, or branching to during execution. This is why we are using the JSRR instruction in the main section of the program instead of the JSR instruction.

In order to figure out what value to put in the .FILL pseudo-ops in the jump table, you will look at the program listing produced by the LC-2 Editor at assembly time. This file has the extension ".lst" and contains the machine code, assembly code, symbols, and address information for your entire program.

Note: when you assemble a program that crosses a page boundary, the LC-2 Editor gives you a warning, but still correctly assembles the program.

7. Sample Input
Remember, X always goes first. You may test your game with the following inputs:

```    InputString          OutputString
---------------      ------------
1 4 2 5 7 6          O wins!
5 4 3 1 7            X wins!
1 2 3 7 8 9 4 5 6    Cat Game!
```

8. Submission Instructions
--Instructions for submission are posted on the course homepage.