CRC über Datenstrom mit variabler Länge

[Davos R. (richmand)]

Hallo.

Ich bin dabei eine CAN Netzwerk aufzubauen und muss mir dazu Gedanken um 
die Einteilung der Nutzdaten machen. Da es sich um ein 
sicherheitsrelevantes System handelt, mus zusätzlich zu der schon 
bestehenden eine weitere CRC-16 implementiert werden, deren checksum auf 
die letzten beiden Datenbytes geschrieben werden soll. Ich möchte die 
CRC gerne über den Identifier und die Nutzdaten bilden, wobei deren 
Länge aber variabel sein können.

Ich muss gestehen, dass ich nicht allzuviel Ahnung von CRC habe und 
komme mit meinem Wissen aus Wikipedia und einigen Foreneinträgen hier 
nicht richtig weiter.

Ich habe mir schon einigt C-Codes zum generieren einer CRC angeschaut, 
allerding wird da die CRC jedesmal nur über ein Byte gebildet und ich 
benötige mindestens 5 oder 6. Außerdem möchte ich es gerne gegen 0 
prüfen, was bedeutet, dass ich bei einer CRC-16 nochmal 2 Byte Nullen 
anhängen muss.

Außerdem verstehe ich auch nicht ganz, wann ich welchen Wert wie 
vorinitialisiern muss (0x00 oder 0xFFFF)?

Wär cool wenn mir da jemand helfen könnte.

MfG

[MaWin (Gast)]

> Ich muss gestehen, dass ich nicht allzuviel Ahnung von CRC habe

So isses wohl.

Eine CRC kann problemlos incrementell byte für byte arbeiten und liefert 
somit für jede Datenpaket-Länge immer ein Ergebnis.

Und du könntest auch statt der 16 bit CRC einfach 2 Bytes ans Ende des 
Datenstroms schreiben, die dann, am Empfänger CRC-aufsummiert wie die 
anderen Bytes, 0 ergeben, allerdings erfordert die Berechnung dieser 
Bytes eine andere Formel (schnell per Tabelle).

> wird da die CRC jedesmal nur über ein Byte gebildet und ich
> benötige mindestens 5 oder 6

Dann machst du die CRC Rechnung eben 5 oder 6 mal, du solltest gelernt 
haben, was eine Schleife ist. Und jedesmal crcvalue=CRC(crcvalue,byte[i)

> Außerdem verstehe ich auch nicht ganz, wann ich welchen Wert wie
> vorinitialisiern muss (0x00 oder 0xFFFF)?

Es ist egal (es muss nur immer derselbe Wert sein), weil CRC mit einem 
vorherigen Teilergebnis weiterrechnen kann, also mit jedem Startwert 
klarkommt. Manche CRC-Algorithmen mögen nur keine 0.

[Peter D. (peda)]

http://www.maxim-ic.com/appnotes.cfm/an_pk/27


Peter

[Thomas P. (tpircher)]

Davos Rit schrieb:
> Außerdem verstehe ich auch nicht ganz, wann ich welchen Wert wie
> vorinitialisiern muss (0x00 oder 0xFFFF)?

Das wird vom jeweiligen CRC-Modell festgelegt. Siehe 
http://www.tty1.net/pycrc/crc-models_en.html oder 
http://homepages.tesco.net/rainstorm/crc-catalogue.htm fuer eine Liste 
von CRC Parametern.

Der CRC Aufruf sieht dann ungefaehr so aus:

crc = CRC_INIT;    // oft auch XOR_IN genannt.
for(int i = 0; i < data_len; i++) {
    crc = crc_update(crc, data[i]);
}
crc = crc ^ XOR_OUT;

> Außerdem möchte ich es gerne gegen 0
> prüfen, was bedeutet, dass ich bei einer CRC-16 nochmal 2 Byte Nullen
> anhängen muss.

Ich denke das hast du falsch verstanden. Zum Ueberpruefen eines CRCs 
hast du 2 Moeglichkeiten:

1) Berechnung des CRCs ueber den Daten und Vergleich des berechneten 
CCRs mit dem empfangenen CRC.

2) Berechnung des CRCs ueber den Daten UND dem empfangenen CRC. Wenn der 
berechnete CRC verschieden von null ist, dann liegt ein Fehler vor.

HTH
Thomas


EDIT:
Vielleicht habe auch ich das mit den 2 bytes Nullen falsch verstanden. 
Bei der einfachsten Variante des CRCs, dem bit-by-bit Algorithmus, musst 
du nach der Schleife (vor dem XOR_OUT) noch einmal 16 Bits Nullen (bei 
einem 16-bit CRC) nachschieben.
Dieser zusaetzliche Schritt faellt bei den schnelleren Varianten 
(table-driven und bit-by-bit-fast) weg.

[Davos R. (richmand)]

Hi. Also vielen Dank erstmal für die Antworten. Wenn ich das richtig 
verstanden habe, bedeutet das also, ich berechne die CRCs der einzelnen 
Bytes quasi separat.

crc = CRC_INIT;    // oft auch XOR_IN genannt.
for(int i = 0; i < data_len; i++) {
    crc = crc_update(crc, data[i]);
}
crc = crc ^ XOR_OUT;

crc_update berecnet jedesmal eine neue CRC über das jeweilige Byte von 
data. Für crc_update könnte ich also folgendes schreiben:

uint16_t crc_update(uint16_t crc, uint8_t data[])
{
  uint8_t i;
  for(i=0;i<8;i++)
  {
    if((crc ^ c) & 1) { crc=(crc>>1)^mask; }
    else crc>>=1;
    c>>=1;
  }
  return (crc);
}

Richtig? Was macht aber dann XOR_OUT?

Irgendwie check ich's glaub ich noch nicht 100%ig!

[Thomas P. (tpircher)]

Davos Rit schrieb:
> ich berechne die CRCs der einzelnen Bytes quasi separat.

Ja. Wenn du dir deinen Algorithmus ansiehst, dann siehst du dass du den 
CRC in einem Durchlauf oder in mehreren Happen berechnen kannst.

Wenn du nur ein Byte uebergibst, brauchst du data nicht als Array 
deklarieren:

 uint16_t crc_update(uint16_t crc, uint8_t data)

> Was macht aber dann XOR_OUT?

Wenn XOR_OUT gleich 0x00 ist, dann macht das gar nichts. Wenn es 0xFFFF 
ist, dann 'flippt' es alle Bits: ein '0'-bit wird zu einem '1' 
gewandelt, und aus einem '1' wird ein '0'. Warum das so gemacht wird, 
kann ich dir nicht sagen.

[Davos R. (richmand)]

Also ich habe jetzt folgendes gemacht:

uint16_t crc_update(uint16_t crc, uint8_t c, uint16_t mask)
{
  uint8_t i;
  for(i=0;i<8;i++)
  {
    if((crc ^ c) & 1)
    { 
      crc = (uint16_t)((crc>>1) ^ mask); 
    }
    else
    {
      crc>>=1;
    }
    c>>=1;
  }
  return (crc);
}

int main()
{

...
  uint32_t data_len = 5;
  uint16_t crcmask = 0xC599;
  uint8_t data[5] = {0xFF, 0xAA, 0xFF, 0x00, 0x00};
 ...
  for(i = 0; i < data_len; i++) 
  {
     crc = crc_update(crc, data[i], crcmask);
  }
 ...
}

Soweit so gut erstmal, das berechnet mir auch einen Wert (ob richtig 
oder nicht ist schwer zu sagen), wenn ich aber die Gegenprobe mache und 
den berechneten Wert in die beiden mit '0x00' initialisierten Felder des 
Arrays einsetze, kommt nicht der erwartete Wert 0 raus. Irgendwo ist 
wohl immernoch der Wurm drin!?

[Karl H. (kbuchegg)]

Davos Rit schrieb:

> Soweit so gut erstmal, das berechnet mir auch einen Wert (ob richtig
> oder nicht ist schwer zu sagen), wenn ich aber die Gegenprobe mache und
> den berechneten Wert in die beiden mit '0x00' initialisierten Felder des
> Arrays einsetze, kommt nicht der erwartete Wert 0 raus. Irgendwo ist
> wohl immernoch der Wurm drin!?

Natürlich nicht.
Die letzte CRC kommt hinten an das Array drann! Du musst dann eine CRC 
über 7 Bytes berechnen: Deine 5 alten Datenbytes + die 2 neuen CRC 
Bytes.

[Davos R. (richmand)]

Das funktioniert leider auch nicht, wenn ich zunächst 3 Bytes nehme und 
dann den vermeintlichen CRC Wert anhänge (5 Bytes) und es mit dem selben 
Funktionsaufruf (und data_len 5 statt 3) laufen lasse, kommt auch 
irgendetwas raus, aber nicht 0.

Man ist das deprimierend... :-(

[Karl H. (kbuchegg)]

Ich habe es mit deinem Programm ausprobiert.
Deine 5 Bytes durch die CRC Berechnung gejagt.
Dann die CRC angehängt (LowByte, HighByte)
und nochmal durch die CRC Berechnung.
Das Ergebnis war 0.

> Man ist das deprimierend... :-(
Das liegt aber nicht am CRC :-)

[Thomas P. (tpircher)]

Prinzipiell machst du das richtig. Und bei Karl Heinz funktioniert das. 
Wahrscheinlich ist es nur eine Kleinigkeit wie die Endianness des CRC 
Wertes, wenn du ihn an die Daten anhaengst.

Poste doch einfach einmal ein ein kleines vollstaendiges Programm, das 
den Fehler enthaelt, ansonsten werden wir dir nicht wirklich 
weiterhelfen koennen.

[Davos R. (richmand)]

Oh man, es lag tatsächlich nur am Vertauschen des High- und des 
Low-Bytes. Ich hab immer zuerst das Highbyte angehängt.

Jetzt funktioniert es auch bei mir! :-)

Vielen vielen Dank nochmal an alle, das war mir eine sehr sehr große 
Hilfe!!!

MfG