Checksumme Berechnen C++

[Stefan (Gast)]

Hallo,

Zur Kommunikationsabsicherung zwischen zwei Steuergeräte muss ich die 
Botschafts-Checksumme berechnen und mit dem Signal Signal_CRC 
übertragen.

Dafür muss ich eine C++-Funktion schreiben was ich leider nicht kann.

Ich habe sowieso Verständnis-Probleme was die Checksumme-Berechnung 
angeht:-(. Warum verwendet man für die Berechnung bzw. für die 
Programmierung eine LUT (Lookup-Tabelle)?

Könnte jemand hier helfen?

Danke!

Gruß
Stefan

[Falk B. (falk)]

@ Stefan (Gast)

>Dafür muss ich eine C++-Funktion schreiben was ich leider nicht kann.

Das kann man lernen. Siehe CRC. Die Theorie ist nice to know, kann 
man aber erstmal überspringen. Entscheidend ist nur der Ablauf. Der wird 
hier recht gut erklärt.

http://www.ross.net/crc/download/crc_v3.txt

>Ich habe sowieso Verständnis-Probleme was die Checksumme-Berechnung
>angeht:-(. Warum verwendet man für die Berechnung bzw. für die
>Programmierung eine LUT (Lookup-Tabelle)?

Das kann man machen, muss aber nicht. Der Vorteil ist die deutlich 
höhere Geschwindigkeit.

[Planlos (Gast)]

Stefan schrieb:
> Warum verwendet man für die Berechnung bzw. für die
> Programmierung eine LUT (Lookup-Tabelle)?

z.B. Weil Steuergeräte oft "kleine" µCs enthalten, bei denen man gerne 
Speicherplatz und Rechenzeit spart.

Eine uint8_t->uint8_t LUT braucht 256 Bytes im ROM, kann in konstanter 
Zeit ausgelesen werden, und braucht kaum RAM/Stack.

[Konrad (Gast)]

Musst Du den CRC unbedingt selbst implementieren?

Gibts aeltere Projekte in der Organisation? Ab einer gewissen Groesse 
des Projekts findet sich meist irgendwo irgendeine CRC-Implementierung 
in sagen wir "crc16.h" und "crc16.c", mit dem Namen eines nicht mehr 
dort arbeitenden Kollegen im Header, und natuerlich nicht angegeben, 
welches CRC-Polynom, welcher Startwert, wieherum die Bits gefuettert 
werden und ob nachher noch etwas ge-XOR-t wird.

Ansonsten braucht man auch keine LUT, wenn man genug Zeit hat. LUT ist 
nur eine Optimierung. Ohne LUT muss man halt Bits einzeln herausshiften.

[Torsten R. (Firma: Torrox.de) (torstenrobitzki)]

Stefan schrieb:

> Dafür muss ich eine C++-Funktion schreiben was ich leider nicht kann.

Dann nimm doch eine, die jemand anderes implementiert hat. Z.b: 
http://www.boost.org/doc/libs/1_60_0/libs/crc/crc.html

[Der Andere (Gast)]

Stefan schrieb:
> Dafür muss ich eine C++-Funktion schreiben was ich leider nicht kann.

Warum "muss" jemand eine C++ Funktion schreiben, der das nicht kann?

Klingt nach Hausaufgabe und keinen Bock auf lernen.
Aber es gibt bestimmt ne triftige Ausrede dazu :-)

[CaptainAlbern (Gast)]

Die einfachste Methode, die ich kenne geht folgendermaßen. Ich hoffe der 
Pseudocode ist verständlich. Wichtig ist, dass ChkA und ChkB UINT8 sind 
und Überläufe nicht abgefangen werden:

UINT8 chkA=0;
UINT8 chkB=0;

for (idx=0...bufferlength-1) {
  chkA+=buffer[idx];
  chkB+=chkA;
}

Die hat auch einen Namen. Fällt mir gerade nicht ein. Wird z.B. im 
binären Protokoll von UBLOX-GPS-Empfängern benutzt.

[Daniel V. (danvet)]

Ich verwende als CRC meistens das hier (! ist kein C++ !)
http://www.ibrtses.com/embedded/shortmsgprotocol.html

[Falk B. (falk)]

@ CaptainAlbern (Gast)

>Die einfachste Methode, die ich kenne geht folgendermaßen. Ich hoffe der
>Pseudocode ist verständlich. Wichtig ist, dass ChkA und ChkB UINT8 sind
>und Überläufe nicht abgefangen werden:

Es geht hier nicht um ein primitivste PrüfSUMME sondern um einen ECHTEN 
CRC, aka Cyclic Redundancy Check.

[Jojo S. (Gast)]

'Checksumme' ist denglisch und könnte auf deutsch aber 'Prüfsumme' 
heissen.
Genauere Angaben wurden ja nicht gemacht, als Informatiker könnte man 
den TO jetzt noch weiter nach Hamming Distanz fragen, ob und wieviele 
Bitfehler korrigiert werden sollen...

[Peter D. (peda)]

Manche Compiler haben schon eine crc16.h, z.B. der AVR-GCC.
Einfach den C-Code kopieren.

Bei 1GBit/s könnte sich ein LUT schon lohnen.

[CaptainAlbern (Gast)]

Ich hab nochmal nachgeschlagen, was ich oben erwähnt habe, nennt sich 
Fletcher-Algorithmus:
https://en.wikipedia.org/wiki/Fletcher%27s_checksum

@Falk: Selbstverständlich taugt das nicht als ECHTER CRC. Das kann man 
unabhängig vom konkreten Einsatzzweck ruhig schon mal so sagen.