Ca simplu pentru a calcula suma de control CRC (crc32 - CRC16 - crc8), omj

Pe Internet, există mai multe opțiuni pentru calcularea sumei de control CRC. Dar ce este de fapt o sumă de control și de ce este calculat în acest fel? Să investigheze.

1
În primul rând, trebuie să înțelegem un pic teorie. Deci, ce este CRC? Pe scurt, acesta este unul dintre soiurile de calcul al sumei 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 teste - utilizarea de biți 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 de bug-uri - foarte uninformative și nu funcționează întotdeauna, deoarece distorsiunea puținele posturi biți, paritate suma nu poate fi schimbată. Prin urmare, există mai multe teste „avansate“, inclusiv CRC.

De fapt, CRC - acest lucru nu este suma, iar rezultatul divizării o anumită cantitate de informații (mesaj de date) la o constantă - sau, mai degrabă, restul de posturi de divizare o constantă. Cu toate acestea, CRC punct de vedere istoric, de asemenea, numit un „control“. Valoarea CRC contribuie fiecare bit al mesajului. Aceasta este, în cazul în care cel puțin un bit al mesajului inițial sa schimbat în tranzit, suma de control se va schimba de asemenea, cu considerabil. Acesta este un mare plus acest test, deoarece vă permite să identificați în mod unic distorsionat mesajul original atunci când trimiteți sau nu.

2
Înainte de a trece la calculul CRC, va avea nevoie de o teorie pic mai mult.
Care este mesajul original ar trebui să fie clar. Aceasta este o secvență de biți continuă de lungime arbitrară.

Ce fel de constantă, pe care trebuie să împartă mesajul original? Este, de asemenea, un număr de orice lungime, dar sunt utilizate în mod tipic multipli de 1 octet - 8, 16 și 32 de biți. Doar așa că este mai ușor să credem, deoarece calculatoarele pentru a lucra cu bytes, mai degrabă decât cu biți.

Constantă-divizor este scris de obicei ca un polinom (polinom) astfel: x ^ 8 + x ^ 2 + x ^ 1 + x ^ 0. Aici, gradul de „x“ înseamnă poziția unităților de biți număr, începând cu zero, iar MSB indică gradul de polinomului este îndepărtat și interpretarea numărului. Aceasta este, numărul înregistrat anterior - acest lucru nu este nimic mai mult decât o (1) 00000111 în notație binară sau zecimală 7. În paranteze, am implicat numărul MSB.
Iată un exemplu: x ^ 16 + x ^ 15 + x ^ 2 + x ^ = 0 (1) 1000000000000101 „= 0x8005 = 32773.
anumite polinoame standard sunt frecvent utilizate pentru diferite tipuri de CRC.

3
Deci, cum considerați suma de control? Există o metodă de bază - împărțirea posturilor de către un polinom „într-o frunte“ - și modificarea acesteia, în scopul de a reduce cantitatea de calcul și, astfel, accelera calculul CRC. Am o metodă de bază ia în considerare.

În termeni generali, divizarea unui polinom se realizează pe o astfel algoritm:
1) creează o matrice (registru) umplut cu zerouri egale cu lungimea bit a polinomului;
2) postul original este căptușit cu zerouri în biți mai mici, într-o cantitate egală cu numărul de biți ai polinomului;
3) în registrul de joasă este introdus una mesaje cifre MSB, și se extinde din etapa mai vechi registru de un bit;
4) dacă bitul extins este „1“, bitul inversia se efectuează (operație XOR, XOR) biților din registrele care corespund unităților din polinomului;
5) în cazul în care mesajul are mai mulți biți, mergeți la pasul 3);
6), atunci când toți biții de mesaje primite în cazul și au fost prelucrate de către acest algoritm, registrul rămâne restul împărțirii, care este un CRC sumă de control.

Figura ilustrează divizarea secvenței originale de biți de numărul (1) 00000111, sau polinomul x ^ 8 + x ^ 2 + x ^ 1 + x ^ 0.

4
Am stat câteva atingeri suplimentare. După cum puteți vedea, mesajul poate fi împărțit în orice număr. Cum să-l aleg? Există un număr de polinoame standard, care sunt utilizate în calculul CRC. De exemplu, crc32 pentru acest lucru poate fi numărul 0x04C11DB7, iar pentru acest lucru poate fi CRC16 0x8005.
În plus, în cazul de la începutul calculelor pot fi scrise nu este zero, dar unele alt număr.

De asemenea, în calculele imediat înainte de emiterea de control CRC final poate fi împărțit în alt număr.

Și ultimul. Mesaj octeți pentru înregistrarea în registru poate fi plasat ca cel mai semnificativ bit „înainte“, și vice-versa, un junior.

5
Pe baza celor de mai sus, să scrie o funcție în limba de bază NET, care va calcula suma de control al CRC, luând o serie de parametri pe care le-am descris mai sus, și returnarea valoarea CRC ca un 32 de biți numere fără semn.

Funcție publică partajată GetCrc (ByVal bytes Ca Byte (), ByVal poli Ca UInteger, latime Opțional ByVal Ca Integer = 32, Opțional ByVal initReg Ca UInteger = HFFFFFFFFUI, Opțional ByVal finalXor Ca UInteger = HFFFFFFFFUI, reverseBytes ByVal Opțional Ca Boolean = Adevărat, Opțional ByVal reverseCrc Ca Boolean = true) Ca UInteger

widthInBytes Dim As Integer = lățimea 8

„Finalizarea mesajului lățime zero (calcul în octeți):
ReDim bytes Preserve (bytes.Length - 1 + widthInBytes)

„Creați toți biții mesajului:
Dim msgFifo Ca noua coadă (de Boolean) (bytes.Count * 8-1)
Pentru fiecare b Ca Byte In octeți
Dim ba Ca nou BitArray ()
Dacă reverseBytes Apoi
Pentru i Ca Integer = 0 la 7
msgFifo.Enqueue (ba (i))
următor
altfel
Pentru i Ca Integer = 7 La 0 Pasul -1
msgFifo.Enqueue (ba (i))
următor
End If
următor

„Creați toți biții umplerii inițiale a registrului:
initBytes Dim byte () = BitConverter.GetBytes (initReg)
Dim initBytesReversed Ca IEnumerable (cu Byte) = (b De la byte În initBytes Ia widthInBytes) .Reverse
Dim initFifo Ca New Queue (Of Boolean) (lățime - 1)
Pentru fiecare b Ca Byte In initBytesReversed
Dim ba Ca nou BitArray ()
Dacă nu este reverseBytes Atunci
Pentru i Ca Integer = 0 la 7
initFifo.Enqueue (ba (i))
următor
altfel
Pentru i Ca Integer = 7 La 0 Pasul -1
initFifo.Enqueue (ba (i))
următor
End If
următor

„Shift și XOR:
registru Dim Ca UInteger = 0 „umple registrul lățime de biți, cu zerouri.
Face în timp ce msgFifo.Count> 0

poppedBit Dim Ca Integer = CINT (înregistrare >> (lățime - 1)) și 1 „pentru a defini un registru de deplasare.

Dim shiftedBit Ca Byte = Convert.ToByte (msgFifo.Dequeue)
Dacă initFifo.Count> 0 Atunci
Dim b Ca Byte = Convert.ToByte (initFifo.Dequeue)
shiftedBit = shiftedBit XOR b
End If

registru = registru <<1
register = registru Sau shiftedBit

Dacă poppedBit = 1 Apoi
registru = registru XOR poli
End If
buclă

„Conversie finală:
crc Dim Ca UInteger = registru „registru conține restul de divizare == control.
Dacă reverseCrc Atunci
crc = reflecta (crc, lățime)
End If
crc = crc XOR finalXor
= crc crc și (HFFFFFFFFUI >> (32 - lățime)) „masca LSBs.

sfat sănătos
Programul propus este scalabilitate slabă. Adică, funcționează bine în calcularea sumei de control CRC pentru mesaje scurte de până la câteva zeci de kilobytes. La calcularea CRC pentru un mesaj lung, dimensiunea de zeci sau sute de megabytes, programul va supraîncărca procesor și memorie, ca întregul mesaj este încărcat în matrice. Pentru a lucra cu astfel de mesaje mari trebuie să pună în aplicare un tampon intermediar, care va transmite un mesaj de la programul în porții mici.
sursă