has_zero et find_zero dans word_at_a_time.h, utilisés pour

Dans le kernel linux, inlucde / linux / word_at_a_time.h, il existe deux fonctions:

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

Il est utilisé dans une fonction de hachage, dans git log, il est écrit:

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

Mais je ne comprends toujours pas

(1) Que fait cette fonction ?, et
(2) comment ils le font?

Supposons que les bits soient numérotés du bit le moins significatif (LSB) (numéroté 0) au bit le plus significatif (MSB).

Ce qu’il fait?

La fonction find_zero() recherche d’ abord N (<= 7) octets avec la valeur zéro en partant de la gauche, à l’aide d’une technique similaire à la division et la conquête.

Comment ça marche?

Supposons un système 64 bits où CONFIG_64BIT est défini, puis le morceau de code suivant s’exécute:

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

Le premier mask note est unsigned , donc >> est non signé le tamisage droit. ( comme Java >>> )

Il vérifie d’abord si la valeur du mask est supérieure à 2 32 (ou on peut dire si dans unsigned long mask un bit entre les bits numérotés de 32 à 63 vaut un).

mask >> 32 produira une valeur pure qui sera son mask décalé à droite avec une extension zéro 0 de 32 bits et obligera les 32 bits de poids fort à contenir zéro.

par exemple, si maks bits sont les suivants:

 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 

Dans cet exemple, les bits 34 et 59 sont à un, ainsi (mask >> 32) == true (ou non différent de zéro !0 ). Par conséquent, pour cet exemple, if (mask >> 32) == if(!0) .
En général, si un bit des bits 32 à 63 vaut un, mask sera mis à jour pour mask >>= 32; == mask = mask >> 32; (comme si true et si l'instruction s'exécute). Cela provoque 32 bits d'ordre élevé devient 32 bits d'ordre inférieur en raison du décalage à droite (et les bits 32 à 63 deviennent 0 ).

Dans l'exemple ci-dessus, mask devient:

  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 | 

Remarque: les bits de 32 à 63 sont 0 et les bits de 0 à 31 copiés des bits 32 à 63 ci-dessus.

Jusqu'à ici:

Cas 1:
Si l'un des bits compris entre 32 et 63 correspond à un dans le mask origine, il exécute les mises à jour vraies et masquées. (comme je l'ai expliqué ci-dessus). Et variable long byte rest 0 . Ensuite, dans if(mask >> 16) suivant if(mask >> 16) , la fonction find_zero() continuera à rechercher un octet dont la valeur est 0 dans la plage de bits comprise entre 48 et 63 (Dans if(mask >> 16) , les bits numérotés de 48 à 63 seront vérifiés si un bit est 1).

Cas 2:
Si tous les bits de 32 à 63 sont nuls dans le mask origine, alors if condition devient fausse (c'est-à-dire if(mask >> 32) == if(0) ) et le mask ne se met pas à jour, et la variable long byte devient 4 , et Cela indique que quatre octets en haut sont 0 dans le mask . Après cela, dans if(mask >> 16) , la fonction find_zero() recherchera un octet avec zéro dans la plage de bits 16 à 31 .

De même, en seconde if() :

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

Il vérifie si un bit compris entre les bits 16 to 31 vaut un ou non. Si tous les bits sont à zéro, l' byte sera incrémenté de 2 dans une autre partie, tandis que le masque dans une partie sera mis à jour par un décalage non signé de 16 bits à droite.
( Remarque : si mask est mis à jour, mask alors ceci if(mask >> 16) vérifie si un bit compris entre 48 to 63 est 48 to 63 un, sinon les bits 16 à 31 du masque d'origine)

Par la suite, le dernier opérateur conditionnel fonctionne de la même manière pour vérifier si un bit compris entre les bits 8 et 15 est mis à 1 ou non.

  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` 

Donc, la fonction find_zero() recherche les N premiers octets avec la valeur zéro en partant de la gauche. La valeur d'octet de sortie peut aller de 0 à 7 et ne prend pas en compte le plus d'octet ( "8" ).
(* remarque: long est 64 bits long = 8 * 8 bits = 8 octets. *)

 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 

octet = 0 -> signifie que le premier octet n'est pas nul
octet = 1 -> octet de poids fort est égal à zéro et correspond aux bits numérotés de 56 à 63
octet = 2 -> deux octets de poids fort sont égaux à zéro et correspondent aux bits numérotés de 48 à 63
octet = 3 -> trois octets de poids fort sont égaux à zéro et correspondent aux bits numérotés de 40 à 63
:
:
De même, octet = 7 -> Sept octets à gauche sont 0 (ou tous 0).

Représentation schématique

représentation schématique

Code

Ci-dessous, j'ai écrit un petit code qui appelle la fonction find_zero() avec différentes valeurs, vous aidera à comprendre la fonction:

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

Veuillez observer le résultat pour comprendre la fonction:

 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 

Remarque: si tous les octets sont à zéro, il en affichera 7 non 8.

La première fonction recherche le premier octet du masque qui n’est pas nul et renvoie son index en commençant par la gauche.

Exemple pour 64 bits, xx signifiant “n’importe quel octet” et “nn” signifiant “octet différent de zéro”:

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

J’aurais nommé cette fonction find_first_significant_byte_index() sans le dernier cas ambigu …

La deuxième fonction divise val selon un masque binary, stocke ses “low_bits” dans des données * pour référence ultérieure et renvoie un résultat opérationnel étrange sur val. (Impossible d’identifier avec certitude ce dernier).

Voir “L’interface mot à la fois”: https://lwn.net/Articles/501492/

has_zero () renvoie un masque différent de zéro si l’entrée contient un octet zéro.

find_zero () trouve l’endroit où le premier zéro utilisait le masque comme entrée (techniquement, ce n’est pas ce masque, mais ce masque est ensuite masqué par deux fonctions supplémentaires). find_zero () N’EST PAS en train de trouver un zéro dans le masque de saisie.

Voir un exemple d’utilisation dans l’article lié:

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