Implementieren des CRC32C von SSE 4.2 in Software
Also ich habe ein design mit CRC32C-Prüfsummen, um sicherzustellen, dass die Daten nicht beschädigt wurde. Ich habe mich entschieden, CRC32C, denn ich kann sowohl eine software-version und hardware-beschleunigte version, wenn der computer läuft die software unterstützt SSE 4.2
Werde ich vom Intel developer manual (vol 2A), die anscheinend den Algorithmus hinter der crc32
Unterricht. Ich bin allerdings mit wenig Glück. Intel developer guide sagt Folgendes:
BIT_REFLECT32: DEST[31-0] = SRC[0-31]
MOD2: Remainder from Polynomial division modulus 2
TEMP1[31-0] <- BIT_REFLECT(SRC[31-0])
TEMP2[31-0] <- BIT_REFLECT(DEST[31-0])
TEMP3[63-0] <- TEMP1[31-0] << 32
TEMP4[63-0] <- TEMP2[31-0] << 32
TEMP5[63-0] <- TEMP3[63-0] XOR TEMP4[63-0]
TEMP6[31-0] <- TEMP5[63-0] MOD2 0x11EDC6F41
DEST[31-0] <- BIT_REFLECT(TEMP6[31-0])
Nun, soweit ich sagen kann, ich habe alles gemacht bis zu der Linie, die TEMP6
richtig, aber ich denke, ich kann entweder Missverständnis der Polynom-division oder die Umsetzung falsch. Wenn mein Verständnis richtig ist, 1 /1 mod 2 = 1
0 /1 mod 2 = 0
und beide teilt durch null nicht definiert sind.
Was ich nicht verstehe ist, wie man binäre division mit 64-bit-und 33-bit-Operanden arbeiten. Wenn SRC
ist 0x00000000
und DEST
ist 0xFFFFFFFF
TEMP5[63-32]
werden alle bits, während TEMP5[31-0]
werden alle undefinierten bits.
Wenn ich die bits aus TEMP5
als der Zähler, würde es 30 Divisionen durch null, da das Polynom 11EDC6F41
nur 33 bits lang (und damit Umwandlung in eine 64-bit-Ganzzahl ohne Vorzeichen lässt die top-30 bits gelöscht), und so der Nenner ist unset für 30 bits.
Allerdings, wenn ich das Polynom als Zähler, die unteren 32 bits der TEMP5
sind ausgeschaltet, wodurch dividiert durch null gibt, und die top-30 bits, das Ergebnis wäre gleich null, wie die top-30 bits der Zähler auf null, als 0 /1 mod 2 = 0
.
Bin ich Missverständnis, wie das funktioniert? Einfach etwas fehlt? Oder hat Intel weggelassen, einige entscheidende Schritt in Ihrer Dokumentation?
Den Grund ging ich zu Intel developer guide für das, was zu sein schien der Algorithmus verwendet, Sie ist, weil Sie verwendet einen 33-bit-Polynom, und ich wollte Ausgänge identisch, was nicht passiert, wenn ich die 32-bit-Polynom 1EDC6F41
(Karte unten).
uint32_t poly = 0x1EDC6F41, sres, crcTable[256], data = 0x00000000;
for (n = 0; n < 256; n++) {
sres = n;
for (k = 0; k < 8; k++)
sres = (sres & 1) == 1 ? poly ^ (sres >> 1) : (sres >> 1);
crcTable[n] = sres;
}
sres = 0xFFFFFFFF;
for (n = 0; n < 4; n++) {
sres = crcTable[(sres ^ data) & 0xFF] ^ (sres >> 8);
}
Den oben genannten code erzeugt 4138093821
als Ausgang, und die crc32
opcode erzeugt 2346497208
mit Hilfe der input 0x00000000
.
Sorry, wenn dies falsch geschrieben ist, oder unverständlich in Orten, es ist ziemlich spät für mich.
InformationsquelleAutor der Frage LMS | 2013-07-15
Du musst angemeldet sein, um einen Kommentar abzugeben.
Mark Adler ' s Antwort ist richtig und vollständig sind, aber diejenigen, die auf schnelle und einfache Weise zu integrieren CRC-32C in Ihrer Anwendung könnte es ein wenig schwierig die Anpassung des code, vor allem, wenn Sie sind mit Windows-und .NET.
Habe ich einen Bibliothek, die CRC-32C entweder hardware-oder software-Methode, die abhängig von der verfügbaren hardware. Es ist als NuGet-Paket für C++ und .NET. Es ist Open-Source, natürlich.
Neben Verpackungen Mark Adler ' s code von oben, die ich gefunden habe, eine einfache Möglichkeit zu verbessern und den Durchsatz der software-fallback von 50%. Auf meinem computer, die Bibliothek erreicht jetzt 2 GB/s in der software und über 20 GB/s in hardware. Für diejenigen, die neugierig sind, hier die optimierte software-Implementierung:
Wie Sie sehen können, ist es lediglich crunches größeren block zu einem Zeitpunkt. Es braucht größere lookup-Tabelle, aber es ist immer noch cache-freundlich. Die Tabelle generiert wird, die gleiche Weise, nur mit mehr Zeilen.
Einen extra-Sache, die ich erkundet ist die Verwendung von PCLMULQDQ-Instruktion zu erhalten, die hardware-Beschleunigung auf AMD-Prozessoren. Ich habe es geschafft, port Intel CRC-patch für zlib (auch verfügbar auf GitHub) CRC-32C Polynom
außer die magic Konstante 0x9db42487. Wenn jemand in der Lage ist, zu entziffern, bitte lassen Sie mich wissen. Nach supersaw7 ausgezeichnete Erklärung auf redditich habe portiert, auch das schwer fassbare 0x9db42487 konstant und ich brauche nur etwas Zeit, um zu Polieren und testen Sie es.InformationsquelleAutor der Antwort Robert Važan
Vergleiche ich die verschiedenen algorithmen hier: https://github.com/htot/crc32c
Der Schnellste Algorithmus stammt aus Intels crc_iscsi_v_pcl.asm assembly code (welcher in einer modifizierten form in den linux-kernel) und mit einem C-wrapper - (crcintelasm.cc) enthalten, der in das Projekt.
Zu können, führen Sie diesen code auf 32-bit-Plattformen zuerst wurde eine Portierung auf C (crc32intelc), wo möglich, eine kleine Menge von inline-assembly erforderlich ist. Bestimmte Teile des Codes hängt von der Bitanzahl, crc32q ist nicht auf 32 bits und ist weder movq, diese werden in makro - (crc32intel.h) mit alternativen code für 32-bit-Plattformen.
InformationsquelleAutor der Antwort Ferry Toth