Assignment 7, Solutions

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: Consider the "string compare" operation:

   	strcmp(a,b)
   

   This compares two strings a and b. If they are equal, it returns zero. If the first string is greater than the second, it returns a positive value. If the first string is less than the second, it returns a negative value. The return value of zero occurs when all characters are equal up to and including the final NUL marking the end of string. The nonzero return values indicate whether the first character where the two strings differ is greater or less ...

   A problem: Write SMAL Hawk code for strcmp(). Use the standard Hawk calling conventions, so pointers to the strings a and b will be passed in R3 and R4, and the result should be returned in R3. (1.0 points).

   STRCMP: ; Expects R3, R4 pointers to two strings s1 and s2
           ; Returns R3>0 if s1 > s2
           ;         R3=0 if s1 = s2
           ;         R3<0 if s1 < s2
           ; Uses R5,R6 as temporaries, wipes out R4
   STRCLP:                         ; loop {
           LOADS   R5,R3
           EXTB    R5,R5,R3        ;   c1 = *s1
           LOADS   R6,R4
           EXTB    R6,R6,R4        ;   c2 = *s2
           SUB     R5,R5,R6        ;   d = c1 - c2
           BZR     STRCQT          ;   if (d != 0) break
                                   ;   -- assert c1 = c2
           TESTR   R6
           BZS     STRCQT          ;   if (c2 == 0) break
           ADDSI   R3,1            ;   s1++
           ADDSI   R4,1            ;   s2++
           BR      STRCLP
   STRCQT:                         ; }
           MOVE    R3,R5
           JUMPS   R1              ; return d
   

2. Exercises from Chapter 8 of the Notes:

   a) Do exercise a). Work this out by: First, drawing the schematic diagram and labeling the output of each gate. Second, writing out a truth table with one output column for each labeled point in the circuit. Work it through to the final output and then compare this with each of the known functions of two inputs. (0.5 points).

   

   a	b		x	y	z		c
   0	0		1	0	0		0
   0	1		1	0	1		1
   1	0		1	1	0		1
   1	1		0	0	0		0

   
   

   Therefore, c = a ⊕ b -- this is an exclusive or gate

   g) Follow the instructions. Note (emphatically) that the borrow signal from one bit to the next signals the need to borrow. So, it is an output from each less significant bit to the next more significant bit, just like carry. (0.5 points)

   

   ai	bi		bi+1	di
   0	0		0	0
   0	1		1	1
   1	0		0	1
   1	1		0	0

   
   

   k) (0.5 points).

   

   a3	b3	s3		V
   0	0	0		0
   0	0	1		1
   0	1	0		0
   0	1	1		0
   1	0	0		0
   1	0	1		0
   1	1	0		1
   1	1	1		0

   
   

   l) (0.5 points).