strlen函数原型为:
size_t strlen_c(const char *str)
参数为C风格字符串,输出为字符长度,以下为高效的实现代码:
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位机):
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',则返回长度;
这是令到longword指向已已对齐的地址
这个是魔法位,它的二进制表示是(最低位为第0位):01111110,11111110,11111110,11111111,其中第31、24、16、8位,为0,暂时称呼为判断位,意义是要检测下一个字节是否为0,这个下面再详细讨论
这是最为核心的:
意思是产生进位,是相应的判断位改变
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比较,相同位为1
取最终结果的第31、24、16、8位
这样,假如最终结果第16位为1,则表示最后结果的第16位与longword的第16位相同,b2字节没有产生进位,b2字节为0
因此,如果longword中含有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,因此算法是可行的。