what is has_zero and find_zero in word_at_a_time.h used for

Question

In linux kernel, inlucde/linux/word_at_a_time.h, there are two functions:

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;
}

It's used in a hash function, in git log it says:

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

But I still don't get

(1) What this function do?, and
(2) How they do it?

Answer 1

Suppose bits are numbered from Least Significant Bit (LSB) (numbered 0) to Most Significant Bit (MSB).

What it does?

Function find_zero() search first N (<=7) bytes with value zero from left hand side using a technique similar to divide and conquer.

How it does?

Suppose a 64 bit-system where CONFIG_64BIT is defined, then following piece of code executes:

#ifdef CONFIG_64BIT
        if (mask >> 32)  //Any bit=1 in left 32 bits 
                mask >>= 32;
        else
                byte = 4;  //<--No, fist 4 bytes are zero

First note mask is unsigned, so >> is unsigned right sift. (like Java's >>>)

It first checks in if for mask value is more then 2³² (or we can say if in unsigned long mask any bit between bit numbered 32 to 63 is one).

mask >> 32 will produces a pure value that is its mask right-shifted with zero 0 extension by 32 bits and causes the 32 high order bits to contain zero.

for example, if maks bits are as follows:

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

In this example, bit number 34 and 59 is one, so (mask >> 32) == true (or say non-zero !0). Hence for this example if (mask >> 32) == if(!0).
In genral, if any bit from bit number 32 to 63 is one then mask will be updated to mask >>= 32; == mask = mask >> 32; (as if true and if statement executes). This causes high order 32 bits becomes low order 32 bits due to right shift (and bits 32 to 63 becomes 0).

In above example mask becomes:

           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                        |

Note: bits from 32 to 63 are 0 and bits from 0 to 31 copied from bits 32 to 63 from above.

Upto here:

Case-1:
If any bit from 32 to 63 is one in original mask then if executes true and mask updates. (as I explained above). And variable long byte remains 0. Then in next if(mask >> 16), function find_zero() will continue to search for a byte with value zero within bit range 48 to 63(In if(mask >> 16), bit numbered 48 to 63 will be checked for if any bit is 1).

Case-2:
If all bits from 32 to 63 are zero in original mask, then if condition becomes false (that is if(mask >> 32) == if(0)) and mask doesn't updates, and variable long byte becomes 4, and This indicates that high four bytes are 0 in mask. After this in if(mask >> 16), function find_zero() will search for a byte with zero in bit range 16 to 31.

Similarly, in Second if():

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

It will checks if any bit between bit numbered 16 to 31 is one or not. If all bits are zero then byte will incremented by 2 in else part, in if-part mask will be updated by unsigned shift right 16-bits.
(Note: if mask is updated mask then actually this if(mask >> 16) checking whether any bit between 48 to 63 is one, otherwise bits 16 to 31 in original mask)

Subsequently, last conditional operator works in similar fashion to check any bit between bit numbed 8 to 15 is one or not.

                  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`

So function find_zero() search first N bytes with value zero from left hand side. Output byte value can be from 0 to 7 and doesn't considers right most byte ("8").
(*note: long is 64 bits long = 8 * 8-bits = 8 bytes.*)

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 --> means first byte is not zero
byte = 1 --> high order byte is zero that is bit numbered 56 to 63
byte = 2 --> two high order bytes are zero that is bit numbered 48 to 63
byte = 3 --> three high order byte is zero that is bit numbered 40 to 63
:
:
Similarly, byte = 7 --> Seven bytes from left are 0, (or all 0).

Flow-diagram

Code

Below I have written a small code that calls find_zero() function with different values, will help you to understand the function:

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;
}

Please observe the output to understand 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

Note: if all bytes are zero it prints 7 not 8.