CS 61C Fall 1994 Midterm 1 solutions 1. Binary to hex. Divide the binary number into groups of four bits: 1010 1011 1011 1010 Then convert each group to a hex digit: A B B A So the answer is 0xABBA. There's no need to convert to decimal as an intermediate step; if you did that, you're not understanding the whole point of hex! We use it as a quick, easy abbreviation for binary. We also accepted -0x5446, although hex numerals are almost always taken as unsigned. Scoring: one point, right or wrong. 2. What's the address? start address size in bytes .data a: .word 0 0xff00 4 b: .word 1:2 0xff04 8 c: .byte 3:4 0xff0c 4 (Each number in the "start address" column is computed by adding the previous size to the previous start address.) So, the last element of c is c[3], which is at address 0xff0f, which is 0xff0c + 3. A few people thought that the addresses would count downward because these variables are on the stack. Nope. The stack is for local variables of procedures. Things that you declare in the data area are *global* variables; they live in between the program code and the heap. Scoring: 2 points if correct. We gave 1 point for 0xff10 (the address *after* the last element of c) and for 0xff15 (what you get by adding 15 decimal to 0xff00 and not noticing that you can't do that). Otherwise zero. 3. Find the errors. There were five errors: 1. Register $0 is always zero and can't be used as a destination. 2. The LW instruction should be SW (store word). 3. The memory argument must come after the register argument in LW and SW instructions. 4. The offset 2 should be 8 because we're using an array of words, not bytes. 5. The base register should be $10, not $8. The correct program is __start:li $8, 1 li $9, 1 ADD $11, $8, $9 la $10, array SW $11, 8($10) done Only the two instructions shown in capital letters need be changed. Note: You can't use the MOVE instruction with a memory operand. MOVE only works with two register operands. Scoring: One point for each error corrected, to a maximum of four (so you could miss one of them), minus one point for each non-error that you thought you had to correct. A few people completely rewrote the program instead of correcting this one; they got 2 points if their program worked. 4. Why is twos complement better? Reason 1: The same algorithm (and therefore the same hardware) that adds unsigned integers works for signed integers in twos complement. The other two representations must treat signed arithmetic specially. Reason 2: In twos complement there is only one representation for zero. This is good because testing for equality doesn't have to recognize two different bit patterns with equal values. There were several answers to which we gave partial credit. Most of them seemed to us to have been copied from the book without full understanding. For example: "The same hardware works for adding positive and negative numbers." This property distinguishes twos and ones complement from sign- magnitude, but doesn't distinguish twos from ones complement. What distinguishes those formats is that for signed arithmetic, ones complement format requires extra hardware -- wrapping the carry out from the leftmost bit into the rightmost bit -- that isn't used for unsigned arithmetic. "Addition of negative numbers works." Pfui. All of these representations can be made to work; I grew up with sign-magnitude computers, and they added and subtracted signed integers just fine. What you meant was that *the same algorithm that adds unsigned integers* also works for signed arithmetic. "Arithmetic is easier." Well, yes, but why? This answer didn't convince us that you really understand anything about what makes one representation better than another. Less impressive than any of those was "A larger range of values can be represented, down to -2^(N-1) instead of -(2^(N-1) - 1)." This is essentially the same answer as "there's only one zero" and it focuses on the least important aspect of that reason. Out of four billion representable numbers, one additional number is an improvement of 0.0000000025%, not very interesting. The absolutely worst answer we saw was "A larger range of values can be represented, from -2^N to 2^N instead of from -2^(N-1) to 2^(N-1)"! That would be a good trick, if using a different representation could change the fundamental law that N bits can represent 2^N values. Scoring: Two points per reason, with partial credit as above. 5. Translate C to MAL. Here is the most straightforward solution. It uses registers $16, $17, and $18 to hold x, y, and z, respectively. foo: add $sp, $sp, -24 # prologue sw $31, 0($sp) sw $16, 4($sp) sw $17, 8($sp) sw $18, 12($sp) sw $4, 16($sp) # preserve original arguments sw $5, 20($sp) sll $4, $4, 6 # a << 6 jal fun move $17, $2 # y = fun(a << 6) lw $4, 20($sp) # b jal fun move $18, $2 # z = fun(b) lw $8, 16($sp) # a lw $9, 20($sp) # b add $8, $8, $18 # a + z add $9, $9, $19 # b + y mul $16, $8, $9 # x = (a + z) * (b + y) move $2, $16 # return x lw $31, 0($sp) # epilogue lw $16, 4($sp) lw $17, 8($sp) lw $18, 12($sp) add $sp, $sp, 24 jr $31 By using saved registers more frugally, it is possible to write correct solutions using as few as 16 bytes of stack space. But a lot of people who tried that didn't succeed. Several people during the exam wanted to know more about the procedure fun. But, you see, the whole point is that the C compiler doesn't know what fun does either! The reason for register and stack conventions is precisely so that you can compile one procedure without having to see the procedures it calls or the procedures that call it. Scoring: 6 correct 3-5 has the idea 1-2 has an idea 0 other Some typical mistakes and their scores: 5 Program works but violates register/stack conventions 4 Assumes that fun will not change $5 3 Doesn't save the saved registers 2 Doesn't even save $31 1 Doesn't call fun twice 0 Calls putc or some such I/O thing instead of returning a value 6. Recursive function in MAL. One saved register will be needed to preserve the value returned by the first recursive call during the second one. pascal: add $sp, $sp, -16 # prologue sw $31, 0($sp) sw $4, 4($sp) sw $5, 8($sp) sw $16, 12($sp) li $2, 1 # return 1 if base case beqz $5, ret beq $4, $5, ret addi $4, $4, -1 addi $5, $5, -1 jal pascal move $16, $2 # save pascal(n-1, r-1) lw $4, 4($sp) # get original args back lw $5, 8($sp) addi $4, $4, -1 jal pascal # pascal(n-1, r) add $2, $2, $16 # return pascal(n-1, r-1) + pascal(n-1, r) ret: lw $31, 0($sp) # epilogue lw $16, 12($sp) add $sp, $sp, 16 jr $31 Again, it's possible to save a little stack space by being very clever. You can write pascal in a way that preserves the values in $4 and $5, and rely on that to avoid having to save them on the stack. But a compiler would have to be very clever indeed to work that out, and most people who tried it messed up. Scoring: 7 correct 4-6 has the idea 1-3 has an idea 0 other Some typical mistakes and their scores: 6 Program works but violates register/stack conventions 5 Assumes that recursive call will not change $4, $5, or $8 4 Doesn't save the saved register 3 Doesn't even save $31 2 Tries to use looping instead of recursion 1 No procedure calls at all 0 Calls putc or some such I/O thing instead of returning a value