Assignment 7, due Mar 13

Solutions

Part of the homework for CS:2630, Spring 2015
by Douglas W. Jones
THE UNIVERSITY OF IOWA Department of Computer Science

  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)

    Case 0.

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

    Case 0 and case 2. Of course, in case 0, it would be better to copy whole words, but working with halfwords allows us to copy two bytes at a time instead of working with eacy byte individually.

  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)

    It is an incrementer, using the and function to compute the carry (as variable b) and the exclusive or function to compute the sum.

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

    It increments it. Here is a demonstration, written in Python: 

    a = 0
while a < 20:
        b = 1
        while b != 0:
                c = a ^ b
                b = (a & b) << 1
                a = c
        print( a )

    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)

    32. The loop propagates the carry from one bit position to the next, so the worst case is when the number being incremented is all ones, that is, ...111112.

  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 an–1, bn–1 and cn–1, (for an n bit word). (0.5 points)

    First note that x ⊕ y is true when x and y are different and false when they are the same, so all of the "same-different" logic can be done with exclusive-or operators. There are many equivalent solutions. Here are some of them:

    V = ¬(an–1 ⊕ bn–1) ∧ (an–1 ⊕ cn–1)

    V = (¬an–1 ⊕ bn–1) ∧ (bn–1 ⊕ cn–1)

    V = (an–1 ⊕ ¬bn–1) ∧ (cn–1 ⊕ an–1)

    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)

    There are, of course, many ways of drawing the circuit. Here is one that puts it in the context of an adder and the other condition codes: schematic notation for the solution