免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
最近访问板块 发新帖
查看: 2872 | 回复: 9
打印 上一主题 下一主题

[算法] 【转】你们猜XP SP2的运行时库里的strlen怎么实现的 [复制链接]

论坛徽章:
0
跳转到指定楼层
1 [收藏(0)] [报告]
发表于 2009-07-09 15:36 |只看该作者 |倒序浏览
我一个同事的早先的帖子,今天谈论起来实在是震撼了我一把,我们现在也不知道这几个数是怎么得来的,请大家指教,谢谢:

/////////////////////////////////////////////////////////////////////原帖///////////////////////////////////////////////////////////////////////////////////

这个礼拜六做了两件事
睡觉+吃饭,我下面说的这件事一般是在睡觉的时候做的,还有一半是吃饭的时候做的,恩。开始了
周末在家很无聊,人太无聊了就会做傻事……
于是我开始逆向XP SP2的ntdll玩,突然有个很想法,闲的没事的时候把里面的函数都用C重写一遍。
本来想找个软柿子捏,我看strlen很不错嘛,又简单,闭着眼就能搞定吧。

程序的结构很简单,移指针找'\0',找到了把指针一减就OK了。
恩,我带着定势思维继续看下去。
完了晕了
.text:7C922ABB                 mov     eax, [ecx]
.text:7C922ABD                 mov     edx, 7EFEFEFFh
.text:7C922AC2                 add     edx, eax
.text:7C922AC4                 xor     eax, 0FFFFFFFFh
.text:7C922AC7                 xor     eax, edx
.text:7C922AC9                 add     ecx, 4
.text:7C922ACC                 test    eax, 81010100h
这罗里巴嗦的忙活什么呢……
屁大点事,找个'\0'还这么麻烦
头晕中……
三小时后
微软的代码果然牛X,这么简单的函数,看看人家考虑的就是周到,大公司就是大公司,大公司就是一定要把简单的事情复杂化,这样才能把复杂的事情简单化……
恩,我们看看他是怎么干的。
//.text:7C922A9D                 mov     ecx, [esp+arg_0]      字符串指针放入EXC
//.text:7C922AA1                 test    ecx, 3                     判断地址是否是4字节对齐的
//.text:7C922AA7                 jz      short loc_7C922ABB
//.text:7C922AA9
//                      不是4字节对齐的地址,一个字节一个字节的比较
//.text:7C922AA9 loc_7C922AA9:                           ; CODE XREF: _strlen+19j  
//.text:7C922AA9                 mov     al, [ecx]   
//.text:7C922AAB                 inc     ecx         
//.text:7C922AAC                 test    al, al                      判断al是不是'\0'
//.text:7C922AAE                 jz      short loc_7C922AEE   是就跳
//.text:7C922AB0                 test    ecx, 3                    是不是对齐地址?
//.text:7C922AB6                 jnz     short loc_7C922AA9   不是就继续
//.text:7C922AB8                 add     eax, 0    eax清0
//.text:7C922ABB 已经是4字节对齐的地址了,这里可以4个字节4个字节的比较了
//.text:7C922ABB loc_7C922ABB:                           ; CODE XREF: _strlen+Aj
//.text:7C922ABB                                                ; _strlen+34j ...
//.text:7C922ABB                 mov     eax, [ecx]             从字符串里读4个字节
//.text:7C922ABD                 mov     edx, 7EFEFEFFh     神奇数字~~!
//.text:7C922AC2                 add     edx, eax               
//.text:7C922AC4                 xor     eax, 0FFFFFFFFh    取反
//.text:7C922AC7                 xor     eax, edx   
//.text:7C922AC9                 add     ecx, 4
//.text:7C922ACC                 test    eax, 81010100h     另一个很神奇的数字
//.text:7C922AD1                 jz      short loc_7C922ABB  检查4字节里有没有0,没有就跳
//.text:7C922AD3                 mov     eax, [ecx-4]          有的话找出哪个是0
//.text:7C922AD6                 test    al, al
//.text:7C922AD8                 jz      short loc_7C922B0C   第一个就是
//.text:7C922ADA                 test    ah, ah
//.text:7C922ADC                 jz      short loc_7C922B02   第二个是就-3
//.text:7C922ADE                 test    eax, 0FF0000h         第三个是就-2
//.text:7C922AE3                 jz      short loc_7C922AF8
//.text:7C922AE5                 test    eax, 0FF000000h      第四个是就-1
//.text:7C922AEA                 jz      short loc_7C922AEE
//.text:7C922AEC                 jmp     short loc_7C922ABB  都不是?有没有搞错……一般来这算法如果没有问题是不会到这里的

它用了一种很神奇的算法,可以找出一个四字节中有没有'\0'。
总之,我仿照着写了一个C函数,感觉不如他们汇编写的那个好。测试了一下是OK的。
就算你知道微软的编译选项也请不要拿编译以后的代码和原来的代码比较,因为我没有那么强悍的逆向水平,呵呵就这么着吧。
我觉得原先的代码就是用汇编手写的。
这么简单的一个函数居然还考虑了字节对齐,很强悍……
[cpp]size_t __cdecl strlen(char* p)
{
char* temp;
temp = p;
long fourbyte = 0;
while (((long)p)&3 != 0) {//如果地址没有对齐
  if (*p != '\0' )
   p++;
  else
   goto exit1;
}
do {
  fourbyte = *(long*)(p);
  p+=4;
} while((((fourbyte^0xffffffff)^(fourbyte+0x7EFEFEFF))&0x81010100) == 0);
//四字节读入一个long型变量的时候是倒着放的,不要忘了
//即char a[4] = {77,78,79,80},放到一个long 里就是80797877
if (((char*)(&fourbyte))[0] == '\0') {
  goto exit4;
}
if (((char*)(&fourbyte))[1] == '\0') {
  goto exit3;
}
if (((char*)(&fourbyte))[2] == '\0') {
  goto exit2;
}
if (((char*)(&fourbyte))[3] == '\0') {
  goto exit1;
}
exit1:
return p-temp-1;
exit2:
return p-temp-2;
exit3:
return p-temp-3;
exit4:
return p-temp-4;
}[/cpp]
关于那个算法,大家来讨论一下原理吧,呵呵就当思考题了
pk8995@163.com
/////////////////////////////////////////////////////////////////////原帖end///////////////////////////////////////////////////////////////////////////////////

原帖在这里:http://www.0ginr.com/bbs/thread-1163-1-1.html

论坛徽章:
0
2 [报告]
发表于 2009-07-09 15:37 |只看该作者
汇编看得头都晕

论坛徽章:
0
3 [报告]
发表于 2009-07-09 15:42 |只看该作者
为啥要看汇编呢
这里有c语言的实现讲解
http://www.cppblog.com/ant/archive/2007/10/12/32886.html

论坛徽章:
0
4 [报告]
发表于 2009-07-09 15:44 |只看该作者
强!

论坛徽章:
0
5 [报告]
发表于 2009-07-09 16:28 |只看该作者
大惊小怪

论坛徽章:
1
双子座
日期:2015-01-04 14:25:06
6 [报告]
发表于 2009-07-09 21:22 |只看该作者
不只是XP SP2里面这么做

论坛徽章:
5
2015年辞旧岁徽章
日期:2015-03-03 16:54:152015年迎新春徽章
日期:2015-03-04 09:53:172015亚冠之水原三星
日期:2015-06-02 16:34:202015年亚冠纪念徽章
日期:2015-10-19 18:13:37程序设计版块每日发帖之星
日期:2015-11-08 06:20:00
7 [报告]
发表于 2009-07-09 21:38 |只看该作者
glibc中这样的代码很常见啊

论坛徽章:
1
2015年辞旧岁徽章
日期:2015-03-03 16:54:15
8 [报告]
发表于 2009-07-09 23:02 |只看该作者
完全看不懂,膜拜中……

论坛徽章:
1
技术图书徽章
日期:2014-03-06 15:32:30
9 [报告]
发表于 2009-07-10 18:55 |只看该作者

回复 #1 Solidus 的帖子

代码有问题
这个差不多

size_t strlen(const char *_string)
{
    const char *str = _string;
    while ( *str && ((DWORD)str & (sizeof(DWORD) - 1)) ) str++;
    if ( ! *str ) return str - _string;

    DWORD magic_bits = 0x7EFEFEFF;
    const DWORD *_ptr = (DWORD *)str;
    DWORD tmp_data;
    do {
         tmp_data = *_ptr++;
    } while ( (~tmp_data ^ (tmp_data + magic_bits)) == ~magic_bits);

    for ( str = (const char *)(_ptr - 1); *str; str++ );
    return str - _string;
}

微软的汇编代码
        page    ,132
        title   strlen - return the length of a null-terminated string
;***
;strlen.asm - contains strlen() routine
;
;       Copyright (c) Microsoft Corporation. All rights reserved.
;
;Purpose:
;       strlen returns the length of a null-terminated string,
;       not including the null byte itself.
;
;*******************************************************************************

        .xlist
        include cruntime.inc
        .list

page
;***
;strlen - return the length of a null-terminated string
;
;Purpose:
;       Finds the length in bytes of the given string, not including
;       the final null character.
;
;       Algorithm:
;       int strlen (const char * str)
;       {
;           int length = 0;
;
;           while( *str++ )
;                   ++length;
;
;           return( length );
;       }
;
;Entry:
;       const char * str - string whose length is to be computed
;
;Exit:
;       EAX = length of the string "str", exclusive of the final null byte
;
;Uses:
;       EAX, ECX, EDX
;
;Exceptions:
;
;*******************************************************************************

        CODESEG

        public  strlen

strlen  proc \
        buf:ptr byte

        OPTION PROLOGUE:NONE, EPILOGUE:NONE

        .FPO    ( 0, 1, 0, 0, 0, 0 )

string  equ     [esp + 4]

        mov     ecx,string              ; ecx -> string
        test    ecx,3                   ; test if string is aligned on 32 bits
        je      short main_loop

str_misaligned:
        ; simple byte loop until string is aligned
        mov     al,byte ptr [ecx]
        add     ecx,1
        test    al,al
        je      short byte_3
        test    ecx,3
        jne     short str_misaligned

        add     eax,dword ptr 0         ; 5 byte nop to align label below

        align   16                      ; should be redundant

main_loop:
        mov     eax,dword ptr [ecx]     ; read 4 bytes
        mov     edx,7efefeffh
        add     edx,eax
        xor     eax,-1
        xor     eax,edx
        add     ecx,4
        test    eax,81010100h
        je      short main_loop
        ; found zero byte in the loop
        mov     eax,[ecx - 4]
        test    al,al                   ; is it byte 0
        je      short byte_0
        test    ah,ah                   ; is it byte 1
        je      short byte_1
        test    eax,00ff0000h           ; is it byte 2
        je      short byte_2
        test    eax,0ff000000h          ; is it byte 3
        je      short byte_3
        jmp     short main_loop         ; taken if bits 24-30 are clear and bit
                                        ; 31 is set

byte_3:
        lea     eax,[ecx - 1]
        mov     ecx,string
        sub     eax,ecx
        ret
byte_2:
        lea     eax,[ecx - 2]
        mov     ecx,string
        sub     eax,ecx
        ret
byte_1:
        lea     eax,[ecx - 3]
        mov     ecx,string
        sub     eax,ecx
        ret
byte_0:
        lea     eax,[ecx - 4]
        mov     ecx,string
        sub     eax,ecx
        ret

strlen  endp

        end

论坛徽章:
1
技术图书徽章
日期:2014-03-06 15:32:30
10 [报告]
发表于 2009-07-10 18:58 |只看该作者
还是这个最好,在我机器上,效率只比上面汇编的低10%左右
size_t strlen(const char *_string)
{
    const char *str = _string;
    while( *str) str++;
    return str - _string;
}
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

  

北京盛拓优讯信息技术有限公司. 版权所有 京ICP备16024965号-6 北京市公安局海淀分局网监中心备案编号:11010802020122 niuxiaotong@pcpop.com 17352615567
未成年举报专区
中国互联网协会会员  联系我们:huangweiwei@itpub.net
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP