CRC-32

 

 

CRC (Cyclic Redundancy Check) 는 데이터 전송 과정에서 오류를 검출하거나 파일의 무결성을 검증하기 위한 방법으로, 그 과정에서 여러 종류의 다항식이 쓰일 수 있는 데 가장 널리 사용되는 CRC 다항식은 CRC-16-CCITT와 CRC-32이다.

 

CRC 다항식 종류 : https://en.wikipedia.org/wiki/Cyclic_redundancy_check

 

 

 

그 중 CRC-32의 다항식(Polynomial)은 아래와 같다.

이 다항식을 16진수로 표현한게 0x04C11DB7이고, reverse한 값이 0xEDB88320이다.

 

다항식을 16진수로 표현하는 방법은 먼저 x의 차수에 해당하는 비트에 1을 쓴다. 나머지 비트는 0으로 한다.

그럼 바이너리로 아래처럼 되는데 이걸 31번째 비트부터 읽은게 Normal Poly인 0x04C11DB7이고, 0번째 비트부터 거꾸로 읽으면 Reverse Poly 0xEDB88320이다.

 

 

 

대부분의 CRC32 SW 구현에서는 리버스 폴리인 0xEDB88320을 사용한다. 그 이유는 CRC32 표준이 RefIn = True, RefOut = True 조건으로 입력 데이터와 출력 데이터의 비트 순서를 반전 처리해야 하는데, 리버스 폴리인 0xEDB88320를 사용하면 별도로 비트 순서를 반전하지 않아도 동일한 효과를 주기 때문이다.

 

 

 

 

 

 

 

 

CRC-32 함수

 

uint32_t crc32(const uint8_t* data, size_t length) {
    uint32_t crc = 0xFFFFFFFF;
    const uint8_t* p;

    for (size_t i = 0; i < length; i++) {
        p = data + i;
        crc ^= *p;

        for (int j = 0; j < 8; j++) {
            if (crc & 1) {
                crc = (crc >> 1) ^ 0xEDB88320;
            }
            else {
                crc = crc >> 1;
            }
        }
    }

    return crc ^ 0xFFFFFFFF;
}

 

 

위 함수에서 CRC 계산시 초기값인 CRC Seed는 0xFFFFFFFF이고 이는 표준에서 사용되는 일반적인 CRC Seed 값인데, 가끔 파라미터로 Seed를 받아서 계산하는 경우도 존재한다. 한편 리턴시 Final XOR 값 또한 0xFFFFFFFF이고 이 역시 대부분의 표준 CRC-32에서 사용하는 이다.

 

 

 

아무튼 문자열 "123456789"의 CRC-32 Result는 0xCBF43926 이 나온다.

 

int main() {

	uint8_t test_data[] = "123456789";
	uint32_t crc = crc32(test_data, sizeof(test_data) - 1);

	printf("0x%08X\n", crc);
	return 0;
}

 

 

 

 

 

 

 

 

 

좀 더 빠르게 CRC-32 계산하는 방법

 

CRC 다항식의 모든 가능한 입력 비트에 대한 결과를 미리 계산하여 CRC Table을 생성해 두고, CRC를 계산하는 동안 테이블에 저장된 값을 참조하여 계산을 수행하면 더 빠른 속도로 계산할 수 있다.

 

static uint32_t crc32_tab[] =
{
    0x00000000L, 0x77073096L, 0xee0e612cL, 0x990951baL, 0x076dc419L,
    0x706af48fL, 0xe963a535L, 0x9e6495a3L, 0x0edb8832L, 0x79dcb8a4L,
    0xe0d5e91eL, 0x97d2d988L, 0x09b64c2bL, 0x7eb17cbdL, 0xe7b82d07L,
    0x90bf1d91L, 0x1db71064L, 0x6ab020f2L, 0xf3b97148L, 0x84be41deL,
    0x1adad47dL, 0x6ddde4ebL, 0xf4d4b551L, 0x83d385c7L, 0x136c9856L,
    0x646ba8c0L, 0xfd62f97aL, 0x8a65c9ecL, 0x14015c4fL, 0x63066cd9L,
    0xfa0f3d63L, 0x8d080df5L, 0x3b6e20c8L, 0x4c69105eL, 0xd56041e4L,
    0xa2677172L, 0x3c03e4d1L, 0x4b04d447L, 0xd20d85fdL, 0xa50ab56bL,
    0x35b5a8faL, 0x42b2986cL, 0xdbbbc9d6L, 0xacbcf940L, 0x32d86ce3L,
    0x45df5c75L, 0xdcd60dcfL, 0xabd13d59L, 0x26d930acL, 0x51de003aL,
    0xc8d75180L, 0xbfd06116L, 0x21b4f4b5L, 0x56b3c423L, 0xcfba9599L,
    0xb8bda50fL, 0x2802b89eL, 0x5f058808L, 0xc60cd9b2L, 0xb10be924L,
    0x2f6f7c87L, 0x58684c11L, 0xc1611dabL, 0xb6662d3dL, 0x76dc4190L,
    0x01db7106L, 0x98d220bcL, 0xefd5102aL, 0x71b18589L, 0x06b6b51fL,
    0x9fbfe4a5L, 0xe8b8d433L, 0x7807c9a2L, 0x0f00f934L, 0x9609a88eL,
    0xe10e9818L, 0x7f6a0dbbL, 0x086d3d2dL, 0x91646c97L, 0xe6635c01L,
    0x6b6b51f4L, 0x1c6c6162L, 0x856530d8L, 0xf262004eL, 0x6c0695edL,
    0x1b01a57bL, 0x8208f4c1L, 0xf50fc457L, 0x65b0d9c6L, 0x12b7e950L,
    0x8bbeb8eaL, 0xfcb9887cL, 0x62dd1ddfL, 0x15da2d49L, 0x8cd37cf3L,
    0xfbd44c65L, 0x4db26158L, 0x3ab551ceL, 0xa3bc0074L, 0xd4bb30e2L,
    0x4adfa541L, 0x3dd895d7L, 0xa4d1c46dL, 0xd3d6f4fbL, 0x4369e96aL,
    0x346ed9fcL, 0xad678846L, 0xda60b8d0L, 0x44042d73L, 0x33031de5L,
    0xaa0a4c5fL, 0xdd0d7cc9L, 0x5005713cL, 0x270241aaL, 0xbe0b1010L,
    0xc90c2086L, 0x5768b525L, 0x206f85b3L, 0xb966d409L, 0xce61e49fL,
    0x5edef90eL, 0x29d9c998L, 0xb0d09822L, 0xc7d7a8b4L, 0x59b33d17L,
    0x2eb40d81L, 0xb7bd5c3bL, 0xc0ba6cadL, 0xedb88320L, 0x9abfb3b6L,
    0x03b6e20cL, 0x74b1d29aL, 0xead54739L, 0x9dd277afL, 0x04db2615L,
    0x73dc1683L, 0xe3630b12L, 0x94643b84L, 0x0d6d6a3eL, 0x7a6a5aa8L,
    0xe40ecf0bL, 0x9309ff9dL, 0x0a00ae27L, 0x7d079eb1L, 0xf00f9344L,
    0x8708a3d2L, 0x1e01f268L, 0x6906c2feL, 0xf762575dL, 0x806567cbL,
    0x196c3671L, 0x6e6b06e7L, 0xfed41b76L, 0x89d32be0L, 0x10da7a5aL,
    0x67dd4accL, 0xf9b9df6fL, 0x8ebeeff9L, 0x17b7be43L, 0x60b08ed5L,
    0xd6d6a3e8L, 0xa1d1937eL, 0x38d8c2c4L, 0x4fdff252L, 0xd1bb67f1L,
    0xa6bc5767L, 0x3fb506ddL, 0x48b2364bL, 0xd80d2bdaL, 0xaf0a1b4cL,
    0x36034af6L, 0x41047a60L, 0xdf60efc3L, 0xa867df55L, 0x316e8eefL,
    0x4669be79L, 0xcb61b38cL, 0xbc66831aL, 0x256fd2a0L, 0x5268e236L,
    0xcc0c7795L, 0xbb0b4703L, 0x220216b9L, 0x5505262fL, 0xc5ba3bbeL,
    0xb2bd0b28L, 0x2bb45a92L, 0x5cb36a04L, 0xc2d7ffa7L, 0xb5d0cf31L,
    0x2cd99e8bL, 0x5bdeae1dL, 0x9b64c2b0L, 0xec63f226L, 0x756aa39cL,
    0x026d930aL, 0x9c0906a9L, 0xeb0e363fL, 0x72076785L, 0x05005713L,
    0x95bf4a82L, 0xe2b87a14L, 0x7bb12baeL, 0x0cb61b38L, 0x92d28e9bL,
    0xe5d5be0dL, 0x7cdcefb7L, 0x0bdbdf21L, 0x86d3d2d4L, 0xf1d4e242L,
    0x68ddb3f8L, 0x1fda836eL, 0x81be16cdL, 0xf6b9265bL, 0x6fb077e1L,
    0x18b74777L, 0x88085ae6L, 0xff0f6a70L, 0x66063bcaL, 0x11010b5cL,
    0x8f659effL, 0xf862ae69L, 0x616bffd3L, 0x166ccf45L, 0xa00ae278L,
    0xd70dd2eeL, 0x4e048354L, 0x3903b3c2L, 0xa7672661L, 0xd06016f7L,
    0x4969474dL, 0x3e6e77dbL, 0xaed16a4aL, 0xd9d65adcL, 0x40df0b66L,
    0x37d83bf0L, 0xa9bcae53L, 0xdebb9ec5L, 0x47b2cf7fL, 0x30b5ffe9L,
    0xbdbdf21cL, 0xcabac28aL, 0x53b39330L, 0x24b4a3a6L, 0xbad03605L,
    0xcdd70693L, 0x54de5729L, 0x23d967bfL, 0xb3667a2eL, 0xc4614ab8L,
    0x5d681b02L, 0x2a6f2b94L, 0xb40bbe37L, 0xc30c8ea1L, 0x5a05df1bL,
    0x2d02ef8dL
};

uint32_t crc32(const char* s, int len)
{
    int i;
    uint32_t crc32val = 0;
    crc32val ^= 0xFFFFFFFF;

    for (i = 0; i < len; i++) {
        crc32val = crc32_tab[(crc32val ^ s[i]) & 0xFF] ^ ((crc32val >> 8) & 0x00FFFFFF);
    }

    return crc32val ^ 0xFFFFFFFF;
}

 

 

 

 

0x01020304의 CRC-32 결과는 0xB63CFBCD이다.

 

int main() {

    uint8_t data[] = {0x01, 0x02, 0x03, 0x04};
    uint32_t crc = crc32(data, 4);

    printf("0x%08X\n", crc);
    return 0;
}

 

 

 

 

 

동일한 128KB 파일을 가지고 1번 bitwise 방법, 2번 lookup table 방법을 각각 사용하여 비교해 보았는데 2번 방법이 256 * 4 bytes의 메모리를 추가로 사용한다는 단점이 있긴 하지만 연산 속도는 4배 이상 빨랐다.

 

 

그리고 SW 구현에 비해 훨씬 빠르게 CRC 연산을 수행할 수 있는 것이 하드웨어 CRC 모듈이다. 하드웨어 CRC 모듈은 로직 회로를 통해 병렬 연산 방식으로 CRC를 빠르게 계산하는데 많은 MCU들이 이를 내장하고 있다. 다만 사용상에 제약사항이 존재하는데.. CRC 알고리즘 자체는 데이터의 길이에 상관없이 사용될 수 있지만 하드웨어 CRC 모듈은 보통 연산 최적화를 위해 CRC32의 경우 32비트의 단위로, CRC16의 경우 16비트 단위로 정렬된 데이터를 요구한다. 따라서 정렬되지 않은 데이터를 하드웨어 CRC 모듈로 처리할 때는 패딩 전처리가 필요할 수 있다.