Für die Berechnung der CRC-Prüfsumme gibt es im Internet viele Möglichkeiten. Aber was genau ist eine Prüfsumme und warum wird sie so berechnet? Lass es uns herausfinden.
Anleitung
Schritt 1
Kommen wir zunächst ein wenig zur Theorie. Was genau ist CRC? Kurz gesagt, dies ist eine der Varianten der Prüfsummenberechnung. Prüfsumme ist ein Verfahren zur Überprüfung der Integrität der empfangenen Informationen auf der Empfängerseite bei der Übertragung über Kommunikationskanäle. Eine der einfachsten Prüfungen besteht beispielsweise darin, das Paritätsbit zu verwenden. Dies ist der Fall, wenn alle Bits der übertragenen Nachricht aufsummiert werden, und wenn die Summe gerade ist, wird 0 an das Ende der Nachricht angehängt, wenn sie ungerade ist, dann 1. Beim Empfang wird die Summe der Nachrichtenbits werden ebenfalls gezählt und mit dem empfangenen Paritätsbit verglichen. Unterscheiden sie sich, so traten Fehler bei der Übertragung auf und die übertragenen Informationen waren verzerrt.
Diese Methode zur Erkennung von Fehlern ist jedoch sehr informativ und funktioniert nicht immer, weil wenn mehrere Bits der Nachricht verzerrt sind, kann sich die Parität der Summe nicht ändern. Daher gibt es viele weitere "fortgeschrittene" Prüfungen, einschließlich CRC.
Tatsächlich ist CRC keine Summe, sondern das Ergebnis der Division einer bestimmten Informationsmenge (Informationsnachricht) durch eine Konstante oder vielmehr der Rest einer Division einer Nachricht durch eine Konstante. Die CRC wird jedoch historisch auch als "Prüfsumme" bezeichnet. Jedes Bit der Nachricht trägt zum CRC-Wert bei. Das heißt, wenn sich während der Übertragung mindestens ein Bit der ursprünglichen Nachricht ändert, ändert sich auch die Prüfsumme, und zwar erheblich. Dies ist ein großes Plus einer solchen Überprüfung, da Sie damit eindeutig feststellen können, ob die ursprüngliche Nachricht während der Übertragung verzerrt wurde oder nicht.
Schritt 2
Bevor wir mit der Berechnung des CRC beginnen, ist noch etwas mehr Theorie erforderlich.
Was ist die ursprüngliche Nachricht sollte klar sein. Es ist eine zusammenhängende Folge von Bits beliebiger Länge.
Durch welche Konstante sollten wir die ursprüngliche Nachricht teilen? Diese Zahl ist ebenfalls beliebig lang, aber normalerweise werden Vielfache von 1 Byte verwendet - 8, 16 und 32 Bit. Es ist nur einfacher zu zählen, weil Computer mit Bytes arbeiten, nicht mit Bits.
Die Teilerkonstante wird normalerweise als Polynom (Polynom) wie folgt geschrieben: x ^ 8 + x ^ 2 + x ^ 1 + x ^ 0. Der Grad der Zahl "x" bedeutet hier die Position des Eins-Bits in der Zahl, beginnend bei Null, und das höchstwertige Bit gibt den Grad des Polynoms an und wird bei der Interpretation der Zahl verworfen. Das heißt, die zuvor geschriebene Zahl ist nichts anderes als (1) 00000111 in binärer Form oder 7 in dezimaler Form. In Klammern habe ich die implizite höchstwertige Ziffer der Zahl angegeben.
Hier ist ein weiteres Beispiel: x ^ 16 + x ^ 15 + x ^ 2 + x ^ 0 = (1) 1000000000000101 = 0x8005 = 32773.
Normalerweise werden einige Standardpolynome für verschiedene Arten von CRCs verwendet.
Schritt 3
Wie berechnet man die Prüfsumme? Es gibt ein grundlegendes Verfahren - das Aufteilen einer Nachricht in ein Polynom "frontal" - und seine Modifikationen, um die Anzahl der Berechnungen zu reduzieren und dementsprechend die CRC-Berechnung zu beschleunigen. Wir werden uns die grundlegende Methode ansehen.
Im Allgemeinen wird die Division einer Zahl durch ein Polynom nach folgendem Algorithmus durchgeführt:
1) ein mit Nullen gefülltes Array (Register) wird erstellt, dessen Länge der Länge der Polynombreite entspricht;
2) die ursprüngliche Nachricht wird mit Nullen in den niedrigstwertigen Bits in einer Menge gleich der Anzahl der Bits des Polynoms ergänzt;
3) ein höchstwertiges Bit der Nachricht wird in das niedrigstwertige Bit des Registers eingegeben und ein Bit wird aus dem höchstwertigen Bit des Registers verschoben;
4) wenn das erweiterte Bit gleich "1" ist, dann werden die Bits in denjenigen Registerbits invertiert (XOR-Operation, exklusives ODER), die denen im Polynom entsprechen;
5) wenn noch Bits in der Nachricht vorhanden sind, gehe zu Schritt 3);
6) Wenn alle Bits der Nachricht in das Register eingetreten sind und von diesem Algorithmus verarbeitet wurden, verbleibt der Rest der Division im Register, das ist die CRC-Prüfsumme.
Die Abbildung veranschaulicht die Division der ursprünglichen Bitfolge durch die Zahl (1) 00000111 oder das Polynom x ^ 8 + x ^ 2 + x ^ 1 + x ^ 0.
Schritt 4
Es gibt noch ein paar zusätzliche Berührungen. Wie Sie vielleicht bemerkt haben, kann die Nachricht durch eine beliebige Zahl geteilt werden. Wie wählt man es aus? Es gibt eine Reihe von Standardpolynomen, die verwendet werden, um den CRC zu berechnen. Für CRC32 könnte es beispielsweise 0x04C11DB7 sein und für CRC16 könnte es 0x8005 sein.
Außerdem können Sie in das Register zu Beginn der Berechnung keine Nullen, sondern eine andere Zahl schreiben.
Außerdem können sie während der Berechnungen unmittelbar vor der Ausgabe der endgültigen CRC-Prüfsumme durch eine andere Zahl geteilt werden.
Und das Letzte. Bytes der Nachricht beim Schreiben in das Register können als höchstwertiges Bit "vorwärts" und umgekehrt als niedrigstwertiges Bit platziert werden.
Schritt 5
Lassen Sie uns auf der Grundlage all dessen eine Basic. NET-Funktion schreiben, die die CRC-Prüfsumme berechnet, indem eine Reihe von Parametern verwendet wird, die ich oben beschrieben habe, und den CRC-Wert als 32-Bit-Zahl ohne Vorzeichen zurückgibt.
Public Shared Function GetCrc (ByVal bytes As Byte (), ByVal poly As UInteger, Optional ByVal width As Integer = 32, Optional ByVal initReg As UInteger = & HFFFFFFFFUI, Optional ByVal finalXor As UInteger = & HFFFFFFFUI, Optional ByVal reverseBytes, Optional Boolean ByVal reverseCrc As Boolean = True) As UInteger
Dim widthInBytes As Integer = width / 8
'Nachrichtenbreite mit Nullen ergänzen (Berechnung in Byte):
ReDim Preserve bytes (bytes. Length - 1 + widthInBytes)
'Erzeuge eine Bit-Warteschlange aus der Nachricht:
Dim msgFifo als neue Warteschlange (von Boolean) (bytes. Count * 8 - 1)
Für jedes b als Byte in Bytes
Dim ba als neues BitArray ({b})
Wenn reverseBytes Dann
Für i As Integer = 0 bis 7
msgFifo. Enqueue (ba (i))
Nächster
Anders
Für i As Integer = 7 bis 0 Schritt -1
msgFifo. Enqueue (ba (i))
Nächster
Ende Wenn
Nächster
'Erzeuge eine Warteschlange aus den anfänglichen Füllbits des Registers:
Dim initBytes As Byte () = BitConverter. GetBytes (initReg)
Dim initBytesReversed As IEnumerable (Of Byte) = (From b As Byte In initBytes Take widthInBytes). Reverse
Dim initFifo als neue Warteschlange (von Boolean) (Breite - 1)
Für jedes b als Byte in initBytesReversed
Dim ba als neues BitArray ({b})
Wenn nicht reverseBytes Then
Für i As Integer = 0 bis 7
initFifo. Enqueue (ba (i))
Nächster
Anders
Für i As Integer = 7 bis 0 Schritt -1
initFifo. Enqueue (ba (i))
Nächster
Ende Wenn
Nächster
'Shift und XOR:
Dim register As UInteger = 0 'fülle das Breite-Bit-Register mit Nullen.
Tun Sie, während msgFifo. Count> 0
Dim poppedBit As Integer = CInt (Register >> (Breite - 1)) und 1 'vor Schieberegister definieren.
Dim shiftedBit As Byte = Convert. ToByte (msgFifo. Dequeue)
Wenn initFifo. Count> 0 Then
Dim b As Byte = Convert. ToByte (initFifo. Dequeue)
shiftedBit = shiftedBit Xor b
Ende Wenn
registrieren = registrieren << 1
register = register Oder shiftedBit
Wenn poppedBit = 1 Dann
registrieren = registrieren Xor poly
Ende Wenn
Schleife
'Endgültige Konvertierungen:
Dim crc As UInteger = register 'Das Register enthält den Rest der Division == Prüfsumme.
Wenn umgekehrtCrc Dann
crc = reflektieren (crc, Breite)
Ende Wenn
crc = crc Xor finalXor
crc = crc And (& HFFFFFFFFUI >> (32 - Breite)) 'maskieren Sie die niedrigstwertigen Bits.
Rücklauf crc
Endfunktion
