Postoji mnogo mogućnosti za izračunavanje CRC kontrolne sume na Internetu. Ali što je točno kontrolna suma i zašto se izračunava na taj način? Shvatimo to.
Upute
Korak 1
Prvo, krenimo malo u teoriju. Pa što je zapravo CRC? Ukratko, ovo je jedna od sorti izračuna kontrolne sume. Kontrolna suma je metoda provjere integriteta primljenih informacija na strani prijamnika prilikom prijenosa putem komunikacijskih kanala. Na primjer, jedna od najjednostavnijih provjera je upotreba bita parnosti. To je kada se zbroje svi bitovi prenesene poruke, a ako se zbroj pokaže parnim, na kraj poruke dodaje se 0, ako je neparan, tada 1. Pri primanju, zbroj bitovi poruka se također broje i uspoređuju s primljenim bitom pariteta. Ako se razlikuju, tada su se tijekom prijenosa dogodile pogreške i prenesene su informacije bile iskrivljene.
Ali ova metoda otkrivanja prisutnosti pogrešaka vrlo je neinformativna i ne funkcionira uvijek, jer ako je nekoliko bitova poruke iskrivljeno, paritet zbroja se možda neće promijeniti. Stoga postoji mnogo više "naprednih" provjera, uključujući CRC.
U stvari, CRC nije zbroj, već je rezultat dijeljenja određene količine informacija (informativne poruke) konstantom, ili tačnije, ostatka dijeljenja poruke konstantom. Međutim, CRC se u povijesti naziva i "kontrolna suma". Svaki bit poruke doprinosi CRC vrijednosti. Odnosno, ako se tijekom prijenosa promijeni barem jedan bit izvorne poruke, promijenit će se i značajna suma. To je veliki plus takve provjere, jer vam omogućuje nedvosmisleno utvrđivanje je li izvorna poruka bila izobličena tijekom prijenosa ili nije.
Korak 2
Prije nego počnemo računati CRC, potrebno je malo više teorije.
Što je izvorna poruka, trebalo bi biti jasno. To je susjedni slijed bitova proizvoljne duljine.
Koja je konstanta po kojoj bismo trebali podijeliti izvornu poruku? Ovaj je broj također bilo koje duljine, ali obično se koriste višekratnici od 1 bajta - 8, 16 i 32 bita. Jednostavno je lakše brojati, jer računala rade s bajtovima, a ne s bitovima.
Konstanta djelitelja obično se zapisuje kao polinom (polinom) ovako: x ^ 8 + x ^ 2 + x ^ 1 + x ^ 0. Ovdje stupanj broja "x" znači položaj jednobita u broju, počevši od nule, a najznačajniji bit označava stupanj polinoma i odbacuje se pri tumačenju broja. Odnosno, prethodno napisani broj nije ništa više od (1) 00000111 u binarnom obliku ili 7 u decimalnom. U zagradi sam naznačio impliciranu najznačajniju znamenku broja.
Evo još jednog primjera: x ^ 16 + x ^ 15 + x ^ 2 + x ^ 0 = (1) 1000000000000101 = 0x8005 = 32773.
Obično se za različite vrste CRC-a koriste neki standardni polinomi.
3. korak
Pa kako izračunati kontrolnu sumu? Postoji osnovna metoda - dijeljenje poruke u polinom "frontalno" - i njene modifikacije kako bi se smanjio broj izračuna i, u skladu s tim, ubrzao CRC izračun. Osvrnut ćemo se na osnovnu metodu.
Općenito, dijeljenje broja polinomom izvodi se prema sljedećem algoritmu:
1) stvara se niz (registar), ispunjen nulama, jednakim duljini duljini širine polinoma;
2) izvorna poruka nadopunjena je nulama u najmanje značajnim bitovima, u količini jednakoj broju bitova polinoma;
3) jedan najznačajniji bit poruke unosi se u najmanje značajni bit registra, a jedan bit se premješta iz najznačajnijeg bita registra;
4) ako je prošireni bit jednak "1", tada su bitovi invertirani (XOR operacija, isključujući ILI) u onim bitovima registra koji odgovaraju onima u polinomu;
5) ako u poruci još ima bitova, idite na korak 3);
6) kada su svi bitovi poruke ušli u registar i obrađeni ovim algoritmom, ostatak podjele ostaje u registru, što je CRC kontrolna suma.
Slika ilustrira podjelu izvorne sekvence bitova brojem (1) 00000111 ili polinomom x ^ 8 + x ^ 2 + x ^ 1 + x ^ 0.
4. korak
Ostalo je još par dodatnih dodira. Kao što ste primijetili, poruku možete podijeliti s bilo kojim brojem. Kako to odabrati? Postoji niz standardnih polinoma koji se koriste za izračunavanje CRC-a. Na primjer, za CRC32 to može biti 0x04C11DB7, a za CRC16 0x8005.
Osim toga, u registar na početku izračuna možete upisati ne nule, već neki drugi broj.
Također, tijekom izračuna, neposredno prije izdavanja konačne CRC kontrolne sume, mogu se podijeliti s nekim drugim brojem.
I posljednja stvar. Bajtovi poruke pri upisu u registar mogu se postaviti kao najznačajniji bit "naprijed" i obrnuto, onaj najmanji značaj.
Korak 5
Na temelju svega navedenog, napišite osnovnu. NET funkciju koja izračunava CRC kontrolnu sumu uzimajući niz parametara koje sam gore opisao i vraćajući vrijednost CRC-a kao 32-bitni nepotpisani broj.
Javna dijeljena funkcija GetCrc (ByVal bytes As Byte (), ByVal poly As UInteger, Neobvezno ByVal width As Integer = 32, Optional ByVal initReg As UInteger = & HFFFFFFFFUI, Optional ByVal finalXor As UInteger = & HFFFFFFFFUI, Optional ByVal, Optional ByVal Bowal, Optional ByVal, optional reverseCrc As Boolean = True) Kao UInteger
Zatamni widthInBytes kao Integer = width / 8
'Dopunite širinu poruke nulama (izračun u bajtovima):
ReDim Preserve bajtovi (bajtovi. Dužina - 1 + širinaInBytes)
'Stvorite red čekanja od poruke:
Zatamni msgFifo kao novi red (od logičke vrijednosti) (bajtovi.broj * 8 - 1)
Za svaki b Kao bajt u bajtovima
Zatamni kao novi BitArray ({b})
Ako reverseBytes Tada
Za ja kao cijeli broj = 0 do 7
msgFifo. Enqueue (ba (i))
Sljedeći
Drugo
Za ja kao cijeli broj = 7 do 0 Korak -1
msgFifo. Enqueue (ba (i))
Sljedeći
Završi ako
Sljedeći
'Stvorite red od početnih bitova za popunjavanje registra:
Zatamni initBytes kao bajt () = BitConverter. GetBytes (initReg)
Zatamni initBytesReversed As IEnumerable (Of Byte) = (From b As Byte In initBytes Take widthInBytes). Reverse
Zatamni initFifo kao novi red (od logičke vrijednosti) (širina - 1)
Za svaki b Kao bajt u initBytesReversed
Zatamni kao novi BitArray ({b})
Ako ne obrne bajtove onda
Za ja kao cijeli broj = 0 do 7
initFifo. Enqueue (ba (i))
Sljedeći
Drugo
Za ja kao cijeli broj = 7 do 0 Korak -1
initFifo. Enqueue (ba (i))
Sljedeći
Završi ako
Sljedeći
'Shift i XOR:
Dim registar kao UInteger = 0 'ispunite registar širine-bita nulama.
Učinite dok je msgFifo. Count> 0
Zatamni poppedBit kao cijeli broj = CInt (registar >> (širina - 1)) I 1 'definirajte prije registra smjene.
Zatamni pomaknutiBit kao bajt = Convert. ToByte (msgFifo. Dequeue)
Ako je initFifo. Count> 0 Tada
Dim b As Byte = Convert. ToByte (initFifo. Dequeue)
pomaknutiBit = pomaknutiBit Xor b
Završi ako
register = registar << 1
register = registrirati ili pomaknuti bit
Ako je poppedBit = 1 Tada
register = registrirati Xor poli
Završi ako
Petlja
'Konačne pretvorbe:
Dim crc Kao UInteger = register 'Registar sadrži ostatak podjele == kontrolne sume.
Ako reverseCrc Tada
crc = odraz (crc, širina)
Završi ako
crc = crc Xor finalXor
crc = crc I (& HFFFFFFFFUI >> (32 - širina)) 'maskiraju najmanje značajne bitove.
Povratak crc
Krajnja funkcija
