2005Fa CS61C Midterm Answers v1.1 (2005-10-19 @ 13:00) 3 hours 15 minutes, 6 questions Grading Standard Legend GS = Grading Standard NPC = No Partial Credit ;;;;;;;;;;;;; ;; Question 1 - Potpourri ;;;;;;;;;;;;; [11 total] ;; a) [1 NPC] big-endian (she said "thirty" first, the 'big' part of the number) GS: All or nothing ;; b) [2 (1 each)] addi $t7, $k0, 0x6821 op rt rs imm 6 5 5 16 opcode rs rt imm (note the rs & rt are swapped...common error!) addi $k0 $t7 0x6821 001000 11010 01111 0x6821 0010 0011 0100 1111 0x6821 0x2 0x3 0x4 0xF 0x6821 Hex: 0x234F6821 Char: (little endian) "#Oh!" (lookup in green sheet) (big endian) "!hO#" GS: If hex was incorrect, but char translated correctly, char gets full marks each part is all or nothing... no partial credit for partially correct hex/char ;; c) [4 total (1 each, NPC)] [1] copying > M&S : After copying our data, we can *defragment*, recovering our slivers [1] RC > copying : Copying can only use half of memory & thus garbage collects twice as early [1] buddy > slab : When you have a lot of malloc requests for one small size (the buddy can adaptively give you more, but the slab has a fixed allocation). [1] slab > K&R : When you have lots of small malloc requests of size 2^n (it will use its bitmap, have no internal fragmentation, and not have to bother searching the freelist which may contain many small "pebbles") ;; d) [3] bfni $a0 done ==> lui $at 0x7F80 # $at = 0111 1111 1000 0000 0000 0000 0000 0000 or $at $at $a0 # Turn on all the Exponent bits beq $at $a0 done # Branch if no change,bits were already all on=255 (NaN/Inf) or srl $at,$a0,23 # Shift over past the mantissa andi $at,$at,255 # Throw the sign away slti $at,$at,255 # Set if NOT Inf/NaN beq $at,$0,done # branch if 0 (it WAS a NaN/Inf) or srl $at,$a0,23 # Shift over past the mantissa andi $at,$at,255 # Throw the sign away xori $at,$at,255 # 0 iff Inf/NaN beq $at,$0,done # branch if 0 (it WAS a NaN/Inf) GS: -1 for clobbering regs instead of using $at -1 for using MAL when you're only allowed to use TAL (this includes long immediates, branches w/ immediates, etc) -1 if it sorta works, but not for all cases (e.g. negative NaN) or if you had a small error in the code that prevented it from working -2 if the code really doesn't work at all (rare for people who actually obeyed all the rules) minimum score of 0 ;; e) [1, NPC] Assembler GS: All or nothing ;;;;;;;;;;;; ;; Question 2 - Opcode reorg ;;;;;;;;;;;;; [7 total] [5 total, 1 each, NPC] 6 bits of function for R doesn't change => 2^6 = 64 Rs before and after 2 Js before and after Before: 6 bits of opcode - "R 0" - "Jump 2" - "Jal 3" = 2^6-3 = 61 I inst After : MSB can't be used! That's 5 opcode bits - "R 0" = 2^5-1 = 31 I inst current: R,I,J = 64,61,2 proposed: R,I,J = 64,31,2 If you were off by one consistently for the instruction type counts, then you earned one point back. [1 for the pro that talks about the BIG change below for Js NPC, 1 for any con that says "fewer I-format insts" NPC] pros: Js now can have a 30-bit wide target, and don't need the PC's upper 4 bits (i.e., Js can now jump ALL around memory)! The key idea is to notice that Jump instructions have more bits for the JUMP TARGET, not immediate. Therefore, as long as you indicated this idea, full credit. con: non-standard opcode width means more difficult for hardware to decode fewer instructions (I format specificially) <-- (this is all we looked for when grading) have to reprint books, green sheets, etc. If you did not notice the lost in instruction type count, no credit for this part. ;;;;;;;;;;;;; ;; Question 3 - Number encoding ;;;;;;;;;;;;; [16 points] ;; a) 0x80000008 [8 total, 1 for decimal value NPC, 1 for mark and {RIGHT,LEFT,ON} pair NPC] 0x80000008 = 0b1000 0000 0000 0000 0000 0000 0000 1000 ENCODING : VALUE : [MIN ~MIDDLE MAX ] LFNL unsigned int: 2^31 + 8 : [0 2^31 2^32-1] MIN|---|---*---|---|MAX (RIGHT) s/mag : -8 : [-2^31 0 2^31 ] MIN|---|---*---|---|MAX (LEFT) signed int : -2^31 + 8 : [-2^31 0 2^31-1] MIN*---|---|---|---|MAX (RIGHT) float : -2^-146 : [-2^128 0 2^128 ] MIN|---|---*---|---|MAX (LEFT) float thoughts... 0) The 1 sign bit means it's a negative number 1) The exponent is a 0 so we're talking about a denorm => 0.MMM...M x 2^-126 2) Filling in the mantissa yields 0.000 0000 0000 0000 0000 1000 x 2^-126 3) 0.000 0000 0000 0000 0000 1000 = 2^3 * 2^-23 = 2^-20 4) Thus, this number is 2^-20 * 2^-126 = 2^-146 5) The linear range of floats is from -2^128 to 2^128 (huge in comparison) ;; b) MIN|---*---|---|---|MAX [8 total, 1 for decimal value, 1 for hex value NPC] ENCODING : [MIN 1/4 1/2 3/4 MAX] <-- aligning to 'simpler' number unsigned char : [ 0 64 128 192 255], so 64 = 0100 0000 = 0x40 sign/mag byte : [-127 -64 0 64 127], so -64 = 1100 0000 = 0xC0 signed char : [-128 -64 0 64 127], so -64 = 1100 0000 = 0xC0 float : [-2^128 -2^127 0 2^127 2^128], so -2^127 = 1 11111110 0...0 = 0xFF000000 ;;;;;;;;;;;;; ;; Question 4 - BSTs ;;;;;;;;;;;;; [17 points, 8 + 3 + 6] ;; a) /* We didn't dock points for those who didn't check malloc's retval != NULL) */ Insert(bst_t *table, const char *key, const char *value) { if (table == NULL) { /* new */ /* Make a new bst */ if ((table = (binarytree_t *) malloc (sizeof(binarytree_t))) == NULL) exit(1); /* Malloc couldn't find space for the struct! */ /* Copy the key in (don't need a malloc because key[80] is on stack) */ strcpy(table->key,key); /* Allocate enough space for the value string (note +1 for \0) */ if ((table->value = (char *)malloc(sizeof(char)*strlen(value)+1)) == NULL) exit(1); /* Malloc couldn't find space for the string! */ /* Copy the value into struct */ strcpy(table->value, value) /* Set the left and right pointers of this leaf node to NULL */ table->left = table->right = NULL; } else if (!(cmp = strcmp(key, table->key))) { /* clobber */ /* Free the space from old value string */ free(table->value); /* Allocate enough space for the value string (note +1 for \0) */ if ((table->value = (char *)malloc(sizeof(char)*strlen(value)+1)) == NULL) exit(1); /* Malloc couldn't find space for the string! */ /* Copy the value into the struct */ strcpy(table->value, value) } else if (cmp < 0) { /* left */ /* Set this table's left child to the retval of adding it below */ table->left = Insert(table->left, key, value); } else { /* right */ /* Set this table's right child to the retval of adding it below */ table->right = Insert(table->right, key, value); } return table; } GS: Each if/else if/else clause is worth 2 points, for a total of 8. Well, actually, in practice, the first clause was worth 3 pts and the second, 1 point. The most important part was the recursion steps in the last two clauses. Failure to do any recursion most likely would result in losing all 4 points for these 2 parts. If they successfully called Insert but did not get the assignment to table->left and table->right pointers, they get one off for each for a total of 2 points off. In the second clause, one point should be taken off for leaving out the malloc and/or free for value (meaning that even if they forget both, they still only lose 1 point total). The first clause was nasty. They lost a point for each of the following (up to a max of 3): - not initializing left and right - not malloc-ing value - not using strcpy (just doing straight assignment) - malloc-ing key Furthermore, if they did not check to make sure table is not null before they dereference, I took off either 1 or 2 points, depending on how bad this was in relation to the rest of the code. Also, if they did not even malloc a null table before using it, i usually took off 2 points, because this usually reflected a number of other serious flaws in the code...if the rest of the code looks good and they really did just forget it, maybe only taking off 1 point would be good. Also, general things, take off one point for each of the following: - incorrect sign on strcmp (only 1 point overall) - wrong dereferencing (only 1 point overall) - forgetting to add 1 to the length allocated for "value" (for the null character. You will notice that there are more negatives than there are points for this problem...these are the guidelines for the low scores. 3 points - basic code structure is sorta there (recursive calls to Insert, without assigning to left and right fields, some setting and allocations for various fields done right, alot of mistakes but still knows what is going on...) 2 points - borderline knowing what is going on...but at least they called Insert recusively correctly. Tried to set up the fields in a node if it was empty. 1 point - weird weird code. Tried to do an iterative solution but failed. Did not call Insert correctly and mostly did not initialize/update node field right. 0 points - largely incomplete, or started a solution that was totally wrong but didn't even get it done. ;; b) [3 total, 1 off for each wrong, NPC] Line 1 static: 4 (head ptr) stack : 0 heap : 0 Line 3 static: 0 stack : 92 = sizeof(bst_t) = 80+4+4+4 heap : 0 Line 4 static: 12 (static strings); 0 also accepted stack : 0 heap : 100 = sizeof(bst_t) + sizeof(8*char) = 80+4+4+4+8 GS: Some people thought we meant that we were talking about the accumulated (running total) values, in which case the answers were: Line 1 static: 4 (head ptr) stack : 0 heap : 0 Line 3 static: 4 stack : 92 = sizeof(bst_t) = 80+4+4+4 heap : 0 Line 4 static: 16 (static strings); 4 also accepted stack : 92 heap : 100 = sizeof(bst_t) + sizeof(8*char) = 80+4+4+4+8 One more note, it is one point off per wrong number...not per line. Which is mostly fine because if someone missed more than one, they ended up missing all the non-zero values. ;; c) [6 points, -2 for each missing part (deletekids, freevalue, freeme), (min 0)] /* Any of the lines labeled '1' can be done in any order but all before '2' */ Delete(bst_t *table) { if (table != NULL) { Delete(table->left); /* 1 */ Delete(table->right); /* 1 */ free(table->value); /* 1 */ free(table); /* 2 */ } return; } Here were some common deductions: - 1 point off for freeing table->key - 1 point off for not freeing table->value - 2 points off for freeing only the leaves of the tree - 1-2 points off for not checking if table was NULL first (1 point off if they had some weird convoluted solution that might have worked except in the case that the initial call was a null pointer, 2 points if they just forgot all together). - 2 points off for not freeing table cause there are probably other issues relating to this problem anyways ;;;;;;;;;;;;; ;; Question 5 - Life1D C->MAL ;;;;;;;;;;;;; [10] // return(rule & (1 << ((a2 << 2) | (a1 << 1) | a0)) ? 1 : 0) sll $a1,$a1,1 # n << 1 --- ^^^ --- --- or $t0,$a1,$a0 # t0 = (n << 1) | a0 --- ^^^ --- --- sll $a2,$a2,2 # nw << 2 --- ^^^ --- --- or $t0,$t0,$a2 # t0 = (nw << 2) | (n << 1) | ne --- --- --- --- ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ li $t1,1 # t1 = 1 --- --- --- sllv $t1,$t1,$t0 # t1 = 1 << ((nw << 2) | (n << 1) | ne) --- --- --- --- ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ and $v0,$a3,$t1 # v0 = rule & (1 << ((a2 << 2) | (a1 << 1) | a0)) --- --- --- --- srlv $v0,$v0,$t0 # v0 >> ((a2 << 2) | (a1 << 1) | a0) ___ ___ ___ ___ jr $ra There was a clever optimization we uncovered in a student solution. Instead of the C expression above, they had: // return(1 & (rule >> ((a2 << 2) | (a1 << 1) | a0))); ...which turns into the optimized MIPS code (saving two lines!!) sll $a1,$a1,1 # n << 1 --- ^^^ --- --- or $t0,$a1,$a0 # t0 = (n << 1) | a0 --- ^^^ --- --- sll $a2,$a2,2 # nw << 2 --- ^^^ --- --- or $t0,$t0,$a2 # t0 = (nw << 2) | (n << 1) | ne --- --- --- --- ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ # --- --- --- srlv $v0,$a3,$t0 # v0 = rule >> ((nw << 2) | (n << 1) | ne) --- --- --- --- andi $v0,$v0, 1 # v0 = 1 & (rule >> ((nw << 2) | (n << 1) | ne)) --- --- --- --- ___ ___ ___ ___ jr $ra GS: Basically 2 for each piece of the C code: +2 : shift a0,a1,a2 to the right place +2 : or them together +2 : for shifting the 1 to the right place +2 : for anding the shifted 1 with the rule +2 : for shifting that and result back to the 0th bit Just to note that there was another very common solution: instead of srlv $v0,$v0,$t0 do sltu $v0, $0, $v0 Another not so uncommon solution was sltu $v0, $v0, 1 xor $v0, $v0, 1 However a common mistake was doing nor $v0, $v0, 0 instead of xor which doesn't have the desired effect. People got only 1 point off for doing nor (very subjective of me, but at least they showed that they realized that 10 needs to be normalized to 1) Yet another solution was and $v0, $a3, $t1 beq $v0, $0, end addi $v0, $0, 1 end: jr $ra Many people though did something really stupid like beq $v0, $0, 1 and got no points Also, there was variation on how the initial shifts and ors were ordered: For example, this solution got all points: sll $a1,$a1,1 sll $t0,$a2,2 or $a2,$a1,a2 or $t0,$a0,$a2 I did not take points off for addi $t1, $0, 1 instead of li $t1, 1 I did take off one point for skipping that altogether and doing sllv $t1, 1, $t0 and I took all two points off for doing something like sll $t1, $t0, 1 since that's absolutely wrong (and it's not like they can claim they were confused what is being shifted by what, because by that time they have done it twice already with a1 and a2) Some typos like stating sll instead of sllv, or stating slli were not penalized, Some typos that made it unclear if the student understood it were penalized one point overall, for example, people who flipped a1 and a2 when shifting by 1 and 2 were apparently unable to pickout what is a1 and a2 in function argument passing and lost a single point on this confusion, since this was not the objective of the problem, but showed some negligence. ;;;;;;;;;;;;; ;; Question 6 - MIPS->C odd counting ;;;;;;;;;;;;; ;; a) int odd_odds(int *p) { if (*p == 0) return(0); else return(1 & (*p ^ odd_odds(p+1))); } /* or */ int odd_odds(int *p) { return(*p ? 1 & (*p ^ odd_odds(p+1)) : 0); } GS: 7 points possible: 2 for prototype 2 for base case and conditional 3 for recursive case -1: Some people used '+' instead of '&' which was probably from reading the andi instruction too quickly. -0.5: Some people used % 2 instead of the & which has the same effect, but it's not what the assembly was doing. ;; b) 1 iff the number of odds in a 0-terminated int array is odd (else 0) 1 iff the sum of the elements in a 0-terminated int array is odd (else 0) GS: 2 points possible, NPC ;; c) 1 iff the number of odds in a 0-terminated int array is even (else 0) 1 iff the sum of the elements in a 0-terminated int array is even (else 0) GS: 2 points possible: If part b was wrong, partial credit was given (1 or 2) if the answer was the compliment or inverse of the answer in a. ;; d) If the int at the address in $a0 is 0, the previous $v0 is returned If the int at the address in $a0 is even, then same as (b) If the int at the address in $a0 is odd, then same as (c) GS: 2 points possible Many people missed the base case here which was -1 point. If someone indicated that the result was garbage or undeterministic, that was accepted as well because we have no control over what was in $v0 before. Some students mentioned that $v0 is initialized to 0. This is not true. Assembly does not have any of those features from higher level programming languages.