Schneller CRC-Algorithmus?

Ich möchte eine 32-Bit-Nummer aus einer ASCII-Zeichenfolge erstellen. CRC32-Algorithmus ist genau das, was ich suche, aber ich kann es nicht verwenden, weil die Tabelle, die es benötigt, viel zu groß ist (es ist für ein eingebettetes System, wo Ressourcen sehr selten sind).Schneller CRC-Algorithmus?

Also: irgendwelche Vorschläge für einen schnellen und schlanken CRC-Algorithmus? Es spielt keine Rolle, wenn Kollisionen etwas wahrscheinlicher sind als mit der ursprünglichen CRC32.

Danke!

Quelle

2015-01-14 Elmi

CRC32 kann ohne Lookup-Tabelle oder mit einer 1k-Byte-Lookup-Tabelle implementiert werden, wenn Sie dies tun müssen, ohne einen größeren Geschwindigkeitsverlust im Vergleich zur 256k-Lookup-Tabellenvariante. Beispiel unter http://wiki.osdev.org/CRC32. Wenn Sie wirklich Bytes speichern müssen, verwenden Sie adler32. – dascandy

Was Sie mit 'Ressourcen sind sehr selten 'meinen? Weniger als 64 MB, weniger als 8 KB oder weniger als 512 Byte? – jeb

jeb: SEHR selten bedeutet, dass ich momentan nicht genug Platz habe, um die Tabelle hinzuzufügen, wie in http://www.opensource.apple.com/source/xnu/xnu-1456.1.26/bsd/libkern/crc32.c gezeigt – Elmi

CRC-Implementierungen verwenden Tabellen für die Geschwindigkeit. Sie sind nicht erforderlich.

Hier ist ein kurzer CRC32, der entweder das Castagnoli-Polynom (das gleiche wie von der Intel-crc32-Anweisung verwendet) oder das Ethernet-Polynom (das gleiche wie in zip, gzip, etc.) 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; 
}

Der anfängliche Wert sollte Null sein. Die Routine kann nacheinander mit Datenstücken aufgerufen werden, um den CRC zu aktualisieren. Sie können die innere Schleife für Geschwindigkeit ausrollen, obwohl Ihr Compiler das für Sie sowieso tun könnte.

Quelle

2015-01-14 19:26:19

@HolyBlackCat: warum? Dies ist das gängige Idiom für die Berechnung von CRCs: Übergeben Sie den bisher berechneten CRC und geben Sie den aktualisierten CRC-Wert zurück. –

Auch dies kompiliert sehr effizient, mit dem Argument kommen und und der Wert wird zurückgegeben bleiben und nie das gleiche Register verlassen. –

@MichaelBurr Ich weiß nicht, warum ich vor drei Jahren das sagte. :/ – HolyBlackCat

Offensichtlich bringt die größte Nachschlagetabelle die beste Leistung, aber Sie können jede (kleinere) Tabelle für 16,8- oder 4-Bit-Nachschlagevorgänge verwenden.

So sind die Tischgrößen sind 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 viermal langsamer als die 16-Bit-Tabelle ist.
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, das Schlüsselwort const zu verwenden.
Meistens müssen Sie die Tabelle in einen Abschnitt in Flash platzieren, indem Sie Ihre Linker-Befehlsdatei ändern.

Quelle

2015-01-14 09:55:43 jeb

Schneller CRC-Algorithmus?

Antwort

Verwandte Themen