[임베디드]메모리 내용 검증 - CRC

이전 글에서 설명한 메모리 테스트 방법은 기본적으로 메모리의 내용을 파괴하면서 진행하는 방법이기에 롬이나 하이브리드(플래시, EEPROM) 메모리에는 적용할 수 없다. 그러나 롬이나 하이브리드 메모리에서도 여전히 메모리가 장착되지 않았거나 잘못 장착되는 경우가 있을 수 있고 물리적 전기적인 충격으로 손상되거나 배선 문제 등으로 인해 정상 동작하지 않는 경우가 생길 수 있다. 그러므로 이런 류의 비휘발성 메모리의 경우에도 문제가 없으리라고 가정해서는 안된다.

그런데 이런 비휘발성 메모리의 경우는 그 용도가 의미있은 초기 데이터(그것이 프로그램이던 순수 데이터이던)를 저장하는 것이기에 단순히 메모리 칩의 물리적인 동작 여부를 검사하는 것보다 저장되어 있는 데이터의 내용이 손상되지 않았다는 것을 증명하는 것이 더 바람직하다. 이런 데이터 내용 검증을 위해 사용할 수 있는 방법이 체크썸이나 CRC이다.

 

체크썸

체크썸은 단순히 데이터 블럭을 내용을 바이트 또는 워드 단위로 캐리를 버리면서 전부 더한 값이다. 이 체크썸을 데이터 블럭과 함께 저장해 놓으면 나중에 데이타 블럭의 오류 여부를 어느 정도 감지할 수 있다. 그러나 데이터 블럭의 내용이 어떤 요인에 의해 전부 0으로 초기화되는 경우, 체크썸도 함께 0으로 바뀌기 때문에 오류를 감지하지 못한다. 이런 문제 때문에 TCP/IP 패킷 헤더 등에서 사용되는 체크썸은 최종 단계에 체크썸의 보수를 취해서 저장한다. 체크썸은 간단한 반면 오류 감지 능력이 대단히 빈약하다. 즉, 동일한 비트 위치에서 발생되는 홀수 개의 비트 오류는 감지하지만 짝수 개의 비트 오류에 대해서는 전혀 감지하지 못한다.

 

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 값을 롬에 저장하여 사용할 수도 있다.

 

참고)

[Programming Embedded Systems in C and C++], 1999, O'Reilly, Michael Barr

(2000년, 한빛미디어, 이석주 역)

[출처] [임베디드]메모리 내용 검증 - CRC|작성자 프리맨K