CRC su USB e algoritmo di SWAP in C

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.

Tabella 1: pacchetti CRC

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 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
Scarica subito una copia gratis

Una risposta

  1. Avatar photo Maurizio Di Paolo Emilio 21 Gennaio 2017

Scrivi un commento

Seguici anche sul tuo Social Network preferito!

Send this to a friend