Homework 6
CSE240 - Introduction to Computer Architecture
Autumn 2004

Due: Thursday, Nov. 4th at 11:59pm

Welcome to Tetr.. er.. Pentris. In this and the next assignment, you will build a working game from the ground up. This first assignment consists of creating the Pentrix Operating System that will handle all of the I/O routines for Pentris; 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 block on the screen, (2) checking the color of a block, and (3) 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 three 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:

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 + (row_coordinate * 128) + column_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].

Playing field: The playing field will be 20 rows of 10 blocks each. Since the pixels are small, we will use a 4x4 pixel square as one block, and your code must map the playing field coordinates to the actual video memory coordinates when drawing the block or checking what color it is. Don't panic, because the formulas are given to you in the pseudocode below.

Coordinate systems: This code uses two distinct coordinate systems: the video console coordinates and the playing field coordinates. Both of these coordinate systems are 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.

Multiply instruction: We've added multiplication to the LC-3 using the "reserved" 1101 opcode. The format of the MUL instruction is the same as that of the ADD or AND instruction (just a different opcode). For example:

    MUL R0, R1, R2  ; R0 = R1 * R2
    MUL R0, R1, #4  ; R0 = R1 * 4
The range of allowable constants for MUL is the same as that for ADD. With a 5 bit immediate specification, you are allowed to specify a constant between -16 and 15.

Return from Trap (RTT) instruction: We've also added a Return from Trap (RTT) instruction, which acts identically to a RET instruction, except it also unsets the privileged bit in the Processor Status Register (PSR).

Operating System Template: We're giving you a basic operating system template to which you can add your code. The template is called pentrix.asm, and you can get it and the other files for this assignment by executing the following commands:

    cd ~
    mkdir cse240hw6
    cd cse240hw6
    cp /mnt/eniac/home1/c/cse240/project/hw/hw6/* .   
Based on this template, your implementation of the Pentrix 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 Pentrix:

    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).

New Simulator: This assignment requires a modified version of the simulator. To use this new simulator, you need to use a path to a different version of the tools:

    export PATH=$PATH:/home1/c/cse240/project-v2/bin/
or you may need to type:
    set path = ( $path  /home1/c/cse240/project-v2/bin/ ) 

Testing and Turnin: Much like the previous assignment, we've included testing code in the same directory as the pentrix.asm file. The only file you need to turn in is your version of the pentrix.asm file. Similar as before, do the following:

    ssh eniac-s.seas.upenn.edu
If prompted, enter your eniac password. Continue by typing:
    cd cse240hw6
    turnin -c cse240 -p HW6 pentrix.asm

TRAP Routine Descriptions

As only the HALT trap routine has been provided for you in the pentrix.asm template file, your task is to complete the other three trap routines. Our implementation of these routines was significantly less than 100 lines, so the totaly amount of code we're asking you to write is not huge.

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. Since there are 124 rows, and the game field will take up 20x4 = 80 rows, we'll start the field at the 24th row to keep the playing field about at the center. Similarly, each row is 128 pixels wide, and the game field will be 10x4 = 40 pixels across, so starting at the 45th column would also get the field close to the center. Since the row and column counts are all zero-based, the top left pixel of the top left block will be at row 23 and column 44.

Since 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. Assume that col, row, and color are given, and that col and row are game field coordinates.

  vid_row = 23 + (4*row);
  vid_col = 44 + (4*col);
  for(r=0; r<=3; r=r+1)
        vid_mem_addr = xC000 + ((vid_row + r) * 128) + vid_col;
        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 the row is in R0, the column is in R1, and the color is in R2. The following LC-3 assembly declarations may be helpful:
; Video Memory Constants
Make sure that these constants are declared after the Return from Trap instruction. Otherwise, the simulator may mistake them for instructions and not data.

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_row = 23+(4*row);
  vid_col = 44+(4*col);
  vid_mem_addr = xC000 + (vid_row * 128) + vid_col;
  put content at vid_mem_addr into R5;
Write the LC-3 code for the above pseudocode assuming that the row is in R0 and the column is in R1. The code must place into R5 the 16-bit value that encodes the current color of the specified block.

Part 3: Get Event (trap x42)

The third part of this assignment is writing LC-3 code to handle the input for the tetris game. The input determines if the active block should: move down, move left, move right, rotate left, or rotate right. Don't worry about how these are implemented just yet, we will first focus on how to report the events when they do happen.

Our game of tetris 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 down" command should 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 block 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.

Note: Please note that the LC-3 terminal 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 events each correspond to an integer value, so that value will be what you report (i.e., return) in R5:

The pseudocode:
    x := OS_TR
    if(x != 0)
        R5 := 0       ; Down
        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 == DOWN_KEY)
        R5 := 0       ; Down
        goto done     ; break out of the loop

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

    if(x == RIGHT_KEY)
         R5 := 2      ; Right
         goto done    ; break out of the loop

    if(x == ROT_LEFT_KEY)
         R5 := 3      ; Rotate Left
         goto done    ; break out of the loop

    if(x == ROT_RIGHT_KEY)
         R5 := 4      ; Rotate Right
         goto done    ; break out of the loop

    if(x == QUIT_KEY)
         R5 := 5      ; 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
UP_KEY          .FILL x0077     ; Up - W
DOWN_KEY        .FILL x0073     ; Down - S
LEFT_KEY        .FILL x0061     ; Left - A
RIGHT_KEY       .FILL x0064     ; Right - D
ROT_LEFT_KEY    .FILL x006B     ; Rotate Left (Counterclockwise) - K
ROT_RIGHT_KEY   .FILL x006C     ; Rotate Right (Clockwise) - L
QUIT_KEY        .FILL x002A     ; Quit - *

; Addresses of various registers
OS_KBSR .FILL xFE00             ; keyboard status register 
OS_KBDR .FILL xFE02             ; keyboard data register 
OS_DSR  .FILL xFE04             ; display status register 
OS_DDR  .FILL xFE06             ; display data register 
OS_TR   .FILL xFE08             ; timer register