Det er mange alternativer for å beregne CRC-kontrollsummen på Internett. Men hva er egentlig en kontrollsum og hvorfor beregnes den på denne måten? La oss finne ut av det.
Bruksanvisning
Trinn 1
Først, la oss få litt teori. Så hva er egentlig CRC? Kort oppsummert er dette en av variantene av kontrollsummen. Sjekksum er en metode for å kontrollere integriteten til den mottatte informasjonen på mottakersiden når den overføres over kommunikasjonskanaler. For eksempel er en av de enkleste kontrollene å bruke paritetsbiten. Dette er når alle biter i den overførte meldingen er oppsummert, og hvis summen viser seg å være jevn, blir 0 lagt til slutten av meldingen, hvis den er merkelig, så 1. Når du mottar, blir meldingsbiter telles også og sammenlignes med mottatt paritetsbit. Hvis de er forskjellige, oppstod feil under overføring, og den overførte informasjonen ble forvrengt.
Men denne metoden for å oppdage tilstedeværelsen av feil er veldig uinformativ og fungerer ikke alltid, fordi hvis flere biter av meldingen er forvrengt, kan det hende at summen ikke endres. Derfor er det mange flere "avanserte" sjekker, inkludert CRC.
Faktisk er CRC ikke en sum, men resultatet av å dele en viss mengde informasjon (informasjonsmelding) med en konstant, eller rettere sagt, resten av å dele en melding med en konstant. Imidlertid er CRC også historisk referert til som en "kontrollsum". Hver bit av meldingen bidrar til CRC-verdien. Det vil si at hvis minst en bit av den opprinnelige meldingen endres under overføring, vil kontrollsummen også endres og betydelig. Dette er et stort pluss av en slik sjekk, siden det lar deg entydig bestemme om den opprinnelige meldingen ble forvrengt under overføring eller ikke.
Steg 2
Før vi begynner å beregne CRC, er det behov for litt mer teori.
Hva er den opprinnelige meldingen, bør være klar. Det er en sammenhengende sekvens av biter av vilkårlig lengde.
Hva er konstanten der vi skal dele det originale budskapet? Dette tallet har også en hvilken som helst lengde, men vanligvis brukes multipler på 1 byte - 8, 16 og 32 bits. Det er bare lettere å telle, fordi datamaskiner fungerer med byte, ikke med biter.
Divisorkonstanten skrives vanligvis som et polynom (polynom) slik: x ^ 8 + x ^ 2 + x ^ 1 + x ^ 0. Her betyr graden av tallet "x" posisjonen til en-biten i tallet, startende fra null, og den mest betydningsfulle biten indikerer graden av polynomet og forkastes når tallet tolkes. Det vil si at det tidligere skrevne tallet ikke er mer enn (1) 00000111 i binær, eller 7 i desimal. I parentes angav jeg det antydede mest sifferet i tallet.
Her er et annet eksempel: x ^ 16 + x ^ 15 + x ^ 2 + x ^ 0 = (1) 1000000000000101 = 0x8005 = 32773.
Vanligvis brukes noen standardpolynomer til forskjellige typer CRC.
Trinn 3
Så hvordan beregner du kontrollsummen? Det er en grunnleggende metode - å dele en melding i et polynom "head-on" - og dens modifikasjoner for å redusere antall beregninger og dermed øke hastigheten på CRC-beregningen. Vi vil se på den grunnleggende metoden.
Generelt blir divisjonen av et tall med et polynom utført i henhold til følgende algoritme:
1) en matrise (register) opprettes, fylt med nuller, like lange som polynombredden;
2) den opprinnelige meldingen suppleres med nuller i de minst signifikante bitene, i en mengde som er lik antall polynomets bits;
3) en mest signifikant bit av meldingen blir lagt inn i den minst signifikante biten i registeret, og en bit flyttes fra den viktigste biten i registeret;
4) hvis den utvidede biten er lik "1", så er bitene invertert (XOR-operasjon, eksklusiv OR) i de registerbitene som tilsvarer de i polynomet;
5) hvis det fremdeles er biter i meldingen, gå til trinn 3);
6) når alle bitene av meldingen kom inn i registeret og ble behandlet av denne algoritmen, forblir resten av delingen i registeret, som er CRC-kontrollsummen.
Figuren illustrerer inndelingen av den originale bitsekvensen med tallet (1) 00000111, eller polynomet x ^ 8 + x ^ 2 + x ^ 1 + x ^ 0.
Trinn 4
Det er et par ekstra detaljer igjen. Som du kanskje har lagt merke til, kan meldingen deles med hvilket som helst tall. Hvordan velge det? Det er en rekke standard polynomer som brukes til å beregne CRC. For eksempel kan det være 0x04C11DB7 for CRC32, og for CRC16 kan det være 0x8005.
I tillegg kan du i registeret i begynnelsen av beregningen ikke skrive nuller, men noe annet tall.
I løpet av beregningene, rett før utstedelse av den endelige CRC-kontrollsummen, kan de også deles med et annet nummer.
Og det siste. Bytes av meldingen når du skriver til registeret kan plasseres som den viktigste biten "fremover", og omvendt, den minst viktige.
Trinn 5
Basert på alt ovenfor, la oss skrive en Basic. NET-funksjon som beregner CRC-kontrollsummen ved å ta et antall parametere som jeg beskrev ovenfor og returnere CRC-verdien som et 32-biters usignert nummer.
Offentlig delt funksjon GetCrc (ByVal bytes As Byte (), ByVal poly Som Uteger, Valgfri ByVal-bredde Som Integer = 32, Valgfri ByVal initReg As UInteger = & HFFFFFFFFUI, Valgfri ByVal finalXor Som UInteger = & HFFFFFFFFUI, Valgfri ByVal reversBytes, reverseCrc som boolsk = sann) som heltall
Dim widthInBytes As Integer = width / 8
'Suppler meldingsbredden med nuller (beregning i byte):
ReDim Bevar byte (byte. Lengde - 1 + breddeInBytes)
'Lag litt kø fra meldingen:
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 Da
For jeg som heltall = 0 til 7
msgFifo. Enqueue (ba (i))
Neste
Ellers
For i som heltall = 7 til 0 trinn -1
msgFifo. Enqueue (ba (i))
Neste
Slutt om
Neste
'Lag en kø fra de første fyllbiter i registeret:
Dim initBytes As Byte () = BitConverter. GetBytes (initReg)
Dim initBytesReversed As IEnumerable (Of Byte) = (From b As Byte In initBytes Take widthInBytes).
Dim initFifo As New Queue (Of Boolean) (bredde - 1)
For hver b som byte i initBytesReversed
Dim ba som ny BitArray ({b})
Hvis ikke reverseBytes Da
For jeg som heltall = 0 til 7
initFifo. Enqueue (ba (i))
Neste
Ellers
For i som heltall = 7 til 0 trinn -1
initFifo. Enqueue (ba (i))
Neste
Slutt om
Neste
'Skift og XOR:
Dim register Som UInteger = 0 'fyll bredde-bit registeret med nuller.
Gjør mens msgFifo. Count> 0
Dim poppedBit As Integer = CInt (register >> (bredde - 1)) Og 1 'definerer 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
Slutt om
register = register << 1
register = register Eller shiftedBit
Hvis poppedBit = 1 Da
register = register Xor poly
Slutt om
Løkke
'Endelige konverteringer:
Dim crc As UInteger = register 'Registeret inneholder resten av divisjonen == sjekksum.
Hvis reverseCrc Da
crc = reflekterer (crc, bredde)
Slutt om
crc = crc Xor finalXor
crc = crc Og (& HFFFFFFFFUI >> (32 - bredde)) 'maskerer de minst viktige bitene.
Retur crc
Sluttfunksjon
