Forum: Mikrocontroller und Digitale Elektronik CRC über Blöcke in umgekehrter Reihenfolge


Announcement: there is an English version of this forum on EmbDev.net. Posts you create there will be displayed on Mikrocontroller.net and EmbDev.net.
von Torsten R. (Firma: Torrox.de) (torstenrobitzki)


Lesenswert?

Hallo,
ich habe folgende, CRC32 Funktion:
1
uint32_t checksum32( const uint8_t* data, size_t size, uint32_t crc )
2
{
3
    crc = ~crc;
4
5
    for ( ; size; --size, ++data )
6
        crc = (crc >> 8) ^ crc_table[ ( crc ^ *data ) & 0xFF ];
7
8
    return ~crc;
9
}

`crc_table` wird einmalig initialisiert (mit polynomial 0xEDB88320).

Die Funktion berechnet also eine CRC über einen Block mit einem 
gegebenem Ausgangswert. Um die CRC über mehrere Blöcke zu rechnen, kann 
man die Funktion mehrfach aufrufen:
1
uint32_t crc = 0;
2
crc = checksum32(block1, block1_length, crc);
3
crc = checksum32(block2, block2_length, crc);

So weit, so gut und normal. Jetzt habe ich das Problem, dass ich die CRC 
gerne in umgekehrter Reihenfolge berechnen würde, dabei aber gerne auf 
das selbe Ergebnis kommen würde:
1
uint32_t crc2 = 0;
2
crc2 = checksum32_2(block2, block2_length, crc2);
3
crc2 = checksum32_2(block1, block1_length, crc2);
4
5
assert(crc2 == crc);

Ist "so etwas" mit vertretbarem Aufwand möglich? (wie müsste 
checksum32_2() aussehen?)

schöne Grüße
Torsten

von Falk B. (falk)


Lesenswert?

Torsten R. schrieb:
> So weit, so gut und normal. Jetzt habe ich das Problem, dass ich die CRC
> gerne in umgekehrter Reihenfolge berechnen würde, dabei aber gerne auf
> das selbe Ergebnis kommen würde:

Das geht prinzipiell nicht. Warum meinst du, das tun zu müssen?

von Torsten R. (Firma: Torrox.de) (torstenrobitzki)


Lesenswert?

Falk B. schrieb:

> Das geht prinzipiell nicht. Warum meinst du, das tun zu müssen?

Das ist nur ein Beispiel. In der Realität habe ich im ersten Block die 
Länge der restlichen Blöcke. Die Ermittlung der Länge der restlichen 
Blöcke ist aber unter Umständen nicht trivial.

von Falk B. (falk)


Lesenswert?

Torsten R. schrieb:
> Das ist nur ein Beispiel. In der Realität habe ich im ersten Block die
> Länge der restlichen Blöcke. Die Ermittlung der Länge der restlichen
> Blöcke ist aber unter Umständen nicht trivial.

Kann es sein, daß du das Prinzip von CRC nicht verstanden hast? Eine 
CRC berechnet den Divisionsrest einer Polynomdivision. Da kann man nicht 
einfach die Datenblöcke in der Reihenfolge vertauschen! Das 
Kommutativgesetzt gilt explizit NICHT! Ein einzelnes, abweichendes Bit 
im Datenstrom ergibt eine vollkommen andere CRC! Das ist der Witz an 
einer CRC! Es ist KEINE einfache Prüfsumme, bei der einfach addiert oder 
XOR (Parität) verknüpft wird!

von Torsten R. (Firma: Torrox.de) (torstenrobitzki)


Lesenswert?

Falk B. schrieb:

> Kann es sein, daß du das Prinzip von CRC nicht verstanden hast?

Stimmt, offensichtlich habe ich CRC nicht bis in's Detail verstanden. 
Sonst würde ich ja nicht fragen. Das war doch aber der Sinn und Zweck so 
eines Forums, oder?

> Eine
> CRC berechnet den Divisionsrest einer Polynomdivision. Da kann man nicht
> einfach die Datenblöcke in der Reihenfolge vertauschen! Das
> Kommutativgesetzt gilt explizit NICHT!

Stimmt, für die Division gilt das Kommutativgesetz auch nicht, aber das 
bedeutet ja nicht, dass folgendes z.B. nicht mehr gilt:

Danke für Deine Antwort.

von MaWin O. (mawin_original)


Lesenswert?

Torsten R. schrieb:
> crc=a/b

Nein, falsch. Polynomdivisionsrest.

von Falk B. (falk)


Lesenswert?

Torsten R. schrieb:
> Stimmt, offensichtlich habe ich CRC nicht bis in's Detail verstanden.
> Sonst würde ich ja nicht fragen. Das war doch aber der Sinn und Zweck so
> eines Forums, oder?

Natürlich. Kein Problem.

Aber es bleibt die Frage offen, warum du die CRC mit einzelnen blöcken 
in unterschiedlicher Reihenfolge machen willst.

von Hans H. (hanshein)


Lesenswert?

>Ist "so etwas" mit vertretbarem Aufwand möglich? (wie müsste
>checksum32_2() aussehen?)

Jetzt nicht ausprobiert, aber die Linearitaet der CRC wird helfen:

crc(a⊕b) = crc(a)⊕crc(b)

Jetzt ist natuerlich wegen der Polynomrestdivision a und b jeweils
die "Bitlaenge" des kompletten Blocks c.

Deinen kompletten Block c koennen wir aber mal so auffassen, wenn wir
oBdA mal einen Block mit A,B,...H ("Bytes") so hinschreiben:

c = (A,B,C,D,E,F,G,H) "Komplettblock" über den die CRC zu berechnen ist
A,B,C,D erster Einzelblock
E,F,G,H zweiter Einzelblock

Um die obige Linearitaet auszunutzen machen wir also (0=Nullbyte):
a = (A,B,C,D,0,0,0,0)   und
b = (0,0,0,0,E,F,G,H)
( c = a ⊕ b )

crc(b) ist trivial zu berechnen, entweder ist bei einem
CRC Startwert von 0 der Startwert ebenso 0
(Null dividiert durch irgendwas = 0 Rest 0 (*)) , oder laesst es lässt
sich einfach durch partielle Evaluation der neue "Reststartwert"
berechnen (aka crc(0,0,0,0)).

(   (*) das Polynom sei <> 0   )

crc(a) waere dann via Programm mit Nullen aufzufuellen... Ich nehme
allerdings an, dass die Teilbloecke nicht unbedingt 4 Bytes gross
sind und es daher vom Zeitbedarf schon was kostet... :-)
Man kann da mit einem symbolischen Math-Solver seiner Wahl
rangehen und dafür sicher eine neue algorithmische Loesung finden.
Das kann ich allerdings nicht ex nunc aus der Hüfte schiessen,
da muesste eine sinnvolle mir-einsichtige Anwendung ("warum
macht man sowas?") und von daher motivierte Zeitressourcen
schon bereitstehen.

Also: Warum koennte diese Vorgehensweise ein
"interessantes Problem" sein?
Wie gross sind die Bloecke und Startwerte.
Was ist das fuer ein Polynom?

: Bearbeitet durch User
von Torsten R. (Firma: Torrox.de) (torstenrobitzki)


Lesenswert?

Hans H. schrieb:

> Also: Warum koennte diese Vorgehensweise ein
> "interessantes Problem" sein?

Gg. ist ein Protokoll zwischen einem Bootloader und einem dazu gehörigem 
Client. Beide, Bootloader und Client berechnen CRC über Länge der 
Firmware, Version der Firmware und über die Firmware. Client sendet CRC 
an Bootloader, nach dem die Firmware übertragen wurde. Wenn der 
Bootloader die gleiche CRC berechnet hat, wie der Client, wird die 
Übertragung als fehlerfrei angenommen.

Jetzt stellt es sich heraus, dass für den Client Situationen entstehen 
können, bei der die Länge der Firmware nicht trivial ermittelbar ist 
(z.B. wenn die Firmware in kleinen Stücken gelesen / übertragen wird).

Eigentlich ist die Länge der Firmware schon redundant und unnötig in der 
CRC. Das Weglassen der Länge in der CRC ist aber eine Änderung im 
Protokoll zwischen Client und Bootloader. Daher habe ich erst einmal 
untersucht, ob ich die ursprüngliche CRC Berechnung bei behalten kann, 
ohne das Protokoll ändern zu müssen.

Mit den hier gewonnenen Informationen (Danke an Falk) habe ich mich 
jetzt schon dafür entschieden, dass Protokoll zu ändern.

> Wie gross sind die Bloecke und Startwerte.

Startwert für den ersten Block ist 0, Länge des ersten Blocks ist 64 
bit, Länge des 2. Blocks ist variable (im Bereich mehrerer Kilobyte). 
Startwert des 2. Blocks, ist die CRC des ersten Blocks.

> Was ist das fuer ein Polynom?

0xEDB88320

von Peter D. (peda)


Lesenswert?

Torsten R. schrieb:
> Client sendet CRC
> an Bootloader, nach dem die Firmware übertragen wurde.

Nun, dann ist die Sache doch ganz einfach. Der Bootloader merkt sich die 
höchste Adresse, für die er Daten empfangen hat und das ist das Ende für 
die CRC-Berechnung.
Werden die Daten immer nur in aufsteigender Folge übertragen, dann kann 
er die CRC on the fly berechnen und muß nicht erst auf das CRC-Kommando 
warten.

Torsten R. schrieb:
> Jetzt stellt es sich heraus, dass für den Client Situationen entstehen
> können, bei der die Länge der Firmware nicht trivial ermittelbar ist

Oft ist doch der Client ein System, was genug RAM für das komplette 
Flashabbild hat, z.B. ein Programmer. Der liest dann erstmal alle 
Records des Hex-Files in den RAM und hat danach die Endadresse. Die kann 
er dann vorne im RAM eintragen. Die Endadresse kann schon wichtig sein, 
wenn z.B. der Bootloader zyklisch die Integrität des Flashinhalts prüfen 
soll.

von Torsten R. (Firma: Torrox.de) (torstenrobitzki)


Lesenswert?

Peter D. schrieb:
> Torsten R. schrieb:
> Nun, dann ist die Sache doch ganz einfach. Der Bootloader merkt sich die
> höchste Adresse, für die er Daten empfangen hat und das ist das Ende für
> die CRC-Berechnung.

Für den Bootloader ist das einfach, ja.

> Oft ist doch der Client ein System, was genug RAM für das komplette
> Flashabbild hat, z.B. ein Programmer.

Genau, weil das ist der "Regel" so ist, ist mir das Problem leider auch 
erst später aufgefallen. Ich habe aber jetzt einige Kunden, die wollen 
z.B. eine Hex-Datei zeilenweise auslesen oder bekommen die Hex-Datei 
selbst über Bluetooth.

> Die Endadresse kann schon wichtig sein,
> wenn z.B. der Bootloader zyklisch die Integrität des Flashinhalts prüfen
> soll.

Ja, die ist auch wichtig. Die wird auch nach wie vor im Client 
ermittelt, allerdings erst nach der Übertragung der Firmware.

von Purzel H. (hacky)


Lesenswert?

Die CRC gehoert natuerlich zu jedem einzelnen uebertrageen Datenblock. 
zB uebertraegt man 60 Bytes am Stueck. Und jeder Datenblock in in einem 
Protokol drin, mit einem CRC.

: Bearbeitet durch User
von Hans H. (hanshein)


Lesenswert?

>> Was ist das fuer ein Polynom?
>>
>0xEDB88320

(== 11101101101110001000001100100000 1, wobei die letzte 1 x^32
denotiert)

CRC Polynome haben immmer eine "... +1" am Ende (X^0 = 1).
Deine Darstellung ist daher sicher "falsch rum" ;-)
Die kanonische Darstellung, wie Du es in der Schule
gelernt hast, ziehen viele vor.
Du hast sicher nie "5 + 4x + x^2" geschrieben, sondern
x^2 + 4x + 5 .

Obiges ergibt dann:
x^32 + x^26 + x^23 + x^22 + x^16 + x^12 + x^11 + x^10 +
x^8 + x^7 + x^5 + x^4 + x^2 + x + 1

Was just dem Ethernet-Polynom in IEEE802.3 gleich ist.
Benutzt Du hier Ethernet auf Layer2/LinkLayer/"Verbinungsebene"?


>Startwert für den ersten Block ist 0, Länge des ersten Blocks ist
>64 bit, Länge des 2. Blocks ist variable (im Bereich mehrerer Kilobyte).

blk1=64Bit Block=(A,B,C,D,E,F,G,H,I)   A,B,..,I Bytes
blk2=variable Länge

crc(a⊕b) = crc(a)⊕crc(b)
a=(A,B,C,D.E,F,G,H,I, 0x00 * len(blk2))
b=(0x00*8, blk2)

>Ich habe aber jetzt einige Kunden, die wollen
>z.B. eine Hex-Datei zeilenweise auslesen oder bekommen die Hex-Datei
>selbst über Bluetooth.
Die de facto Standard "Hex-Dateien" sind Intel-Standard(I) oder
Motorola(M) S-Records oder Derivate davon.
VORSICHT: diese "I/M-Hex-Records" muessen bzgl Adressen
nicht aufeinanderfolgend sein, koennen also Lücken enthalten.
Oder man duerfte vorher beschriebene Stellen nochmal mit
anderen Werten überschreiben (z.B. 1-Pass Codegeneratoren, die erst
nach einem Block die forward adresse kennen bei einem Sprung)

Da könnte die Längenbestimmung sicher ein Spass werden und einige
interessante Supportanfragen bescheren ;-)

>Mit den hier gewonnenen Informationen (Danke an Falk) habe ich mich
>jetzt schon dafür entschieden, dass Protokoll zu ändern.

Das ist sicher eine gute Idee, sofern in dem ersten 64-Bit Block
eine Versionsnummer des Protokoll vorhanden und änderbar ist.
Überdenke auch mal den Startwert des CRC, denn wenn es da auf die
Lange ankommt ist (z.B.) crc(0x0 0x0...0x0 blk2) = crc(0x0 blk2)  :-)

von Torsten R. (Firma: Torrox.de) (torstenrobitzki)


Lesenswert?

Hans H. schrieb:

> Was just dem Ethernet-Polynom in IEEE802.3 gleich ist.
> Benutzt Du hier Ethernet auf Layer2/LinkLayer/"Verbinungsebene"?

Die CRC wird einfach über die Firmware gerechnet, damit der Bootloader 
feststellen kann, dass die Firmware unbeschädigt ist. Der Client 
berechnet die selbe CRC um sicher zu stellen, dass die Übertragung 
fehlerfrei war.

> Da könnte die Längenbestimmung sicher ein Spass werden und einige
> interessante Supportanfragen bescheren ;-)

Ich liefere dem Kunden eine Bibliothek, in der das Protokoll 
implementiert ist. Die Firmware auf der Client-Seite ist als Funktion, 
die Code-Blöcke liefert abstrahiert. Da diese Funktion die Code-Blöcke 
nicht in Reihenfolge aufsteigender Adresse liefern muss, führt die 
Protokoll-Bilbliothek dort mehrere lineare Suchen durch. Das passt sehr 
gut, für den von mir geschriebenen hex-File Command Line Client, nicht 
aber, wenn man auf einem µC mit SD-Karte das Hex-File zeilenweise 
auslesen will :-)

Danke Unit-Tests ist diese Art von Komplexität aber zum Glück gut 
handhabbar.

> Überdenke auch mal den Startwert des CRC, denn wenn es da auf die
> Lange ankommt ist (z.B.) crc(0x0 0x0...0x0 blk2) = crc(0x0 blk2)  :-)

Autsch, zu spät. Werde ich mal vormerken, für den Fall, dass noch mal 
eine Protokoll-Änderung nötig ist.

Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.