【老刘谈算法002】反向快速比较——instring函数的汇编实现分析

OldLiu

挂下代码先，

1. ;注释修改&中文注释添加 by 老刘
   
2. 
   
3. ; #########################################################################
   
4. 
   
5. ;       这个算法的子循环代码被EKO重新设计来反向执行比较，
   
6. ;       这种比较方法通过分支比较减少了需要执行的指令数。
   
7. 
   
8. ; #########################################################################
   
9. 
   
10.     .486
    
11.     .model flat, stdcall  ; 32 bit memory model
    
12.     option casemap :none  ; case sensitive
    
13. 
    
14.     StrLen PROTO :DWORD
    
15. 
    
16.     .code
    
17. 
    
18. ; ########################################################################
    
19. 
    
20. InString proc startpos:DWORD,lpSource:DWORD,lpPattern:DWORD
    
21. 
    
22.   ; ------------------------------------------------------------------
    
23.   ; InString函数在一个更大的“源字符串”中寻找“匹配字符串”，
    
24.   ; 如果找到了的话，“匹配字符串”在“源字符串”的位置会被放在eax中。
    
25.   ;
    
26.   ; "StartPos"即“起始位”参数和返回值均使用1来作为首个字符的索引。
    
27.   ; （第一个字符是1，第二个字符是2，等等……）
    
28.   ;
    
29.   ;
    
30.   ; 返回值：
    
31.   ; 如果函数执行成功，它将会返回“源字符串”的位置。
    
32.   ;  0 = 没找着
    
33.   ; -1 = “匹配字符串”的长度不短于“源字符串”
    
34.   ; -2 = "StartPos"参数越界。
    
35.   ; ------------------------------------------------------------------
    
36. 
    
37.     LOCAL sLen:DWORD
    
38.     LOCAL pLen:DWORD
    
39. 
    
40.     push ebx
    
41.     push esi
    
42.     push edi
    
43. 
    
44.     invoke StrLen,lpSource
    
45.     mov sLen, eax           ;源字符串长度
    
46.     invoke StrLen,lpPattern
    
47.     mov pLen, eax           ;匹配字符串长度
    
48. 
    
49.     cmp startpos, 1
    
50.     jge @F
    
51.     mov eax, -2
    
52.     jmp isOut               ;如果“起始位”参数为0则退出。
    
53.   @@:
    
54. 
    
55.     dec startpos            ;改成0为第一个字符的索引。
    
56. 
    
57.     cmp  eax, sLen                        ;这里的eax依旧=pLen
    
58.     jl @F
    
59.     mov eax, -1
    
60.     jmp isOut               ;匹配字符串不短于源字符串，退出。
    
61.   @@:
    
62. 
    
63.     sub sLen, eax           ;sLen-=pLen源字符串去尾
    
64.     inc sLen
    
65. 
    
66.     mov ecx, sLen
    
67.     cmp ecx, startpos
    
68.     jg @F
    
69.     mov eax, -2
    
70.     jmp isOut               ;不可能匹配上，退出
    
71.   @@:
    
72. 
    
73.   ; ----------------
    
74.   ; setup loop code
    
75.   ; ----------------
    
76.     mov esi, lpSource
    
77.     mov edi, lpPattern
    
78.     mov al, [edi]           ;al=匹配字符串中的第一个字符
    
79. 
    
80.     add esi, ecx            ;源字符串地址加上源字符串长（使esi指向源字符串末尾，以便倒序比较）
    
81.     neg ecx                 ;ecx=-ecx
    
82.     add ecx, startpos       ;加上起始位参数
    
83. 
    
84.     jmp Scan_Loop
    
85. 
    
86.     align 16                ;使下条指令的地址从0x10倍数处开始，提升速度
    
87. 
    
88.   ; @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
    
89. 
    
90.   Pre_Scan:
    
91.     inc ecx
    
92. 
    
93.   Scan_Loop:
    
94.     cmp al, [esi+ecx]       ;判断esi+ecx指向的第一个字符是否=匹配字符串中的第一个字符
    
95.     je Pre_Match            ;如果匹配，则跳到Pre_Match继续判断
    
96.     inc ecx
    
97.     js Scan_Loop            ;ecx为负时继续循环
    
98. 
    
99.     jmp No_Match
    
100. 
     
101.   Pre_Match:
     
102.     lea ebx, [esi+ecx]      ;ebx=第一个匹配的字符的地址
     
103.     mov edx, pLen
     
104. 
     
105.   Test_Match:
     
106.     mov ah, [ebx+edx-1]     ;ah=ebx+edx-1指向的字符
     
107.     cmp ah, [edi+edx-1]     ;与匹配字符串中对应的字符比较
     
108.     jne Pre_Scan            ;不匹配，跳到Pre_Scan
     
109.     dec edx
     
110.     jnz Test_Match          ;edx非0时继续倒序循环判断
     
111. 
     
112.   ; @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
     
113. 
     
114.   Match:
     
115.     add ecx, sLen
     
116.     mov eax, ecx
     
117.     inc eax
     
118.     jmp isOut
     
119.    
     
120.   No_Match:
     
121.     xor eax, eax
     
122. 
     
123.   isOut:
     
124.     pop edi
     
125.     pop esi
     
126.     pop ebx
     
127. 
     
128.     ret
     
129. 
     
130. InString endp
     
131. 
     
132. ; ########################################################################
     
133. 
     
134.     end

复制代码

那么什么条件下可以直接判断不可能匹配呢？
我们设
a=startpos
b=sLen
c=pLen
令d=b-(a-1)
则d即为实际需要进行查找的字符串的长度，
那么当被查找的字符串长小于需要查找的字符串长度的时候，即
当(a-1)+c>b的时候，
显然不可能匹配上，
作者可谓考虑的十分周到了。