Ci sono molte opzioni per calcolare il checksum CRC su Internet. Ma cos'è esattamente un checksum e perché viene calcolato in questo modo? Scopriamolo.
Istruzioni
Passo 1
Per prima cosa, facciamo un po' di teoria. Quindi cos'è esattamente il CRC? In breve, questa è una delle varietà di calcolo del checksum. Il checksum è un metodo per verificare l'integrità delle informazioni ricevute sul lato ricevitore durante la trasmissione sui canali di comunicazione. Ad esempio, uno dei controlli più semplici consiste nell'utilizzare il bit di parità. Questo è quando vengono sommati tutti i bit del messaggio trasmesso e se la somma risulta pari, viene aggiunto 0 alla fine del messaggio, se è dispari, quindi 1. Alla ricezione, la somma dei anche i bit del messaggio vengono contati e confrontati con il bit di parità ricevuto. Se differiscono, si sono verificati errori durante la trasmissione e le informazioni trasmesse sono state distorte.
Ma questo metodo per rilevare la presenza di errori è molto poco informativo e non sempre funziona, perché se diversi bit del messaggio sono distorti, la parità della somma potrebbe non cambiare. Pertanto, ci sono molti più controlli "avanzati", incluso CRC.
Infatti, CRC non è una somma, ma il risultato della divisione di una certa quantità di informazioni (messaggio informativo) per una costante, o meglio, il resto della divisione di un messaggio per una costante. Tuttavia, il CRC è anche storicamente indicato come "checksum". Ogni bit del messaggio contribuisce al valore CRC. Cioè, se almeno un bit del messaggio originale cambia durante la trasmissione, cambierà anche il checksum, e in modo significativo. Questo è un grande vantaggio di tale controllo, poiché consente di determinare in modo inequivocabile se il messaggio originale è stato distorto durante la trasmissione o meno.
Passo 2
Prima di iniziare a calcolare il CRC, è necessaria un po' più di teoria.
Qual è il messaggio originale dovrebbe essere chiaro. È una sequenza contigua di bit di lunghezza arbitraria.
Qual è la costante per la quale dovremmo dividere il messaggio originale? Anche questo numero è di qualsiasi lunghezza, ma di solito vengono utilizzati multipli di 1 byte - 8, 16 e 32 bit. È solo più facile contare, perché i computer funzionano con i byte, non con i bit.
La costante divisore viene solitamente scritta come un polinomio (polinomio) in questo modo: x ^ 8 + x ^ 2 + x ^ 1 + x ^ 0. Qui, il grado del numero "x" indica la posizione dell'un bit nel numero, a partire da zero, e il bit più significativo indica il grado del polinomio e viene scartato durante l'interpretazione del numero. Cioè, il numero precedentemente scritto non è altro che (1) 00000111 in binario o 7 in decimale. Tra parentesi ho indicato la cifra implicita più significativa del numero.
Ecco un altro esempio: x ^ 16 + x ^ 15 + x ^ 2 + x ^ 0 = (1) 1000000000000101 = 0x8005 = 32773.
Di solito vengono utilizzati alcuni polinomi standard per diversi tipi di CRC.
Passaggio 3
Quindi come si calcola il checksum? Esiste un metodo di base - dividere un messaggio in un polinomio "frontale" - e le sue modifiche per ridurre il numero di calcoli e, di conseguenza, accelerare il calcolo del CRC. Vedremo il metodo di base.
In generale, la divisione di un numero per un polinomio viene eseguita secondo il seguente algoritmo:
1) viene creato un array (registro), riempito di zeri, di lunghezza pari alla lunghezza della larghezza del polinomio;
2) il messaggio originario è integrato con zeri nei bit meno significativi, in quantità pari al numero di bit del polinomio;
3) un bit più significativo del messaggio viene inserito nel bit meno significativo del registro e un bit viene spostato dal bit più significativo del registro;
4) se il bit esteso è uguale a "1", allora i bit vengono invertiti (operazione XOR, OR esclusivo) in quei bit di registro che corrispondono a quelli del polinomio;
5) se ci sono ancora dei bit nel messaggio, passare al punto 3);
6) quando tutti i bit del messaggio sono entrati nel registro e sono stati elaborati da questo algoritmo, il resto della divisione rimane nel registro, che è il checksum CRC.
La figura illustra la divisione della sequenza di bit originale per il numero (1) 00000111, o il polinomio x ^ 8 + x ^ 2 + x ^ 1 + x ^ 0.
Passaggio 4
Ci sono ancora un paio di tocchi aggiuntivi. Come avrai notato, il messaggio può essere diviso per qualsiasi numero. Come sceglierlo? Esistono numerosi polinomi standard utilizzati per calcolare il CRC. Ad esempio, per CRC32 potrebbe essere 0x04C11DB7 e per CRC16 potrebbe essere 0x8005.
Inoltre, nel registro all'inizio del calcolo, puoi scrivere non zeri, ma qualche altro numero.
Inoltre, durante i calcoli, immediatamente prima dell'emissione del checksum CRC finale, possono essere divisi per un altro numero.
E l'ultima cosa. I byte del messaggio in fase di scrittura nel registro possono essere posizionati come bit più significativo "forward", e viceversa, il meno significativo.
Passaggio 5
Sulla base di tutto quanto sopra, scriviamo una funzione Basic. NET che calcola il checksum CRC prendendo un numero di parametri che ho descritto sopra e restituendo il valore CRC come numero senza segno a 32 bit.
Funzione condivisa pubblica GetCrc (ByVal byte As Byte (), ByVal poly As UInteger, facoltativo ByVal larghezza As Integer = 32, facoltativo ByVal initReg As UInteger = & HFFFFFFFFUI, facoltativo ByVal finalXor As UInteger = & HFFFFFFFFUI, facoltativo ByVal reverseBytes, facoltativo Boolean ByVal reverseCrc As Boolean = True) As UInteger
Dim widthInBytes As Integer = width / 8
'Integrare la larghezza del messaggio con zeri (calcolo in byte):
ReDim Preserve byte (bytes. Length - 1 + widthInBytes)
'Crea una coda di bit dal messaggio:
Dim msgFifo As New Queue (Of Boolean) (bytes. Count * 8 - 1)
Per ogni b come byte in byte
Dim ba come nuovo BitArray ({b})
Se reverseBytes Then
Per i come numero intero = da 0 a 7
msgFifo. Enqueue (ba (i))
Prossimo
Altro
Per i come numero intero = da 7 a 0 passaggio -1
msgFifo. Enqueue (ba (i))
Prossimo
Finisci se
Prossimo
'Crea una coda dai bit di riempimento iniziali del registro:
Dim initBytes As Byte () = BitConverter. GetBytes (initReg)
Dim initBytesReversed As IEnumerable (Of Byte) = (From b As Byte In initBytes Take widthInBytes). Reverse
Dim initFifo As New Queue (Of Boolean) (larghezza - 1)
Per ogni b come byte in initBytesReversed
Dim ba come nuovo BitArray ({b})
Se non inverti Byte Allora
Per i come numero intero = da 0 a 7
initFifo. Enqueue (ba (i))
Prossimo
Altro
Per i come numero intero = da 7 a 0 passaggio -1
initFifo. Enqueue (ba (i))
Prossimo
Finisci se
Prossimo
'Maiusc e XOR:
Dim register As UInteger = 0 'riempi il registro width-bit con zero.
Esegui mentre msgFifo. Count> 0
Dim poppedBit As Integer = CInt (register >> (width - 1)) E 1' definire prima del registro a scorrimento.
Dim shiftedBit As Byte = Convert. ToByte (msgFifo. Dequeue)
Se initFifo. Count> 0 Allora
Dim b As Byte = Convert. ToByte (initFifo. Dequeue)
shiftedBit = shiftedBit Xor b
Finisci se
registro = registro << 1
register = register O shiftedBit
Se poppedBit = 1 Allora
registro = registro Xor poly
Finisci se
Ciclo continuo
'Conversioni finali:
Dim crc As UInteger = register 'Il registro contiene il resto della divisione == checksum.
Se reverseCrc Allora
crc = riflettere (crc, larghezza)
Finisci se
crc = crc Xor finalXor
crc = crc And (& HFFFFFFFFUI >> (32 - larghezza)) 'maschera i bit meno significativi.
Restituisci crc
Fine funzione
