An mehreren Stellen habe ich gelesen, dass crc32 additiv ist und so: CRC (A xor B) = CRC (A) x oder CRC (B).
Die obige Aussage wurde durch den folgenden Code, den ich geschrieben habe, widerlegt:
%Vor%Programmausgabe:
%Vor%Könnte jemand einen geeigneten Code zur Verfügung stellen, der diese Theorie beweist oder mich darauf hinweisen, wo ich versagt habe?
CRC ist additiv im mathematischen Sinne, da der CRC-Hash nur ein Restwert aus einer Übertragslosen Division aller Daten (behandelt als eine riesige ganze Zahl) dividiert durch die Polynomkonstante ist. In Ihrem Beispiel ist das ähnlich:
7 mod 5 = 2
6 mod 5 = 1
(7 mod 5) + (6 mod 5) = 3
(7 + 6) mod 5 = 3
In dieser Analogie ist "5" unser CRC-Polynom.
Hier ist ein Beispiel zum Spielen mit (gcc basiert):
%Vor%Die Ausgabe ist wie erwartet:
%Vor%Da dieser Code die Anweisung x86 CRC32 verwendet, wird er nur auf einem Intel i7 oder neuer ausgeführt. Die intrinsische Funktion nimmt den laufenden CRC-Hash als ersten Parameter und die neuen Daten als zweiten Parameter an. Der Rückgabewert ist der neue laufende CRC.
Der anfängliche laufende CRC-Wert von 0 im obigen Code ist kritisch. Wenn Sie einen anderen Anfangswert verwenden, ist CRC im praktischen Sinn nicht "additiv", weil Sie effektiv Informationen über die Ganzzahl, in die Sie einteilen, verworfen haben. Und genau das passiert in Ihrem Beispiel. CRC-Funktionen initialisieren diesen initial laufenden CRC-Wert niemals auf Null, sondern normalerweise auf -1. Der Grund dafür ist, dass ein anfänglicher CRC von 0 erlaubt, dass eine beliebige Anzahl von führenden Nullen in den Daten einfach durchfällt, ohne den laufenden CRC-Wert zu ändern, der 0. Daher ist das Initialisieren des CRC auf 0 mathematisch sinnvoll, aber für praktische Zwecke der Berechnung Hash, es ist das letzte, was du willst.
Wenn a, b und c die gleiche Länge haben, ist CRC (a) x oder CRC (b) x oder CRC (c) gleich CRC (a xor b xor c). Zurück zu Ihrer ursprünglichen Formulierung bedeutet dies, dass CRC (a xor b) gleich CRC (a) x oder CRC (b) x oder CRC (z) ist, wobei z eine Sequenz von Nullen mit der gleichen Länge wie die anderen beiden Sequenzen ist >
Dies würde bedeuten, dass jede Bitposition des CRC-Ergebnisses nur durch die äquivalente Bitposition in der Eingabe gesteuert wird. Betrachten Sie Ihr Beispiel mit B == 0.
Die Beziehung, die Sie beschreiben, trifft eher auf einige primitive xor- oder additive Prüfsummenalgorithmen zu.
Der CRC-32-Algorithmus basiert auf Polynomdivision, wobei einige zusätzliche Schritte hinzugefügt werden. Reiner Polynomrest ist additiv.
Damit meine ich: mod (poly1 + poly2, poly3) = mod (mod (poly1, poly3) + mod (poly2, poly3), poly3)
Der CRC-32-Algorithmus baut darauf auf und ist nicht additiv. Um den CRC-32 eines Byte-Arrays zu berechnen m:
Die Operation für den reinen Polynomrest ist in Schritt # 4. Es sind die Schritte 1 und 6, die den CRC-32-Algorithmus nicht additiv machen. Wenn Sie also den Effekt von Schritt 1 und 6 rückgängig machen, können Sie den CRC-32-Algorithmus als additiv modifizieren.
(Siehe auch: Python CRC-32 Probleme )