======================= Floating Point Question ======================= 2 pts per letter a-f: 1 pt for correct location 1 pt for correct value 1 pt total for correct value/location, but wrong +/- 2 pts for letter g: full credit for correct answer (2^32 - 2^7) --> 2&32 1 pt for answers +/- approximately one exponent (2^32 - 2^8) or (2^32 - 2^6), or (2^32 - 2^7 - 1) =================== C Question - Part A =================== You were expected to find at least 4 bugs. Each bug was worth 1.5 points. 0.5 points - A correct bug description 0.5 points - A correct test case for the given bug description 0.5 points - Correct return values given the test case you gave. (0.25 each for the return values). NOTE: For highly incorrect bug descriptions, we subtracted all 1.5 points - this is to prevent people from giving arbitrary test cases without identifying bugs. There were other bugs present (Michael: some are in the solution): Exponent compared before sign no return value for equality Significand comparison is incorrect when both numbers are negative Incorrect comparisons when a and b have different length significands. 0 and -0 are not treated as equal i should be declared as an unsigned int, rather than a signed int. Sign test is inverted as '-' has a higher ASCII value as '+' Note: the dealing with nonnormalized numbers was not a bug. Being scientific notation, you were not allowed to have leading 0's. Also, since the class standard is C99, the declaration in the for loop is legal. =================== C Question - Part B =================== General Notes: If a solution would completely work we gave it full credit (despite extra lines, etc.). Generally 0.5 points were deducted for small errors, or 1 point was deducted for single significant errors or omissions. We did not deduct for repeated typing mistakes (like using -> where . was necessary), but we did deduct if the first line with blanks and the second line with blanks both incorrectly used vec->elts [i] as a pointer instead of a struct. Question totaled 9 points. Line A (total 1 point): 0.5 points for min_sigfigs as one arg, 0.5 points vec->elts [i].num_sigfigs. Only 0.25 points were deducted if the latter was off by only a parenthesis error. Line B (total 1 point): 0.5 points if only ampersand was missing. Line C (total 1 point): 0.5 for one of the blanks incorrect. No partial credit for reversal. Line D (total 1.5 points): 0.5 points deducted for each of (i) not using sizeof correctly (ii) not having +1 for null terminator (iii) wrong cast (iv) not using min_sigfigs. Capped at -1.5 points. No cast on the malloc had no points deducted, since automatic casting is OK. Answers that were far from correct were given no credit. Line E (total 1.5 points): 0.5 points given for b->significand, 0.5 points for min_sigfigs as index, 0.5 points for '\0' or equivalent. Answers that were far from correct were given no credit. Lines F through G: One point for each of (i) free(b->significand) (ii) b->significand = new_significand (iii) b->num_sigfigs = min_sigfigs if in a working order. Again, no points were deducted for working answers, but incorrect lines were marked off by 1 point each. Detailed Walkthrough -------------------- Here is a step-by-step solution in-line with the frame of code students were given. #define MIN(a, b) ((a)<(b)?(a):(b)) void clean_vector(sci_vector_t *vec) { unsigned int min_sigfigs = 0xFFFFFFFF; // Initialize to biggest unsigned int /* get min significant digits */ for (unsigned int i = 0; i < vec->num_elts; i++) min_sigfigs = MIN( _________________ , _________________); This section is a standard iterative process for finding the minimum (or maximum) of a set using a two-argument MIN (or MAX) operation. The MIN operation here is defined using a preprocessor macro. To get the minimum element of an array, we iterate over the array and keep a running "smallest-so-far" variable, here called min_sigfigs. At each loop iteration we update the smallest-so-far by choosing the smaller of the smallest-so-far and the current element. The loop invariant is that the statement is executed, min_sigfigs contains the smallest element of the array up to index i. When the loop has traversed the entire array we have the smallest element of the entire array. To achieve the above loop invariant, one of the arguments to the MIN operation must be min_sigfigs. The other should be the "current element" of the array, which in this case is the number of sigfigs in the i'th sci_bignum_t. We have to be careful of pointers to extract the correct value here. We are given a pointer to a sci_vector_t as an argument (vec) and we want to access the sci_bignum_t *elts field. We use the usual pointer- to-struct access syntax: vec->elts. The value of the expression is of type sci_bignum_t * as in the struct declaration, treated as an array of sci_bignum_t elements. Given the array of sci_bignum_t elements, we want to dereference the i'th sci_bignum_t. We can use the usual array dereference syntax added onto the above expression: vec->elts[i]. Note that this new expression is equivalent to *(vec->elts + i), and so we are performing pointer arithmetic to get the appropriate sci_bignum_t * and then dereferencing to get the appropriate sci_bignum_t. The sci_bignum_t that we have extracted is a struct, and so we can access one of its fields with the struct-access syntax added to the expression: vec->elts[i].num_sigfigs. We should not use the "->" syntax here because that is only appropriate to attach to a struct pointer, whereas our type here is a struct. Essentially, the [i] has already done the dereferencing for us. The final expression is vec->elts[i].num_sigfigs. It is important to follow the type of the expression at each step. The final result is equivalent to (*((*vec).elts + i)).num_sigfigs. /* truncate all elts to have min_sigfigs */ for (unsigned int i = 0; i < vec->num_elts; i++) { sci_bignum_t *b = _____________________ This loop is intended to iterate over all the struct_bignum_t elements in our sci_vector_t, and this line is intended to extract the appropriate struct_bignum_t * from the sci_vector_t *vec. Again we must be careful to extract the appropriate type. We want a struct_bignum_t *, and we see that the only one is the elts array in our sci_vector struct. Thus we want to access the elts field: vec- >elts. The expression has type struct_bignum_t *, but it's not the i'th struct_bignum_t * in elts (it is the 0'th), and so we need to perform some pointer arithmetic to get to the correct struct_bignum_t. We could simply add i to the expression and arrive at vec->elts + i or we could use the array indexing notation &vec- >elts[i]. In the latter case the ampersand is necessary because we want to extract the pointer to the struct_bignum_t and not the struct itself. if (______________________ > _______________________) The body of the loop is intended to truncate all struct_bignum_t elements to have the same size significands and the same min_sigfigs value. This is the test to see if the current element needs to be truncated to the minimum. An element needs to be truncated if its num_sigfigs is greater than the min_sigfigs value, or b->num_sigfigs > min_sigfigs. char *new_significand = (_______) malloc (_________________________________); There are two steps to the truncation process; first we need to reduce the number of sigfigs stored in the current struct_bignum_t. We essentially need to downsize an array on the heap. To resize an array, we start by allocating a new one of appropriate size by filling in the above line. We want malloc's argument to be the size of the new significand array, which needs to fit exactly min_sigfigs numerical (character) elements. However, whenever we are dealing with strings we need to be careful of the null terminator! The null terminator is an additional character stored in the significand array, and so we need to allocate a spot in the array for the null terminator in addition to the min_sigfigs number of numerical characters. The expression (min_sigfigs + 1) will give us the number of chars to include in our new array, and so we multiply by the size (in bytes) per char to get the argument to the malloc call: (min_sigfigs + 1) * sizeof(char); Since malloc retruns a void * result and we are assigning to a char * variable, the result should be cast to a char *. However, the casting isn't necessary because the compiler will essentially perform the cast for us, and so points were not deducted for leaving the cast area blank, though points were deducted for an incorrect cast. Now that we have allocated the new array space, we need too copy over the first min_sigfigs elements (and the null terminator) from the old significand array. This operation could be accomplished through a loop, but we are provided with a strcpy call two lines down and a hint that the next line is "for strcpy": _________________________________________ // for strcpy strcpy(new_significand, b->significand); The given code is intended to copy from the previous significand (b- >significand) to our newly allocated new_significand. We need to recall how strcpy (and any general string operation) traverses an array of characters; strcpy iterates along the character array until it reaches a null terminator, since the null terminator marks where to stop the string. We want strcpy to copy the first min_sigfigs numerical characters, and thus we want it to stop copying from b->significand when it passes min_sigfigs characters. We insert the "stop" sign with a null terminator after the first min_sigfigs characters: b->significand [min_sigfigs] = '\0'. Note we do not need to add one to min_sigfigs because the first min_sigfigs elements are at indexes 0 to (min_sigfigs - 1), and so we insert the '\0' terminating character immeiately after. The strcpy function copies this terminator to new_sigificand, but points were not deducted for assigning the new_significand terminator explicitly. Now we fill in some of the remaining lines below strcpy. We now have saved all the digits that we want to keep into new_significand, and thus we want to get rid of the old significand (since keeping it around would be a memory leak, as forbidden in the problem statement). After convincing ourselves that we definitely no longer need it, we get rid of the old significand with free(b->significand). We are then free to replace the significand pointer in our struct_bignum_t with new_significand. If we had replaced it before freeing we would have clobbered the reference to the old significand and thus been unable to free it. The call to free must come before the re-assignment of b->significand to new_significand. Now we have completely resized and replaced the significand in the current struct_bignum_t of the loop, and freed the memory holding the previous significand. The second part of the truncation is simply to update the num_sigfigs field to reflect the new size of the significand. The new num_sigfigs for all of the elements is the same, so we set b->num_sigfigs = min_sigfigs. That statement could be done at any point in the loop. Now we have finished our complete solution: #define MIN(a, b) ((a)<(b)?(a):(b)) void clean_vector(sci_vector_t *vec) { unsigned int min_sigfigs = 0xFFFFFFFF; // Initialize to biggest unsigned int /* get min significant digits */ for (unsigned int i = 0; i < vec->num_elts; i++) min_sigfigs = MIN( min_sigfigs , vec->elts[i].num_sigfigs); /* truncate all elts to have min_sigfigs */ for (unsigned int i = 0; i < vec->num_elts ; i++) { sci_bignum_t *b = &vec->elts[i]; if (b->num_sigfigs > min_sigfigs) { char *new_significand = (char *) malloc((min_sigfigs + 1) * sizeof(char)); b->significand[min_sigfigs] = '\0'; strcpy(new_significand, b->significand); free(b->significand); b->significand = new_significand; b->num_sigfigs = min_sigfigs; } } } ================ C->MIPS Question ================ HE’S A UNIX. HE’S DEFINITELY A UNIX. HE’S DEAD! Rubric created by and the question graded by: Alex Kronrod NOTE: I gave a lot of partial credit for this question. If you missed anything, try to understand what you did wrong and what we were expecting. Essentially, what this question is asking for is to convert the following C code into MIPS: int main(int argc, char **argv){ char *str; int result=0; while (--argc){ str = argv[argc]; while (*str++){ result++; } } return result; } Note that argv[0] is the name of the program and not an actual argument that you want to count the letters for! # this solution starts looking from the last argument argv[argc-1] until it reaches the first # argument argv[1] inclusively SOLUTION 1: main: li $v0, 0 # Other things you could have put (but not limited to): # "mv $v0, $0", "addu $v0, $0, $0", "and $v0, $v0, $0" # and best one that I saw: "xor $v0, $v0, $v0" word: addiu _$a0, $a0, 1__ beq __$a0, $0,_ done sll __$t0, _$a0_, _2__ addu _$t0, $a1, $t0___ lw $t1, 0($t0) ____ letr: lb $t2, 0($t1) ____ beq $t2, _$0__, word addiu $v0, $v0, 1____ addiu $t1, $t1, 1 __________________ #noop j _letr_____________ done: jr $ra # The next two solutions are traversing the arguments in order, from the first # argument argv[1] until it reaches the last argument argv[argc-1] inclusively SOLUTION 2: main: li $v0, 0 word: addiu _$a0, $a0, 1__ beq _$a0, $0,_ done addiu_ $t0, _$a1, _4_ lw $t1, 0($t0) ____ addiu $a1, $a1, 4___ letr: lb $t2, 0($t1) ____ beq $t2, __$0_, word addiu $v0, $v0, 1____ addiu $t1, $t1, 1 __________________ #noop j _letr_____________ done: jr $ra SOLUTION 3: main: li $v0, 0 word: addiu _$a0, $a0, 1__ beq _$a0, $0,_ done ____ $t0, ___, ____ #ignore, i.e. a no0p. For example "addu $t0, $t0, $0" addiu $a1, $a1, 4__ lw $t1, 0($t0) ____ letr: lb $t2, 0($t1) ____ beq $t2, __$0_, word addiu $v0, $v0, 1____ addiu $t1, $t1, 1 __________________ #noop j _letr_____________ done: jr $ra Rubric: 1 point: First line 1 point: Second line 1 point: Third line. -1/2 if compared to "-1", meaning that you are counting argv[0] point given if the register used is consistent with the register given on line 2. 2 points: Traversing the arguments correctly: +1 attempt to increment the argument, but fails to word align -1/2 if you read argv[0] - argv[argc-2], i.e. fail to realize that argv[0] is name of the program 4 points: Loading a pointer to an argument from the handle, +3 points for getting lw, -2 for using lb or lbu instead of lw. +1 point for correct operands 3 points: Loading a character correctly from the argument string +2 for using lb or lbu -1.5 for realizing you need to read something from memory, but using lw instread +1 point for correct operands 1 point each for the last three lines. -1/2 for switching order of args, i.e argc == $a1, argv == $a0. Quite a few people thought that main takes in "char *argv" instead of a handle, so they figured that the argument is one long string "I love cs61c". Since this question is asking more about mips rather than C, I deducted points for not realizing you needed to do two load instructions, so I deducted points for not using "lw $t1, 0($t0)" based on the rubric above and then graded your solution based on your assumption. Thus if you did the question "correctly" based on your assumption, you pretty much got half credit. Common Mistakes: * Many students used lw instead of lb when reading character from the argument string * Some students did "j word" instead of "j letr" * A lot of students didn’t know how to pass in arguments to the program using the command line (HW2 taught you this!) They thought that it is all one argument delimited by spaces. * Many students didn’t realize that argv[0] is the name of the program and not the first "argument" passed in through the command line. * Tons of students switched $a0 and $a1 * A lot of students were unable to word align when incrementing argv to point to next argument ================ MIPS->C Question ================ fun with MIPS a) worth 5 points b) worth 6 points c) worth 4 points a) correct answers something along the lines of: the lowest y bits of x x mod 2^y correctness based on a gradient of how close answer was to one of these -1 no conciseness/clarity b) -3 if any looping used -1 off by one error -1 add'l errors -1 not 1 line solution if incorrect value returned remaining score based on a gradient of how close to correct answer c) -1 for each register besides $s0, $s1 loaded and stored (the pair sw a_reg mem, lw a_reg mem counts as one) automatic score of 0 for c) if stack not properly reset ========= Potpourri ========= a) 1 pt, all or nothing. We accepted 2 more bits (the correct answer) and also N + 2, giving you the benefit of doubt that you did not read "MORE" bits and thought total bits b) 1 pt per row for a total of 5 pts for this part. Each column wrong = -0.5UP TO 1 point wrong max (even if you got the entire row wrong) c) 4 pts total. For a simple switch in order between two lines, -1 (so -1 per switch) unless it was a off by one error or you shifted an entire chunk to a different position (like you moved 7, 8, 9 to 5, 6, 7), then it was -2. For writing a number twice (on accident presumably) -1 pt. d) 2 pts, all or nothing. Had to be 16 kibithings. Though we did give 1 pt to people who did not write "kibi" but "kilo" e) 3 pts total. -1 for writing in size in incorrect column. -1 for getting a line that should have a value incorrect. -1 if we saw a bunch of extra incorrect lines. -1 for filling in multiple columns on a line. Detailed Explaination --------------------- a) For every bit added, we can represent twice the data. So if we add 1 more bit, we can represent only 2 times as many numbers, and with 2 more bits, we can represent 4 times as many numbers. Thus, the answer must be 2 more bits since it is the smallest amount of whole bits that can be added to represent 3 times as many numbers. b) A = 0xF, B = 0b0010, SUM = encode(decode-to-decimal(A) + decode-to-decimal(B)) SUM(S/M) = 0b1 111 + 0b0 010 = -7 + 2 = -5 =(encode)=> 0b1101 = 0xD The first bit is the sign (1 = negative, 0 = positive), the rest is the actual number SUM(1's) = 0b1 111 + 0b0 010 = -0 + 2 = 2 =(encode)=> 0b0010 = 0x2 Flip the bits if the first bit is 1, the resulting value is negative. Else, positive so do nothing. SUM(Unsigned) = 0b1111 + 0b0010 = 15 + 2 = 17 =(encode)=> 0b1 0001 = 0xD Treat all the bits as part of the number. Note that the sum is 17 = 0b10001, but since a nibble is only 4 bits, we have to ignore the first 1 to get the decimal/hex encoding of 1. This is an overflow. SUM(2's) = 0b1111 + 0b0010 = -1 + 2 = 1 =(encode)=> 0b0001 = 0x1 Flip the bits if the first bit is 1 and add 1, the resulting value is negative. Else, positive so do nothing. SUM(Bias) = 0b1111 + 0b0010 = 8 + (-5) = 3 =(encode)=> 0b0011 = 0x3 Treat numbers as unsigned numbers, but subtract 7 from the number since there is a bias of 7. (15 - 7) + (2 - 7) = 8 + (-5) = 3 Then, to encode the sum, you need to remember to add back the bias of 7, so 3 + 7 = 0xA | SUM | Decimal | Overflow? S/M | 0xD | -5 | no 1's | 0x2 | 2 | no Unsigned | 0x1 | 1 | yes 2's | 0x1 | 1 | no Bias of 7 | 0xA | 3 | no c) Pretty self explanatory -- 1. A CS61C student is assigned a project that implements big_nums. (given) 2. The student writes his or her code in C. (before you can translate code, you must write it) 3. The student's C code is translated into MIPS. (need C code before translating to MIPS) 4. MAL is translated into TAL. (you write MIPS as MAL initially, which is converted to TAL) 5. Link tables are produced. (tables showing dependencies of variables/symbols generated) 6. Code and Data from various places are stitched together. (all code is put together) 7. Links are "edited" (links to variables/symbols can be finalized once everything is put together) 8. Static, code, and global space are reserved/initialized in memory. (loading the program) 9. Execution begins at main. (running final product) d) 1 zebibyte = 2^70, 512 = 2^9 so in total, to represent 512 zebibytes, we need 70 + 9 bits = 79 bits. 9 = 4 bits, 50 bits to have 2^50 things so in total, it takes 4 + 50 = 54 bits to represent 9 x 2^50 things. 2000 = 2^11 (equals 2048) so need 11 bits to represent 2000 things. Thus, taking the total number of bits (79) - used bits (54 + 11): 79 - 54 - 11 = 14 bits left over 1 kibithing takes 10 bits, so that leaves 4 bits left which can represent 16 numbers. Putting that together, we have up to 16 kibithings that can be represented with the 14 bits left over. e) The entire typedef struct from lines 1-5 would not allocate any memory since it is not a declaration of a variable (remember typedefs act as a sort of definition of a "search and replace" of types). It is not until line 6 that an actual variable is declared, a pointer of type bignum_t with a size of 4 bytes (32-bits) since all pointers are the same size, no matter the data being pointed to. This bignum_t * lives in static space because it is outside of all functions (main). Line 9 has 108 bytes allocated on the stack since it is a local variable declared within a function and will go away when the function ends (main). 108 bytes is from (int + char* + char[100]) = 4 bytes (int) + 4 bytes (pointer) + 100 bytes (1 byte per char) = 108 bytes total. Line 10 has 5 bytes on the heap since it is dynamically allocated with malloc and 5 * sizeof(char) == 5 * 1 == 5 byes (since chars are 1 byte big).