glibc strlen()实现如何工作

Question

的strlen()从K&R只需要几行.

int strlen(char *s)
{
    char *p = s;
    while (*p != '\0')
        p++;
    return p - s;
}

但是glibc版本要长得多.为简单起见,我删除了所有注释和64位实现,提取的版本strlen()如下所示:

size_t strlen(const char *str)
{
    const char *char_ptr;
    const unsigned long int *longword_ptr;
    unsigned long int longword, magic_bits, himagic, lomagic;

    for (char_ptr = str; ((unsigned long int) char_ptr 
             & (sizeof (longword) - 1)) != 0; ++char_ptr)
       if (*char_ptr == '\0')
           return char_ptr - str;

    longword_ptr = (unsigned long int *) char_ptr;

    himagic = 0x80808080L;
    lomagic = 0x01010101L;

    for (;;)
    { 
        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;
        }
    }
}

在非常有用的评论(点击这里)的帮助下,我得到了大部分的工作原理.'\0'glibc 不是逐字节检查,而是strlen()检查每个字(32位机器中的4个字节,64位机器中的8个字节).这样,当弦线相对较长时,可以提高性能.

它通过逐字节读取来检查前几个字符,直到char_ptr在longword边界上对齐.然后它使用一个循环来检查是否longword有任何包含全零的字节.如果有,检查哪个字节,并返回结果.

我没有得到的部分是,如何检查一个字节longword是全零？

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

我可以构建一个longword值0x81818181,它可以0x81818181 - 0x01010101) & 0x80808080不等于0,但没有全零字节.

这是一个事实,即ASCII值的范围从相关0到127,所以0x81是无效的ASCII？但我不认为C标准强制字符串使用ASCII.

Answer 1

我想到了.简直不敢相信,我花了半个多小时才上完.

检查没关系

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

让值像0x81818181pass 一样,因为如果它通过,则每个字节的后续测试都不会返回,因为没有全零字节.所以循环可以继续测试下一个longword.

检查后面的算法基于确定一个字是否具有零字节

unsigned int v; 
bool hasZeroByte = ~((((v & 0x7F7F7F7F) + 0x7F7F7F7F) | v) | 0x7F7F7F7F);

在2的补码中,- 0x01010101具有相同的效果+ 0xFEFEFEFF.不同之处在于glibc没有v & 0x7F7F7F7F,这可以确保单词中的字节具有最重要的位0.这可以防止像这样的例子0x81818181,但glibc省略它,因为它不必像前面所述那样让它通过,只要它不会错过任何具有全零字节的单词,检查是正确的.