Was macht die Maskenvariable in dieser CRC-Prüfsummenberechnung?

Question

Die Frage bezieht sich auf Code in Abbildung 14-6 in here.

wird die Maske wie folgt berechnet:

mask = -(crc & 1) 

Warum wir & crc mit 1 und dann Ergebnis negativ machen? Die Abbildung 14-5 hat diese Maskenvariable nicht, warum?

Edit:

So, da dieser Punkt klar ist, warum haben wir diese Linie auch:

crc = crc^byte; 

Diese Linie ist nicht in Abbildung 14-5.

Kann dieses Programm verwendet werden, wenn die Generatorpolynomlänge nicht ein Vielfaches von 8 Bits ist?

Answer 1

Was das ist, ist das niedrigstwertige Bit von crc zu überprüfen und dann zu negieren. Der Effekt ist, dass, wenn das Bit Null ist, mask Null ist (das sind alles Nullen) und wenn das Bit eins ist, wird mask-1 sein (das sind alle Einsen). Dies wird verwendet, um xor mit 0xEDB88320 bedingt. Die andere Lösung verwendet stattdessen if, um diese Bedingung zu erfüllen.

Der zweite Trick, den sie in der zweiten Lösung verwenden, besteht darin, den XOR für die Bitprüfung in einem Vorgang für alle acht Bits auszuführen. Im ersten Beispiel verwenden sie (int)(crc^byte) < 0 (was eine Prüfung auf das XOR des höchstwertigen Bits oder des Vorzeichenbits bedeutet), sie verschieben dann sowohl crc als auch byte ein Bit nach links und machen dasselbe auf dem nächsten Bit. Im zweiten Beispiel führen sie das XOR acht Bits gleichzeitig aus und prüfen dann jedes Bit des Ergebnisses.

Um zu sehen, was passiert, betrachten, wenn wir das erste Beispiel zu ändern:

for(j=0; j<=7; j++) { 
    crc = crc^mask_sign_bit(byte); 
    if((int)crc < 0) 
     crc = (crc << 1)^0x04C11DB7; 
    else 
     crc = crc << 1; 
    byte = byte << 1; 
} 

wo mask_sign_bit Masken, außer dem Vorzeichenbit jedes Bit, wird das Zeichen crc^byte die gleiche wie crc^mask_sign_bit(byte) so die Folge der if Anweisung wird gleich. Wenn dann crc nach links verschoben wird, geht das durch crc = crc^mask_sign_bit(byte) geänderte Bit verloren.

Answer 2

Diese Operation wandelt das niedrigstwertige Bit in eine Maske um.

beispielsweise für einen 8-Bit-Wert (der Einfachheit halber) haben wir:

00000000 -> 00000000 
00000001 -> 11111111 

unären Minus- verkompliziert die Schaltung der CRC-Funktion massiv, die sonst keine Additionen erfordert. Es kann als Funktion der Addition implementiert werden, wie

-x = ~x + 1 

Einige Architekturen folgt möglicherweise ein Bitvektor „broadcast“ Operation unterstützen, die am wenigsten signifikanten Bits für alle anderen Bits zu senden, die enorme Leistungssteigerung geben.