Department of Electrical and Computer Engineering
306, Fall 2004
Problem Set 5
Yale N. Patt, Instructor
Siddharth Balwani, Linda Bigelow, Tommy Buell, Jeremy Carrillo, Aamir Hasan,
Danny Lynch, Rustam Miftakhutdinov, Veynu Narasiman, Vishal Parikh, Basit Sheikh, TAs
You are encouraged to work on the problem set in groups and turn in one problem set for the entire group. Remember to put all your names on the solution sheet. Also remember to put the name of the TA in whose discussion section you would like the problem set turned back to you
1. A) Bob Computer just bought a fancy new graphics display for his LC3. In order to test out how fast it is, he rewrote the OUT trap handler so it would not check the DSR before outputting. Sadly he discovered that his display was not fast enough to keep up with the speed at which the LC3 was writing to the DDR. How was he able to tell?
B) Bob also rewrote the handler for GETC, but when he typed ABCD into the keyboard, the following values were input
What did Bob do wrong?
2. The program from page 193, problem 7.13 in the text adds the values stored in memory locations A, B, and C, and stores the result into memory location 0x300B. There are two errors in the code. For each, describe the error and indicate whether it will be detected at assembly time or at run time, and then correct the error.
3. (9.2) A) How many trap service routines can be implemented in the LC-3? Why?
B) Why must a RET instruction be used to return from a TRAP routine? Why won't a BR (unconditional Branch) instruction work instead?
C) How many accesses to memory are made during the processing of a TRAP instruction? Assume the TRAP is already in the IR.
4. (changed from 9.7 to 9.8) Assume that an integer greater than 2 and less than 32,768 is deposited in memory location A by another module before the program below is executed.
.ORIG x3000 AND R4, R4, #0 LD R0, A NOT R5, R0 ADD R5, R5, #2 ADD R1, R4, #2 ; REMOD JSR MOD BRz STORE0 ; ADD R7, R1, R5 BRz STORE1 ADD R1, R1, #1 BR REMOD ; STORE1 ADD R4, R4, #1 STORE0 ST R4, RESULT TRAP x25 ; MOD ADD R2, R0, #0 NOT R3, R1 ADD R3, R3, #1 DEC ADD R2, R2, R3 BRp DEC RET ; A .BLKW 1 RESULT .BLKW 1 .END
In 20 words or fewer, what does the above program do?
Hint: If you do not know what RET does, try the Index at the back of the book. In fact, you might even take care to look at footnotes on the referenced pages, in addition to the body of the page.
5. A) What does the following
LDI R0, A1
LDI R1, A2
LDI R2, B1
LDI R3, B2
STI R0, B1
STI R1, B2
STI R2, A1
STI R3, A2
A1 .fill 0x4000
A2 .fill 0x4001
B1 .fill 0x5000
B2 .fill 0x5001
B) Unfortunately we dropped our LC3 and now the LDI instruction is broken. Rewrite the program without using LDI. It is possible to do it using the same number of total memory locations for the program.
6. We’ve decided to change the LC3 to have special opcodes for I/O instead of Memory Mapped I/O. The following instructions have been added to the ISA:
LDKS DR Loads the KBSR into a register R0-R7
LDKD DR Loads the KBDR into a register R0-R7
LDDS DR Loads the DSR into a register R0-R7
STDD SR Stores the value of SR (R0-R7) to the DDR
How will this change affect the other instructions? Was this a wise choice?
Hint: Make up a binary format for the instructions
7. Suppose we are writing an algorithm to multiply the elements of an array (unpacked, 16-bit 2's complement numbers). Because we are doing this procedure on several different arrays, we do not want to have to copy our code every time we want to do the array multiply. Assume that you can jump to a subroutine with label mult_array to carry out this procedure (YOU DO NOT HAVE TO WRITE mult_array). The subroutine mult_array assumes the following: R1 contains the number of elements in the array, registers R2 through R5 contain the elements of the array, and mult_array returns the result in R0. (Assume there is at least one and no more than 4 elements in the array)
a) Write assembly code that calls the subroutine at label mult_array, and stores the result at label result. You need to prepare the data before calling the subroutine. Assume the label N references the number of elements in the array, and that label array_a references the first element of our array. Only load the registers that are needed for multiply subroutine (eg. If N=3 then only load registers R2, R3 and R4).
... ; your code calls mult_array
... ; "
... ; "
... ; "
... ; "
... ; (not necessarly this many lines of code)
mult_array ... ; DO NOT WRITE mult_array
N .blkw 1 ; N is filled in at runtime
array_a .blkw 4 ; 4 is the maximum number of elements in our array
result .blkw 1 ; store result here
b) Suppose we now want to call mult_array for an array with more than 4 elements. What recommendation would you give the programmer writing mult_array?
8. Jane Computer (Bob’s adoring wife), not to be outdone by her husband, decided to rewrite the TRAP x22 handler at a different place in memory. Consider her implementation below. If a user writes a program that uses this TRAP handler to output an array of characters, how many times is the ADD instruction with label A executed? Assume that the user only calls this TRAP handler once. What is wrong with this TRAP handler? Now add the necessary instructions so the TRAP handler executes properly.
HINT: RET uses R7 as linkage back to the caller. (You can write this program yourself and simulate it if you are stuck. You’ll need the other program below as well)
; TRAP handler
; Outputs ASCI characters stored in consecutive memory locations.
; R0 points to the first ASCI character.
; The null character (x00) provides a sentinel that terminates the output sequence.
START LDR R1, R0, #0
ST R0, SAVER0
ADD R0, R1, #0
LD R0, SAVER0
A ADD R0, R0, #1
SAVER0 .BLKW #1
Beginning at location x4000, there is a null-terminated array of no more than 100 characters and integers. Note that the array consists of both integers and characters. The integers are limited to the range [1, 9] , but are not in ASCII format. Write a program (starting at x3000) that converts the integers to ASCII so they can be output. Do not change the memory locations at x4000. Then the program must output the array of characters and integers using your corrected TRAP handler from above.
Assume the program below is also loaded into memory