CRC Bitwise

What Is CRC and Why Does It Use Bitwise Operations?

A CRC (Cyclic Redundancy Check) treats a block of data as a giant binary number and performs polynomial division on it. The remainder of that division is the CRC checksum. What makes CRC fascinating from a bitwise perspective is that the entire division operation is implemented using only XOR and shift — no actual division hardware needed. I wrote my first CRC implementation in C after reading the PNG specification, and watching those 32 XOR-and-shift operations produce the same result as zlib was one of those "aha" moments.

CRC is fundamentally different from a simple checksum. While a XOR checksum is just a parity calculation across all bytes, CRC performs a rigorously defined mathematical operation that guarantees detection of all burst errors up to the polynomial length. CRC-32, used in Ethernet, PNG, ZIP, and countless other formats, detects 100% of burst errors up to 32 bits long.

When debugging a serial communication protocol, I manually computed the CRC of a test packet by tracing through the polynomial division. The exercise reinforced why CRC is preferred over simple checksums for detecting burst errors in noisy communication channels.

Polynomial Division in Binary (GF(2))

CRC operates in what mathematicians call GF(2) — the Galois Field with two elements. In this field, addition and subtraction are the same operation: XOR. There is no carry in addition and no borrow in subtraction. This is why CRC polynomial division is implemented entirely with XOR gates in hardware and XOR operations in software.

The polynomial is the key. Every CRC standard defines a specific polynomial. CRC-32 uses 0x04C11DB7 (which represents x^32 + x^26 + x^23 + ... + 1). The degree of the polynomial determines the width of the CRC — a degree-N polynomial produces an N-bit checksum.

CRC-32: The Bit-Level Implementation

Here is what a raw, bit-by-bit CRC-32 computation looks like. This processes each bit individually and is straightforward to understand even if it is not the fastest approach.

// Bit-by-bit CRC-32 (straightforward but slow)
uint32_t crc32_bitwise(const uint8_t *data, size_t len) {
    uint32_t crc = 0xFFFFFFFF;  // Initial value (all 1s)
    const uint32_t poly = 0xEDB88320;  // Reflected CRC-32 polynomial

    for (size_t i = 0; i < len; i++) {
        crc ^= data[i];  // XOR next byte into the CRC register
        for (int bit = 0; bit < 8; bit++) {
            if (crc & 1) {
                crc = (crc >> 1) ^ poly;  // LSB is 1: shift and XOR polynomial
            } else {
                crc >>= 1;  // LSB is 0: just shift
            }
        }
    }
    return crc ^ 0xFFFFFFFF;  // Final XOR (all 1s)
}

Each byte requires 8 iterations of the inner loop. For a megabyte of data, that is 8 million iterations. This works, but it is not fast enough for network interfaces that run at gigabits per second.

The Lookup Table Optimization

The standard optimization precomputes the CRC result for all 256 possible byte values in a table. Instead of 8 inner-loop iterations per byte, the table method processes one byte per iteration with a single XOR and table lookup. This is how zlib, PNG, and Ethernet implement CRC-32.

// Table-driven CRC-32 (standard optimization)
uint32_t crc32_table[256];

void crc32_init_table(void) {
    for (uint32_t i = 0; i < 256; i++) {
        uint32_t crc = i;
        for (int j = 0; j < 8; j++) {
            crc = (crc & 1) ? ((crc >> 1) ^ 0xEDB88320) : (crc >> 1);
        }
        crc32_table[i] = crc;
    }
}

uint32_t crc32_table_driven(const uint8_t *data, size_t len) {
    uint32_t crc = 0xFFFFFFFF;
    for (size_t i = 0; i < len; i++) {
        uint8_t index = (crc ^ data[i]) & 0xFF;
        crc = (crc >> 8) ^ crc32_table[index];
    }
    return crc ^ 0xFFFFFFFF;
}

The table approach runs about 8 times faster than the bit-by-bit method. Hardware CRC implementations go even further, processing 32 or 64 bits per clock cycle using specialized XOR trees. Every modern CPU has a CRC instruction (SSE 4.2's CRC32 on x86, or the CRC extension on ARM).

Common CRC Polynomials

Different standards use different polynomials. Each polynomial gives different error-detection properties. Here are the most widely used ones:

CRC-32C is worth special mention. It uses a different polynomial that is faster to compute in hardware and has slightly better error-detection properties for long data streams. Google uses CRC-32C extensively in its filesystems and networking stack.

How CRC Detects Errors

When the receiver computes the CRC of the received data (including the appended CRC), a perfect transmission produces a CRC of zero. Any non-zero result means corruption occurred. Here is what CRC-32 guarantees:

• All single-bit errors — any single flipped bit changes the remainder
• All two-bit errors — as long as the data is within 2^32 - 1 bits long
• All burst errors up to 32 bits — any contiguous run of up to 32 corrupted bits is always detected
• 99.99999998% of longer burst errors — only 1 in 2^32 random error patterns produces a false match

This is dramatically better than simple parity or XOR checksums, which is why CRC is the standard for Ethernet frames, hard drive sectors, and file compression formats.