Machine-Level Programming IV:Control FlowTopicsTopics Control Flow For Loops Switch StatementsSystems I2“For” Loop ExampleAlgorithmAlgorithm Exploit property that p = p0 + 2p1 + 4p2 + … 2n–1pn–1 Gives: xp = z0 · z1 2 · (z2 2) 2 · … · (…((zn –12) 2 )…) 2zi = 1 when pi = 0zi = x when pi = 1 Complexity O(log p)/* Compute x raised to nonnegative power p */int ipwr_for(int x, unsigned p) {int result; for (result = 1; p != 0; p = p>>1) { if (p & 0x1) result *= x; x = x*x; } return result;}n–1 timesExample310= 32 * 38 = 32 * ((32) 2) 23ipwr Computation/* Compute x raised to nonnegative power p */int ipwr_for(int x, unsigned p) {int result; for (result = 1; p != 0; p = p>>1) { if (p & 0x1) result *= x; x = x*x; } return result;}result x p131019598129656115314414304672104“For” Loop Examplefor (Init; Test; Update ) Body int result; for (result = 1; p != 0; p = p>>1) { if (p & 0x1) result *= x; x = x*x; }General FormInitresult = 1Testp != 0Updatep = p >> 1Body { if (p & 0x1) result *= x; x = x*x; }5“For”→ “While”for (Init; Test; Update ) BodyInit;while (Test ) { Body Update ;}Goto Version Init; if (!Test) goto done;loop: Body Update ; if (Test) goto loop;done:While VersionFor VersionDo-While Version Init; if (!Test) goto done; do { Body Update ; } while (Test)done:6“For” Loop CompilationInitresult = 1Testp != 0Updatep = p >> 1Body { if (p & 0x1) result *= x; x = x*x; }Goto Version Init; if (!Test) goto done;loop: Body Update ; if (Test) goto loop;done: result = 1; if (p == 0) goto done;loop: if (p & 0x1) result *= x; x = x*x; p = p >> 1; if (p != 0) goto loop;done:7SwitchStatementsImplementation OptionsImplementation Options Series of conditionals Good if few cases Slow if many Jump Table Lookup branch target Avoids conditionals Possible when casesare small integerconstants GCC Picks one based oncase structure Bug in example code No default giventypedef enum {ADD, MULT, MINUS, DIV, MOD, BAD} op_type;char unparse_symbol(op_type op){ switch (op) { case ADD : return '+'; case MULT: return '*'; case MINUS: return '-'; case DIV: return '/'; case MOD: return '%'; case BAD: return '?'; }}8Jump Table StructureCode Block0Targ0:Code Block1Targ1:Code Block2Targ2:Code Blockn–1Targn-1:•••Targ0Targ1Targ2Targn-1•••jtab:target = JTab[op];goto *target;switch(op) { case val_0: Block 0 case val_1: Block 1 • • • case val_n-1: Block n–1}Switch FormApprox. TranslationJump TableJump Targets9Switch Statement ExampleBranching PossibilitiesBranching PossibilitiesSetup:unparse_symbol:pushl %ebp # Setupmovl %esp,%ebp # Setupmovl 8(%ebp),%eax # eax = opcmpl $5,%eax # Compare op : 5 ja .L49 # If > goto donejmp *.L57(,%eax,4) # goto Table[op]Enumerated ValuesADD 0MULT 1MINUS 2DIV 3MOD 4BAD 5typedef enum {ADD, MULT, MINUS, DIV, MOD, BAD} op_type;char unparse_symbol(op_type op){ switch (op) { • • • }}10Assembly Setup ExplanationSymbolic LabelsSymbolic Labels Labels of form .LXX translated into addresses by assemblerTable StructureTable Structure Each target requires 4 bytes Base address at .L57JumpingJumpingjmp .L49 Jump target is denoted by label .L49jmp *.L57(,%eax,4) Start of jump table denoted by label .L57 Register %eax holds op Must scale by factor of 4 to get offset into table Fetch target from effective Address .L57 + op*411Jump TableEnumerated ValuesADD 0MULT 1MINUS 2DIV 3MOD 4BAD 5.section .rodata .align 4.L57:.long .L51 #Op = 0.long .L52 #Op = 1.long .L53 #Op = 2.long .L54 #Op = 3.long .L55 #Op = 4.long .L56 #Op = 5Table Contents.L51:movl $43,%eax # ’+’jmp .L49.L52:movl $42,%eax # ’*’jmp .L49.L53:movl $45,%eax # ’-’jmp .L49.L54:movl $47,%eax # ’/’jmp .L49.L55:movl $37,%eax # ’%’jmp .L49.L56:movl $63,%eax # ’?’# Fall Through to .L49Targets & Completion12Switch Statement CompletionPuzzlePuzzle What value returned when op is invalid?AnswerAnswer Register %eax set to op at beginning of procedure This becomes the returned valueAdvantage of Jump TableAdvantage of Jump Table Can do k-way branch in O(1) operations.L49: # Done:movl %ebp,%esp # Finishpopl %ebp # Finishret # Finish13Object CodeSetupSetup Label .L49 becomes address 0x804875c Label .L57 becomes address 0x8048bc0 08048718 <unparse_symbol>: 8048718:55 pushl %ebp 8048719:89 e5 movl %esp,%ebp 804871b:8b 45 08 movl 0x8(%ebp),%eax 804871e:83 f8 05 cmpl $0x5,%eax 8048721:77 39 ja 804875c <unparse_symbol+0x44> 8048723:ff 24 85 c0 8b jmp *0x8048bc0(,%eax,4)14Object Code (cont.)Jump TableJump Table Doesnʼt show up in disassembled code Can inspect using GDBgdb code-examples(gdb) x/6xw 0x8048bc0 Examine 6 hexadecimal format “words” (4-bytes each) Use command “help x” to get format documentation0x8048bc0 <_fini+32>: 0x08048730 0x08048737 0x08048740 0x08048747 0x08048750 0x0804875715Extracting Jump Table from BinaryJump Table Stored in Read Only Data Segment (.Jump Table Stored in Read Only Data Segment (.rodatarodata)) Various fixed values needed by your codeCan examine with Can examine with objdumpobjdumpobjdump code-examples –s –-section=.rodata Show everything in indicated segment.Hard to readHard to read Jump table entries shown with reversed byte ordering E.g., 30870408 really means 0x08048730Contents of section .rodata: 8048bc0 30870408 37870408 40870408 47870408 [email protected]... 8048bd0 50870408 57870408 46616374 28256429 P...W...Fact(%d) 8048be0 203d2025 6c640a00 43686172 203d2025 = %ld..Char = % …16Disassembled Targets movl %esi,%esi does nothing Inserted to align instructions for better cache performance 8048730:b8 2b 00 00 00 movl $0x2b,%eax 8048735:eb 25 jmp 804875c <unparse_symbol+0x44> 8048737:b8 2a 00 00 00 movl $0x2a,%eax 804873c:eb 1e jmp 804875c <unparse_symbol+0x44> 804873e:89 f6 movl %esi,%esi 8048740:b8 2d 00 00 00 movl $0x2d,%eax 8048745:eb 15 jmp 804875c <unparse_symbol+0x44> 8048747:b8 2f 00 00 00 movl $0x2f,%eax 804874c:eb 0e jmp 804875c <unparse_symbol+0x44> 804874e:89 f6 movl %esi,%esi 8048750:b8 25 00 00 00 movl $0x25,%eax 8048755:eb 05 jmp 804875c <unparse_symbol+0x44> 8048757:b8 3f