【老刘谈算法001】这位运算玩的真溜—strlen函数的汇编实现分析
本帖最后由 老刘 于 2018-6-28 12:48 编辑新手刷下存在感，大佬们见笑了，轻喷
首先挂下代码，
;原函数作者为Agner Fog，出处为MASM32开发包，在此表示感谢。
;中文注释修改&添加 By 老刘。
.486
.model flat, stdcall
option casemap :none
.code
OPTION PROLOGUE:NONE
OPTION EPILOGUE:NONE
align 4
StrLen proc item:DWORD
mov eax, ;获得参数item，即字符串指针
lea edx, ;edx=指针+3
push ebp ;备份ebp edi
push edi
mov ebp, 80808080h
@@:
REPEAT 3
mov edi, ;edi=读4个字节
add eax, 4 ;字符串指针指到下4个字节起始，即+4
lea ecx, ;ecx=四字节每个字节-1
not edi ;edi=四字节逻辑取反
and ecx, edi ;ecx=取反后的每个字节和没取反后-1的每个字节进行逻辑与
and ecx, ebp ;判断每个字节的二进制第8位是否为1，为1则说明原字节=0
jnz nxt ;如果出现了一个null异端，跳到nxt继续判断
ENDM
mov edi, ;和上面的一样
add eax, 4
lea ecx,
not edi
and ecx, edi
and ecx, ebp
jz @B ;如果没有异端，回去上面循环，有的话都不用跳了，下面就是nxt
nxt:
test ecx, 00008080h ;测试null是否在前2个字节中
jnz @F
shr ecx, 16 ;不在前2字节，ecx右移16个二进制位，即右移2字节，使原来的第3、4字节移位到1、2字节处。
add eax, 2 ;字符串指针+2
@@:
shl cl, 1 ;第一个字节逻辑左移1位，如果第一个字节为Null，则CF=1，否则即说明第二个字节为Null
sbb eax, edx ;eax=eax-edx-CF=eax-(item+3)-CF=字符串长度
pop edi
pop ebp
ret 4
StrLen endp
OPTION PROLOGUE:PrologueDef
OPTION EPILOGUE:EpilogueDef
end
作者的底层知识非常牢固，位运算运用的炉火纯青，
代码算不上精简，但非常高效，
为了达到上述目的，其代码人类直接不好理解，让我们将几处难理解的地方细细分析道来。
一、高效 —— 一次判断4个字节
对应Line25~~42，
这段代码运用位运算，在寄存器中一次性判断4个Byte内有无Null。
我们按一个字节进行分析，用数学语言转换代码，下述的十进制数均为UByte类型。
令a=该Byte的无符号值，
令f(x)为逻辑非运算的对应函数，
有f(x)=255-x
b=a-1
此时因为溢出，有b=a-1（a∈）或b=255（a=0)
我们将其设为函数，有b=g(a)
c=f(a)
d=b and c
进行逻辑与运算时，结果总是不大于两个进行运算的数
所以有d<=b和c中较小的那一个
易得a∈时，d<=g(a)，此时g(a)max=g(127)=126，
a∈时，d<=f(a)，f(a)max=f(128)=127，
a=0时，d = 255 and 255 = 255，
e=d and 0x80
a∈时，d<=126，此时∵d的第8二进制位上定为0，e=0
同理，a∈，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个长度
不过对于一个用英文编程的老外来说，也可以理解，
代码质量可以说是很高了，只是让分析它的人非常蛋痛(ˉ▽ˉ；)…
可能这就是“最高效率和可读性不可兼得”吧！ 本帖最后由 老刘 于 2018-6-27 17:30 编辑
yikuaidao 发表于 2018-6-27 15:54
请使用不同位数的cpu运算比较一下运算效率(字符串随机生成)
主要是比较4字节判断和1字节判断,哪种效率高
本来想做长字串验证，800K的文本切割成100byte的，但masm连100个byte长的变量都不能搞，真是服
所以就做的短字串多次求长，一亿次，
结果如下（i3）
C:\masm32\_test>(
More? cscript -nologo %windir%\ElapsedTime.VBS C:\masm32\_test\test2.exe
More? cscript -nologo %windir%\ElapsedTime.VBS C:\masm32\_test\test2.exe
More? cscript -nologo %windir%\ElapsedTime.VBS C:\masm32\_test\test2.exe
More? )
4.8515625
4.8671875
4.80859375
C:\masm32\_test>(
More? cscript -nologo %windir%\ElapsedTime.VBS C:\masm32\_test\test.exe
More? cscript -nologo %windir%\ElapsedTime.VBS C:\masm32\_test\test.exe
More? cscript -nologo %windir%\ElapsedTime.VBS C:\masm32\_test\test.exe
More? )
2.1171875
2.13671875
2.42578125
C:\masm32\_test>
test.asm
Include masm32rt.inc
.code
start:
mov ecx,100000000
@@:
push ecx
mov eax,cfm$("Hello,World.")
Invoke StrLen,EAX
pop ecx
dec ecx
cmp ecx,0
jne @B
Invoke ExitProcess,NULL
end start
test2.asm
Include masm32rt.inc
.code
StrLen2 proc item:DWORD
push ecx
xor ecx,ecx
mov eax,item
@@:
mov cl,byte ptr
inc eax
jcxz @F
jmp @B
@@:
dec eax
sub eax,item
pop ecx
ret 4
StrLen2 endp
start:
mov ecx,100000000
@@:
mov eax,cfm$("Hello,World.")
Invoke StrLen2,EAX
dec ecx
cmp ecx,0
jne @B
Invoke ExitProcess,NULL
end start
哈哈，我想这已经可以说明一些问题了 welcome7758521 发表于 2018-6-27 14:19
收听大佬了，希望大佬讲的细节和延伸知识也可以说一下。
哈哈，同为初学，
第一次写这样的文章，原来写的篇幅较长，又觉得自己比较啰嗦，就改短了，
位运算，大端小端，指针这些算是基础知识吧，就没有细说，
对照着王爽老师的书看看应该还是很好理解的吧 看不懂但是觉得很牛逼系列. 汇编无非就是转移跳转出栈压栈等，哈哈 收听大佬了，希望大佬讲的细节和延伸知识也可以说一下。 汇编很不好看，有的还看不懂。 大佬还在看雪上发:Dweeqw lyliucn 发表于 2018-6-27 14:28
汇编很不好看，有的还看不懂。
为了效率丢掉可读性系列，
原来我觉得这函数挺简单的，
被他搞这么复杂，蛋疼T_T gxkyrftx 发表于 2018-6-27 14:35
大佬还在看雪上发
不敢不敢，同为初学
看来俩论坛自带联通蛤 学习了，感谢