Homework 6 -- BreakOS
CSE240 - Introduction to Computer Architecture
Autumn 2005

Due: Monday 31 October

Finally! Let's write some code. In this and the next assignment, you will build a working game from the ground up. This first assignment consists of creating the BreakOS Operating System that will handle all of the I/O routines for Breakout; 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, 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:

Important files: Because Mac and Windows machines seem to get upset when downloading files with wierd file extensions (e.g., .asm), we've included all the files you will need to get started in one zip file, hw6.zip.

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

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.

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.

Register Saving/Restoring: You will notice, in the stubs provided in breakos.asm that each trap begins with a register saving section and ends with a register restoring section. This needs to be done since the caller may expect register values to be preserved when the trap returns. Because no traps call each other, we won't have to worry about the values saved being overwritten. However, in the next assignment, you will see the use of the user stack through the stack pointer. (Note: The first version of this assignment that we passed out erroneously included a discussion of the stack pointer, which won't be used until the next assignment. You can ignore that for now.)

Memory-mapped timer: The LC3 architecture was nice enough to give us a timer, so we can actually know when to move the ball! 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.

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

Input Range Checking: While it's generally a good idea to error check strenuously when programming, this is just too much of a performance hit when done on the TRAP level in our slow little LC3 machine. So, for the purposes of this assignment, you are not required to do any out of bounds checking on the input arguments. We'll deal with that next time.

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.

TRAP Routine Descriptions

For this assignment you will implement the 5 trap handlers that constitude the BreakOS (along with the existing handlers, like TRAP). Each trap handler is described, below.

Part 1: Draw Point (trap x40)

The first part of this assignment is writing LC-3 code to draw various shapes. We'll start with the most basic one -- a pixel on the screen. Your input will be a row number from 0 to 123 (since there are 124 rows) and a column number from 0 to 127 (since there are 128 columns). You'll also have the color to place into that pixel.

Assume that row, col, and color are given, and row and col are video memory coordinates.

vid_mem_addr = xC000 + row * 128 + col;
set memory at vid_mem_addr 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 (they're already provided in breakos.asm):

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

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 dots showing up on the video memory. Unfortunately, to compute precise locations to check, you'll have to do out the math to compute the address corresponding to where each dot is supposed to go.

Part 2: Draw Ball (trap x41)

Now we'll draw something a little more complex, a 2x2 square. Your input will now be the coordinates of the top left pixel of this square. Once you figure out the memory address of this pixel, getting the other three should only require a little bit of addition. The pseudocode for this is very similar to that of part 1, so we won't provide it again.

Write the LC-3 code for Draw Ball assuming, again, that the row is in R0, the column is in R1, and the color is in R2.

Once again, to test whether this code is working, run the scripts we've provided. Then you can follow the same routine, except this time you can expect what appears to be bigger dots, which are actually 2 by 2 squares.

Note: Don't call Draw Point when implementing this, because the LC-3 does not allow recursive traps. Why not? Well, when a trap handler returns, the processor exits privileged mode. This is a problem if returning to privileged (i.e., other OS) code.

Part 3: Draw Rectangle (trap x42)

Expanding once again on the box drawing concept, we'll try to now generalize the function so that you can draw an arbitrary size rectangle. In addition to being provided with the row, column, and color, you'll also be given height and width of the rectangle as input.

for (r=0; r < height; r++)
    for (c=0; c < width; c++)
        vid_mem_addr = xC000 + r * 128 + c;
	set memory at vid_mem_addr to color;

Write the LC-3 code for the above pseudocode assuming that R0 is the row, R1 is the col, R2 is the height, R3 is the width, and R4 is the color.

This time, you should be able to more easily test for whether your function is at least close to working, by putting in for example a width of 10 and a height of 20, and a bright color to clearly see that you are drawing a rectangle. Use the test scripts and your own calculations to verify that you're drawing the rectangle in the right place and at the right size.

Note: Don't call Draw Point or Draw Ball when implementing this.

You might wonder why we bothered with the first two parts (Draw Point and Draw Ball) when they are merely special cases of Draw Rectangle. Because our LC-3 machine is so slow, our game will be much more playable if we have optimized point and ball drawing trap handlers. In other words, these special case handlers will dramatically improve the performance of our code.

Note that it's very hard to code this trap in assembly with the number of registers provided, especially since R6 and R7 should normally not be used. There are ways to get around this, involving either saving values onto the stack or reserving memory locations when coding and swapping register values to/from those memory locations. Experiment a little and see which works better for you.

Part 4: Check Point (trap x43)

Now we'll go back to a single pixel. This time, instead of drawing the pixel on the screen, we want to figure out what color is already sitting in that pixel. The procedure very similar to what we did in part 1.

vid_mem_addr = xC000 + row * 128 + 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.

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

Part 5: Get Event (trap x44)

The third part of this assignment is writing LC-3 code to handle events for Breakout. There are two kinds of events relevant to Breakout. First, there are keyboard events indicating that the user wants to quit or move the paddle to the left or right. Second, there are timer events indicating that it is time to move the ball to its next position on the screen. At this point, we're not writing code to move the paddle or ball. Instead, we are simply detecting events.

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 ball should move. If the user presses the 'a' key, we return 1 (in R5) indicating that the user wants to move the paddle to the left. If the user presses the 'd' key, we return 2 (in R5) indicating that the user wants to move the paddle to the right. Finally, if the user presses the 'q' key, we return -1 (in R5) indicating that the user wants to quit the game.

Dealing with the timer is easy. 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 ('a', 'd', or 'q'). When we find a match, we return the appropriate value. Otherwise, we continue polling the TSR and KBSR. The pseudocode:

    x := OS_TSR
    if(x != 0)
        R5 := 0       ; Move Ball
        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 == RIGHT_KEY)
         R5 := 2      ; Right
         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

Although the above code has gotos in it, the code is still well structured. Basically, we have a loop that terminates when we assign an interesting value to R5. Think of it as a switch statement in a loop.

The exact keys and input locations are specified in breakos.asm using the following LC-3 assembly code:

; Input key ASCII codes
LEFT_KEY        .FILL x0061     ; Left - A
RIGHT_KEY       .FILL x0064     ; Right - D
QUIT_KEY	.FILL x0071	; Quit - Q

; Addresses of various registers
OS_KBSR .FILL xFE00             ; keyboard status register 
OS_KBDR .FILL xFE02             ; keyboard data register 
OS_TSR  .FILL xFE08             ; timer 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 unrecognize 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.

By the way, you might be wondering why this is placed before the other parts in breakos.asm, and it is because this subroutine relies on some constants defined in memory which are located in lower addresses, and placing it at the end of the assignment meant a high risk of running out of bounds on the LD statements.

Your Assignment

Yeah, sorry for making you scroll all the way down here to find out what your actual assignment is. Well, if you haven't figured it out yet, you're to implement all 5 of the traps described above. We'll give you some skeleton breakos.asm code to get you started. Now implement and test Parts 1 - 5, and you're done! Here's the formal breakdown:

Problem 1 (15 pts): Implement Part 1.

Problem 2 (15 pts): Implement Part 2.

Problem 3 (25 pts): Implement Part 3.

Problem 4 (15 pts): Implement Part 4.

Problem 5 (25 pts): Implement Part 5.

Total: 95 points.


Please submit your breakos.asm file online at the CSE240 submission site. This is due by MIDNIGHT on the due day (note that this gives you a little more time).