C: the CRC-32 frame check sequence

Compute the cyclic redundancy check used by Ethernet and detect a single flipped bit.

#include <stdint.h>
#include <stdio.h>
#include <string.h>

static uint32_t crc32(const unsigned char *data, size_t n) {
  uint32_t crc = 0xFFFFFFFFu;
  for (size_t i = 0; i < n; i++) {
    crc ^= data[i];
    for (int k = 0; k < 8; k++) {
      crc = (crc >> 1) ^ (0xEDB88320u & (0u - (crc & 1u)));
    }
  }
  return ~crc;
}

int main(void) {
  unsigned char frame[] = "123456789";
  size_t n = strlen((const char *)frame);
  printf("crc32 = %08X\n", (unsigned)crc32(frame, n));

  frame[3] ^= 0x01;
  printf("after one flipped bit = %08X\n", (unsigned)crc32(frame, n));
  return 0;
}

Output

crc32 = CBF43926
after one flipped bit = 00A8EA83

Explanation

A cyclic redundancy check (CRC) treats the message as a very long binary number and takes the remainder after division by a fixed polynomial. Link layers such as Ethernet append a CRC-32 to every frame, and the receiver recomputes it. Any single-bit error, and most bursts of errors, change the result.

The bitwise version starts with all ones, XORs each byte into the low bits, and then shifts one bit at a time. If the lowest bit is 1 it XORs the shifted value with the reflected polynomial 0xEDB88320. The final value is complemented. For the standard test text 123456789 the CRC-32 is CBF43926.

Explore the dry run

Guided walkthroughReady

1#include <stdint.h>

2#include <stdio.h>

3#include <string.h>

5static uint32_t crc32(const unsigned char *data, size_t n) {

6 uint32_t crc = 0xFFFFFFFFu;

7 for (size_t i = 0; i < n; i++) {

8 crc ^= data[i];

9 for (int k = 0; k < 8; k++) {

10 crc = (crc >> 1) ^ (0xEDB88320u & (0u - (crc & 1u)));

11 }

12 }

13 return ~crc;

14}

16int main(void) {

17 unsigned char frame[] = "123456789";

18 size_t n = strlen((const char *)frame);

19 printf("crc32 = %08X\n", (unsigned)crc32(frame, n));

21 frame[3] ^= 0x01;

22 printf("after one flipped bit = %08X\n", (unsigned)crc32(frame, n));

23 return 0;

24}

Follow the example

Start to inspect the source, values, and output. These prepared steps explain the published sample; grouped loop steps describe multiple iterations.

View the complete dry-run table

Prepared trace of the published program. Some rows group repeated iterations.
What happens	State after step	Output so far
Start with all ones so that leading zero bytes still affect the result.	`—`	—
Shift right; if the bit shifted out was 1, XOR with the polynomial. The expression 0u - (crc & 1u) is all ones or all zeros, so no branch is needed.	`—`	—
This matches the published check value for 123456789.	`—`	crc32 = CBF43926
Flip one bit of the fourth character.	`—`	crc32 = CBF43926
The CRC changes, so the receiver would detect the corruption.	`—`	crc32 = CBF43926 after one flipped bit = 00A8EA83

Cost and common mistakes

O(n) time for n bytes, with 8 steps per byte in this version.

A CRC detects accidental errors but is not secure. An attacker can change a message and fix the CRC. Use a keyed MAC for security.
Different CRC-32 variants use different initial values, polynomials, and final steps. Make sure both ends use the same one.
Table-driven implementations process a byte at a time and are much faster than this bitwise version.

Try it yourself

Why does the receiver recompute the CRC instead of comparing messages?

Reveal answer and reasoning

The receiver has no second copy of the message to compare with. It checks that the received data is consistent with the CRC that arrived with it.

C: the CRC-32 frame check sequence

Explanation

Follow the example

Cost and common mistakes

Try it yourself

Further reading