CRC and Checksum Algorithms in Embedded C: A Practical Guide

Error detection is a fundamental requirement of robust embedded communication protocols. From UART frames to CAN bus messages, from SPI flash reads to Over-The-Air (OTA) firmware updates, uncorrected bit flips can cascade into critical system failures. Despite its importance, CRC implementation is frequently treated as a black box—often resulting in the blind integration of unverified polynomials and lookup tables without a rigorous understanding of the underlying mathematics.

This article dissects the mathematics behind error detection, compares algorithmic approaches, and provides production-ready C implementations optimized for resource-constrained targets.

The Mathematics of Error Detection

Error detection codes add redundancy to data so the receiver can detect corruption. The fundamental tradeoff is between detection capability and overhead (compute cycles, code size, bandwidth).

Checksums: Simple Arithmetic

The simplest approach treats data as a sequence of integers and computes a summary value.

// Internet checksum (RFC 1071) - 16-bit ones' complement sum
uint16_t internet_checksum(const uint8_t *data, size_t len) {
    uint32_t sum = 0;
    size_t i = 0;

    // Process 16-bit words
    while (len > 1) {
        sum += ((uint32_t)data[i] << 8) | data[i + 1];
        i += 2;
        len -= 2;
    }

    // Handle odd byte
    if (len == 1) {
        sum += (uint32_t)data[i] << 8;
    }

    // Fold carry bits back into lower 16 bits
    while (sum >> 16) {
        sum = (sum & 0xFFFF) + (sum >> 16);
    }

    return (uint16_t)~sum;  // Ones' complement
}

Strengths: Extremely fast, minimal code size, hardware-friendly. Weaknesses: Misses many error patterns (bit transpositions, compensated errors). Unsuitable for safety-critical links.

CRC: Polynomial Division over GF(2)

Cyclic Redundancy Check treats the message as a polynomial over GF(2) (coefficients 0 or 1, addition = XOR). The transmitter divides the message polynomial by a generator polynomial G(x) and appends the remainder. The receiver divides the received polynomial by G(x) — a zero remainder means no detected errors.

Message:     1101          (4 bits)
Append 0s:   11010000      (append degree(G) zeros, 4 zeros)
Divide by:   10011         (G(x) = x^4 + x + 1, degree 4)
Remainder:   0100          (4-bit CRC)
Transmitted: 11010100

The generator polynomial choice determines error detection properties. Standard polynomials are irreducible over GF(2) and have specific bit patterns.

// Standard CRC polynomials (reflected/reversed representation for bitwise algorithm)
#define CRC16_CCITT_POLY    0x8408   // x^16 + x^12 + x^5 + 1 (reflected 0x1021)
#define CRC16_IBM_POLY      0xA001   // x^16 + x^15 + x^2 + 1 (reflected 0x8005)
#define CRC32_POLY          0xEDB88320  // Reflected 0x04C11DB7

Why reflected polynomials? Bit-serial CRC processes LSB first (natural for UART shift registers). The reflected polynomial produces the same remainder as the non-reflected version when bits are processed in reverse order.

Algorithm Comparison

+------------------------+------------+-------------+--------------+------------------+
| Algorithm              | Detects    | Code Size   | Cycles/Byte  | Best For         |
+------------------------+------------+-------------+--------------+------------------+
| 8-bit sum              | Single-bit | ~50 bytes   | 2-3          | Quick sanity     |
| 16-bit Internet cksum  | Many 16-bit| ~80 bytes   | 3-4          | IP/UDP/TCP       |
| CRC-8 (0x07)           | Good burst | ~100 bytes  | 8-12         | 1-Wire, SMBus    |
| CRC-16-CCITT (table)   | Excellent  | ~600 bytes  | 4-5          | XModem, Bluetooth|
| CRC-32 (table)         | Near-perf  | ~1.5 KB     | 4-5          | Ethernet, ZIP    |
| CRC-32 (slice-by-8)    | Near-perf  | ~8 KB       | 1-2          | High-throughput  |
+------------------------+------------+-------------+--------------+------------------+

Table-driven CRC processes one byte per loop iteration with a single table lookup and XOR — optimal for software on byte-addressable architectures.

Production-Ready CRC-16-CCITT Implementation

#include <stdint.h>
#include <stddef.h>

/* CRC-16-CCITT (XModem) polynomial: 0x1021, initial: 0x0000, no reflection, no final XOR */
/* Reflected polynomial for bitwise LSB-first: 0x8408 */

static const uint16_t crc16_ccitt_table[256] = {
    0x0000, 0x1021, 0x2042, 0x3063, 0x4084, 0x50A5, 0x60C6, 0x70E7,
    0x8108, 0x9129, 0xA14A, 0xB16B, 0xC18C, 0xD1AD, 0xE1CE, 0xF1EF,
    0x1231, 0x0210, 0x3273, 0x2252, 0x52B5, 0x4294, 0x72F7, 0x62D6,
    0x9339, 0x8318, 0xB37B, 0xA35A, 0xD3BD, 0xC39C, 0xF3FF, 0xE3DE,
    /* ... 216 more entries generated by polynomial 0x1021 ... */
    0x6E17, 0x7E36, 0x4E55, 0x5E74, 0x2E93, 0x3EB2, 0x0ED1, 0x1EF0
};

uint16_t crc16_ccitt(const uint8_t *data, size_t length, uint16_t init) {
    uint16_t crc = init;
    for (size_t i = 0; i < length; i++) {
        crc = (crc << 8) ^ crc16_ccitt_table[((crc >> 8) ^ data[i]) & 0xFF];
    }
    return crc;
}

/* Usage for XModem (initial 0x0000) */
uint16_t crc16_xmodem(const uint8_t *data, size_t length) {
    return crc16_ccitt(data, length, 0x0000);
}

/* Usage for CCITT-FALSE (initial 0xFFFF) */
uint16_t crc16_ccitt_false(const uint8_t *data, size_t length) {
    return crc16_ccitt(data, length, 0xFFFF);
}

Generating the Lookup Table at Build Time

Lookup tables should not be manually copied from unverified sources. Instead, they should be generated dynamically within the build system to mathematically guarantee correctness:

# gen_crc_table.py
def generate_crc16_table(poly=0x1021, reflect=False):
    table = []
    if reflect:
        # Reflect polynomial for 16-bit LSB-first
        poly_use = 0
        for i in range(16):
            if (poly >> i) & 1:
                poly_use |= 1 << (15 - i)
    else:
        poly_use = poly

    for i in range(256):
        if reflect:
            crc = i
            for _ in range(8):
                crc = (crc >> 1) ^ poly_use if (crc & 1) else (crc >> 1)
        else:
            crc = i << 8
            for _ in range(8):
                crc = ((crc << 1) ^ poly_use) if (crc & 0x8000) else (crc << 1)
                crc &= 0xFFFF
        table.append(crc & 0xFFFF)
    return table

# CMake integration:
# add_custom_command(
#   OUTPUT ${CMAKE_CURRENT_BINARY_DIR}/crc16_table.h
#   COMMAND python3 ${CMAKE_CURRENT_SOURCE_DIR}/gen_crc_table.py
#   > ${CMAKE_CURRENT_BINARY_DIR}/crc16_table.h
#   DEPENDS ${CMAKE_CURRENT_SOURCE_DIR}/gen_crc_table.py
# )

// Generated crc16_table.h
static const uint16_t crc16_ccitt_table[256] = {
    0x0000, 0x1021, 0x2042, 0x3063, 0x4084, 0x50A5, 0x60C6, 0x70E7,
    0x8108, 0x9129, 0xA14A, 0xB16B, 0xC18C, 0xD1AD, 0xE1CE, 0xF1EF,
    0x1231, 0x0210, 0x3273, 0x2252, 0x52B5, 0x4294, 0x72F7, 0x62D6,
    0x9339, 0x8318, 0xB37B, 0xA35A, 0xD3BD, 0xC39C, 0xF3FF, 0xE3DE,
    // ... remaining 224 entries
};

CRC-32 for High-Throughput Links

Ethernet, ZIP, PNG, and many storage formats use CRC-32 (polynomial 0x04C11DB7). For high-speed links, slice-by-8 (or slice-by-4/16) processes multiple bytes per iteration using multiple lookup tables.

// CRC-32 slice-by-4: 4 tables, 4KB total, ~1.5 cycles/byte on Cortex-M4
static uint32_t crc32_table[4][256];

void crc32_init_sliceby4(void) {
    const uint32_t poly = 0xEDB88320;  // Reflected 0x04C11DB7
    for (int i = 0; i < 256; i++) {
        uint32_t crc = i;
        for (int j = 0; j < 8; j++) {
            crc = (crc >> 1) ^ (poly & -(crc & 1));
        }
        crc32_table[0][i] = crc;
    }
    // Build tables 1-3 by shifting table 0 (LSB-first / reflected)
    for (int i = 0; i < 256; i++) {
        uint32_t c = crc32_table[0][i];
        crc32_table[1][i] = crc32_table[0][c & 0xFF] ^ (c >> 8);
        c = crc32_table[1][i];
        crc32_table[2][i] = crc32_table[0][c & 0xFF] ^ (c >> 8);
        c = crc32_table[2][i];
        crc32_table[3][i] = crc32_table[0][c & 0xFF] ^ (c >> 8);
    }
}

uint32_t crc32_sliceby4(const uint8_t *data, size_t len, uint32_t crc) {
    crc = ~crc;
    while (len >= 4) {
        // Safe read to prevent strict-aliasing, alignment faults, and host-endianness bugs
        uint32_t word = (uint32_t)data[0] | 
                        ((uint32_t)data[1] << 8) | 
                        ((uint32_t)data[2] << 16) | 
                        ((uint32_t)data[3] << 24);
        crc ^= word;
        crc = crc32_table[3][crc & 0xFF] ^
              crc32_table[2][(crc >> 8) & 0xFF] ^
              crc32_table[1][(crc >> 16) & 0xFF] ^
              crc32_table[0][(crc >> 24) & 0xFF];
        data += 4;
        len -= 4;
    }
    while (len--) {
        crc = crc32_table[0][(crc ^ *data++) & 0xFF] ^ (crc >> 8);
    }
    return ~crc;
}

Memory vs. Speed Trade-off:

For most embedded targets, slice-by-4 hits the sweet spot.

Hardware CRC Peripherals

Modern MCUs include CRC computation units. STM32 example:

// STM32H7 CRC peripheral (polynomial configurable)
uint32_t crc32_hardware(const uint8_t *data, size_t len) {
    RCC->AHB4ENR |= RCC_AHB4ENR_CRCEN; // STM32H7 uses AHB4 for CRC
    // Configure hardware for bit-reversal (required for Ethernet CRC-32)
    CRC->CR = CRC_CR_RESET | CRC_CR_REV_IN | CRC_CR_REV_OUT; 
    CRC->INIT = 0xFFFFFFFF;  // Initial value
    CRC->POL = 0x04C11DB7;   // Polynomial 

    // Process 32-bit words (hardware handles bit reflection)
    size_t word_count = len / 4;
    for (size_t i = 0; i < word_count; i++) {
        uint32_t word = (uint32_t)data[i * 4] |
                        ((uint32_t)data[i * 4 + 1] << 8) |
                        ((uint32_t)data[i * 4 + 2] << 16) |
                        ((uint32_t)data[i * 4 + 3] << 24);
        CRC->DR = word;
    }
    // Handle remaining bytes
    for (size_t i = word_count * 4; i < len; i++) {
        *(volatile uint8_t *)&CRC->DR = data[i];
    }
    return ~CRC->DR;
}

Hardware CRC Caveats:

• Polynomial may not be fully configurable (some MCUs fix to CRC-32)
• Bit/byte reflection settings vary — verify against software reference
• DMA integration requires careful buffer alignment
• Not available on all MCU families (e.g., small Cortex-M0+)

Protocol Integration: Modbus RTU Example

Modbus RTU uses CRC-16-IBM (polynomial 0x8005, initial 0xFFFF, reflected).

// Modbus RTU frame: [Slave ID][Function Code][Data...][CRC Lo][CRC Hi]
bool modbus_rtu_verify(const uint8_t *frame, size_t len) {
    if (len < 4) return false;  // Min: ID + FC + 2-byte CRC

    uint16_t received_crc = (uint16_t)frame[len - 2] | ((uint16_t)frame[len - 1] << 8);
    uint16_t calc_crc = crc16_ibm(frame, len - 2, 0xFFFF);

    return received_crc == calc_crc;
}

void modbus_rtu_append_crc(uint8_t *frame, size_t *len) {
    uint16_t crc = crc16_ibm(frame, *len, 0xFFFF);
    frame[(*len)++] = crc & 0xFF;       // Low byte first (little-endian)
    frame[(*len)++] = (crc >> 8) & 0xFF;
}

Modbus RTU Frame with CRC

+--------+--------+----------------+--------+--------+
| Slave  | Func   | Data (N bytes) | CRC Lo | CRC Hi |
| ID     | Code   |                |        |        |
+--------+--------+----------------+--------+--------+
  1 byte   1 byte      N bytes         1 byte  1 byte
                                    (LSB)   (MSB)

Transmission order: Slave ID -> Func Code -> Data[0]...Data[N-1] -> CRC Lo -> CRC Hi
CRC calculation covers: Slave ID + Func Code + Data[0]...Data[N-1]
Polynomial: 0x8005 (x^16 + x^15 + x^2 + 1), reflected: 0xA001
Initial value: 0xFFFF, Final XOR: 0x0000, Reflected in/out: Yes

Common Pitfalls and Debugging

1. Polynomial Representation Confusion

Rule: Match the polynomial representation to your algorithm’s shift direction.

• LSB-first protocols (Modbus, Ethernet): Use the reflected polynomial (e.g., 0xA001) and shift right (crc >> 1 or crc >> 8).
• MSB-first protocols (XModem, CCITT-FALSE): Use the normal polynomial (e.g., 0x1021) and shift left (crc << 1 or crc << 8).

2. Initial Value and Final XOR Mismatches

// Kermit: init=0x0000, xorout=0x0000, reflect in/out
// CCITT-FALSE: init=0xFFFF, xorout=0x0000, NO reflection
// XModem: init=0x0000, xorout=0x0000, NO reflection
// Modbus: init=0xFFFF, xorout=0x0000, reflect in/out

Implementations must always be verified against known standard test vectors:

// CRC-16-CCITT (XModem) test vector: "123456789" -> 0x31C3
uint8_t test_data[] = "123456789";
uint16_t result = crc16_xmodem(test_data, 9);
assert(result == 0x31C3);  // Fails if reflection/init/xor wrong

3. Endianness in Multi-byte CRCs

CRC-16 is transmitted LSB-first (little-endian) for Modbus, but MSB-first for many other protocols. This must be documented explicitly in any protocol specification:

// Modbus RTU: CRC transmitted LOW byte first
frame[len++] = crc & 0xFF;
frame[len++] = crc >> 8;

// Some protocols (e.g., CRC-32 in PNG): MSB first
frame[len++] = crc >> 24;
frame[len++] = crc >> 16;
frame[len++] = crc >> 8;
frame[len++] = crc & 0xFF;

CRC Shift Register Operation (CRC-4 Example)

Polynomial: x^4 + x + 1  (Drops x^4 for 4-bit register -> XOR with 0011)

Message: 1101  (append 4 zeros) -> 11010000

Process: Shift left, bringing in message bits at the right. If MSB shifted out is 1, XOR with 0011.

Step 1: Input bit '1' -> Shift out '0'
        Register: [0][0][0][1]

Step 2: Input bit '1' -> Shift out '0'
        Register: [0][0][1][1]

Step 3: Input bit '0' -> Shift out '0'
        Register: [0][1][1][0]

Step 4: Input bit '1' -> Shift out '0'
        Register: [1][1][0][1]

Step 5: Input bit '0' -> Shift out '1' (MSB was 1!)
        Shifted:  [1][0][1][0]
        XOR poly: [0][0][1][1]
        Result:   [1][0][0][1]

Step 6: Input bit '0' -> Shift out '1' (MSB was 1!)
        Shifted:  [0][0][1][0]
        XOR poly: [0][0][1][1]
        Result:   [0][0][0][1]

Step 7: Input bit '0' -> Shift out '0'
        Register: [0][0][1][0]

Step 8: Input bit '0' -> Shift out '0'
        Register: [0][1][0][0]

Final register holds the 4-bit CRC: 0100 (0x4)
Transmitted: 1101 + 0100 -> 11010100

Performance Optimization Checklist

1. Utilize table-driven byte-wise CRC — Yields ~4-5 cycles/byte on ARM Cortex-M architectures.
2. Align buffers for 32-bit memory access — Enables optimized slice-by-4/8 algorithms.
3. Leverage hardware CRC peripherals with DMA — Offloads computation entirely, requiring zero CPU cycles for large data blocks.
4. Generate lookup tables at build time — Mathematically guarantees correctness and prevents manual transcription errors.
5. Verify implementations against standard test vectors — The ASCII string “123456789” is the universally accepted standard input for baseline validation.
6. Document polynomial, initial value, final XOR, and reflection — Prevents interoperability failures across diverse protocol stacks.

Summary

Error detection is not optional in embedded systems — it is the critical distinction between a detected communication fault and silent data corruption. CRC provides mathematically proven detection capabilities that are fundamentally superior to simple arithmetic checksums. Key conclusions:

• Adhere to standard polynomials to ensure interoperability (e.g., CRC-16-IBM for Modbus, CRC-16-CCITT for XModem, CRC-32 for Ethernet/storage).
• Table-driven byte-wise implementations offer the optimal balance of execution speed and memory footprint for software on 32-bit MCUs.
• Hardware CRC augmented with DMA eliminates CPU overhead, making it ideal for high-throughput data links.
• Empirically verify all algorithms against established test vectors and document all mathematical parameters explicitly.
• Generate lookup tables programmatically at build time to preclude manual transcription vulnerabilities.

Related Reading

• DMA Programming in Embedded C for High-Throughput Data Transfer
• Memory-Mapped I/O and Peripheral Register Access in Embedded C
• Fixing I2C Clock Stretching Timeouts on STM32

References

1. Williams, R. “A Painless Guide to CRC Error Detection Algorithms.” 1993. The definitive tutorial on CRC mathematics and implementation.
2. Koopman, P. “32-Bit Cyclic Redundancy Codes for Internet Applications.” IEEE, 2002. Polynomial selection criteria and optimal CRC-32 polynomials.
3. ISO 3309:1991. “Information technology — Telecommunications and information exchange between systems — High-level data link control (HDLC) procedures — Frame structure.” Standardizes CRC-16-CCITT (0x1021).
4. Modbus Organization. “Modbus over Serial Line Specification and Implementation Guide V1.02.” 2006. CRC-16-IBM specification for Modbus RTU.
5. STM32 Reference Manual RM0433. “Cyclic Redundancy Check Calculation Unit (CRC).” Hardware CRC peripheral configuration and polynomial programming.
6. Castagnoli, G., Bräuer, S., Herrmann, M. “Optimization of Cyclic Redundancy-Check Codes with 24 and 32 Parity Bits.” IEEE Transactions on Communications, 1993. Discovery of CRC-32C (Castagnoli) polynomial 0x1EDC6F41.