project:useful_code_slice:boyer_moore_algorithm [Xie Yubo‘s Wiki]

Boyer Moore 算法

说明

代码所演示的算法就是参考文献1中的“Quick Search”算法，它实际是由BM算法改进而来，只使用了“坏字符启发”策略，其它时候按“Strict Forward”算法处理，实际运算的速度相当快。

这里对上述算法进行了一个很小的改动，加入了对中英文混合，也即单字节词与双字节词混合的支持。在使用原算法找出疑似匹配串后，再确定一下是否是一个词（可以是单字节词，也可以是双字节词）的起点，如果不是，则跳过匹配串，从下一个词开始重新匹配。

源代码是由纯汇编写的，如下：

;改进型的bm匹配算法 支持中英文混合(即单字节与双字节词混合
;用nasm编译
;函数原型
;extern "C" bool sfstrstr(unsigned int td[256], const char* str1, const char* str2, char case_table[256]);
;其中:
;   td内的所有元素需在最初被初始化为0
;   casetable是一个大小写转换用的转换表，加快大小写转换的速度，需用如下的方法生成
;   for(int i = 0; i < 256; ++i) 
;      casetable[i] = tolower(i);
;
;如果匹配成功返回true(1), 否则返回false(0)
;
;[e-mail]
;
;Last Modified: 2005.10.15
 
[BITS 32]
[global sfstrstr]
 
countstrlen:
    xor eax, eax
    
    _countstrlen_loop:
    cmp [esi + eax], byte 0
    je _countstrlen_exit
    inc eax
    jmp _countstrlen_loop
 
    _countstrlen_exit:
    ret
 
lower:
    mov al, [esp + 4]
    and eax, 0xff
    add eax, [ebp + 20]
    mov al, [eax]
    mov [esp + 4], al
    ret
 
getnumcnword:
    xor eax, eax
    xor ebx, ebx
 
    _getnumcnword_loop:
    cmp ebx, [ebp - 8]
    je _getnumcnword_exit
    mov edx, [ebp + 12]
    add edx, ebx
    test [edx], byte 0x80
    jz _getnumcnword_loop_goto
    inc eax
    
    _getnumcnword_loop_goto:
    inc ebx
    jmp _getnumcnword_loop
 
    _getnumcnword_exit:
    ret
 
inittd:
    mov esi, [ebp + 16]
    mov edi, [ebp + 8]
    xor ecx, ecx
      
    _inittd_loop:
    mov eax, [ebp - 12]
    cmp ecx, eax
    jnl _inittd_exit
    mov edx, eax
    sub edx, ecx
    push dword [esi + ecx]
    call lower
    pop eax
    and eax, 0xff
    mov [edi + eax * 4], edx    
    inc ecx
    jmp _inittd_loop
    
    _inittd_exit:
    ret
 
resettd:
    mov esi, [ebp + 16]
    mov edi, [ebp + 8]
    xor ecx, ecx
      
    _resettd_loop:
    cmp ecx, [ebp - 12]
    jnl _resettd_exit
    push dword [esi + ecx]
    call lower
    pop eax
    and eax, 0xff
    mov [edi + eax * 4], dword 0
    
    inc ecx
    jmp _resettd_loop
    
    _resettd_exit:
    ret
        
sfstrstr:
    push ebp
    mov ebp, esp
    sub esp, 20
    push esi
    push edi
    
    ;;strlen(str1)
    mov esi, [ebp + 12]
    call countstrlen
    mov [ebp - 16], eax
    
    ;;strlen(str2)
    mov esi, [ebp + 16]
    call countstrlen
    mov [ebp - 12], eax
    
    call inittd
    
    mov esi, [ebp + 16]
    mov edi, [ebp + 12]
    mov [ebp - 4], dword 0
    mov [ebp - 8], dword 0
    
    _sfstrstr_loop2:
    xor ecx, ecx
    mov eax, [ebp - 8]
    add eax, [ebp - 12]
    cmp eax, [ebp - 16]
    jg  _sfstrstr_loop2_exit
    
    _sfstrstr_loop3:
    cmp ecx, [ebp - 12]
    jnl _sfstrstr_loop3_exit
    mov eax, [ebp - 8]
    add eax, ecx
    push dword [edi + eax]
    call lower
    pop ebx
    push dword [esi + ecx]
    call lower
    pop edx
    cmp bl, dl
    jne _sfstrstr_loop3_exit
    inc ecx
    jmp _sfstrstr_loop3
    
    _sfstrstr_loop3_exit:
    cmp ecx, [ebp - 12]
    jne _sfstrstr_goto1
    call getnumcnword
    test eax, 0x00000001
    jz _sfstrstr_goto3
    mov eax, [ebp - 12]
    inc eax
    add [ebp - 8], eax
    jmp _sfstrstr_loop2
 
    _sfstrstr_goto3:
    mov [ebp - 4], dword 1
    jmp _sfstrstr_loop2_exit
 
    _sfstrstr_goto1:
    mov eax, [ebp - 8]
    add eax, [ebp - 12]
    push dword [edi + eax]
    call lower
    pop eax
    and eax, 0xff
    shl eax, 2
    add eax, [ebp + 8]
    mov eax, [eax]
    cmp eax, 0
    je _sfstrstr_goto2
    add [ebp - 8], eax
    jmp _sfstrstr_loop2
 
    _sfstrstr_goto2:
    mov eax, [ebp - 12]
    inc eax
    add [ebp - 8], eax
    jmp _sfstrstr_loop2
 
    _sfstrstr_loop2_exit:
    call resettd
    mov eax, [ebp - 4]
    
    return:
    pop edi
    pop esi
    mov esp, ebp
    pop ebp
    ret

参考文献