În primul rând, să aruncăm o privire asupra teoriei. Deci, ce este CRC? Pe scurt, acesta este unul dintre tipurile de calcul al sumelor de control. Checksum - o metodă de verificare a integrității informațiilor primite pe partea de receptor a transmisiei prin canale de comunicare. De exemplu, una dintre cele mai simple verificări este utilizarea bitului de paritate. Acest lucru atunci când a adăugat toți biții mesajului transmis, iar în cazul în care suma este chiar, apoi se adaugă la mesajul 0 dacă impar - 1. Atunci când recepția se calculează ca suma de biți de mesaje și este comparat cu bitul de paritate primit. În cazul în care acestea sunt diferite, atunci apar erori de transmisie, iar informațiile transmise au fost denaturate.
Dar această metodă de determinare a prezenței erorilor este foarte neinformativă și nu funcționează întotdeauna; Dacă sunt distorsionați câțiva biți ai mesajului, este posibil ca paritatea sumei să nu se modifice. Prin urmare, există mai multe verificări "avansate", inclusiv CRC.
De fapt, CRC nu este o sumă, ci rezultatul împărțirii unei anumite cantități de informații (mesaj de informație) într-o constantă, sau mai precis, restul de a împărți un mesaj într-o constantă. Cu toate acestea, CRC este, de asemenea, numită în trecut un "control de sumă". Fiecare bit al mesajului contribuie la valoarea CRC. Adică, dacă cel puțin un bit al mesajului original se modifică în timpul transmisiei, suma de control se va schimba și semnificativ. Acesta este un plus important al acestei verificări, deoarece vă permite să stabiliți în mod unic dacă mesajul original a fost distorsionat în timpul transmiterii sau nu.
Înainte de a începe calcularea CRC, va fi nevoie de o teorie mai mică.
Care este mesajul original trebuie să fie clar. Aceasta este o secvență continuă de biți de lungime arbitrară.
Care este constanta, la care trebuie sa divizam mesajul original? Acest număr are, de asemenea, orice lungime, dar de obicei numerele care sunt multiplii de 1 octet sunt 8, 16 și 32 de biți. Este mai ușor să contezi, deoarece computerele lucrează cu octeți, nu biți.
Divizorul constant este scris în mod obișnuit sub forma unui polinom (polinom) astfel: x ^ 8 + x ^ 2 + x ^ 1 + x ^ 0. Aici gradul numărului "x" denotă poziția unității de biți în număr, pornind de la zero, iar bitul de ordin înalt indică gradul polinomului și este aruncat la interpretarea numărului. Adică, numărul scris anterior nu este mai mult decât (1) 00000111 în sistemul binar sau 7 în zecimal. În paranteze, am indicat cea mai înaltă cifră implicită a numărului.
Iată un alt exemplu: x ^ 16 + x ^ 15 + x ^ 2 + x ^ 0 = (1) 1000000000000101 "= 0x8005 = 32773.
De obicei, unele polinoame standard sunt folosite pentru diferite tipuri de CRC.
Deci, cum contezi suma de control? Există o metodă de bază - împărțirea mesajului pe polinomul "în frunte" - și modificările acestuia pentru a reduce numărul de calcule și, prin urmare, pentru a accelera calculul CRC. Vom lua în considerare metoda de bază.
În general, împărțirea unui număr într-un polinom este efectuată conform următorului algoritm:
1) este creată o matrice (registru), umplută cu zerouri, egală cu lungimea lățimii polinomului;
2) mesajul inițial este umplut cu zerouri în cifrele inferioare, într-o cantitate egală cu numărul de biți ai polinomului;
3) un bit superior al mesajului este introdus în cel mai puțin semnificativ bit al registrului și un bit este scos din bitul de înregistrare superior;
4) dacă bitul extins este "1", atunci se efectuează inversarea biților (operația XOR excluzând OR) în acei biți ai registrului care corespund celor din polinom;
5) dacă mai există biți în mesaj, mergeți la pasul 3);
6) când toți biți ai mesajului au intrat în registru și au fost procesați de acest algoritm, restul diviziunii rămâne în registru, care este suma de control CRC.
Figura ilustrează împărțirea secvenței de biți inițiale cu un număr (1) 00000111 sau un polinom x ^ 8 + x ^ 2 + x ^ 1 + x ^ 0.
Mai există încă câteva atingeri suplimentare. După cum puteți vedea, mesajul poate fi împărțit în orice număr. Cum de a alege? Există un număr de polinoame standard care sunt folosite la calcularea CRC. De exemplu, pentru CRC32 acesta poate fi un număr de 0x04C11DB7, iar pentru CRC16 acesta poate fi 0x8005.
În plus, este posibil să se scrie în registru la începutul calculelor nu zerouri, ci un alt număr.
De asemenea, atunci când se calculează chiar înainte de emitere, suma de control finală CRC poate fi împărțită în alt număr.
Și ultimul. Bytes de mesaj atunci când scrieți în registru poate fi plasat ca cel mai mare bit "înainte", și invers, cel mai tânăr.
Pe baza celor de mai sus. să scriem o funcție în limba .NET de bază care va calcula suma de control CRC, luând un număr de parametri pe care i-am descris mai sus și returnând valoarea CRC ca număr nesemnificativ de 32 de biți.
Funcția publică partajată GetCrc (ByVal bytes ca byte (), ByVal poli ca UInteger, lățime opțională ByVal ca integer = 32, ByVal opțional initReg Ca UInteger = HFFFFFFFFUI, opțional ByVal finalXor ca UInteger = HFFFFFFFFUI, opțional ByVal reverseBytes ca boolean = adevărat, opțional ByVal inverseCrc ca boolean = adevărat) ca UInteger
Lățimea de dimensiuneInBilete ca Integer = lățime \ 8
"Suplimentăm lățimea mesajului cu zerouri (calcul în octeți):
ReDim păstrați octeți (octeți.Lungime - 1 + widthInBytes)
'Creați o coadă de biți din mesaj:
Dim msgFifo ca noua coadă (de boolean) (bytes.Count * 8 - 1)
Pentru fiecare b Ca octet în octeți
Dim ba ca nou BitArray ()
În cazul în care apoi reverseBytes
Pentru i ca Integer = 0 Pentru 7
msgFifo.Enqueue (ba (i))
următor
altfel
Pentru i ca Integer = 7 Pentru 0 Pasul -1
msgFifo.Enqueue (ba (i))
următor
Sfârșit Dacă
următor
"Creăm o coadă de biți din umplerea inițială a registrului:
Dimit initBytes ca octet () = BitConverter.GetBytes (initReg)
Dim initBytesReversed ca IEnumerable (Of Byte) = (De la b ca octet in initBytes Take widthInBytes). Reverse
Dim initFifo ca noua coada (de boolean) (latime - 1)
Pentru fiecare b ca octet initBytes inversat
Dim ba ca nou BitArray ()
Dacă nu reversibilă atunci
Pentru i ca Integer = 0 Pentru 7
initFifo.Enqueue (ba (i))
următor
altfel
Pentru i ca Integer = 7 Pentru 0 Pasul -1
initFifo.Enqueue (ba (i))
următor
Sfârșit Dacă
următor
"Shift și XOR:
Dim registru Ca UInteger = 0 'umpleți registrul de lățime-bit cu zerouri.
În timp ce msgFifo.Count> 0
Dim poppedBit Ca Integer = CInt (registru >> (lățime - 1)) Și 1 'definiți înainte de a schimba registrul.
Dim schimbatBit ca octet = Convert.ToByte (msgFifo.Dequeue)
Dacă initFifo.Count> 0 Apoi
Dim b ca octet = Convert.ToByte (initFifo.Dequeue)
shiftedBit = shiftedBit X sau b
Sfârșit Dacă
registru = înregistrare <<1
registru = registru sau schimbat
Dacă poppedBit = 1 Apoi
registru = înregistrare Xor poli
Sfârșit Dacă
buclă
"Transformări finale:
Dim crc Ca UInteger = registru 'Registrul conține restul din suma == checksum.
În cazul în care apoi reverseCrc
crc = reflectă (crc, lățime)
Sfârșit Dacă
crc = crc Xor finalXor
crc = crc Și (HFFFFFFFFUI >> (32 - lățime)) 'maschează biții de ordin inferior.