`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_tcrc=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_tcrc2=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
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?
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.
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!
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:
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.
>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?
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
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.
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.
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.
>> 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) :-)
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.
Thread beobachten
Seitenaufteilung abschalten