strlen高效实现

高效实现

(1) 一次判断一个字符直到内存对齐，如果在内存对齐之前就遇到""则直接return，否则到(2)；
(2) 一次读入并判断一个WORD，如果此WORD中没有为0的字节，则继续下一个WORD，否则到(3)；
(3) 到这里则说明WORD中至少有一个字节为0，剩下的就是找出第一个为0的字节的位置然后return。

为了便于下面的讨论，这里假设所用的计算机为32位，即一个WORD为4个字节。下面给出在32位计算机上的C语言实现(假设unsigned long为4个字节)：

typedef unsigned long ulong;

size_t strlen_c(const char * str) {
	const char * char_ptr;
	const ulong * longword_ptr;
	register ulong longword, magic_bits;

	for (char_ptr = str; ((ulong) char_ptr & (sizeof(ulong) - 1)) != 0;
			++char_ptr) {
		if (*char_ptr == "")
			return char_ptr - str;
	}

	longword_ptr = (ulong*) char_ptr;
	magic_bits = 0x7efefeffL;
	while (1) {
		longword = *longword_ptr++;
		if ((((longword + magic_bits) ^ ~longword) & ~magic_bits) != 0) {
			const char *cp = (const char*) (longword_ptr - 1 );
			if (cp[0] == 0)
				return cp - str;
			if (cp[1] == 0)
				return cp - str + 1;
			if (cp[2] == 0)
				return cp - str + 2;
			if (cp[3] == 0)
				return cp - str + 3;
		}
	}
}

源码剖析

上面给出的C语言实现虽然不算特别复杂，但也值得花点时间来弄清楚

	for (char_ptr = str; ((ulong) char_ptr & (sizeof(ulong) - 1)) != 0;
			++char_ptr) {
		if (*char_ptr == "")
			return char_ptr - str;
	}

上面的代码实现了数据对齐，如果在对齐之前就遇到""则可以直接return char_ptr - str;

第14行将longword_ptr指向数据对齐后的首地址

longword_ptr = (ulong*) char_ptr;

第15行给magic_bits赋值(在后面会解释这个值的意义)

magic_bits = 0x7efefeffL;

第17行读入一个WORD到longword并将longword_ptr指向下一个WORD

longword = *longword_ptr++;

第18行的if语句是整个算法的核心，该语句判断17读入的WORD中是否有为0的字节

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

if语句中的计算可以分为如下3步：
(1) longword + magic_bits
其中magic_bits的二进制表示如下：

                  b3      b2       b1       b0
              31------------------------------->0
  magic_bits: 01111110 11111110 11111110 11111111
magic_bits中的31,24,16,8这些bits都为0，我们把这几个bits称为holes，注意在每个byte的左边都有一个hole。
检测0字节：
如果longword 中有一个字节的所有bit都为0，则进行加法后，从这个字节的右边的字节传递来的进位都会落到这个字节的最低位所在的hole上，而从这个字节的最高位则永远不会产生向左边字节的hole的进位。则这个字节左边的hole在进行加法后不会改变，由此可以检测出0字节；相反，如果longword中所有字节都不为0，则每个字节中至少有1位为1，进行加法后所有的hole都会被改变。

为了便于理解，请看下面的例子：
                  b3      b2       b1       b0
              31------------------------------->0
  longword:   XXXXXXXX XXXXXXXX 00000000 XXXXXXXX
+ magic_bits: 01111110 11111110 11111110 11111111上面longword中的b1为0，X可能为0也可能为1。因为b1的所有bit都为0，而从b0传递过来的进位只可能是0或1，很显然b1永远也不会产生进位，所以加法后longword的第16 bit这个hole不会变。

(2)  ^ ~longword
这一步取出加法后longword中所有未改变的bit。

(3)  & ~magic_bits
最后取出longword中未改变的hole，如果有任何hole未改变则说明longword中有为0的字节。

根据上面的描述，如果longword中有为0的字节，则if中的表达式结果为非0，否则为0。

NOTE：
如果b3为10000000，则进行加法后第31 bit这个hole不会变，这说明我们无法检测出b3为10000000的所有WORD。值得庆幸的是用于strlen的字符串都是ASCII标准字符，其值在0-127之间，这意味着每一个字节的第一个bit都为0。因此上面的算法是安全的。

一旦检测出longword中有为0的字节，后面的代码只需要找到第一个为0的字节并返回相应的长度就OK

			const char *cp = (const char*) (longword_ptr - 1 );
			if (cp[0] == 0)
				return cp - str;
			if (cp[1] == 0)
				return cp - str + 1;
			if (cp[2] == 0)
				return cp - str + 2;
			if (cp[3] == 0)
				return cp - str + 3;

另一种实现

size_t strlen_d(const char *str) {

    const char *char_ptr;
    const ulong *longword_ptr;
    register ulong longword, himagic, lomagic;
    for (char_ptr = str; ((ulong) char_ptr & (sizeof(ulong) - 1)) != 0;
            ++char_ptr) {
        if (*char_ptr == "")
            return char_ptr - str;
    }

    longword_ptr = (ulong*) char_ptr;
    himagic = 0x80808080L;
    lomagic = 0x01010101L;
    while (1) {

        longword = *longword_ptr++;
        if (((longword - lomagic) & himagic) != 0) {
            const char *cp = (const char*) (longword_ptr - 1);
            if (cp[0] == 0)
                return cp - str;
            if (cp[1] == 0)
                return cp - str + 1;
            if (cp[2] == 0)
                return cp - str + 2;
            if (cp[3] == 0)
                return cp - str + 3;
        }
    }
}

上面的代码与strlen_c基本一样，不同的是：
magic_bits换成了himagic和lomagic

    himagic = 0x80808080L;
    lomagic = 0x01010101L;

以及 if语句变得比较简单了

if (((longword - lomagic) & himagic) != 0)

if语句中的计算可以分为如下2步：
(1) longword - lomagic
himagic和lomagic的二进制表示如下：
                b3      b2       b1       b0
            31------------------------------->0
  himagic:  10000000 10000000 10000000 10000000
  lomagic:  00000001 00000001 00000001 00000001
在这种方法中假设所有字符都是ASCII标准字符，其值在0-127之间，因此longword总是如下形式：
                b3      b2       b1       b0
            31------------------------------->0
  longword: 0XXXXXXX 0XXXXXXX 0XXXXXXX 0XXXXXXX检测0字节：
如果longword 中有一个字节的所有bit都为0，则进行减法后，这个字节的最高位一定会从0变为1；相反，如果longword中所有字节都不为0，则每个字节中至少有1位为1，进行减法后这个字节的最高位依然为0。

 (2)  & himagic
这一步取出每个字节最高位的1，如果有任意字节最高位为1则说明longword中有为0的字节。

根据上面的描述，如果longword中有为0的字节，则if中的表达式结果为非0，否则为0。