Assignment 7, due Mar 13

On every assignment, write your name legibly as it appears on your University ID card! Homework is due on paper at the start of class on the day indicated (usually Friday). Exceptions will be made only by advance arrangement (excepting "acts of God"). 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: Review the section of Chapter 7 entitled: A Big Optimization, Working With Words. Consider applying the ideas from that section to strncpy(dst,src). This routine must deal with several possibilities relating to the alignment of src and dst

   0) (src-dst)&3 = 0 (identical alignment)
   1) (src-dst)&3 = 1
   2) (src-dst)&3 = 2
   3) (src-dst)&3 = 3

   a) Which of the above cases could be handled by logic similar to that for the ultra-fast version of strlen() given in the notes? (0.5 points)

   b) Which two of the above cases could be improved significantly by logic that copied one halfword at a time? (0.5 points)

2. Background:

   Consider this bit of high-level language code in the style of C and Java (it is largely the same in Python, except for the curly braces and semicolons):

   {
       int b = 1;
       do {
           int c = a ^ b;
           b = (a & b) << 1;
           a = c;
       } while (b != 0);
   }
   

   This code transforms the integer variable a from its value prior to the code to a new value after it.

   a) The code of the loop body describes a logic circuit found in Chapter 8 of the notes. What is the name of that circuit? (0.3 points)

   b) What does this code do to the variable a? (Try it if you can't figure it out.) (0.3 points)

   c) If the integer variables in this code are 32 bits each, what is the maximum number of iterations of the loop? (0.4 points)

3. Background: There is an alternative definition of the overflow bit from the one given in the section of Chapter 8 on the conditon codes. Here is how it is stated in English:

   There is an overflow if the sign of the addend a and the sign of the augend b are the same, but the sign of the sum c = a + b is different.

   For example, if you add two positive numbers and get a negative result, there was an overflow.

   a) Give a boolean equation for V as a function of a_n–1, b_n–1 and c_n–1, (for an n bit word). (0.5 points)

   b) Draw the corresponding logic circuit, in the style of the figure captioned Derivation of the condition codes in Chapter 8. (Draw only the part of the circuit that gives the V output in terms of the inputs and output(s) of the most significant full adder in the circuit.) (0.5 points)