Machine-Level Programming II: Control Flow Jan 29, 2004Condition CodesSetting Condition Codes (cont.)Slide 4Reading Condition CodesReading Condition Codes (Cont.)JumpingConditional Branch ExampleConditional Branch Example (Cont.)“Do-While” Loop Example“Do-While” Loop CompilationGeneral “Do-While” Translation“While” Loop Example #1Actual “While” Loop TranslationGeneral “While” Translation“For” Loop Exampleipwr ComputationSlide 18“For” “While”“For” Loop CompilationSwitch StatementsJump Table StructureSwitch Statement ExampleAssembly Setup ExplanationJump TableSwitch Statement CompletionObject CodeObject Code (cont.)Extracting Jump Table from BinaryDisassembled TargetsMatching Disassembled TargetsSparse Switch ExampleSparse Switch CodeSparse Switch Code StructureSummarizingMachine-Level Programming II:Control FlowJan 29, 2004TopicsCondition CodesSettingTestingControl FlowIf-then-elseVarieties of LoopsSwitch Statementsclass06.ppt15-213“The course that gives CMU its Zip!”– 2 –15-213, S’04Condition CodesSingle Bit RegistersCF Carry Flag SF Sign FlagZF Zero Flag OF Overflow FlagImplicitly Set By Arithmetic Operationsaddl Src,DestC analog: t = a + bCF set if carry out from most significant bitUsed to detect unsigned overflowZF set if t == 0SF set if t < 0OF set if two’s complement overflow(a>0 && b>0 && t<0) || (a<0 && b<0 && t>=0)Not Set by leal instruction– 3 –15-213, S’04Setting Condition Codes (cont.)Explicit Setting by Compare Instructioncmpl Src2,Src1 cmpl b,a like computing a-b without setting destinationCF set if carry out from most significant bitUsed for unsigned comparisonsZF set if a == bSF set if (a-b) < 0OF set if two’s complement overflow(a>0 && b<0 && (a-b)<0) || (a<0 && b>0 && (a-b)>0)– 4 –15-213, S’04Setting Condition Codes (cont.)Explicit Setting by Test instructiontestl Src2,Src1Sets condition codes based on value of Src1 & Src2Useful to have one of the operands be a mask testl b,a like computing a&b without setting destination ZF set when a&b == 0SF set when a&b < 0– 5 –15-213, S’04Reading Condition CodesSetX Condition Descriptionsete ZFEqual / Zerosetne ~ZFNot Equal / Not Zerosets SFNegativesetns ~SFNonnegativesetg ~(SF^OF)&~ZFGreater (Signed)setge ~(SF^OF)Greater or Equal (Signed)setl (SF^OF)Less (Signed)setle (SF^OF)|ZFLess or Equal (Signed)seta ~CF&~ZFAbove (unsigned)setb CFBelow (unsigned)SetX InstructionsSet single byte based on combinations of condition codes– 6 –15-213, S’04Reading Condition Codes (Cont.)SetX InstructionsSet single byte based on combinations of condition codesOne of 8 addressable byte registersEmbedded within first 4 integer registersDoes not alter remaining 3 bytesTypically use movzbl to finish job%eax%edx%ecx%ebx%esi%edi%esp%ebp%al%ah%dl%dh%cl%ch%bl%bhint gt (int x, int y){ return x > y;}movl 12(%ebp),%eax # eax = ycmpl %eax,8(%ebp) # Compare x : ysetg %al # al = x > ymovzbl %al,%eax # Zero rest of %eaxNote inverted ordering!Body– 7 –15-213, S’04JumpingjX Condition Descriptionjmp 1Unconditionalje ZFEqual / Zerojne ~ZFNot Equal / Not Zerojs SFNegativejns ~SFNonnegativejg ~(SF^OF)&~ZFGreater (Signed)jge ~(SF^OF)Greater or Equal (Signed)jl (SF^OF)Less (Signed)jle (SF^OF)|ZFLess or Equal (Signed)ja ~CF&~ZFAbove (unsigned)jb CFBelow (unsigned)jX InstructionsJump to different part of code depending on condition codes– 8 –15-213, S’04Conditional Branch Exampleint max(int x, int y){ if (x > y) return x; else return y;}_max:pushl %ebpmovl %esp,%ebpmovl 8(%ebp),%edxmovl 12(%ebp),%eaxcmpl %eax,%edxjle L9movl %edx,%eaxL9:movl %ebp,%esppopl %ebpretBodySetUpFinish– 9 –15-213, S’04Conditional Branch Example (Cont.)movl 8(%ebp),%edx # edx = xmovl 12(%ebp),%eax # eax = ycmpl %eax,%edx # x : yjle L9 # if x <= y goto donemovl %edx,%eax # eax = xL9: # done:int goto_max(int x, int y){ int rval = y; int ok = (x <= y); if (ok)goto done; rval = x;done: return rval;}Skipped when x yC allows “goto” as means of transferring controlCloser to machine-level programming styleGenerally considered bad coding style– 10 –15-213, S’04C Codeint fact_do(int x){ int result = 1; do { result *= x; x = x-1; } while (x > 1); return result;}Goto Versionint fact_goto(int x){ int result = 1;loop: result *= x; x = x-1; if (x > 1) goto loop; return result;}“Do-While” Loop ExampleUse backward branch to continue loopingOnly take branch when “while” condition holds– 11 –15-213, S’04Goto Versionintfact_goto(int x){ int result = 1;loop: result *= x; x = x-1; if (x > 1) goto loop; return result;}“Do-While” Loop CompilationRegisters%edx x%eax result_fact_goto:pushl %ebp # Setupmovl %esp,%ebp # Setupmovl $1,%eax # eax = 1movl 8(%ebp),%edx # edx = xL11:imull %edx,%eax # result *= xdecl %edx # x--cmpl $1,%edx # Compare x : 1jg L11 # if > goto loopmovl %ebp,%esp # Finishpopl %ebp # Finishret # FinishAssembly– 12 –15-213, S’04C Codedo Body while (Test);Goto Versionloop: Body if (Test) goto loopGeneral “Do-While” TranslationBody can be any C statementTypically compound statement:Test is expression returning integer= 0 interpreted as false 0 interpreted as true{ Statement1; Statement2; … Statementn;}– 13 –15-213, S’04C Codeint fact_while(int x){ int result = 1; while (x > 1) { result *= x; x = x-1; }; return result;}First Goto Versionint fact_while_goto(int x){ int result = 1;loop: if (!(x > 1)) goto done; result *= x; x = x-1; goto loop;done: return result;}“While” Loop Example #1Is this code equivalent to the do-while version?Must jump out of loop if test fails– 14 –15-213, S’04C Codeint fact_while(int x){ int result = 1; while (x > 1) { result *= x; x = x-1; }; return result;}Second Goto Versionint fact_while_goto2(int x){ int result = 1; if (!(x > 1)) goto done; loop: result *= x; x = x-1; if (x > 1) goto loop;done: return result;}Actual “While” Loop TranslationUses same inner loop as do-while versionGuards loop entry with extra test– 15 –15-213, S’04C Codewhile (Test) BodyDo-While Version if (!Test) goto done; do Body while(Test);done:General “While” TranslationGoto Version if (!Test) goto done;loop: Body if (Test) goto loop;done:– 16 –15-213, S’04“For” Loop ExampleAlgorithmExploit
View Full Document