15-213 Exam 1 Spring 2002 Solutions Question 1: Expression decimal binary ----------------------------------- Zero | 0 | 00 0000 --- | -3 | 11 1101 --- | -14 | 11 0010 ux | 51 | 11 0011 y | -3 | 11 1101 x >> 2 | -4 | 11 1100 TMax | 31 | 01 1111 ----------------------------------- Question 2: Description | Binary | M | E | Value ------------------------------------------------------------------ Positive Zero | 0 000 0000 | 0 | -2 | 0.0 ------------------------------------------------------------------ --- | 0 000 0101 | 5/16 | -2 | 5/64 ------------------------------------------------------------------ Largest Denormalized | 0 000 1111 | 15/16 | -2 | 15/64 ------------------------------------------------------------------ Smallest Normalized | 1 001 0000 | 8/8 | -2 | -1/4 ------------------------------------------------------------------ Negative Two | 1 100 0000 | 1 | 1 | -2.0 ------------------------------------------------------------------ --- | 1 110 1101 | 29/16 | 3 | -14.5 ------------------------------------------------------------------ Negative infinity | 1 111 0000 | --- | --- | -infty ------------------------------------------------------------------ Question 3: A. 4 B. 0 1 2 4 8 14 16 24 26 32 |--------------------------------------------------------| | c[0] | c[1] | pad | intp | union1 | pad | d | s | pad | |--------------------------------------------------------| C. 32 bytes D. 24 bytes Question 4: int foo (int op, int a, int b) { int result = 0; switch (op) { case 0: result = a & b; break; case 1: result = a | b; break; case 2: result = a ^ b; break; case 3: result = ~a ; break; case 4: result = a + b; break; } return result; } Question 5: A. -- alloc -- Uses the next free BP register to save the number of the last used stack register. Why don't we have to save the 'old base pointer'? There is a separate register for each stack frame. Hence, there's no need to save any values - they are automatically saved by the BPn registers. -- push -- Uses the next free STK register to save data on the 'stack' (and increments/decrements some index into the STK registers) -- pop -- Takes the value from the last used register and decrements/increments some index into the STK registers. -- call -- Uses the next free RET register to save the return address. Also jumps to the procedure B. What is the problem with using registers in this fashion? Registers only offer a limited, static amount of space. C. Why is the notion of a base pointer still required? If the call stack gets too large, the data in these registers still must be saved in a stack-ish area. Hence, the notion of a base pointer is still required because we may need to save these registers out to a area of memory. It's not really a base pointer in the same sense as we know, and the solution to the problem at hand (putting the 'base pointer' in the BP registers) isn't necessarily good either, but at some point, system software will have to save out these registers to a memory area, since the stack must remain valid Many people thought that we would still need some memory address to serve as the base pointer because we need it to index on the stack. However, imagine the case where the STK, BP, and RET sets of registers are infinitely large. Following the above solution for the operation of each instruction, it is possible to see that there is no reason to keep a base pointer (since there is a BP register for each stack frame and all the BP registers do is store an index - not a pointer) to be able to index into data. Question 6: Part A: Send some negative number for index such that cmds[index] is a bad address. Part B: Overflow buffer to set the return address to point into the buffer you sent, which contains the code to execute. Part C: The head of the buffer should contain the /etc/passwd entry. Overflow buffer to set return address into the buffer, which sets result_fname to point to "/etc/passwd" (stored in the sent buffer), and then code to jump to the line with open(). Question 7: FindMin: push %ebp push %ebp mov %esp, %ebp push %ebx -- save callee-save register mov 0x8(%ebp), %ecx -- ecx = A mov 0xc(%ebp), %edx -- edx = size mov (%ecx), %eax -- eax = min = A[0] mov \$0x0, %ebx -- ebx = i cmp %edx, %ebx -- cmp size, i jge .done .loop cmp %edx, (%ecx, %ebx, 4) -- cmp min, A[i] jge .incr mov (%ecx, %ebx, 4), %eax -- eax = min = A[i] .incr inc %ebx -- incr i cmp %edx, %ebx -- cmp size, i jl .loop .done pop %ebx -- restore callee-save reg. mov %ebp, %esp pop %ebp ret