CSI 333 -- Fall 2011 -- Solutions to the Sample Final ----------------------------------------------------- Question I: ----------- (a) Using a function incurs a run-time overhead unlike a macro. (b) The size of the array is 6 since the string has a terminating '\0' character. (c) memcpy(v2, v1, sizeof(v1)); (d) The "lbu" instruction sets the leading 24 bits of the target register to 0; the "lb" instruction sets the leading 24 bits of the target register to the sign bit of the byte value. (e) When the "space" directive is used, the array "input" may not be word aligned (i.e., its starting address may not be a multiple of 4). ============================================================================= Question II: ------------ (a) A9 (hex) = 10 x 16 + 9 = 169 (decimal). To convert 169 (decimal) into base 7 representation, we have Division Quotient Remainder 169 div 7 24 1 24 div 7 3 3 3 div 7 0 3 Hence, the answer is 331 (base 7). (b) Now, 17 (decimal) = 11 (hex) = 10001 (binary). To convert 0.3 (decimal) into binary, we have: 0.3 x 2 = 0.6 bit = 0 0.6 x 2 = 1.2 bit = 1 0.2 x 2 = 0.4 bit = 0 0.4 x 2 = 0.8 bit = 0 0.8 x 2 = 1.6 bit = 1 The bit pattern 1001 repeats indefinitely. Therefore, ---- 17.3 (decimal) = 10001.01001 (binary) (c) F8 (hex) = 1111 1000 (binary). Since the sign bit is 1, the integer is negative. Taking the 2's complement of the above binary value we get 0000 1000 which is +8 decimal. Therefore, the original value is -8 (decimal). ============================================================================= Question III: ------------- (a) c1: 0x0F and c2: 0x03 (b) $13: 0x10 and $15: 0xF8000000 (c) Let x denote the starting address of the array. Using the formula for computing addresses in column-major order, we have Address of A[0][4] = 380 = x + 4 * 4 * 5 + 4 * 0 That is, 380 = x + 80 or x = 300. In other words, the starting address of the array is 300 (decimal). (d) Note: We use $7 and $8 for scratch work. add $7, $6, $0 # $7 has a copy of the value in $6. sll $8, $7, 16 # $8 has the right half of the value # in $6 followed by 16 zeros. srl $7, $7, 16 # $7 has 16 zeros followed by the left # half of the value in $6. or $6, $7, $8 # Now, $6 has the swapped result. ============================================================================= Question IV: ------------ void modify (short *val) { short mask_seven = 0x80; /* Mask to check the bit in position 7. */ short mask_eleven = 0xF7FF; /* Mask to change the bit in position 11 to 0 without changing the other bits. */ short mask_three = 0x8; /* Mask to change the bit in position 3 to 1 without changing the other bits. */ if (*val & mask_seven) { /* Here, the bit in position 7 of *val is a 1. So, we must change the bit in position 11 to 0 (without changing the other bits). */ *val &= mask_eleven; } else { /* Here, the bit in position 7 of *val is a 0. So, we must change the bit in position 3 to 1 (without changing the other bits). */ *val |= mask_three; } } /* End of modify */ ============================================================================= Question V: ----------- void move_to_front (PNODE *phead, int x) { PNODE cur, prev; /* Pointers to traverse the list. */ /* We need prev for removing a node from the middle of the list. */ /* If the list is empty or the first node itself contains the value given by x, we do nothing. */ if ((*phead == NULL) || ((*phead)->key == x)) return; /* Here, the list is not empty and the first node does not have the value given by x. */ prev = *phead; cur = (*phead)->next; /* A node containing value x may occur later in the list. */ /* Traverse the list using cur and prev pointers. */ while ((cur != NULL) && (cur->key != x)) { prev = cur; cur = cur->next; } /* End of while loop. */ if (cur != NULL) { /* Here, cur points to the first node containing value x. */ /* We need to remove that node and move it to the beginning. */ /* (Here, prev can't be NULL.) */ prev->next = cur->next; /* Bypass the node with key x. */ /* The node pointed to by cur should become the first node. */ cur->next = (*phead)->next; *phead = cur; } } /* End of move_to_front. */ ============================================================================= Question VI: ----------- Part (a): --------- Register Assignment: $10 -- Addresses of the elements of array a. $11 -- Addresses of the elements of array b. $12 -- Variable i. $13 -- Variable count. $14 -- Contains the value 20 (the size of a and b). $15 -- Scratch work. $16 -- Scratch work. .data a: .byte 0:20 b: .byte 0:20 .text # It is assumed that values have been read into arrays a and b. li $13, 0 # Initialize count to 0. li $14, 20 # Size of array in $14. la $10, a # Starting addresses of a and b la $11, b # in $10 and $11 respectively. move $12, $0 # Initialize i to 0. loop: bge $12, $14, pri # When $12 becomes 20, the loop ends. lbu $15, 0($10) # Get a[i] in $15. lbu $16, 0($10) # Get b[i] in $16. bne $15, $16, skip # If a[i] != b[i] don't change count. addi $13, $13, 1 # Increment count. skip: addi $10, $10, 1 # Addr. of next element of a. addi $11, $11, 1 # Addr. of next element of b. addi $12, $12, 1 # i++ j loop pri: move $a0, $13 # Steps needed to print count. li $v0, 1 syscall Part (b): --------- The reverse function given below uses registers $8, $9, $10 and $11 for scratch work. #Some initialization. reverse: la $8, x # $8 has the start addr. of x. la $9, y # $9 has the start addr. of y. addi $9, $9, 9 # $9 has the addr. of the last char of y. li $10, 10 # $10 has no. of chars to be copied. # from x to y. copy_char: beqz $10, return # Return if all characters have been # copied. lbu $11, 0($8) # Get a char from x. sb $11, 0($9) # Put it at the end of y. addi $8, $8, 1 # Move forward in x. addi $9, $9, -1 # Move backward in y. addi $10, $10, -1 # Decrement the no. of chars to be copied. j copy_char # Loop back to copy other characters. # Here all characters have been handled. So, return: jr $31 =============================================================================