c - 如何判断一个字中的一个字节是否为空

Question

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

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

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

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

其中 longword 是数据 block ，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

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

The subexpression (v - 0x01010101UL), evaluates to a high bit set in any byte whenever the corresponding byte in v is zero or greater than 0x80. The sub-expression ~v & 0x80808080UL evaluates to high bits set in bytes where the byte of v doesn't have its high bit set (so the byte was less than 0x80). Finally, by ANDing these two sub-expressions the result is the high bits set where the bytes in v were zero, since the high bits set due to a value greater than 0x80 in the first sub-expression are masked off by the second.

似乎 glibc 源代码中的注释令人困惑，因为它不再适用于代码实际执行的操作 - 它描述了算法的实现Anderson 在描述 hasless(v, 1) 算法之前描述了这一点。