Andrew login ID:Full Name:CS 15-213, Fall 2006Final ExamThursday Dec 14, 2006• Make sure that your exam is not missing any sheets, then write your full name and Andrew login IDon the front.• Write your answers in the space provided below the problem. If you make a mess, clearly indicateyour final answer.• The exam has a maximum score of 92 points.• This exam is OPEN BOOK. You may use any books or notes you like. You may use a calculator, butno other electronic devices. Good luck!01 (06):02 (09):03 (06):04 (12):05 (12):06 (06):07 (15):08 (06):09 (04):10 (08):11 (08):TOTAL (92):Page 1 of 17Problem 1. (6 points):Floating point encoding. Consider the following 5-bit floating point representation based on the IEEEfloating point format. This format does not have a sign bit – it can only represent nonnegative numbers.• There are k = 3 exponent bits. The exponent bias is 3.• There are n = 2 fraction bits.Numeric values are encoded as a value of the form V = M × 2E, where E is exponent after biasing, andM is the significand value. The fraction bits encode the significand value M using either a denormalized(exponent field 0) or a normalized representation (exponent field nonzero). Any rounding of the significandis based on round-to-even.Below, you are given some decimal values, and your task it to encode them in floating point format. Inaddition, you should give the rounded value of the encoded floating point number. Give these as wholenumbers (e.g., 17) or as fractions in reduced form (e.g., 3/4).Value Floating Point Bits Rounded value9/32 001 00 1/41/321/163/3211112Page 2 of 17Problem 2. (9 points):Structs and arrays. The next two problems require understanding how C code accessing structures andarrays is compiled. Assume the x86-64 conventions for data sizes and alignments.You are given the following C code:#include "decls.h"typedef struct {int x[CNT2]; /* Unknown constant */int y;int z[CNT3]; /* Unknown constant */} struct_a;typedef struct{struct_a data[CNT1]; /* Unknown constant */int idx;} struct_b;void set_y(struct_b *bp, int val){int idx = bp->idx;bp->data[idx].y = val;}You do not have a copy of the file decls.h, in which constants CNT1, CNT2, and CNT3 are defined, butyou have the following x86-64 code for the function set_y:set_y:bp in %rdi, val in %esimovslq 168(%rdi),%raxleaq (%rax,%rax,2), %raxmovl %esi, 12(%rdi,%rax,8)retBased on this code, determine the values of the three constantsA. CNT1 =B. CNT2 =C. CNT3 =Page 3 of 17Problem 3. (6 points):Structs and arrays. As in the previous problem, assume the x86-64 conventions for data sizes and align-ments.You are given the following C code:#include "decls.h"typedef struct{type_t x; /* Unknown type */int y[3];} struct_a;typedef struct{int low;struct_a val[N]; /* Unknown constant */int high;} struct_b;int get_high(struct_b *bp){return bp->high;}You do not have a copy of the file decls.h, in which constant N and data type type_t are declared, butyou have the following x86-64 code for the function get_high:get_high:bp in %rdimovl 104(%rdi), %eaxretProvide some valid combination of these two parameters for which the assembly code would be generated.A. type_t:B. N =Page 4 of 17Problem 4. (12 points):Loops. Consider the following x86-64 assembly function, called looped:looped:# a in %rdi, n in %esimovl $0, %edxtestl %esi, %esijle .L4movl $0, %ecx.L5:movslq %ecx,%raxmovl (%rdi,%rax,4), %eaxcmpl %eax, %edxcmovl %eax, %edxincl %ecxcmpl %edx, %esijg .L5.L4:movl %edx, %eaxretFill in the blanks of the corresponding C code.• You may only use the C variable names n, a, i and x, not register names.• Use array notation in showing accesses or updates to elements of a.int looped(int a[], int n){int i;int x = ______________;for(i = ____________; ________________; i++) {if (___________________)x = _________________;}return x;}Page 5 of 17Problem 5. (12 points):Stack discipline. Below is a segment of code you will remember from your buffer lab, the section that readsa string from standard input.int getbuf() {char buf[8];Gets(buf);return 1;}The function Gets is similar to the library function gets. It reads a string from standard input (terminatedby \n or end-of-file) and stores it (along with a null terminator) at the specified destination. Gets has noway of determining whether buf is large enough to store the whole input. It simply copies the entire inputstring, possibly overrunning the bounds of the storage allocated at the destination.Below is the object dump of the getbuf function:08048c4b <getbuf>:8048c4b: 55 push %ebp8048c4c: 89 e5 mov %esp,%ebp8048c4e: 83 ec 38 sub $0x20,%esp8048c51: 8d 45 d8 lea 0xfffffff0(%ebp),%eax8048c54: 89 04 24 mov %eax,(%esp)8048c57: e8 f2 00 00 00 call 8048d4e <Gets>8048c5c: b8 01 00 00 00 mov $0x1,%eax8048c61: c9 leave8048c62: c3 ret(over)Page 6 of 17Suppose that we set a breakpoint in function getbuf and then use gdb to run the program with an input fileredirected to standard input. The program stops at the breakpoint when it has completed the sub instructionat 0x08048c4e and is poised to execute the lea instruction at 0x08048c51. At this point we run thefollowing gdb command that lists the 12 4-byte words on the stack starting at the address in %esp:0x08048c51 in getbuf ()(gdb) x/12w $esp0x55683a58: 0x003164f8 0x00000001 0x55683a98 0x0030bab60x55683a68: 0x003166a4 0x555832e8 0x00000001 0x000000010x55683a78: 0x55683ab0 0x08048bf9 0x55683ab0 0x0035b690A. What is the address of buf? 0x_________________B. When the program reaches the breakpoint, what is the value of %ebp? 0x__________________C. To which address will getbuf return after executing? 0x__________________D. When the program reaches the breakpoint, what is the value of %esp? 0x__________________E. Instead of having getbuf return to its calling function, suppose we want it to return to a function smokethat has the address 0x8048b20.Below is an incomplete sequence of the hex values of each byte in the file that was input to the program (wehave given you the first 8 padding values). Fill in the remaining blank hex values so that the call to Getswill return to smoke. Note that smoke does not depend on the value stored in %ebp.0x01 0x02 0x03 0x04 0x05 0x06 0x07 0x080x___ 0x___ 0x___ 0x___ 0x___ 0x___ 0x___ 0x___0x___ 0x___ 0x___ 0x___ 0x___ 0x___ 0x___ 0x___Page 7 of 17Problem 6. (6 points):Consider the following function for computing the dot product of two arrays of n integers each. We haveunrolled the loop by a factor of 3.int dotprod(int a[],
View Full Document