Mal 'ne Frage: Ich hab ein Protocol wo ich zwei Byte Platz für eine Prüfsumme habe. Vorgesehen ist eigentlich ein CRC16. Soweit, so einfach. Allerdings habe ich gute Gründe kein CRC16 einzusetzen. Da wäre Beispielsweise die Code Größe, die ein Thema ist also auch die Tatsache, das ich auf meiner Platform bereits Hardware Support für CRC32 habe. Nun dachte ich mir: ich könnte ja statt: Checksum16 = CRC16(data) sowas machen: Checksum16 = LSB16(CRC32(data)) oder Checksum16 = MSB16(CRC32(data)) oder gar beide Teile von CRC32 verwursten: Checksum16 = LSB16(CRC32(data)) ^ MSB16(CRC32(data)) Wie CRC funktioniert habe ich verstanden, und mir ist klar, das ich im Prinzip eine einigermaßen brauchbare Prüfsumme zur Fehlererknnung bekomme. Allerdings kann ich nicht abschätzen, wie sehr dieser Hack der Fehlererkennung schadet. D.h. wie viel schlechter die Benutzung einer verkürzen CRC32 im Vergleich zu CRC16 ist. Hat da jemand Erfahrung oder einen Tip wie ich mathematisch an das Thema heran gehen kann?
Mit XOR könntest Du die oberen und unteren 16 Bit zu einer 16 Bit Prüfsumme verwursteln, verlierst halt damit enstprechend viel Redunanz, aber 16 Bit reichen für die meisten Fälle, (solange die Übertragung im Normalfall fehlerfrei läuft) Handkerum benötigt ein ein Software CRC16-Generator wenig Speicher, Code und CPU-Power.
Auf den Plattformen, die CRC32-Support in Hardware haben, ist die Codegröße kein Thema. Klar, wenn Du mit Lookup-Tabelle über volle Bytes herangehst, dann brauchst Du 256 * 2 Bytes, also 512 Bytes. Der Code selber ist minimal. Sind 512 Bytes (ROM!) zuviel, kannst Du die Lookup-Tabelle aber auch bloß auf Halbbytes machen, dann brauchst Du 16 * 2 Bytes, also 32 Bytes dafür. Vorteil, wenn Du das in Software machst: Das kann dann jede Gegenstelle. Bei CRC in Hardware hängt es sehr davon ab, was genau denn implementiert wurde. Welcher CRC-Initwert, mit Einerkomplement am Ende oder ohne.
Nils P. schrieb: > Allerdings habe ich gute Gründe kein CRC16 einzusetzen. Da wäre > Beispielsweise die Code Größe, die ein Thema ist also auch die Tatsache, > das ich auf meiner Platform bereits Hardware Support für CRC32 habe. Für manche CRC16 Polynome gibt es sehr kompakte C-Implementationen, zum Beispiel CRC16-CCITT (Kermit): Geklaut aus den AVR standard libraries:
1 | uint16_t crc16_ccitt_kermit_update(uint16_t crc, char data) { |
2 | data ^= (crc & 0xff); |
3 | data ^= data << 4; |
4 | return ((((uint16_t)data << 8) | (crc >> 8)) ^ (uint8_t)(data >> 4) ^ ((uint16_t)data << 3)); |
5 | }
|
wird auf nem Cortex-M0 zu 13 Instruktionen kompiliert:
1 | 00000514 <crc16_ccitt_kermit_update>: |
2 | 514: 4041 eors r1, r0 |
3 | 516: b249 sxtb r1, r1 |
4 | 518: b2cb uxtb r3, r1 |
5 | 51a: 011b lsls r3, r3, #4 |
6 | 51c: 4059 eors r1, r3 |
7 | 51e: b2c9 uxtb r1, r1 |
8 | 520: 020b lsls r3, r1, #8 |
9 | 522: 0a00 lsrs r0, r0, #8 |
10 | 524: 4318 orrs r0, r3 |
11 | 526: 090b lsrs r3, r1, #4 |
12 | 528: 00c9 lsls r1, r1, #3 |
13 | 52a: 4059 eors r1, r3 |
14 | 52c: 4048 eors r0, r1 |
15 | 52e: 4770 bx lr |
Jetzt subtrahiere zum Vergleich davon das Bitgeschubse das nötig wäre um die Hardware CRC zu initialisieren, sie zu bedienen, das Ergebnis auf 16 Bit zu kürzen und dann bleibt nicht mehr viel Vorteil bzgl Flashverbrauch. Einzig die Laufzeit der Hardware wird kürzer sein. Aber Dir ging es ja primär um den Flashverbrauch wenn ich das richtig verstanden habe.
:
Bearbeitet durch User
Nils P. schrieb: > Allerdings habe ich gute Gründe kein CRC16 einzusetzen Dann musst du das allerdings auf beiden Seiten implementieren. Wenn Kompatibilität kein Problem ist kannst du natürlich machen was du willst. Nils P. schrieb: > D.h. wie viel schlechter die Benutzung einer > verkürzen CRC32 im Vergleich zu CRC16 ist. Bei geeignetem Polynom dürfte es keinen Unterschied geben, aber hast du da überhaupt Einfluss drauf? Bei einer halbwegs brauchbaren Verbindung macht das sowieso nichts aus, da würde auch eine einfache Prüfsumme genügen. Georg
Bernd K. schrieb: > uint16_t crc16_ccitt_kermit_update(uint16_t crc, char data) { > data ^= (crc & 0xff); > data ^= data << 4; > return ((((uint16_t)data << 8) | (crc >> 8)) ^ (uint8_t)(data >> 4) ^ > ((uint16_t)data << 3)); > } Danke alle miteinander. Ich wusste gar nicht, das es eine so kompakte Implementation gibt. Da gibt es wirklich keine Ausreden mehr. Gruß, Nils
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
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.