# new data structure: a slice is an open interval of addresses [start, end) # that includes 'start' but not 'end' == code # instruction effective address register displacement immediate # . op subop mod rm32 base index scale r32 # . 1-3 bytes 3 bits 2 bits 3 bits 3 bits 3 bits 2 bits 2 bits 0/1/2/4 bytes 0/1/2/4 bytes slice-empty?: # s : (address slice) -> eax : boolean # . prologue 55/push-ebp 89/copy 3/mod/direct 5/rm32/ebp . . . 4/r32/esp . . # copy esp to ebp # . save registers 51/push-ecx # ecx = s 8b/copy 1/mod/*+disp8 5/rm32/ebp . . . 1/r32/ecx 8/disp8 . # copy *(ebp+8) to ecx # if (s->start == s->end) return true # . eax = s->start 8b/copy 0/mod/indirect 1/rm32/ecx . . . 0/r32/eax . . # copy *ecx to eax # . compare eax and s->end 39/compare 1/mod/*+disp8 1/rm32/ecx . . . 0/r32/eax 4/disp8 . # compare eax and *(ecx+4) b8/copy-to-eax 1/imm32/true 74/jump-if-equal $slice-empty?:end/disp8 b8/copy-to-eax 0/imm32/false $slice-empty?:end: # . restore registers 59/pop-to-ecx # . epilogue 89/copy 3/mod/direct 4/rm32/esp . . . 5/r32/ebp . . # copy ebp to esp 5d/pop-to-ebp c3/return test-slice-empty-true: # . prologue 55/push-ebp 89/copy 3/mod/direct 5/rm32/ebp . . . 4/r32/esp . . # copy esp to ebp # var slice/ecx = {34, 34} 68/push 34/imm32/end 68/push 34/imm32/start 89/copy 3/mod/direct 1/rm32/ecx . . . 4/r32/esp . . # copy esp to ecx # slice-empty?(slice) # . . push args 51/push-ecx # . . call e8/call slice-empty?/disp32 # . . discard args 81 0/subop/add 3/mod/direct 4/rm32/esp . . . . . 4/imm32 # add to esp # check-ints-equal(eax, 1, msg) # . . push args 68/push "F - test-slice-empty-true"/imm32 68/push 1/imm32 50/push-eax # . . call e8/call check-ints-equal/disp32 # . . discard args 81 0/subop/add 3/mod/direct 4/rm32/esp . . . . . 0xc/imm32 # add to esp # . epilogue 89/copy 3/mod/direct 4/rm32/esp . . . 5/r32/ebp . . # copy ebp to esp 5d/pop-to-ebp c3/return test-slice-empty-false: # . prologue 55/push-ebp 89/copy 3/mod/direct 5/rm32/ebp . . . 4/r32/esp . . # copy esp to ebp # var slice/ecx = {34, 23} 68/push 23/imm32/end 68/push 34/imm32/start 89/copy 3/mod/direct 1/rm32/ecx . . . 4/r32/esp . . # copy esp to ecx # slice-empty?(slice) # . . push args 51/push-ecx # . . call e8/call slice-empty?/disp32 # . . discard args 81 0/subop/add 3/mod/direct 4/rm32/esp . . . . . 4/imm32 # add to esp # check-ints-equal(eax, 0, msg) # . . push args 68/push "F - test-slice-empty-false"/imm32 68/push 0/imm32 50/push-eax # . . call e8/call check-ints-equal/disp32 # . . discard args 81 0/subop/add 3/mod/direct 4/rm32/esp . . . . . 0xc/imm32 # add to esp # . epilogue 89/copy 3/mod/direct 4/rm32/esp . . . 5/r32/ebp . . # copy ebp to esp 5d/pop-to-ebp c3/return slice-equal?: # s : (address slice), p : (address string) -> eax : boolean # pseudocode: # if (p == 0) return (s == 0) # currs = s->start # maxs = s->end # if (maxs - currs != p->length) return false # currp = p->data # while currs < maxs # if (*currs != *currp) return false # ++currs # ++currp # return true # # registers: # currs: edx # maxs: esi # currp: ebx # *currs: eax # *currp: ecx # # . prologue 55/push-ebp 89/copy 3/mod/direct 5/rm32/ebp . . . 4/r32/esp . . # copy esp to ebp # . save registers 51/push-ecx 52/push-edx 53/push-ebx 56/push-esi # esi = s 8b/copy 1/mod/*+disp8 5/rm32/ebp . . . 6/r32/esi 8/disp8 . # copy *(ebp+8) to esi # currs/edx = s->start 8b/copy 0/mod/indirect 6/rm32/esi . . . 2/r32/edx . . # copy *esi to edx # maxs/esi = s->end 8b/copy 1/mod/*+disp8 6/rm32/esi . . . 6/r32/esi 4/disp8 . # copy *(esi+4) to esi # eax = maxs - currs 89/copy 3/mod/direct 0/rm32/eax . . . 6/r32/esi . . # copy esi to eax 29/subtract 3/mod/direct 0/rm32/eax . . . 2/r32/edx . . # subtract edx from eax # ebx = p 8b/copy 1/mod/*+disp8 5/rm32/ebp . . . 3/r32/ebx 0xc/disp8 . # copy *(ebp+12) to ebx # if (p != 0) goto next check 81 7/subop/compare 3/mod/direct 3/rm32/ebx . . . . . 0/imm32 # compare ebx 75/jump-if-not-equal $slice-equal?:nonnull-string/disp8 $slice-equal?:null-string: # return s->start == s->end 3d/compare-eax-and 0/imm32 74/jump-if-equal $slice-equal?:true/disp8 eb/jump $slice-equal?:false/disp8 $slice-equal?:nonnull-string: # if (eax != p->length) return false 39/compare 0/mod/indirect 3/rm32/ebx . . . 0/r32/eax . . # compare *ebx and eax 75/jump-if-not-equal $slice-equal?:false/disp8 # currp/ebx = p->data 81 0/subop/add 3/mod/direct 3/rm32/ebx . . . . . 4/imm32 # add to ebx # eax = ecx = 0 31/xor 3/mod/direct 0/rm32/eax . . . 0/r32/eax . . # clear eax 31/xor 3/mod/direct 1/rm32/ecx . . . 1/r32/ecx . . # clear ecx $slice-equal?:loop: # if (currs >= maxs) return true 39/compare 3/mod/direct 2/rm32/edx . . . 6/r32/esi . . # compare edx with esi 73/jump-if-greater-or-equal-unsigned $slice-equal?:true/disp8 # AL = *currp 8a/copy-byte 0/mod/indirect 3/rm32/ebx . . . 0/r32/AL . . # copy byte at *ebx to AL # CL = *currs 8a/copy-byte 0/mod/indirect 2/rm32/edx . . . 1/r32/CL . . # copy byte at *edx to CL # if (eax != ecx) return false 39/compare 3/mod/direct 0/rm32/eax . . . 1/r32/ecx . . # compare eax and ecx 75/jump-if-not-equal $slice-equal?:false/disp8 # ++currp 43/increment-ebx # ++currs 42/increment-edx eb/jump $slice-equal?:loop/disp8 $slice-equal?:false: b8/copy-to-eax 0/imm32 eb/jump $slice-equal?:end/disp8 $slice-equal?:true: b8/copy-to-eax 1/imm32 $slice-equal?:end: # . restore registers 5e/pop-to-esi 5b/pop-to-ebx 5a/pop-to-edx 59/pop-to-ecx # . epilogue 89/copy 3/mod/direct 4/rm32/esp . . . 5/r32/ebp . . # copy ebp to esp 5d/pop-to-ebp c3/return test-slice-equal: # - slice-equal?(slice("Abc"), "Abc") == 1 # . prologue 55/push-ebp 89/copy 3/mod/direct 5/rm32/ebp . . . 4/r32/esp . . # copy esp to ebp # (eax..ecx) = "Abc" b8/copy-to-eax "Abc"/imm32 8b/copy 0/mod/indirect 0/rm32/eax . . . 1/r32/ecx . . # copy *eax to ecx 8d/copy-address 1/mod/*+disp8 4/rm32/sib 0/base/eax 1/index/ecx . 1/r32/ecx 4/disp8 . # copy eax+ecx+4 to ecx 05/add-to-eax 4/imm32 # var slice/ecx = {eax, ecx} 51/push-ecx 50/push-eax 89/copy 3/mod/direct 1/rm32/ecx . . . 4/r32/esp . . # copy esp to ecx # eax = slice-equal?(ecx, "Abc") # . . push args 68/push "Abc"/imm32 51/push-ecx # . . call e8/call slice-equal?/disp32 # . . discard args 81 0/subop/add 3/mod/direct 4/rm32/esp . . . . . 8/imm32 # add to esp # check-ints-equal(eax, 1, msg) # . . push args 68/push "F - test-slice-equal"/imm32 68/push 1/imm32 50/push-eax # . . call e8/call check-ints-equal/disp32 # . . discard args 81 0/subop/add 3/mod/direct 4/rm32/esp . . . . . 0xc/imm32 # add to esp # . epilogue 89/copy 3/mod/direct 4/rm32/esp . . . 5/r32/ebp . . # copy ebp to esp 5d/pop-to-ebp c3/return test-slice-equal-false: # - slice-equal?(slice("bcd"), "Abc") == 0 # . prologue 55/push-ebp 89/copy 3/mod/direct 5/rm32/ebp . . . 4/r32/esp . . # copy esp to ebp # (eax..ecx) = "bcd" b8/copy-to-eax "bcd"/imm32 8b/copy 0/mod/indirect 0/rm32/eax . . . 1/r32/ecx . . # copy *eax to ecx 8d/copy-address 1/mod/*+disp8 4/rm32/sib 0/base/eax 1/index/ecx . 1/r32/ecx 4/disp8 . # copy eax+ecx+4 to ecx 05/add-to-eax 4/imm32 # var slice/ecx = {eax, ecx} 51/push-ecx 50/push-eax 89/copy 3/mod/direct 1/rm32/ecx . . . 4/r32/esp . . # copy esp to ecx # eax = slice-equal?(ecx, "Abc") # . . push args 68/push "Abc"/imm32 51/push-ecx # . . call e8/call slice-equal?/disp32 # . . discard args 81 0/subop/add 3/mod/direct 4/rm32/esp . . . . . 8/imm32 # add to esp # check-ints-equal(eax, 0, msg) # . . push args 68/push "F - test-slice-equal-false"/imm32 68/push 0/imm32 50/push-eax # . . call e8/call check-ints-equal/disp32 # . . discard args 81 0/subop/add 3/mod/direct 4/rm32/esp . . . . . 0xc/imm32 # add to esp # . epilogue 89/copy 3/mod/direct 4/rm32/esp . . . 5/r32/ebp . . # copy ebp to esp 5d/pop-to-ebp c3/return test-slice-equal-too-long: # - slice-equal?(slice("Abcd"), "Abc") == 0 # . prologue 55/push-ebp 89/copy 3/mod/direct 5/rm32/ebp . . . 4/r32/esp . . # copy esp to ebp # (eax..ecx) = "Abcd" b8/copy-to-eax "Abcd"/imm32 8b/copy 0/mod/indirect 0/rm32/eax . . . 1/r32/ecx . . # copy *eax to ecx 8d/copy-address 1/mod/*+disp8 4/rm32/sib 0/base/eax 1/index/ecx . 1/r32/ecx 4/disp8 . # copy eax+ecx+4 to ecx 05/add-to-eax 4/imm32 # var slice/ecx = {eax, ecx} 51/push-ecx 50/push-eax 89/copy 3/mod/direct 1/rm32/ecx . . . 4/r32/esp . . # copy esp to ecx # eax = slice-equal?(ecx, "Abc") # . . push args 68/push "Abc"/imm32 51/push-ecx # . . call e8/call slice-equal?/disp32 # . . discard args 81 0/subop/add 3/mod/direct 4/rm32/esp . . . . . 8/imm32 # add to esp # check-ints-equal(eax, 0, msg) # . . push args 68/push "F - test-slice-equal-too-long"/imm32 68/push 0/imm32 50/push-eax # . . call e8/call check-ints-equal/disp32 # . . discard args 81 0/subop/add 3/mod/direct 4/rm32/esp . . . . . 0xc/imm32 # add to esp # . epilogue 89/copy 3/mod/direct 4/rm32/esp . . . 5/r32/ebp . . # copy ebp to esp 5d/pop-to-ebp c3/return test-slice-equal-too-short: # - slice-equal?(slice("A"), "Abc") == 0 # . prologue 55/push-ebp 89/copy 3/mod/direct 5/rm32/ebp . . . 4/r32/esp . . # copy esp to ebp # (eax..ecx) = "A" b8/copy-to-eax "A"/imm32 8b/copy 0/mod/indirect 0/rm32/eax . . . 1/r32/ecx . . # copy *eax to ecx 8d/copy-address 1/mod/*+disp8 4/rm32/sib 0/base/eax 1/index/ecx . 1/r32/ecx 4/disp8 . # copy eax+ecx+4 to ecx 05/add-to-eax 4/imm32 # var slice/ecx = {eax, ecx} 51/push-ecx 50/push-eax 89/copy 3/mod/direct 1/rm32/ecx . . . 4/r32/esp . . # copy esp to ecx # eax = slice-equal?(ecx, "Abc") # . . push args 68/push "Abc"/imm32 51/push-ecx # . . call e8/call slice-equal?/disp32 # . . discard args 81 0/subop/add 3/mod/direct 4/rm32/esp . . . . . 8/imm32 # add to esp # check-ints-equal(eax, 0, msg) # . . push args 68/push "F - test-slice-equal-too-short"/imm32 68/push 0/imm32 50/push-eax # . . call e8/call check-ints-equal/disp32 # . . discard args 81 0/subop/add 3/mod/direct 4/rm32/esp . . . . . 0xc/imm32 # add to esp # . epilogue 89/copy 3/mod/direct 4/rm32/esp . . . 5/r32/ebp . . # copy ebp to esp 5d/pop-to-ebp c3/return test-slice-equal-empty: # - slice-equal?(slice(""), "Abc") == 0 # . prologue 55/push-ebp 89/copy 3/mod/direct 5/rm32/ebp . . . 4/r32/esp . . # copy esp to ebp # var slice/ecx 68/push 0/imm32/end 68/push 0/imm32/start 89/copy 3/mod/direct 1/rm32/ecx . . . 4/r32/esp . . # copy esp to ecx # eax = slice-equal?(ecx, "Abc") # . . push args 68/push "Abc"/imm32 51/push-ecx # . . call e8/call slice-equal?/disp32 # . . discard args 81 0/subop/add 3/mod/direct 4/rm32/esp . . . . . 8/imm32 # add to esp # check-ints-equal(eax, 0, msg) # . . push args 68/push "F - test-slice-equal-empty"/imm32 68/push 0/imm32 50/push-eax # . . call e8/call check-ints-equal/disp32 # . . discard args 81 0/subop/add 3/mod/direct 4/rm32/esp . . . . . 0xc/imm32 # add to esp # . epilogue 89/copy 3/mod/direct 4/rm32/esp . . . 5/r32/ebp . . # copy ebp to esp 5d/pop-to-ebp c3/return test-slice-equal-with-empty: # - slice-equal?(slice("Ab"), "") == 0 # . prologue 55/push-ebp 89/copy 3/mod/direct 5/rm32/ebp . . . 4/r32/esp . . # copy esp to ebp # (eax..ecx) = "Ab" b8/copy-to-eax "Ab"/imm32 8b/copy 0/mod/indirect 0/rm32/eax . . . 1/r32/ecx . . # copy *eax to ecx 8d/copy-address 1/mod/*+disp8 4/rm32/sib 0/base/eax 1/index/ecx . 1/r32/ecx 4/disp8 . # copy eax+ecx+4 to ecx 05/add-to-eax 4/imm32 # var slice/ecx = {eax, ecx} 51/push-ecx 50/push-eax 89/copy 3/mod/direct 1/rm32/ecx . . . 4/r32/esp . . # copy esp to ecx # eax = slice-equal?(ecx, "") # . . push args 68/push ""/imm32 51/push-ecx # . . call e8/call slice-equal?/disp32 # . . discard args 81 0/subop/add 3/mod/direct 4/rm32/esp . . . . . 8/imm32 # add to esp # check-ints-equal(eax, 0, msg) # . . push args 68/push "F - test-slice-equal-with-empty"/imm32 68/push 0/imm32 50/push-eax # . . call e8/call check-ints-equal/disp32 # . . discard args 81 0/subop/add 3/mod/direct 4/rm32/esp . . . . . 0xc/imm32 # add to esp # . epilogue 89/copy 3/mod/direct 4/rm32/esp . . . 5/r32/ebp . . # copy ebp to esp 5d/pop-to-ebp c3/return test-slice-equal-empty-with-empty: # - slice-equal?(slice(""), "") == 1 # . prologue 55/push-ebp 89/copy 3/mod/direct 5/rm32/ebp . . . 4/r32/esp . . # copy esp to ebp # var slice/ecx 68/push 0/imm32/end 68/push 0/imm32/start 89/copy 3/mod/direct 1/rm32/ecx . . . 4/r32/esp . . # copy esp to ecx # eax = slice-equal?(ecx, "") # . . push args 68/push ""/imm32 51/push-ecx # . . call e8/call slice-equal?/disp32 # . . discard args 81 0/subop/add 3/mod/direct 4/rm32/esp . . . . . 8/imm32 # add to esp # check-ints-equal(eax, 1, msg) # . . push args 68/push "F - test-slice-equal-empty-with-empty"/imm32 68/push 1/imm32 50/push-eax # . . call e8/call check-ints-equal/disp32 # . . discard args 81 0/subop/add 3/mod/direct 4/rm32/esp . . . . . 0xc/imm32 # add to esp # . epilogue 89/copy 3/mod/direct 4/rm32/esp . . . 5/r32/ebp . . # copy ebp to esp 5d/pop-to-ebp c3/return test-slice-equal-with-null: # - slice-equal?(slice("Ab"), null) == 0 # . prologue 55/push-ebp 89/copy 3/mod/direct 5/rm32/ebp . . . 4/r32/esp . . # copy esp to ebp # (eax..ecx) = "Ab" b8/copy-to-eax "Ab"/imm32 8b/copy 0/mod/indirect 0/rm32/eax . . . 1/r32/ecx . . # copy *eax to ecx 8d/copy-address 1/mod/*+disp8 4/rm32/sib 0/base/eax 1/index/ecx . 1/r32/ecx 4/disp8 . # copy eax+ecx+4 to ecx 05/add-to-eax 4/imm32 # var slice/ecx = {eax, ecx} 51/push-ecx 50/push-eax 89/copy 3/mod/direct 1/rm32/ecx . . . 4/r32/esp . . # copy esp to ecx # eax = slice-equal?(ecx, 0) # . . push args 68/push 0/imm32 51/push-ecx # . . call e8/call slice-equal?/disp32 # . . discard args 81 0/subop/add 3/mod/direct 4/rm32/esp . . . . . 8/imm32 # add to esp # check-ints-equal(eax, 0, msg) # . . push args 68/push "F - test-slice-equal-with-null"/imm32 68/push 0/imm32 50/push-eax # . . call e8/call check-ints-equal/disp32 # . . discard args 81 0/subop/add 3/mod/direct 4/rm32/esp . . . . . 0xc/imm32 # add to esp # . epilogue 89/copy 3/mod/direct 4/rm32/esp . . . 5/r32/ebp . . # copy ebp to esp 5d/pop-to-ebp c3/return slice-starts-with?: # s : (address slice), head : (address string) -> eax : boolean # pseudocode # lenh = head->length # if (lenh > s->end - s->start) return false # i = 0 # currs = s->start # currp = head->data # while i < lenh # if (*currs != *currh) return false # ++i # ++currs # ++currh # return true # # registers: # currs: esi # currh: edi # *currs: eax # *currh: ebx # i: ecx # lenh: edx # # . prologue 55/push-ebp 89/copy 3/mod/direct 5/rm32/ebp . . . 4/r32/esp . . # copy esp to ebp # . save registers 51/push-ecx 52/push-edx 53/push-ebx 56/push-esi 57/push-edi # esi = s 8b/copy 1/mod/*+disp8 5/rm32/ebp . . . 6/r32/esi 8/disp8 . # copy *(ebp+8) to esi # ecx = s->end - s->start 8b/copy 1/mod/*+disp8 6/rm32/esi . . . 1/r32/ecx 4/disp8 . # copy *(esi+4) to ecx 2b/subtract 0/mod/indirect 6/rm32/esi . . . 1/r32/ecx . . # subtract *esi from ecx # edi = head 8b/copy 1/mod/*+disp8 5/rm32/ebp . . . 7/r32/edi 0xc/disp8 . # copy *(ebp+12) to edi # lenh/edx = head->length 8b/copy 0/mod/indirect 7/rm32/edi . . . 2/r32/edx . . # copy *edi to edx # if (lenh > s->end - s->start) return false 39/compare 3/mod/direct 2/rm32/edx . . . 1/r32/ecx . . # compare edx with ecx 7f/jump-if-greater $slice-starts-with?:false/disp8 # currs/esi = s->start 8b/subtract 0/mod/indirect 6/rm32/esi . . . 6/r32/esi . . # copy *esi to esi # currh/edi = head->data 81 0/subop/add 3/mod/direct 7/rm32/edi . . . . . 4/imm32 # add to edi # i/ecx = 0 31/xor 3/mod/direct 1/rm32/ecx . . . 1/r32/ecx . . # clear ecx # eax = ebx = 0 31/xor 3/mod/direct 0/rm32/eax . . . 0/r32/eax . . # clear eax 31/xor 3/mod/direct 3/rm32/ebx . . . 3/r32/ebx . . # clear ebx $slice-starts-with?:loop: # if (i >= lenh) return true 39/compare 3/mod/direct 1/rm32/ecx . . . 2/r32/edx . . # compare ecx with edx 7d/jump-if-greater-or-equal $slice-starts-with?:true/disp8 # AL = *currs 8a/copy-byte 0/mod/indirect 6/rm32/esi . . . 0/r32/AL . . # copy byte at *esi to AL # BL = *currh 8a/copy-byte 0/mod/indirect 7/rm32/edi . . . 3/r32/BL . . # copy byte at *edi to BL # if (*currs != *currh) return false 39/compare 3/mod/direct 0/rm3