CRC16 von Maxim Frage

[Miss Understood (Gast)]

Hallo Leute,

ich wollte einen CRC-Generator programmieren, der möglichst schnell ist. 
Dazu gibt es natürlich viele Source-Codes.

Ich habe nun folgenden für das Polynom x^16 + x^15 + x^2 + 1 gefunden:

 
unsigned int calcCRC(unsigned int srcCRC, unsigned char testByte)
{
       int i;

       srcCRC ^= testByte;

       for (i = 0; i < 8; ++i)
       {
         if (srcCRC & 1)
           srcCRC = (srcCRC >> 1) ^ 0xA001;
         else
           srcCRC = (srcCRC >> 1);
       }
       return srcCRC;


  
}

//Aufruf in Main
void main ()
{
 unsigned int CRC;

 unsigned char byte1=0xAA;
 unsigned char byte2=0xAA;


 //Vorladewert
 CRC = 0xFFFF;//0x0000;

 CRC = calcCRC(myCRC, b1);

 CRC = calcCRC(myCRC, b2);
}

Dann bin ich noch auf die folgende Seite gestoßen:

http://www.lammertbies.nl/comm/info/crc-calculation.html?crc=00000003&method=hex


Je nachdem welchen Vorladewert ich eingebe, kommt entweder das Gleiche 
oder was anderes raus.
Meine Frage ist nun, welchen Vorladewert wird für eine CRC16 bei einem 
1-Wire-Produkt verwendet (z.B. EEPROM)?
Benutzt Maxim einen Wert von 0x0000 oder 0xFFFF?

Vielen Dank für eure Hilfe.

Grüße
M.U.

[Detlev Neumann (Gast)]

Hallo M.U.

aus meiner Erinnerung ist in den meisten Fällen 0xffff als startwert für 
die CRC Berechnung zu wählen. 0x0000 ist mir bisher noch nicht 
untergekommen. Aber vieleicht irre ich mich auch

Hoffe Dir geholfen zu haben

Gruß

Detlev

[Miss Understood (Gast)]

Hallo Detlev,

danke für die Antwort.

Ich werde es mal mit 0xFFFF testen. Vielleicht funktioniert es ja.
Wenn nicht, muss ich es nochmal mit 0x0000 ausprobieren.

Leider finde ich keine wirklich eindeutige Beschreibung von 
Dallas/Maxim, die den Startwert für die CRC16 beschreibt.


Grüße
M.U.

[eProfi (Gast)]

Der Startwert ist 0, aber das Ergebnis wird invertiert (1's complement):

steht im 1w-standard.pdf  auf S. 124

hier meine 1-Zeilen-Version:
Beitrag "Re: Ideen um CRC-Routine zu beschleunigen? (AVR, gcc)"

[Miss Understood (Gast)]

Guten Morgen eProfi,

vielen Dank für die Antwort.

Und deine Version scheint ja richtig schnell zu sein? Hast du das mal 
getestet?

Viele Grüße
M.U.

[Miss Understood (Gast)]

Hallo,

ich habe mal deinen Code ein wenig übersichtlicher geschrieben.

Funktionieren alle deine Beispiele oder ist nur das letzte (6.) die 
schnelle Version?

Grüße
M.U.

[Pro-Grammar (Gast)]

@eProfi:

Deine Version ist keine eine-Zeile-Version. Du hast doch nur alle 
Befehle in eine Zeile geschmissen - so würde ja jeder eine 
eine-Zeile-Version schreiben.

Aber du hast die Standardausführung der CRC16-Routine sehr gut 
zusammengefasst, soweit ich das auf die Schnelle beurteilen kann. Dafür 
ein großes Lob an dich!

Euer
Pro-Grammar

[eProfi (Gast)]

Danke,  hör ich gern.

Die Versionen funktionieren alle und sind äquivalent.

hier habe ich noch drei:
for(i=9;--i;c=c>>1^((c^d)&1?p:0),d>>=1);
for(i=9;--i;c=c/2^((c^d)&1?p:0),d/=2);
for(i=9;--i;d/=2)c=c/2^((c^d)&1?p:0);

Ich glaub, noch kürzer geht es nicht.

Der Vorteil ist, dass das Zero-Flag nach dem --i direkt ausgewertet 
werden kann, was einen Befehl (compare) einspart.
Nachteil ist, dass man wissen muss, dass die Routine nur 8 mal 
durchlaufen wird, trotzdem 9 dortsteht.
Evtl. könnte man i=8+1 schreiben. Aber ich mag es gern kurz.

Der Link zum o.g. 1w-standard (Book of iButton standards):
AN937, AN 937, APP937, Appnote937, Appnote 937
http://pdfserv.maxim-ic.com/en/an/AN937.pdf

[Miss Understood (Gast)]

Hi,

ich habe noch eine Frage zu deiner Auswertung mit der for-Schleife:


eProfi schrieb:
> for(i=9;--i;c=c>>1^((c^d)&1?p:0),d>>=1);
> for(i=9;--i;c=c/2^((c^d)&1?p:0),d/=2);



Wie habe ich die zu interpretieren?

Ich meine, klar: i=9 ist der Wert, der initialisiert wird.
Aber käme nicht an zweiter STelle die Bedingung, wie weit gezählt wird 
und an dritter Stelle die Anzahl, um die runtergezählt werden soll.
Aber irgendwie ist das bei dir vertauscht und du hast in der dritten 
Anweisung noch ein "," eingefügt - was hat das zu bedeuten?

Vielen Dank für deine grandiose Hilfe :-)

Grüße
M.U.

[Peter D. (peda)]

Miss Understood schrieb:
> Meine Frage ist nun, welchen Vorladewert wird für eine CRC16 bei einem
> 1-Wire-Produkt verwendet (z.B. EEPROM)?

1-Wire benutzt nur eine 8-Bit CRC.

Über den EEPROM erfolgt intern keine CRC. Du kannst also eine beliebige 
CRC und Vorladewert benutzen.


Peter

[Miss Understood (Gast)]

Peter Dannegger schrieb:
> Über den EEPROM erfolgt intern keine CRC. Du kannst also eine beliebige
> CRC und Vorladewert benutzen.

Aber z.B. in DS2431 ist in den Flow-Charts eine invertierte CRC16 
generiert worden, die dann übermittelt wird?
Kann ich die dann einfach weglassen?

[Hans M. (Firma: mayer) (oe1smc)]

hallo Miss Understood

> Wie habe ich die zu interpretieren?
> Aber käme nicht an zweiter STelle die Bedingung, wie weit gezählt wird

ja ist es ja auch.
solange i groesser null ist, wird es ausgefuehrt. zusaetzlich wird halt 
noch davor um 1 hinunter gezaehlt.
eine anweisung  if(i>0)  kann auch als   if(i)  geschrieben werden.
( gilt in diesem fall natuerlich nur fuer positive i's.

gruss
hans

--

[Peter D. (peda)]

Miss Understood schrieb:
> Aber z.B. in DS2431 ist in den Flow-Charts eine invertierte CRC16
> generiert worden, die dann übermittelt wird?

Stimmt, da ist ja noch ne CRC für die Datenübertragung.
Ich hab mal nen DS1994 benutzt, da gab es sowas nicht.


Miss Understood schrieb:
> Kann ich die dann einfach weglassen?

Glaube nicht.


Peter

[Miss Understood (Gast)]

Hans Mayer schrieb:
> ja ist es ja auch.
> solange i groesser null ist, wird es ausgefuehrt. zusaetzlich wird halt
> noch davor um 1 hinunter gezaehlt.
> eine anweisung  if(i>0)  kann auch als   if(i)  geschrieben werden.
> ( gilt in diesem fall natuerlich nur fuer positive i's.

Ok, das habe ich verstanden. Eigentlich auch logisch. Danke.

Aber bei folgendem Ausdruck

c=c>>1^((c^d)&1?p:0),d>>=1

weiß ich nicht was das Komma bedeutet.

Ich hätte den Befehl jetzt mal so übersetzt:
C= Wert, d>>=1

c>>1^((c^d)&1?p:0) <- das ergibt ja irgendeinen Wert. Was allerdings das 
",d>>=1" bedeutet kann ich nicht so richtig interpretieren.

Danke für eure Hilfe.

@Peter:
Dann werde ich mal die CRC wieder einbauen. Danke :-)

Gruß
M.U.

[eProfi (Gast)]

Ich gebe zu, das sind schon fortgeschrittenen Tricks.

> for(i=9;--i;

Er erwartet als zweiten Parameter einen Wert, der mit Null verglichen 
wird.
--i ist dann Null, wenn es vor dem Decrement 1 war.
In Asm schaut das so aus:
dec i     hier wird das Zero-Flag abhängig vom Ergebnis  Z oder NZ
beq ende  und hier ausgewertet

> c=c/2^((c^d)&1?p:0),d/=2);

Das ist der Kommaoperator. Er wirkt wie ein Strichpunkt, nur dass es 
wie eine Einheit aufgefasst wird, z.B. wo nur ein Ausdruck erlaubt ist.
wird z.B. auch so verwendet  uint8_t a,b,c,d;

Allerdings werden die Teilausdrücke von rechts nach links ausgewertet, 
also zuerst d/=2 (äquivalent zu d=d/2)  und dann c=c/2^((c^d)&1?p:0).

c wird halbiert (d.h. um eine Bitstelle nach rechts geschoben) und 
geXORt
mit p, wenn das Bit 0 von c^d gesetzt ist  oder
mit 0, also beibehalten, wenn das Bit 0 nicht gesetzt ist.

Wobei das ganze für mich ein Sport ist, es (natürlich auf Kosten der 
Lesbarkeit) möglichst kurz zu schreiben.

> eine anweisung  if(i>0)  kann auch als   if(i)
genauer gesagt: if(i!=0) ist das selbe wie if(i)