Există multe opțiuni pentru calcularea sumei de control CRC pe Internet. Dar ce este exact o sumă de control și de ce este calculată în acest fel? Să ne dăm seama.
Instrucțiuni
Pasul 1
În primul rând, să luăm un pic de teorie. Deci, ce este exact CRC? Pe scurt, acesta este unul dintre soiurile de calcul al sumei de control. Suma de verificare este o metodă de verificare a integrității informațiilor primite pe partea receptorului atunci când se transmite prin canale de comunicație. De exemplu, una dintre cele mai simple verificări este utilizarea bitului de paritate. Acesta este momentul în care sunt rezumați toți biții mesajului transmis și, dacă suma se dovedește a fi pară, atunci se adaugă 0 la sfârșitul mesajului, dacă este impar, atunci 1. Când primiți, suma biții de mesaj sunt, de asemenea, numărați și comparați cu bitul de paritate primit. Dacă diferă, atunci au apărut erori în timpul transmisiei, iar informațiile transmise au fost distorsionate.
Dar această metodă de detectare a prezenței erorilor este foarte neinformativă și nu funcționează întotdeauna, deoarece dacă mai mulți biți ai mesajului sunt distorsionați, paritatea sumei poate să nu se schimbe. Prin urmare, există mult 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ții) la o constantă sau, mai bine zis, la restul împărțirii unui mesaj la o constantă. Cu toate acestea, CRC este, de asemenea, denumit în mod istoric o „sumă de control”. Fiecare bit al mesajului contribuie la valoarea CRC. Adică, dacă cel puțin un bit din mesajul original se schimbă în timpul transmiterii, suma de control se va schimba și semnificativ. Acesta este un mare plus al unei astfel de verificări, deoarece vă permite să determinați fără echivoc dacă mesajul original a fost distorsionat sau nu în timpul transmisiei.
Pasul 2
Înainte de a începe calcularea CRC, este nevoie de puțină teorie.
Care este mesajul original ar trebui să fie clar. Este o secvență contiguă de biți de lungime arbitrară.
Care este constanta prin care ar trebui să împărțim mesajul original? Acest număr este, de asemenea, de orice lungime, dar de obicei se folosesc multipli de 1 octet - 8, 16 și 32 de biți. Este doar mai ușor de numărat, deoarece computerele funcționează cu octeți, nu cu biți.
Constanta divizorului este de obicei scrisă ca polinom (polinom) astfel: x ^ 8 + x ^ 2 + x ^ 1 + x ^ 0. Aici, gradul numărului "x" înseamnă poziția unui bit în număr, începând de la zero, iar bitul cel mai semnificativ indică gradul polinomului și este aruncat la interpretarea numărului. Adică, numărul scris anterior nu este altceva decât (1) 00000111 în binar sau 7 în zecimal. În paranteze, am indicat cea mai semnificativă 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 utilizate pentru diferite tipuri de CRC-uri.
Pasul 3
Deci, cum calculați suma de control? Există o metodă de bază - împărțirea unui mesaj într-un polinom „frontal” - și modificările sale pentru a reduce numărul de calcule și, în consecință, pentru a accelera calculul CRC. Ne vom uita la metoda de bază.
În general, împărțirea unui număr printr-un polinom se realizează conform următorului algoritm:
1) se creează o matrice (registru), umplută cu zerouri, egală în lungime cu lungimea lățimii polinomiale;
2) mesajul original este completat cu zerouri în biții cel mai puțin semnificativi, într-o cantitate egală cu numărul de biți ai polinomului;
3) un bit cel mai semnificativ al mesajului este introdus în bitul cel mai puțin semnificativ al registrului și un bit este mutat din bitul cel mai semnificativ al registrului;
4) dacă bitul extins este egal cu "1", atunci biții sunt inversați (operație XOR, OR exclusiv) în acei biți de registru care corespund celor din polinom;
5) dacă mai sunt biți în mesaj, treceți la pasul 3);
6) când toți biții mesajului au intrat în registru și au fost prelucraț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 la numărul (1) 00000111 sau polinomul x ^ 8 + x ^ 2 + x ^ 1 + x ^ 0.
Pasul 4
Au mai rămas câteva atingeri suplimentare. După cum ați observat, mesajul poate fi împărțit la orice număr. Cum să o alegi? Există o serie de polinoame standard care sunt utilizate pentru a calcula CRC. De exemplu, pentru CRC32 ar putea fi 0x04C11DB7, iar pentru CRC16 ar putea fi 0x8005.
În plus, în registrul de la începutul calculului, puteți scrie nu zerouri, ci un alt număr.
De asemenea, în timpul calculelor, imediat înainte de a emite suma de control finală CRC, acestea pot fi împărțite la un alt număr.
Și ultimul lucru. Octetii mesajului la scrierea în registru pot fi plasați ca cel mai semnificativ bit „înainte” și invers, cel mai puțin semnificativ.
Pasul 5
Pe baza tuturor celor de mai sus, să scriem o funcție de bază. NET care calculează suma de control CRC luând un număr de parametri descriși mai sus și returnând valoarea CRC ca un număr nesemnat pe 32 de biți.
Funcție publică partajată GetCrc (ByVal bytes As Byte (), ByVal poly As UInteger, Optional ByVal width As Integer = 32, Optional ByVal initReg As UInteger = & HFFFFFFFFUI, Optional ByVal finalXor As UInteger = & HFFFFFFFFFFUI, Optional ByVal reverseBy reverseCrc As Boolean = True) Ca UInteger
Dim widthInBytes As Integer = width / 8
'Completați lățimea mesajului cu zerouri (calculul în octeți):
ReDim Preserve bytes (octeți. Lungime - 1 + widthInBytes)
'Creați o coadă de biți din mesaj:
Dim msgFifo As New Queue (Of Boolean) (bytes. Count * 8 - 1)
Pentru fiecare b Ca octeți În octeți
Dim ba ca nou BitArray ({b})
Dacă inversBytes Atunci
Pentru i Ca întreg = 0 până la 7
msgFifo. Enqueue (ba (i))
Următorul
Altfel
Pentru i Ca întreg = 7 la 0 Pasul -1
msgFifo. Enqueue (ba (i))
Următorul
End If
Următorul
'Creați o coadă din biții de umplere inițiali ai registrului:
Dim initBytes As Byte () = BitConverter. GetBytes (initReg)
Dim initBytesReversed As IEnumerable (Of Byte) = (From b As Byte In initBytes Take widthInBytes). Reverse
Dim initFifo Ca coadă nouă (de boolean) (lățime - 1)
Pentru fiecare b ca octeți în initBytesReversed
Dim ba ca nou BitArray ({b})
Dacă nu reverseBytes, atunci
Pentru i Ca întreg = 0 până la 7
initFifo. Enqueue (ba (i))
Următorul
Altfel
Pentru i Ca întreg = 7 la 0 Pasul -1
initFifo. Enqueue (ba (i))
Următorul
End If
Următorul
„Shift și XOR:
Dim înregistrare Ca UInteger = 0 'umpleți registrul lățimii cu zerouri.
Faceți în timp ce msgFifo. Count> 0
Dim poppedBit As Integer = CInt (register >> (width - 1)) Și 1 'definește înainte de shift shift.
Dim shiftedBit As Byte = Convert. ToByte (msgFifo. Dequeue)
Dacă initFifo. Count> 0 Atunci
Dim b As Byte = Convert. ToByte (initFifo. Dequeue)
shiftedBit = shiftedBit Xor b
End If
registru = registru << 1
register = register Sau shiftedBit
Dacă poppedBit = 1 Apoi
register = register Xor poly
End If
Buclă
„Conversii finale:
Dim crc Ca UInteger = register 'Registrul conține restul diviziunii == suma de control.
Dacă inversCrc Atunci
crc = reflect (crc, lățime)
End If
crc = crc Xor finalXor
crc = crc Și (& HFFFFFFFFUU >> (32 - lățime)) 'maschează cei mai puțin semnificativi biți.
Întoarceți crc
Funcția de sfârșit
