c - 什么是 word_at_a_time.h 中的 has_zero 和 find_zero 用于

Question

在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) 这个函数有什么作用？，以及
(2) 他们是怎么做的？

Answer 1

假设位的编号从最低有效位 (LSB)(编号为 0)到最高有效位 (MSB)。

它能做什么？

函数 find_zero() search first N (<=7) 使用类似于分而治之的技术从左侧开始的零值字节。

它是怎么做的？

假设定义了 CONFIG_64BIT 的 64 位系统，然后执行以下代码:

#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 ，所以 >> 是无符号右筛。 ( like Java's >>> )

它首先检查 mask 的值是否大于 232(或者我们可以说在 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 是一，所以 (mask >> 32) == true (或者说非零 !0 )。因此对于这个例子 if (mask >> 32) == if(!0) 。
一般而言，如果从位号 32 到 63 的任何位为 1，则 mask 将更新为 mask >>= 32; == mask = mask >> 32;(就像 true 和 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 中为 1，则 if 执行 true 和 mask 更新。 (正如我上面解释的那样)。变量 long byte 仍然是 0 。然后在下一个 if(mask >> 16) 中，函数 find_zero() 将继续在 48 到 63 的位范围内搜索值为零的字节(在 if(mask >> 16) 中，如果任何位为 1，将检查编号为 48 到 63 的位)。

案例 2:
如果原始 32 中从 63 到 mask 的所有位都为零，则 if 条件变为假(即 if(mask >> 32) == if(0) )并且 mask 不更新，变量 long byte 变为 4 ，这表明 0 中的高四字节为 mask .在 if(mask >> 16) 中，函数 find_zero() 将在 16 到 31 的位范围内搜索零字节。

同样，在第二个 if() 中:

if (mask >> 16)
  mask >>= 16;    
else
  byte += 2; 

它将检查编号为 16 to 31 的位之间的任何位是否为 1。如果所有位都为零，则 byte 将在 else 部分由 2 递增，在 if 部分掩码将通过无符号右移 16 位更新。
( Note : 如果 mask 更新了 mask 那么实际上这个 if(mask >> 16) 检查 48 to 63 之间的任何位是否为 1，否则位 16 到 31 在原始掩码中)

随后，最后一个条件运算符以类似的方式工作，以检查位 NumPy 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() search 第一个 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 --> 高位字节是 0 位编号 56 到 63byte = 2 --> 两个高位字节为零，位编号为 48 到 63byte = 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;
}

请观察输出以了解功能:

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。