# Exam 1: Midterm

## Solutions and Commentary

### Exam I

```                                   X
X
X X
Mean   = 7.13                      X X X
Median = 7.5                   X   X X X
X   X X X
X X   X X X
X X X X X X X
X X X X X X X
X   X X X X X X X
_____________X_X___X_X_X_X_X_X_X_X_X_X_X______
0 . 1 . 2 . 3 . 4 . 5 . 6 . 7 . 8 . 9 . 10
```

### Homework Assignments 1 - 6

```                                                                   X
X
Mean   = 14.97                                                     X
Median = 16.1                                                X   X X
X X   X X
X X X X X
X X X X X
X       X   X   X X X X X
X   X       X X X   X X X X X
_____X_X_________X___________________X_X_X_X_X___X_X_X___X_X_X_X_X_X_
2 . 3 . 4 . 5 . 6 . 7 . 8 . 9 . 10. 11. 12. 13. 14. 15. 16. 17. 18
```

### Machine Problems 1 - 2

```                                             X
etc
Mean   =  9.46                              etc
Median = 10.0                                X
X
X         X
X       X X
X     X   X       X X
___X___________________X_____X___X_X_____X_X__
0 . 1 . 2 . 3 . 4 . 5 . 6 . 7 . 8 . 9 . 10
```

### Total Scores

```                                                             X
X
X
Mean   = 31.40                                               X
Median = 32.9                                                X X
X X
X           X X X
X X   X     X X X
X   X X X X X X X X X
X X X X X X X X X X X
_______X_____________________X_X_________X_X_X_X_X_X_X_X_X_X_X_X_X____
6 . 8 . 10. 12. 14. 16. 18. 20. 22. 24. 26. 28. 30. 32. 34. 36. 38
A very tentative grade scale:   F   |   D   |   C   |   B   |   A
```

## Exam Solutions and Commentary

1. Fill in the following table; values in the blanks in each column derive from the given values in that column, all values in each row are derived from the given values using the same rules. (4 points)

There were two versions of this question:

```Bit Pattern x         011000     010110     110111     000101     101111

Unsigned decimal     ___24___   ___22___   ___55___   ___5____   ___47___

1's complement of x  _100111_   _101001_   _001000_   _111010_   _010000_
(binary)
2's complement of x  _101000_   _101010_   _001001_   _111011_   _010001_

x as a 1's comp num  ___24___   ___22___   ___-8___   ____5___   __-16___
(signed decimal)
x as a 2's comp num  ___24___   ___22___   ___-9___   ____5___   __-17___
```

```Bit Pattern x         001100     001011     100010     011011     110111

Unsigned decimal     ___12___   ___11___   ___34___   ___27___   ___55___

1's complement of x  _110011_   _110100_   _011101_   _100100_   _001000_
(binary)
2's complement of x  _110100_   _110101_   _011110_   _100101_   _001001_

x as a 1's comp num  ___12___   ___11___   __-29___   ___27___   ___-8___
(signed decimal)
x as a 2's comp num  ___12___   ___11___   __-30___   ___27___   ___-9___
```

Regardless of the version of the exam, only scattered people had any difficulty with the first three rows of the table. In contrast, all of the conversions to signed decimal caused problems for from for about 1/7 of the class. Typical problems included giving negative answers where the number was positive, giving positive answers when the number was negative, and giving answers off by one.

2. Translate the following brief useless SMAL code to a sequence of bytes loaded in memory. The spaces to the right are labeled with a word and byte in word addresses; fill in the hexadecimal value that goes in that byte; leave uninitialized bytes blank. The result of assembling the first lines are given. (2 points)

There were two versions of this question:

```    . = 0                       ||  Address    3    2    1    0
A:  H     #2345             ||          |----|----|----|----|
B     #01               ||  000000: |    | 01 | 23 | 45 |
B:  ; solved to here        ||          |----|----|----|----|
ALIGN 4                 ||  000004: | 00 | 42 | 00 | 0A |
H     #A,"B"            ||          |----|----|----|----|
ALIGN 2                 ||  000008: | 00 | 00 | AB | CD |
W     #ABCD             ||          |----|----|----|----|
C:  B     D,C,B,A           ||  00000C: | 00 | 03 | 0C | 10 |
ALIGN 4                 ||          |----|----|----|----|
D:  H     #C,D              ||  000010: | 00 | 10 | 00 | 0C |
END                     ||          |----|----|----|----|
```

```    . = 0                       ||  Address    3    2    1    0
D:  H     #2345             ||          |----|----|----|----|
B     #01               ||  000000: |    | 01 | 23 | 45 |
C:  ; solved to here        ||          |----|----|----|----|
ALIGN 4                 ||  000004: | 00 | 42 | 00 | 0A |
H     #A,"B"            ||          |----|----|----|----|
ALIGN 2                 ||  000008: | 00 | 00 | AB | CD |
W     #ABCD             ||          |----|----|----|----|
B:  B     D,C,B,A           ||  00000C: | 10 | 0C | 03 | 00 |
ALIGN 4                 ||          |----|----|----|----|
A:  H     #C,D              ||  000010: | 00 | 00 | 00 | 0C |
END                     ||          |----|----|----|----|
```

Regardless of the version of the exam, the biggest problems fell into the following categories
Byte or Halfword order — 1/10 of the class made consistent errors about this. Worse, a few used inconsistent orders, reversing some fields but not others.
W #ABCD — 1/7 of the class assumed that, despite the W directive, this should assemble as a halfword, evidently because only 4 hex digits were given.
Label values – Almost everyone had trouble with the second label (B in the first solution above, C in the second). The problem was the ALIGN directive immediately after the label; the assembler is not smart enough to look ahead to this directive and have it change the value of the label, but most students assumed it would do so, giving the label the value 4.
Labels confused – Almost 1/3 of the class made significant errors in the value of one or more labels other than the one discussed above.
Labels confused with ASCII – A significant but small number of students confused the label A with the ASCII character "A". It is hard to fathom how an experienced programmer can confuse an identifier with a quoted string.

Only one student had a perfect score on this problem, but most students did reasonably well.

3. a) The SMAL Hawk code for a Hawk function is given to the left. Work out corresponding Hawk machine code on the right, as a sequence of 8-bit bytes given in hexadecimal, two per line: (1.5 points)

There were two versions of this question that differed in the registers used. Here is one of them:

```    SMAL Hawk code      ||   Scratch space    || Addr:   0    1
||                    ||
F:      MOVE    R6,R3   ||                    || 1000: _F6_ _F3_
LIS     R3,0    ||                    ||
LIS     R4,1    ||                    || 1002: ____ ____
BLT     B       ||                    || 1004: ____ ____
MOVE    R3,R4   ||                    || 1006: ____ ____
MOVE    R4,R5   ||                    ||
BR      A       ||                    || 1008: ____ ____
B:      JUMPS   R1      ||                    ||
||                    ||  ...
```

Here are assembly listings for both versions; note that the order of the bytes of the object code in the assembly listings is exactly to the order requested by the blanks in the problem statement shown above.

```+00000000: F6  F3                3  F:      MOVE    R6,R3
+00000002: D3  00                4          LIS     R3,0
+00000004: D4  01                5          LIS     R4,1
+00000006: 16  CF                6  A:      ADDSI   R6,-1
+00000008: 05  04                7          BLT     B
+0000000A: 35  34                8          ADD     R5,R3,R4
+0000000C: F3  F4                9          MOVE    R3,R4
+0000000E: F4  F5               10          MOVE    R4,R5
+00000010: 00  FA               11          BR      A
+00000012: F0  B1               12  B:      JUMPS   R1
```

```+00000000: F4  F3                3  F:      MOVE    R4,R3
+00000002: D3  00                4          LIS     R3,0
+00000004: D5  01                5          LIS     R5,1
+00000006: 14  CF                6  B:      ADDSI   R4,-1
+00000008: 05  04                7          BLT     A
+0000000A: 36  35                8          ADD     R6,R3,R5
+0000000C: F3  F5                9          MOVE    R3,R5
+0000000E: F5  F6               10          MOVE    R5,R6
+00000010: 00  FA               11          BR      B
+00000012: F0  B1               12  A:      JUMPS   R1
```

1/6 of the class did perfectly here while 1/10 of the class earned no credit at all. Among those earning partial credit, by far the most difficult problem involved PC-relative branch instructions. Forward branches were slightly easier than backward branches, and off-by-one errors were common, but many students had wild answers verging on random. 1/10 of the class switched the order of all of the bytes, and an additional 1/10 did worse, switching the order of some bytes but not others.

b) It is a function. If F is called with the integer 3 in R3, what value is returned? (0.5 points)

```       ___2_____________________________________________________
```

The sequence is 0 1 1 2 3 5 8, etc., the Fibonacci series, where zero is the zeroth element.

Over 1/3 of the class got this, and close to 1/2 of the class gave off-by-one answers, mostly 1 but also 3.

4. Background: The following two fragments of SMAL Hawk code are from the body of an optimized versions of the traverse subroutine, TRAVERS from a solution to MP3:

There were two versions of this question that differed only in the order and labeling of the two versions of the code. Only one version of the question is given here:

```; ----- VERSION 1 -----
LEA     R8,R3,CHILDREN  ; c = *p->children
TRAVLP:
BZS     TRAVQT          ; while (*c != NULL) { -- note: *c is in R3
JSR     R1,TRAVERS      ;   travers( *c )
BR      TRAVLP
TRAVQT:                         ; }
```
```; ----- VERSION 2 -----
LEA     R8,R3,CHILDREN  ; c = *p->children
BZS     TRAVQT          ; if (*c != NULL) { -- note: *c is in R3
TRAVLP:				;   do {
JSR     R1,TRAVERS      ;     travers( *c )
BZR     TRAVLP          ;   } while (*c != NULL)
TRAVQT:                         ; }
```

a) Which version is faster? (0.4 points)

```       __Version 2 is faster____________________________________
```

Over 1/2 of the class got this right.

b) Briefly explain why (but merely saying "one is shorter" is not sufficient). (0.6 points)

```       __The loop body of version 2 has one less instruction____

__(an unconditional branch has been eliminated)__________
```

1/10 got this right, while another 1/10 embedded right answers in larger statements containing significant errors. Among those with wrong answers for part a), 1/10 of the class earned a bit of credit here for giving clear static analysis supporting their wrong answer by the assertion that Version 1 contains one less instruciton.

1/3 of the class made a serious error, asserting that Version 2 did redundant computations. In fact, both versions execute exactly the same number of LOADSCC instructions for any particular tree node, and exactly the same number of conditional branch instructions test the condition codes.

c) What register must be saved before either block of code and restored after in order to conform to our standard Hawk calling sequence? (0.5 points)

```       __R8 must be saved and restored__________________________
```

1/5 got this right. Some credit was given for the 1/5 who focused on R1, since it is usually saved and restored during subroutine calls, but the conventional boilerplate calling sequences save it by default, while R8 is not included in our boilerplate methodology.

Almost 1/2 of the class focused on R3. In fact, in a preorder traversal, there would be no need to save and restore R3 in the above code, but token credit was given for this answer. No credit was given for those who asserted that R2 needed to be saved and restored. None of the calling sequences we have studied operate by saving and restoring R2.

d) What other optimization was done that moved key code out of the loop to places before and after this? (0.5 points)

```       __Pushing and popping the activation record______________
```

1/6 of the class got this right. Token credit was given for those who said something about moving the address of the children out of the loop, since a pure array addressing approach to the problem would have included subscript calculation inside the loop instead of simply advancing a pointer by 4. 1/2 of the class gave answers that repeated things that had already been discussed in parts a) and b).