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?)
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?
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.
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!
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:
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?
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.
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.
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.
Torsten R. schrieb im Beitrag #7478724:
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.
(== 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 .
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) :-)
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.
