Elmi
Ich möchte aus einem ASCII-String eine 32-Bit-Zahl erstellen. Der CRC32-Algorithmus ist genau das, wonach ich suche, aber ich kann ihn nicht verwenden, weil die erforderliche Tabelle viel zu groß ist (es ist für ein eingebettetes System, bei dem Ressourcen SEHR selten sind).
Also: Irgendwelche Vorschläge für einen schnellen und schlanken CRC-Algorithmus? Es macht nichts, wenn Kollisionen etwas wahrscheinlicher sind als beim originalen CRC32.
Markus Adler
CRC-Implementierungen verwenden Tabellen für die Geschwindigkeit. Sie sind nicht erforderlich.
Hier ist ein kurzer CRC32, der entweder das Castagnoli-Polynom (dasselbe wie von der Intel crc32-Anweisung verwendet) oder das Ethernet-Polynom (dasselbe wie in zip, gzip usw.) verwendet.
#include <stddef.h>
#include <stdint.h>
/* CRC-32C (iSCSI) polynomial in reversed bit order. */
#define POLY 0x82f63b78
/* CRC-32 (Ethernet, ZIP, etc.) polynomial in reversed bit order. */
/* #define POLY 0xedb88320 */
uint32_t crc32c(uint32_t crc, const unsigned char *buf, size_t len)
{
int k;
crc = ~crc;
while (len--) {
crc ^= *buf++;
for (k = 0; k < 8; k++)
crc = crc & 1 ? (crc >> 1) ^ POLY : crc >> 1;
}
return ~crc;
}
Die Initiale crc Wert sollte Null sein. Die Routine kann nacheinander mit Datenblöcken aufgerufen werden, um den CRC zu aktualisieren. Sie können die innere Schleife aus Geschwindigkeitsgründen entrollen, obwohl Ihr Compiler dies möglicherweise sowieso für Sie erledigt.
crc = (crc >> 1) ^ (POLY & (0 - (crc & 1))); ist ~33 % schneller, wenn es für x86 mit GCC/ICC/CLANG kompiliert wird (104 MB/s vs. 134 MB/s). Auf demselben System beträgt Slice-8 2040 MB/s und Intel CRC32C 8 GB/s, also macht es am Ende vielleicht keinen großen Unterschied.
– t0rakka
13. Februar 2018 um 14:37 Uhr
@SnappleLVR Noch schneller wäre eine byteweise oder wortweise Tabellenimplementierung. Sehen crcanydie solche Routinen generiert.
– Markus Adler
13. Februar 2018 um 18:03 Uhr
Benchmarking mit derselben Maschine wie oben: 1430 MB/s, nicht schlecht, aber Slice-8 ist immer noch 30 % schneller und die CRC32C-Anweisungen sind 450 % schneller. Ich habe nur darauf hingewiesen, dass die einfache bitweise Version mit einer kleinen chirurgischen Änderung der Quelle so optimiert werden kann, dass sie 33% schneller ist. Der ursprüngliche Code, der mit CLANG und GCC unter Verwendung von -O3 in “test/cmov” kompiliert wurde. Die schnellere Variante verwendet einfaches NEG/XOR/AND, wie es von der Quelle erwartet werden kann. Das (0 – n) ist nur ein Trick, um die Negation von vorzeichenlosen Ganzzahlen zuzulassen. Um es klarzustellen, ich habe nicht behauptet, es sei die schnellstmögliche Routine. xD
– t0rakka
14. Februar 2018 um 9:22 Uhr
jeb
Natürlich bringt die größte Lookup-Tabelle die beste Leistung, aber Sie können jede (kleinere) Tabelle für 16,8- oder 4-Bit-Lookups verwenden.
Die Tabellengrößen sind also für crc32:
16bit-lookup: 4*2^16=256k
8bit-lookup: 4*2^8=1k
4bit-lookup: 4*2^4=64byte
Die 4-Bit-Tabelle ist viermal langsamer als die 16-Bit-Tabelle.
Was Sie verwenden sollten, hängt von Ihren Geschwindigkeitsanforderungen ab.
Wie Luka Rahne erwähnt, ist es eine gute Idee, eine Tabelle in den Flash-Speicher zu legen, aber auf vielen Plattformen reicht es nicht aus, die zu verwenden const Stichwort.
Meistens müssen Sie die Tabelle in einen in Flash platzierten Abschnitt platzieren, indem Sie Ihre Linker-Befehlsdatei ändern.
Siehe auch Schneller CRC32eine Webseite von Stephan Brumme, die einen Vergleich mit unterschiedlichen Tabellengrößen bietet.
– Wolf
26. August 2021 um 9:10 Uhr
CRC32 kann ohne Lookup-Tabelle oder mit einer 1k-Byte-Lookup-Tabelle implementiert werden, wenn Sie müssen, ohne größere Geschwindigkeitseinbußen im Vergleich zur Variante mit 256k-Lookup-Tabellen. Beispiel bei wiki.osdev.org/CRC32. Wenn Sie wirklich Bytes sparen müssen, verwenden Sie adler32.
– dascandy
14. Januar 2015 um 9:47 Uhr
Was meinst du mit
ressources are VERY rare? Weniger als 64 MB, weniger als 8 KB oder weniger als 512 Byte?– jeb
14. Januar 2015 um 9:49 Uhr
Vielleicht reparieren Sie einfach diesen Code und legen die Tabelle im Flash ab. Die meisten Linker setzen konstante Variablen in Flash, und heutzutage kommen sogar Low-End-CPUs mit einer absteigenden Menge an OTP. Definieren Sie einfach die Tabelle als konstant.
– Lukas Rahne
14. Januar 2015 um 9:54 Uhr
Wenn Sie keine besonderen Anforderungen an die Qualität des Hash/der Prüfsumme/was auch immer haben, etwas ganz Einfaches wie
boost::hash_combineoder sogar nur XOR, könnte gut genug sein.– Mike Seymour
14. Januar 2015 um 9:59 Uhr
Die Frage ist nicht off-topic. Die Stackoverflow-Polizei kennt anscheinend nicht den Unterschied zwischen einem Algorithmus und einer Implementierung. Es ist hier völlig Thema, zu fragen, welche Algorithmen existieren, um eine bestimmte Aufgabe zu erledigen.
– Markus Adler
22. Januar 2017 um 17:00 Uhr