Det finns många alternativ för att beräkna CRC-kontrollsumman på Internet. Men vad är en kontrollsumma exakt och varför beräknas den på detta sätt? Låt oss ta reda på det.
Instruktioner
Steg 1
Låt oss först få lite teori. Så vad är CRC exakt? Kort sagt, detta är en av varianterna av kontrollsumma. Kontrollsumma är en metod för att kontrollera integriteten hos den mottagna informationen på mottagarsidan vid sändning över kommunikationskanaler. Till exempel är en av de enklaste kontrollerna att använda paritetsbiten. Detta är när alla bitar i det överförda meddelandet summeras, och om summan visar sig vara jämn, läggs 0 till i slutet av meddelandet, om det är udda, då 1. Vid mottagning kommer summan av meddelandebitar räknas också och jämförs med den mottagna paritetsbiten. Om de skiljer sig uppstod fel under överföringen och den överförda informationen förvrängdes.
Men den här metoden för att upptäcka förekomsten av fel är mycket informativ och fungerar inte alltid, för om flera bitar av meddelandet är förvrängda, kan paritet av summan kanske inte ändras. Därför finns det många fler "avancerade" kontroller, inklusive CRC.
I själva verket är CRC inte en summa, utan resultatet av att dela en viss mängd information (informationsmeddelande) med en konstant, eller snarare, resten av att dela ett meddelande med en konstant. CRC kallas dock historiskt också för en "kontrollsumma". Varje bit av meddelandet bidrar till CRC-värdet. Det vill säga om åtminstone en bit av det ursprungliga meddelandet ändras under överföringen kommer kontrollsumman också att ändras och betydligt. Detta är ett stort plus av en sådan kontroll, eftersom det låter dig entydigt avgöra om det ursprungliga meddelandet förvrängdes under sändningen eller inte.
Steg 2
Innan vi börjar beräkna CRC behövs lite mer teori.
Vad som är det ursprungliga meddelandet ska vara tydligt. Det är en sammanhängande sekvens av bitar med godtycklig längd.
Vad är den konstant genom vilken vi bör dela det ursprungliga meddelandet? Detta antal har också valfri längd, men vanligtvis används multiplar om 1 byte - 8, 16 och 32 bitar. Det är bara lättare att räkna, eftersom datorer arbetar med byte, inte med bitar.
Delarkonstanten skrivs vanligtvis som ett polynom (polynom) så här: x ^ 8 + x ^ 2 + x ^ 1 + x ^ 0. Här betyder graden av talet "x" positionen för enbiten i talet, med början från noll, och den mest signifikanta biten indikerar graden av polynom och kasseras när talet tolkas. Det vill säga det tidigare skrivna numret är inget mer än (1) 00000111 i binär eller 7 i decimal. Inom parentes indikerade jag den underförstådda siffran för den viktigaste siffran.
Här är ett annat exempel: x ^ 16 + x ^ 15 + x ^ 2 + x ^ 0 = (1) 1000000000000101 = 0x8005 = 32773.
Vanligtvis används vissa standardpolynom för olika typer av CRC.
Steg 3
Så hur beräknar du kontrollsumman? Det finns en grundläggande metod - att dela upp ett meddelande i ett polynom "head-on" - och dess modifieringar för att minska antalet beräkningar och därmed påskynda CRC-beräkningen. Vi kommer att titta på den grundläggande metoden.
I allmänhet utförs delningen av ett tal med ett polynom enligt följande algoritm:
1) en matris (register) skapas, fylld med nollor, lika långa som längden på polynombredden;
2) det ursprungliga meddelandet kompletteras med nollor i de minst signifikanta bitarna, i en mängd som är lika med antalet bitar i polynomet;
3) en viktigaste bit av meddelandet matas in i registerets minst signifikanta bit, och en bit flyttas från den viktigaste biten i registret;
4) om den utökade biten är lika med "1", så är bitarna inverterade (XOR-operation, exklusiv ELLER) i de registerbitar som motsvarar de i polynomet;
5) om det fortfarande finns bitar i meddelandet, gå till steg 3);
6) när alla bitar av meddelandet kom in i registret och bearbetades av denna algoritm, återstår resten av uppdelningen i registret, vilket är CRC-kontrollsumman.
Figuren illustrerar uppdelningen av den ursprungliga bitsekvensen med numret (1) 00000111 eller polynomet x ^ 8 + x ^ 2 + x ^ 1 + x ^ 0.
Steg 4
Det finns ett par ytterligare detaljer kvar. Som du kanske har märkt kan meddelandet delas med valfritt nummer. Hur väljer man det? Det finns ett antal standardpolynom som används för att beräkna CRC. Till exempel för CRC32 kan det vara 0x04C11DB7 och för CRC16 kan det vara 0x8005.
Dessutom kan du i registret i början av beräkningen inte skriva nollor utan något annat nummer.
Vid beräkningar, direkt före utfärdandet av den slutliga CRC-kontrollsumman, kan de också delas med något annat nummer.
Och det sista. Bytes av meddelandet när du skriver till registret kan placeras som den viktigaste biten "framåt", och vice versa, den minst signifikanta.
Steg 5
Baserat på allt ovan, låt oss skriva en Basic. NET-funktion som beräknar CRC-kontrollsumman genom att ta ett antal parametrar som jag beskrivit ovan och returnera CRC-värdet som ett 32-bitars osignerat nummer.
Offentlig delad funktion GetCrc (ByVal-byte som byte (), ByVal poly som heltal, valfri byval-bredd som heltal = 32, valfri ByVal-initReg som UInteger = & HFFFFFFFFUI, valfri ByVal finalXor som UInteger = & HFFFFFFFFUI, valfri ByVal-omvända byte, reverseCrc As Boolean = True) Som heltal
Dim breddInBytes som heltal = bredd / 8
'Komplettera meddelandets bredd med nollor (beräkning i byte):
ReDim Bevara byte (bytes. Length - 1 + widthInBytes)
'Skapa lite kö från meddelandet:
Dim msgFifo As New Queue (Of Boolean) (bytes. Count * 8 - 1)
För varje b som byte i byte
Dim ba som ny BitArray ({b})
Om reverseBytes Då
För jag som heltal = 0 till 7
msgFifo. Enqueue (ba (i))
Nästa
Annan
För i som heltal = 7 till 0 steg -1
msgFifo. Enqueue (ba (i))
Nästa
Avsluta om
Nästa
'Skapa en kö från de ursprungliga fyllbitarna i registret:
Dim dimBytes 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) (bredd - 1)
För varje b som byte i initBytesReversed
Dim ba som ny BitArray ({b})
Om inte reverseBytes då
För jag som heltal = 0 till 7
initFifo. Enqueue (ba (i))
Nästa
Annan
För i som heltal = 7 till 0 steg -1
initFifo. Enqueue (ba (i))
Nästa
Avsluta om
Nästa
'Skift och XOR:
Dimregistrera som UInteger = 0 ', fyll breddbitsregistret med nollor.
Gör medan msgFifo. Count> 0
Dim poppedBit As Integer = CInt (register >> (bredd - 1)) Och 1 'definieras före skiftregister.
Dim shiftedBit As Byte = Convert. ToByte (msgFifo. Dequeue)
Om initFifo. Count> 0 Då
Dim b As Byte = Convert. ToByte (initFifo. Dequeue)
shiftedBit = shiftedBit Xeller b
Avsluta om
registrera = registrera << 1
register = register Eller shiftedBit
Om poppedBit = 1 Då
register = register Xor poly
Avsluta om
Slinga
'Slutliga omvandlingar:
Dim crc As UInteger = register 'Registret innehåller resten av divisionen == kontrollsumma.
Om reverseCrc Då
crc = reflektera (crc, bredd)
Avsluta om
crc = crc Xor finalXor
crc = crc Och (& HFFFFFFFFUI >> (32 - bredd)) 'maskerar de minst betydande bitarna.
Retur crc
Slutfunktion
