Introduction to Computer systems Exam l Apr.,2006 Time allowed: 2 hours Instructions 1. This paper contains EIGHT (8)questions and comprises SEVEN(7) pages 2. The total pts on the paper is 100 Chinese Student1 N S 姓名学号 Problem 1: (0. 14=7pts) Assume we are running code on a 6-bit machine using twos complement arithmetic for signed integers. A"short integer is encoded using 3 bits. Fill in the empty boxes in the table below. The following definitions are used in the table int unsigned ux =x Note You need not fill in entries marked with" Expression Decimal Representation Binary Representation -14 UX TM . TMin TMin+TMin Problem 2:(1*17=17pts) Consider the following 8-bit floating point representation based on the IEEE floating point format There is a sign bit in the most significant bit The next 3 bits are the exponent The exponent bias is 23-1-1=3 Page 1 of 7
-Page 1 of 7 Introduction to Computer Systems Exam 1 Apr., 2006 Time Allowed: 2 hours Instructions 1. This paper contains EIGHT (8) questions and comprises SEVEN (7) pages. 2. The total pts on the paper is 100. Chinese Name 姓名 Student No. 学号 1 2 3 4 5 6 7 8 Total Score Problem 1: (0.5*14 = 7pts) Assume we are running code on a 6-bit machine using two’s complement arithmetic for signed integers. A “short” integer is encoded using 3 bits. Fill in the empty boxes in the table below. The following definitions are used in the table: short sy = -3; int y = sy; int x = -29; unsigned ux = x; Note: You need not fill in entries marked with “–”. Expression Decimal Representation Binary Representation _ -14 _ 011110 ux y x>>2 TMax -TMin TMin+TMin Problem 2:（1*17=17pts） Consider the following 8-bit floating point representation based on the IEEE floating point format: ⚫ There is a sign bit in the most significant bit. ⚫ The next 3 bits are the exponent. The exponent bias is 2 3-1 -1 = 3
The last 4 bits are the fraction The representation encodes numbers of the form: V=(-1)s XMX2E, where M is the significand and E is the biased exponent The rules are like those in the IEEE standard(normalized, denormalized, representation of 0, infinity and NAN). FILL in the table below. Here are the instructions for each field Binary: The 8 bit binary representation M: The value of the significand. E: The integer value of the exponer Value: The numeric value represented Note: you need not fill in entries marked with Description Minus zero 0.0 01101101 Smallest denormalized(negative) Largest normalized(positive) 8.5 Problem 3:(0.5*24=12pts) Consider the following program struct s i double d float fi short union u t unsigned char buf [24]i struct s ai int 1 }u1 int main o int 1,] memset(&ul.a, 0, sizeof(struct s))i ul.as=0xbcde 0x12345678; / print out the bytes of ul buf as 2 digit hexidecimal numbers with a line break after every 8 bytes * for(i=0;i<3;i++) printf("0x\8. 2x ",ul buf [i*8+3]) Page 2 of 7
-Page 2 of 7 ⚫ The last 4 bits are the fraction. ⚫ The representation encodes numbers of the form:V = (-1) s ×M×2 E , where M _ is the significand and E is the biased exponent. The rules are like those in the IEEE standard(normalized, denormalized, representation of 0, infinity, and NAN). FILL in the table below. Here are the instructions for each field: Binary: The 8 bit binary representation. M: The value of the significand. E: The integer value of the exponent. Value:The numeric value represented. Note: you need not fill in entries marked with ”—”. Description Binary M E V Minus zero -0.0 — 0 110 1101 Smallest denormalized (negative) Largest normalized (positive) — 8.5 Problem 3: (0.5*24=12pts) Consider the following program: struct s { char c; double d; float f; short s; }; union u { unsigned char buf[24]; struct s a; int i; } u1; int main() { int i,j; memset(&u1.a, 0, sizeof(struct s)); u1.a.c = 0xac; u1.a.d = -3.3; u1.a.f = 0x1; u1.a.s = 0xbcde; u1.i = 0x12345678; /* print out the bytes of u1.buf as 2 digit hexidecimal numbers with a line break after every 8 bytes */ for(i = 0; i < 3; i++) { for(j = 0; j < 8; j++) printf("0x\%.2x ",u1.buf[i*8+j]); printf("\n"); } }
This program is compiled and run on a linux/x86 machine. Fill in the output below. Write"??"if the value cannot be determined from the information provided 0 0 0 0x 0 0x 0x 0x Ox Problem 4:(2*7= 14pts) This problem tests your understanding of labl Fill the following function as you do in Labl ∥ //Determines whether argument y can be added to argument x without overflow ops ∥ Max ops:20 ∥ int addo(int x, int y) Ints=x+y; int over=((Sx) (s^y))>>31 return //Adds two values and if the result(x+y) has a positive overflow it returns l the greatest possible positive value(instead of getting a negative result l If the result has a negative overflow, then it should retum the least Examples: sat Add(0x40000000, 0x40000000)=0x7fffffff satAdd(Ox8000000t=0x8000000 ∥ Legal ops:!~&^|+≤ ∥ Max ops:30 int satAdd(int x, int y) int over=((xs)(ys))>>31 int differ3=s(over 31) return differ3(over <<31); Problem 5:2*5=10pts) the s problem tests your understanding of how for loops in C relate to IA32 machine code. Consider ne following IA32 assembly code for a procedure dog () Page 3 of 7
-Page 3 of 7 This program is compiled and run on a Linux/x86 machine. Fill in the output below. Write “??” if the value cannot be determined from the information provided. 0x____ 0x____ 0x____ 0x____ 0x____ 0x____ 0x____ 0x____ 0x____ 0x____ 0x____ 0x____ 0x____ 0x____ 0x____ 0x____ 0x____ 0x____ 0x____ 0x____ 0x____ 0x____ 0x____ 0x____ Problem 4: (2*7 = 14pts) This problem tests your understanding of Lab1. Fill the following function as you do in Lab1. // // Determines whether argument y can be added to argument x without overflow. // Legal ops: ! ~ & ^ | + > // Max ops: 20 // int addOK(int x, int y) { int s = x + y; int over = ( ( s ^ x ) ( s ^ y ) ) >> 31; return ; } // Adds two values and if the result (x+y) has a positive overflow it returns // the greatest possible positive value (instead of getting a negative result). // If the result has a negative overflow, then it should return the least // possible negative value. // Examples: satAdd(0x40000000,0x40000000) = 0x7fffffff // satAdd(0x80000000,0xffffffff) = 0x80000000 // Legal ops: ! ~ & ^ | + > // Max ops: 30 int satAdd(int x, int y) { int s = x ____ y; int over = ( ( x ^ s ) ____ ( y ^ s ) ) >> 31; int differ3 = s ____ ( over ____ 31 ); return differ3 ____ ( over << 31 ); } Problem 5: (2*5 = 10pts) This problem tests your understanding of how for loops in C relate to IA32 machine code. Consider the following IA32 assembly code for a procedure dog():
pushl ebp mov112(8ebp),暑ecx movl $l, movl 8(gebp), edx cmpl ecx, edx imu11edx,暑eax addl $2, edx cmpl &ecx, edx popl ebp Based on the assembly code, fill in the blanks below in its corresponding C source code. (Note: you may only use symbolic variablesx, y, i, and result, from the source code in your expre ssions belo -do not use register names.) int dog(int x, int y) int i, result esu⊥t= for (i result return resulti Problem 6:(2*4=8pts) This problem tests your understanding of how while loops in C relate to IA32 machine code Consider the following IA32 assembly code for a procedure cat( pushl ebp ovl esp, ebp ovl 8(sebp), ecx pushl ebx xorl ebx, ebx movl 12(ebp), eax decl secx cmp1-1,暑ecx je. L6 mov1暑ecx,8edx imu11eax,各ed 1 p2align 4,, 15 decl secx ddl sedx, sex add18eax,暑edx Page 4 of 7
-Page 4 of 7 dog: pushl %ebp movl %esp, %ebp movl 12(%ebp), %ecx movl $1, %eax movl 8(%ebp), %edx cmpl %ecx, %edx jge .L7 .L5: imull %edx, %eax addl $2, %edx cmpl %ecx, %edx jl .L5 .L7: popl %ebp ret Based on the assembly code, fill in the blanks below in its corresponding C source code. (Note: you may only use symbolic variables x, y, i, and result, from the source code in your expressions below — do not use register names.) int dog(int x, int y) { int i, result; result = ________; for (i = ________; _____________; ________) result = _________________; return result; } Problem 6: (2*4 = 8pts) This problem tests your understanding of how while loops in C relate to IA32 machine code. Consider the following IA32 assembly code for a procedure cat(): cat: pushl %ebp movl %esp, %ebp movl 8(%ebp), %ecx pushl %ebx xorl %ebx, %ebx movl 12(%ebp), %eax decl %ecx cmpl $-1, %ecx je .L6 movl %ecx, %edx imull %eax, %edx negl %eax .p2align 4,,15 .L4: decl %ecx addl %edx, %ebx addl %eax, %edx cmpl $-1, %ecx
Jne L4 movl geba, eax popl ebx popl ebp may only use symbolic variablesx, y, i, and ret, from the source code in your expressions belor ou Based on the assembly code, fill in the blanks below in its corresponding C source code. ( Note do not use register names. int cat (int x, int y) int i, reti while( ret= return reti Problem7:(1*2+8*1.5=14pts) This problem tests your understanding of both control flow and multidimensional array layout Consider the following assembly code for a procedure moo () moo pushl ebp movl esp, ebp push1旨e pushl esi pushl geba movl $0, ecx novI Sarl, edi ov1sarr2+8,旨 mov18(sebp),岩eax 1ea10(,号eax,4),ebx 1ea1(岩ecx,ecx,2),岩eax mov1ebx,岩edx dd1(eax,号esi),暑edx mov1岩edx,(号eax,器edi) cmp1$10,号ecx movl ecx, beax pop1号ebx popl esi pop1岩edi popl ebp Page 5 of 7
-Page 5 of 7 jne .L4 .L6: movl %ebx, %eax popl %ebx popl %ebp ret Based on the assembly code, fill in the blanks below in its corresponding C source code. (Note: you may only use symbolic variables x, y, i, and ret, from the source code in your expressions below — do not use register names.) int cat(int x, int y) { int i, ret; ret = ________; i = ________; while(_____________) { ret = _______________________; } return ret; } Problem 7: (1*2 + 8*1.5 = 14pts) This problem tests your understanding of both control flow and multidimensional array layout. Consider the following assembly code for a procedure moo(): moo: pushl %ebp movl %esp, %ebp pushl %edi pushl %esi pushl %ebx movl $0, %ecx movl $arr1, %edi movl $arr2+8, %esi movl 8(%ebp), %eax leal 0(,%eax,4), %ebx .L5: leal (%ecx,%ecx,2), %eax sall $2, %eax movl %ebx, %edx addl (%eax,%esi), %edx movl %edx, (%eax,%edi) incl %ecx cmpl $10, %ecx jle .L5 movl %ecx, %eax popl %ebx popl %esi popl %edi popl %ebp ret
Based on the assembly code, fill in the blanks below in moo' s C source code. ( Note: you may only use symbolic variables from the source code in your expressions below-do not use register names. Hint: First figure out what the loop variable(i) is in the assembly and what the value of M ine M (lpts) (lpts) int arrl[M] IN int arr2[M]IN]i nt moo (int x) ) return Problem 8: (18pts) Consider the following C program main([ swap(&a, &b) oid swap (int *a, int *b)t int te temp =*a emp printf("号d,号d\n",*a,+); gcc generate the following assembly code for function swap swap 1 push gebp 号esp,号 3 su 0x8(ebp),号eax (eax),号eax 6mov号eax,0 xfffffffc(号ebp) 0x8(ebp),号edx 8 mov C(ebp),号eax (eax),号eax 10mov号eax,(号edx) 11mov0xC(岩ebp),暑edx Oxfffffffc(sebp),seax Page 6 of 7
-Page 6 of 7 Based on the assembly code, fill in the blanks below in moo’s C source code. (Note: you may only use symbolic variables from the source code in your expressions below-do not use register names.) Hint: First figure out what the loop variable (i) is in the assembly and what the value of M is. #define M _____ (1pts) #define N _____ (1pts) int arr1[M][N]; int arr2[M][N]; int moo(int x) { int i; for(__________; i < M; ________ ){ arr1[_____][_____] = arr2[_____][_____]+______________; } return _______; } Problem 8: (18pts) Consider the following C program: main() { int a = 0, b = 1; swap(&a, &b); } void swap(int *a, int *b) { int temp ; temp = *a ; *a = * b ; *b = temp ; printf("%d, %d\n", *a, *b); } gcc generate the following assembly code for function swap: swap: 1 push %ebp 2 mov %esp,%ebp 3 sub $0x8,%esp 4 mov 0x8(%ebp),%eax 5 mov (%eax),%eax 6 mov %eax,0xfffffffc(%ebp) 7 mov 0x8(%ebp),%edx 8 mov 0xc(%ebp),%eax 9 mov (%eax),%eax 10 mov %eax,(%edx) 11 mov 0xc(%ebp),%edx 12 mov 0xfffffffc(%ebp),%eax 13 mov %eax,(%edx)
14subs0x4,岩esp 15mov0xc(号ebp),号eax 16push1(岩eax) 17 mov 0x8(号ebp),号eax 18push1(暑eax) 19 push $0x80484d8 180482f0 21addS0x10,告esp gebp, esp 23 pop 号eb 24 ret Assume that procedure swap starts executing whith the following register values Register value %oebp Oxbffff628 Oxbffff60c Questions (1) What value does %ebp get set to on line2.(I pts) (2) At what address are the local variable"temp"stored, and where are parameters and the return address placed for function swap. (4 pts) (3) Explain caller saved registers and callee registers together with this segment of code. (4 pts) (4) Draw a diagram of the stack frame for function"swap"right after the 20th instruction call 80482f0" Include as much information as you can about the addresses and the contents of the stack frame elements. (8 pt (5) Indicate the regions of the stack frame that are not used by swap. (1 pts) 7 of 7
-Page 7 of 7 14 sub $0x4,%esp 15 mov 0xc(%ebp),%eax 16 pushl (%eax) 17 mov 0x8(%ebp),%eax 18 pushl (%eax) 19 push $0x80484d8 20 call 80482f0 21 add $0x10,%esp 22 mov %ebp,%esp 23 pop %ebp 24 ret Assume that procedure swap starts executing whith the following register values: Register Value %ebp 0xbffff628 %esp 0xbffff60c Questions: （1） What value does %ebp get set to on line2. (1 pts) （2） At what address are the local variable “temp” stored, and where are parameters and the return address placed for function swap. (4 pts) （3） Explain caller saved registers and callee registers together with this segment of code. (4 pts) （4） Draw a diagram of the stack frame for function “swap” right after the 20th instruction ”call 80482f0 ”. Include as much information as you can about the addresses and the contents of the stack frame elements. (8 pts) （5） Indicate the regions of the stack frame that are not used by swap. (1 pts)