深入理解计算机系统第二版习题答案.pdf

深入理解计算机系统第二版 习题答案Computer Systems:A Programmers PerspectiveInstructors Solution Manual1Randal E.BryantDavid R.OHallaronDecember 4,20031Copyright c?2003,R.E.Bryant,D.R.OHallaron.All rights reserved.Chapter 1Solutions to Homework ProblemsThe text uses two different kinds of exercises:Practice Problems.These are problems that are incorporated directly into the text,with explanatorysolutions at the end of each chapter.Our intention is that students will work on these problems as theyread the book.Each one highlights some particular concept.Homework Problems.These are found at the end of each chapter.They vary in complexity fromsimple drills to multi-week labs and are designed for instructors to give as assignments or to use asrecitation examples.This document gives the solutions to the homework problems.1.1Chapter 1:A Tour of Computer Systems1.2Chapter 2:Representing and Manipulating InformationProblem 2.40 Solution:This exercise should be a straightforward variation on the existing code.code/data/show-ans.c1void show_short(short int x)23show_bytes(byte_pointer)&x,sizeof(short int);456void show_long(long int x)78show_bytes(byte_pointer)&x,sizeof(long);912CHAPTER 1.SOLUTIONS TO HOMEWORK PROBLEMS1011void show_double(double x)1213show_bytes(byte_pointer)&x,sizeof(double);14code/data/show-ans.cProblem 2.41 Solution:There are many ways to solve this problem.The basic idea is to create some multibyte datum with differentvalues for the most and least-significant bytes.We then read byte 0 and determine which byte it is.In the following solution is to create an int with value 1.We then access its first byte and convert it to anint.This byte will equal 0 on a big-endian machine and 1 on a little-endian machine.code/data/show-ans.c1int is_little_endian(void)23/*MSB=0,LSB=1*/4int x=1;56/*Return MSB when big-endian,LSB when little-endian*/7return(int)(*(char*)&x);8code/data/show-ans.cProblem 2.42 Solution:This is a simple exercise in masking and bit manipulation.It is important to mention that 0 xFF is a wayto generate a mask that selects all but the least significant byte that works for any word size.(x&0 xFF)|(y&0 xFF)Problem 2.43 Solution:These exercises require thinking about the logical operation!in a nontraditional way.Normally we thinkof it as logical negation.More generally,it detects whether there is any nonzero bit in a word.A.!xB.!xC.!(x&0 xFF)D.!(x&0 xFF)Problem 2.44 Solution:1.2.CHAPTER 2:REPRESENTING AND MANIPULATING INFORMATION3There are many solutions to this problem,but it is a little bit tricky to write one that works for any wordsize.Here is our solution:code/data/shift-ans.c1int int_shifts_are_arithmetic()23int x=0;/*All 1s*/45return(x 1)=x;6code/data/shift-ans.cThe above code peforms a right shift of a word in which all bits are set to 1.If the shift is arithmetic,theresulting word will still have all bits set to 1.Problem 2.45 Solution:This problem illustrates some of the challenges of writing portable code.The fact that 132 yields 0 onsome 32-bit machines and 1 on others is common source of bugs.A.The C standard does not define the effect of a shift by 32 of a 32-bit datum.On the SPARC(andmany other machines),the expression x k shifts by?,i.e.,it ignores all but the leastsignificant 5 bits of the shift amount.Thus,the expression 1 32 yields 1.B.Compute beyond_msb as 2 31.C.We cannot shift by more than 15 bits at a time,but we can compose multiple shifts to get thedesired effect.Thus,we can compute set_msb as 2 15 15,and beyond_msb asset_msb 1.Problem 2.46 Solution:This problem highlights the difference between zero extension and sign extension.It also provides an excuseto show an interesting trick that compilers often use to use shifting to perform masking and sign extension.A.The function does not perform any sign extension.For example,if we attempt to extract byte 0 fromword 0 xFF,we will get 255,rather than.B.The following code uses a well-known trick for using shifts to isolate a particular range of bits and toperform sign extension at the same time.First,we perform a left shift so that the most significant bitof the desired byte is at bit position 31.Then we right shift by 24,moving the byte into the properposition and peforming sign extension at the same time.code/data/xbyte.c1int xbyte(packed_t word,int bytenum)24CHAPTER 1.SOLUTIONS TO HOMEWORK PROBLEMS3int left=word (3-bytenum)24;5code/data/xbyte.cProblem 2.47 Solution:?Problem 2.48 Solution:This problem lets students rework the proof that complement plus increment performs negation.We make use of the property that twos complement addition is associative,commutative,and has additiveinverses.Using C notation,if we define y to be x-1,then we have y+1 equal to-y,and hence y equals-y+1.Substituting gives the expression-(x-1)+1,which equals-x.Problem 2.49 Solution:This problem requires a fairly deep understanding of twos complement arithmetic.Some machines onlyprovide one form ofmultiplication,and hence the trick shown in thecode here isactually required to performthat actual form.As seen in Equation 2.16 we have?!?$#!?&%(*)+,#-%.*)+?%#-?&%(*)/%.*)?10%.The final termhas no effect on the?32-bit representation of?3,but the middle term represents a correction factor thatmust be added to the high order2bits.This is implemented as follows:code/data/uhp-ans.c1unsigned unsigned_high_prod(unsigned x,unsigned y)23unsigned p=(unsigned)signed_high_prod(int)x,(int)y);45if(int)x 0)/*x_w-1=1*/6p+=y;7if(int)y 0)/*y_w-1=1*/8p+=x;9return p;10code/data/uhp-ans.cProblem 2.50 Solution:Patterns of the kind shown here frequently appear in compiled code.1.2.CHAPTER 2:REPRESENTING AND MANIPULATING INFORMATION5A.?:x+(x 2)B.?:x+(x 3)C.?:(x 4)-(x1)D.?:(x 3)-(x 6)Problem 2.51 Solution:Bit patterns similar to these arise in many applications.Many programmers provide them directly in hex-adecimal,but it would be better if they could express them in more abstract ways.A.%(?.(1 k)-1)B.%(?.(1 k)-1)jProblem 2.52 Solution:Byte extraction and insertion code is useful in many contexts.Being able to write this sort of code is animportant skill to foster.code/data/rbyte-ans.c1unsigned replace_byte(unsigned x,int i,unsigned char b)23int itimes8=i 3;4unsigned mask=0 xFF itimes8;56return(x&mask)|(b k;5/*Make mask of low order 32-k bits*/6unsigned mask=k?(1 k;5/*Make mask of high order k bits*/6unsigned mask=k?(1 (32-k)-1):0;78return(x 0)?mask|xsrl:xsrl;9code/data/rshift-ans.cProblem 2.54 Solution:These“C puzzle”problems are a great way to motivate students to think about the properties of computerarithmetic from a programmers perspective.Our standard lecture on computer arithmetic starts by showinga set of C puzzles.We then go over the answers at the end.A.(x-y).No,Let x=?0?.B.(x+y)1)1)31;6unsigned sy=uy 31;78return9(ux1=0&uy=0,y=uy)|/*x=0,y=0*/12(sx&sy&ux=uy);/*x 0,y 0*/13code/data/floatge-ans.cProblem 2.57 Solution:Exercises such as this help students understand floating point representations,their precision,and theirranges.A.The numberwill have?,?0?,0)?,and.The exponent bitswill be?and the fraction bits will be?.B.The largest odd integer that can be represented exactly will have a binary representation consistingof#1s.It will have?,?0?,?0?,anda value?().The bit representation of the exponent will be the binary representation of#?*).The bit representation of the fraction will be?.C.The reciprocal of the smallest positive normalized value will have value?00.It will have?*)?,?,and.The bit representation of the exponent will be?.The bitrepresentation of the fraction will be?.Problem 2.58 Solution:8CHAPTER 1.SOLUTIONS TO HOMEWORK PROBLEMSThis exercise is of practical value,since Intel-compatible processors perform all of their arithmetic in ex-tended precision.It is interesting to see how adding a few more bits to the exponent greatly increases therange of values that can be represented.DescriptionExtended precisionValueDecimalSmallest denorm.?*)?0?3?)Smallest norm.?*)?0?0Largest norm.?)?0Problem 2.59 Solution:We have found that working through floating point representations for small word sizes is very instructive.Problems such as this one help make the description of IEEE floating point more concrete.DescriptionHex?8000?Smallest value?3F010?0?0?0?2564700?Largest denormalized00FF0?0?FF00Number with hex representation 3AA0)?)?0?Problem 2.60 Solution:This problem requires students to think of the relationship between int,float,and double.A.(double)(float)x=dx.No.Try x=?0.Note that it is true with Linux/GCC,sinceit uses a extended precision representation for both double and float.B.dx+dy=(double)(y+x).No.Let x=y=?0.C.dx+dy+dz=dz+dy+dx.Yes.Sinceeach value ranges between?0and?0,their sum can be represented exactly.D.dx*dy*dz=dz*dy*dx.No.Letdx=?0,dy=?0,dz=?0?.(Not detected with Linux/gcc)E.dx/dx=dy/dy.No.Let x=0,y=1.Problem 2.61 Solution:This problem helps students understand the relation between the different categories of numbers.Gettingall of the cutoff thresholds correct is fairly tricky.Our solution file contains testing code.code/data/fpwr2-ans.c1.3.CHAPTER 3:MACHINE LEVEL REPRESENTATIONOF C PROGRAMS91/*Compute 2*x*/2float fpwr2(int x)34unsigned exp,sig;5unsigned u;67if(x -149)8/*Too small.Return 0.0*/9exp=0;10sig=0;11 else if(x -126)12/*Denormalized result*/13exp=0;14sig=1 (x+149);15 else if(x 128)16/*Normalized result.*/17exp=x+127;18sig=0;19 else 20/*Too big.Return+oo*/21exp=255;22sig=0;2324u=exp 23|sig;25return u2f(u);26code/data/fpwr2-ans.cProblem 2.62 Solution:This problem requires students to work from a bit representation of a floating point number to its fractionalbinary representation.A.?0.B.?0.C.They diverge in the ninth bit to the right of the binary point.1.3Chapter 3:Machine Level Representation of C ProgramsProblem 3.31 Solution:This is an example of a problem that requires students to reverse engineer actions of the Ccompiler.Wehavefound that reverse engineering is a good way to learn about both compilers and machine-level programs.10CHAPTER 1.SOLUTIONS TO HOMEWORK PROBLEMSint decode2(int x,int y,int z)int t1=y-z;int t2=x*t1;int t3=(t1 31;int t4=t3 t2;return t4;Problem 3.32 Solution:This code example demonstrates one of the pedagogical challenges of using a compiler to generate assemblycode examples.Seemingly insignificant changes in the C code can yield very different results.Of course,students will have to contend with this property as work with machine-generated assembly code anyhow.They will need to be able to decipher many different code patterns.This problem encourages them to thinkin abstract terms about one such pattern.The following is an annotated version of the assembly code:1movl 8(%ebp),%edxx2movl 12(%ebp),%ecxy3movl%edx,%eax4subl%ecx,%eaxresult=x-y5cmpl%ecx,%edxCompare x:y6jge.L3if=goto done:7movl%ecx,%eax8subl%edx,%eaxresult=y-x9.L3:done:A.When?,it will compute first?and then?.When?it just computes?.B.The code for then-statement gets executed unconditionally.It then jumps over the code for else-statement if the test is false.C.then-statementt=test-expr;if(t)goto done;else-statementdone:D.The code in then-statement must not have any side effects,other than to set variables that are also setin else-statement.1.3.CHAPTER 3:MACHINE LEVEL REPRESENTATIONOF C PROGRAMS11Problem 3.33 Solution:This problem requires students to reason about the code fragments that implement the different branches ofa switch statement.For this code,it also requires understanding different forms of pointer dereferencing.A.In line 29,register%edx is copied to register%eax as the return value.From this,we can infer that%edx holds result.B.The original C code for the function is as follows:1/*Enumerated type creates set of constants numbered 0 and upward*/2typedef enum MODE_A,MODE_B,MODE_C,MODE_D,MODE_E mode_t;34int switch3(int*p1,int*p2,mode_t action)56int result=0;7switch(action)8case MODE_A:9result=*p1;10*p1=*p2;11break;12case MODE_B:13*p2+=*p1;14result=*p2;15break;16case MODE_C:17*p2=15;18result=*p1;19break;20case MODE_D:21*p2=*p1;22/*Fall Through*/23case MODE_E:24result=17;25break;26default:27result=-1;2829return result;30Problem 3.34 Solution:This problem gives students practice analyzing disassembled code.The switch statement contains all thefeatures one can imaginecases with multiple labels,holes in the range of possible case values,and casesthat fall through.code/asm/switchbody-ans.c12CHAPTER 1.SOLUTIONS TO HOMEWORK PROBLEMS1int switch_prob(int x)23int result=x;45switch(x)6case 50:7case 52:8result=2;12break;13case 54:14result*=3;15/*Fall through*/16case 55:17result*=result;18/*Fall through*/19default:20result+=10;212223return result;24code/asm/switchbody-ans.cProblem 3.35 Solution:This example illustrates a case where the compiler was clever,but humans can be more clever.Such cases are notunusual,and it is important for students to realize that compilers do not always generate optimal code.In the following,we have merged variables B and nTjPk into a single pointer Bptr.This pointer gets incrementedby n(which the compiler scales by 4)on every iteration.code/asm/varprod-ans.c1int var_prod_ele_opt(var_matrix A,var_matrix B,int i,int k,int n)23int*Aptr=&Ai*n;4int*Bptr=&Bk;5int result=0;6int cnt=n;78if(n right using a displacement of 184(0 xb8).That meansarray a spans from bytes 4 to 184 of b_struct,implying that CNT is?3?.3.Line 9 appears to dereference ap.Actually,it is computing ap-idx,since field idx is at thebeginning of structure a_struct.4.Line 10 scales ap-idx by 4,and line 13 stores n at an address computed by adding this scaledvalue,ap,and 4.From this we conclude that field x denotes an array of integers that follow rightafter field idx.This analysis leads us to the following answers:A.CNT is 9.B.code/asm/structprob-ans.c1typedef struct 2int idx;3int x4;4 a_struct;code/asm/structprob-ans.cProblem 3.37 Solution:This problem gets students in the habit of writing reliable code.As a general principle,code should not bevulnerable to conditions over which it has no control,such as the length of an input line.The followingimplementation uses the library function fgets to read up to BUFSIZE characters at a time.14CHAPTER 1.SOLUTIONS TO HOMEWORK PROBLEMS1/*Read input line and write it back*/2/*Code will work for any buffer size.Bigger is more time-efficient*/3#define BUFSIZE 644void good_echo()56char bufBUFSIZE;7int i;8while(1)9if(!fgets(buf,BUFSIZE,stdin)10return;/*End of file or error*/11/*Print characters in buffer*/12for(i=0;bufi&bufi!=n;i+)13if(putchar(bufi)=EOF)14return;/*Error*/15if(bufi=n)16/*Reached terminating newline*/17putchar(n);18return;192021An alternative implementation is to use getchar to read the characters one at a time.Problem 3.38 Solution:Successfully mounting a buffer overflow attack requires understanding many aspects of machine-level pro-grams.It is quite intriguing that by supplying a string to one function,we can alter the behavior of anotherfunction that should always return a fixed value.In assigning this problem,you should also give students astern lecture abo