Andrew login ID:Full Name:CS 15-213, Spring 2002Final ExamMay 9, 2002Instructions: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 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. You may use a calculator, butno laptops or other wireless devices. Good luck!1 (7):2 (9):3 (8):4 (8):5 (15):6 (10):7 (9):8 (5):9 (8):10 (9):TOTAL (86):Page 1 of 22Problem 1. (7 points):In this problem, you will complete a function that converts float to int without explicit use of a conversionoperator.The following information may prove useful.The IEEE float type uses 1 bit for sign, 8 bits for the exponent (with a bias of 127), and 23 bits for thefraction.Your function shouldtruncate floating pointing numbers (i.e., round toward zero). For example: ,.Since you are writing the conversion function, you may not use the built-in type conversion facilities ofC. You may not use relational operators (<, ==, and so on) taking floating point arguments. Keep in mindthat C does not allow the use of bitwise operators on floating point types.In the event of overflow or infinity, you should return the largest (INT MAX) or smallest (INT MIN)representable integer, as appropriate.NaN (not a number) should be converted to 0.The following is the framework for the conversion function. Fill in the blank lines with an appropriate Cexpression.union conv {float f;unsigned long u;};int float2int(float f){union conv conv;unsigned long u;int sign,exp,frac,shift;conv.f = f;u = conv.u;if ( ____________________ )sign = -1;elsesign = 1;exp = _________________________ ;frac = ________________________ ;if ( ____________________ ) /* zero or denormalized */return 0;if ( ____________________ ) {if ( __________________ ) /* NaN */return 0;else if (sign > 0) /* +Inf */return INT_MAX;elsereturn INT_MIN;}Page 2 of 22/* Add implicit 1.x in normalized representation */frac |= 1 << 23;/* compute decimal point position, i.e., total right shift needed */shift = _______________________ ;if (shift > 0) {if (shift > 32)return 0;elsereturn sign * (frac >> shift);} else {if (-shift > 32) {if (sign > 0)return INT_MAX;elsereturn INT_MIN;}return sign * (frac << -shift);}}Page 3 of 22Problem 2. (9 points):Part 1Given the assembly for the function mystery1, fill in the corresponding function in C.<mystery1>:push %ebpmov %esp,%ebppush %ebxsub $0x18,%espmovl $0x0,%ecxmovl $0x0,%ebx.L1cmp 0xc(%ebp),%ebxjl .L2jmp .L3.L2mov 0x8(%ebp),%eaxmov (%eax,%ebx,4),%edxadd %edx, %ecxincl %ebxjmp .L1.L3mov %ecx,%eaxpop %ebxmov %ebp,%esppop %ebpretint mystery1(int A[], int n) {int i;int mystery = _______; % answer: 0for (_________________________________) % answer: i = 0; i < n; i++{_________________________________; % answer: mystery += A[i];}return(________________); % answer: mystery}Page 4 of 22Part 2<mystery2>:push %ebpmov %esp,%ebpsub $0x18,%espmov 0x8(%ebp),%edxmov 0xc(%ebp), %ecxcmp %ecx, %edxjge .L1add $0xfffffff8,%espsub %edx,%ecxpush %ecxpush %edxcall mystery2add $0x10,%espjmp .L3.L1cmp %ecx, %edxjle .L2add $0xfffffff8,%esppush %ecxsub %ecx,%edxpush %edxcall mystery2add $0x10,%espjmp .L3.L2mov %edx,%eax.L3mov %ebp,%esppop %ebpretA. What would the following function call return?x = mystery2(6, 4);x = _________________________________ % answer: 2B. What is the mystery2 function computing?Page 5 of 22Problem 3. (8 points):This question is testing your understandingof the stack frame structure.Part I The following memory image embeds a binary tree with root node at 0x804961c. Please draw thelogical organization of the tree in the same format as the shown example. Please indicate the address and keyvalue (in hexidecimal) of all the tree nodes and the pointers from parent nodes to child nodes. The declarationof the tree node structure is as follows.struct tree_node {int key;struct tree_node * left;struct tree_Node * right;};/* address of the root node */tree_node * root;Key: 45Addr: 0x8049a4cAddr: 0x8049a6cKey: 10Addr: 0x8049a34Key: 70Example binary treeMemory image:<address> <value>0x80495f8: 0x0000000c0x80495fc: 0x000000000x8049600: 0x000000000x8049604: 0x0000001f0x8049608: 0x080495f80x804960c: 0x080496100x8049610: 0x000000220x8049614: 0x000000000x8049618: 0x000000000x804961c: 0x000000370x8049620: 0x080496040x8049624: 0x080496280x8049628: 0x0000003c0x804962c: 0x000000000x8049630: 0x080496340x8049634: 0x0000004e0x8049638: 0x000000000x804963c: 0x00000000...Page 6 of 22Part II The following function traverses the binary tree to locate the node with a given key value.1: struct tree_node * search(struct tree_node * node,2: int value)3: {4: if (node->key == value)5: return node;6: else if (node->key > value) {7: if (node->left == NULL)8: return NULL;9: else return search(node->left, value);10: }11: else {12: if (node->right == NULL)13: return NULL;14: else return search(node->right, value);15: }16: }Suppose we call search(root, 0x4e). Fill in the blanks the value of these memory location so thatit shows the stack when the execution is at line 5. (More space than needed is provided. ) You can assumethat the stack stores only arguments, return address, and the ebp register value. The value of ebp is0xbffff880 when the program calls the function. Write ”rtnaddr” for return addresses.Address Value0xbffff800 0x4e0xbffff7fc 0x804961c0xbffff7f8 rtn addr0xbffff7f40xbffff7f00xbffff7ec0xbffff7e80xbffff7e40xbffff7e00xbffff7dc0xbffff7d80xbffff7d40xbffff7d00xbffff7cc0xbffff7c80xbffff7c4Page 7 of 22Problem 4. (8 points):In this problem, you will compare the performance of direct mapped and-way associative caches for theinitialization of 2-dimensional array of data structures. Both caches have a size of bytes. The directmapped cache has -byte lines while the-way associative cache has-byte lines.You are given the following definitionstypedef struct{float* position;float velocity[3];float forces[3];particle_t *adjacent;} particle_t;particle_t cloth[32][32];register int i, j, k;Also assume thatsizeof(* float) and sizeof(* particle_t) = 4sizeof(float) = 4surface begins at
View Full Document
Unlocking...