Andrew login ID:Full Name:Recitation Section:CS 15-213, Spring 2009Exam 1Tuesday, February 24, 2009Instructions:• Make sure that your exam is not missing any sheets, then write your full name, Andrew login ID, andrecitation section (A–J) on the front.• Write your answers in the space provided for the problem. If you make a mess, clearly indicate yourfinal answer.• The exam has a maximum score of 100 points.• The problems are of varying difficulty. The point value of each problem is indicated. Pile up the easypoints quickly and then come back to the harder problems.• This exam is OPEN BOOK. You may use any books or notes you like. No calculators or otherelectronic devices are allowed.• Good luck!1 (16):2 (22):3 (13):4 (13):5 (22):6 (14):TOTAL (100):Page 1 of 17Problem 1. (16 points):Consider a new floating point format that follows the IEEE spec you should be familiar, except with 3exponent bits and 2 fraction bits (and 1 sign bit). Fill in all blank cells in the table below. If, in the processof converting a decimal number to a float, you have to round, write the rounded value next to the originaldecimal as well.Description Decimal Binary RepresentationBias -----Smallest positive numberLowest finiteSmallest positive normalized----- −716-----54----- 1 010 01----- 13Page 2 of 17Problem 2. (22 points):Consider the C code written below and compiled on a 32-bit Linux system using GCC.struct s1{short x;int y;};struct s2{struct s1 a;struct s1*b;int x;char c;int y;char e[3];int z;};short fun1(struct s2*s){return s->a.x;}void*fun2(struct s2*s){return &s->z;}int fun3(struct s2*s){return s->z;}short fun4(struct s2*s){return s->b->x;}Page 3 of 17a) What is the size of struct s2?b) How many bytes are wasted for padding?You may use the rest of the space on this page for scratch space to help with the rest of this problem.Nothing written below this line will be graded.Page 4 of 17c) Which of the following correspond to functions fun1, fun2, fun3, and fun4?push %ebpmov %esp,%ebpmov 0x8(%ebp),%eaxadd $0x1c,%eaxpop %ebpretANSWER: ________push %ebpmov %esp,%ebpmov 0x8(%ebp),%eaxmov 0x8(%eax),%eaxmovswl (%eax),%eaxpop %ebpretANSWER: ________push %ebpmov %esp,%ebpmov 0x8(%ebp),%eaxmov 0x1c(%eax),%eaxpop %ebpretANSWER: ________push %ebpmov %esp,%ebpmov 0x8(%ebp),%eaxmovswl (%eax),%eaxpop %ebpretANSWER: ________Page 5 of 17d) Assume a variable is declared as struct s2 myS2; and the storage for this variable begins at ad-dress 0xbfb2ffc0.(gdb) x/20w &myS20xbfb2ffc0: 0x0000000f 0x000000d5 0xbfb2ffe8 0x000000000xbfb2ffd0: 0xb7f173ff 0x0000012c 0xbf030102 0x0000000c0xbfb2ffe0: 0xb7e2dfd5 0xb7f15ff4 0xbfb30012 0x000000f30xbfb2fff0: 0xb7e2e0b9 0xb7f15ff4 0xbfb30058 0xb7e1adce0xbfb30000: 0x00000001 0xbfb30084 0xbfb3008c 0xbfb30010Fill in all the blanks below.HINTS: Label the fields. Not all 20 words are used. Remember endianness!What would be returned by:fun1(&myS2) = 0x___________fun2(&myS2) = 0x___________fun3(&myS2) = 0x___________fun4(&myS2) = 0x___________What is the value of:myS2.b->y = 0x___________myS2.a.y = 0x___________myS2.z = 0x___________myS2.e[1] = 0x___________Page 6 of 17Problem 3. (13 points):Given the memory dump and disassembly from GDB on the next page, fill in the C skeleton of the functionswitchfn:int switchfn(int a, long b) {int y = 0, x = ____________;switch (a*b) {case 1:return 24;case 6:a = _______________;return a;case 0:return a + b;case 4:x = a;y*= b;break;case ____:a = y == x;case 3:b = y ____ x;case 5:return a ____ b;}return x == y;}Page 7 of 17There may be a few instructions you haven’t seen before in this assembly dump. data16 is functionallyequivalent to nop. setcc functions similarly to jcc except it will set its operand to 1 or 0 instead ofjumping or not jumping, respectively. cqto is the 64-bit equivalent of cltd.(gdb) x/7xg 0x4005c00x4005c0 <_IO_stdin_used+8>: 0x00000000004004a1 0x00000000004004940x4005d0 <_IO_stdin_used+24>: 0x00000000004004ac 0x00000000004004b40x4005e0 <_IO_stdin_used+40>: 0x00000000004004a5 0x00000000004004bc0x4005f0 <_IO_stdin_used+56>: 0x000000000040049a0x0000000000400476 <switchfn+0>: mov $0x0,%ecx0x000000000040047b <switchfn+5>: mov $0xdeadbeef,%edx0x0000000000400480 <switchfn+10>: movslq %edi,%rax0x0000000000400483 <switchfn+13>: imul %rsi,%rax0x0000000000400487 <switchfn+17>: cmp $0x6,%rax0x000000000040048b <switchfn+21>: ja 0x4004c5 <switchfn+79>0x000000000040048d <switchfn+23>: jmpq*0x4005c0(,%rax,8)0x0000000000400494 <switchfn+30>: mov $0x18,%eax0x0000000000400499 <switchfn+35>: retq0x000000000040049a <switchfn+36>: lea (%rdx,%rsi,4),%eax0x000000000040049d <switchfn+39>: data160x000000000040049e <switchfn+40>: data160x000000000040049f <switchfn+41>: nop0x00000000004004a0 <switchfn+42>: retq0x00000000004004a1 <switchfn+43>: lea (%rdi,%rsi,1),%eax0x00000000004004a4 <switchfn+46>: retq0x00000000004004a5 <switchfn+47>: mov %edi,%edx0x00000000004004a7 <switchfn+49>: imul %esi,%ecx0x00000000004004aa <switchfn+52>: jmp 0x4004c5 <switchfn+79>0x00000000004004ac <switchfn+54>: cmp %edx,%ecx0x00000000004004ae <switchfn+56>: sete %al0x00000000004004b1 <switchfn+59>: movzbl %al,%edi0x00000000004004b4 <switchfn+62>: cmp %edx,%ecx0x00000000004004b6 <switchfn+64>: setl %al0x00000000004004b9 <switchfn+67>: movzbl %al,%esi0x00000000004004bc <switchfn+70>: movslq %edi,%rax0x00000000004004bf <switchfn+73>: cqto0x00000000004004c1 <switchfn+75>: idiv %rsi0x00000000004004c4 <switchfn+78>: retq0x00000000004004c5 <switchfn+79>: cmp %ecx,%edx0x00000000004004c7 <switchfn+81>: sete %al0x00000000004004ca <switchfn+84>: movzbl %al,%eax0x00000000004004cd <switchfn+87>: retqPage 8 of 17Problem 4. (13 points):The function below is hand-written assembly code for a sorting algorithm. Fill in the blanks on the nextpage by converting this assembly to C code..globl mystery_sort # exports the symbol so other .c files# can call the functionmystery_sort:jmp loop1_checkloop1:xor %rdx, %rdxmov %rsi, %rcxjmp loop2_checkloop2:mov (%rdi, %rcx, 8), %raxcmp %rax, (%rdi, %rdx, 8)jg loop2_checkmov %rcx, %rdxloop2_check:dec %rcxtest %rcx, %rcxjnz loop2dec %rsimov (%rdi, %rsi, 8), %raxmov (%rdi, %rdx, 8), %rcxmov %rcx, (%rdi, %rsi, 8)mov %rax, (%rdi, %rdx, 8)loop1_check:test %rsi, %rsijnz loop1retPage 9 of 17void mystery_sort (long*array, long len){long a, b, tmp;while (_____ > _____){a = _____;for (b = _____; b > _____; b--){if (array[_____] > array{_____]){_____ = _____;}}len--;tmp = array[_____];array[_____] = array[_____];array[_____] = tmp;}}Page 10 of 17Problem 5. (22
View Full Document