【老刘谈算法002】反向快速比较——instring函数的汇编实现分析
挂下代码先，;注释修改&中文注释添加 by 老刘
; #########################################################################
; 这个算法的子循环代码被EKO重新设计来反向执行比较，
; 这种比较方法通过分支比较减少了需要执行的指令数。
; #########################################################################
.486
.model flat, stdcall; 32 bit memory model
option casemap :none; case sensitive
StrLen PROTO :DWORD
.code
; ########################################################################
InString proc startpos:DWORD,lpSource:DWORD,lpPattern:DWORD
; ------------------------------------------------------------------
; InString函数在一个更大的“源字符串”中寻找“匹配字符串”，
; 如果找到了的话，“匹配字符串”在“源字符串”的位置会被放在eax中。
;
; "StartPos"即“起始位”参数和返回值均使用1来作为首个字符的索引。
; （第一个字符是1，第二个字符是2，等等……）
;
;
; 返回值：
; 如果函数执行成功，它将会返回“源字符串”的位置。
;0 = 没找着
; -1 = “匹配字符串”的长度不短于“源字符串”
; -2 = "StartPos"参数越界。
; ------------------------------------------------------------------
LOCAL sLen:DWORD
LOCAL pLen:DWORD
push ebx
push esi
push edi
invoke StrLen,lpSource
mov sLen, eax ;源字符串长度
invoke StrLen,lpPattern
mov pLen, eax ;匹配字符串长度
cmp startpos, 1
jge @F
mov eax, -2
jmp isOut ;如果“起始位”参数为0则退出。
@@:
dec startpos ;改成0为第一个字符的索引。
cmpeax, sLen ;这里的eax依旧=pLen
jl @F
mov eax, -1
jmp isOut ;匹配字符串不短于源字符串，退出。
@@:
sub sLen, eax ;sLen-=pLen源字符串去尾
inc sLen
mov ecx, sLen
cmp ecx, startpos
jg @F
mov eax, -2
jmp isOut ;不可能匹配上，退出
@@:
; ----------------
; setup loop code
; ----------------
mov esi, lpSource
mov edi, lpPattern
mov al, ;al=匹配字符串中的第一个字符
add esi, ecx ;源字符串地址加上源字符串长（使esi指向源字符串末尾，以便倒序比较）
neg ecx ;ecx=-ecx
add ecx, startpos ;加上起始位参数
jmp Scan_Loop
align 16 ;使下条指令的地址从0x10倍数处开始，提升速度
; @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
Pre_Scan:
inc ecx
Scan_Loop:
cmp al, ;判断esi+ecx指向的第一个字符是否=匹配字符串中的第一个字符
je Pre_Match ;如果匹配，则跳到Pre_Match继续判断
inc ecx
js Scan_Loop ;ecx为负时继续循环
jmp No_Match
Pre_Match:
lea ebx, ;ebx=第一个匹配的字符的地址
mov edx, pLen
Test_Match:
mov ah, ;ah=ebx+edx-1指向的字符
cmp ah, ;与匹配字符串中对应的字符比较
jne Pre_Scan ;不匹配，跳到Pre_Scan
dec edx
jnz Test_Match ;edx非0时继续倒序循环判断
; @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
Match:
add ecx, sLen
mov eax, ecx
inc eax
jmp isOut
No_Match:
xor eax, eax
isOut:
pop edi
pop esi
pop ebx
ret
InString endp
; ########################################################################
end
那么什么条件下可以直接判断不可能匹配呢？
我们设
a=startpos
b=sLen
c=pLen
令d=b-(a-1)
则d即为实际需要进行查找的字符串的长度，
那么当被查找的字符串长小于需要查找的字符串长度的时候，即
当(a-1)+c>b的时候，
显然不可能匹配上，
作者可谓考虑的十分周到了。
页:
[1]