CRC16 - CCITT

[Toni (Gast)]

Hallo,

mir ist bewusst, dass mal wieder eine Frage gestellt wird, warum das 
Ergebnis (m)einer CRC-Prüfung mit den üblichen CRC Online Auswertungen 
nicht übereinstimmt, aber es hilft nichts. Nach diversen verzweifelten 
Nächten ist die Grenze erreicht... Ich habe diverse Foren abgegrast. 
Jeder macht's irgendwie anders, dabei sind es "nur" ein paar 
Programmzeilen..., siehe unten.

Es geht um CRC16-CCITT, dessen Checksummenprüfung einfach nicht das 
richtige Ergebnis liefert.

Gibt man testweise die Zeichenfolge "0123" vor, so kommt als Ergebnis 
bei mir 0x1EAE heraus.
Laut https://www.lammertbies.nl/comm/info/crc-calculation.html kommt 
aber 0x3F7B heraus.


Hat jemand eine Idee, was ich falsch mache?

dim w as word
dim txt_5_st as string[5]
const crcblock as byte[100] = (48, 49, 50, 51) 'hier testweise "0123" als ASCII

sub function CRC16_CCITT(dim byref localcrcblock as byte[100], dim startbyte as byte, dim endbyte as word) as word
dim j, lsb as Byte
dim i, crc as Word 
crc = $FFFF                  'Anfangswert

For i = startbyte to endbyte
  crc = crc xor localcrcblock[i]
  For j = 0 to 7
     crc = crc >> 1
     lsb = crc and $01       'Take carry bit
     If lsb <> 0 Then
        crc = crc xor $1021  'Poly
     End If
  Next j
Next i

Result = crc                 'Rückgabe
End sub

main:
   Test = CRC16_CCITT(crcblock, 0, 3)
end.

[Frank (Gast)]

Steck mal nur 1 Byte rein.
So lässt sich das etwas leichter nachvollziehen.

[A. S. (Gast)]

Frank schrieb:
> Steck mal nur 1 Byte rein.

Eigentlich sollte man sogar mit 0 Byte anfangen, um Startwert und 
Endbehandlung zu prüfen.

Und dann bei 1 Byte zuerst mit 0 anfangen. Wenn das klappt, dann z.B. 
mit 0x01. Wenn das nicht klappt, dann probieren, ob mit 0x80 beim 
online-Checker das gleiche rauskommt wie mit 0x01 beim eigenen Code (den 
Wert halt "spiegeln".)

[Johnny B. (johnnyb)]

Das Problem ist, dass es da draussen in der Welt viele fehlerhafte 
Implementationen zur Berechnung des CRC16-CCITT gibt, welche auch so 
eingesetzt werden.
Willst Du nun mit einem Gerät kommunizieren, welches eine solche 
fehlerhafte Implementation einsetzt, musst Du natürlich auch eine 
fehlerhafte Implementation einsetzen, welche die selben Resultate 
liefert, so dass es dann zusammenpasst.
Es kommt also auf Deine Anwendung darauf an, wie Du nun vorgehen musst, 
also mit was genau Du kompatibel sein willst.

Hier noch ein paar Infos:
http://srecord.sourceforge.net/crc16-ccitt.html

[Michael K. (aemkai)]

Hallo,

du musst ggfs. ein abschließendes XOR sowie die Bitreihenfolge des 
Eingangs-/Ausgangswertes beachten.

Probier mal den folgenden Online-Rechner, da kann man es beliebig 
einstellen und sieht auch die notwendigen Einstellungen für diverse 
Vorgaben:
http://www.sunshine2k.de/coding/javascript/crc/crc_js.html

Damit findest du einfach heraus, ob es ein solcher Fehler ist oder etwas 
anderes.

Für CRC16-CCITT sollte aber beides "normal" sein.

Wichtig ist auch der Initialwert, i.d.R. 0x0000 oder 0xFFFF, im 
Allgemeinen aber beliebig.

P.S: 0x3F7B ist für CRC16-CCITT mit Initalwert 0xFFFF schonmal richtig.

[Detlef _. (detlef_a)]

Yo,

verzweifelte Nächte.

Beitrag "Yet another CRC32 Code"

Ist für 32 Bit, aber vllt. ähnlich.

Cheers
Detlef

[Michael K. (aemkai)]

Wo wandelst du eigentlich die ASCII-Werte in Zahlen um?

[Jörg W. (dl8dtl) (Moderator)]

Johnny B. schrieb:
> Das Problem ist, dass es da draussen in der Welt viele fehlerhafte
> Implementationen zur Berechnung des CRC16-CCITT gibt, welche auch so
> eingesetzt werden.

Das Hauptproblem ist nach meiner Erfahrung die Bitreihenfolge.

Kommunikationsprotokolle (wie CCITT) übertragen in der Regel Bit 0
zuerst.  Wenn man das aufschreibt, dann steht da ein Bitstrom

b0 b1 b2 b3 b4 b5 b6 b7 b8 b9 …

Das widerspricht allerdings unserer „natürlichen“ Leserichtung,
weshalb es nun auch Implementierungen gibt, die so arbeiten:

[pre]b7 b6 b5 b4 b3 b2 b1 b0 | b15 b14 b13 b12 b11 … [pre]

Beide Varianten benutzen dann formal das gleiche Polynom
x^16 + x^12 + x^5 + 1, aber einmal wird es als 0x8408 dargestellt,
ein anderes Mal als 0x1021.

Das Problem unterschiedlicher Startwerte wurde auch schon genannt.
Zuweilen vermeidet man einen Startwert von 0x0000 und nimmt lieber
0xFFFF, weil sich 0x0000 bei einem Datenstrom aufeinanderfolgender
Nullbytes danach nie verändert.  Bei Protokollen, die ohnehin als
erstes Octet nie eine 0 haben können, hat man das Problem jedoch
nicht und kann auch mit 0x0000 als Startwert beginnen.

Vernünftige Protokoll-Specs schreiben daher immer auch einen
Testvektor mit in die Spec.  Spätestens bei dem merkt man, ob man
sich mit der eigenen Implementierung vertan hat.

[Michael K. (aemkai)]

Jörg W. schrieb:
> Beide Varianten benutzen dann formal das gleiche Polynom
> x^16 + x^12 + x^5 + 1, aber einmal wird es als 0x8408 dargestellt,
> ein anderes Mal als 0x1021.
Das ist die erwähnte Bitreihenfolge des Eingangs-/Ausgangswertes.

Bei der von dir genannten Invertierung des Polynoms muss dann aber auch 
der Ausgangswert noch umgedreht werden und als Überlauf das LSB statt 
MSB geprüft werden (wenn ich nicht irre).

[Jörg W. (dl8dtl) (Moderator)]

Michael K. schrieb:
> as ist die erwähnte Bitreihenfolge des Eingangs-/Ausgangswertes.

Ja.

[Johnny B. (johnnyb)]

Ich kann nur nochmals empfehlen, die Infos von folgendem Link zu lesen, 
da ist sehr viel Wissen zur praktischen Anwendung drin, inkl. einer 
korrekt funktionierenden Implementation in C und einer weit 
verbreiteten, welche aber z.T. falsche Resultate liefert (unter falsch 
verstehe ich, nicht dem CCITT Standard entsprechend):
http://srecord.sourceforge.net/crc16-ccitt.html

Es sind auch Beispielstrings enthalten um eigene Implementationen zu 
testen/vergleichen.

[Sebastian K. (sek)]

Es wurde hier bereits einiges geschrieben, was ich teils voll und ganz 
bestätigen kann.
Die Hauptprobleme einer "falschen" CRC Berechnung liegen

- am Startwert...die einen Algorithmen starten mit 0x00000000, die 
anderen mit 0xFFFFFFFF und andere wieder mit einem ganz anderen Wert
- an der Byte und Bit Reihenfolge
- an der Ausgabe des Endwertes

Für ein STM32 Projekt habe ich kürzlich auch wieder CRC 
Berechnungsroutinen schreiben müssen. Und Anfangs auch noch versucht, 
meine Ergbnisse der Prüfsummen mit den Online Tools gegenzuchecken. Dies 
habe ich aber schnell wieder verworfen, da zwar die wenigsten Tools 
falsche Berechnungen anstellen, die Implementierung der drei oben 
genannten Punkte aber alles andere als einheitlich ist.

Am Ende habe ich das ganze für mich bzw. den STM32 passend gemacht. Und 
zwar habe ich meinen CRC Algorithmus in einer 32-Bit Version so 
implementiert, dass er die gleichen Ergebnisse wie die CRC-32 Einheit 
des STM32 liefert. Davon habe ich dann die übrigen CRC Funktionen mit 
den unterschiedlichen Generatorpolynomen abgeleitet.

[Toni (Gast)]

Hallo an alle,

es sind inzwischen einige Beiträge gekommen, danke!

Ich habe folgenden Test gemacht, siehe unten Tabelle.

Data     mein Ergebnis (hex/bin)    Poly    Ergebnis Soll (hex/bin)
  -     0xFFFF                     0x1021  0xFFFF (ok Frank, das klappt
                                                          schon mal ;-)
(0x00)  0x318 = %0000001100011000  0x1021  0xE1F0 = %1110000111110000
(0x00)  0xC1CB= %1100000111001011  0x8408  0xDE48 = %1101111001001000
(0x01)  0x318                      0x1021  0xF1D1 = %1111000111010001

Nach dem das Ergebnis bei Data= 0x00 und 0x01 identisch ist, ist klar 
dass mein Code Mist ist.
Lässt sich auch schnell erklären, da crc = crc xor localcrcblock[i] nur 
einmalig vor der For j-Schleife gesetzt wird
und sofort herausgeschoben wird crc = crc >> 1.

Es ist wohl wahr, dass im Netz viel Schrott abgelegt wird.

Ich probierte es nun mal mit diesem Code-schnipsel:  [Link] 
Beitrag "CRC-16 Prüfsumme (serielle Übertragung)" von  J.St.
Das sieht dann bei mir so aus:

crc = $FFFF    
For i = startbyte to endbyte
  For j = 0 to 7
     lsb = (crc xor localcrcblock[i]) and $01
     crc = crc >> 1
     If lsb = 1 Then
        crc = crc xor $1021  'Poly
     End If
     localcrcblock[i] = localcrcblock[i] >> 1
  Next j
Next i

Result = crc
End sub

Mit folgender Testreihe:
Data   mein Ergebnis (hex/bin)  Poly    Ergebnis Soll (hex/bin)
(0x00) 0x127B = %1001001111011  0x1021  0xE1F0 = %1110000111110000
(0x01) 0xFF                     0x1021  0xF1D1 = %1111000111010001
(0x80) 0x127B                   0x1021  0x7078 = %0111000001111000


Der Code scheint aber auch falsch zu sein, da das Ergebnis bei Data=0x00 
und 0x80 identisch ist, oder...?

Hat jemand evtl. eine todsicher funktionierende Implementierung? Die 
würde ich gern mal ausprobieren.


PS: @ Sebastian K. Wie schaffst du es bei deinem STM ein bestimmtes 
Polynom vorzugeben? Die CRC-Unit des STM32F4 als Bsp. scheint mit einem 
fest installiertem Poly belegt zu sein: 0x4C11DB7.

Toni

[A. S. (Gast)]

Nochmal zu den Online-Tools: Bevor man eines nutzt ist natürlich ein 
Original-Datenstrom mit >2 Byte (ungleich 0) zu besorgen und damit zu 
testen.

Erst wann das Tool mit den richtigen Einstellungen (Startwert, Polynom, 
Bit- und Byte-Reihenfolge, Endbehandlung) das gleiche Ergebnis liefert, 
kann man seinen eigenen Code dann damit testen (angefangen wie gesagt 
bei 0 Byte Daten).

[Jörg W. (dl8dtl) (Moderator)]

Toni schrieb:
> Hat jemand evtl. eine todsicher funktionierende Implementierung?

<util/crc16.h> in der avr-libc enthält eine Sammlung von diversen
Derivaten (auch 8 und 32 bit breite).  Die sind zwar dort in
Inline-Assembler implementiert, aber im Kommentar steht jeweils
C-(Pseudo-)Code dazu.  Den C-Code dafür habe ich (nach Ersatz von
lo8/hi8 durch reale C-Ausdrücke) auch schon mehrfach anderweitig
benutzt, einschließlich IEEE 802.15.4.

[Johnny B. (johnnyb)]

Toni schrieb:
> Hat jemand evtl. eine todsicher funktionierende Implementierung? Die
> würde ich gern mal ausprobieren.

Hatte ich ja oben schon zweimal verlinkt, aber Du scheinst ziemlich 
beratungsresistent zu sein.