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!

1. From PS4.
   (Adapted from 6.14) Consider the following machine language program:

   	AND R2, R2, #0
   LOOP	ADD R1, R1, #-3
   	BRn END
   	ADD R2, R2, #1
   	BRnzp LOOP
   END	HALT

   What are the possible initial values of R1 that cause the final value in R2 to be 3?



2. From PS4.
   (Adapted from 7.16) Assume a sequence of nonnegative integers is stored in consecutive memory locations, one integer per memory location, starting at location x4000. Each integer has a value between 0 and 30,000 (decimal). The sequence terminates with the value -1 (i.e., xFFFF).
   1. Create the symbol table entries generated by the assembler when translating the following routine into machine code:

      	.ORIG x3000
      	AND R4, R4, #0
      	AND R3, R3, #0
      	LD R0, NUMBERS
      LOOP	LDR R1, R0, #0
      	NOT R2, R1
      	BRz DONE
      	AND R2, R1, #1
      	BRz L1
      	ADD R4, R4, #1
      	BRnzp NEXT
      L1	ADD R3, R3, #1
      NEXT	ADD R0, R0, #1
      	BRnzp LOOP
      DONE	TRAP x25
      NUMBERS	.FILL x4000
      	.END

   2. What does the above program do?



3. From PS4.
   Below is a segment of LC-3 machine language program.

   	ADD R2, R1, #0
   HERE	ADD R3, R2, #-1
   	AND R3, R3, R2
   	BRz END
   	ADD R2, R2, #1
   	BRnzp HERE
   END	HALT

   If the data in R1 is an unsigned integer larger than 1, what does the program do? (Hint: what is the relationship between the resulting integer in R2 and the original integer in R1?)



4. From PS4.
   (Adapted from 7.18) The following LC-3 program compares two character strings of the same length. The source strings are in the .STRINGZ form. The first string starts at memory location x4000, and the second string starts at memory location x4100. If the strings are the same, the program terminates with the value 1 in R5; otherwise the program terminates with the value 0 in R5. Insert one instruction each at (a), (b), and (c) that will complete the program. Note: The memory location immediately following each string contains x0000.

   	.ORIG x3000
   	LD R1, FIRST
   	LD R2, SECOND
   	AND R0, R0, #0
   LOOP	____________________	; (a)
   	LDR R4, R2, #0
   	BRz NEXT
   	ADD R1, R1, #1
   	ADD R2, R2, #1
   	____________________	; (b)
   	____________________	; (c)
   	ADD R3, R3, R4
   	BRz LOOP
   	AND R5, R5, #0
   	BRnzp DONE
   NEXT	AND R5, R5, #0
   	ADD R5, R5, #1
   DONE	TRAP x25
   FIRST	.FILL x4000
   SECOND	.FILL x4100
   	.END




5. From PS4.
   The data at memory address x3500 is a bit vector with each bit representing whether a certain power plant in the area is generating electricity (bit = 1) or not (bit = 0). The program counts the number of power plants that generate electricity and stores the result at x3501. However, the program contains a mistake which prevents it from correctly counting the number of electricity generating (operational) power plants. Identify it and explain how to fix it.

   	.ORIG x3000
   	AND R0, R0, #0
   	LD R1, NUMBITS
   	LDI R2, VECTOR
   	ADD R3, R0, #1
   CHECK	AND R4, R2, R3
   	BRz NOTOPER
   	ADD R0, R0, #1
   NOTOPER	ADD R3, R3, R3
   	ADD R1, R1, #-1
   	BRp CHECK
   	STR R0, R2, #1
   	TRAP x25
   NUMBITS	.FILL #16
   VECTOR	.FILL x3500
   	.END



6. From PS4.
   

   The following program does not do anything useful. However, being an "electronic idiot," LC-3 will still execute it.

   
           .ORIG x3000
           LD R0, Addr1
           LEA R1, Addr1
           LDI R2, Addr1
           LDR R3, R0, #-6
           LDR R4, R1, #0
           ADD R1, R1, #3
           ST R2, #5
           STR R1, R0, #3
           STI R4, Addr4
           HALT
   Addr1   .FILL x300B
   Addr2   .FILL x000A
   Addr3   .BLKW 1
   Addr4   .FILL x300D
   Addr5   .FILL x300C
           .END
   
   

   Without using the simulator, answer the following questions:

   1. What will the values of registers R0 through R4 be after the LC-3 finishes executing the ADD instruction?

   2. What will the values of memory locations Addr1 through Addr5 be after the LC-3 finishes executing the HALT instruction?




7. From PS4.
   

   1. Bob Computer just bought a fancy new graphics display for his LC-3. 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 LC-3 was writing to the DDR. How was he able to tell?

   2. Bob also rewrote the handler for GETC, but when he typed ABCD into the keyboard, the following values were input:

      
      AAAAAAAAAAAAAAAAABBBBBBBBBBBBBBBBBBBBCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDDDDDDDDD
      

      What did Bob do wrong?



8. From PS4. Added 10/26/2011.
   (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.



9. 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 (RET is equivalent to JMP R7).

   
   ; 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
   



10. (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?



11. Postponed to PS6.
    

    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.

    Hint: You should remember to save and restore any registers your subroutine uses (the "callee save" convention). Use the RET instruction as the last instruction in your subroutine (R7 contains the address of where in the caller to return to.)



12. Postponed to PS6.
    

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



13. Postponed to PS6.
    (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