CRC durch uC berechnen lassen - Problem bei der Umsetzung

[CRC-hilfesuchender (Gast)]

Hi Leute!

Ich möchte gerne Daten, welche ich über ein 1m langes Kabel in einem 
EEPROM speichere, mit einer Prüfsummer versehen.

Die generelle Vorgehensweise zum erstellen der Prüfsumme habe ich 
verstanden und das klappt auch.

Hier mal als Beispiel:

Daten:   0x3E (0011 1110)
Polynom: 0xA7 (1010 0111) (x^7 + x^5 + x^2 + x + 1)

Prüfsummer erstellen:

001111100000000
  10100111|||||
  --------|||||
  010111110||||
   10100111||||
   --------||||
   00011001000|
      10100111|
      --------|
      011011110
       10100111
       --------
       01111001 Pruefsumme

Diese Prüfsumme speichere ich jetzt separat zum Datenbyte ab.

Beim Empfänger, bzw. beim Auslesen der Daten aus dem EEPROM lese ich 
dann die Daten und die zusätzlich für diese Daten gespeicherte Prüfsumme 
aus und mache das ganze erneut:

001111101111001
  10100111|||||
  --------|||||
  010111001||||
   10100111||||
   --------||||
   00011110100|
      10100111|
      --------|
      010100111
       10100111
       --------
              0 PASST!

Jetzt habe ich ein wenig Schwierigkeiten bei der Umsetzung des ganzen im 
uC. Pseudocode-mäßig mache ich doch folgendes beim Erstellen der CRC:

Schiebe die Daten solange nach links, bis die erste Stelle eine 1 ist.
XOR die Daten mit dem Generator-Polynom (die 1 muss hier auch ganz links 
stehen) und speichere diesen Wert an die Stelle, wo vorher die Daten 
standen. Widerhole solange, bis die erste Stelle der Daten gleich 0 ist.

Ist das soweit erstmal richtig, oder totaler Humbug?

Würde mich über Ratschläge sehr freuen. Habe auch schon im Forum gesucht 
und auch Sachen dazu gefunden, aber da ist das alles sehr knapp (was 
natürlich optimal ist), aber für mich nicht so ganz verständlich. Eine 
sehr kurze Variante von KHB habe ich gefunden. Ich verstehe sie nur 
nicht, daher würde ich auch erstmal mit einer längeren Variante 
zufrieden sein, die ich dann aber nachvollziehen kann.

Gruß

[... (Gast)]

Ein CRC sollte sich doch auch mit Gurgel finden lassen. Was war daran 
nicht brauchbar?

[CRC-hilfesuchender (Gast)]

... schrieb:
> Ein CRC sollte sich doch auch mit Gurgel finden lassen. Was war daran
> nicht brauchbar?

Ich sag ja nicht, dass nichts brauchbares dabei ist, habe mich übrigens 
vertan, meinte hier das von Peda:

Beitrag "Re: CRC-16 Prüfsumme (serielle Übertragung)"

Ich sagte nur, dass ich das nicht verstehe!

[Falk B. (falk)]

@  CRC-hilfesuchender (Gast)

>Schiebe die Daten solange nach links, bis die erste Stelle eine 1 ist.
>XOR die Daten mit dem Generator-Polynom

Ja.

> (die 1 muss hier auch ganz links
>stehen) und speichere diesen Wert an die Stelle, wo vorher die Daten
>standen. Widerhole solange, bis die erste Stelle der Daten gleich 0 ist.

Nö, solang wie die Daten sind.

>Würde mich über Ratschläge sehr freuen. Habe auch schon im Forum gesucht
>und auch Sachen dazu gefunden, aber da ist das alles sehr knapp (was
>natürlich optimal ist), aber für mich nicht so ganz verständlich.

Siehe CRC.

In dem bekannten CRC explaind ist es doch recht verständlich 
beschrieben.

>nicht, daher würde ich auch erstmal mit einer längeren Variante
>zufrieden sein, die ich dann aber nachvollziehen kann.

http://www.csm.ornl.gov/~dunigan/crc.html

[CRC-hilfesuchender (Gast)]

Ich habe das Beispiel mal ausprobiert, aber damit bekomme ich auf jeden 
Fall nicht das richtige heraus:

uint8_t generate_crc_8bit( uint8_t data )
{
  uint8_t checksum;
  uint8_t counter;

  checksum = data;
  for( counter = 8; counter; counter-- )
  {
    checksum = (checksum >> 1) ^ ((checksum & 1) ? CRC_POLYNOM : 0 );
  }
  
  return checksum;
}

[Falk B. (falk)]

@  CRC-hilfesuchender (Gast)

>Ich habe das Beispiel mal ausprobiert, aber damit bekomme ich auf jeden
>Fall nicht das richtige heraus:

Das Problem ist vielfälltig.
Wird deine CRC in der gleichen Richtung geschoben wie in dem Beispiel 
nach RECHTS?
CRC_Polynom richtig eingetragen?
Stimmt der Initialisierungswert der CRC?

MFG
Falk

[CRC-hilfesuchender (Gast)]

Falk Brunner schrieb:
> Das Problem ist vielfälltig.

Nee, hier stimmt grad garnix bei mir. Moment, ich muss nochmal 
drübergucken.

[Alexander V. (avogra)]

CRC-hilfesuchender schrieb:
> uint8_t generate_crc_8bit( uint8_t data )
> {
>   uint8_t checksum;
>   uint8_t counter;
>
>   checksum = data;

also ich kenn das eigentlich so, dass checksum auch als parameter 
übergeben wird. bei jedem neuen datenbyte wird der alte crc-wert 
übergeben, beim ersten datenbyte irgendein initialwert.

Gruß, Alex

[CRC-hilfesuchender (Gast)]

Alexander v. Grafenstein schrieb:
> bei jedem neuen datenbyte wird der alte crc-wert
> übergeben

Und wieso?

[CRC-hilfesuchender (Gast)]

Ich habe es jetzt so, aber da ist am Ende dann immer ein Shift zuviel:

uint8_t generate_crc_8bit( uint8_t data )
{
  uint8_t checksum = data;
  uint8_t counter;

  for( counter = 0; counter < 8; counter++ )
  {
    if( checksum & 0x80 )
    {
      checksum ^= CRC_POLYNOM;
    }
    
    checksum <<= 1;
  }

  return checksum;
}

Sonst isses richtig

[Falk B. (falk)]

@  CRC-hilfesuchender (Gast)

>> bei jedem neuen datenbyte wird der alte crc-wert
>> übergeben

>Und wieso?

Na weil die CRC über einen Block Daten zusammenhägend berechnet wird, 
das Ergebnis eines Bytes beeinflußt die Berechnung des nächsten.

[CRC-hilfesuchender (Gast)]

Falk Brunner schrieb:
> Na weil die CRC über einen Block Daten zusammenhägend berechnet wird

Aber wenn ich doch grad nur ein Byte habe

[CRC-hilfesuchender (Gast)]

OK, formuliere ich es anders: Ich habe nur einzelne Daten, keine Blöcke. 
Ich schreibe z.B. zum uint8 eine Prüfsumme, oder zu einem uint16, o. ä.

Einen Datneblock habe ich nicht.

[CRC-hilfesuchender (Gast)]

Ich sehe gerade, dass meine Variante da auch nur klappt, wenn das 
Polynom so aufgebaut ist, dass es am MSB des Bytes eine 1 hat.

Ach scheiße - ist bestimmt voll simpel, aber ich kriegs nicht gescheit 
hin.

[Karl H. (kbuchegg)]

CRC-hilfesuchender schrieb:
> Falk Brunner schrieb:
>> Na weil die CRC über einen Block Daten zusammenhägend berechnet wird
>
> Aber wenn ich doch grad nur ein Byte habe

Was willst du dann mit einer CRC?

CRC macht nur dann wirklich Sinn, wenn du viele Bytes absichern willst. 
Das ist ja gerade der Witz an der Sache: Viele Informationen (viele 
Bytes) so auf ein paar Bytes eindampfen, dass zufällige Fehler in der 
Übertragungen möglichst auffallen.

[Falk B. (falk)]

@  CRC-hilfesuchender (Gast)

>Ich habe es jetzt so, aber da ist am Ende dann immer ein Shift zuviel:

Nö, das passt. Aber das XOR passt nicht.

Eher so.

uint8_t generate_crc_8bit( uint8_t data )
{
  uint8_t checksum = data;
  uint8_t counter;

  for( counter = 0; counter < 8; counter++ )
  {
    if( checksum & 0x80 )
    {
       checksum <<= 1;
       checksum ^= CRC_POLYNOM;
    } else {
       checksum <<= 1;
    }   
  }

  return checksum;
}

Da man seltenst die Prüfsumme über einzelne Bytes berechnet, übergibt 
man der Funktion eher einen Pointer auf einen Datenblock und einen 
Bytezähler.

uint8_t generate_crc_block( uint8_t *data, unit8_t count )
{
  uint8_t checksum;
  uint8_t newdata;
  uint8_t bitmask;

  checksum = *data;
  data++;
  count--;

  For(; count>0; count--) {
    newdata = *data;
    data++;

    for( bitmask= 0x80; bitmask !=0; bitmask >>=1 )
    { 
      if( checksum & 0x80 )
      {
         checksum <<= 1;
         if (newdata & bitmask) checksum |=1;
         checksum ^= CRC_POLYNOM;
      } else {
         checksum <<= 1;
         if (newdata & bitmask) checksum |=1;
      }   
    }
  }

  return checksum;
}

MFG
Falk

[CRC-hilfesuchender (Gast)]

Falk Brunner schrieb:
> Eher so.
> uint8_t generate_crc_8bit( uint8_t data )
> {
>   uint8_t checksum = data;
>   uint8_t counter;
>
>   for( counter = 0; counter < 8; counter++ )
>   {
>     if( checksum & 0x80 )
>     {
>        checksum <<= 1;
>        checksum ^= CRC_POLYNOM;
>     } else {
>        checksum <<= 1;
>     }
>   }
>
>   return checksum;
> }

Da ist doch auch der Shift zuviel drin. Ich habe gerade gesehen, dass 
ich in meinem Quelltext das Shift rausgenommen hatte, um es 
auszuprobieren und dann natürlich genau den Text ohne das Shift hier 
rein gepostet habe - jedenfalls hatte ich den Shift auch drin. Wenn das 
Shift vor dem ^= steht, geht es nicht, danach isses richtig bis auf den 
zusätzlichen Shift.

Und was meinst du mit

Falk Brunner schrieb:
> Nö, das passt. Aber das XOR passt nicht.

[Falk B. (falk)]

@  CRC-hilfesuchender (Gast)

>Da ist doch auch der Shift zuviel drin.

Nein! Es wird IMMER geschoben, nur je nach 8. Bit XOR oder nicht 
gemacht.

"To perform the division perform the following:

   Load the register with zero bits.
   Augment the message by appending W zero bits to the end of it.
   While (more message bits)
      Begin
      Shift the register left by one bit, reading the next bit of the
         augmented message into register bit position 0.
      If (a 1 bit popped out of the register during step 3)
         Register = Register XOR Poly.
      End
   The register now contains the remainder.

(Note: In practice, the IF condition can be tested by testing the top
 bit of R before performing the shift.)"

> Ich habe gerade gesehen, dass
>ich in meinem Quelltext das Shift rausgenommen hatte, um es
>auszuprobieren und dann natürlich genau den Text ohne das Shift hier
>rein gepostet habe - jedenfalls hatte ich den Shift auch drin. Wenn das
>Shift vor dem ^= steht, geht es nicht, danach isses richtig bis auf den
>zusätzlichen Shift.

Dann ist villeicht deine andere CRC-Berechnung falsch.

>Und was meinst du mit
>> Nö, das passt. Aber das XOR passt nicht.

Dass VOR dem XOR ein Shift rein muss. Siehe oben.

[CRC-hilfesuchender (Gast)]

Falk Brunner schrieb:
> Nein! Es wird IMMER geschoben, nur je nach 8. Bit XOR oder nicht
> gemacht.

OK!

Falk Brunner schrieb:
> Dann ist villeicht deine andere CRC-Berechnung falsch.

Das kann natürlich auch sein, habe sie halt nach dem Schema gemacht, wie 
es auch im iNet steht. Meine manuelle Berechnung ist ja ganz oben im 
Eröffnungsthread. Ist die falsch?

[CRC-hilfesuchender (Gast)]

Karl Heinz Buchegger schrieb:
> CRC macht nur dann wirklich Sinn, wenn du viele Bytes absichern willst.
> Das ist ja gerade der Witz an der Sache: Viele Informationen (viele
> Bytes) so auf ein paar Bytes eindampfen, dass zufällige Fehler in der
> Übertragungen möglichst auffallen.

Das sehe ich ja auch ein. Ich habe halt nur einzelne 
Datenbytes/Worte/etc..., welche verändert und dann einzeln abgespeichert 
werden, nur halt in einem EEPROM, das auf einer extra Platine in einem 
anderen Gehäuse (steckbar) ist. Ich will vermeiden, dass hier 
Übertragungsfehler entstehen, bzw. diese zumindest erkennen können.

[Falk B. (falk)]

@  CRC-hilfesuchender (Gast)

>es auch im iNet steht. Meine manuelle Berechnung ist ja ganz oben im
>Eröffnungsthread. Ist die falsch?

Ja. Du musst das XOR eine Stelle tiefer ansetzen. Jedes Polynom hat noch 
ein implizites höchstwertiges Bit, das immer 1 ist aber direkt nie 
hingeschrieben wird. Dein Polynom 0xA7 ist in Wirklichkeit 0x1A7

001111100000000
  110100111||||
  ---------||||
  00101011100||
    110100111||
    ---------||
    0111110110|
     110100111|
     ---------|
     00101000100
       110100111
       ---------
       011100011 Pruefsumme

Und genau das kommt incl. Zwischenschritte auch bei dem C-Code raus.

MFG
Falk

[CRC-hilfesuchender (Gast)]

Jetzt komme durcheinander...nach diesem Rechner ist sie aber doch auch 
richtig, ohne das implizite Bit.

http://www.leischner.inf.fh-bonn-rhein-sieg.de/lehrmat/crc.htm

Wonach soll ich mich denn jetzt richten? So hatte ich es zumindest 
früher auch gelernt.

:-/

[CRC-hilfesuchender (Gast)]

Ich muss mich nochmal melden :-\ Ich bin jetzt wirklich ratlos. Wieso 
gehen die Berechnungen für die CRC denn so auseinander?

Kann da evtl. nochmal einer drüber gucken?

@Falk: Vielen Dank für deine Mühe. Wenn das Ergebnis mit diesem 
impliziten Bit hinhaut nach dem C-Code, dann ist das ja spitze, aber 
warum wird das anders gerechnet, als von Hand?

[Falk B. (falk)]

@  CRC-hilfesuchender (Gast)

>Ich muss mich nochmal melden :-\ Ich bin jetzt wirklich ratlos. Wieso
>gehen die Berechnungen für die CRC denn so auseinander?

Erstmal ist die Seite oben falsch, weil bei einer 8 Bit CRC auch acht 
Bit an die Daten angehängt werden müssen und nicht sieben.

Meiner Meinung ist die Berechung auf der Website falsch, weil eben das 
XOR eine Bit zu früh gemacht wird. Das implizite gesetzte Bit der CRC 
fehlt dort.

http://smbus.org/faq/crc8Applet.htm

Wenn man es mit dem Polynom 0x07 rechnet, stimmt es mit meiner Funktion 
überein.

http://www.lammertbies.nl/comm/software/index.html

Hier wird es auch so gemacht, erst schieben, dann XOR.

http://www.zorc.breitbandkatze.de/crc.html

Hier stimmt was nicht, ich kommen nicht auf die gleichen Zahlen.

http://ghsi.de/CRC/index.php?Polynom=1010+0111&Message=3E

Hier sind auch massive Fehler drin, nicht mal das Polynom wird korrekt 
dargestellt!

Ergo. Man darf nicht alles glauben, was im Internet steht ;-)