glibc中的strlen实现
近来打算阅读glibc源码, 便从最简单的string.h开始. 说道string库, 第一个想到的是什么函数? 当然是strlen
于是翻开strlen.c , 大牛写的代码就是不一样, 总像是故意把原本简单的东西写得复杂, 仔细阅读才发现简直是神作.
对任何c程序员来说以下代码可以说是信手拈来:
size_t strlen(const char *str) { const char *str_iter = str; while(*str_iter++); return str_iter - str - 1; }
原以为strlen无非就是做循环, 逐个字节做判断, 看了glibc的strlen实现才发现我之前简直是too young too simple!
先贴代码:
size_t strlen (str) const char *str; { const char *char_ptr; const unsigned long int *longword_ptr; unsigned long int longword, himagic, lomagic; /* Handle the first few characters by reading one character at a time. Do this until CHAR_PTR is aligned on a longword boundary. */ for (char_ptr = str; ((unsigned long int) char_ptr & (sizeof (longword) - 1)) != 0; ++char_ptr) if (*char_ptr == '') return char_ptr - str; /* All these elucidatory comments refer to 4-byte longwords, but the theory applies equally well to 8-byte longwords. */ longword_ptr = (unsigned long int *) char_ptr; /* Bits 31, 24, 16, and 8 of this number are zero. Call these bits the "holes." Note that there is a hole just to the left of each byte, with an extra at the end: bits: 01111110 11111110 11111110 11111111 bytes: AAAAAAAA BBBBBBBB CCCCCCCC DDDDDDDD The 1-bits make sure that carries propagate to the next 0-bit. The 0-bits provide holes for carries to fall into. */ himagic = 0x80808080L; lomagic = 0x01010101L; if (sizeof (longword) > 4) { /* 64-bit version of the magic. */ /* Do the shift in two steps to avoid a warning if long has 32 bits. */ himagic = ((himagic << 16) << 16) | himagic; lomagic = ((lomagic << 16) << 16) | lomagic; } if (sizeof (longword) > 8) abort (); /* Instead of the traditional loop which tests each character, we will test a longword at a time. The tricky part is testing if *any of the four* bytes in the longword in question are zero. */ for (;;) { longword = *longword_ptr++; if (((longword - lomagic) & ~longword & himagic) != 0) { /* Which of the bytes was the zero? If none of them were, it was a misfire; continue the search. */ 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; if (sizeof (longword) > 4) { if (cp[4] == 0) return cp - str + 4; if (cp[5] == 0) return cp - str + 5; if (cp[6] == 0) return cp - str + 6; if (cp[7] == 0) return cp - str + 7; } } } }
注释得挺详细, 可以看出这段代码高效就在于循环时不是逐字节判断, 而是逐字长判断
为什么快, 首先这符合循环展开(CSAPP p348), 这样一次循环就可以判断4个/8个字节. 其次, 从机器角度讲, 操作数为机器字长的指令相对较快
但一开始需要先处理一些没对齐的情况, 直到指针指向第一个地址对齐的字节
(i386没有强制要求边界对齐, 但对齐了可以提高处理效率. 这里应该是出于可移植性的考虑, 因为某些cpu需要对齐)
代码最关键的地方在于50行中: (longword – lomagic) & ~longword & himagic
(在旧版本中是(longword – lomagic) & himagic, 但存在一些缺陷)
这个表达式是为了判断longword中是否存在某字节为0, 如果存在则返回0, 否则不为0
对于这行代码, 想了很久, 终于理解了它的正确性.
一: 假设机器字长只有一个字节, longword 也是一个字节
lomagic: 0000 0001
himagic: 1000 0000
(longword – lomagic) & ~longword & himagic 等效为 (longword – 1) & (~longword) & 0x80
只需要关注最高位, (longword-1) 和(~longword) 中任何一个最高位等于0, 则整个表达式为0
1. 如果(longword >= 0x80), 那么~longword 最高位则为0, 于是表达式的值为0
2. 如果(0 < longword < 0x80), 那么 0 <= (longword -1) <= (0x80-2) , 即(longword -1) 最高位为0, 表达式的值为0
3. 如果 (longword == 0) 有 ongword-1 == 255, ~longword == 255, 表达式结果为0x80, 为非0
也就是当(longword == 0) 时结果是非0, (longword != 0) 时结果为0
那么对于单个字节, 表达式的正确性已经得到验证
二. 再假设机器字长为32位, 那么两个魔数位模式如下
high low byte3, byte2, byte1, byte0 lomagic: 0000 0001, 0000 0001, 0000 0001, 0000 0001 himagic: 1000 0000, 1000 0000, 1000 0000, 1000 0000 longword: xxxx xxxx, xxxx xxxx, xxxx xxxx, xxxx xxxx result: xxxx xxxx, xxxx xxxx, xxxx xxxx, xxxx xxxx
以result表示表达式计算结果
1. 如果任何字节都不等于0, 也就是每个字节都大于等于1
那么 longword-lomagic 相当于每个字节分别减去1, 不存在借位
后面的取反以及按位与操作, 都可以看作是4个独立的字节单独计算的, 互不影响, 此时表达式的计算结果还是0
2. 如果有一个或者多个字节等于0, 考察值为0的最低字节, 比如longword中byte3, byte1都等于0, 考察其中的byte1
由于从低到高, byte1是第一个值等于0的字节, byte0不会向byte1借位
所以byte1对应的字节仍然可以看作单独计算 (longword_byte1 – 0x01) & ~longword_byte1 & 0x80
于是result中byte1字节处的值不等于0, 整个结果也就非0
第一步中 longword – lomagic 的时候, longword的byte1会向byte2借一位, 如果单独考察byte2做减法时相当于(byte2 – 0x02).
但这不会影响整体的结果, 因为结果中byte1处是非0, 无论byte2结果如何, 总体结果都是非0
32位如此, 64位也是如此
而当遇到字当中存在值为0的字节, 便继续判断是具体哪个字节, 后面的都比较简单了
仔细阅读注释, 可以看到很多精辟的技巧.
字长操作代替字节操作也可以应用到其他函数, 比如strcpy, memcpy, memset