La specifica USB utilizza il classico CRC (Cyclic Redundancy Checksums) per garantire l’integrità dei pacchetti dagli errori di trasmissione. I pacchetti previsti dallo standard USB sono quattro: token, data, handshake e special. Ogni pacchetto è diviso in campi di 8 bit (o multipli di 8) ciascuno. I bit sono inviati sul bus dal bit meno significativo al più significativo. La specifica USB utilizza due polinomi differenti per il calcolo del CRC: uno per i token e l’altro per i dati. La tabella 1 pone in evidenza i vari pacchetti in relazione ai gruppi presenti nella specifica.
Implementazione CRC per USb
Il generatore utilizzato per i token deve essere conforme al polinomio:
X5 + X2 + X0
mentre si utilizza il polinomio
x16 + x15 + x2 + x0
per i pacchetti dati. Il pacchetto DATA può contenere al massimo 1024 byte con un CRC a 16 bit. I listati 1 e 2 scritti in Perl possono essere utilizzati per controllare l’implementazione e verificare i valori del CRC. In questo modo possiamo verificare e testare la trasmissione di pacchetti.
Esempi per il calcolo del CRC
Vediamo di seguito alcuni esempi su dei pacchetti dati applicando, come previsti dalla specifica, il polinomio CRC16. Consideriamo due pacchetti, Data1 e Data2, ognuno con 4 byte di dati (in notazione esadecimale), con l’uso dell’algoritmo CRC16 e con il pacchetto risultante NRZ, si genera la seguente sequenza:
DATA1, compreso dei seguenti pacchetti: 00 01 02 03. Ricorrendo alla routine scritta in Perl, listato 2, si ottiene lo stream:
CRC16 00000000100000000100000011000000
1111011101011110
00000001110000110000000010000000010
00000110000001111011101011110XX1;
Oppure con:
DATA2
23 45 67 89
CRC16
11000100101000101110011010010001
0111000000111000
00000001110100101100010010100010111
00110100100010111000000111000XX1;
Viceversa, con un token SOF, con timestamp di 0x710, l’algoritmo da utilizzare è il CRC5. Utilizzando la routine Perl del listato 1, il CRC che generiamo sul timestamp produce il seguente risultato:
CRC5 00001000111
10100
Il timestamp, il CRC e l’EOP (END Of Packet) può essere posto con il Sync e PID per generare il pacchetto NRZ (Non Return to Zero), come segue:
00000001101001010000100011110100XX1;
In questo esempio il campo NRZ è uguale a 00000001 e il pacchetto EOP viene indicato come XX1. I campi PID e PID check assumono il valore di 0101 e 1010 rispettivamente. Per quanto stabilito dalla specifica USB, il bit stuffing e la conversione in NRZI (Non Return to Zero Invert) è permessa prima che il pacchetto è trasmesso. Il successivo esempio mostra la generazione di un CRC5 e il pacchetto NRZ risultante a fronte SETUP, OUT, IN e token SOF (per approfondimenti consulta il seguente link).
setup addr 15 endp e
crc5 10101000111
10111
00000001101101001010100011110111XX1;
out addr 3a endp a
crc5 01011100101
11100
00000001100001110101110010111100XX1;
in addr 70 endp 4
crc5 00001110010
01110
00000001100101100000111001001110XX1;
sof timestamp 001
crc5 10000000000
10111
00000001101001011000000000010111XX1;
Algoritmo di swap
Lo scambio tra due elementi può essere fatto anche senza l’uso di variabili temporanee. L’algoritmo utilizza l’operatore logico XOR in questo modo, oltre a non utilizzare spazio sullo stack, permette di sfruttarne la sua velocità di esecuzione. Questo algoritmo è rappresentato schematicamente in questo modo:
A <- A xor B
B <- B xor A
A <- A xor B
L’algoritmo è implementato in C utilizzando una macro:
#define SWAP(A,B) (A) ^= (B); (B) ^= (A); (A) ^= (B);
#! /usr/local/bin/perl ## crc5 nrzstream ## e.g. crc5 1000111 ## nrz stream is sent in left to right order ## generated crc should also be sent out in left to right order sub xor5 { local(@x) = @_[0..4]; local(@y) = @_[5..9]; local(@results5) = (); for($j=0;$j<5;$j++) { if (shift(@x) eq shift(@y)) { push(@results5, ‘0’); } else { push(@results5, ‘1’); } } return(@results5[0..4]); } { local($st_data) = $ARGV[0]; local(@G) = (‘0’,’0’,’1’,’0’,’1’); local(@data) = split (//,$st_data); local(@hold) = (‘1’,’1’,’1’,’1’,’1’); if (scalar(@data) > 0) { loop5: while (scalar(@data) > 0) { $nextb=shift(@data); if (($nextb ne “0”) && ($nextb ne “1”)) {next loop5} ## comment character if ($nextb eq shift(@hold)) {push(@hold, ‘0’)} else { push(@hold, ‘0’); @hold = &xor5(@hold,@G); } ## print (@hold); print “\n”; } } ## print (@hold); print “\n”; ## invert shift reg contents to generate crc field for ($i=0;$i<=$#hold;$i++) {if (@hold[$i] eq “1”) {print(“0”)} else { print(“1”)} } print “\n”; }
Listato 1 |
#! /usr/local/bin/perl ## usage: ## crc16 nrzstream ## nrz stream is sent in left to right order ## generated crc should also be sent out in left to right order sub xor16 { local(@x) = @_[0..15]; local(@y) = @_[16..31]; local(@results16) = (); for($j=0;$j<16;$j++) { if (shift(@x) eq shift(@y)) { push(@results16, ‘0’); } else { push(@results16, ‘1’); } } return(@results16[0..15]); } { local($st_data) = $ARGV[0]; local(@G) = (‘1’,’0’,’0’,’0’,’0’,’0’,’0’,’0’,’0’,’0’,’0’,’0’,’0’,’1’,’0’,’1’); local(@hold) = (‘1’,’1’,’1’,’1’,’1’,’1’,’1’,’1’,’1’,’1’,’1’,’1’,’1’,’1’,’1’,’1’); local(@data) = split (//,$st_data); if (scalar(@data) > 0) { loop16: while (scalar(@data) > 0) { $nextb=shift(@data); if (($nextb ne “0”) && ($nextb ne “1”)) {next loop16} ## comment character if ($nextb eq shift(@hold)) {push(@hold, ‘0’)} else { push(@hold, ‘0’); @hold = &xor16(@hold,@G); } } } # print (@hold); print “\n”; ## invert shift reg to generate CRC field for ($i=0;$i<=$#hold;$i++) {if (@hold[$i] eq “1”) {print(“0”)} else { print(“1”)} } print “\n”; }
Listato 2 |
La particolarità del CRC è la semplicità di implementazione, anche facile da un punto di vista matematico. Seppur queste “semplici” caratteristiche, riesce a rilevare rumori del canale in maniera efficiente. La tecnica di lavoro consiste nella cyclic error-correcting codes.