AngoLinux

Calcolo del CRC di una sequenza di caratteri immessi da standard input

- A cura del Prof. Stefano Salvi -

Arriviamo all'algoritmo di calcolo del CRC. Questo algoritmo prevede un'estensivo uso delle operazioni bit a bit.

Il testo dell'esercizio è il seguente:

Scrivere un programma C che legga da standard input una sequenza di codici (caratteri) terminata da EOF (ctrl-D) e calcoli il CRC della sequanza, usando come polinomio generatore il valore 0x11021 (che corrisponde al polinomio generatore standard CCITT x¹⁶+x¹²+x⁵+1).

Calcolo del CRC

Il CRC non e' altro che il resto della divisione tra la stringa di bit di ingresso (la sequenza di codici concatenata), intesa come coefficienti di un polinomio, per un polinomio divisore dato. Il polinomio divisore è espresso anch'esso come una stringa di coefficienti. Naturalmente se vogliamo un resto a 16 bit, la stringa dei coefficienti (detta polinomio generatore) deve essere a 17 bit.

La divisione tra polinomi si esegue in maniera molto simile alla divisione tra numeri, usando le stringhe dei coefficienti.
Ci sono solo tre differenze:

• Per ottenere il resto si devono agggiungere alla stringa del polinomio dividendo tanti bit a 0 a destra quanti sono i bit del resto (quindi i bit del divisore - 1)
• Si valuta che il divisore ci sta nel dividendo non quando il dividendo è realente maggiore del divisore, ma quando ha lo stesso ordine di grandezza, vale a dire quando il suo bit più significativo vale 1.
• La sottrazione per ridurre il dividendo và fatta senza riporti, quindi si riduce ad un'operazione di Exclusive Or (XOR).

Passiamo ad un esempio, per chiarire le cose. Calcoliamo, ad esempio, il CRC della stringa esadecimale 0xa3 0xac con polinomio generatore 0x1a.
Per prima cosa trasformeremo i codici in binario (cosa che nel calcolatore non sarà necessaria, visto che il formato interno &egrvae già binario) e li concateneremo.
Otterremo la seguente stringa di bit.

1010 0011 1010 1100

Per semplificare la lettura ho lasciato uno spazio dopo ogni gruppo di quattro bit, corrispondenti ad una cifra esadecimale.
Adesso occorre agiungere tanti bit quanto è il resto. Il polinomio generatore (0x1a) è lungo 5 bit, quindi il resto e' di quattro bit. Aggiungo quindi quattro bit a 0:

1010 0011 1010 1100 0000

Ora possiamo incominciar eil meccanismo della divisione. Scopriamo che il bit più a sinistra vale 1, quindi cominciamo subito con la sottrazione:

1010 0011 1010 1100 0000 1101 0 0111 0

Abbiamo eseguito l'XOR tra i primi bit del dividendo ed il divisore, ottenendo il promo resto.
A questo punto possiamo portare giù la prossima cifra

1010 0011 1010 1100 0000 1101 0| 0111 00

Vediamo che il bit 4 (evidenziato in azzurro) è ancora ad 1, quindi procediamo alla sottrazione (all' XOR):

1010 0011 1010 1100 0000 1101 0 0111 00 110 10 001 10

Portiamo giù la prossima cifra:

1010 0011 1010 1100 0000 1101 0 | 0111 00| 110 10| 001 101

Questa volta il bit 4 (sempre evidenziato in azzurro) non è ad uno, quindi non eseguiamo la somma
Portiamo giù quindi un'altra cifra:

1010 0011 1010 1100 0000 1101 0 | 0111 00 | 110 10 | 001 101| 01 1011

A questo punto ripeto le operazioni indicate, fino ad arrivare al resto finale:

1010 0011 1010 1100 0000 1101 0 0111 00 110 10 001 101 01 1011 1 1010 0 0001 1 0001 10 001 101 01 1010 1 1010 0 0000 1 0000 11 000 110 00 1100 0 1100 0 1101 0 0001 00 001 000 01 0000 1 1010 0 1010

Quindi arriviamo a calcolare il CRC che vale 1010 in binario, vale a dire 0xa in esadecimale.
Proviamo a descrivere il procedimento in forma algoritmica:
Assumiamo che il polinomio generatore abbia dimensone g bit e che il bit più significativo del codice sia 1.

• Eseguire l'XOR tra i primi g bit del codice ed il polinomio generatore, ottenendo il primo resto r.
• Per ogni bit dopo il g:
  • Ruotare il resto r a sinistra
  • Aggiungere il bit che si stà trattando come bit meno significativo ad r
  • Se il bit g del resto r (il più significativo) è ad 1, eseguire l'XOR tra il resto r ed il polinimio generatore

... 0000 1010 0011 1010 1100 0000
  0 0000 1
    0000 10
     000 101
      00 1010
       0 1010 0
         1101 0
         0111 00
          110 10
          001 101

• Per ogni bit del codice:
  • Ruotare il resto r a sinistra
  • Aggiungere il bit che si stà trattando come bit meno significativo ad r
  • Se il bit g del resto r (il più significativo) è ad 1, eseguire l'XOR tra il resto r ed il polinimio generatore

Una possibile soluzione è la seguente:

// Tizio - Pinco - 3AIN - 12/04/2002 // Programma che calcola il CRC di una sequenza di caratteri // immessi da tastiera, terminati con EOF #include <stdio.h> #define PG 0x11021 /* Polinomio generatre */ int crc(int oldcrc, unsigned char toadd); /* Aggiunge toadd al CRC calcolato */ main() { int resto=0; // CRC int c; // Carattere letto int i = 0; // Contatore dei caratteri printf("Inserisci una sequenza di caratteri: "); while((c=getchar())!=EOF) { resto=crc(resto,c); // Agginge il carattere letto al CRC dei precedenti i++; // Conta i caratteri letti } resto=crc(resto,0); // Agginge al CRC i primi otto zeri resto=crc(resto,0); // Agginge al CRC i secondi otto zeri in fondo printf("\nLetti %d caratteri, CRC calcolato: %x\n", i, resto); } /* Aggiunge i bit del codice oldcrc al dividendo, per * calcolare il nuovo CRC */ int crc(int oldcrc, unsigned char toadd) { int i; // Indice del bit // I bit del carattere vanno trattati dal piu' significativo al meno for(i=0;i<8;i++) // Per ogni bit del byte { oldcrc= (oldcrc<<1) | (toadd>>7); // Aggiunge il bit piu' significativo // del codice in fondo al CRC, // spostando a sinistra i bit del CRC toadd <<= 1; // Toglie il bit gestito dal codice if((oldcrc & 0x10000) != 0) // Se il divisore ci sta' (alla sua maniera) { oldcrc=oldcrc^PG; // Allora lo toglie (sottrazione senza riporti, // quindi XOR } } return oldcrc; // Restituisce il CRC ricalcolato }

Per provare il programma, scaricare il sorgente, compilarlo con il comando cc crc.c ed eseguirlo con il comando ./a.out.

[Home Page dell'ITIS "Fermi"] [Indice Terza] [Precedente] [Successivo]

© Ing. Stefano Salvi - Released under GPL licence