Sebbene possano esistere opzioni più veloci rispetto al CRC, se le utilizzi, è probabile che finisca per sacrificare un certo grado di capacità di rilevamento degli errori. Un'alternativa potrebbe essere quella di utilizzare il codice CRC ottimizzato per la tua applicazione.

Un'opzione per aiutarti è pycrc che è uno strumento (scritto in python < sup> 1 ) che può generare codice sorgente C per dozzine di combinazioni di modello crc e algoritmo . Ciò consente di ottimizzare la velocità e le dimensioni della propria applicazione selezionando e confrontando diverse combinazioni. ^{1: Richiede Python 2.6 o versioni successive.}

Supporta il crc-8 modello , ma supporta anche crc-5 , crc-16 e crc-32 tra gli altri. Per quanto riguarda gli algoritmi , supporta bit-by-bit , bit-by-bit-fast e table-driven .

Ad esempio (download dell'archivio):

$ wget --quiet http://sourceforge.net/projects/pycrc/files/pycrc/pycrc-0.8/pycrc-0.8.tar.gz/download
$ tar -xf pycrc-0.8.tar.gz
$ cd pycrc-0.8
$ ./pycrc.py --model=crc-8 --algorithm=bit-by-bit      --generate c -o crc8-byb.c
$ ./pycrc.py --model=crc-8 --algorithm=bit-by-bit-fast --generate c -o crc8-bybf.c
$ ./pycrc.py --model=crc-8 --algorithm=table-driven    --generate c -o crc8-table.c
$ ./pycrc.py --model=crc-16 --algorithm=table-driven   --generate c -o crc16-table.c
$ wc *.c
   72   256  1790 crc8-byb.c
   54   190  1392 crc8-bybf.c
   66   433  2966 crc8-table.c
  101   515  4094 crc16-table.c
  293  1394 10242 total

Puoi anche fare cose funky come specificare usando le ricerche dual nibble (con una tabella di ricerca a 16 byte) piuttosto che la ricerca a byte singolo, con una tabella di ricerca a 256 byte.

Ad esempio (clonazione del repository git):

$ git clone http://github.com/tpircher/pycrc.git
$ cd pycrc
$ git branch
* master
$ git describe
v0.8-3-g7a041cd
$ ./pycrc.py --model=crc-8 --algorithm=table-driven --table-idx-width=4 --generate c -o crc8-table4.c
$ wc crc8-table4.c
  53  211 1562 crc8-table4.c

Dati i limiti di memoria e velocità, questa opzione potrebbe essere il miglior compromesso tra velocità e dimensioni del codice. L'unico modo per essere sicuri sarebbe di benchmark però.

Il repository git pycrc si trova su github , così come il suo issue tracker , ma può anche essere scaricato da sourceforge .

La semplice parità un bit (in pratica XORing dei dati su se stessa ripetutamente) è più veloce che si può ottenere . Però perdi un sacco di errori nel controllo di un CRC.

In pseudocode:

char checksum = 0;
for each (char c in buffer)
{
    checksum ^= c;
    SendToPC(c);
}
SendToPc(checksum);

Un ottimo documento che confronta le prestazioni di vari checksum e CRC in un contesto integrato:

L'efficacia dei checksum per reti integrate

Alcune citazioni dalle conclusioni (basate sui loro studi sulle probabilità di errore non rilevate):

Quando dominano gli errori di burst

XOR, two’s complement addition, and CRC checksums provide better error detection performance than one’s complement addition, Fletcher, and Adler checksums.

In altre applicazioni

a “good” CRC polynomial, whenever possible, should be used for error detection purposes

Se il costo del calcolo è molto limitato

(come nel tuo caso), usa (in ordine di efficacia):

• checksum di Fletcher
• aggiunta del complemento
• aggiunta del complemento a due

Altre citazioni:

The Fletcher checksum has lower computational cost than the Adler checksum and, contrary to popular belief, is also more effective in most situations.

e

There is generally no reason to continue the common practice of using an XOR checksum in new designs, because it has the same software computational cost as an addition-based checksum but is only about half as effective at detecting errors.

Il checksum Adler dovrebbe essere sufficiente per verificare le distorsioni della trasmissione. Viene utilizzato dalla libreria di compressione Zlib ed è stato adottato da Java 3D Graphics Graphics Standard per fornire un controllo dell'integrità dei dati rapido ma efficace.

Dalla pagina di Wikipedia :

An Adler-32 checksum is obtained by calculating two 16-bit checksums A and B and concatenating their bits into a 32-bit integer. A is the sum of all bytes in the string plus one, and B is the sum of the individual values of A from each step.

At the beginning of an Adler-32 run, A is initialized to 1, B to 0. The sums are done modulo 65521 (the largest prime number smaller than 2^16 or 65536). The bytes are stored in network order (big endian), B occupying the two most significant bytes.

The function may be expressed as

 A = 1 + D1 + D2 + ... + Dn (mod 65521)
 B = (1 + D1) + (1 + D1 + D2) + ... + (1 + D1 + D2 + ... + Dn) (mod 65521)
   = n×D1 + (n-1)×D2 + (n-2)×D3 + ... + Dn + n (mod 65521)

 Adler-32(D) = B × 65536 + A

where D is the string of bytes for which the checksum is to be calculated, and n is the length of D.

Non sono a conoscenza di nulla che sia efficace nel rilevamento degli errori come un CRC e più veloce - se ci fosse, la gente lo userebbe invece.

Potresti provare un semplice checksum, ma è molto meno probabile che rilevi errori.

Bene, anche la logica di checksum è buona e le persone possono aiutare con algoritmi più veloci.

Se vuoi migliorare la velocità del tuo componente, potresti dover cambiare la tecnica generale per separare il componente di trasferimento dal componente di convalida.

Se hai questi due elementi indipendenti (su diversi thread), puoi ottenere la massima velocità di trasferimento e inviare nuovamente i pacchetti non riusciti.

Algorithm avrebbe un aspetto simile a:

• Il server si divide in dimensioni di pacchetti note (ad esempio blocchi di 1 KB). Li mette in coda "da inviare".
• Ogni pacchetto viene inviato con un ID 16 o 32 bit E il suo checksum.
• Il client riceve ciascun pacchetto e lo inserisce in una coda da elaborare.
• In un thread separato che il client prende di un pacchetto alla volta, esegue la convalida.
  • In caso di successo lo aggiunge alla raccolta finale di pacchetti (in ordine ID) che sono
  • In caso di errore riporta l'ID fallito al server, che accoda quel pacchetto da inviare nuovamente.
• Una volta che hai ricevuto e convalidato i pacchetti e hai gli ID nel sequnce corretto (a partire da 1) puoi iniziare a scriverli su disco (o fare ciò che è richiesto).

Questo ti permetterà di trasmettere alla massima velocità possibile e se giochi con le dimensioni del tuo pacchetto puoi calcolare il tasso di errore optimium VS convalida / rispondi il tasso.

I checksum sono tradizionali

(riduci # '+ stream)

Anche XOR come indicato sopra funzionerebbe allo stesso modo

(riduce # 'stream XOR)

Uno schema leggermente più elaborato (più lento) è il controllo di parità standard per le connessioni seriali.

A questo livello, stai commerciando correttezza per la velocità. Questi a volte falliscono.

Al livello successivo più sofisticato, puoi usare alcune cose tipo crc / hash.

Un altro design potrebbe essere quello di aumentare la dimensione del blocco utilizzato per lo streaming.

Dovresti avere una stima del tasso di errore effettivo per ottimizzare la selezione dell'algoritmo e i parametri per la dimensione del blocco.