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