Er zijn veel opties voor het berekenen van de CRC-controlesom op internet. Maar wat is een controlesom precies en waarom wordt deze op deze manier berekend? Laten we het uitzoeken.
instructies:
Stap 1
Laten we eerst een beetje theorie krijgen. Dus wat is CRC precies? Kortom, dit is een van de varianten van checksum-berekening. Checksum is een methode om de integriteit van de ontvangen informatie aan de ontvangerzijde te controleren bij het verzenden via communicatiekanalen. Een van de eenvoudigste controles is bijvoorbeeld het gebruik van de pariteitsbit. Dit is wanneer alle bits van het verzonden bericht worden opgeteld, en als de som even blijkt te zijn, wordt 0 aan het einde van het bericht toegevoegd, als het oneven is, dan 1. Bij ontvangst wordt de som van de berichtbits worden ook geteld en vergeleken met de ontvangen pariteitsbit. Als ze verschillen, zijn er fouten opgetreden tijdens de verzending en is de verzonden informatie vervormd.
Maar deze methode om de aanwezigheid van fouten te detecteren is erg weinig informatief en werkt niet altijd, omdat als meerdere bits van het bericht vervormd zijn, kan de pariteit van de som niet veranderen. Daarom zijn er veel meer "geavanceerde" controles, waaronder CRC.
In feite is CRC geen som, maar het resultaat van het delen van een bepaalde hoeveelheid informatie (informatiebericht) door een constante, of liever, de rest van het delen van een bericht door een constante. De CRC wordt echter historisch ook wel een "checksum" genoemd. Elk bit van het bericht draagt bij aan de CRC-waarde. Dat wil zeggen, als ten minste één bit van het originele bericht verandert tijdens verzending, zal de controlesom ook veranderen, en aanzienlijk. Dit is een groot pluspunt van zo'n controle, omdat je hiermee ondubbelzinnig kunt bepalen of het originele bericht tijdens het verzenden is vervormd of niet.
Stap 2
Voordat we beginnen met het berekenen van de CRC, is er wat meer theorie nodig.
Wat de oorspronkelijke boodschap is, moet duidelijk zijn. Het is een aaneengesloten reeks bits van willekeurige lengte.
Wat is de constante waardoor we de oorspronkelijke boodschap moeten delen? Dit nummer is ook van elke lengte, maar meestal worden veelvouden van 1 byte gebruikt - 8, 16 en 32 bits. Het is gewoon makkelijker te tellen, omdat computers met bytes werken, niet met bits.
De delerconstante wordt meestal geschreven als een polynoom (polynoom) als volgt: x ^ 8 + x ^ 2 + x ^ 1 + x ^ 0. Hier betekent de graad van het getal "x" de positie van de ene bit in het getal, beginnend bij nul, en de meest significante bit geeft de graad van de polynoom aan en wordt weggegooid bij het interpreteren van het getal. Dat wil zeggen, het eerder geschreven getal is niets meer dan (1) 00000111 in binair getal, of 7 in decimaal. Tussen haakjes heb ik het impliciete meest significante cijfer van het getal aangegeven.
Hier is nog een voorbeeld: x ^ 16 + x ^ 15 + x ^ 2 + x ^ 0 = (1) 1000000000000101 = 0x8005 = 32773.
Gewoonlijk worden enkele standaardpolynomen gebruikt voor verschillende soorten CRC's.
Stap 3
Dus hoe bereken je de checksum? Er is een basismethode - het verdelen van een bericht in een polynoom "head-on" - en de aanpassingen ervan om het aantal berekeningen te verminderen en dienovereenkomstig de CRC-berekening te versnellen. We zullen kijken naar de basismethode.
In het algemeen wordt de deling van een getal door een polynoom uitgevoerd volgens het volgende algoritme:
1) er wordt een array (register) gemaakt, gevuld met nullen, in lengte gelijk aan de lengte van de polynoombreedte;
2) het oorspronkelijke bericht wordt aangevuld met nullen in de minst significante bits, in een hoeveelheid die gelijk is aan het aantal bits van de polynoom;
3) één meest significante bit van het bericht wordt ingevoerd in de minst significante bit van het register, en één bit wordt verplaatst van de meest significante bit van het register;
4) als de uitgebreide bit gelijk is aan "1", dan worden de bits geïnverteerd (XOR-bewerking, exclusieve OR) in die registerbits die overeenkomen met die in de polynoom;
5) als er nog stukjes in het bericht staan, ga dan naar stap 3);
6) wanneer alle bits van het bericht het register zijn binnengekomen en door dit algoritme zijn verwerkt, blijft de rest van de deling in het register, wat de CRC-controlesom is.
De afbeelding illustreert de verdeling van de oorspronkelijke bitreeks door het getal (1) 00000111, of de polynoom x ^ 8 + x ^ 2 + x ^ 1 + x ^ 0.
Stap 4
Er zijn nog een paar extra details. Zoals je misschien hebt gemerkt, kan het bericht worden gedeeld door een willekeurig getal. Hoe het te kiezen? Er zijn een aantal standaardpolynomen die worden gebruikt om de CRC te berekenen. Voor CRC32 kan het bijvoorbeeld 0x04C11DB7 zijn en voor CRC16 kan het 0x8005 zijn.
Bovendien kunt u in het register aan het begin van de berekening geen nullen schrijven, maar een ander getal.
Ook kunnen ze tijdens berekeningen, vlak voordat de definitieve CRC-controlesom wordt uitgegeven, worden gedeeld door een ander getal.
En het laatste. Bytes van het bericht bij het schrijven naar het register kunnen worden geplaatst als de meest significante bit "forward", en vice versa, de minst significante.
Stap 5
Laten we op basis van al het bovenstaande een Basic. NET-functie schrijven die de CRC-controlesom berekent door een aantal parameters te nemen die ik hierboven heb beschreven en de CRC-waarde terug te geven als een 32-bits niet-ondertekend getal.
Public Shared Function GetCrc (ByVal bytes As Byte (), ByVal poly As UInteger, Optioneel ByVal breedte As Integer = 32, Optioneel ByVal initReg As UInteger = & HFFFFFFFFUI, Optioneel ByVal finalXor As UInteger = & HFFFFFFFFUI, Optioneel ByVal reverseBytesal, Optioneel Boolean Bytesal reverseCrc As Boolean = True) As UInteger
Dim widthInBytes As Integer = width / 8
'Vul de berichtbreedte aan met nullen (berekening in bytes):
ReDim Behoud bytes (bytes. Length - 1 + widthInBytes)
'Maak een bitwachtrij van het bericht:
Dim msgFifo als nieuwe wachtrij (van Boolean) (bytes. Count * 8 - 1)
Voor elke b Als byte in bytes
Dim ba als nieuwe BitArray ({b})
Als reverseBytes Dan
Voor i als geheel getal = 0 tot 7
msgFifo. Enqueue (ba (i))
Volgende
Anders
Voor i als geheel getal = 7 tot 0 Stap -1
msgFifo. Enqueue (ba (i))
Volgende
Stop als
Volgende
'Maak een wachtrij van de eerste vulbits van het register:
Dim initBytes As Byte () = BitConverter. GetBytes (initReg)
Dim initBytesReversed As IEnumerable (Of Byte) = (Van b As Byte In initBytes Neem widthInBytes). Reverse
Dim initFifo als nieuwe wachtrij (van Boolean) (breedte - 1)
Voor elke b Als byte in initBytesOmgekeerd
Dim ba als nieuwe BitArray ({b})
Indien niet reverseBytes dan
Voor i als geheel getal = 0 tot 7
initFifo. Enqueue (ba (i))
Volgende
Anders
Voor i als geheel getal = 7 tot 0 Stap -1
initFifo. Enqueue (ba (i))
Volgende
Stop als
Volgende
'Shift en XOR:
Dim register As UInteger = 0 'vul het width-bit register met nullen.
Do While msgFifo. Count> 0
Dim poppedBit As Integer = CInt (register >> (breedte - 1)) En 1 'definiëren voor schuifregister.
Dim shiftedBit As Byte = Convert. ToByte (msgFifo. Dequeue)
Als initFifo. Count> 0 Dan
Dim b As Byte = Convert. ToByte (initFifo. Dequeue)
shiftedBit = shiftedBit Xor b
Stop als
registreren = registreren << 1
register = register Of shiftedBit
Als poppedBit = 1 Dan
register = register Xor poly
Stop als
Lus
'Definitieve conversies:
Dim crc As UInteger = register 'Het register bevat de rest van de deling == controlesom.
Als reverseCrc Dan
crc = reflecteren (crc, breedte)
Stop als
crc = crc Xor finalXor
crc = crc En (& HFFFFFFFFUI >> (32 - breedte)) 'masker de minst significante bits.
retour crc
Functie beëindigen
