</>EmbeddedInterview

How do you compute a CRC and why is it used?

MediumData Structures & Algorithms

Short answer: A Cyclic Redundancy Check treats the data as a polynomial over GF(2), divides it by a fixed generator polynomial, and uses the remainder as the check value. It is very good at detecting accidental errors, including all single-bit errors, all bursts shorter than the CRC width, and most other patterns, so it is used in Ethernet, CAN, USB, storage, flash images and serial protocols. Bitwise implementations are tiny; table-driven implementations process a byte per lookup; many MCUs have a hardware CRC unit.

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

uint8_t crc8(const uint8_t *d, size_t n)              /* CRC-8, poly 0x07, init 0 (SMBus PEC) */
{
    uint8_t crc = 0;
    while (n--) {
        crc ^= *d++;
        for (int i = 0; i < 8; i++)
            crc = (crc & 0x80) ? (uint8_t)((crc << 1) ^ 0x07) : (uint8_t)(crc << 1);
    }
    return crc;
}

uint16_t crc16_modbus(const uint8_t *d, size_t n)     /* reflected poly 0xA001, init 0xFFFF */
{
    uint16_t crc = 0xFFFF;
    while (n--) {
        crc ^= *d++;
        for (int i = 0; i < 8; i++)
            crc = (crc & 1) ? (uint16_t)((crc >> 1) ^ 0xA001) : (uint16_t)(crc >> 1);
    }
    return crc;
}

uint32_t crc32(const uint8_t *d, size_t n)            /* IEEE 802.3 (zlib), reflected 0xEDB88320 */
{
    uint32_t crc = 0xFFFFFFFFu;
    while (n--) {
        crc ^= *d++;
        for (int i = 0; i < 8; i++) crc = (crc >> 1) ^ (0xEDB88320u & (0u - (crc & 1u)));
    }
    return ~crc;
}

int main(void)
{
    const uint8_t s[] = "123456789";                  /* standard check string */
    printf("%02X %04X %08X\n", crc8(s, 9), crc16_modbus(s, 9), crc32(s, 9));   /* F4 4B37 CBF43926 */
    return 0;
}

Parameters that define a CRC: width, polynomial, initial value, input/output reflection and final XOR. Two "CRC-16" implementations with different parameters give different results, so always check against the standard check value for "123456789".

CRC vs checksum vs hash vs MAC

Detects Protects against tampering
Sum / XOR checksum some errors, weak no
CRC accidental errors, strong for bursts no (easy to forge)
Cryptographic hash (SHA-256) any change only if the hash itself is protected
MAC / signature (HMAC, ECDSA) any change yes

Embedded uses: image integrity in bootloaders (CRC32 for corruption, a signature for authenticity), configuration blocks in flash, and frame checks in UART protocols.