crc32 코드

출처 : 

http://blog.naver.com/PostView.nhn?blogId=kgw1729&logNo=140062753310&redirect=Dlog&widgetTypeCall=true

CRC(Cyclic Redundancy Check)

CRC는 생성 다항식(generator polynominal)이라 불리는 고정 크기의 키 값(제수, divider)으로 데이터 블럭의 값을 차례대로 나누어서 그 나머지를 누적시키는 일종의 해시 함수이다. 이때 생성 다항식을 어떤 값으로 선택하느냐에 따라 데이터 블럭 내의 오류 패턴을 검출하는 능력에 영향을 미치게 된다. 보통 한 두개의 비트 오류는 물론 연속적으로 비트 오류가 발생되는 버스트 에러까지도 99.99% 이상 감지한다.

국제 표준으로 아래 3가지의 생성 다항식이 채택되어 있다. 각각의 표준에는 체크썸의 비트 수, 생성 다항식, 생성 다항식을 이진수로 표현한 제수, 나머지의 초기값, 최종 나머지에 적용할 XOR 값이 명시되어 있다. CRC32는 이더넷에서 MAC 프레임의 오류 검출에 사용되는 방식이다.

 

1) CCITT

체크썸 크기  : 16 비트

생성 다항식  : X^16 + X^12 + X^5 + 1

제 수        : 0x1021

나머지 초기값: 0xFFFF

최종 XOR값   : 0x0000

 

2) CRC16

체크썸 크기  : 16 비트

생성 다항식  : X^16 + X^15 + X^2 + 1

제 수        : 0x8005

나머지 초기값: 0x0000

최종 XOR값   : 0x0000

 

3) CRC32

체크썸 크기  : 32 비트

생성 다항식  : X^32 + X^26 + X^23 + X^22 + X^16 + X^12 + X^11 +

               X^10 + X^8 + X^7 + X^5 + X^4 + X^2 + X^1 + 1

제 수        : 0x04C11DB7

나머지 초기값: 0xFFFFFFFF

최종 XOR값   : 0xFFFFFFFF

 

아래의 C 코드는 CCITT 방식의 CRC를 계산할 수 있는 코드이다. CRC16이나 CRC32를 계산하려면 원하는 방식에 맞게 CRC 파라미터에 대한 3개의 상수 정의(POLYNOMIAL, INITIAL_REMAINDER, FINAL_XOR_VALUE)와 체크썸 크기에 대한 타입 정의(width)를 수정하면 된다.

CRC16 표준으로 바꾸려면 3개의 상수를 각각 0x8005, 0x0000, 0x0000으로 바꾸면 된다.

CRC32 표준으로 바꾸려면 3개의 상수를 각각 0x04C11DB7, 0xFFFFFFFF, 0xFFFFFFFF으로 바꾸고 체크썸 크기(width)에 대한 타입 정의를 unsigned long으로 바꾸면 된다.

 

/*
 * The CRC parameters.  Currently configured for CCITT.
 * Simply modify these to switch to another CRC standard.
 */
#define POLYNOMIAL          0x1021
#define INITIAL_REMAINDER   0xFFFF
#define FINAL_XOR_VALUE     0x0000

 

/*
 * The width of the CRC calculation and result.
 * Modify the typedef for an 8 or 32-bit CRC standard.
 */
typedef unsigned short width;

 

#define WIDTH   (8 * sizeof(width))
#define TOPBIT  (1 << (WIDTH - 1))

 

/*
 * An array containing the pre-computed intermediate result for each
 * possible byte of input.  This is used to speed up the computation.
 */
width  crcTable[256];

 

/*****************************************************************
 * Function:    crcInit()
 *
 * Description: Initialize the CRC lookup table.  This table is used
 *              by crcCompute() to make CRC computation faster.
 * Notes:       The mod-2 binary long division is implemented here.
 * Returns:     None defined.
 *****************************************************************/
void crcInit(void)
{
    width  remainder;             
    width  dividend;             
    int    bit;                 

 

    /* Perform binary long division, a bit at a time. */
    for (dividend = 0; dividend < 256; dividend++)
    {
        /* Initialize the remainder. */
        remainder = dividend << (WIDTH - 8);

 

        /* Shift and XOR with the polynomial. */
        for (bit = 0; bit < 8; bit++)
        {
            /* Try to divide the current data bit. */
            if (remainder & TOPBIT)
                remainder = (remainder << 1) ^ POLYNOMIAL;
            else
                remainder = remainder << 1;
        }

 

        /* Save the result in the table. */
        crcTable[dividend] = remainder;
    }

}

 

/*****************************************************************
 * Function:    crcCompute()
 *
 * Description: Compute the CRC checksum of a binary message block.
 * Notes:       This function expects that crcInit() has been called
 *              first to initialize the CRC lookup table.
 * Returns:     The CRC of the data.
 *****************************************************************/
width crcCompute(unsigned char *message, unsigned int nBytes)
{
    unsigned int   offset;
    unsigned char  byte;
    width          remainder = INITIAL_REMAINDER;

 

    /* Divide the message by the polynomial, a byte at time. */
    for (offset = 0; offset < nBytes; offset++)
    {
        byte = (remainder >> (WIDTH - 8)) ^ message[offset];
        remainder = crcTable[byte] ^ (remainder << 8);
    }

 

    /* The final remainder is the CRC result. */
    return (remainder ^ FINAL_XOR_VALUE);

}

 

crcInit() 함수는 CRC 계산을 비트 단위가 아닌 바이트 단위로 하기 위해 한 바이트가 가질 수 있는 나머지 값을 미리 구하는 함수이다. 이 중간 결과는 전역 변수(crcTable)에 저장되어 crcCompute() 함수에서 사용된다. crcCompute()를 호출하여 CRC 계산을 하기 위해선 crcInit()이 먼저 실행되어 crcTable이 만들어져 있어야 한다. crcInit()은 프로그램이 실행될 때 최초로 한 번만 실행되면 된다. 또는 미리 실행하여 구한 crcTable 값을 롬에 저장하여 사용할 수도 있다.

===========================================================================================

여러곳에 있는 crc 코드를 가져다가 해보고 해봐도 그렇게 안되던것이 ,,

역시 단순한 변수 형때문이었다 .

회사 서버는 64bit  client 보드는 당연히 32bit ,,

crc32로 한다고 unsigned long으로 하면 안된다 ,,, 뭐 책에서 본 내용대로라면 당연히 안되야 맞지만

여기도 그렇고 저기도 그렇고 ,, long으로 하라는데 ,, 

crc32 알고리즘을 정확히 이해가 안된 상황에서 하라는데로 했다가 ...

결론 !

unsigned long 대신

그냥 unsigned int 를 하면 64bit, 32bit 안가리고 자료형의 크기가 같기때문에 잘! 된다 !!

아주 잘 된다 !!!

오예 ~ 이제 파일 전송을 해보자 ! 고고 ㅋ