Bug in Boyer-Moore BM.asm ?

[Rav]

Confirmed

Thanks / Rav

[hutch--]

Using small samples in short strings to search is just about meaningless. Look at any BM variant and you will see that they are designed for finding longer sub strings in longer main strings. If you are doing searches of main strings under a few megabytes, you use a byte scanner as it will generally be fast enough and are byte perfect.

This topic should not be in the Campus, it should be in the lab.

[Rav]

Using small samples in short strings to search is just about meaningless. Look at any BM variant and you will see that they are designed for finding longer sub strings in longer main strings. If you are doing searches of main strings under a few megabytes, you use a byte scanner as it will generally be fast enough and are byte perfect.

This topic should not be in the Campus, it should be in the lab.

Hi, hutch.  In fact, I WAS using large strings in my testing (600K and upwards), when I found all these issues.  But when reporting them to the forum I reduced them to a minimum length that still produced the error in order to simplify people being able to replicate them.  Either way, whether it makes sense to use a byte scanner or not for small strings, I think that any program should always return the correct result no matter what size strings they are passed and, of course, not hang.

[jj2007]

The BM algos are not that impressive, either. This searches Windows.inc for "Duplicate":

Code Select Expand

Intel(R) Core(TM) i5-2450M CPU @ 2.50GHz
2534 ms         for BMBinSearch, result=977320
2298 ms         for MB Instr_(),  result=977320
788 ms          for new Instr_(),  result=977320

2493 ms         for BMBinSearch, result=977320
2309 ms         for MB Instr_(),  result=977320
784 ms          for new Instr_(),  result=977320

2488 ms         for BMBinSearch, result=977320
2328 ms         for MB Instr_(),  result=977320
781 ms          for new Instr_(),  result=977320

[hutch--]

 

Rav,

> I think that any program should always return the correct result no matter what size strings they are passed and, of course, not hang.

What I did over 16 years ago was produce 3 BM algos according to the original design specs of Bob Boyer. Although I did massive testing of these algos over gigabytes of data, I don't believe there is an exhaustive technique to verify this family of algorithms.

The solution has always been if you need algos of this type and the existing ones are not doing the job you want, write them yourself, researching BM algos is a joy to behold, character building and a ton of fun if you can spend the life and time doing it.

A well written byte scanner is generally fast enough on modern hardware unless you are into gigabytes of data to search and there you will have to look for other designs of search algorithms.

[jj2007]

The Boyer-Moore stuff is too slow for my taste. Good ol' Instr_() is already faster than BMBinSearch, and I am working on a new one that is even a tick faster. Results for a 4,397,206 bytes file:

Code Select Expand

Intel(R) Core(TM) i5-2450M CPU @ 2.50GHz
317 ms          for BMBinSearch, result=4397069
199 ms          for MB Instr_(),  result=4397069
58 ms           for new Instr_(),  result=4397069

312 ms          for BMBinSearch, result=4397069
199 ms          for MB Instr_(),  result=4397069
56 ms           for new Instr_(),  result=4397069

314 ms          for BMBinSearch, result=4397069
197 ms          for MB Instr_(),  result=4397069
56 ms           for new Instr_(),  result=4397069

Just run the attached exe, it will grab the 4MB file from my personal site if it doesn't find it in the folder.

[hutch--]

The type of testing that makes sense to me is start with a long string, your 4 meg is fine. Append a unique string pattern to search for, almost at the end, add something after it and test the search algo on something predictable. This means the algo must plough through a mountain of stuff where there are no matches to get to the near end to find a match.

What kills a BM based algo is the lookup table construction before any search is done. It must also repeatedly access the table which is a slow memory acess at a high hit rate. At their best, a very long search string with highly random data to search through yields fast results but there are many situations where they deliver sub optimal performance. Byte scanners are reliable and are not alignment sensitive.

I have seen attempts to use larger data sizes than bytes but the overhead usually kills them.

[jj2007]

The type of testing that makes sense to me is start with a long string, your 4 meg is fine. Append a unique string pattern to search for, almost at the end, add something after it and test the search algo on something predictable.

That's exactly what the test above does, and it yields exactly the same correct result for all three algos tested. Besides, you get an interesting text free of charge

[hutch--]

How long is your search string ?

[jj2007]

13 bytes. With a 60 byte string, BM is still half as fast as the new algo.

[hutch--]

You are wasting your time with such small strings, both the source and the search string. Any decent byte scanner will eat it alive when the source and search is so small. Try a 64 byte string on a few gigabytes of data to see which is faster in that context. A BM has never been any good on tiny search patterns, you get a break even point as they get longer then advantages if the string being searched does not have repetitive patterns.

I am working on 64 bit code at the moment so I don't have the time to play with this but from the research I did back 15 years or so, if the search pattern is long enough, it allows the search point to jump much longer distances which if it is long enough, it makes up for the table construction and the high memory reads.

[mineiro]

Hello sir Rav;
This code is not optimized. I created this code after read this topic, to you do your tests in an easy way.
main.asm

Code Select Expand


;ML.EXE /c /coff /Cp main.asm
;LINK.EXE /SUBSYSTEM:CONSOLE main.obj
;main | echo %errorlevel%

include \masm32\include\masm32rt.inc

Boyer_Moore PROTO :dword,:dword,:dword,:dword,:dword

.data
file db "\masm32\include\windows.inc",0

string db "Duplicate"


align 4
Text_test db 'xx includix'
String_test db 'did'


.code
start:

;-----------------------------------
    call main ;will search for string "Duplicate" in file \masm32\include\windows.inc
;-----------------------------------
;if you want to check specific cases, comment call above and uncoment line below to Text_test and String_test cases
;    invoke Boyer_Moore,0,addr Text_test,sizeof Text_test,addr String_test,sizeof String_test
;-----------------------------------
    invoke ExitProcess,eax


main proc uses esi edi ebx

LOCAL plc:DWORD ;cmd line pointer
LOCAL saida:DWORD ;output handle
LOCAL manipulador_arquivo:dword ;file handle
LOCAL tamanho:DWORD ;source file size
LOCAL mapeado:DWORD ;ptr source file
LOCAL mem_aloc:DWORD ;ptr mem alloc
LOCAL nada:dword
LOCAL arq_mape:DWORD ;mapped file handle
LOCAL pos:DWORD ;initial position
LOCAL return_value:DWORD ;return result in eax register

invoke GetStdHandle,STD_OUTPUT_HANDLE
mov saida,eax

invoke GetCommandLine
mov plc,eax

invoke CreateFile,addr file,GENERIC_READ,0,0,OPEN_EXISTING,FILE_FLAG_SEQUENTIAL_SCAN,0 ;open source file
mov manipulador_arquivo,eax ;handle

invoke GetFileSize, manipulador_arquivo,NULL ;sizeof source file
mov tamanho,eax
invoke CreateFileMapping,manipulador_arquivo,NULL,PAGE_READONLY,0,0,0 ;mapped file handle
mov arq_mape,eax

invoke MapViewOfFile,eax,FILE_MAP_READ,0,0,0 ;map it, file contents pointer
mov mapeado,eax
invoke CloseHandle,manipulador_arquivo ;don't need this anymore


mov pos,0
invoke Boyer_Moore,pos,mapeado,tamanho,addr string,sizeof string
mov return_value,eax

invoke UnmapViewOfFile,mapeado

mov eax,return_value
    ret
main endp


Boyer_Moore proc uses ebx esi edi startpos:dword,lpSource:dword,srcLngth:dword,lpSubStr:dword,subLngth:dword
LOCAL bad_chars[256]:dword

mov eax,-2 ;assume error in parameters data

.if srcLngth == 0
ret
.endif

.if subLngth == 0
ret
.endif

mov ecx,subLngth
.if ecx > srcLngth
ret
.endif

mov ecx,startpos
.if ecx > srcLngth
ret
.endif

lea edi,bad_chars
mov ecx,256
mov eax,subLngth
rep stosd

lea edi,bad_chars
mov esi,lpSubStr
mov ecx,subLngth
add esi,ecx
dec esi

movzx eax,byte ptr [esi]
mov dword ptr [edi+eax*4],1
mov ebx,1
dec esi
dec ecx
mov edx,subLngth

.while ecx != 0
movzx eax,byte ptr [esi]
.if dword ptr [edi+eax*4] == edx
mov dword ptr [edi+eax*4],ebx
inc ebx
.endif
dec esi
dec ecx
.endw

mov esi,lpSubStr
mov edi,lpSource
mov eax,startpos
add edi,eax
mov ebx,srcLngth
add ebx,lpSource

try_again:
.if edi >= ebx
mov eax,-1
ret
.endif

mov ecx,subLngth
add ecx,edi
.if edi > ebx
mov eax,-1
ret
.endif

mov ecx,subLngth
@@:
movzx eax,byte ptr [edi+ecx-1]
.if byte ptr [esi+ecx-1] == al
dec ecx
jnz @B
mov eax,edi
sub eax,lpSource
ret
.else
mov eax,dword ptr [bad_chars+eax*4]
.if eax != subLngth
add edi,eax
jmp try_again
.else
add edi,ecx
jmp try_again
.endif
.endif
ret
Boyer_Moore endp

end start



[Rav]

Hello sir Rav;
This code is not optimized. I created this code after read this topic, to you do your tests in an easy way.

Thank you.  / Rav

[mineiro]

I have commented code, maybe can be usefull:

Code Select Expand


;ML.EXE /c /coff /Cp main.asm
;LINK.EXE /SUBSYSTEM:CONSOLE main.obj
;main | echo %errorlevel%

include \masm32\include\masm32rt.inc

Boyer_Moore PROTO :dword,:dword,:dword,:dword,:dword

.data
file db "\masm32\include\windows.inc",0

string db "Duplicate"


align 4
Text_test db 'a'
String_test db 'a'

;Text_test db 'xx includix'
;String_test db 'did'

.code
start:

;-----------------------------------
;    call main ;will search for string "Duplicate" in file \masm32\include\windows.inc
;-----------------------------------
;if you want to check specific cases, comment call above and uncoment line below to Text_test and String_test cases
    invoke Boyer_Moore,0,addr Text_test,sizeof Text_test,addr String_test,sizeof String_test
;-----------------------------------
    invoke ExitProcess,eax


main proc uses esi edi ebx

LOCAL plc:DWORD ;cmd line pointer
LOCAL saida:DWORD ;output handle
LOCAL manipulador_arquivo:dword ;file handle
LOCAL tamanho:DWORD ;source file size
LOCAL mapeado:DWORD ;ptr source file
LOCAL mem_aloc:DWORD ;ptr mem alloc
LOCAL nada:dword
LOCAL arq_mape:DWORD ;mapped file handle
LOCAL pos:DWORD ;initial position
LOCAL return_value:DWORD ;return result in eax register

invoke GetStdHandle,STD_OUTPUT_HANDLE
mov saida,eax

invoke GetCommandLine
mov plc,eax

invoke CreateFile,addr file,GENERIC_READ,0,0,OPEN_EXISTING,FILE_FLAG_SEQUENTIAL_SCAN,0 ;open source file
mov manipulador_arquivo,eax ;handle

invoke GetFileSize, manipulador_arquivo,NULL ;sizeof source file
mov tamanho,eax
invoke CreateFileMapping,manipulador_arquivo,NULL,PAGE_READONLY,0,0,0 ;mapped file handle
mov arq_mape,eax

invoke MapViewOfFile,eax,FILE_MAP_READ,0,0,0 ;map it, file contents pointer
mov mapeado,eax
invoke CloseHandle,manipulador_arquivo ;don't need this anymore


mov pos,0
invoke Boyer_Moore,pos,mapeado,tamanho,addr string,sizeof string
mov return_value,eax

invoke UnmapViewOfFile,mapeado
;invoke GlobalFree,mem_aloc

mov eax,return_value
    ret
main endp


Boyer_Moore proc uses ebx esi edi startpos:dword,lpSource:dword,srcLngth:dword,lpSubStr:dword,subLngth:dword
LOCAL bad_chars[256]:dword


mov eax,-2 ;assume error in parameters data

.if srcLngth == 0 ;input size is zero?
ret
.endif

.if subLngth == 0 ;substring size is zero?
ret
.endif

mov ecx,subLngth
.if ecx > srcLngth ;substring size is bigger than source size?
ret
.endif

mov ecx,startpos ;start position is bigger than source size?
.if ecx > srcLngth
ret
.endif

lea edi,bad_chars ;create a lookup table filled with substring size
mov ecx,256
mov eax,subLngth
rep stosd

lea edi,bad_chars
mov esi,lpSubStr
mov ecx,subLngth
add esi,ecx
dec esi ;point to last char of substring, zero index based


;-------------------------
;eg: string = "batata", a=1, t=1, b=2, any other chars will be = 6 (sizeof string)
;eg: string = "done", e=1, n=1, o=2, d=3, any other chars will be = 4
;-------------------------
movzx eax,byte ptr [esi] ;read last char
mov dword ptr [edi+eax*4],1 ;its size will be one displacement, insert in bad_chars table
mov ebx,1 ;second char will be one too, third char will be 2, fourth char will be 3, ...
dec esi
dec ecx
mov edx,subLngth
.while ecx != 0 ;while exist chars in substring
movzx eax,byte ptr [esi] ;read that char
.if dword ptr [edi+eax*4] == edx ;actual char have a sizeof subLngth?
mov dword ptr [edi+eax*4],ebx ;yes, so overwrite this char displacement substring in lookup table
inc ebx ;increase displacement
.endif
dec esi
dec ecx
.endw

mov esi,lpSubStr
mov edi,lpSource
mov eax,startpos
add edi,eax ;edi=lPSource+startpos
mov ebx,srcLngth
add ebx,lpSource ;ebx=lpSource+srcLngth

try_again:
.if edi >= ebx ;we reach end of source?, exit
mov eax,-1
ret
.endif

mov ecx,subLngth
@@:
movzx eax,byte ptr [edi+ecx-1] ;read one char from source
.if byte ptr [esi+ecx-1] == al ;is this char equal to string char?
dec ecx ;yes, so, sizeof string = sizeof string -1
jnz @B ;repeat
mov eax,edi ;found string in text
sub eax,lpSource ;calculate position
ret ;return to caller
.else ;no, this char in source is not equal to string char
mov eax,dword ptr [bad_chars+eax*4] ;but this char it's a good char? This char exist in string chars?
.if eax != subLngth ;yes
add edi,eax ;so, align string to next position and try again
jmp try_again
.else ;no, actual char do not exist in string, we "should" add sizeof string displacement or less
;but actual char does not mean previous equal chars comparisions
add edi,ecx ;so, align string to next position and try again
jmp try_again
.endif
.endif

ret
Boyer_Moore endp

end start


[mineiro]

Follow 2 codes, first was optimized in logic and code. Second was optimized in fact that lookup table does not need be created at each call to BM procedure, only in first call that table will be created and sucessive calls will skip table creation.
Now code prints position, and second version print ocurrences found:

Code Select Expand


;version 0.01
;ML.EXE /c /coff /Cp main2.asm
;LINK.EXE /SUBSYSTEM:CONSOLE main2.obj
;main

include \masm32\include\masm32rt.inc
.686
Boyer_Moore PROTO :dword,:dword,:dword,:dword,:dword
printf proto C :dword, :vararg          ; msvcrt
.data
format_string db "%d",13,10,0


file db "\masm32\include\windows.inc",0
string db "Duplicate"

align 4
Text_test db 'xx includix'
String_test db 'did'

.code
start:

;-----------------------------------
    call main ;will search for string "Duplicate" in file \masm32\include\windows.inc
;-----------------------------------
;if you want to check specific cases, comment call above and uncoment line below to Text_test and String_test cases
;    invoke Boyer_Moore,0,addr Text_test,sizeof Text_test,addr String_test,sizeof String_test
;-----------------------------------
    invoke ExitProcess,eax


main proc uses esi edi ebx

LOCAL plc:DWORD ;cmd line pointer
LOCAL saida:DWORD ;output handle
LOCAL manipulador_arquivo:dword ;file handle
LOCAL tamanho:DWORD ;source file size
LOCAL mapeado:DWORD ;ptr source file
LOCAL mem_aloc:DWORD ;ptr mem alloc
LOCAL nada:dword
LOCAL arq_mape:DWORD ;mapped file handle
LOCAL pos:DWORD ;initial position
LOCAL return_value:DWORD ;return result in eax register

invoke GetStdHandle,STD_OUTPUT_HANDLE
mov saida,eax

invoke GetCommandLine
mov plc,eax

invoke CreateFile,addr file,GENERIC_READ,0,0,OPEN_EXISTING,FILE_FLAG_SEQUENTIAL_SCAN,0 ;open source file
mov manipulador_arquivo,eax ;handle

invoke GetFileSize, manipulador_arquivo,NULL ;sizeof source file
mov tamanho,eax
invoke CreateFileMapping,manipulador_arquivo,NULL,PAGE_READONLY,0,0,0 ;mapped file handle
mov arq_mape,eax

invoke MapViewOfFile,eax,FILE_MAP_READ,0,0,0 ;map it, file contents pointer
mov mapeado,eax
invoke CloseHandle,manipulador_arquivo ;don't need this anymore


mov pos,0
@@:
invoke Boyer_Moore,pos,mapeado,tamanho,addr string,sizeof string
mov return_value,eax
invoke printf,addr format_string,return_value
.if return_value == -1
jmp done
.elseif return_value == -2
jmp done
.else
inc return_value
m2m pos,return_value
jmp @B
.endif

done:
invoke UnmapViewOfFile,mapeado

mov eax,return_value
    ret
main endp


Boyer_Moore proc uses ebx esi edi startpos:dword,lpSource:dword,srcLngth:dword,lpSubStr:dword,subLngth:dword
LOCAL bad_chars[256]:dword

lea edi,bad_chars ;create a lookup table filled with substring size
mov ecx,256
mov eax,subLngth
rep stosd

lea edi,bad_chars
mov esi,lpSubStr
mov ecx,subLngth
add esi,subLngth
dec esi ;point to last char of substring, zero index based

;-------------------------
;eg: string = "batata", a=1, t=1, b=5, any other chars will be = 6 (sizeof string)
;eg: string = "done", e=1, n=1, o=2, d=3, any other chars will be = 4
;-------------------------
movzx eax,byte ptr [esi] ;read last char
mov dword ptr [edi+eax*4],1 ;its size will be one displacement, insert in bad_chars table
mov ebx,1 ;second char will be one too, third char will be 2, fourth char will be 3, ...
dec esi
dec ecx
mov edx,subLngth
.while ecx != 0 ;while exist chars in substring
movzx eax,byte ptr [esi] ;read that char


.if dword ptr [edi+eax*4] == edx ;actual char have a sizeof subLngth?
mov dword ptr [edi+eax*4],ebx ;yes, so overwrite this char displacement substring in lookup table
              inc ebx ;increase displacement   ;<<<<<
.endif

dec esi
dec ecx
.endw

;------------------------------
mov eax,-2 ;assume error in parameters data
mov esi,lpSubStr
mov edi,lpSource
mov ebx,srcLngth
mov ecx,subLngth

test ebx,ebx
jz done
test ecx,ecx
jz done
cmp ecx,ebx
ja done

add ebx,edi ;ebx=lpSource+srcLngth
add edi,startpos ;edi=lpSource+startpos

mov edx,subLngth
align 4
try_again:
mov eax,-1
cmp ebx,edi
jbe done
mov ecx,edx
@@:
movzx eax,byte ptr [edi+ecx-1] ;read one char from source
cmp byte ptr [esi+ecx-1],al
jne @F
dec ecx
jnz @B
sub edi,lpSource
mov eax,edi
jmp done
@@:
mov eax,dword ptr [bad_chars+eax*4]
cmp eax,edx ;cmp eax,edx
cmove eax,ecx
add edi,eax
jmp try_again

align 4
done:
ret

Boyer_Moore endp

end start


--------------------------------------

Code Select Expand


;version 0.02
;ML.EXE /c /coff /Cp main.asm
;LINK.EXE /SUBSYSTEM:CONSOLE main.obj
;main

include \masm32\include\masm32rt.inc
.686
Boyer_Moore PROTO :dword,:dword,:dword,:dword,:dword,:dword
printf proto C :dword, :vararg          ; msvcrt

.data
format_string db "pos: %d",13,10,0
occurrences db "found %d ocurrence(s)",13,10,0


file db "\masm32\include\windows.inc",0
string db "Duplicate"

align 4
Text_test db 'xx includix'
String_test db 'did'

.data?
bad_chars dd 256 dup (?)

.code
start:
;-----------------------------------
    call main ;will search for string "Duplicate" in file \masm32\include\windows.inc
;-----------------------------------
;if you want to check specific cases, comment call above and uncoment lines below to Text_test and String_test cases
;    invoke Boyer_Moore,0,addr Text_test,sizeof Text_test,addr String_test,sizeof String_test,0
;    push eax
; invoke printf,addr format_string,eax
; pop eax   
;-----------------------------------
    invoke ExitProcess,eax


main proc uses esi edi ebx

LOCAL plc:DWORD ;cmd line pointer
LOCAL saida:DWORD ;output handle
LOCAL manipulador_arquivo:dword ;file handle
LOCAL tamanho:DWORD ;source file size
LOCAL mapeado:DWORD ;ptr source file
LOCAL mem_aloc:DWORD ;ptr mem alloc
LOCAL nada:dword
LOCAL arq_mape:DWORD ;mapped file handle
LOCAL pos:DWORD ;initial position
LOCAL return_value:DWORD ;return result in eax register
LOCAL first_r:DWORD

invoke GetStdHandle,STD_OUTPUT_HANDLE
mov saida,eax

invoke GetCommandLine
mov plc,eax

invoke CreateFile,addr file,GENERIC_READ,0,0,OPEN_EXISTING,FILE_FLAG_SEQUENTIAL_SCAN,0 ;open source file
mov manipulador_arquivo,eax ;handle

invoke GetFileSize, manipulador_arquivo,NULL ;sizeof source file
mov tamanho,eax
invoke CreateFileMapping,manipulador_arquivo,NULL,PAGE_READONLY,0,0,0 ;mapped file handle
mov arq_mape,eax

invoke MapViewOfFile,eax,FILE_MAP_READ,0,0,0 ;map it, file contents pointer
mov mapeado,eax
invoke CloseHandle,manipulador_arquivo ;don't need this anymore


mov pos,0
mov first_r,0 ;inserted one more parameter to Boyer_Moore procedure
;if first_run is zero, so table creation is done
;if first_run is not zero, so table creation is skipped, gaining time execution
;so, table bad_chars was moved to data section to be globally accessed
@@:
invoke Boyer_Moore,pos,mapeado,tamanho,addr string,sizeof string,first_r
mov return_value,eax
.if return_value == -1
jmp done
.elseif return_value == -2
jmp done
.else
invoke printf,addr format_string,return_value
inc return_value
m2m pos,return_value
inc first_r ;this is a occurrences count, and will trigger to not recreate lookup table
jmp @B
.endif

done:
invoke UnmapViewOfFile,mapeado

invoke printf,addr occurrences,first_r
mov eax,return_value
    ret
main endp


Boyer_Moore proc uses ebx esi edi startpos:dword,lpSource:dword,srcLngth:dword,lpSubStr:dword,subLngth:dword,first_run:dword

cmp first_run,0
jnz @F
lea edi,bad_chars ;create a lookup table filled with substring size
mov ecx,256
mov eax,subLngth
rep stosd

lea edi,bad_chars
mov esi,lpSubStr
mov ecx,subLngth
add esi,subLngth
dec esi ;point to last char of substring, zero index based

;-------------------------
;eg: string = "batata", a=1, t=1, b=5, any other chars will be = 6 (sizeof string)
;eg: string = "done", e=1, n=1, o=2, d=3, any other chars will be = 4
;-------------------------
movzx eax,byte ptr [esi] ;read last char
mov dword ptr [edi+eax*4],1 ;its size will be one displacement, insert in bad_chars table
mov ebx,1 ;second char will be one too, third char will be 2, fourth char will be 3, ...
dec esi
dec ecx
mov edx,subLngth
.while ecx != 0 ;while exist chars in substring
movzx eax,byte ptr [esi] ;read that char


.if dword ptr [edi+eax*4] == edx ;actual char have a sizeof subLngth?
mov dword ptr [edi+eax*4],ebx ;yes, so overwrite this char displacement substring in lookup table
        inc ebx ;increase displacement
.endif

dec esi
dec ecx
.endw

;------------------------------
@@:
mov eax,-2 ;assume error in parameters data
mov esi,lpSubStr
mov edi,lpSource
mov ebx,srcLngth
mov ecx,subLngth

test ebx,ebx
jz done
test ecx,ecx
jz done
cmp ecx,ebx
ja done

add ebx,edi ;ebx=lpSource+srcLngth
add edi,startpos ;edi=lpSource+startpos

mov edx,subLngth
align 4
try_again:
mov eax,-1
cmp ebx,edi
jbe done
mov ecx,edx
@@:
movzx eax,byte ptr [edi+ecx-1] ;read one char from source
cmp byte ptr [esi+ecx-1],al
jne @F
dec ecx
jnz @B
sub edi,lpSource
mov eax,edi
jmp done
@@:
mov eax,dword ptr [bad_chars+eax*4]
cmp eax,edx ;test eax,edx
cmove eax,ecx
add edi,eax
jmp try_again

align 4
done:
ret

Boyer_Moore endp

end start



Code can be optimized more, but I need travel tomorrow, so, ... .
---edited---
Corrected code. First fault was optimization used "test" instead of "cmp", second was a logic problem.