Was ist eine schnellere Alternative zu einem CRC?

27

Ich führe eine Datenübertragung von einem dsPIC zu einem PC durch und führe eine 8-Bit-CRC für jeden Block mit 512 Bytes durch, um sicherzustellen, dass keine Fehler vorliegen. Wenn mein CRC-Code aktiviert ist, erhalte ich ungefähr 33 KB / s, ohne ihn erhalte ich 67 KB / s.

Mit welchen alternativen Fehlererkennungsalgorithmen können Sie feststellen, ob dies schneller ist?

FigBug
quelle
5
Wie ist das CRC selbst implementiert? Bitweise? Wechseln Sie dann zu einer tabellenbasierten Methode. Bytewise? Berücksichtigen Sie den Kompromiss zwischen Platz, Komplexität und Zeit, der mit dem Erhöhen der Tabellengröße auf beispielsweise 16 Bit verbunden ist (was zwei Bytes gleichzeitig verarbeiten würde, aber 64 KB Tabellenspeicher beanspruchen würde).
Aidan Cully
Ich habe nur 16 KB RAM und 128 KB ROM, so dass eine 64-KB-Tabelle keine Option ist.
FigBug
1
Sie verwenden also eine 256-Byte-Tabelle? oder bitweises CRC? Wenn Sie bitweise vorgehen, wäre bytewise (mit einer 256-Byte-Tabelle) achtmal schneller.
Aidan Cully
Derzeit probiere ich bitweise einen
256er-
1
67 kb / s bis 33 kb / s? Ich bin mir nicht sicher, was Ihre andere Verarbeitung betrifft, aber das klingt selbst für ein PIC ziemlich aufwändig. Vielleicht gibt es noch andere Probleme, die Ihre Leistung beeinträchtigen?
Rei Miyasaka

Antworten:

41

Es gibt zwar möglicherweise schnellere Optionen als CRC, aber wenn Sie diese verwenden, werden Sie wahrscheinlich ein gewisses Maß an Fehlererkennungsfähigkeit einbüßen. Abhängig von Ihren Anforderungen an die Fehlererkennung besteht eine Alternative darin, stattdessen einen für Ihre Anwendung optimierten CRC-Code zu verwenden.

Einen Vergleich von CRC mit anderen Optionen finden Sie in der hervorragenden Antwort von Martin Thompson .

Eine Option, die dabei hilft, ist pycrc , ein Tool (in Python 1 geschrieben ), das C-Quellcode für Dutzende von Kombinationen aus crc-Modell und Algorithmus generieren kann . Auf diese Weise können Sie Geschwindigkeit und Größe für Ihre eigene Anwendung optimieren, indem Sie verschiedene Kombinationen auswählen und bewerten. 1: Benötigt Python 2.6 oder höher.

Es unterstützt das crc-8 Modell , sondern auch unterstützt crc-5, crc-16und crc-32unter anderem. Wie für Algorithmen unterstützt sie bit-by-bit, bit-by-bit-fastund table-driven.

Zum Beispiel (Herunterladen des Archivs):

$ wget --quiet http://sourceforge.net/projects/pycrc/files/pycrc/pycrc-0.8/pycrc-0.8.tar.gz/download
$ tar -xf pycrc-0.8.tar.gz
$ cd pycrc-0.8
$ ./pycrc.py --model=crc-8 --algorithm=bit-by-bit      --generate c -o crc8-byb.c
$ ./pycrc.py --model=crc-8 --algorithm=bit-by-bit-fast --generate c -o crc8-bybf.c
$ ./pycrc.py --model=crc-8 --algorithm=table-driven    --generate c -o crc8-table.c
$ ./pycrc.py --model=crc-16 --algorithm=table-driven   --generate c -o crc16-table.c
$ wc *.c
   72   256  1790 crc8-byb.c
   54   190  1392 crc8-bybf.c
   66   433  2966 crc8-table.c
  101   515  4094 crc16-table.c
  293  1394 10242 total

Sie können sogar irre Dinge wie das Festlegen mit Dual-Nibble-Lookups (mit einer 16-Byte-Lookup-Tabelle) anstelle von Single-Byte-Lookups (mit 256-Byte-Lookup-Tabelle) ausführen.

Zum Beispiel (Klonen des Git-Repository):

$ git clone http://github.com/tpircher/pycrc.git
$ cd pycrc
$ git branch
* master
$ git describe
v0.8-3-g7a041cd
$ ./pycrc.py --model=crc-8 --algorithm=table-driven --table-idx-width=4 --generate c -o crc8-table4.c
$ wc crc8-table4.c
  53  211 1562 crc8-table4.c

Angesichts Ihrer Speicher- und Geschwindigkeitsbeschränkungen ist diese Option möglicherweise der beste Kompromiss zwischen Geschwindigkeit und Codegröße. Der einzige Weg, um sicher zu sein, wäre jedoch ein Benchmarking.


Das pycrc- Git-Repository befindet sich auf github , ebenso wie der Issue-Tracker , kann aber auch von sourceforge heruntergeladen werden .

Mark Booth
quelle
Ich glaube nicht, dass die meisten Leute, die Dinge für das PIC schreiben, C verwenden, aber das könnte funktionieren, wenn dem so ist.
Billy ONeal
4
@ Billy - Wirklich? Ich glaube nicht, dass mir jemand begegnet ist, der für PIC kommerziell entwickelt hat und C nicht verwendet. Ich habe heutzutage sicherlich nicht die Geduld für Assembler, und gut strukturiertes C kann ziemlich kompakt werden.
Mark Booth
Ich verwende ein dsPIC und ich verwende C.
FigBug
@FigBug - Danke, ich freue mich, dass dir meine Antwort gefällt. Wenn Sie einige Benchmark-Tests durchführen, können Sie meine Antwort mit Ihren Ergebnissen bearbeiten. Ich würde gerne wissen, welchen Unterschied die einzelnen Algorithmen in Bezug auf den Anwendungsdurchsatz und den Speicherbedarf machen.
Mark Booth
1
Noch ein Votum für pyCrc hier. Verwenden Sie es in verschiedenen Projekten mit unterschiedlichen Einschränkungen und es ist einfach großartig.
Vicky
11

Einfache Ein-Bit-Parität (im Grunde XOR-Verknüpfung der Daten über sich selbst immer wieder) ist ungefähr so ​​schnell wie möglich. Sie verlieren jedoch einen Großteil der Fehlerprüfung eines CRC.

Im Pseudocode:

char checksum = 0;
for each (char c in buffer)
{
    checksum ^= c;
    SendToPC(c);
}
SendToPc(checksum);
Billy ONeal
quelle
1
Ich habe das vor einiger Zeit untersucht. Ich glaube, dass Summieren statt XOR tatsächlich ein bisschen besser funktioniert. (Summiere normalerweise alles und sende dann das Zweierkomplement der Summe als Prüfsumme. Summiere auf dem Empfänger alles einschließlich der erhaltenen Prüfsumme. Das Ergebnis ist 0, wenn alles in
Ordnung ist
1
@quickly: Ich glaube nicht, dass es einen signifikanten Unterschied zwischen diesen beiden gibt - keine der beiden Methoden bietet die Gewissheit, dass die Dinge nicht beschädigt wurden. Wenn add auf der Zielarchitektur auf jeden Fall schneller ist, verwenden Sie dies stattdessen.
Billy ONeal
7
Ich erinnere mich: Der Hauptunterschied zwischen ADD und XOR besteht darin, dass Mehrbitfehler weniger auffindbar sind. Bei einem Bytestrom werden Fehler an derselben Bitposition mit XOR aufgehoben. Wenn ADD verwendet wird, bedeutet die Ausbreitung von Bits durch ein Prüfsummenbyte, dass dieser Fall besser erkennbar ist. (Mehrere Bitfehler in verschiedenen Bits, die über den Bytestrom verteilt sind, sind jedoch - abhängig von den jeweiligen Umständen - wahrscheinlich weniger erkennbar.) Eine solche Prüfsummenanordnung ist für Mehrbitfehler SCHRECKLICH, daher ist sie ein eher untergeordnetes Argument.
quick_now
XOR ist viel weniger hilfreich als CRC.
3
@ Thorbjørn: Ich glaube, das habe ich in meiner Antwort anerkannt. :)
Billy ONeal
10

Ein wirklich gutes Papier zum Vergleich der Leistung verschiedener Prüfsummen und CRCs in einem eingebetteten Kontext:

Die Wirksamkeit von Prüfsummen für eingebettete Netzwerke

Einige Zitate aus den Schlussfolgerungen (basierend auf ihren Studien über unentdeckte Fehlerwahrscheinlichkeiten):

Wenn Burst-Fehler dominieren

XOR, Zweierkomplementadditions- und CRC-Prüfsummen bieten eine bessere Fehlererkennungsleistung als die eigenen Komplementadditions-, Fletcher- und Adler-Prüfsummen.

In anderen Anwendungen

Zur Fehlererkennung sollte nach Möglichkeit ein „gutes“ CRC-Polynom verwendet werden

Wenn die Berechnungskosten sehr begrenzt sind

(wie in Ihrem Fall), verwenden Sie (in der Reihenfolge der Wirksamkeit):

Andere Zitate:

Die Fletcher-Prüfsumme hat geringere Rechenkosten als die Adler-Prüfsumme und ist entgegen der landläufigen Meinung in den meisten Situationen auch effektiver.

und

Es gibt im Allgemeinen keinen Grund, die übliche Praxis der Verwendung einer XOR-Prüfsumme in neuen Konstruktionen fortzusetzen, da sie die gleichen Software-Berechnungskosten wie eine additionsbasierte Prüfsumme hat, jedoch nur etwa halb so effektiv bei der Erkennung von Fehlern ist.

Martin Thompson
quelle
1
Als Bonus ist eine Fletcher-Prüfsumme sehr einfach zu implementieren.
RubberDuck
6

Die Adler-Prüfsumme sollte ausreichen, um Übertragungsverzerrungen festzustellen. Es wird von der Zlib-Komprimierungsbibliothek verwendet und vom Java 3D Mobile Graphics Standard übernommen, um eine schnelle, aber effektive Überprüfung der Datenintegrität zu ermöglichen.

Von der Wikipedia-Seite :

Eine Adler-32-Prüfsumme wird erhalten, indem zwei 16-Bit-Prüfsummen A und B berechnet und ihre Bits zu einer 32-Bit-Ganzzahl verkettet werden. A ist die Summe aller Bytes in der Zeichenfolge plus eins und B ist die Summe der einzelnen Werte von A aus jedem Schritt.

Zu Beginn eines Adler-32-Laufs wird A auf 1, B auf 0 initialisiert. Die Summen erfolgen modulo 65521 (die größte Primzahl kleiner als 2 ^ 16 oder 65536). Die Bytes werden in der Netzwerkreihenfolge (Big Endian) gespeichert, wobei B die beiden höchstwertigen Bytes belegt.

Die Funktion kann ausgedrückt werden als

 A = 1 + D1 + D2 + ... + Dn (mod 65521)
 B = (1 + D1) + (1 + D1 + D2) + ... + (1 + D1 + D2 + ... + Dn) (mod 65521)
   = n×D1 + (n-1)×D2 + (n-2)×D3 + ... + Dn + n (mod 65521)

 Adler-32(D) = B × 65536 + A

Dabei ist D die Zeichenfolge von Bytes, für die die Prüfsumme berechnet werden soll, und n ist die Länge von D.

Gnawme
quelle
Beachten Sie, dass Adler32 für kurze Datenmengen nahezu unbrauchbar ist. Bis zu ca. 180 Bytes erzeugt es zahlreiche Kollisionen.
greyfade
+1 - ein vernünftiger Mittelweg zwischen einer CRC und einer einfachen Bitparität.
Billy ONeal
@greyfade - FigBug erwähnte die Verwendung von 512-Byte-Blöcken, daher sollte dies für das OP kein Problem darstellen. Gut, dass es für Menschen mit anderen Anforderungen gilt.
Mark Booth
5

Mir ist nichts bekannt, das bei der Fehlererkennung so effektiv ist wie ein CRC und schneller - wenn es das gäbe, würden die Leute es stattdessen verwenden.

Sie könnten es mit einer einfachen Prüfsumme versuchen, aber das ist weitaus unwahrscheinlicher, Fehler zu erkennen.

Bob Murphy
quelle
2
Ich bin bereit, eine Effektivität für die Geschwindigkeit aufzugeben.
FigBug
3

Nun, die Prüfsummenlogik selbst ist gut und die Leute können mit schnelleren Algorithmen helfen.

Wenn Sie die Geschwindigkeit Ihrer Komponente verbessern möchten, müssen Sie möglicherweise die gesamte Technik ändern, um die Übertragungskomponente von der Validierungskomponente zu trennen.

Wenn Sie diese als zwei unabhängige Elemente (auf verschiedenen Threads) haben, können Sie die volle Übertragungsgeschwindigkeit erhalten und nur fehlgeschlagene Pakete erneut senden.

Der Algorithmus würde ungefähr so ​​aussehen:

  • Der Server teilt sich in bekannte Paketgrößen auf (z. B. 1K-Chunks). Stellt sie in die Warteschlange "gesendet werden".
  • Jedes Paket wird mit einer 16- oder 32-Bit-ID UND seiner Prüfsumme übertragen.
  • Der Client empfängt jedes Paket und stellt es in eine Warteschlange, um es zu verarbeiten.
  • Auf einem separaten Thread entnimmt der Client jeweils ein Paket und führt die Validierung durch.
    • Bei Erfolg wird es der endgültigen Sammlung von Paketen (in ID-Reihenfolge) hinzugefügt
    • Bei einem Fehler wird die fehlgeschlagene ID an den Server zurückgemeldet, der das zu sendende Paket in die Warteschlange stellt.
  • Sobald Sie die Pakete erhalten und validiert haben und die IDs in der richtigen Reihenfolge (beginnend mit 1) vorliegen, können Sie diese auf die Festplatte schreiben (oder tun, was immer erforderlich ist).

Auf diese Weise können Sie mit der höchstmöglichen Geschwindigkeit übertragen, und wenn Sie mit Ihrer Paketgröße spielen, können Sie die Optimium-Fehlerrate im Vergleich zur Validierungs- / Erneutsenderate ermitteln.

Robin Vessey
quelle
2

Prüfsummen sind traditionell

(reduziere # '+ stream)

XOR wie oben angegeben würde ebenfalls funktionieren

(Reduziere # 'XOR-Stream)

Ein etwas aufwändigeres (langsameres) Schema ist die Standard-Paritätsprüfung für serielle Verbindungen.

Auf dieser Ebene tauschen Sie Korrektheit gegen Geschwindigkeit. Diese werden gelegentlich fehlschlagen.

Auf der nächst anspruchsvolleren Ebene können Sie einige Dinge vom Typ crc / hash verwenden.

Ein anderes Design würde darin bestehen, die Größe des für den Stream verwendeten Blocks zu erhöhen.

Sie sollten eine Schätzung der tatsächlichen Fehlerrate haben, um Ihre Algorithmusauswahl und Parameter für die Blockgröße abzustimmen.

Paul Nathan
quelle