Carnegie Mellon Introduction to Computer Systems 15 213 18 243 spring 2009 7th Lecture Feb 3rd Instructors Gregory Kesden and Markus P schel Carnegie Mellon Last Time Complete memory addressing mode eax 17 eax 2 ebx ecx 8 Arithmetic operations subl eax ecx sall 4 edx addl 16 ebp ecx ecx ecx eax edx edx 4 ecx ecx Mem 16 ebp leal 4 edx eax eax imull ecx eax eax 4 edx eax eax eax ecx Carnegie Mellon Last Time x86 64 vs IA32 Integer registers 16 x 64 bit vs 8 x 32 bit movq addq vs movl addl Better support for passing function arguments in registers rax eax r8 r8d rbx edx r9 r9d rcx ecx r10 r10d rdx ebx r11 r11d rsi esi r12 r12d rdi edi r13 r13d rsp esp r14 r14d rbp ebp r15 r15d Control Condition code registers Set as side effect or by cmp test Used CF ZF Read out by setx instructions setg setle Or by conditional jumps jle L4 je L10 SF OF Carnegie Mellon Last Time Do While loop Goto Version C Code do Body while Test loop Body if Test goto loop While Do loop Do While Version While version while Test Body if Test goto done do Body while Test done or Goto Version if Test goto done loop Body if Test goto loop done goto middle loop Body middle if Test goto loop Carnegie Mellon Today For loops Switch statements Procedures Carnegie Mellon For Loop Example Square and Multiply 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 bit representation p p0 2p1 22p2 2n 1pn 1 Gives xp z0 z1 2 z2 2 2 zn 12 2 2 Example zi 1 when pi 0 zi x when pi 1 Complexity O log p n 1 times 310 32 38 32 32 2 2 Carnegie Mellon 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 before iteration result x 3 p 10 1 2 3 4 5 1 1 9 9 59049 3 9 81 6561 43046721 10 10102 5 1012 2 102 1 12 0 Carnegie Mellon For Loop Example int result for result 1 p 0 p p 1 if p 0x1 result x x x x General Form for Init Test Update Body Test p 0 Init result 1 Update p p 1 Body if p 0x1 result x x x x Carnegie Mellon For While Do While For Version for Init Test Update Body Goto Version Init if Test goto done loop Body Update if Test goto loop done While Version Init while Test Body Update Do While Version Init if Test goto done do Body Update while Test done Carnegie Mellon For Loop Compilation 1 For Version for Init Test Update Body Goto Version Init if Test goto done loop Body Update if Test goto loop done for result 1 p 0 p p 1 if p 0x1 result x x x x 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 Carnegie Mellon For While Jump to Middle For Version for Init Test Update Body While Version Init while Test Body Update Goto Version Init goto middle loop Body Update middle if Test goto loop done Carnegie Mellon For Loop Compilation 2 For Version for Init Test Update Body Goto Version Init goto middle loop Body Update middle if Test goto loop done for result 1 p 0 p p 1 if p 0x1 result x x x x result 1 goto middle loop if p 0x1 result x x x x p p 1 middle if p 0 goto loop done Carnegie Mellon Today For loops Switch statements Procedures Carnegie Mellon long switch eg long x long y long z long w 1 switch x case 1 w y z break case 2 w y z Fall Through case 3 w z break case 5 case 6 w z break default w 2 return w Switch Statement Example Multiple case labels Here 5 6 Fall through cases Here 2 Missing cases Here 4 Carnegie Mellon Jump Table Structure switch x case val 0 Block 0 case val 1 Block 1 case val n 1 Block n 1 Jump Targets Jump Table Switch Form jtab Targ0 Targ0 Targ1 Targ2 Targn 1 Targ1 Targ2 Code Block 0 Code Block 1 Code Block 2 Approximate Translation target JTab x goto target Targn 1 Code Block n 1 Carnegie Mellon Switch Statement Example IA32 long switch eg long x long y long z long w 1 switch x return w Setup switch eg pushl ebp movl esp ebp pushl ebx movl 1 ebx movl 8 ebp edx movl 16 ebp ecx cmpl 6 edx ja L61 jmp L62 edx 4 Setup Setup Setup w 1 edx x ecx z Will disappear x 6 Blackboard if goto default goto JTab x Carnegie Mellon Switch Statement Example IA32 long switch eg long x long y long z long w 1 switch x return w Setup Indirect jump switch eg pushl ebp movl esp ebp pushl ebx movl 1 ebx movl 8 ebp edx movl 16 ebp ecx cmpl 6 edx ja L61 jmp L62 edx 4 Jump table section rodata align 4 L62 long L61 long L56 long L57 long L58 long L61 long L60 long L60 Setup Setup Setup w 1 edx x ecx z x 6 if goto default goto JTab x x x x x x x x 0 1 2 3 4 5 6 Carnegie Mellon Assembly Setup Explanation Table Structure Each target requires 4 bytes Base address at L62 Jumping Direct jmp L61 Jump target is denoted by label L61 Jump table section rodata align 4 L62 long L61 long L56 long L57 long L58 long L61 long L60 long L60 Indirect jmp L62 edx 4 Start of jump table L62 Must scale by factor of 4 labels have 32 bit 4 Bytes on IA32 Fetch target from effective Address L61 edx 4 Only for 0 x 6 x x x x x x x 0 1 2 3 4 5 6 Carnegie Mellon Jump Table Jump table section rodata align 4 L62 long L61 long L56 long L57 long L58 long L61 long L60 long L60 x x x x x x x 0 1 2 3 4 5 6 switch x case 1 L56 w y z break case 2 L57 w y z Fall Through case 3 L58 w z break case 5 case 6 L60 w z break default L61 w 2 Carnegie Mellon Code Blocks Partial switch x case 2 L57 w y z Fall Through case 3 L58 w z break default L61 w 2 L61 Default case movl 2 ebx w 2 movl ebx eax Return w popl ebx leave ret L57 Case 2 …
View Full Document
Unlocking...