C CRC 계산 구현

CRC(Cyclic Redundancy Check)는 데이터 전송 오류를 검출하는 방법이다. 데이터를 다항식으로 나눈 나머지를 체크섬으로 사용한다. 단순 체크섬보다 오류 검출 능력이 훨씬 높다.

원리

데이터를 이진수로 보고, 생성 다항식(generator polynomial)으로 나눈다. 나눗셈은 일반 나눗셈이 아니라 XOR 기반이다.

데이터:    1101011011
다항식:   10011 (x^4 + x + 1, CRC-4)
───────────────────────
데이터 뒤에 0000(4비트) 추가: 11010110110000

XOR 나눗셈 수행 → 나머지: 1110
이 1110이 CRC 값이다.

수신 측은 데이터 + CRC를 동일한 다항식으로 나눈다. 나머지가 0이면 오류 없음.

Bit-by-bit 구현 (CRC-16)

#define CRC16_POLY  0x8005
#define CRC16_INIT  0xFFFF

uint16_t crc16_bitwise(const uint8_t *data, uint32_t len) {
    uint16_t crc = CRC16_INIT;

    for (uint32_t i = 0; i < len; i++) {
        crc ^= (uint16_t)data[i] << 8;

        for (int bit = 0; bit < 8; bit++) {
            if (crc & 0x8000) {
                crc = (crc << 1) ^ CRC16_POLY;
            } else {
                crc = crc << 1;
            }
        }
    }
    return crc;
}

바이트마다 8번 비트 시프트를 수행한다. 메모리 사용은 최소지만 느리다.

Lookup Table 구현 (CRC-16)

256개 엔트리의 테이블을 미리 계산하면, 바이트 단위로 한 번에 처리할 수 있다.

테이블 생성

static uint16_t crc16_table[256];

void crc16_init_table(void) {
    for (int i = 0; i < 256; i++) {
        uint16_t crc = (uint16_t)i << 8;
        for (int bit = 0; bit < 8; bit++) {
            if (crc & 0x8000)
                crc = (crc << 1) ^ CRC16_POLY;
            else
                crc = crc << 1;
        }
        crc16_table[i] = crc;
    }
}

테이블 기반 계산

uint16_t crc16_table_calc(const uint8_t *data, uint32_t len) {
    uint16_t crc = CRC16_INIT;

    for (uint32_t i = 0; i < len; i++) {
        uint8_t idx = (crc >> 8) ^ data[i];
        crc = (crc << 8) ^ crc16_table[idx];
    }
    return crc;
}

바이트당 테이블 lookup 1회 + XOR 1회. Bit-by-bit 대비 약 5배 빠르다.

	Bit-by-bit	Lookup table
속도	느림 (바이트당 8회 분기)	빠름 (바이트당 1회 lookup)
메모리	0	CRC-16: 512B, CRC-32: 1KB
적합 환경	RAM 극소 MCU	RAM 여유 있는 시스템

CRC-8 구현

#define CRC8_POLY  0x07  // x^8 + x^2 + x + 1

uint8_t crc8(const uint8_t *data, uint32_t len) {
    uint8_t crc = 0x00;

    for (uint32_t i = 0; i < len; i++) {
        crc ^= data[i];
        for (int bit = 0; bit < 8; bit++) {
            if (crc & 0x80)
                crc = (crc << 1) ^ CRC8_POLY;
            else
                crc = crc << 1;
        }
    }
    return crc;
}

테이블은 256바이트면 된다. 간단한 센서 프로토콜에 적합하다.

CRC-32 구현 (Ethernet)

#define CRC32_POLY  0xEDB88320  // reflected polynomial

static uint32_t crc32_table[256];

void crc32_init_table(void) {
    for (int i = 0; i < 256; i++) {
        uint32_t crc = i;
        for (int bit = 0; bit < 8; bit++) {
            if (crc & 1)
                crc = (crc >> 1) ^ CRC32_POLY;
            else
                crc = crc >> 1;
        }
        crc32_table[i] = crc;
    }
}

uint32_t crc32(const uint8_t *data, uint32_t len) {
    uint32_t crc = 0xFFFFFFFF;

    for (uint32_t i = 0; i < len; i++) {
        uint8_t idx = (crc ^ data[i]) & 0xFF;
        crc = (crc >> 8) ^ crc32_table[idx];
    }
    return crc ^ 0xFFFFFFFF;  // final XOR
}

CRC-32는 reflected 방식이다. 비트를 LSB부터 처리하므로 시프트 방향이 오른쪽이다. 다항식도 reflected 형태(0xEDB88320)를 사용한다.

CRC 파라미터

같은 “CRC-16”이라도 파라미터에 따라 결과가 완전히 다르다.

파라미터	설명
Polynomial	생성 다항식
Init	CRC 레지스터 초기값
RefIn	입력 바이트를 비트 반전할지 (reflected)
RefOut	최종 CRC를 비트 반전할지
XorOut	최종 CRC에 XOR할 값

주요 변형

이름	Poly	Init	RefIn	RefOut	XorOut	용도
CRC-8-CCITT	0x07	0x00	No	No	0x00	SMBus
CRC-16-CCITT	0x1021	0xFFFF	No	No	0x0000	X.25, BLE
CRC-16-Modbus	0x8005	0xFFFF	Yes	Yes	0x0000	Modbus RTU
CRC-32	0x04C11DB7	0xFFFFFFFF	Yes	Yes	0xFFFFFFFF	Ethernet, ZIP

RefIn/RefOut = Yes이면 reflected 구현을 사용한다 (시프트 방향이 반대).

Reflected(LSB-first) vs Normal(MSB-first)

// Normal (MSB-first): CRC-16-CCITT
// 시프트 왼쪽, MSB 검사
if (crc & 0x8000)
    crc = (crc << 1) ^ 0x1021;

// Reflected (LSB-first): CRC-16-Modbus
// 시프트 오른쪽, LSB 검사
if (crc & 0x0001)
    crc = (crc >> 1) ^ 0xA001;  // 0x8005의 reflected

Modbus의 0xA001은 0x8005의 비트를 뒤집은 값이다. Reflected 방식은 UART처럼 LSB를 먼저 전송하는 인터페이스에서 자연스럽다.

하드웨어 CRC

STM32 등 많은 MCU가 CRC 하드웨어 유닛을 내장한다.

// STM32 HAL
__HAL_RCC_CRC_CLK_ENABLE();

CRC_HandleTypeDef hcrc = {
    .Instance = CRC,
    .Init.DefaultPolynomialUse = DEFAULT_POLYNOMIAL_ENABLE,  // CRC-32
};
HAL_CRC_Init(&hcrc);

uint32_t result = HAL_CRC_Calculate(&hcrc, (uint32_t *)data, len);

소프트웨어 대비 수십 배 빠르다. 단, 기본 다항식(CRC-32 Ethernet)만 지원하는 모델이 많다. 커스텀 다항식이 필요하면 확인이 필요하다.

메모

테이블을 const로 선언하면 flash에 배치된다. 런타임 초기화가 불필요하고 RAM을 소비하지 않는다. 단 테이블을 코드에 하드코딩해야 한다
CRC는 오류 검출이지 정정이 아니다. 오류가 발견되면 재전송을 요청해야 한다
CRC-16은 16비트 미만의 버스트 오류를 100% 검출한다. 랜덤 오류의 미검출 확률은 1/65536이다
data = "123456789"에 대한 CRC 결과가 표준 check value와 일치하는지 확인하는 것이 가장 확실한 검증 방법이다. CRC-32의 check value는 0xCBF43926이다
프로토콜 문서에서 CRC 파라미터(Init, RefIn, RefOut, XorOut)를 정확히 확인해야 한다. 한 파라미터라도 다르면 전혀 다른 결과가 나온다