python crc32와 polynomial과 c로 구현한 crc32

python crc32

파이썬의 standard library에서 crc32를 지원한다. zlib.crc32와 binascii.crc32 두가지가 있다. 

import binascii
import zlib

print('binascii.crc32(\'123456789\') = ',hex(binascii.crc32('123456789'.encode('UTF-8'))&0xffffffff))
print('zlib.crc32(\'123456789\') = ',hex(zlib.crc32('123456789'.encode('UTF-8'))&0xffffffff))

입력데이터는 bytes-like object를 사용해야 하며, 위 코드의 결과는 아래와 같다. 

binascii.crc32('123456789') =  0xcbf43926
zlib.crc32('123456789') =  0xcbf43926

온라인 사이트에서 crc32 계산 결과와 같다.

https://www.lammertbies.nl/comm/info/crc-calculation

Polynomial

위 온라인 사이트에서 일반적으로 crc32에 사용되는 polynomial 이 0x04C11DB7라고 되어있어 위 사이트에서도 0x04C11DB7를 사용하는 줄 알았으나, c로 구현한 crc32에서 0x04C11DB7를 사용하면 crc32 결과가 맞지 않는다. 

여기저기 검색하다 GZIP file format rfc1952의 예제 코드에서 사용하는 polynomial 0xEDB88320을 사용하면 python의 crc32결과와 동일하게 나오는 것을 발견했다.

c로 구현한 crc32

crc32 table을 만드는 코드는 아래와 같다.

unsigned int *crc32_table(unsigned int polynomial)
{
        int i, j;
        unsigned int crc = 0;
        unsigned int *table = (unsigned int*)malloc(sizeof(unsigned int) * 256);
        if (!table) return NULL;


        memset(table, 0, sizeof(unsigned int) * 256);

        for (i = 0; i<256; i++)
        {
                crc = i;
                for (j = 0; j<8; j++)
                {
                        if (crc & 0x1)
                        { 
                                crc >>= 1;
                                crc ^= polynomial;
                        }
                        else
                        {
                                crc >>= 1;
                        }
                }
                table[i] = crc;
        }
        return table;
}

crc32를 생성하는 코드는 아래와 같다.

unsigned int crc32_cal(unsigned int* table, unsigned int crc, unsigned char *buf, int len)
{
        if (!table || !buf) return crc;

        crc = ~crc;
        for (int k = 0; k<len; k++)
        {
                crc = (crc >> 8) ^ table[(crc & 0xff) ^ (unsigned int)buf[k]];
        }
        return ~crc;
}

위 코드를 사용해 crc를 수행하면,

char *msg = "123456789";
unsigned int *table = crc32_table(0xEDB88320);
if (table)
{
    unsigned int crc = crc32_cal(table, 0, (unsigned char*)msg, strlen(msg)) & 0xffffffff;
    _trace(TEXT("polynomial 0x%x  crc = 0x%x\n"), 0xEDB88320, crc);
    free(table);
}

다음과 같이 출력된다.

polynomial 0xedb88320  crc = 0xcbf43926