Calcolo di un CRC a 8 bit con il preprocessore C?

Question

Scrivo codice per un microcontroller a 8 bit con pochi byte di RAM. Ha un lavoro semplice che è quello di trasmettere 7 parole a 16 bit, quindi il CRC di quelle parole. I valori delle parole sono scelti al momento della compilazione. Il CRC in particolare è "resto della divisione di parola da 0 a parola 6 come numero senza segno diviso per il polinomio x^8 + x² + x + 1 (valore iniziale 0xFF)."

È possibile calcolare il CRC di quei byte in fase di compilazione utilizzando il preprocessore C C?

#define CALC_CRC(a,b,c,d,e,f,g) /* what goes here? */ 

#define W0 0x6301 
#define W1 0x12AF 
#define W2 0x7753 
#define W3 0x0007 
#define W4 0x0007 
#define W5 0x5621 
#define W6 0x5422 
#define CRC CALC_CRC(W0, W1, W2, W3, W4, W5, W6) 

Answer 1

L'algoritmo di checksum semplice è il cosiddetto controllo di parità longitudinale, che rompe i dati in "parole" con un numero n di bit fisso, e quindi calcola la esclusiva o di tutte quelle parole. Il risultato viene aggiunto al messaggio come una parola in più.

Per verificare l'integrità di un messaggio, il ricevitore calcola l'esclusiva o tutte le sue parole, compreso il checksum; se il risultato non è una parola con n zeri, il ricevitore sa che si è verificato un errore di trasmissione.

(souce: wiki)

Nel tuo esempio:

#define CALC_CRC(a,b,c,d,e,f) ((a)^(b)^(c)^(d)^(e)^(f)) 

Answer 2

Esonero di responsabilità: questo non è davvero una risposta diretta, ma piuttosto una serie di domande e suggerimenti che sono troppo lunghi per un commento.

Prima domanda: avete il controllo su entrambe le estremità del protocollo, ad es. puoi scegliere l'algoritmo di checksum tramite te stesso o un collega che controlla il codice all'altro capo?

Se SI alla domanda # 1:

È necessario valutare il motivo per cui è necessario il checksum, che cosa checksum è appropriato, e le conseguenze di ricezione di un messaggio danneggiato con un checksum valido (che fattori in entrambi il che cosa & perché).

Qual è il tuo mezzo di trasmissione, protocollo, bitrate, ecc.? Ti stai aspettando/osservando errori di bit? Quindi, ad esempio, con SPI o I2C da un chip a un altro sulla stessa scheda, se si verificano errori di bit, è probabilmente colpa dei tecnici HW o è necessario rallentare la frequenza di clock o entrambi. Un checksum non può far male, ma non dovrebbe essere davvero necessario. D'altra parte, con un segnale a infrarossi in un ambiente rumoroso, e avrai una probabilità di errore molto più alta.

Le conseguenze di un messaggio errato è sempre la domanda più importante qui. Quindi se stai scrivendo il controller per il termometro digitale della camera e inviando un messaggio per aggiornare il display 10 volte al secondo, un valore errato di 1000 messaggi ha pochissimi danni reali. Nessun checksum o checksum debole dovrebbe andare bene.

Se questi 6 byte sparano un missile, impostano la posizione di un bisturi robotico, o causano il trasferimento di denaro, è meglio essere sicuri di avere il giusto checksum e potrebbe anche voler guardare in un hash crittografico (che potrebbe richiedere più RAM di quella che hai).

Per le cose intermedie, con notevole pregiudizio per le prestazioni/soddisfazione del prodotto, ma nessun danno reale, è la vostra chiamata.Ad esempio, un televisore che occasionalmente modifica il volume anziché il canale potrebbe infastidire i clienti - più che semplicemente abbandonando il comando se un buon CRC rileva un errore, ma se sei nel business di rendere economico/televisori knock-off che potrebbero andare bene se il prodotto viene commercializzato più rapidamente.

Quindi quale somma di controllo è necessaria?

Se una o entrambe le estremità hanno il supporto HW per un checksum incorporato nella periferica (abbastanza comune in SPI per esempio), questa potrebbe essere una scelta saggia. Quindi diventa più o meno libero da calcolare.

Un LRC, come suggerito dalla risposta di vulkanino, è l'algoritmo più semplice.

Wikipedia ha alcune informazioni decente su come/perché scegliere un polinomio se si ha realmente bisogno di un CRC: http://en.wikipedia.org/wiki/Cyclic_redundancy_check

Se NO alla domanda # 1:

Che CRC algoritmo/polinomiale fa il l'altra estremità richiede? Questo è quello con cui sei bloccato, ma dicendoci potresti ottenere una risposta migliore/più completa.

Pensieri sulla realizzazione:

maggior parte degli algoritmi sono abbastanza leggero in termini di RAM/registri, che richiede solo un paio di byte in più. In generale, una funzione risulterà in un codice migliore, più pulito, più leggibile e debugger-friendly.

Si dovrebbe pensare alla soluzione macro come a un trucchetto di ottimizzazione e, come tutti i trucchi di ottimizzazione, saltare a loro all'inizio potrebbe essere uno spreco di tempo di sviluppo e una causa di più problemi di quanti ne valga la pena.

utilizzando una macro ha anche alcune strane implicazioni potrebbe non avere considerato ancora:
siete consapevoli che il preprocessore solo può fare il calcolo se tutti i byte in un messaggio sono fissati al momento della compilazione, giusto? Se hai una variabile, il compilatore deve generare codice. Senza una funzione, quel codice sarà inarcato ogni volta che viene usato (sì, questo potrebbe significare un sacco di utilizzo della ROM). Se tutti i byte sono variabili, quel codice potrebbe essere peggio di scrivere semplicemente la funzione in C. O con un buon compilatore, potrebbe essere meglio. Difficile da dire per certo. D'altra parte, se un numero diverso di byte è variabile a seconda del messaggio che si sta inviando, si potrebbe finire con diverse versioni del codice, ciascuna ottimizzata per quel particolare utilizzo.

Answer 3

È possibile progettare una macro che eseguirà un calcolo CRC in fase di compilazione. Qualcosa come

 
// Choosing names to be short and hopefully unique. 
#define cZX((n),b,v) (((n) & (1 << b)) ? v : 0) 
#define cZY((n),b, w,x,y,z) (cZX((n),b,w)^CzX((n),b+1,x)^CzX((n),b+2,y)^cZX((n),b+3,z)) 
#define CRC(n) (cZY((n),0,cZ0,cZ1,cZ2,cZ3)^cZY((n),4,cZ4,cZ5,cZ6,cZ7)) 

dovrebbe probabilmente funzionare e sarà molto efficiente se (n) può essere valutato come costante in fase di compilazione; valuterà semplicemente una costante stessa. D'altra parte, se n è un'espressione, quell'espressione verrà ricalcolata otto volte. Anche se n è una variabile semplice, il codice risultante sarà probabilmente molto più grande del più veloce metodo di scrittura non basato sulla tabella e potrebbe essere più lento del modo più compatto di scriverlo.

BTW, una cosa che mi piacerebbe davvero vedere nello standard C e C++ sarebbe un modo per specificare gli overload che verrebbero utilizzati per le funzioni dichiarate in linea solo se determinati parametri potrebbero essere valutati come costanti in fase di compilazione.La semantica sarebbe tale che non ci sarebbe alcuna "garanzia" che qualsiasi sovraccarico di questo tipo sarebbe usato in ogni caso in cui un compilatore potrebbe essere in grado di determinare un valore, ma ci sarebbe una garanzia che (1) non si utilizzerebbe tale sovraccarico in ogni caso dove un parametro "compile-time-const" dovrebbe essere valutato al runtime, e (2) qualsiasi parametro che è considerato una costante in uno di questi overload sarà considerato una costante in tutte le funzioni invocate da esso. Esistono molti casi in cui una funzione può essere scritta per valutare una costante in fase di compilazione se il suo parametro è costante, ma dove la valutazione in fase di esecuzione sarebbe assolutamente orribile. Ad esempio:

 
#define bit_reverse_byte(n) ((((n) & 128)>>7)|(((n) & 64)>>5)|(((n) & 32)>>3)|(((n) & 16)>>1)| 
    (((n) & 8)<<1)|(((n) & 4)<<3)|(((n) & 2)<<5)|(((n) & 1)<<7)) 
#define bit_reverse_word(n) (bit_reverse_byte((n) >> 8) | (bit_reverse_byte(n) << 8)) 

Una semplice rappresentazione di una funzione bit inversa non-loop singolo byte in C sul PIC sarebbe di circa 17-19 istruzioni ciclo unico; una parola bit-reverse sarebbe 34, o circa 10 più una funzione byte-reverse (che verrebbe eseguita due volte). Il codice di assemblaggio ottimale sarebbe di circa 15 istruzioni a ciclo singolo per l'inversione dei byte o 17 per l'inversione delle parole. L'elaborazione di bit_reverse_byte(b) per una variabile di alcuni byte b richiederebbe molte dozzine di istruzioni per un totale di molte dozzine di cicli. Computing bit_reverse_word( w ) for some 16-bit word w` probabilmente richiederemo centinaia di istruzioni per eseguire centinaia o migliaia di cicli. Sarebbe davvero bello se si potesse contrassegnare una funzione da espandere in linea usando qualcosa come la formulazione di cui sopra nello scenario in cui si espanderebbe ad un totale di quattro istruzioni (fondamentalmente solo caricando il risultato) ma usare una chiamata di funzione in scenari in cui è in linea l'espansione sarebbe atroce.