was ist has_zero und find_zero in word_at_a_time.h verwendet für

Angenommen, Bits sind von niedrigstwertigem Bit (LSB) (nummeriert 0) bis höchstwertigstes Bit (MSB) nummeriert.

Was macht es?

Funktion find_zero() Suche erste N (& lt; = 7) Bytes mit dem Wert Null von der linken Seite mit einer Technik, die dem Teilen und Erobern ähnlich ist.

Wie funktioniert es?

Angenommen, ein 64-Bit-System, in dem CONFIG_64BIT definiert ist, führt das folgende Code-Teil aus:

Erste Anmerkung mask ist unsigned , also >> ist unsigniert rechts sift. ( wie Java & gt; & gt; & gt; )

Es überprüft zunächst, wenn für mask Wert ist mehr als 2 ³² (oder wir können sagen, wenn in unsigned long mask ein Bit zwischen Bit nummerierte 32 bis 63 gehört) .

mask >> 32 wird erzeugt einen Wert, der sein reinen% ist co_de% rechts verschoben mit Null mask Dehnung von 0 Bits und bewirkt, dass der 32 höherwertigen Bits Null enthalten.

zum Beispiel, wenn 32 Bits wie folgt sind:

In diesem Beispiel ist die Bitnummer maks und 34 eins, also 59 == (mask >> 32) (oder sagen wir nicht-null true ). Daher für dieses Beispiel !0 == if (mask >> 32) .
Wenn ein Bit von der Bitnummer if(!0) bis 32 eins ist, dann wird 63 im allgemeinen auf mask == mask >>= 32; aktualisiert (als ob es wahr ist und wenn die Anweisung ausgeführt wird). Dies bewirkt, dass eine hohe Ordnung mask = mask >> 32; Bits aufgrund einer Rechtsverschiebung zu Bits niedriger Ordnung 32 wird (und die Bits 32 bis 63 werden 32 ).

Im obigen Beispiel wird 0 zu

Hinweis: Bits von 32 bis 63 sind mask und Bits von 0 bis 0 kopiert von den Bits 31 bis 32 von oben.

Bis hierhin:

Fall 1:
Wenn ein Bit von 63 bis 32 im ursprünglichen 63 eins ist, führt mask true aus und maskiert Aktualisierungen. (wie ich oben erklärt habe). Und die Variable if bleibt long byte . Dann in der nächsten 0 , Funktion if(mask >> 16) wird weiterhin für ein Byte mit dem Wert Null innerhalb Bitbereich find_zero() bis 48 (in 63 suchen, nummeriert Bit if(mask >> 16) bis 48 für überprüft werden wenn irgendein Bit 1 ist.

Fall 2:
Wenn alle Bits von 63 bis 32 Null in Original 63 sind, dann mask Bedingung falsch (dh if == if(mask >> 32) ) und if(0) nicht-Updates und Variable mask wird long byte , und Dies zeigt an, dass hohe vier Bytes 4 in 0 sind. Danach sucht die Funktion mask in if(mask >> 16) nach einem Byte mit Null im Bitbereich find_zero() bis 16 .

Ähnlich, in Second 31 :

Es wird geprüft, ob ein Bit zwischen dem Bit mit der Nummer if() eins ist oder nicht. Wenn alle Bits Null sind, wird 16 to 31 um byte im anderen Teil inkrementiert, wenn die if-part-Maske durch vorzeichenlose 16-Bit-Verschiebungsrechte aktualisiert wird.
( Hinweis : if 2 aktualisiert mask dann dies tatsächlich mask zu prüfen, ob ein Bit zwischen if(mask >> 16) ist, sonst Bits 48 to 63 bis 16 in Original Maske)

Anschließend arbeitet der letzte Bedingungsoperator in ähnlicher Weise, um jedes Bit zwischen dem Bit betagt 31 bis 8 ist eins oder nicht zu prüfen.

So Funktion 15 Suche erste find_zero() Bytes mit Wert Null von der linken Seite. Der Ausgabe-Byte-Wert kann von N bis 0 sein und berücksichtigt nicht das rechte Byte ( 7 ).
(* Hinweis: lang ist 64 Bit lang = 8 * 8 Bit = 8 Byte. *)

byte = "8" - & gt; bedeutet erstes Byte ist nicht null
byte = 0 - & gt; höherwertiges Byte ist Null, das heißt Bit 1 bis 56
byte = 63 - & gt; zwei höherwertige Bytes sind Null, das heißt Bit 2 bis 48
byte = 63 - & gt; drei höherwertige Bytes sind null, das heißt Bit 3 bis 40
   :
   :
Ähnlich, Byte = 63 - & gt; Sieben Bytes von links sind 0 (oder alle 0).

Flussdiagramm

Code

Im Folgenden habe ich einen kleinen Code geschrieben, der 7 function mit verschiedenen Werten aufruft und Ihnen hilft, die Funktion zu verstehen:

Bitte beachten Sie die Ausgabe, um die Funktion zu verstehen:

Hinweis: Wenn alle Bytes Null sind, wird find_zero() nicht 8 ausgegeben.

Die erste Funktion sucht nach dem ersten Byte in der Maske, das nicht null ist, und gibt ihren Index beginnend von links zurück.

Beispiel für 64bit, xx bedeutet "beliebiges Byte" und "nn" bedeutet "Nicht-Null-Byte":

Ich hätte diese Funktion find_first_significant_byte_index() genannt, wenn nicht für den letzten mehrdeutigen Fall ...

Die zweite Funktion teilt val entsprechend einer Bitmaske, speichert ihre "low_bits" in * data für weitere Referenz und gibt ein seltsames op-Ergebnis für val zurück. (Kann dieses letzte nicht sicher identifizieren).

Siehe "Die Wort-auf-Zeit-Schnittstelle": Ссылка

has_zero () gibt eine Maske ungleich Null zurück, wenn die Eingabe ein Nullbyte enthält.

find_zero () findet wo das erste Null war die Maske als Eingabe verwendet (technisch ist es nicht das Maske, aber diese Maske weiter durch zwei weitere Funktionen massiert) . find_zero () findet KEINE Null in der Eingabemaske.

Siehe Beispielverwendung in verlinktem Artikel: