Department of Electrical and Computer Engineering

The University of Texas at Austin

EE 306, Fall 2013
Problem Set 5
Due: 11 November, before class
Yale N. Patt, Instructor
TAs: Ben Lin, Mochamad Asri, Ameya Chaudhari, Nikhil Garg, Lauren Guckert
Jack Koenig, Saijel Mokashi, Sruti Nuthalapati, Sparsh Singhai, Jiajun Wang

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

      Some of the characters written to the DDR weren't being output to the screen.

    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?

      The handler didn't check the KBSR before inputting the character.



  2. Moved to problem set 6
  3. Moved to problem set 6
  4. Moved to problem set 6
  5. 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.

      Solution:
      
              CLEAR: ST R2, TEMP
      	       LEA R2, MASKS
      	       ADD R2,R1,R2
      	       LDR R2,R2,#0
      	       NOT R2,R2
      	       AND R0,R2,R0
      	       LD R2, TEMP
      	       RET
      	TEMP:  .BLKW #1
      	
      	
    2. Write a similar subroutine SET that sets the specified bit instead of clearing it.

      Solution:
      
      	SET:   ST R2, TEMP
      	       LEA R2, MASKS
      	       ADD R2,R1,R2
      	       LDR R2,R2,#0
      	       NOT R2,R2
      	       NOT R0,R0
      	       AND R0,R2,R0
      	       NOT R0,R0
      	       LD R2, TEMP
      	       RET
      	TEMP:  .BLKW #1
      	
      	
  6. 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.

      Hint: Feel free to include in your program

      
      PTR	.FILL x6001
      CNT	.FILL x6000
      

      Solution:
      
            .ORIG x3000
            LD R5, PTR
            LDI R6, CNT
            BRz DONEz    ;checks if more numbers to multiply(CNT=0)
      MORE  LDR R1,R5,#0
            ADD R5,R5,#1
            ADD R6,R6,#-1
            BRz DONE1    ;continues if more numbers to multiply
            LDR R2,R5,#0       ;
            ADD R5,R5,#1
            ADD R6,R6,#-1
            BRz DONE2    ;continues if more numbers to multiply
            LDR R3,R5,#0
            ADD R5,R5,#1
            ADD R6,R6,#-1
            BRz DONE3    ;continues if more numbers to multiply
            LDR R4,R5,#0
            ADD R5,R5,#1
            ADD R6,R6,#-1
            BRnzp READY ;CNT is multiple of 4
      DONEz AND R0,R0,#0
            ADD R0,R0,#1
            BRnzp END
      
      ;(CNT = 4x+1) multiplies R1 by three 1's
      DONE1 AND R2,R2,#0
            ADD R2,R2,#1       ;R2 = 1
            ADD R3,R2,#0       ;R3 = 1
            ADD R4,R2,#0       ;R4 = 1
            BRnzp READY
      
      ;(CNT = 4x+2) multiplies R1,R2 by two 1's
      DONE2 AND R3,R3,#0
            ADD R3,R3,#1       ;R3 = 1
            ADD R4,R4,#0       ;R4 = 1
            BRnzp READY
      ;
      ;(CNT = 4x+3) multiplies R1,R2,R3 by 1
      DONE3 AND R4,R4,#0
            ADD R4,R4,#1
      READY JSR mult_all
            ADD R6,R6,#0
            BRz END            ;checks CNT
      ;
      ;if CNT is not zero takes R0 from subroutine and puts back into
      memory to multiply more numbers
             ADD R5,R5,#-1
             STR R0,R5,#0
      ;add one back to CNT because R0 is back into memory
             ADD R6,R6,#1
             BRnzp MORE
      ;
      ;store result of multiplication in memory location RESULT
      END    ST R0,RESULT
             HALT
      RESULT        .BLKW 1
      mult_all ... ;multiples R1,R2,R3,R4 and stores result in R0
                  ...
                  ...
                  RET
      PTR    .FILL x6001
      CNT    .FILL x6000
      .END
      
      
  7. (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
        
    
    Solution:
    Need to save R7 so 1st service routine can return. Second RET overwrites the first RET value.

  8. Moved to problem set 6

  9. (Adapted from 8.16)
    What does the following LC-3 program do?
    
            .ORIG X3000
            LD R0,ASCII
            LD R1,NEG
    AGAIN   LDI R2,DSR
            BRzp AGAIN
            STI R0,DDR
            ADD R0,R0,#1
            ADD R2,R0,R1
            BRnp AGAIN
            HALT
    ASCII   .FILL X0041
    NEG     .FILL XFFB6
    DSR     .FILL XFE04
    DDR     .FILL XFE06
            .END
    
    Solution
    Letter ABCDEFGHI will be displayed on console.

  10. (Adapted from 9.5)
    The following LC-3 program is assembled and then executed. There are no assemble time or run-time errors. What is the output of this program? Assume all registers are initialized to 0 before the program executes.
    
            .ORIG X3000
            ST R0, X3007
            LEA R0, LABEL
            TRAP X22
            TRAP x25
    LABEL   .STRINGZ "FUNKY"
    LABEL2  .STRINGZ "HELLO WORLD"
            .END
    
    Solution
    FUN

  11. 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. 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
    
    
    Solution:
    Marc 90
    Jack 18
    Mike 76
  12. The program below counts the number of zeros in a 16-bit word.

                .ORIG x3000
                AND   R0, R0, #0
                LD    R1, SIXTEEN
                LD    R2, WORD
    A           BRn   B
                ADD   R0, R0, #1
    B           ADD   R1, R1, #-1
                BRz   C
                ADD   R2, R2, R2
                BR    A
    C           ST    R0, RESULT
                HALT
    
    SIXTEEN     .FILL #16
    WORD        .BLKW #1
    RESULT      .BLKW #1
                .END
    1. Fill in the missing blanks below to make it work.
    2. After you have the correct answer above, what one instruction can you change (without adding any instructions) that will make the program count the number of ones instead?

      Replace the BRn instruction with a BRzp.
  13. Suppose we use the unused opcode 1101 to specify a new instruction. We will require 3 states after decode (state 32) to complete the job. The control signals required to carry out the work of the new instruction are shown below. All control signals not shown below are 0.
    1. What does this new instruction do?
    2. Adds contents of SR1 (IR[8:6]) to SR2 (or immediate) and store the result in location specified by BaseR (IR[11:9]).
    3. There are two different formats for specifying the operands of this instruction. Fill them out below.