Postoji mnogo opcija za izračunavanje CRC kontrolne sume na Internetu. Ali što je zapravo kontrolna suma i zašto se izračunava na ovaj način? Hajde da shvatimo.
Instrukcije
Korak 1
Prvo, krenimo malo u teoriju. Pa šta je zapravo CRC? Ukratko, ovo je jedna od varijanti izračunavanja kontrolne sume. Kontrolna suma je metoda provjere integriteta primljenih informacija na strani prijemnika prilikom prijenosa putem komunikacijskih kanala. Na primjer, jedna od najjednostavnijih provjera je upotreba bita parnosti. To je kada se sabiru svi bitovi prenesene poruke, a ako se zbroj pokaže parnim, tada se 0 dodaje na kraj poruke, ako je neparan, onda 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 greške i prenesene informacije su iskrivljene.
Ali ovaj metod otkrivanja prisutnosti grešaka vrlo je neinformativan i ne funkcionira uvijek, jer ako je nekoliko bitova poruke izobličeno, 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ć rezultat dijeljenja određene količine informacija (informativne poruke) konstantom, ili tačnije, ostatka dijeljenja poruke konstantom. Međutim, CRC se u prošlosti naziva i "kontrolna suma". Svaki bit poruke doprinosi CRC vrijednosti. Odnosno, ako se tijekom prijenosa promijeni barem jedan bit originalne 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 izobličena tijekom prijenosa ili ne.
Korak 2
Prije nego što započnemo s izračunavanjem CRC-a, potrebno je malo više teorije.
Šta je originalna poruka, mora biti jasno. To je susjedni niz bitova proizvoljne dužine.
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čunari 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 cifru broja.
Evo još jednog primjera: x ^ 16 + x ^ 15 + x ^ 2 + x ^ 0 = (1) 1000000000000101 = 0x8005 = 32773.
Obično se neki standardni polinomi koriste za različite vrste CRC-a.
Korak 3
Pa kako izračunati kontrolnu sumu? Postoji osnovna metoda - dijeljenje poruke u polinom "frontalno" - i njene modifikacije kako bi se smanjio broj izračunavanja 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) kreira se niz (registar), ispunjen nulama, jednakim dužini dužini širine polinoma;
2) originalna poruka je dopunjena 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, ekskluzivno ILI) u onim registracionim bitovima koji odgovaraju onima u polinomu;
5) ako u poruci još uvijek postoje bitovi, 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.
Korak 4
Ostalo je još par dodatnih dodira. Kao što ste već primijetili, poruku možete podijeliti s bilo kojim brojem. Kako 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.
Pored toga, u registar na početku izračuna možete upisati ne nule, već neki drugi broj.
Takođe, tokom izračunavanja, neposredno pre izdavanja konačne CRC kontrolne sume, mogu se podijeliti sa nekim drugim brojem.
I poslednja stvar. Bajtovi poruke pri upisu u registar mogu se postaviti kao najznačajniji bit "naprijed" i obrnuto, onaj najmanji značaj.
Korak 5
Na osnovu svega navedenog, napišimo osnovnu. NET funkciju koja izračunava CRC kontrolnu sumu uzimajući niz parametara koje sam gore opisao i vraćajući CRC vrijednost kao 32-bitni nepotpisani broj.
Javna zajednička funkcija GetCrc (ByVal bajtova kao bajt (), ByVal poli kao UInteger, neobavezna širina ByVal kao Integer = 32, opcionalno ByVal initReg kao UInteger = & HFFFFFFFFUI, opcionalno ByVal finalXor kao UInteger = & HFFFFFFFFUI, opcionalno ByVal, opcionalno ByVal, opcionalno ByVal reverseCrc As Boolean = True) Kao UInteger
Zatamni widthInBytes kao Integer = width / 8
'Širinu poruke dopunite nulama (izračun u bajtovima):
ReDim Sačuvaj bajtove (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
For i As Integer = 0 do 7
msgFifo. Enqueue (ba (i))
Sljedeći
Inače
For i As Integer = 7 do 0 Korak -1
msgFifo. Enqueue (ba (i))
Sljedeći
Kraj ako
Sljedeći
'Stvorite red od početnih bitova popunjavanja registra:
Zatamni initBytes kao bajt () = BitConverter. GetBytes (initReg)
Zatamni initBytesReversed As IEnumerable (Of Byte) = (Od b Kao bajt u initBytes uzmi widthInBytes).
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
For i As Integer = 0 do 7
initFifo. Enqueue (ba (i))
Sljedeći
Inače
For i As Integer = 7 do 0 Korak -1
initFifo. Enqueue (ba (i))
Sljedeći
Kraj ako
Sljedeći
'Shift i XOR:
Zatamni registar Kao UInteger = 0 'popuni registar širine-bita nulama.
Učinite dok je msgFifo. Count> 0
Zatamni poppedBit kao integritet = CInt (registar >> (širina - 1)) I 1 'definirajte prije registra smjene.
Priguši pomaknuti Bit kao bajt = Convert. ToByte (msgFifo. Dequeue)
Ako je initFifo. Count> 0 Tada
Dim b As Byte = Convert. ToByte (initFifo. Dequeue)
shiftedBit = pomaknutiBit Xor b
Kraj ako
register = registar << 1
register = registruj ili pomakni bit
Ako je poppedBit = 1 Tada
register = registruj Xor poli
Kraj ako
Petlja
'Konačne konverzije:
Dim crc Kao UInteger = register 'Registar sadrži ostatak kontrolne sume podjele ==.
Ako reverseCrc Tada
crc = odraz (crc, širina)
Kraj ako
crc = crc Xor finalXor
crc = crc I (& HFFFFFFFFUI >> (32 - širina)) 'maskira najmanje značajne bitove.
Povratak crc
Krajnja funkcija
