【老刘谈算法001】这位运算玩的真溜—strlen函数的汇编实现分析

OldLiu

首先挂下代码，

1. ;原函数作者为Agner Fog，出处为MASM32开发包，在此表示感谢。
   
2. ;中文注释修改&添加 By 老刘。
   
3. 
   
4. 
   
5.     .486
   
6.     .model flat, stdcall
   
7.     option casemap :none
   
8. 
   
9.     .code
   
10. 
    
11. 
    
12. OPTION PROLOGUE:NONE
    
13. OPTION EPILOGUE:NONE
    
14. 
    
15. align 4
    
16. 
    
17. StrLen proc item:DWORD
    
18. 
    
19.     mov     eax, [esp+4]            ;获得参数item，即字符串指针
    
20.     lea     edx, [eax+3]            ;edx=指针+3
    
21.     push    ebp                                                ;备份ebp edi
    
22.     push    edi
    
23.     mov     ebp, 80808080h
    
24. 
    
25.   @@:     
    
26.   REPEAT 3
    
27.     mov     edi, [eax]              ;edi=读4个字节
    
28.     add     eax, 4                  ;字符串指针指到下4个字节起始，即+4
    
29.     lea     ecx, [edi-01010101h]    ;ecx=四字节每个字节-1
    
30.     not     edi                     ;edi=四字节逻辑取反
    
31.     and     ecx, edi                ;ecx=取反后的每个字节和没取反后-1的每个字节进行逻辑与
    
32.     and     ecx, ebp                                ;判断每个字节的二进制第8位是否为1，为1则说明原字节=0
    
33.     jnz     nxt                                                ;如果出现了一个null异端，跳到nxt继续判断
    
34.   ENDM
    
35. 
    
36.     mov     edi, [eax]              ;和上面的一样
    
37.     add     eax, 4                  
    
38.     lea     ecx, [edi-01010101h]   
    
39.     not     edi                     
    
40.     and     ecx, edi               
    
41.     and     ecx, ebp
    
42.     jz      @B                      ;如果没有异端，回去上面循环，有的话都不用跳了，下面就是nxt
    
43. 
    
44.   nxt:
    
45.     test    ecx, 00008080h          ;测试null是否在前2个字节中
    
46.     jnz     @F
    
47.     shr     ecx, 16                 ;不在前2字节，ecx右移16个二进制位，即右移2字节，使原来的第3、4字节移位到1、2字节处。
    
48.     add     eax, 2                                        ;字符串指针+2
    
49.   @@:
    
50.     shl     cl, 1                   ;第一个字节逻辑左移1位，如果第一个字节为Null，则CF=1，否则即说明第二个字节为Null
    
51.     sbb     eax, edx                ;eax=eax-edx-CF=eax-(item+3)-CF=字符串长度
    
52.     pop     edi
    
53.     pop     ebp
    
54. 
    
55.     ret     4
    
56. 
    
57. StrLen endp
    
58. 
    
59. OPTION PROLOGUE:PrologueDef
    
60. OPTION EPILOGUE:EpilogueDef
    
61. 
    
62. 
    
63. end

复制代码

作者的底层知识非常牢固，位运算运用的炉火纯青，
代码算不上精简，但非常高效，
为了达到上述目的，其代码人类直接不好理解，让我们将几处难理解的地方细细分析道来。

**一、高效 —— 一次判断4个字节**
对应Line25~~42，
这段代码运用位运算，在寄存器中一次性判断4个Byte内有无Null。
我们按一个字节进行分析，用数学语言转换代码，下述的十进制数均为UByte类型。
令a=该Byte的无符号值，
令f(x)为逻辑非运算的对应函数，
有f(x)=255-x
b=a-1
此时因为溢出，有b=a-1（a∈[1,255]）或b=255（a=0)
我们将其设为函数，有b=g(a)
c=f(a)
d=b and c
进行逻辑与运算时，结果总是不大于两个进行运算的数
所以有d<=b和c中较小的那一个
易得a∈[1,127]时，d<=g(a)，此时g(a)max=g(127)=126，
a∈[128,255]时，d<=f(a)，f(a)max=f(128)=127，
a=0时，d = 255 and 255 = 255，
e=d and 0x80
a∈[1,127]时，d<=126，此时∵d的第8二进制位上定为0，e=0
同理，a∈[128,255]，e=0
a=0，e=0x80
即a不为0时，e=0，a为0时，e=0x80。

**二、拒绝浪费寄存器——字符串长度的最终计算**
对应Line:20、28、37、48、50、51
作者读取完需判断的字节后，不管3721，先将指针+4（28、37行）
这方便了再次循环，简化了代码，
在48行将指针+2，
50行时令CF=指针所指字节第8位
51行则是最终计算，
由一可知，当Byte为null时，判断下来第8二进制位=1
即当指针所指字节不为null，CF=1
51行得到的结果=当前指针-字符串起始指针-3-1
当Byte不为null时，由其他语句得知下一个byte肯定为null，
此时第8二进制位=0，CF=0
51行得到的结果则少减了1，正好对应真实的字符串长度。
这位老外是真的秀，在追求高效率的时候还不忘精简一波代码~

该代码还有局限性，当出现双字节字符时就会判断成2个长度
不过对于一个用英文编程的老外来说，也可以理解，
代码质量可以说是很高了，只是让分析它的人非常蛋痛(ˉ▽ˉ；)...
可能这就是“最高效率和可读性不可兼得”吧！