C语言 如何确定单词中的字节是否为空

Question

我正在从glibc读取"strlen"源代码，开发人员发现加快速度的技巧是读取n个字节，其中n是一个长字的大小，而不是在每次迭代时读取1个字节。

我假设一个长字有 4 个字节。

棘手的部分是，函数读取的每个 4 个字节的"块"都可以包含一个空字节，因此在每次迭代时，函数都必须检查块中是否有空字节。他们这样做就像

if (((longword - lomagic) & ~longword & himagic) != 0) { /* null byte found */ }

其中longword是数据块，himagic和lowmagic是定义为

：

himagic = 0x80808080L;
lomagic = 0x01010101L;

这是这些值的评论

/* 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.  */

这个查找空字节的技巧是如何工作的？

Answer 1

来自Sean Eron Anderson著名的"Bit Twiddling Hacks"页面，描述了您所指glibc实现中当前使用的内容(Anderson称该算法为hasless(v, 1)(：

子表达式 (v - 0x01010101UL) 的计算结果为 任何字节，只要 V 中的相应字节为零或大于 0x80 .子表达式~v & 0x80808080UL计算结果为高位集 以字节为单位，其中 V 的字节没有设置其高位(因此 字节小于 0x80 (。最后，通过对这两个子表达式进行 结果是高位集，其中 V 中的字节为零，因为 由于第一个值大于 0x80 而设置的高位 子表达式被第二个表达式掩盖。

似乎glibc源代码中的注释令人困惑，因为它不再适用于代码实际正在做的事情 - 它描述了在描述hasless(v, 1)算法之前Anderson描述的算法的实现。