Assignment 8, due Oct 24

On every assignment, write your name legibly as it appears on your University ID card! Homework is due on paper Homework is due on paper at the start of class on the day indicated (usually Friday). Late work must be turned in to the TA's mailbox (ask the CS receptionist in 14 MLH for help). Never push homework under someone's door!

1. Background: Consider the BGT instruction. This makes the decision to branch (or not) based on the 4 condition codes, N, Z, V and C.

   A Problem: Give the logic diagram (in graphical notation) for the logic that produces a true output if the BGT instruciton is supposed to branch, and a false output if not. (0.5 points)

2. Background: The Hawk shift instructions all take a constant shift count. Suppose you wanted an instruction to shift by a variable amount, corresponding to a<<b where b is not a constant. The following algorithm would do this, but it is not efficient except for very small shift counts.

   leftshift( int a, int c) { // iterative shifter
       while (c > 0) { a = a << 1; c = c - 1; }
       return a;
   }
   

   Consider the following alternative:

   leftshift( int a, int c) { // software barrel shifter
       if (c & 1)  a = a << 1;
       if (c & 2)  a = a << 2;
       if (c & 4)  a = a << 4;
       if (c & 8)  a = a << 8;
       if (c & 16) a = a << 16;
       return a;
   }
   

   The iterative shifter and the barrel shifter produce the same result for all values of c from 1 to 31.

   a) What is the result of the iterative shifter for larger values of c? (0.2 points)

   b) What is the result of the barrel shifter for larger values of c? (0.2 points)

   c) Code the barrel shifter as a SMAL Hawk assembly language subroutine. Take advantage of the BITTST instruction for testing individual bits of a register (see Section 6.4 of the Hawk manual). (0.6 points)

3. Some problems: Write the fastest SMAL Hawk code you can for multipliction by the following constants. In each case, assume that the number to be multiplied is in R3 and your code should leave the result there. If you need an additional register, use R1.

   a) × 120. (0.3 points)

   b) × 192. (0.3 points)

   c) × 500. (0.3 points)

4. A problem: Given that R3 and R4 hold a 64-bit unsigned value, with the least significant 32 bits in R3, write SMAL Hawk code to divide that value by 16. If you need an additional register, use R1. (0.6 points)

   Hint: Two 4-bit right-shift instructions get all but 4 bits of the result correct. The problem is to rescue those 4 bits. This can be done with some left shifting and an add. Keep in mind that the maximum shift count that the hawk permits is 16, but some of the shifting you need to do requires more. This will take multiple instructions. and an add