c - 魔术位如何改进 glibc 中的 strlen 功能

Question

我正在查看 strlen for glibc 的来源.他们用过 magic bits找到字符串的长度。有人可以解释一下它是如何工作的。
谢谢

Answer 1

假设这个函数正在查看一个字符串——一次 4 个字节，正如注释所解释的(我们假设 long ints 是 4 个字节)——并且当前的“块”看起来像这样:

'\3'     '\3'     '\0'     '\3'
00000011 00000011 00000000 00000011  (as a string: "\x03\x03\x00\x03")

strlen 函数只是在这个字符串中寻找第一个零字节。它首先通过检查此 magic_bits 来确定每个 4 字节块中是否有任何零字节。首先是快捷方式:它将 4 个字节添加到此值:

01111110 11111110 11111110 11111111

通过传播进位，向该值添加任何非零字节将导致 1 溢出到由零标记的孔中。对于我们的块，它看起来像这样:

  11111111 111111          1 1111111   Carries
  00000011 00000011 00000000 00000011  Chunk
  01111110 11111110 11111110 11111111  Magic bits
+ -----------------------------------
  10000010 00000001 11111111 00000010
  ^      ^        ^        ^         

(孔位由 ^ 标记。)

而且，从评论:

       /* Look at only the hole bits.  If any of the hole bits
          are unchanged, most likely one of the bytes was a
          zero.  */

如果块中没有零，则所有空位都将设置为 1的。然而，由于零字节，一个空位没有被传播进位填充，然后我们可以去检查它是哪个字节。

本质上，它通过对 4 字节块应用一些位加法来扫描零，然后将搜索范围缩小到单字节比较，从而加速 strlen 计算。