CRC-32 Checksum (C)
Topics: bit manipulation, checksums, polynomials
Problem
Implement CRC-32 (the IEEE 802.3 / zlib variant) over a byte buffer.
uint32_t crc32(const unsigned char *data, size_t len);
This is the exact checksum used by gzip, PNG, ZIP, and Ethernet frames, so a
correct implementation matches their well-known values.
How it works
CRC treats the message as a big binary polynomial and returns the remainder after
dividing by a fixed generator polynomial, using XOR for the arithmetic. The
practical bitwise recipe:
- Start a 32-bit register at
0xFFFFFFFF.
- For each byte, XOR it into the low byte of the register, then repeat 8 times:
shift the register right by one, and if the bit shifted out was set, XOR with the
reversed polynomial
0xEDB88320.
- After all bytes, return the bitwise-NOT of the register.
crc ^= data[i];
for (int j = 0; j < 8; j++)
crc = (crc >> 1) ^ (0xEDB88320u & -(crc & 1u));
The -(crc & 1u) idiom is the bit trick worth noticing: it is 0xFFFFFFFF when the
low bit is set and 0 otherwise, so it conditionally XORs the polynomial with no
branch.
Check your work
The canonical CRC-32 check value is crc32("123456789") == 0xCBF43926. The empty
input is 0, and a single changed byte must change the result.
Run
cc -std=c11 -O2 -Wall tests.c -o /tmp/crc32 && /tmp/crc32
Sign in to submit your solution.