CRC-32-Prüfsumme
CRC-32 (Cyclic Redundancy Check, 32 Bit) ist eine Prüfsumme, mit der sich Übertragungs- und Speicherfehler erkennen lassen. Sie steckt in jedem PNG-Chunk, in jedem ZIP-Eintrag, in gzip und in Ethernet-Frames.
Die Idee stammt aus der Polynomdivision: Die Daten werden als ein riesiges Polynom über GF(2) (Rechnen modulo 2, also XOR) aufgefasst und durch ein festes Generatorpolynom geteilt. Der Rest dieser Division ist die CRC.
In der Praxis rechnet man nicht bitweise, sondern mit einer vorberechneten 256-Einträge-Tabelle byteweise — das ist deutlich schneller und liefert exakt dasselbe Ergebnis.
0xEDB88320 · Init 0xFFFFFFFF · End-XOR 0xFFFFFFFF⚙️ So funktioniert der Algorithmus
Startwert, byteweise Tabellen-Verknüpfung, abschließendes XOR.
Tabellengesteuerter CRC-32 (wie in PNG/ZIP):
crc = 0xFFFFFFFF ← Startwert
│
▼ für jedes Byte b:
┌─────────────────────────────────────────────┐
│ idx = (crc XOR b) AND 0xFF │
│ crc = table[idx] XOR (crc >> 8) │
└─────────────────────────────────────────────┘
│
▼
crc = crc XOR 0xFFFFFFFF ← End-XOR = Ergebnis
Tabellenaufbau (einmalig, pro Eintrag n):
c = n
8×: c = (c & 1) ? (0xEDB88320 ^ (c>>1)) : (c>>1)
table[n] = c🎬 Visuelles Beispiel
CRC-32 von "IEND" — Schritt für Schritt bis zum bekannten Wert AE426082:
CRC-32 verarbeitet die Bits LSB-first und verknüpft sie über die Lookup-Tabelle (vorberechnete Polynomdivision).
Kontrolle: crc32("IEND") = AE426082
Zweites Beispiel
Der Klassiker "123456789" → CBF43926:
CRC-32 verarbeitet die Bits LSB-first und verknüpft sie über die Lookup-Tabelle (vorberechnete Polynomdivision).
Kontrolle: crc32("123456789") = CBF43926
🧮 Woher kommt 0xEDB88320?
Der Wert 0xEDB88320 ist NICHT willkürlich: Er ist die bit-reflektierte Schreibweise des standardisierten CRC-32-Generatorpolynoms 0x04C11DB7. Dieses Polynom wurde 1975 für das ARPANET gewählt und später in IEEE 802.3 (Ethernet) festgeschrieben.
Als Polynom geschrieben lautet 0x04C11DB7: x³² + x²⁶ + x²³ + x²² + x¹⁶ + x¹² + x¹¹ + x¹⁰ + x⁸ + x⁷ + x⁵ + x⁴ + x² + x + 1. Es wurde so gewählt, dass es möglichst viele Fehlerarten (Einzelbit-, Doppelbit-, Bündelfehler) zuverlässig erkennt.
Weil PNG, ZIP & gzip die Bits LSB-first (reflektiert) verarbeiten, dreht man die Bitreihenfolge des Polynoms um — aus 0x04C11DB7 wird 0xEDB88320. Beide beschreiben dasselbe mathematische Polynom, nur in unterschiedlicher Leserichtung. (0x82608EDB ist die dritte gängige, „reversed reciprocal“ Schreibweise.)
In der Praxis gibt es viele CRC-32-Varianten mit ANDEREN Polynomen — sie sind nicht kompatibel zueinander:
Verbreitete CRC-32-Varianten (unterschiedliche Polynome!)
| Variante | Polynom (reflektiert) | Verwendung |
|---|---|---|
| CRC-32 (IEEE) | 0xEDB88320 | PNG, ZIP, gzip, Ethernet |
| CRC-32C (Castagnoli) | 0x82F63B78 | iSCSI, ext4, SSE4.2-Befehl |
| CRC-32K (Koopman) | 0xEB31D82E | fehlertolerante Systeme |
| CRC-32Q | 0xD5828281 | Luftfahrt (AIXM) |
📊 Referenzwerte & Parameter
Bekannte CRC-32-Werte (IEEE 802.3)
| Eingabe | CRC-32 (hex) |
|---|---|
| "" (leer) | 00000000 |
| "123456789" | CBF43926 |
| "IEND" | AE426082 |
| "The quick brown fox…lazy dog" | 414FA339 |
Parameter dieser CRC-Variante
| Parameter | Wert |
|---|---|
| Breite | 32 Bit |
| Polynom (normal) | 0x04C11DB7 |
| Polynom (reflektiert) | 0xEDB88320 |
| Init | 0xFFFFFFFF |
| Reflect In/Out | ja / ja |
| End-XOR | 0xFFFFFFFF |
⌨️ Implementierung in C
#include <stdint.h>
uint32_t crc_table[256];
void make_crc_table(void) {
for (uint32_t n = 0; n < 256; n++) {
uint32_t c = n;
for (int k = 0; k < 8; k++) {
/* bei gesetztem LSB mit dem Polynom XOR-en, dann schieben */
c = (c & 1) ? (0xEDB88320u ^ (c >> 1)) : (c >> 1);
}
crc_table[n] = c;
}
}ℹ️ Achtung auf das Polynom: 0xEDB88320 (reflektiert). Ein Tippfehler hier liefert falsche, aber plausibel aussehende Prüfsummen.
uint32_t crc32(const uint8_t *data, size_t len) {
uint32_t crc = 0xFFFFFFFFu; /* Init */
for (size_t i = 0; i < len; i++) {
uint8_t idx = (crc ^ data[i]) & 0xFF;
crc = crc_table[idx] ^ (crc >> 8);
}
return crc ^ 0xFFFFFFFFu; /* End-XOR */
}
/* Beispiel: crc32((const uint8_t*)"IEND", 4) == 0xAE426082 */ℹ️ Exakt dieser Algorithmus prüft die Integrität jedes PNG-Chunks und ZIP-Eintrags.
/* Prüft die CRC eines PNG-Chunks (Typ[4] + Daten[len]) */
int png_chunk_ok(const char type[4], const uint8_t *data,
size_t len, uint32_t stored_crc) {
uint32_t crc = 0xFFFFFFFFu;
for (int i = 0; i < 4; i++) /* zuerst der Typ */
crc = crc_table[(crc ^ type[i]) & 0xFF] ^ (crc >> 8);
for (size_t i = 0; i < len; i++) /* dann die Daten */
crc = crc_table[(crc ^ data[i]) & 0xFF] ^ (crc >> 8);
crc ^= 0xFFFFFFFFu;
return crc == stored_crc; /* gültig? */
}ℹ️ Die CRC läuft über Typ + Daten — NICHT über das Längenfeld.