什么是word_at_a_time.h中的has_zero和find_zero用于
在linux内核中，inlucde / linux / word_at_a_time.h有两个函数：
static inline long find_zero(unsigned long mask) { long byte = 0; #ifdef CONFIG_64BIT if (mask >> 32) mask >>= 32; else byte = 4; #endif if (mask >> 16) mask >>= 16; else byte += 2; return (mask >> 8) ? byte : byte + 1; } static inline bool has_zero(unsigned long val, unsigned long *data, const struct word_at_a_time *c) { unsigned long rhs = val | c->low_bits; *data = rhs; return (val + c->high_bits) & ~rhs; } 它用在哈希函数中，在git log中它说：
- has_zero(): take a word, and determine if it has a zero byte in it. It gets the word, the pointer to the constant pool, and a pointer to an intermediate "data" field it can set.
但我仍然没有得到
（1）这个function做什么？，和
（2）他们是怎么做到的？
假设位从最低有效位（LSB）（编号0）到最高有效位（MSB）编号。
它能做什么？
函数find_zero()使用类似于除法和征服的技术从左侧搜索第一个 N （<= 7）个字节，其值为零。
怎么样？
假设一个64位系统定义了CONFIG_64BIT ，然后执行以下代码：
#ifdef CONFIG_64BIT if (mask >> 32) //Any bit=1 in left 32 bits mask >>= 32; else byte = 4; //<--No, fist 4 bytes are zero
第一个音符mask是unsigned ，所以>>是无符号的右移。 （ 比如Java的>>> ）
它首先检查mask值是否大于2 32 （或者我们可以说，如果在unsigned long mask ，编号为32到63位之间的任何位是1）。
mask >> 32将产生一个纯值，即它的mask右移，零0扩展32位，并使32高阶位包含零。
例如，如果maks位如下：
63 56 55 48 47 40 39 32 31 24 23 16 15 7 0 ▼ ▼ ▼ ▼ ▼ ▼ ▼ ▼ ▼ ▼ ▼ ▼ ▼ ▼ ▼ 0000 1000 0000 0000 0000 0000 0000 0100 0000 0000 0000 0000 0000 0000 0001 0101 ▲ ▲ MSB LSM
在这个例子中，位号34和59是1，所以(mask >> 32) == true （或说非零!0 ）。 因此，对于此示例if (mask >> 32) == if(!0) 。
在通用中，如果位号32到63任何位是1，则mask将被更新为mask >>= 32; == mask = mask >> 32; （好像是真的，if语句执行）。 这导致高阶32位由于右移而变为低阶32位（并且位32至63变为0 ）。
在上面的示例mask变为：
shifted OLD bit number ----> 63 45 32 63 47 32 31 15 0 ▼ ▼ ▼ ▼ ▼ ▼ 0000 0000 0000 0000 0000 0000 0000 0000 0000 1000 0000 0000 0000 0000 0000 0100 ▲ ▲ MSB LSM |-------------------------------------| | All are zero |
注意：从32到63的位为0 ，从0到31位从上面的位32到63复制。
到此为止：
情况1：
如果32到63任何位是原始mask 一个 ，那么if执行true并且掩码更新。 （正如我上面解释的那样）。 变量long byte保持为0 。 然后在下一个if(mask >> 16) ，函数find_zero()将继续在位范围48到63内搜索值为零的字节（ if(mask >> 16) ，将检查编号为48到63位如果有任何一位是1）。
案例2：
如果原始mask 32到63所有位都为零，那么if条件变为假（即if(mask >> 32) == if(0) ）并且mask不更新，并且变量long byte变为4 ，并且这表示mask中高四个字节为0 。 在if(mask >> 16) ，函数find_zero()将搜索位为16到31零字节。
同样，在Second if() ：
if (mask >> 16) mask >>= 16; else byte += 2;
它将检查编号为16 to 31位之间是否有1位。 如果所有位都为零，那么在其他部分中， byte将递增2 ，在if部分掩码将由无符号右移16位更新。
（ 注意 ：如果mask更新mask那么实际上这个if(mask >> 16)检查48 to 63之间的任何位是否为1，否则原始掩码中的位16到31 ）
随后，最后一个条件运算符以类似的方式工作，以检查位麻痹8到15之间的任何位是否为1。
long byte = 0; 64 bit `mask` | | ▼ if(any bit from 32 to 62 is one)---+ | | |False: if(0) |True: if(!0) all bits between 32 to 64 |A byte=Zero NOT found are zero Some bits are one from bit 32-63 | | | | byte = 4 byte= 0, and 64 bit `mask` <--Orignal `mask` updated as `mask >>= 32;` | | | | ▼ ▼ if(Any bit from 16 to 31 is one) if(Any bit from 48 to 63 is one) |Because high order bits are Zero |Note due to >> all high order |It check for bits numbered 16-31 |bits becomes zero. | |2nd if checks for bit from 16-31 | |that were originally bit | | numbered 48 to 63 | | ▼ ▼ Case False: if(0) Case False: if(0) All bits Zero from 16-31 All bits Zero from 49-63 mask will NOT updated and mask will NOT updated and byte = 6 byte = 2 Case True: if(!0) Case False: if(!0) Some bits are one from 16-31 Some bits are one from 49-63 mask updated mask Updated byte = 4 byte = 0 | | | | ▼ ▼ more four cases more four cases Total 8 different answer outputs from `0` to `7`
因此函数find_zero()从左侧搜索前 N个字节，值为零。 输出字节值可以是0到7 ，不考虑最右边的字节（ "8" ）。
（*注意：long是64位长= 8 * 8位= 8字节。*）
byte NUMBER ("): "1" "2" "3" "4" "5" "6" "7" "8" 63 56 55 48 47 40 39 32 31 24 23 16 15 7 0 ▼ ▼ ▼ ▼ ▼ ▼ ▼ ▼ ▼ ▼ ▼ ▼ ▼ ▼ ▼ 0000 1000 0000 0000 0000 0000 0000 0100 0000 0000 0000 0000 0000 0000 0001 0101 ▲ ▲ MSB LSM
byte = 0 - >表示第一个字节不为零
byte = 1 - >高位字节为零，位编号为56到63
byte = 2 - >两个高位字节为零，位编号为48到63
byte = 3 - >三个高位字节为零，位编号为40到63
：
：
类似地，byte = 7 - >左起七个字节是0，（或全0）。
流程图
码
下面我写了一个小代码，调用不同值的find_zero()函数，将帮助您理解函数：
int main(){ printf("\nmask=0x0, all bytes are zero, result =%ld", find_zero(0x0L)); // not prints 8 printf("\nmask=0xff, left seven bytes are zero, result =%ld", find_zero(0xffL)); printf("\nmask=0xffff, left six bytes are zero, result =%ld", find_zero(0xffffL)); printf("\nmask=0xffffff, left five bytes are zero, result =%ld", find_zero(0xffffffL)); printf("\nmask=0xffffffff, left four bytes are zero, result =%ld", find_zero(0xffffffffL)); printf("\nmask=0xffffffffff, left three bytes are zero, result =%ld", find_zero(0xffffffffffL)); printf("\nmask=0xffffffffffff, left two bytes are zero, result =%ld", find_zero(0xffffffffffffL)); printf("\nmask=0xffffffffffffff, left most one byte is zero, result =%ld", find_zero(0xffffffffffffffL)); printf("\nmask=0xffffffffffffffff, No byte is zero, result =%ld", find_zero(0xffffffffffffffffL)); printf("\nmask=0x8000000000000000L, first byte is NOT zero (so no search), result =%ld", find_zero(0x8000000000000000LL)); printf("\n"); return 1; }
请观察输出以了解function：
mask=0x0, all bytes are zero, result =7 mask=0xff, left seven bytes are zero, result =7 mask=0xffff, left six bytes are zero, result =6 mask=0xffffff, left five bytes are zero, result =5 mask=0xffffffff, left four bytes are zero, result =4 mask=0xffffffffff, left three bytes are zero, result =3 mask=0xffffffffffff, left two bytes are zero, result =2 mask=0xffffffffffffff, left most one byte is zero, result =1 mask=0xffffffffffffffff, No byte is zero, result =0 mask=0x8000000000000000L, first byte is NOT zero (so no search), result =0
注意：如果所有字节都为零，则打印7而不是8。
第一个函数查找掩码中非空的第一个字节，并从左侧开始返回其索引。
64位的示例， xx表示“任意字节”，“nn”表示“非零字节”：
.nn.xx.xx.xx.xx.xx.xx.xx -> find_zero() -> 0 .00.nn.xx.xx.xx.xx.xx.xx -> find_zero() -> 1 .00.00.nn.xx.xx.xx.xx.xx -> find_zero() -> 2 ... .00.00.00.00.00.00.00.nn -> find_zero() -> 7 .00.00.00.00.00.00.00.00 -> find_zero() -> 7 (this one is strange)
如果不是最后一个不明确的情况，我会将此函数命名为find_first_significant_byte_index()
第二个函数根据位掩码拆分val ，将其“low_bits”存储在* data中以供进一步引用，并在val上返回一些奇怪的op结果。 （无法确定最后一个）。
请参阅“一次一词的界面”： https ： //lwn.net/Articles/501492/
如果输入中包含零字节，则has_zero（）返回非零掩码。
find_zero（）找到第一个零点使用掩码作为输入的位置（从技术上讲，它不是那个掩码，而是由另外两个函数进一步按下的掩码）。 find_zero（）未在输入掩码中找到零。
请参阅链接文章中的示例用法：
if (has_zero(value, &bits, &constants)) { bits = prep_zero_mask(value, bits, &constants); bits = create_zero_mask(bits); zero_byte = find_zero(bits); /* ... */