C++::CRC-16 계산 알고리즘 구현 (소스코드)

 

CRC-16 Calculation Algorithm Source Code in C/C++

 

low-level network 인터페이스를 구현하는 회사 업무 중 송/수신 패킷의 CRC 계산 및 검증을 임베디드 HW단에서 구현해야 하는 이슈가 있어서 직접 C++로 구현해봤다

(회사에서 자체 제작한 보드들간에 통신하는 방식이라 오류 검증은 심플하게 CRC 사용하기로 결정)

 

본 포스트에서는 CRC-16에 대해서만 구현한 결과를 다루고 있으며, CRC-8이나 CRC-32 구현은 다른 글에서 다루도록 한다 (사실 코어 알고리즘은 크게 변동이 없어서 쓸만한 거리도 없겠지만...)

 

CRC(cyclic redundancy check)에 대한 소개는 위키백과를 참고하도록 한다

순환 중복 검사(巡環重復檢査), CRC(cyclic redundancy check)는 네트워크 등을 통하여 데이터를 전송할 때 전송된 데이터에 오류가 있는지를 확인하기 위한 체크값을 결정하는 방식을 말한다.
데이터를 전송하기 전에 주어진 데이터의 값에 따라 CRC 값을 계산하여 데이터에 붙여 전송하고, 데이터 전송이 끝난 후 받은 데이터의 값으로 다시 CRC 값을 계산하게 된다. 이어서 두 값을 비교하고, 이 두 값이 다르면 데이터 전송 과정에서 잡음 등에 의해 오류가 덧붙여 전송된 것 임을 알 수 있다.
CRC는 이진법 기반의 하드웨어에서 구현하기 쉽고, 데이터 전송 과정에서 발생하는 흔한 오류들을 검출하는 데 탁월하다. 하지만 CRC의 구조 때문에 의도적으로 주어진 CRC 값을 갖는 다른 데이터를 만들기가 쉽고, 따라서 데이터 무결성을 검사하는 데는 사용될 수 없다. 이런 용도로는 MD5 등의 함수들이 사용된다.
순환 중복 검사를 계산하는 과정은 하드웨어적 방식과 소프트웨어적 방식을 생각할 수 있다. 하드웨어적 방식을 말할 때, 직렬데이터를 계산하는 것이 단순하다. 통신시스템에서 프로토콜 계층에서 물리층에 가까울수록 하드웨어 접근을 그리고 상위계층에 가까울 수록 소프트웨어적인 방식이 적용된다.

---

CRC-16 계산 코어 알고리즘은 다음과 같이 간단히 구현할 수 있다

(CRC-16 여러 알고리즘들의 구현 편의성을 위해 객체지향 구현)

#include <vector>
#include <algorithm>

static const uint8_t REFLECT_BIT_ORDER_TABLE[256] = {
    0x00, 0x80, 0x40, 0xC0, 0x20, 0xA0, 0x60, 0xE0,
    0x10, 0x90, 0x50, 0xD0, 0x30, 0xB0, 0x70, 0xF0,
    0x08, 0x88, 0x48, 0xC8, 0x28, 0xA8, 0x68, 0xE8,
    0x18, 0x98, 0x58, 0xD8, 0x38, 0xB8, 0x78, 0xF8,
    0x04, 0x84, 0x44, 0xC4, 0x24, 0xA4, 0x64, 0xE4,
    0x14, 0x94, 0x54, 0xD4, 0x34, 0xB4, 0x74, 0xF4,
    0x0C, 0x8C, 0x4C, 0xCC, 0x2C, 0xAC, 0x6C, 0xEC,
    0x1C, 0x9C, 0x5C, 0xDC, 0x3C, 0xBC, 0x7C, 0xFC,
    0x02, 0x82, 0x42, 0xC2, 0x22, 0xA2, 0x62, 0xE2,
    0x12, 0x92, 0x52, 0xD2, 0x32, 0xB2, 0x72, 0xF2,
    0x0A, 0x8A, 0x4A, 0xCA, 0x2A, 0xAA, 0x6A, 0xEA,
    0x1A, 0x9A, 0x5A, 0xDA, 0x3A, 0xBA, 0x7A, 0xFA,
    0x06, 0x86, 0x46, 0xC6, 0x26, 0xA6, 0x66, 0xE6,
    0x16, 0x96, 0x56, 0xD6, 0x36, 0xB6, 0x76, 0xF6,
    0x0E, 0x8E, 0x4E, 0xCE, 0x2E, 0xAE, 0x6E, 0xEE,
    0x1E, 0x9E, 0x5E, 0xDE, 0x3E, 0xBE, 0x7E, 0xFE,
    0x01, 0x81, 0x41, 0xC1, 0x21, 0xA1, 0x61, 0xE1,
    0x11, 0x91, 0x51, 0xD1, 0x31, 0xB1, 0x71, 0xF1,
    0x09, 0x89, 0x49, 0xC9, 0x29, 0xA9, 0x69, 0xE9,
    0x19, 0x99, 0x59, 0xD9, 0x39, 0xB9, 0x79, 0xF9,
    0x05, 0x85, 0x45, 0xC5, 0x25, 0xA5, 0x65, 0xE5,
    0x15, 0x95, 0x55, 0xD5, 0x35, 0xB5, 0x75, 0xF5,
    0x0D, 0x8D, 0x4D, 0xCD, 0x2D, 0xAD, 0x6D, 0xED,
    0x1D, 0x9D, 0x5D, 0xDD, 0x3D, 0xBD, 0x7D, 0xFD,
    0x03, 0x83, 0x43, 0xC3, 0x23, 0xA3, 0x63, 0xE3,
    0x13, 0x93, 0x53, 0xD3, 0x33, 0xB3, 0x73, 0xF3,
    0x0B, 0x8B, 0x4B, 0xCB, 0x2B, 0xAB, 0x6B, 0xEB,
    0x1B, 0x9B, 0x5B, 0xDB, 0x3B, 0xBB, 0x7B, 0xFB,
    0x07, 0x87, 0x47, 0xC7, 0x27, 0xA7, 0x67, 0xE7,
    0x17, 0x97, 0x57, 0xD7, 0x37, 0xB7, 0x77, 0xF7,
    0x0F, 0x8F, 0x4F, 0xCF, 0x2F, 0xAF, 0x6F, 0xEF,
    0x1F, 0x9F, 0x5F, 0xDF, 0x3F, 0xBF, 0x7F, 0xFF
};

class CRC16
{
public:
    CRC16(uint16_t polynomial, uint16_t init_value = 0, bool reflect_input = true, bool reflect_output = true, uint16_t xor_output = 0) {
        this->polynomial = polynomial;
        this->init_value = init_value;
        this->reflect_input = reflect_input;
        this->reflect_output = reflect_output;
        this->xor_output = xor_output;
    };

    uint16_t calculate(const char* string) {
        std::vector<uint8_t> data;
        for (size_t i = 0; i < strlen(string); i++) {
            data.push_back(string[i]);
        }
        return calculate(data);
    }

    uint16_t calculate(const uint8_t* data_in, const int length) {
        std::vector<uint8_t> data;
        for (int i = 0; i < length; i++) {
            data.push_back(data_in[i]);
        }
        return calculate(data);
    }
    
    uint16_t calculate(std::vector<uint8_t> data) {
        uint16_t crc = init_value;
        for (size_t i = 0; i < data.size(); i++) {
            uint8_t byte = reflect_input ? REFLECT_BIT_ORDER_TABLE[data[i]] : data[i];
            crc ^= (byte << 8);
            for (int j = 0; j < 8; j++) {
                crc = crc & 0x8000 ? (crc << 1) ^ polynomial : crc << 1;
            }
        }
        if (reflect_output) {
            crc = reflect(crc);
        }
        crc = (crc ^ xor_output) & 0xFFFF;
        return crc;
    }

private:
    uint16_t polynomial;
    uint16_t init_value;
    bool reflect_input;
    bool reflect_output;
    uint16_t xor_output;

    uint16_t reflect(uint16_t value) {
        uint16_t reflected = 0;
        for (int i = 0; i < 16; i++) {
            if (value & 0x01)
                reflected |= (1 << ((16 - 1) - i));
            value = (value >> 1);
        }
        return reflected;
    }
};

• 다항식 계수, 초기값, XOR 출력값: 2바이트 멤버변수 (uint16_t)
• 입/출력 반전(reflection) 여부: 1비트 boolean 멤버변수
• 입력 데이터 반전을 위해 Look-up table 작성
• 계산을 위한 데이터는 1바이트 (uint8_t) 벡터로 전달받음
• 문자열 데이터 및 바이트배열 입력받기 위해 calculate 메서드 오버로드
• 출력 반전은 2바이트 데이터를 위한 메서드로 따로 구현 (reflect)

 

다항식 계수, 초기값, XOR 출력값, 입력 Reflection, 출력 Reflection 5개 파라미터에 따라 다양한 알고리즘이 존재한다

https://crccalc.com/

Online CRC-8 CRC-16 CRC-32 Calculator

 

위 사이트에서 각 알고리즘별 파라미터들에 대한 정보를 제공하니, 위에서 구현해둔 CRC16 베이스 클래스를 상속받아 다음과 같이 쉽게 구현할 수 있다

class CRC16_ARC : public CRC16
{
public:
    CRC16_ARC() : CRC16(0x8005, 0x0000, true, true, 0x0000) {};
};

class CRC16_CCITT_FALSE : public CRC16
{
public:
    CRC16_CCITT_FALSE() : CRC16(0x1021, 0xFFFF, false, false, 0x0000) {};
};

class CRC16_AUG_CCITT : public CRC16
{
public:
    CRC16_AUG_CCITT() : CRC16(0x1021, 0x1D0F, false, false, 0x0000) {};
};

class CRC16_BUYPASS : public CRC16
{
public:
    CRC16_BUYPASS() : CRC16(0x8005, 0x0000, false, false, 0x0000) {};
};

class CRC16_CMDA2000 : public CRC16
{
public:
    CRC16_CMDA2000() : CRC16(0xC867, 0xFFFF, false, false, 0x0000) {};
};

class CRC16_DDS_110 : public CRC16
{
public:
    CRC16_DDS_110() : CRC16(0x8005, 0x800D, false, false, 0x0000) {};
};

class CRC16_DECT_R : public CRC16
{
public:
    CRC16_DECT_R() : CRC16(0x0589, 0x0000, false, false, 0x0001) {};
};

class CRC16_DECT_X : public CRC16
{
public:
    CRC16_DECT_X() : CRC16(0x0589, 0x0000, false, false, 0x0000) {};
};

class CRC16_DNP : public CRC16
{
public:
    CRC16_DNP() : CRC16(0x3D65, 0x0000, true, true, 0xFFFF) {};
};

class CRC16_EN_13757 : public CRC16
{
public:
    CRC16_EN_13757() : CRC16(0x3D65, 0x0000, false, false, 0xFFFF) {};
};

class CRC16_GENIBUS : public CRC16
{
public:
    CRC16_GENIBUS() : CRC16(0x1021, 0xFFFF, false, false, 0xFFFF) {};
};

class CRC16_MAXIM : public CRC16
{
public:
    CRC16_MAXIM() : CRC16(0x8005, 0x0000, true, true, 0xFFFF) {};
};

class CRC16_MCRF4XX : public CRC16
{
public:
    CRC16_MCRF4XX() : CRC16(0x1021, 0xFFFF, true, true, 0x0000) {};
};

class CRC16_RIELLO : public CRC16
{
public:
    CRC16_RIELLO() : CRC16(0x1021, 0xB2AA, true, true, 0x0000) {};
};

class CRC16_T10_DIF : public CRC16
{
public:
    CRC16_T10_DIF() : CRC16(0x8BB7, 0x0000, false, false, 0x0000) {};
};

class CRC16_TELEDISK : public CRC16
{
public:
    CRC16_TELEDISK() : CRC16(0xA097, 0x0000, false, false, 0x0000) {};
};

class CRC16_TMS37157 : public CRC16
{
public:
    CRC16_TMS37157() : CRC16(0x1021, 0x89EC, true, true, 0x0000) {};
};

class CRC16_USB : public CRC16
{
public:
    CRC16_USB() : CRC16(0x8005, 0xFFFF, true, true, 0xFFFF) {};
};

class CRC_A : public CRC16
{
public:
    CRC_A() : CRC16(0x1021, 0xC6C6, true, true, 0x0000) {};
};

class CRC16_KERMIT : public CRC16
{
public:
    CRC16_KERMIT() : CRC16(0x1021, 0x0000, true, true, 0x0000) {};
};

class CRC16_MODBUS : public CRC16
{
public:
    CRC16_MODBUS() : CRC16(0x8005, 0xFFFF, true, true, 0x0000) {};
};

class CRC16_X_25 : public CRC16
{
public:
    CRC16_X_25() : CRC16(0x1021, 0xFFFF, true, true, 0xFFFF) {};
};

class CRC16_XMODEM : public CRC16
{
public:
    CRC16_XMODEM() : CRC16(0x1021, 0x0000, false, false, 0x0000) {};
};

 

CRC 계산 결과 테스트에 일반적으로 사용되는 "123456789" 문자열을 사용해 테스트해보자

int main()
{
    char string[] = "123456789";
    uint16_t result;

    result = CRC16_ARC().calculate(string);
    printf("CRC-16/ARC: 0x%04X\n", result);
    result = CRC16_CCITT_FALSE().calculate(string);
    printf("CRC-16/CCITT-FALSE: 0x%04X\n", result);
    result = CRC16_AUG_CCITT().calculate(string);
    printf("CRC-16/AUT-CCITT: 0x%04X\n", result);
    result = CRC16_BUYPASS().calculate(string);
    printf("CRC-16/BUYPASS: 0x%04X\n", result);
    result = CRC16_CMDA2000().calculate(string);
    printf("CRC-16/CDMA2000: 0x%04X\n", result);
    result = CRC16_DDS_110().calculate(string);
    printf("CRC-16/DDS-110: 0x%04X\n", result);
    result = CRC16_DECT_R().calculate(string);
    printf("CRC-16/DECT-R: 0x%04X\n", result);
    result = CRC16_DECT_X().calculate(string);
    printf("CRC-16/DECT-X: 0x%04X\n", result);
    result = CRC16_DNP().calculate(string);
    printf("CRC-16/DNP: 0x%04X\n", result);
    result = CRC16_EN_13757().calculate(string);
    printf("CRC-16/EN-13757: 0x%04X\n", result);
    result = CRC16_GENIBUS().calculate(string);
    printf("CRC-16/GENIBUS: 0x%04X\n", result);
    result = CRC16_MAXIM().calculate(string);
    printf("CRC-16/MAXIM: 0x%04X\n", result);
    result = CRC16_MCRF4XX().calculate(string);
    printf("CRC-16/MCRF4XX: 0x%04X\n", result);
    result = CRC16_RIELLO().calculate(string);
    printf("CRC-16/RIELLO: 0x%04X\n", result);
    result = CRC16_T10_DIF().calculate(string);
    printf("CRC-16/T10-DIF: 0x%04X\n", result);
    result = CRC16_TELEDISK().calculate(string);
    printf("CRC-16/TELEDISK: 0x%04X\n", result);
    result = CRC16_TMS37157().calculate(string);
    printf("CRC-16/TMS37157: 0x%04X\n", result);
    result = CRC16_USB().calculate(string);
    printf("CRC-16/USB: 0x%04X\n", result);
    result = CRC_A().calculate(string);
    printf("CRC-A: 0x%04X\n", result);
    result = CRC16_KERMIT().calculate(string);
    printf("CRC16/KERMIT: 0x%04X\n", result);
    result = CRC16_MODBUS().calculate(string);
    printf("CRC16/MODBUS: 0x%04X\n", result);
    result = CRC16_X_25().calculate(string);
    printf("CRC16/X-25: 0x%04X\n", result);
    result = CRC16_XMODEM().calculate(string);
    printf("CRC16/XMODEM: 0x%04X\n", result);
    
    return 0;
}

 

[실행 결과]

CRC-16/ARC: 0xBB3D
CRC-16/CCITT-FALSE: 0x29B1
CRC-16/AUT-CCITT: 0xE5CC
CRC-16/BUYPASS: 0xFEE8
CRC-16/CDMA2000: 0x4C06
CRC-16/DDS-110: 0x9ECF
CRC-16/DECT-R: 0x007E
CRC-16/DECT-X: 0x007F
CRC-16/DNP: 0xEA82
CRC-16/EN-13757: 0xC2B7
CRC-16/GENIBUS: 0xD64E
CRC-16/MAXIM: 0x44C2
CRC-16/MCRF4XX: 0x6F91
CRC-16/RIELLO: 0x63D0
CRC-16/T10-DIF: 0xD0DB
CRC-16/TELEDISK: 0x0FB3
CRC-16/TMS37157: 0x26B1
CRC-16/USB: 0xB4C8
CRC-A: 0xBF05
CRC16/KERMIT: 0x2189
CRC16/MODBUS: 0x4B37
CRC16/X-25: 0x906E
CRC16/XMODEM: 0x31C3

---

실제로 오가는 패킷 길이가 256바이트 언저리라 CRC 계산시 큰 부하는 걸리지 않아서 위와 같이 모든 데이터에 대해 루프를 돌며 bit-shift 연산을 하도록 구현했는데, 일반적으로는 CRC 알고리즘 결정 (=다항식 결정) 후 0~255 값에 대한 bit-shift 연산 결과를 LUT로 메모리에 적재해두고 계산 시 참조하는 방식이 속도 측면에서 훨씬 효율적이다 (이중 for문 제거)

class CRC16
{
public:
    CRC16(uint16_t polynomial, uint16_t init_value = 0, bool reflect_input = true, bool reflect_output = true, uint16_t xor_output = 0) {
        /* 중략 */
        // 인스턴스 생성 시 LUT 초기화
        create_lookup_table();
    };
    /* 중략 */
    uint16_t calculate(std::vector<uint8_t> data) {
        uint16_t crc = init_value;
        for (size_t i = 0; i < data.size(); i++) {
            uint8_t byte = reflect_input ? REFLECT_BIT_ORDER_TABLE[data[i]] : data[i];
            // LUT 참조로 이중 for문 제거
            crc = (crc << 8) ^ lut_crc[((crc >> 8) ^ byte)];
        }
        if (reflect_output) {
            crc = reflect(crc);
        }
        crc = (crc ^ xor_output) & 0xFFFF;
        return crc;
    }

private:
    /* 중략 */
    uint16_t lut_crc[256] = { 0 };

    void create_lookup_table() {
        // LUT 초기화 메서드
        uint16_t x;
        for (uint16_t i = 0; i < 256; i++) {
            x = i << 8;
            for (int j = 0; j < 8; j++) {
                x = x & 0x8000 ? (x << 1) ^ polynomial : x << 1;
            }
            lut_crc[i] = x;
        }
    }
    /* 중략 */
};

 

시간이 나면 CRC-8, CRC-32 뿐만 아니라 MD5 등 알고리즘까지 모두 손수 구현한 다음에 깃헙에 저장소 하나 마련해서 올려봐야겠다 ㅎㅎ (우선 회사 업무 급한 불은 껐으니~)

 

 

[참고]

https://ko.wikipedia.org/wiki/%EC%88%9C%ED%99%98_%EC%A4%91%EB%B3%B5_%EA%B2%80%EC%82%AC

https://www.zlib.net/crc_v3.txt

https://pythonhosted.org/crccheck/_modules/crccheck/base.html#reflectbitorder

https://blog.naver.com/PostView.nhn?isHttpsRedirect=true&blogId=dolicom&logNo=10070824912