别人家的 strlen

RIXO

今天看反汇编发现了一个奇怪的函数，然后百度后了解了一下原理，转载一下文章

原文参考链接
原文的帖子


　　　　【原创性声明】在调试到strlen的汇编代码时，我发现其汇编代码略显“古怪”，当时并未有精力去关注，在研究过后重新查看了strlen的汇编代码。对strlen的原理解释并非原创，而是参考了《strlen源码剖析》一文的解释，在理解后感觉有必要写此文记之。



　　　　首先我们创建一个测试项目，来比较以下我们自己用常规方法写的的strlen函数和<string.h> 中的strlen的时间消耗水平，这里我用 GetTickCount（）做一个初步的估算（并不精确），测试代码如下：

1. strlen时间消耗测试
   
2. 
   
3. Code highlighting produced by Actipro CodeHighlighter (freeware)http://www.CodeHighlighter.com/-->#include "stdafx.h"
   
4. #include <stdlib.h>
   
5. #include <stdio.h>
   
6. #include <string.h>
   
7. #include <windows.h>
   
8. 
   
9. //这是我们自己按常规算法实现的strlen，即逐个byte判断是否为0
   
10. size_t mystrlen(char* s)
    
11. {
    
12.     char* p = s;
    
13.     while(*p) ++p;
    
14.     return (p - s);
    
15. }
    
16. 
    
17. int main(int argc, char* argv[])
    
18. {
    
19.     char* s;
    
20.     size_t result, i;
    
21.     DWORD tickcount;
    
22. 
    
23.     s = (char*)malloc(4096);
    
24.     memset(s, 'a', 4096);
    
25.     s[4091] = 0;
    
26. 
    
27.     //粗略测试两种strlen的时间
    
28.     //标准库中的strlen：
    
29.     tickcount = GetTickCount();
    
30.     for(i=0; i<20000; i++)
    
31.     {
    
32.         result = strlen(s);
    
33.     }
    
34.     printf("strlen  :  %ld ms, result = %ld\n", GetTickCount() - tickcount, result);
    
35. 
    
36.     //我们自己编写的strlen：
    
37.     tickcount = GetTickCount();
    
38.     for(i=0; i<20000; i++)
    
39.     {
    
40.         result = mystrlen(s);
    
41.     }
    
42.     printf("mystrlen:  %ld ms, result = %ld\n", GetTickCount() - tickcount, result);
    
43. 
    
44.     free(s);
    
45.     return 0;
    
46. }

复制代码

　　　　该测试的输出结果如下：

　　　　strlen  :  16 ms, result = 4091
　　　　mystrlen:  218 ms, result = 4091



　　　　首先毫无疑问两种方法的时间复杂度相同（O（n）），区别在于常数系数不同，在这里我们自己写的函数的时间消耗大约是标准库版本的 13 倍之多。下面我们可以分别看下两个版本的汇编代码。



　　　　首先是我们自己编写的mystrlen版本，编译器产生的汇编代码如下：

1. 代码
   
2. 
   
3. Code highlighting produced by Actipro CodeHighlighter (freeware)http://www.CodeHighlighter.com/-->
   
4. .text:00401020 mystrlen        proc near
   
5. .text:00401020
   
6. .text:00401020 var_44          = dword ptr -44h
   
7. .text:00401020 var_4           = dword ptr -4
   
8. .text:00401020 arg_0           = dword ptr  8
   
9. .text:00401020
   
10. .text:00401020                 push    ebp
    
11. .text:00401021                 mov     ebp, esp
    
12. .text:00401023                 sub     esp, 44h
    
13. .text:00401026                 push    ebx
    
14. .text:00401027                 push    esi
    
15. .text:00401028                 push    edi
    
16. .text:00401029                 lea     edi, [ebp+var_44]
    
17. .text:0040102C                 mov     ecx, 11h
    
18. .text:00401031                 mov     eax, 0CCCCCCCCh
    
19. .text:00401036                 rep stosd
    
20. .text:00401038                 mov     eax, [ebp+arg_0]  ;
    
21. .text:0040103B                 mov     [ebp+var_4], eax  ; char* p = s;
    
22. .text:0040103E
    
23. .text:0040103E loc_40103E:                             ;
    
24. .text:0040103E                 mov     ecx, [ebp+var_4]
    
25. .text:00401041                 movsx   edx, byte ptr [ecx] ; edx = *p;
    
26. .text:00401044                 test    edx, edx            ; if ( edx == 0 )
    
27. .text:00401046                 jz      short loc_401053    ;     break;
    
28. .text:00401048                 mov     eax, [ebp+var_4]
    
29. .text:0040104B                 add     eax, 1
    
30. .text:0040104E                 mov     [ebp+var_4], eax    ; ++p;
    
31. .text:00401051                 jmp     short loc_40103E    ;  
    
32. .text:00401053 ;
    
33. .text:00401053
    
34. .text:00401053 loc_401053:                             ; CODE XREF: mystrlen+26j
    
35. .text:00401053                 mov     eax, [ebp+var_4]     ; eax = p;
    
36. .text:00401056                 sub     eax, [ebp+arg_0]     ; return (p - s);
    
37. .text:00401059                 pop     edi
    
38. .text:0040105A                 pop     esi
    
39. .text:0040105B                 pop     ebx
    
40. .text:0040105C                 mov     esp, ebp
    
41. .text:0040105E                 pop     ebp
    
42. .text:0040105F                 retn
    
43. .text:0040105F mystrlen        endp

复制代码

　　　　很明显，我们自己编写的函数 mystrlen 是逐个 byte 去比较的。

　　　　下面我们看标准库中的strlen的汇编代码，位于VC6的如下路径：...\Microsoft Visual Studio\VC98\CRT\SRC\Intel\strlen.ASM

1. 
   
2. Code highlighting produced by Actipro CodeHighlighter (freeware)http://www.CodeHighlighter.com/-->        CODESEG
   
3. 
   
4.         public  strlen
   
5. 
   
6. strlen  proc
   
7. 
   
8.         .FPO    ( 0, 1, 0, 0, 0, 0 )
   
9. 
   
10. string  equ     [esp + 4]
    
11. 
    
12.         mov     ecx,string              ; ecx -> string
    
13.         test    ecx,3                   ; test if string is aligned on 32 bits
    
14.         je      short main_loop
    
15. 
    
16. str_misaligned:
    
17.         ; simple byte loop until string is aligned
    
18.         mov     al,byte ptr [ecx]        ; 在DWORD未对齐部分逐个字节扫描
    
19.         inc     ecx
    
20.         test    al,al
    
21.         je      short byte_3
    
22.         test    ecx,3
    
23.         jne     short str_misaligned
    
24. 
    
25.         add     eax,dword ptr 0         ; 5 byte nop to align label below
    
26. 
    
27.         align   16                      ; should be redundant
    
28. 
    
29. main_loop:
    
30.         mov     eax,dword ptr [ecx]     ; read 4 bytes, 复制四个char到eax
    
31.         mov     edx,7efefeffh           ; 魔数 0x 7efefeff
    
32.         add     edx,eax                 ; edx = 0x7efefeff + eax;
    
33.         xor     eax,-1                  ; eax = ~eax （按位取反）
    
34.         xor     eax,edx                 ; eax = ~eax ^ edx
    
35.         add     ecx,4                   ; ecx 指向到下一个 DWORD
    
36.         test    eax,81010100h           ; eax & (~0x 7efefeff), 含 0字节 吗？
    
37.         je      short main_loop
    
38.         ; found zero byte in the loop     如果当前的DWORD含0，找出其位于哪一个字节
    
39.         mov     eax,[ecx - 4]
    
40.         test    al,al                   ; is it byte 0
    
41.         je      short byte_0
    
42.         test    ah,ah                   ; is it byte 1
    
43.         je      short byte_1
    
44.         test    eax,00ff0000h           ; is it byte 2
    
45.         je      short byte_2
    
46.         test    eax,0ff000000h          ; is it byte 3
    
47.         je      short byte_3
    
48.         jmp     short main_loop         ; taken if bits 24-30 are clear and bit
    
49.                                         ; 31 is set
    
50. 
    
51.         ; 0 字节的地址减去字符串地址，即为strlen的结果。
    
52. byte_3:
    
53.         lea     eax,[ecx - 1]
    
54.         mov     ecx,string
    
55.         sub     eax,ecx
    
56.         ret
    
57. byte_2:
    
58.         lea     eax,[ecx - 2]
    
59.         mov     ecx,string
    
60.         sub     eax,ecx
    
61.         ret
    
62. byte_1:
    
63.         lea     eax,[ecx - 3]
    
64.         mov     ecx,string
    
65.         sub     eax,ecx
    
66.         ret
    
67. byte_0:
    
68.         lea     eax,[ecx - 4]
    
69.         mov     ecx,string
    
70.         sub     eax,ecx
    
71.         ret
    
72. 
    
73. strlen  endp
    
74. 
    
75.         end

复制代码

　请注意，strlen的主循环部分，是已4个char为一组作为一个DORD送到eax去检测的，因此要求必须读取DWORD时以 4 bytes 对齐，所以如果字符串地址并不对齐，则前面的1~3个char必须逐个字节检测。进入主循环的循环条件相当于以下代码：



　　　　if ((((longword + magic_bits) ^ ~longword) & ~magic_bits) != 0 )

            {

　　　　　　　　//则在这4个char中至少有一个char的值是0！

　　　　}



　　　　理解strlen代码的关键在于理解上面这个检测DWORD中含有 0 字节的条件。可以详细参考参考资料中的解释，这里我再少许重复以下：



　　　　我们把 4 个 char 取到 eax 中，然后为了检测 eax 中是否含有 0 byte，注意不能逐个判断（否则效率就和普通算法无异），而是对eax加上一个魔数，该数字的取值是：7efefeff, 写成2进制是：

                                                             <-----------------------|    ...  ...     string

         |     byte [3]    |    byte [2]     |    byte [1]     |   byte [0]      |

         |       7E          |       FE          |      FE           |       FF          |

         | 0111 1110    | 1111 1110    | 1111 1110    | 1111 1111    |



　　　　请注意上面这个数字的4个 0 的位置（holes），它们的位置是经过选取的，主要目的为了检测是否有进位。在eax和它相加后，如果eax的某个字节不为0，一定会在该字节上产生向“左侧”hole的进位，反之如果某个字节为0，则一定不会产生进位。这样相加后我们只要检测 4 个hole是否全部发生改变，如果有任何一个hole依旧为0不变，就知道当前的四个byte中必含有0，然后我们从byte[0]到byte[3]逐个探查哪一个byte为0即可。

　　　　注意，当发现含有 0 的时候，是从低位byte到高位byte的顺序去检测的，这个顺序也很重要，因为低位的byte更靠近字符串的开始位置。

　　　　上面的判断条件，是根据异或的性质，通过异或操作去找出 holes 是否发生改变，如果有任何hole在相加后未发生变化，会在计算结果中的相应位产生1，即不为0。如果所有hole都发生变化，这计算结果为0，即4个byte都不为0。



　　　　代码中的" XOR EAX -1 "； 由于 -1 的补码是 0x FFFFFFFF，和1异或的结果相当于取反( 0^1 = 1, 1^1 = 0)，即和（-1）异或相当于对该操作数取反。