Instructions:
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 and the time for the discussion section you would like the problem set turned back to you. Show your work.
Please staple your Problem Sets BEFORE coming to class!

Questions

1. Moved from Problem Set 4
   (Adapted from 6.16) Shown below are the partial contents of memory locations x3000 to x3006.
   
   

   	15															0
   x3000	0	0	1	0	0	0	0
   x3001	0	0	0	1	0	0	0	0	0	0	1	0	0	0	0	1
   x3002	1	0	1	1	0	0	0
   x3003
   x3004	1	1	1	1	0	0	0	0	0	0	1	0	0	1	0	1
   x3005	0	0	0	0	0	0	0	0	0	0	1	1	0	0	0	0
   x3006

   
   
   The PC contains the value x3000, and the RUN button is pushed.
   
   As the program executes, we keep track of all values loaded into the MAR. Such a record is often referred to as an address trace. It is shown below.
   
   MAR Trace
   x3000
   x3005
   x3001
   x3002
   x3006
   x4001
   x3003
   x0021
   
   Your job: Fill in the missing bits in memory locations x3000 to x3006.




2. Assume that you have the following table in your program:

   
   MASKS   .FILL x0001
           .FILL x0002
           .FILL x0004
           .FILL x0008
           .FILL x0010
           .FILL x0020
           .FILL x0040
           .FILL x0080
           .FILL x0100
           .FILL x0200
           .FILL x0400
           .FILL x0800
           .FILL x1000
           .FILL x2000
           .FILL x4000
           .FILL x8000
   

   1. Write a subroutine CLEAR in LC-3 assembly language that clears a bit in R0 using the table above. The index of the bit to clear is specified in R1. R0 and R1 are inputs to the subroutine.

   2. Write a similar subroutine SET that sets the specified bit instead of clearing it.

3. 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 at the location with label A executed? Assume that the user only calls this "new" TRAP x22 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.

   
   ; TRAP handler
   ; Outputs ASCII characters stored in consecutive memory locations.
   ; R0 points to the first ASCII character before the new TRAP x22 is called.
   ; The null character (x00) provides a sentinel that terminates the output sequence.
   
           .ORIG x020F
   START   LDR R1, R0, #0
           BRz DONE
           ST R0, SAVER0
           ADD R0, R1, #0
           TRAP x21
           LD R0, SAVER0
   A       ADD R0, R0, #1
           BRnzp START
   DONE    RET
    
   SAVER0  .BLKW #1
           .END
   

4. (Adapted from 9.2)

   1. How many TRAP service routines can be implemented in the LC-3? Why?

   2. Why must a RET instruction be used to return from a TRAP routine? Why won't a BRnzp (unconditional BR) instruction work instead?

   3. How many accesses to memory are made during the processing of a TRAP instruction?

5. Suppose we are writing an algorithm to multiply the elements of an array (unpacked, 16-bit 2's complement numbers), and we are told that a subroutine "mult_all" exists which multiplies four values, and returns the product. The mult_all subroutine assumes the source operands are in R1, R2, R3, R4, and returns the product in R0. For purposes of this assignment, let us assume that the individual values are small enough that the result will always fit in a 16-bit 2's complement register.

   Your job: Using this subroutine, write a program to multiply the set of values contained in consecutive locations starting at location x6001. The number of such values is contained in x6000. Store your result at location x7000. Updated 11/14/2009: Assume there is at least one value in the array(i.e., M[x6000] is greater than 0).

   Hint: Feel free to include in your program

   
   PTR	.FILL x6001
   CNT	.FILL x6000
   

6. (Adapted from 9.13)
   The following program is supposed to print the number 5 on the screen. It does not work. Why? Answer in no more than ten words, please.

   
   	.ORIG 	x3000
   	JSR	A
   	OUT			;TRAP  x21
   	BRnzp	DONE
   A 	AND	R0,R0,#0
   	ADD	R0,R0,#5
   	JSR	B
   	RET	
   DONE	HALT
   ASCII	.FILL	x0030
   B	LD	R1,ASCII
   	ADD	R0,R0,R1
   	RET
   	.END
       
   
   

7. (Adapted from 10.1)
   What are the defining characteristics of a stack? Give two implementations of a stack and describe their differences.


8. A zero-address machine is a stack-based machine where all operations are done by using values stored on the operand stack. For this problem, you may assume that the ISA allows the following operations:
   
   PUSH M - pushes the value stored at memory location M onto the operand stack.
   
   POP M - pops the operand stack and stores the value into memory location M.
   
   OP - Pops two values off the operand stack and performs the binary operation OP on the two values. The result is pushed back onto the operand stack.
   
   Note: OP can be ADD, SUB, MUL, or DIV for parts a and b of this problem.
   Note: See the stack machine supplemental handout for help on this problem.
   
   
   1. Draw a picture of the stack after each of the instructions below are executed. What is the minimum number of memory locations that have to be used on the stack for the purposes of this program? Also write an arithmetic equation expressing u in terms of v, w, x, y, and z. The values u, v, w, x, y, and z are stored in memory locations U, V, W, X, Y, and Z.

                  PUSH V
                  PUSH W
                  PUSH X
                  PUSH Y
                  MUL
                  ADD
                  PUSH Z
                  SUB
                  DIV
                  POP U
      	    

   2. Write the assembly language code for a zero-address machine (using the same type of instructions from part a) for calculating the expression below. The values a, b, c, d, and e are stored in memory locations A, B, C, D, and E.
      
      e = ((a * ((b - c) + d))/(a + c))
      
      
9. Updated on 11/13/09.
   The memory locations given below store students' exam scores in form of a linked list. Each node of the linked list uses three memory locations to store
   1) Address of the next node
   2) Starting address of the memory locations where name of the student is stored
   3) Starting address of the memory locations where the his/her exam score is stored
   in the given order. The first node is stored at the location x4000 in locations x4000 ~ x4002. The ASCII code x0000 is used as a sentinel to indicate the end of the string. Both the name and exam score are stored as strings.
   Write down the student's name and score in the order that it appears in the list
   

    
   
       Address         Contents
       x4000           x4016
       x4001           x4003
       x4002           x4008
       x4003           x004D
       x4004           x0061
       x4005           x0072
       x4006           x0063
       x4007           x0000
       x4008           x0039
       x4009           x0030
       x400A           x0000
       x400B           x0000
       x400C           x4019
       x400D           x401E
       x400E           x004A
       x400F           x0061
       x4010           x0063
       x4011           x006B
       x4012           x0000
       x4013           x0031
       x4014           x0038
       x4015           x0000
       x4016           x400B
       x4017           x400E
       X4018           x4013
       x4019           x004D
       x401A           x0069
       x401B           x006B
       x401C           x0065
       x401D           x0000
       x401E           x0037
       x401F           x0036
       x4020           x0000