首页
社区
课程
招聘
[原创]【老刘谈算法001】这位运算玩的真溜—strlen函数的汇编实现分析
发表于: 2018-6-27 14:08 10371

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

2018-6-27 14:08
10371
首先挂下代码,
;原函数作者为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, [esp+4]            ;获得参数item,即字符串指针
    lea     edx, [eax+3]            ;edx=指针+3
    push    ebp                     ;备份ebp edi
    push    edi
    mov     ebp, 80808080h
 
  @@:     
  REPEAT 3
    mov     edi, [eax]              ;edi=读4个字节
    add     eax, 4                  ;字符串指针指到下4个字节起始,即+4
    lea     ecx, [edi-01010101h]    ;ecx=四字节每个字节-1
    not     edi                     ;edi=四字节逻辑取反
    and     ecx, edi                ;ecx=取反后的每个字节和没取反后-1的每个字节进行逻辑与
    and     ecx, ebp                ;判断每个字节的二进制第8位是否为1,为1则说明原字节=0
    jnz     nxt                     ;如果出现了一个null异端,跳到nxt继续判断
  ENDM
 
    mov     edi, [eax]              ;和上面的一样
    add     eax, 4                  
    lea     ecx, [edi-01010101h]    
    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∈[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个长度
不过对于一个用英文编程的老外来说,也可以理解,
代码质量可以说是很高了,只是让分析它的人非常蛋痛(ˉ▽ˉ;)…
可能这就是“最高效率和可读性不可兼得”吧!

[注意]传递专业知识、拓宽行业人脉——看雪讲师团队等你加入!

最后于 2018-6-28 12:47 被老刘NoOne编辑 ,原因: 找到代码原作者了
收藏
免费 1
支持
分享
打赏 + 1.00雪花
打赏次数 1 雪花 + 1.00
 
赞赏  junkboy   +1.00 2018/06/27
最新回复 (7)
雪    币: 171
活跃值: (519)
能力值: ( LV4,RANK:50 )
在线值:
发帖
回帖
粉丝
2
这是要出系列的节奏啊,顶一个!!!
2018-6-27 20:39
0
雪    币: 11716
活跃值: (133)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
3
等待002
2018-6-27 20:59
0
雪    币: 2359
活跃值: (528)
能力值: ( LV4,RANK:50 )
在线值:
发帖
回帖
粉丝
4
Lthis 这是要出系列的节奏啊,顶一个!!!
哈哈,主要是想分析一下这些masm32带的函数和宏,据罗老师说很有研究价值,正好提前锻炼一下阅读汇编代码的能力,权当为逆向打基础了
2018-6-27 22:18
0
雪    币: 2359
活跃值: (528)
能力值: ( LV4,RANK:50 )
在线值:
发帖
回帖
粉丝
5
junkboy 等待002
感谢支持!
2018-6-27 22:19
0
雪    币: 2359
活跃值: (528)
能力值: ( LV4,RANK:50 )
在线值:
发帖
回帖
粉丝
6
附一个效率比较:https://www.52pojie.cn/forum.php?mod=redirect&goto=findpost&ptid=758048&pid=20666371
最后于 2018-6-27 22:26 被老刘NoOne编辑 ,原因: 超链接忘加了
2018-6-27 22:25
0
雪    币: 6
活跃值: (3290)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
7
老刘NoOne 附一个效率比较:https://www.52pojie.cn/forum.php?mod=redirect&amp;goto=findpost&amp;ptid=758048& ...
首先,逐字节比较0,代码应该不超过10行,效率应该更高。
最主要你这代码是一次读4字节,有可能会跨页,造成缺页异常呢????????????
最后于 2019-3-4 21:04 被咖啡_741298编辑 ,原因:
2019-3-4 20:57
0
雪    币: 2359
活跃值: (528)
能力值: ( LV4,RANK:50 )
在线值:
发帖
回帖
粉丝
8
咖啡_741298 老刘NoOne 附一个效率比较:https://www.52pojie.cn/forum.php?mod=redirect&amp;amp;goto= ...
感谢提醒,跨页这个确实没考虑到,
不过x86下,cpu对4字节的读取储存速度是最快的,对4字节整数倍的内存地址读取储存也是最快的,这些在代码中都有优化到(如align 4),快慢也不能单用执行的语句数来衡量,
其实大多数情况下,如果已知一段内存空间的大小,而且除了字符串外其它数据为0时,用二分检索法应该会更好些。
欢迎测试速度,若有更好方案也请不吝赐教
2019-3-5 12:01
0
游客
登录 | 注册 方可回帖
返回
//