现在的位置: 首页 > 综合 > 正文

strlen源码分析

2013年11月10日 ⁄ 综合 ⁄ 共 2924字 ⁄ 字号 评论关闭

 

strlen函数原型为:

         size_t strlen_c(const char *str)

参数为C风格字符串,输出为字符长度,以下为高效的实现代码:

 1 typedef unsigned long  ulong;
 2 

 3 size_t strlen_c(const char * str) {
 4 

 5     const char * char_ptr;
 6     const ulong *
longword_ptr;
 7 
    register ulong longword, magic_bits;
 8 

 9     for (char_ptr =  str; ((ulong)char_ptr 
10         & (sizeof(ulong) - 1)) != 0
;
11         ++
char_ptr) {
12         if (*char_ptr == '/0'
)
13             return char_ptr -
 str;
14 
    }
15 

16     longword_ptr = (ulong* )char_ptr;
17 

18     magic_bits = 0x7efefeffL ;
19 

20     while (1 ) {
21 

22         longword = *longword_ptr++ ;
23 

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

26             const char *cp = (const char*)(longword_ptr - 1 );
27 
            
28             if (cp[0== 0
)
29                 return cp -
 str;
30             if (cp[1== 0
)
31                 return cp - str + 1
;
32             if (cp[2== 0
)
33                 return cp - str + 2
;
34             if (cp[3== 0
)
35                 return cp - str + 3
;
36 
        }
37 
    }
38 }

 

这种算法不是每次比较一个字符,而是比较一个机器字(32位机器是4个字节),利用了数据对齐技术。数据对齐是指数据在内存中的开始地址要是数据长度的整数倍,这样存取是最快的。

算法大致步骤:

1、首先把指针移到地址是机器字的整数倍的位置,假如已经遇到为0的字节,则直接返回长度

2、从此位置开始,每次比较一个机器字,直至遇到第一个为0的字节

3、找出这个字节在这个机器字的位置,然后返回长度

下面详细看代码(假设机器为32位机):

9     for (char_ptr =  str; ((ulong)char_ptr 
10         & (sizeof(ulong) - 1)) != 0
;
11         ++
char_ptr) {
12         if (*char_ptr == '/0'
)
13             return char_ptr -
 str;
14 
    }

这段代码完成步骤1。for成立条件:((ulong)char_ptr & (sizeof(ulong) - 1)) != 0 它的意思是char_ptr是否为4的倍数,意义是把char_ptr移到地址是4的倍数的位置上,在这个过程中如果已有字符'/0',则返回长度;

16     longword_ptr = (ulong* )char_ptr;

这是令到longword指向已已对齐的地址

这个是魔法位,它的二进制表示是(最低位为第0位):01111110,11111110,11111110,11111111,其中第31、24、16、8位,为0,暂时称呼为判断位,意义是要检测下一个字节是否为0,这个下面再详细讨论

18     magic_bits = 0x7efefeffL ;

 

这是最为核心的:

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

 

(longword + magic_bits)

意思是产生进位,是相应的判断位改变

longword是四个字节,分别是b4 b3 b2 b1,对于magic_bits,只要b4~b1有一个不为0,那么必定会产生进位,使判断位为1

例如:
                               b4                    b3                    b2                     b1
longword :         00011010      01001011      00000000      00110110
magic_bits:       01111110      11111110      11111110      11111111 +
结果:                   10010001      01001001       11111111      00110101

b3此字节不为0,令到magic_bits的第24位为1了

 

^ ~longword

意思是把结果与longword比较,相同位为1

 

& ~magic_bits

取最终结果的第31、24、16、8位

这样,假如最终结果第16位为1,则表示最后结果的第16位与longword的第16位相同,b2字节没有产生进位,b2字节为0
因此,如果longword中含有0字节,最终结果为非0

 

28             if (cp[0== 0 )
29                 return cp -  str;
30             if (cp[1== 0 )
31                 return cp - str + 1 ;
32             if (cp[2== 0 )
33                 return cp - str + 2 ;
34             if (cp[3== 0 )
35                 return cp - str + 3 ;

找出0字节位置,返回长度;

问题:
1、为什么magic_bits第31位为0?
      这是为了检测到b4为0的情况,因为无法检测第32位,因此把31位置0,检测31位,检测b4为00000000的情况
2、当longword中b4为10000000时,算法失败
      当longword中b4为10000000时,最终结果的b4字节永远为0,算法失败,幸好参数字符的ascii码范围为0~127,因此算法是可行的。

 

 

抱歉!评论已关闭.