mikrocontroller.net

Forum: Mikrocontroller und Digitale Elektronik CRC8 / OneWire Frage


Autor: ARM-Fan (Gast)
Datum:

Bewertung
0 lesenswert
nicht 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?

Autor: Ssss Ssssss (sssssss)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hi!

Hier mal ein Stück Perlcode dass diese Tabelle berechnet:
#!/usr/bin/perl
#############################
# calc crc8 lookuptable:
# by simon  [[ avr <AT> auctionant.de ]]

$poly        = 0x18;  # => x^8 + x^5 + x^4 + x^0
$crc_initval = 0x00;

@crctable = ();

for ($i=0; $i<256; $i++){
        $data = $i;
        $crc  = $crc_initval;
        for($bitcnt = 8; $bitcnt>0; $bitcnt--){
                $fbit = ($crc ^ $data) & 0x01;
                if ($fbit == 1){
                        $crc = $crc ^ $poly;
                }

                $crc = ($crc>>1) & 0x7F;

                if ($fbit == 1){
                        $crc = $crc | 0x80;
                }
                $data = $data>>1;
        }
        #printf("crc[$i] = $crc\n");
        $crctable[$i] = $crc;
}

#print table as c code:
printf("\n\n");
printf("unsigned char crc8_lookuptable[256] = {");

for($i=0; $i<256; $i+=16){
        printf("\n");
        for($j=0; $j<16; $j++){
                printf(" 0x%02X,",$crctable[$i+$j]);
        }
}
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

Autor: ARM-Fan (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Na das war ja mal ne spontane Antwort!

Vielen DANK!

Autor: Profi (Gast)
Datum:

Bewertung
0 lesenswert
nicht 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).

Autor: Profi (Gast)
Datum:

Bewertung
0 lesenswert
nicht 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;
*/

Autor: Profi (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
eine ausführlich Beschreibung findet sich in
http://www.mikrocontroller.net/forum/read-1-190635...

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.

Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [avrasm]AVR-Assembler-Code[/avrasm]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.
Hinweis: der ursprüngliche Beitrag ist mehr als 6 Monate alt.
Bitte hier nur auf die ursprüngliche Frage antworten,
für neue Fragen einen neuen Beitrag erstellen.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.