CS:2630, Exam 2, Fall 2019

The grade scale suggested above is very rough. No attempt has been made to pin down the exact borders between grades. Note that no homework scores have been dropped. By the end of the semester, there will be 12 homeworks, and the low two scores will be dropped.

Background: Here is a little floating point format that is based on all of the same ideas as the IEEE floating point format:


s	exp			mnt

sign of mantissa

exp

biased exponent
111 – not a number, infinity if m=0
011 – represents zero
000 – non-normalized values (hidden bit = 0)

mnt

mantissa with hidden bit in 1's place

Give an algebraic expression and an approximate decimal equivalents for each of the following binary values in this system (0.3 points each):

a) 000010 = __+1_*_0.25_*_0.5__________________________________ = __+0.125_____

b) 100100 = __-1_*_0.25_*_1.0__________________________________ = __-0.25______

c) 011011 = __+1_*_8_*_1.75____________________________________ = __+14________

d) 110111 = __-1_*_4_*_1.75____________________________________ = __-7_________

e) 101110 = __-1_*_1_*_1.5_____________________________________ = __-1.5_______

Given that there are only 2 bits of mantissa, plus the hidden bit, it would be wrong to give more than about 1 decimal digit of precision, so 0.125 would better be expressed as .1, for example.

1 in 10 made no errors, very few earned no credit, although 1 in 10 only got the signs right. 1 in 6 earned no credit on part a), and another 1 in 6 got the exponent wrong there. Clerical errors were particularly common on c) and d).

A simple question: Given that R3 holds an integer value, write reasonably good code to multiply it by 54: (1.5 points)

_____ADDSL___R3,R3,3___________________________    Note, 54 is 9*3*2 or 18*3

_____ADDSL___R3,R3,1_________MOVE____R1,R3_____

_____SL______R3,1____________ADDSL___R3,R1,1___

_____________________________ADDSL___R3,R1,2___    Note, 54 is 110110

_____________________________ADDSL___R3,R1,1___

_____________________________SL______R3,1______

The first solution given above, based on factoring, is the best. The second solution, based on adding partial products, is slightly optimized from the obvious one that takes 5 instructions.

Over 1 in 3 gave variants on the first solution given above — the three instructions in this solution can be given in any order. Only a few gave solutions comparable to the second given above, although there were a few more short solutions; the best of these was based on the observation that 54 is 64–10.

1 in 10 gave code that did not multiply at all. Some partial credit was given when it was possible to figure out the clerical errors that led to incorrect results. The most common incorrect result was to multiply by 37. One student each proposed code to multiply by 43, 45, 56, 81, 97, 480, 3072, and 262,162. In these cases, a tiny amount of credit was given for code that was at least syntactically correct and did multiply by something.

Background: strchr is a routine in the C strings.h collection that you are unlikely to have studied. Here is the Hawk code for it, without comments:

STRCHR:
STRCLP:
        LOADS   R5,R3
        EXTB    R5,R5,R3  <-- a) R3 must be the string pointer
        CMP     R5,R4     <-- b) what it points to is compared with R4
        BEQ     STRCQT
        TESTR   R5
        BZS     STRCQN
        ADDSI   R3,1
        BR      STRCLP
STRCQN:
        LIS     R3,0      <-- c) returns NULL on end of string
STRCQT:
        JUMPS   R1

a) On entry, what register holds a string pointer? (0.5 points) __R3_______________

A comment is added above showing the reasoning.

3 in 4 got this right. 1 in 10 suggested R5, while a few suggested R4. A bit of partial credit was given for these wrong answers because at least the program uses these registers.

b) On entry, what register holds a character? (0.5 points) __R4_______________

A comment is added above showing the reasoning.

2 in 3 got this right. The majority of the wrong answers focused on R5 Again, a bit of partial credit was given for these wrong answers.

c) On exit, what register holds the result? (0.5 points) __R3_______________

A comment is added above showing the reasoning.

6 in 10 got this. 1 in 4 gave R5 for some credit — more than for the wrong answers given above because R5 indeed contains a more interesting value. Not credit was given to the few who suggested R4 which never changes, or for R1 the return address is not the return value.

d) Give a C function header for strchr. (0.5 points)

____char_*_strchr(_char_*_s,_char_c_)_________________________________

The names of the actual parameters given abive are arbitrary.

1 in 15 gave correct answers. Among the common small errors leading to deductions, almost 1 in 4 gave the wrong return type or omitted the type alltogether. A smaller deduction was given to those who said the return type was just char instead of char*. Fewer made mistakes on the parameters, adding a level of indirection (an extra *) was the most common, made by 1 in 15 on each parameter. A few simply omitted the parameter. 1 in 10 made various syntax errors.

Almost half earned no credit. The most common error was to confuse the concept of a C function header with that of a header file, and then give an #include preprocessor directive. Some people tried to write appropriat SMAL comments for the function header.

e) What does it do? (0.5 points)

__return_a_pointer_to_the_first_occurance_of_character_c_in_string_s__

__or_NULL_if_c_is_not_in_s____________________________________________

1 in 6 did well, while another 1 in 12 were penalized for suggesting that it returned the character instead of a pointer to that character, and another 1 in 8 suggested that it just tested to see if the character was in the string. Among the weaker answers, almost 1 in 6 did not understand what the code compared, while slightly more did state understand that there was some kind of return value.

1 in 10 left this blank, and 1 in 4 gave answers that earned no credit.

Background: Here is some SMAL Hawk code:

        LEA     R3,ARRAY
        LOAD    R4,R2,INDEX
        ADDSL   R4,R3,4        <-- multiplies index by 16
        LOAD    R3,R4,FIELD

a) Where is the array stored (what part of memory)? (0.3 points)

___Somewhere_in_ROM_near_the_code_____________________________________

1 in 6 got this. Among those earning no credit, 1 in 6 said it was a local variable, 1 in 8 said it was a global variable, and a similar number said RAM. Even stranger answers included read-write ROM, R3 and the CPU.

b) Where is the array index loaded from? (0.3 points)

___The_activation_record______________________________________________

6 in 10 got this. Among those earning no credit, 1 in 5 said R2, while a few gave odder answers such as R3, R4, or malloc.

c) How big is each array entry, in bytes? (0.3 points) ___16____________

1 in 4 got this. A little credit was given to the 1 in 12 who said 8 bytes (an off by one error). No credit was given to the 1 in 3 who said 4 bytes, the 1 in 5 wo said 2 bytes or 16 bits, or even odder answers such as 1/2, 16kb or 2¹⁸. A few left this blank.

d) Each element of the array is an instance of what kind of data? (0.3 points)

___A_record_(a_C_struct)_with_a_field_named_FIELD_____________________

1 in 10 got this. Wrong answers included 1 in 6 who said an integer, 1 in 8 who said a string, 1 in 10 who said a pointer, and more. It seems that these were guessing.

e) Give C code that is a reasonable equivalent to the above code. (0.3 points)

___array[index].field_________________________________________________

Two gave this. 1 in 4 omitted the field, while 1 in 10 used a -> instead of a dot to refer to the field. 1 in 6 added various arithmetic to the index, for example, multiplying it by 4.

Among those earning no credit, 1 in 6 gave odd code that seemed to be in C, while a similar number left it blank.

Background: Consider this C code:

void doit( node * n ) {
    if (n != NULL) {
        doit( n->left );
        (n->thing)( n->value );
        doit( n->right );
    }
}

A problem: Finish the following translation of this code to SMAL Hawk code: (3 points)

DOIT:                           ; void doit( node * n ) {
        STORES  R1,R2
        STORE   R8,R2,R8SV
        ADDI    R2,R2,ARSIZE
        MOVECC  R8,R3           ;   -- R8 holds n from here on
        
	_BZS___ _DOITQT________

        _LOAD__ _R3,R8,LEFT____
        JSR     R1,DOIT         ;   doit( n->left )

        _LOAD__ _R3,R8,VALUE___

        _LOAD__ _R1,R8,THING___
        JSRS    R1,R1           ;   (n->thing)( n-> value );

        _LOAD__ _R3,R8,RIGHT___

        _JSR___ _R1,DOIT_______ ;   doit( n->right )
        
DOITQT: _ADDI__ _R2,R2,-ARSIZE_

        _LOAD__ _R8,R2,R8SV____ ;   -- restore R8
        LOADS   R1,R2
        JUMPS   R1

There were several typos in the exam question as printed, but instructions were given in class for how to fix them (indicated above by boldface). The comments are not repaired by the corrections given, but an if statement could be added in the comments.

Of course, the label DOITQT has an arbitrary name, so any name will suffice.

1 in 10 earned full credit, 1 in 6 earned none. Just one student left this blank, but there were many answers that looked like random nonsense, including calls to STRLEN and STRCMP, answers were all the blanks were filled with ADD or MOVE instructions, and so on.

Where a relationship could be found between the code written and the solution, a 0.1 point penalty was assessed per wrong field in the assembly code. Where no relationship could be found, a 0.1 point penalty was assessed per field in the nonsense code, and a 0.1 point penalty was assessed for each missing field of instructions that would solve the problem.

It is clear that several students had no clue about the meaning of (n->thing)( n->value ). One put in a call to MULTIPLY, suggesting that the multiplication operator was implied by the two adjacent parentheses. In fact, this notation was discussed in Chapter 10 of the notes and in lecture on Oct. 31, where the example presented in class was distributed on line after class.

Exam 2: Midterm

Solutions and Commentary

Grade Distributions

Exam II

Exams I and II

Machine Problems 1 — 4

Homework 1 — 10

Total Scores

Exam Solutions and Commentary