Systems I Machine Level Programming IV Control Flow Topics Control Flow For Loops Switch Statements For Loop Example 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 Algorithm Exploit property that p p0 2p1 4p2 2n 1pn 1 Gives xp z0 z1 2 z2 2 2 zn 12 2 2 zi 1 when pi 0 zi x when pi 1 Complexity O log p n 1 times Example 310 32 38 32 32 2 2 2 ipwr 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 1 1 9 9 531441 x 3 9 81 6561 43046721 p 10 5 2 1 0 3 For Loop Example General Form int result for result 1 p 0 p p 1 if p 0x1 result x x x x for Init Test Update Body Init result 1 Body Test p 0 Update p p 1 if p 0x1 result x x x x 4 For While For Version for Init Test Update Body Do While Version Init if Test goto done do Body Update while Test done While Version Init while Test Body Update Goto Version Init if Test goto done loop Body Update if Test goto loop done 5 For Loop Compilation Goto Version 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 Init if Test goto done loop Body Update if Test goto loop done Init result 1 Test p 0 Body if p 0x1 result x x x x Update p p 1 6 typedef 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 Switch Statements Implementation Options Series of conditionals Good if few cases Slow if many Jump Table Lookup branch target Avoids conditionals Possible when cases are small integer constants GCC Picks one based on case structure Bug in example code No default given 7 Jump Table Structure Switch Form switch op case val 0 Block 0 case val 1 Block 1 case val n 1 Block n 1 Jump Table jtab Targ0 Jump Targets Targ0 Targ1 Targ2 Targn 1 Targ1 Targ2 Code Block 0 Code Block 1 Code Block 2 Approx Translation target JTab op goto target Targn 1 Code Block n 1 8 Switch Statement Example Branching Possibilities typedef enum ADD MULT MINUS DIV MOD BAD op type Enumerated Values ADD MULT MINUS DIV MOD BAD char unparse symbol op type op switch op Setup unparse symbol pushl ebp movl esp ebp movl 8 ebp eax cmpl 5 eax ja L49 jmp L57 eax 4 0 1 2 3 4 5 Setup Setup eax op Compare op 5 If goto done goto Table op 9 Assembly Setup Explanation Symbolic Labels Labels of form LXX translated into addresses by assembler Table Structure Each target requires 4 bytes Base address at L57 Jumping jmp L49 Jump target is denoted by label L49 jmp 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 4 10 Jump Table Table Contents Targets Completion section rodata align 4 L57 long L51 Op long L52 Op long L53 Op long L54 Op long L55 Op long L56 Op 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 L49 0 1 2 3 4 5 Enumerated Values ADD MULT MINUS DIV MOD BAD 0 1 2 3 4 5 11 Switch Statement Completion L49 movl ebp esp popl ebp ret Done Finish Finish Finish Puzzle What value returned when op is invalid Answer Register eax set to op at beginning of procedure This becomes the returned value Advantage of Jump Table Can do k way branch in O 1 operations 12 Object Code Setup Label L49 becomes address 0x804875c Label L57 becomes address 0x8048bc0 08048718 unparse symbol 8048718 55 pushl 8048719 89 e5 movl 804871b 8b 45 08 movl 804871e 83 f8 05 cmpl 8048721 77 39 ja 8048723 ff 24 85 c0 8b jmp ebp esp ebp 0x8 ebp eax 0x5 eax 804875c unparse symbol 0x44 0x8048bc0 eax 4 13 Object Code cont Jump Table Doesn t show up in disassembled code Can inspect using GDB gdb code examples gdb x 6xw 0x8048bc0 Examine 6 hexadecimal format words 4 bytes each Use command help x to get format documentation 0x8048bc0 fini 32 0x08048730 0x08048737 0x08048740 0x08048747 0x08048750 0x08048757 14 Extracting Jump Table from Binary Jump Table Stored in Read Only Data Segment rodata Various fixed values needed by your code Can examine with objdump objdump code examples s section rodata Show everything in indicated segment Hard to read Contents 8048bc0 8048bd0 8048be0 Jump table entries shown with reversed byte ordering of section rodata 30870408 37870408 40870408 47870408 50870408 57870408 46616374 28256429 203d2025 6c640a00 43686172 203d2025 E g 30870408 0 7 G P W Fact d ld Char really means 0x08048730 15 Disassembled Targets 8048730 b8 8048735 eb 8048737 b8 804873c eb 804873e 89 8048740 b8 8048745 eb 8048747 b8 804874c eb 804874e 89 8048750 b8 8048755 eb 8048757 b8 2b 25 2a 1e f6 2d 15 2f 0e f6 25 05 3f 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 movl jmp movl jmp movl movl jmp movl jmp movl movl jmp movl 0x2b eax 804875c unparse symbol 0x44 0x2a eax 804875c unparse symbol 0x44 esi esi 0x2d eax 804875c unparse symbol 0x44 0x2f eax 804875c unparse symbol 0x44 esi esi 0x25 eax 804875c unparse symbol 0x44 0x3f eax movl esi esi does nothing Inserted to align instructions for better cache performance 16 Matching Disassembled Targets Entry 0x08048730 0x08048737 0x08048740 0x08048747 0x08048750 0x08048757 8048730 b8 8048735 eb 8048737 b8 804873c eb 804873e 89 8048740 b8 8048745 eb 8048747 b8 804874c eb 804874e 89 8048750 b8 8048755 eb 8048757 b8 2b 25 2a 1e f6 2d 15 2f 0e f6 25 05 3f 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 movl jmp movl jmp movl movl jmp movl jmp movl movl jmp movl 17 Sparse Switch Example Return x 111 if x is multiple 999 1 otherwise int div111 int x switch x case 0 return 0 case 111 return 1 case 222 return 2 case 333 return 3 case 444 return 4 case 555 return 5 case 666 return 6 case 777 return 7 case 888 return 8 case 999 return 9 default return 1 Not practical to use jump table Would require 1000 entries …