Hallo! Ich hätte da mal eine Frage: In der OneWire C-Bibliothek von Dallas/Maxim ist eine Tabelle zur CRC8 Berechnung abgelegt. Ich habe auch irgendwo ergoogeln können, dass dieser Tabelle das Polynom x^8 + x^5 + x^4 + 1 zu Grunde liegen soll. Sicher bin ich mir da jedoch nicht. Kann mir jemdand sagen, ob das stimmt. Und wenn ja... WIE kann ich mir genau diese Tabelle selbst (z.B. zur Laufzeit) berechnen? Hier mal der Anfang der 256 byte großen Tabelle: static uchar code dscrc_table[] = { 0, 94,188,226, 97, 63,221,131,194,156,126, 32,163,253, 31, 65, 157,195, 33,127,252,162, 64, 30, 95, 1,227,189, 62, 96,130,220, 35,125,159,193, 66, 28,254,160,225,191, 93, 3,128,222, 60, 98, .... snip Wie man leicht sieht, wäre es mit einfachem Einsetzen ( x = 0..255 ) nicht getan. Wer kann mir helfen?
Hi! Hier mal ein Stück Perlcode dass diese Tabelle berechnet:
1 | #!/usr/bin/perl
|
2 | #############################
|
3 | # calc crc8 lookuptable:
|
4 | # by simon [[ avr <AT> auctionant.de ]]
|
5 | |
6 | $poly = 0x18; # => x^8 + x^5 + x^4 + x^0 |
7 | $crc_initval = 0x00; |
8 | |
9 | @crctable = (); |
10 | |
11 | for ($i=0; $i<256; $i++){ |
12 | $data = $i; |
13 | $crc = $crc_initval; |
14 | for($bitcnt = 8; $bitcnt>0; $bitcnt--){ |
15 | $fbit = ($crc ^ $data) & 0x01; |
16 | if ($fbit == 1){ |
17 | $crc = $crc ^ $poly; |
18 | }
|
19 | |
20 | $crc = ($crc>>1) & 0x7F; |
21 | |
22 | if ($fbit == 1){ |
23 | $crc = $crc | 0x80; |
24 | }
|
25 | $data = $data>>1; |
26 | }
|
27 | #printf("crc[$i] = $crc\n");
|
28 | $crctable[$i] = $crc; |
29 | }
|
30 | |
31 | #print table as c code:
|
32 | printf("\n\n"); |
33 | printf("unsigned char crc8_lookuptable[256] = {"); |
34 | |
35 | for($i=0; $i<256; $i+=16){ |
36 | printf("\n"); |
37 | for($j=0; $j<16; $j++){ |
38 | printf(" 0x%02X,",$crctable[$i+$j]); |
39 | }
|
40 | }
|
41 | printf("\n};\n\n"); |
Aufruf: perl skriptname.pl Ausgabe: Array den man direkt in ein avr gcc file einbinden kann. Das Generatorpolynom kannst du beliebig ändern. Bye, Simon
das geht wie immer auch ein wenig kürzer: #define p 140 //0x008C ist EIN CRC8-GeneratorPolynom //(es gibt mehrere verschiedene) //es ist immer gleich dem 128. Tabelleneintrag unsigned int i; //muss 16bit sein, da sonst Endebedingung //(<256) schwieriger zu realisieren //(<=255 geht nicht mit 8 bit, da es nach //Überlauf 0 und damit <= 255 ist) unsigned char b,c,d,j; //temp.Bool Crc Data loopcnt2 void main(void){ for(i=0;i<256;i++){ c=0;d=i; //CRC immer vor Beginn löschen for(j=8;j;j--,b=c^d,c/=2,d/=2,b&1?c^=p:0); i&15?0:printf("\r\n");printf("%3u,",c); } } //40961 0xA001 ist EIN CRC16-Polynom (es gibt mehrere verschiedene) //aber dies ist das üblichste //für 16bit-Berechnung muss c unsigned int statt unsigned char sein //das Polynom für CRC32 muss ich noch finden (habe keine Beispiele) --------------------------- Druckt genau die Liste aus. Es lohnt sich mit der Liste nur, wenn es extrem schnell gehen muss. Der obere Code läßt sich sehr einfach in schnellen Asm-Code realisieren. Da habe ich ganz schön lange hinoptimiert. Bei meinen CodeBeispielen mache ich mir meist den Sport, es mit möglichst wenigen Buchstaben hinzubekommen. Ich weiß, es ist nicht sonderlich leserlich, aber es macht mir einfach Spaß. Es bleibt jedem überlassen, den Code "normal" hinzuschreiben (und ihn dabei besser zu verstehen).
Dazu gibt es einige gute AN von Dallas, z.B.: Application Note 27 Understanding and Using Cyclic Redundancy Checks with Dallas Semiconductor iButton TM Products http://www.maxim-ic.com/appnotes.cfm/appnote_number/27 Da bei einem Startwert von 0 und Daten von 0 wieder 0 rauskommt, nimmt man manchmal einen anderen Startwert für crc, z.B. 0xB001. Da in meinem Code die Reihenfolge der Berechnungen anders ist, muss die Zahl p (0x8c, repräsentiert das Polynom) einen anderen Wert haben als in Simons Code (, der im Prinzip das selbe macht). Das Prog eignet sich nicht nur zur Berechnung der Tabelle, sondern auch zum Berechnen der CRC (ohne Tabelle), dazu d=datenbyte setzen und crc nicht vor jedem Beginn löschen. Gerade als ich mit dem Prog fertig war, fand ich folgenden sehr ähnlichen Code in einem Zip-file: /* --- CRC routine used to compare agianst the CRC returned from the DS1615 Temperature Recorder */ unsigned int CRC,CRCb,DIN,CRCIN; int calc_crc(unsigned int data) { unsigned int i; for (i=0; i<8; i++) { CRCIN = (((CRC^data)&1) << 15); //<< 15 ist überflüssig data = data >> 1; CRC = CRC >> 1; if (CRCIN != 0) { //!= 0 ist überflüssig CRC = CRC ^ (0xA001); } CRCb = 0xFFFF - CRC; } return CRCb; } /* // clear CRC global variable CRC = 0; // retreive 32 bytes of page (calculating a running crc) for (i = 0; i < 32; i ++) { d = sgetchar(); // read byte from the DS1615 calc_crc(d); } c1 = (int)sgetchar(); // read word CRC from DS1615 c2 = (int)sgetchar(); // compare CRC returned from DS1615 with CRCb check = c2 * 0x0100 + c1; if (check == CRCb) good = 1; */
eine ausführlich Beschreibung findet sich in http://www.mikrocontroller.net/forum/read-1-190635.html#321383 Zum Überprüfen einer Übertragung füttert man den CRC-Algo nach den Daten mit der übertragenen CRC, dann muss ein fixes Ergebnis (oft 0 oder 0xb001) herauskommen.
Nun, ich habe mal untersucht, wie diese 256 Byte lange Tabelle zustande kommt. Zugrunde liegt das reflektierte Generatorpolynom, weil Rechtsschieben angesagt ist. Diese Routine für C++14 und höher wird in nichts anderes als 256 Byte PROGMEM-Daten übersetzt, es entsteht KEIN Assemblerkode. Vorausgesetzt, die Optimierung -Os oder -O1 ist angegeben. Mal ein Grund, nicht alles in Assembler zu schreiben sondern C++ produktiv einzusetzen.
:
Bearbeitet durch User
Henrik H. schrieb: > Mal ein Grund, nicht alles in Assembler zu schreiben sondern C++ > produktiv einzusetzen. Oder man bindet beim avr-gcc einfach die crc16.h ein:
1 | static __inline__ uint8_t |
2 | _crc_ibutton_update(uint8_t __crc, uint8_t __data) |
Ssss S. schrieb: > Das Generatorpolynom kannst du beliebig ändern. Es wäre aber zu berücksichtigen, dass es mehr oder weniger gute Codes gibt.
Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.