Der er mange muligheder for beregning af CRC-kontrolsummen på Internettet. Men hvad er nøjagtigt et kontrolsum, og hvorfor beregnes det på denne måde? Lad os finde ud af det.
Instruktioner
Trin 1
Lad os først få en smule teori. Så hvad er CRC præcist? Kort sagt er dette en af varianterne af beregning af checksum. Kontrolsum er en metode til at kontrollere integriteten af den modtagne information på modtagersiden, når der sendes over kommunikationskanaler. For eksempel er en af de enkleste kontroller at bruge paritetsbiten. Dette er når alle bits i den transmitterede meddelelse opsummeres, og hvis summen viser sig at være jævn, tilføjes 0 til slutningen af meddelelsen, hvis den er ulige, så 1. Når du modtager, bliver summen af meddelelsesbits tælles også og sammenlignes med den modtagne paritetsbit. Hvis de adskiller sig, opstod der fejl under transmission, og de transmitterede oplysninger blev forvrænget.
Men denne metode til at detektere tilstedeværelsen af fejl er meget uinformativ og fungerer ikke altid, fordi hvis flere bits i meddelelsen er forvrænget, ændres summen muligvis ikke. Derfor er der mange flere "avancerede" checks, herunder CRC.
Faktisk er CRC ikke en sum, men resultatet af at dividere en bestemt mængde information (informationsmeddelelse) med en konstant, eller rettere, resten af at dividere en besked med en konstant. Imidlertid kaldes CRC historisk også som en "kontrolsum". Hver bit af meddelelsen bidrager til CRC-værdien. Det vil sige, at hvis mindst en bit af den oprindelige besked ændres under transmission, vil kontrolsummen også ændre sig og væsentligt. Dette er et stort plus af en sådan kontrol, da det giver dig mulighed for entydigt at afgøre, om den oprindelige besked var forvrænget under transmission eller ej.
Trin 2
Før vi begynder at beregne CRC, er der brug for lidt mere teori.
Hvad der er den oprindelige meddelelse skal være klar. Det er en sammenhængende sekvens af bits med vilkårlig længde.
Hvad er den konstante, hvormed vi skal dele den oprindelige besked? Dette tal har også en hvilken som helst længde, men der bruges normalt multipla på 1 byte - 8, 16 og 32 bits. Det er bare lettere at tælle, fordi computere arbejder med bytes, ikke med bits.
Divisorkonstanten skrives normalt som et polynom (polynom) som dette: x ^ 8 + x ^ 2 + x ^ 1 + x ^ 0. Her betyder graden af tallet "x" positionen af en-bit i tallet startende fra nul, og den mest betydningsfulde bit angiver graden af polynomet og kasseres, når tallet fortolkes. Det vil sige, det tidligere skrevne tal er intet mere end (1) 00000111 i binær eller 7 i decimal. I parentes angav jeg det antydede mest betydningsfulde tal i nummeret.
Her er et andet eksempel: x ^ 16 + x ^ 15 + x ^ 2 + x ^ 0 = (1) 1000000000000101 = 0x8005 = 32773.
Normalt bruges nogle standardpolynomer til forskellige typer CRC'er.
Trin 3
Så hvordan beregner du kontrolsummen? Der er en grundlæggende metode - opdeling af en besked i et polynom "head-on" - og dens ændringer for at reducere antallet af beregninger og følgelig fremskynde CRC-beregningen. Vi vil se på den grundlæggende metode.
Generelt udføres delingen af et tal med et polynom i henhold til følgende algoritme:
1) der oprettes en matrix (register), fyldt med nuller, der er lig med længden af polynombredden;
2) den oprindelige meddelelse suppleres med nuller i de mindst signifikante bits i en mængde svarende til antallet af bit i polynomet;
3) en mest signifikant bit af meddelelsen indtastes i den mindst signifikante bit af registret, og en bit flyttes fra den mest betydningsfulde bit af registret;
4) hvis den udvidede bit er lig med "1", så er bitene inverteret (XOR-operation, eksklusiv OR) i de registerbits, der svarer til dem i polynomet;
5) hvis der stadig er bits i meddelelsen, skal du gå til trin 3);
6) når alle bitene i meddelelsen trådte ind i registret og blev behandlet af denne algoritme, forbliver resten af divisionen i registret, som er CRC-kontrolsummen.
Figuren illustrerer delingen af den originale bitsekvens med tallet (1) 00000111 eller polynomet x ^ 8 + x ^ 2 + x ^ 1 + x ^ 0.
Trin 4
Der er et par ekstra hånd tilbage. Som du måske har bemærket, kan meddelelsen deles med et hvilket som helst tal. Hvordan vælger jeg det? Der er et antal standardpolynomer, der bruges til at beregne CRC. For eksempel kan det for CRC32 være 0x04C11DB7, og for CRC16 kan det være 0x8005.
Derudover kan du i registret i begyndelsen af beregningen ikke skrive nuller, men noget andet nummer.
Under beregninger kan de lige inden udstedelsen af den endelige CRC-kontrolsum divideres med et andet nummer.
Og den sidste ting. Bytes af meddelelsen, når du skriver til registret, kan placeres som den mest betydningsfulde bit "fremad", og omvendt, den mindst signifikante.
Trin 5
Baseret på alt det ovenstående, lad os skrive en Basic. NET-funktion, der beregner CRC-kontrolsummen ved at tage et antal parametre, som jeg beskrev ovenfor, og returnere CRC-værdien som et 32-bit usigneret nummer.
Offentlig delt funktion GetCrc (ByVal-byte som byte (), ByVal poly som heltal, valgfri byval-bredde som heltal = 32, valgfri ByVal-initReg som U-heltal = & HFFFFFFFFUI, valgfri ByVal finalXor som U-heltal = & HFFFFFFFFUI, Valgfri ByVal-omvendt byte, reverseCrc As Boolean = True) Som UInteger
Dim widthInBytes As Integer = width / 8
'Suppler beskedbredden med nuller (beregning i byte):
ReDim Bevar bytes (bytes. Længde - 1 + breddeInBytes)
'Opret en smule kø fra meddelelsen:
Dim msgFifo As New Queue (Of Boolean) (bytes. Count * 8-1)
For hver b som byte i byte
Dim ba som ny BitArray ({b})
Hvis reverseBytes Så
For jeg som heltal = 0 til 7
msgFifo. Enqueue (ba (i))
Næste
Andet
For i som heltal = 7 til 0 trin -1
msgFifo. Enqueue (ba (i))
Næste
Afslut Hvis
Næste
'Opret en kø fra de første udfyldningsbits i registret:
Dim initBytes As Byte () = BitConverter. GetBytes (initReg)
Dim initBytesReversed As IEnumerable (Of Byte) = (From b As Byte In initBytes Tag widthInBytes).
Dim initFifo som ny kø (af boolsk) (bredde - 1)
For hver b som byte i initBytesReversed
Dim ba som ny BitArray ({b})
Hvis ikke reverseBytes Så
For jeg som heltal = 0 til 7
initFifo. Enqueue (ba (i))
Næste
Andet
For i som heltal = 7 til 0 trin -1
initFifo. Enqueue (ba (i))
Næste
Afslut Hvis
Næste
'Skift og XOR:
Dim register Som UInteger = 0 'udfyld bredde-bit registeret med nuller.
Gør mens msgFifo. Count> 0
Dim poppedBit As Integer = CInt (register >> (bredde - 1)) Og 1 'defineres før skiftregister.
Dim shiftedBit As Byte = Convert. ToByte (msgFifo. Dequeue)
Hvis initFifo. Count> 0 Så
Dim b As Byte = Convert. ToByte (initFifo. Dequeue)
shiftedBit = shiftedBit Xeller b
Afslut Hvis
register = register << 1
register = register Eller shiftedBit
Hvis poppedBit = 1 Så
register = register Xor poly
Afslut Hvis
Sløjfe
'Endelige konverteringer:
Dim crc As UInteger = register 'Registeret indeholder resten af divisionen == kontrolsum.
Hvis reverseCrc Derefter
crc = reflekterer (crc, bredde)
Afslut Hvis
crc = crc Xeller endeligXor
crc = crc Og (& HFFFFFFFFUI >> (32 - bredde)) 'maskerer de mindst signifikante bits.
Retur crc
Afslut funktion
