Assignment 8, Solutions

Problems

1. Background: The 74181 was a popular ALU design that originated with Texas Instruments around 1970. This had 5 control inputs for function selection, although of the 32 functions it offered, most were useless. Each one-bit stage of this ALU has the following inputs and outputs, at least conceptually (the chip had lots of optimization done to it):
   • Inputs A_i and B_i, one bit of each operand.
   • Inputs S₀, S₁, S₂ and S₃, control bits used to determine the operation.
   • Input M, another control bit. 
   • Input C_i, the carry in.
   • Outputs F_i and C_i+1 the sum and carry out.

   This circuit is well documented. The Wikipedia page for it has links to manufacturer's data sheets, which you will need to examine to solve this problem.

   A Problem: Give the values of the inputs S₀, S₁, S₂, S₃ and M that must be given to make this circuit compute the arithmetic sum of inputs A_i and B_i, assuming that these use positive logic (where high value represent ones and low values represent zeros). (1.0 points)

   S₃ S₂ S₁ S₀, M = H L L H, L = 1 0 0 1, 0

2. Background: When you multiply two n-digit numbers, the result has 2n digits. This applies in binary as well as it does in decimal, so if you multiply two arbitrary 32-bit unsigned integers, the product could require 64 bits. Here is the most common algorithm used for producing the full product:

           multlong( ier, icand ) {
           -- given ier and icand, 32-bit values
           -- returns prod, a 64-bit value
           -- internally, prodh is the high half of prod,
           -- and prodl is the low half of prod,
                   prodh = 0
                   prodl = ier
                   repeat 32 times {
                           if prodl is odd {
                                   prodh = prodh + icand
                           }
                           shift prod one place right
                   }
                   return prod
           }
   

   Assignment: Write a SMAL Hawk subroutine MULTLONG that implements the above algorithm. It should take the multiplier and multiplicand in R3 and R4 and it should return the low half of the product in R3 and the high half in R4. (1.0 points)

   Note: This is not big code. You are not asked for a full working program, no main program, just the subroutine. You are not asked for optimal code. The only really interesting part of the problem is the 64-bit right shift, and that is discussed in the lecture notes for the current chapter, as well as in the Hawk manual, which you should be reasonably familiar with by now.

   MULTLONG:
           ; given R3 = multiplier (ier)
           ; given R4 = multiplicand (icand)
           ; returns R3 = low half of unsigned product (prodl)
           ; returns R4 = high half of unsigned product (prodh)
           MOVE    R5,R4           ; save icand
           LIS     R4,0            ; prodh = 0 -- note, prodl = ier
           LIS     R6,32
   MULTLP:                         ; for (i = 32; i > 0; i--) {
           BITTEST R3,0
           BCR     MULTEI          ;    if prodl is odd {
           ADD     R4,R4,R5        ;      prodh = prodh + icand
   MULTEI:                         ;    }
           SRU     R3,1
           SRU     R4,1
           ADJUST  R3,CMSB         ;    shift prod one place right
           ADDSI   R6,-1
           BZR     MULTLP          ; }
           JUMPS   R1              ; return
   

3. A Problem: Give SMAL Hawk code to efficiently multiply R3 by the constant 210, producing a 32 bit result. Your code should use everything you know about efficient multiplication by constants. It should not require more than about 5 instructions. There are two very good ways to do this. (1.0 points)

           ; given R3, an integer to multiply by 210
           ; note, 210 is 2 * 3 * 5 * 7, straightforward version
           SL      R3,1            ;   R3 times 2
           ADDSL   R3,R3,1         ;   R3 times 3
           ADDSL   R3,R3,2         ;   R3 times 5
           NEG     R1,R3           ; \ R3 times 7
           ADDSL   R3,R1,3         ; /
   
           ; given R3, an integer to multiply by 210
           ; note, 210 is 11010010 in binary, straightforward version
           MOVE    R1,R3           ; R1 --        0
           ADDSL   R3,R1,1         ; R3 --       11
           ADDSL   R3,R1,2         ; R3 --     1101
           ADDSL   R3,R1,3         ; R3 --  1101001
           SL      R3,1            ; R3 -- 11010010
   
           ; given R3, an integer to multiply by 210
           ; note, 210 is 11010010 in binary, optimized -- the winner
           MOVSL   R1,R3,1         ; R1 --       10
           ADDSL   R3,R1,2         ; R3 --      110
           ADDSL   R3,R1,2         ; R3 --    11010
           ADDSL   R3,R1,3         ; R3 -- 11010010