Forum: Mikrocontroller und Digitale Elektronik CRC8 / OneWire Frage


von ARM-Fan (Gast)


Lesenswert?

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?

von Ssss S. (sssssss)


Lesenswert?

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

von ARM-Fan (Gast)


Lesenswert?

Na das war ja mal ne spontane Antwort!

Vielen DANK!

von Profi (Gast)


Lesenswert?

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).

von Profi (Gast)


Lesenswert?

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;
*/

von Profi (Gast)


Lesenswert?

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.

von Henrik H. (Firma: TU Chemnitz) (heha)


Angehängte Dateien:

Lesenswert?

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
von Peter D. (peda)


Lesenswert?

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)

von A. F. (chefdesigner)


Lesenswert?

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
Noch kein Account? Hier anmelden.