Newsgroup: it.comp.java
Titolo: Algoritmo CRC16 CCITT

CDO, devo inviare messaggi ad un dispositivo il cui protocollo richiede 
CRC16 (polinomio X^16 + X^12 + X^5 + 1). Gli esempi disponibili in rete 
non calcolano il valore atteso secondo gli esempi del manuale. Lo stesso 
manuale mi offre due spiegazioni dell'algoritmo, una descrittiva:
 
 
Il CRC viene diviso in due byte
 
Inizializzazione:
CRCLSB = 0xFF (byte meno significativo del CRC)
CRCMSB = 0xFF (byte piu' significativo del CRC)
 
 
Per ogni byte D del messaggio, calcolare:
X = D XOR CRCMSB
X = X XOR (X >> 4)
CRCMSB = CRCLSB XOR (X >> 3) XOR (X << 4)
CRCLSB = X XOR (X << 5)
 
 
Alla fine:
CRCLSB = CRCLSB XOR 0xFF
CRCMSB = CRCMSB XOR 0xFF
 
 
..ed una spiegazione con funzione C:
 
void calc_crc (unsigned chat data_byte)
{
   data_byte ^= crcmsb;
   data_byte ^= (data_byte / 16);
   crcmsb = crclsb ^ (data_byte / 8) ^ (data_byte * 16);
   crclsb = data_byte ^ (data_byte * 32);
}
 
 
 
La mia difficolta' e' di non riuscire a trascriverlo in java. Qualcuno 
gentile mi aiuta? :))
 
Questo il mio tentativo:
 
byte ms = 0xFF;
byte ls = 0xFF;
byte tmp;
 
for (byte b : bytes) 
{
  b ^= ms;
  b ^= (b >> 4);
  tmp = ls;
  tmp ^= (b >> 3);
  tmp ^= (b >> 4);
  ms = tmp;
  tmp = b;
  tmp ^= (b << 5);
  ls = tmp;
}
 
ms ^= 0xFF;
ls ^= 0xFF;	
 
NB: Ho dovuto usare la variabile tmp, perche' per ragioni che non 
capisco, Eclipse mi consente l'istruzione b^=ms ma non mi consente b = 
b^ms   
 
 
 
Il manuale indica che per un messaggio come il seguente, il crc e' C840
 
0D 0A 0D 0A 0D 0A 0D 0A 0D 0A 0D 0A 2D 2D 2D 2D 2D 2D 2D 2D 2D 2D 2D 2D 
2D 2D 0D 0A 11 44 41 54 45 20 30 38 2F 32 38 2F 38 39 20 0D 0A 54 49 4D 
45 20 30 39 3A 35 35 3A 31 33 20 0D 0A 49 44 20 31 32 33 34 36 30 20 20 
20 20 20 00 00 00 00 00 20 0D 0A 49 44 20 00 00 00 00 00 00 00 00 00 00 
00 00 00 00 00 00 20 0D 0A 43 41 53 53 2F 50 4F 53 20 30 30 31 31 2F 30 
35 20 20 20 0D 0A 11 30 43 57 42 43 20 20 20 20 30 2E 30 00 20 20 4C 0D 
0A 52 42 43 20 20 20 30 2E 30 30 00 20 52 4C 0D 0A 48 47 42 20 20 20 20 
30 2E 30 00 20 20 4C 0D 0A 48 43 54 20 20 20 20 30 2E 30 00 20 52 4C 0D 
0A 4D 43 56 20 20 20 20 20 2E 30 00 2A 52 4C 0D 0A 4D 43 48 20 20 2B 2B 
2B 2B 2B 00 20 20 20 0D 0A 4D 43 48 43 20 20 20 30 2E 30 00 20 52 4C 0D 
0A 52 44 57 20 20 20 20 30 2E 30 00 20 52 4C 0D
 

   tmp ^= (b >> 4);
 
Questa sicuro l'ho toppata.. 
Ritento con tmp1 e tmp2
 

 ha scritto:

Se vabbe, sto andando nel pallone. Era corretto tmp.. anche se non fa 
comunque quello che dovrebbe
 
 

 manuale mi offre due spiegazioni dell'algoritmo, una descrittiva:
 
gli esempio disponibili in rete danno tutti lo stesso risultato? perche'
potrebbe essere sbagliato il manuale.
 
In ogni caso questo (e' in C):
 
http://automationwiki.com/index.php?title=CRC-16-CCITT
 
 
usa il tuo polinomio e una tabella per velocizzare i calcoli
 
Qui ci sono delle implementazioni:
http://stackoverflow.com/questions/13209364/convert-c-crc16-to-java-crc1
 
6
 
la risposta "vistata" probabilmente e' la soluzione al tuo problema.
 
Inoltre puoi guardare qua:
http://jamod.sourceforge.net
 
 
dove c'e' implementato un CRC16 (ma non ricordo se CCITT e se ha il tuo
polinomio) che funziona, quindi puoi prendere spunto per far funzionare
il tuo.
 
Ciao Jack
-- 
Yoda of Borg am I! Assimilated shall you be! Futile resistance is, hmm?

 potrebbe essere sbagliato il manuale.
 
Si quei 2 algoritmi recuperati in rete (su CCITT non ce ne sono molti) 
determinano tutti lo stesso risultato, diverso da quello del manuale (che 
riporta 2 esempi, quindi non credo sia un errore). La questione credo sia 
dovuta al discorso unsigned, non gestito in java. Cosi' ho fatto un 
accrocchio davvero orrendo. Ho preso per buono l'algoritmo in C proposto 
dal manuale, cioe' questo: 
 
void calc_crc (unsigned chat data_byte)
{
   data_byte ^= crcmsb;
   data_byte ^= (data_byte / 16);
   crcmsb = crclsb ^ (data_byte / 8) ^ (data_byte * 16);
   crclsb = data_byte ^ (data_byte * 32);
}
 
 
e mi sono messo a giocare con le stringhe. Cioe' mi sono fatto le 
funzioni xor, shiftLeft, shiftRight, che prendono come parametri le 
stringhe in binario (00000001, 00000011, ..) 
 
Alla fine ho ottenuto il risultato del manuale, ma con un algoritmo che 
definirlo orrendo e' un complimento :)
 
 

 definirlo orrendo e' un complimento :)
 
e ma guarda come hanno gestito l'unsigned in jamod.
Inoltre, visto che immagino tu non abbia problemi di RAM, IMHO conviene
implementare i CRC usando le tabelle. L'algoritmo rimane piu' semplice
ma soprattutto _molto_ piu' veloce.



Ciao 
Sto implementando lo stesso protocollo (in C++) ed ho il medesimo problema con il CRC.
Potresti dirmi come hai risolto il problema ? 
 
Grazie
Vincenzo

 Potresti dirmi come hai risolto il problema ? 
 
In un modo molto grezzo che piu' grezzo non si puo'. 
Ho convertito e lavorato in stringhe di '1' e '0'. Quindi ho fatto le mie 
funzioni XOR, shiftRight e shiftLeft, ed applicato quello stesso 
algoritmo. 
 
 
 

 algoritmo.
 
Vuol dire che sono sbagliate le funzioni di libreria ?
Perchè hai dovuto lavorare sui bit ?
Il Tuo shift fa rientrare bit diversi rispetto alla libreria ?

 Il Tuo shift fa rientrare bit diversi rispetto alla libreria ?
 
Non penso siano sbagliate le funzioni base (parliamo di java), forse mi 
sfuggiva qualcosa che non mi permetteva di utilizzarle a dovere. Ricordo che 
avevo poco tempo, e dovevo trovare una (qualsiasi) soluzione. Come ho visto 
che quella descritta funzionava, l'ho lasciata. 
 


La classe BigInteger ha queste funzioni implementate.
