c - 魔术位如何改进 glibc 中的 strlen 函数

Question

我正在浏览glibc 的 strlen的来源。他们习惯于magic bits查找字符串的长度。有人可以解释它是如何工作的。谢谢

Answer 1

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

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

strlen 函数只是在此字符串中查找第一个零字节。它首先通过首先检查此快捷方式来确定每个 4 字节块中是否有任何零字节magic_bits：它将 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
  ^      ^        ^        ^         

（孔位用^'s 标记。）

而且，从评论中：

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

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

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

Answer 2

这个想法是一次将一个字节与零进行比较，而不是一次检查一个unsigned long对象，如果其字节之一为零。这意味着在is8时检查字节。sizeof (unsigned long)8

使用位黑客，有一个快速已知的表达式可以确定一个字节是否等于零。然后，如果其中一个字节为零，则单独测试对象的字节以找到第一个为零的字节。使用按位运算的优点是减少了分支指令的数量。

用于检查多字节对象的一个​​字节是否等于 0 的 bit hack 表达式在著名的 Stanford Bit Twiddling Hacks 页面中进行了解释，在

确定一个单词是否有零字节 http://graphics.stanford.edu/~seander/bithacks.html#ZeroInWord