Hi ha moltes opcions per calcular la suma de comprovació CRC a Internet. Però, què és exactament una suma de control i per què es calcula d'aquesta manera? Esbrinem-ho.
Instruccions
Pas 1
En primer lloc, fem una mica de teoria. Llavors, què és exactament CRC? En resum, aquesta és una de les varietats del càlcul de la suma de control. La suma de verificació és un mètode per comprovar la integritat de la informació rebuda al costat del receptor quan es transmet per canals de comunicació. Per exemple, un dels controls més senzills és utilitzar el bit de paritat. És quan es resumeixen tots els bits del missatge transmès i, si la suma resulta ser parella, s’afegeix 0 al final del missatge, si és senar, aleshores 1. Quan es rep, la suma del els bits de missatge també es compten i es comparen amb el bit de paritat rebut. Si difereixen, es van produir errors durant la transmissió i es va distorsionar la informació transmesa.
Però aquest mètode de detecció de la presència d'errors és molt poc informatiu i no sempre funciona, perquè si es distorsionen diversos fragments del missatge, la paritat de la suma pot no canviar. Per tant, hi ha molts controls més "avançats", inclòs el CRC.
De fet, CRC no és una suma, sinó el resultat de dividir una determinada quantitat d'informació (missatge d'informació) per una constant, o millor dit, la resta de dividir un missatge per una constant. No obstant això, històricament també es coneix el CRC com a "suma de verificació". Cada bit del missatge contribueix al valor CRC. És a dir, si almenys un bit del missatge original canvia durant la transmissió, la suma de comprovació també canviarà i significativament. Aquest és un gran avantatge d’aquest control, ja que permet determinar sense ambigüitats si el missatge original es va distorsionar durant la transmissió o no.
Pas 2
Abans de començar a calcular el CRC, cal una mica més de teoria.
Quin és el missatge original hauria de quedar clar. És una seqüència contigua de bits de longitud arbitrària.
Quina és la constant per la qual hem de dividir el missatge original? Aquest nombre també té qualsevol longitud, però normalment s’utilitzen múltiples d’1 byte: 8, 16 i 32 bits. És més fàcil de comptar, perquè els ordinadors funcionen amb bytes i no amb bits.
La constant divisora sol escriure's com un polinomi (polinomi) així: x ^ 8 + x ^ 2 + x ^ 1 + x ^ 0. Aquí, el grau del número "x" significa la posició d'un bit en el nombre, a partir de zero, i el bit més significatiu indica el grau del polinomi i es descarta en interpretar el número. És a dir, el número escrit anteriorment no és res més que (1) 00000111 en binari o 7 en decimal. Entre parèntesis, he indicat el dígit més significatiu del nombre.
Aquí hi ha un altre exemple: x ^ 16 + x ^ 15 + x ^ 2 + x ^ 0 = (1) 1000000000000101 = 0x8005 = 32773.
Normalment s’utilitzen alguns polinomis estàndard per a diferents tipus de CRC.
Pas 3
Llavors, com es calcula la suma de control? Hi ha un mètode bàsic: dividir un missatge en un polinomi "frontal" - i les seves modificacions per reduir el nombre de càlculs i, per tant, accelerar el càlcul de CRC. Veurem el mètode bàsic.
En general, la divisió d’un nombre per un polinomi es realitza segons l’algoritme següent:
1) es crea una matriu (registre), plena de zeros, de longitud igual a la longitud de l’amplada del polinomi;
2) el missatge original es complementa amb zeros en els bits menys significatius, en una quantitat igual al nombre de bits del polinomi;
3) un bit més significatiu del missatge s'introdueix al bit menys significatiu del registre i un bit es mou del bit més significatiu del registre;
4) si el bit estès és igual a "1", els bits s'inverteixen (operació XOR, OR exclusiu) en aquells bits de registre que corresponen als del polinomi;
5) si encara hi ha bits al missatge, aneu al pas 3);
6) quan tots els bits del missatge van entrar al registre i van ser processats per aquest algorisme, la resta de la divisió roman al registre, que és la suma de comprovació CRC.
La figura il·lustra la divisió de la seqüència de bits original pel nombre (1) 00000111 o el polinomi x ^ 8 + x ^ 2 + x ^ 1 + x ^ 0.
Pas 4
Queden un parell de tocs addicionals. Com haureu notat, el missatge es pot dividir per qualsevol número. Com triar-lo? Hi ha una sèrie de polinomis estàndard que s’utilitzen per calcular el CRC. Per exemple, per a CRC32 pot ser 0x04C11DB7 i per a CRC16 pot ser 0x8005.
A més, al registre al començament del càlcul, podeu escriure no zeros, sinó algun altre número.
A més, durant els càlculs, immediatament abans d’emetre la suma de comprovació CRC final, es poden dividir per algun altre número.
I l’últim. Els bytes del missatge en escriure al registre es poden col·locar com el bit més significatiu "endavant", i viceversa, el menys significatiu.
Pas 5
Basant-nos en tot l'anterior, escrivim una funció. NET bàsica que calcula la suma de comprovació CRC prenent una sèrie de paràmetres que he descrit anteriorment i retornant el valor CRC com un número sense signe de 32 bits.
Funció compartida pública GetCrc (ByVal bytes As Byte (), ByVal poly As UInteger, Opcional ByVal width As Integer = 32, Opcional ByVal initReg As UInteger = & HFFFFFFFFUI, Opcional ByVal finalXor As UInteger = & HFFFFFFFFUU, Opcional ByVal invers By reverseCrc As Boolean = True) Com UInteger
Dim widthInBytes As Integer = ample / 8
'Complementeu l'amplada del missatge amb zeros (càlcul en bytes):
ReDim Preserve bytes (bytes. Length - 1 + widthInBytes)
Creeu una cua de bits a partir del missatge:
Dim msgFifo As New Queue (Of Boolean) (bytes. Count * 8-1)
Per a cada b Com Bytes En bytes
Dim ba com a BitArray nou ({b})
Si inversBytes Llavors
Per a mi com a enter = 0 a 7
msgFifo. Enqueue (ba (i))
Pròxim
Altrament
Per a mi com a enter = 7 a 0 Pas -1
msgFifo. Enqueue (ba (i))
Pròxim
Finalitza If
Pròxim
'Creeu una cua a partir dels bits d'emplenament inicials del registre:
Dim initBytes As Byte () = BitConverter. GetBytes (initReg)
Dim initBytesReversed As IEnumerable (Of Byte) = (De b As Byte In initBytes Take widthInBytes).
Dim initFifo com a cua nova (de booleà) (amplada - 1)
Per a cada b com a byte a initBytesReversed
Dim ba com a BitArray nou ({b})
Si no reverseBytes, llavors
Per a mi com a enter = 0 a 7
initFifo. Enqueue (ba (i))
Pròxim
Altrament
Per a mi com a enter = 7 a 0 Pas -1
initFifo. Enqueue (ba (i))
Pròxim
Finalitza If
Pròxim
Maj i XOR:
Esborra el registre com a UInteger = 0 'omple el registre de bits d'amplada amb zeros.
Feu mentre que msgFifo. Count> 0
Dim poppedBit As Integer = CInt (registre >> (amplada - 1)) I 1 'defineix abans del registre de desplaçament.
Dim shiftedBit As Byte = Convert. ToByte (msgFifo. Dequeue)
Si initFifo. Count> 0 Aleshores
Dim b As Byte = Convert. ToByte (initFifo. Dequeue)
shiftedBit = shiftedBit Xor b
Finalitza If
registre = registre << 1
registre = registre O shiftedBit
Si poppedBit = 1, llavors
register = registre Xor poly
Finalitza If
Bucle
'Conversions finals:
Dim crc As UInteger = register 'El registre conté la resta de la divisió == suma de verificació.
Si reverseCrc Aleshores
crc = reflect (crc, amplada)
Finalitza If
crc = crc Xor finalXor
crc = crc I (& HFFFFFFFFUI >> (32 - ample)) 'emmascara els bits menys significatius.
Torna crc
Funció final
