Un semplice CRC8 per Arduino

Durante la trasmissione su un canale disturbato può accadere che alcuni dei dati si corrompano. Ciò può accadere per motivi di natura accidentale (un’interferenza elettrica) oppure a causa di un’azione intenzionale (un tentativo di violare il canale). Per controllare la bontà dei dati trasmessi si ricorre spesso alle cosiddette somme di controllo, o checksum in inglese. Una somma di controllo altro non è che un metodo per sommare i vari bit di un messaggio. Le somme più semplici sono quelle algebriche, che però soffrono di un paio di grossi problemi: non riescono ad individuare il riordinamento dei dati né riescono ad accorgersi dell’introduzione di dati con valore 0. Per ovviare a questi inconvenienti sono stati inventati alcuni algoritmi di calcolo, tra cui uno dei più semplici è il CRC8.

CRC è l’acronimo di Cyclic Redundancy Check, ed è un algoritmo inventato da Wesley Peterson e pubblicato la prima volta nel 1961. Esso opera introducendo i dati in ingresso in una rete logica all’interno della quale scorrono in un registro. Durante lo scorrimento, vengono prelevati e combinati fra loro dei bit da determinate posizioni del registro: il risultato di questa operazione viene combinato con il bit in ingresso. Esistono versioni dell’algoritmo con differenti dimensioni del risultato: il CRC8, che produce una somma di controllo ad 8 bit, il CRC16, che produce una somma a 16 bit, ed il CRC32, che la produce a 32 bit, sono i più diffusi. Qui sotto vedete la rappresentazione del CRC8 (cliccando sull’immagine vedrete l’animazione dei dati in ingresso – fonte: Wikipedia):

Il CRC8 è l’algoritmo della famiglia CRC che produce, come detto, la somma di dimensioni più ridotte: esso è perciò utile solo in quelle situazioni in cui non si ricerca una sicurezza elevata. Infatti, più è piccola la dimensione della somma di controllo e maggiori sono le probabilità che si possa verificare una collisione, ossia che 2 sequenze di dati differenti producano la stessa somma. Ma nell’ambito di un utilizzo amatoriale, il CRC8 è più che sufficiente per garantire se non altro la validità dei dati trasmessi.

Il codice proposto è molto semplice. Si tratta di una funzione per Arduino che calcola il CRC8 di un qualunque array di byte fornito come parametro e lo restituisce sotto forma di byte. L’algoritmo è stato rielaborato da un codice sviluppato da Dallas Semiconductor (adesso facente parte di Maxim Integrated Products) per controllare i dati spediti dai suoi integrati che dialogavano con il bus 1-Wire.

//CRC-8 - algoritmo basato sulle formule di CRC-8 di Dallas/Maxim
//codice pubblicato sotto licenza GNU GPL 3.0
byte CRC8(const byte *data, byte len) {
  byte crc = 0x00;
  while (len--) {
    byte extract = *data++;
    for (byte tempI = 8; tempI; tempI--) {
      byte sum = (crc ^ extract) & 0x01;
      crc >>= 1;
      if (sum) {
        crc ^= 0x8C;
      }
      extract >>= 1;
    }
  }
  return crc;
}

Un paio di esempi. Il CRC8 dell’array {3, 2, 10, 56, 23, 0} corrisponde a 184 mentre il CRC8 dell’array {2, 3, 10, 56, 23, 0} corrisponde a 66: come potete vedere, lo scambio di posizione di 2 byte produce 2 CRC completamente differenti. Lo stesso scambio non sarebbe stato rilevabile nel caso avessimo usato un controllo basato sulla semplice somma aritmetica.

PS: ho messo online una vecchia versione della funzione, quella che avevo inserito cercando di ottimizzarla calcolava CRC solo per vettori con elementi diversi da 0.