Homework 6 -- SnakeOS
CSE240 - Introduction to Computer Architecture
Autumn 2006

Due: Friday, November 3rd, 2006 at 11:59pm

Finally! Let's get to writing Snake. In the next two assignments, you will build a working game from the ground up. This first assignment consists of creating the SnakeOS, the operating system that will handle all of the I/O routines for Snake. The next assignment consists of writing the game logic.

The operations that a program can ask the operating system to perform are: (1) drawing a rectangle on the screen, (2) checking the color of a pixel, (3) generating a random number, and (4) checking for keyboard and timer input. These operations are the fundamental pieces that allow us to build up more complex functionalities in the next assignment. User-level (non-privileged) programs invoke these four operating systems operations using the TRAP instruction. As such, the code you write in this assignment will be in the form of trap handling routines.

Background Information

Some important background information for this assignment:

Important files:All of the files you'll need for the assignment are available in a hw6code.zip Zip archive. You can also view the snakeos.asm template file.

Video console interface: The video console is directly linked to a region of addressable memory, namely xC000 to xFDFF. Every row is 128 dots (also called pixels) across, and there are 124 rows in total, which gives us a 128x124 screen to work with. Each pixel is linked to one memory address, so xC000 is the pixel on the top left corner, xC001 is the pixel to the right of it, and so on. Since 128 is x0080 in hex, xC000 + x0080 = xC080 is the location of the leftmost pixel on the second row from the top, and xC000 + 2*x0080 = xC100 would be the next pixel down. In general, you can use the following formula to calculate which address of a pixel:

    address = xC000 + (y_coordinate * 128) + x_coordinate

Color encoding: Each location holds a 16-bit value which determines the color of that pixel. The high-order bit is ignored, and the remaining 15 bits specify the color, using a 5-bit values for each of red [14:10], green [9:5], and blue [4:0].

Coordinate systems: This code uses just the video console coordinates. This system is zero based (that is, the top-most row is row 0 and the left-most column is column 0). Thus, if you start your rows and columns at 1, you'll be off by quite a bit by the time you're done.

New instructions:We've added some new instructions to the LC-3 to make writing LC-3 code easier.

Register Saving/Restoring: You will notice, in the stubs provided in snakeos.asm that each trap begins with a register saving section and ends with a register restoring section. This saving and restoring is done because the caller expects register values to be preserved when the trap returns. Because no traps call each other recursively, we won't have to worry about the values saved being overwritten.

Memory-mapped Timer:We've extended the LC-3 architecture with a timer device, so we can actually know when to move the snakes! This timer, as with the other I/O devices like the keyboard or display, is memory-mapped. Initially, the Timer Status Register (TSR) is set to 0. Every time the timer goes off, the TSR is set to 1. When any instruction reads from the TSR, it resets itself back to 0 until the next time the timer expires.

There is also a second register associated with the timer that can be useful. The Timer Interval Register (TIR) tells the simulator how short or long the timer interval is. In fact, it specifies the amount of time in milliseconds between each timer clock tick. However, there is a special case; if the register contains the value 0, then the timer will never expire and hence is disabled. Disabling the timer is useful when debugging.

Operating System Template: We're giving you a basic operating system template to which you can add your code. The template is called snakeos.asm. Based on this template, your implementation of the SnakeOS operating system will have three sections. Of these three sections you'll only need to modify the third and final section.

  1. The TRAP/interrupt vector table: The TRAP vector table is the first 256 16-bit location in memory that determines the next PC when a TRAP instruction is called. This table begins at memory location x0000. Immediately following the TRAP vector table is the 256-entry interrupt vector table (which we won't be using in this project, but we need to leave space for it).
  2. System initialization code: The portion of memory immediately following the vector tables is the system initialization code. The start of this portion of memory (memory location x0200) is the initial PC when the processor is first started. Thus, after loading the operating system into the LC-3 simulator, when you press "continue", the execution will commence from 0x0200. The code present in the template sets the memory protection register and jumps to PC x3000. This location marks the start of the unprivileged user-level program. For this assignment, the user-level program are simple test programs; in the next assignment, the user-level programs will be the Pentris game code.
  3. TRAP routines: The next portion of memory contains the code for reacting to each of the four TRAP routines supported by SnakeOS:

    Each of the trap routines starts with a prolog (which saves the current value of all the registers) and ends with an epilogue (which restores the original register values and invokes the Return from Trap (RTT) instruction).

Input Range Checking: While it's generally necessary to error check strenuously when programming, for the purposes of this assignment you are not required to do any out of bounds checking on the input arguments.

Official Test Scripts: To use each official test script, first assemble the asm test file associated with the part, then open up the simulator and run "script p#-test#.lcs", replacing the two # with the part number and the test number. You can run all the tests by running "script all-test.lcs". Important: The test scripts we're giving you are NOT exhaustive tests; they are only to get you started. For grading, we'll make additional test cases that were not covered in the test cases we gave you.

Turnin: The only file you need to turn in is your version of the snakeos.asm file. Similar as before, do the following:

    turnin -c cse240 -p hw6 snakeos.asm

TRAP Routine Descriptions

For this assignment you will implement the four of the trap routines that constitude the SnakeOS. Each trap handler is described, below.

Part 1: Draw Block (trap x40)

The first part of this assignment is writing LC-3 code to draw a 4x4 block of pixels with a specified color. Because the block sizes are 4 by 4, for both this and the next part, to map the game field row/column to the video memory row/column, simply multiply the game field row/column number by 4 then add to it the starting row/column number. This formula is used in the pseudocode below. You then need to map the video memory coordinates to the actual address of the pixel so that you can actually "draw" that pixel. As the video display is 128 pixels horizontally and 124 pixels vertically, this corresponds to 32 horizontal blocks and 31 vertical blocks. Assume that x, y, and color are given, and that x and y are game field coordinates.
  vid_x = 4*x;
  vid_y = 4*y;
  for (r=0; r<=3; r=r+1)
        vid_mem_addr = xC000 + ((vid_y + r) * 128) + vid_x;
        set memory at vid_mem_addr to color;
        set memory at vid_mem_addr+1 to color;
        set memory at vid_mem_addr+2 to color;
        set memory at vid_mem_addr+3 to color;
Write the LC-3 code for the above pseudocode assuming that x is in R0, y is in R1, and the color is in R2. The following LC-3 assembly declarations have been included in the snakeos.asm skeleton code; you may find them helpful:
; Video Memory Constants

To test whether this code is working, first run the scripts we've provided. Then, if you would like to test further, try setting a breakpoint to the beginning of the trap. Once the program execution breaks there, set R0 and R1 to various values and R2 to a bright enough color to be seen (x7FFF, white, is recommended). By altering values of R0 and R1, you should be able to see white blocks showing up on the video memory. Unfortunately, to compute precise locations to check, you'll have to do the math to compute the address corresponding to where each block is supposed to go.

Part 2: Get Block Color (trap x41)

In addition to being able to draw a block, we also want to be able to query the current color of a block on the screen. For example, we'll use this ability in the next assignment to detect collisions. Thus, the second part of this assignment is to write the LC-3 code to do just that.

The code for querying the color of a block is conceptually similar to the coded in the previous part. Once again, you'll need to map game coordinates to video memory coordinates. However, this time you'll only need to access the top left corner of the block, because we can assume the entire block is a single color.

Assume that row and col are given in game field coordinates.

  vid_x = 4*x;
  vid_y = 4*y;
  vid_mem_addr = xC000 + (vid_y * 128) + vid_x;
  put content at vid_mem_addr into R5;
Write the LC-3 code for the above pseudocode assuming that x is in R0 and y is in R1. The code must place into R5 the 16-bit value that encodes the current color of the specified block.

Testing this involves doing the reverse of Part 1: put a color in some block on the screen, then run the trap with that location as the input.

Part 3: Random Number (trap x43)

In the next assignment, there will be several points where we would like to have random events occur (i.e. apple placement or evil snake AI desicions). The process of generating random numbers is suprisingly difficult for computers. For simplicity of the assignment, we will implement a random number routine which simply iterates through a list of preconstructed pseduorandom numbers. This will be sufficient for our purposes.
    R_POS := R_POS + 1
    if R_POS >= R_SIZE
       R_POS := 0
    R5 := Memory[R_START+R_POS]
Some local variables and the list of numbers is included in the skeleton.
R_POS:   .FILL 0                ; initially zero
R_SIZE:  .FILL x19
R_START: .FILL x35FE            ; Array of "random" numbers
         .FILL x342D
         .FILL x26D3
         .FILL xDE45
         .FILL xF56E
         .FILL xBFD4
         .FILL xDE31
         .FILL x25DE
         .FILL xFF45
         .FILL x34ED
         .FILL x12E9
         .FILL x82AB
         .FILL x08E4
         .FILL x5400
         .FILL xED25
         .FILL x346E
         .FILL x2300
         .FILL x3644
         .FILL x1AE4
         .FILL x85D4
         .FILL xED48
         .FILL x347D
         .FILL x1234
         .FILL x4842
         .FILL xADEF

Part 4: Get Event (trap x42)

The final part of this assignment is writing LC-3 code to handle the input for the snake game. The input determines if the snake should move left, right, up, or down. Don't worry about how these are implemented just yet, we will first focus on how to report the events when they do happen. We're not (yet) writing code to move the snakes; we are simply detecting events.

Our game of snake uses two types of inputs to trigger these movements: (1) a hardware timer and (2) the keyboard. The timer is designed to tick on a regular interval. When it does, a "move forward" command will be issued. The keyboard, on the other hand, is harder to deal with. When a key is pressed, you must check through each key that signifies an event, for example the "a" key to issue a command to move the snake left. If the key pressed doesn't match any event keys, then ignore it and keep polling for input. Basically, the game will just sit in a loop waiting for a command or the timer tick before doing anything.

The trap handler you will write will return a value (in register R5) indicating what event has taken place. Note that your handler will not return until some event happens. If the timer goes off (i.e., TSR takes on a non-zero value), we return 0 (in R5) indicating that the snakes should move. If the user presses the 'a' key, we return 1 (in R5) indicating that the user wants to move the snake to the left. If the user presses the 'd' key, we return 2 (in R5) indicating that the user wants to move the snake to the right, etc. If the user presses the '*' key, we return -1 (in R5) indicating that the user wants to quit the game.

To handle the timer, when TSR becomes non-zero, we know the timer has expired and we return the appropriate value. Reading TSR automatically resets it back to zero. The keyboard is a little trickier. We must first determine when a key is pressed (via KBSR). When a key is pressed we must fetch it (via KBDR) and check it against all the keys we are interested in (see below). When we find a match, we return the appropriate value. Otherwise, we continue polling the TSR and KBSR. Important Note: Please note that the LC-3 terminal output window (the lower-left of the simulator window) must be the active window for the keystrokes to be sent to the keyboard device in the simulator. That is, click on the terminal window to make it active before typing characters intended for the simulated keyboard device. The window will be highlighted yellow when keyboard input is active.

The events each correspond to an integer value, so that value will be what you report (i.e., return) in R5:

The pseudocode:
    x := OS_TSR
    if x != 0
        R5 := 0       ; Timer
        goto done     ; break out of the loop

    x := OS_KBSR
    if x == 0
        goto loop     ; continue with the next iteration

    x := OS_KBDR

    if x == LEFT_KEY
        R5 := 1       ; Left
        goto done     ; break out of the loop

    if x == UP_KEY
        R5 := 2       ; Up
        goto done     ; break out of the loop

    if x == RIGHT_KEY
         R5 := 3      ; Right
         goto done    ; break out of the loop

    if x == DOWN_KEY
         R5 := 4      ; Down
         goto done    ; break out of the loop

    if x == QUIT_KEY
         R5 := -1     ; Quit
         goto done    ; break out of the loop

    goto loop         ; continue with the next iteration
The exact keys and input locations should be specified in memory using the following LC-3 assembly code:
; Input key ASCII codes
LEFT_KEY        .FILL x0061     ; Left - 'a'
UP_KEY          .FILL x0077     ; Up - 'w'
RIGHT_KEY       .FILL x0064     ; Right - 'd'
DOWN_KEY        .FILL x0073     ; Down - 's'
QUIT_KEY        .FILL x002A     ; Quit - '*'

; Addresses of various registers
OS_KBSR .FILL xFE00             ; keyboard status register 
OS_KBDR .FILL xFE02             ; keyboard data register 
OS_TSR  .FILL xFE08             ; timer status register 
OS_TIR  .FILL xFE0A             ; timer interval register 

This part is the hardest to write a script for, but the easiest to test by hand. When testing manually, all you have to do is set a good time interval for the timer, run the trap, and see if it returns correctly when the timer goes off. To test the keyboard stuff, set the TIR to 0 to disable the timer and check if the keys correspond correctly to the return values. Make sure that unrecognized keys don't cause the loop to break!

Each script for this part involves two files: p5-test#.lcs and p5-test#.in. The former will take care of setting the registers and checking values, while the latter is the actual sequence of simulated keystrokes. If you want to create your own test scripts for this part, you will need to do something similar.

Your Assignment

Implement and test the four TRAPs described above using the snakeos.asm template as a starting point.