Calcolatore di Crc

Dato un flusso di dati e una serie di parametri, il calcolatore ne calcola il checksum CRC.

Cos’è il CRC

CRC sta per Cyclic Redundancy Check. È un codice di ridondanza a carattere ciclico: si basa su un’operazione di divisione polinomiale in GF(2) (aritmetica “modulo-2”), pensando ai dati come a un grande polinomio i cui coefficienti sono i bit.

Il risultato (il resto della divisione) è un “digest” di lunghezza fissa, tipicamente 8, 16, 32 o più bit, usato come impronta contro errori accidentali.

Ruolo del calcolatore di CRC

Un calcolatore di CRC esegue questi passi:

1. Parametri di configurazione
   • Polinomio generatore (ad es. 0x04C11DB7 per CRC-32)
   • Valore iniziale del registro (initial remainder)
   • Riflessione (reflect in/out): se i bit vengono presi in ordine inverso
   • XOR finale (final XOR value)
2. Elaborazione dei dati
   • I bit di input scorrono (bitwise) in un registro di shift, combinandosi con il polinomio tramite XOR.
   • In implementazioni software si ricorre spesso a tabelle pre-calcolate (table-driven) per accelerare il processo.
3. Output
   • Al termine, il contenuto del registro è il resto della divisione polinomiale, cioè il CRC.
   • Viene spesso presentato in esadecimale.

Parametri più comuni

Standard CRC	Polinomio	Larghezza	Init	Refin/Rofout	XORout
CRC-8	0x07	8 b	0x00	false/false	0x00
CRC-16-IBM	0x8005	16 b	0x0000	true/true	0x0000
CRC-16-CCITT	0x1021	16 b	0xFFFF	false/false	0x0000
CRC-32	0x04C11DB7	32 b	0xFFFFFFFF	true/true	0xFFFFFFFF

Esempio pratico

Calcoliamo il CRC-32 della stringa ASCII "123456789":

1. Parametri standard CRC-32:
   • polinomio = 0x04C11DB7
   • init = 0xFFFFFFFF
   • reflect in/out = true
   • final XOR = 0xFFFFFFFF
2. Risultato noto:arduinoCopiaModificaCRC-32("123456789") = 0xCBF43926

Questo valore è usato come test di correttezza: ogni implementazione CRC-32 valida deve produrre esattamente CB F4 39 26.

Implementazioni di un calcolatore di CRC

• Hardware
  • Shift-register con XOR tap corrispondenti ai coefficienti del polinomio. Molto veloce, spesso integrato nei controller di rete o nei chip di memoria.
• Software
  • Bitwise: esegue l’algoritmo base, lento ma semplice.
  • Table-driven (lookup table): suddivide l’input in byte e lo processa con tabelle da 256 voci, molto più veloce.
  • Slice-by-N: ottimizzazioni che processano più byte in parallelo.

A cosa serve

• Verifica integrità nei protocolli di comunicazione (Ethernet, USB, CAN bus, etc.).
• Controllo errori nei file system e nelle memorie di massa.
• Validazione di firmware, pacchetti dati e archivi.