What has_zero and find_zero in word_at_a_time.h is used for

Question

There are two functions in the linux kernel 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; } 

It is used in a hash function, the git log 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 it

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

Answer 1

Assume that the bits are numbered from the least significant bit (LSB) (number 0) to the most significant bit (MSB).

What is he doing?

The find_zero() function first searches for N (<= 7) bytes with a zero value on the left side using a technique similar to the divide and conquer method.

How to do it?

Suppose that a 64-bit system, where CONFIG_64BIT defined, runs the following code fragment:

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

The first note of mask is unsigned , so >> is an unsigned right screening. ( like Java> "> )

First, it is checked if the mask value is greater than 2 ³² (or we can say that if in an unsigned long mask any bit between bits 32 to 63 is one).

mask >> 32 will produce a pure value, which is its mask with a right shift with a zero extension of 0 by 32 bits and makes the upper order 32 bits contain zero.

for example if maks bit:

 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, the number of bits 34 and 59 is equal to one, therefore (mask >> 32) == true (or say non-zero !0 ). Therefore, for this example, if (mask >> 32) == if(!0) .
In genral, if any bit from bit number 32 to 63 is 1, then mask will be updated to mask >>= 32; == mask = mask >> 32; (as if true and if were executed). This causes high-order bit 32 to become the low-order bit of 32 due to a right shift (and bits 32 through 63 become 0 ).

In the 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 32 through 63 are 0 and bits 0 through 31 are copied from bits 32 to 63 above.

Here:

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

Case-2:
If all bits 32 to 63 are equal to zero in the original mask , then the if condition becomes false (this is if(mask >> 32) == if(0) ) and mask not updated, and the long byte variable becomes 4 , and this means that high four bytes 0 in mask . After that, in if(mask >> 16) , the find_zero() if(mask >> 16) function will search for a byte with zero in the range of bits 16 to 31 .

Similarly, in the second if() :

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

It will check if the bit between bit number 16 to 31 one or not. If all the bits are equal to zero, then the byte will increase by 2 in the other part, in the if-part mask it will be updated with an unsigned right shift of 16 bits.
( Note : if mask updated, mask is actually if(mask >> 16) , checking if there is any bit between 48 to 63 , otherwise bit 16 to 31 in the original mask)

Subsequently, the last conditional statement works similarly to checking any bit between bits numbed 8 to 15 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` 

Thus, the find_zero() function searches for the first N bytes with a value of 0 on the left side. The value of the output byte can be from 0 to 7 and does not take into account the right byte ( "8" ).
(* note: long - length 64 bits = 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 that the first byte is not equal to zero
byte = 1 → high byte is zero, the digit of which is numbered 56 to 63
byte = 2 → two upper order bytes - this is zero, the digit of which is numbered from 48 to 63
byte = 3 → three high-order bytes is a zero whose digit is numbered from 40 to 63
:
:
Similarly, byte = 7 → The seven bytes on the left are 0, (or all 0).

Flow diagram

the code

Below I wrote a little code that calls the find_zero() function with different values, will help you understand this 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; } 

Pay attention to the output for understanding the 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.

Answer 2

The first function searches for the first byte in the mask, which is not null, and returns its index starting at the left.

Example for 64bit, xx , meaning "any byte" and "nn", which means "non-zero byte":

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

I would call this function find_first_significant_byte_index() , if not for the latter case, which is ambiguous ...

The second function splits val according to the bitmask, saves its "low_bits" in * data for future use, and returns some strange op result to val. (Unable to identify this last last).

Answer 3

See “Time-Based Interface”: https://lwn.net/Articles/501492/

has_zero () returns a nonzero mask if the input has zero byte inside.

find_zero () finds where this first zero used the mask as an input (technically this is not the mask, but this mask is further massaged by two more functions). find_zero () does NOT find zero in the input mask.

See a usage example in a related article:

 if (has_zero(value, &bits, &constants)) { bits = prep_zero_mask(value, bits, &constants); bits = create_zero_mask(bits); zero_byte = find_zero(bits); /* ... */