체크섬 생성

기술노트 26457

아키텍처:

All

컴포넌트:

general

업데이트:

2021-06-29 오전 4:02

소개

본 내용은 체크섬 생성에 대한 개요로, CRC 구현물의 무게 대비 속도에 대한 내용을 담고 있습니다. 

CRC에 대해 잘 모르시는 분은 먼저 "A PAINLESS GUIDE TO CRC ERROR DETECTION ALGORITHMS" (저:Ross N. Williams)를 먼저 읽어 보시는 것이 좋습니다. 이 글에서는 CRC에 대해 아무 자세하게 소개하고 있으며, 먼저 byte sum (byte1 + byte2 + byte3 + ...)부터 시작해 점점 더 개선 시켜 나가는 방식으로 진행합니다. 최종적으로는 다항 표 방식이 사용되며 이것은 최근에는 거의 표준으로 자리잡은 방식입니다. 

이 글은 20년 전에 작성된 것이지만 CRC는 그 후 바뀐 적이 없으며, 아직도 그 텍스트는 CRC 분야에서 고전으로 일컬어 지고 있습니다. 

본 텍스트에서는 CRC16  polynominal(0x1021) 및 2-byte 체크섬을 사용하기로 합니다.  이는 더 큰 polynominal 및 체크섬 용량에 대해서도 쉽게 일반화 할 수가 있으며, 별첨 A에서는 CRC32 () 에 대해 간단한 샘플 코드를 제공하고 있습니다.

논의

기본 버전 

C 언어 crc 구현의 아주 간단한 예를 들어 보면 아래와 같습니다:

typedef unsigned char * ptr;
typedef unsigned char   uint8_t;
typedef unsigned short  uint16_t;
typedef unsigned long   uint32_t;

uint16_t
crc_impl(uint16_t sum, ptr p, uint32_t len)
{
 while (len--)
 {
  uint8_t byte = *p++;

  for (int i = 0; i < 8; ++i)
  {
   uint16_t osum = sum;

   sum <<= 1;

   if (byte & 0x80)
    sum |= 1 ;

   if (osum & 0x8000)
    sum ^= 0x1021; // the polynomial

   byte <<= 1;
  }
 }
 return sum;
}

이것은 확실히 통하는 코드입니다만, crc_impl 로부터 리턴되는 체크섬과 crc 툴에서 계산된 결과(ielftool 등)를 비교하고 싶다면, byte 시퀀스를 처리한 다음 0을 두 개 추가로 투입하여야 합니다. 왜 그럴까요? Williams는 그것을 위에서 링크된 텍스트로 설명하고 있습니다. 이를 간단히 설명 드리면, 아직 “파이프라인” 안에 있는 상황으로 “배출”하지 않으면 안 되는 것입니다. 

static const uint8_t zeroes[] = { 0, 0 };

uint16_t
crc(uint16_t sum, ptr p, uint32_t len)
{
 return crc_impl(crc_impl(sum, p, len), (ptr)zeroes, 2);
}

Cortex-M3를 사용할 경위 위의 코드를 컴파일하면 72 bytes가 됩니다. (하이 밸런스 최적화) 그리고 각각의 체크섬 바이트에 대해 125 사이클이 소요됩니다. 

사이클 횟수 관련 

이 기사에 수록되어 있는 사이클 횟수는 Simulator를 통해 도출된 것입니다. Simulator는 사이클의 횟수를 정확하게 측정해 내지는 못하며, 일부 명령의 타이밍은 실제 프로세서의 타이밍과 차이가 있을 수 있습니다. 실제 사이클의 횟수는 더 높거나 낮을 수가 있습니다. 

ielftool로 생성된 체크섬의 확인 

  • 링커를 설정하여 체크섬를 채우고 생성하도록 합니다. 
  • 채움 문자열 0xFF을 사용합니다(구체적으로 어떤 문자열을 선택하는 지는 중요하지 않으나, 0xFF가 채움값으로 가장 자주 사용되는 것입니다). 0x0 ~ 0x1FFF으로 채움을 진행합니다. 구체적인 값은 그다지 중요하지 않으나, 일반적으로 전체 ROM을 채운 후 체크섬을 생성합니다. 
  • 2-byte crc-16 체크섬을 생성하며, 이때 시작값은 0x0입니다. 
  • 여수(complement)는 없으나, MSB가 우선(미러링 없음)이며 체크섬 단위의 크기는 8비트 입니다. 

그러면 이제 체크섬을 검증하는 프로그램을 작성할 순서입니다. 체크섬 자체는 체크섬 프로세스에서 반드시 배제해야 합니다. 그 이유는 __checksum의 생성자는 체크섬의 바이트를 사용하여 체크섬 바이트를 생성하는 것이 불가능하기 때문입니다. 이들은 프로세스로부터 완전히 배제되지 않으면 안 됩니다.  

첫 번째 방법은 체크섬이 절대로 체크섬되지 않도록 하는 것입니다. 링커에서 정의된 라벨 __checksum_begin에서부터 체크섬 전 마지막 바이트까지 체크섬을 진행한 다음, 체크섬 다음의 첫 바이트부터 링커 정의 라벨 __checksum_end까지 체크섬 합니다. 

extern uint16_t __checksum;          // linker defined
extern int      __checksum_begin;    // linker defined
extern int      __checksum_end;      // linker defined

int main()
{
 // where checksumming starts
 ptr p0 = (ptr)&__checksum_begin;

 // the address of the checksum
 ptr p1 = (ptr)&__checksum;

 // number of bytes between the start address and the checksum
 uint32_t len1 = (p1-p0),

 // number of bytes after the checksum
 len2 = ((ptr)&__checksum_end-p1)-1;

 // the initial value of the checksum
 uint16_t sum = 0;

 // if they exist, checksum the bytes between the checksum start
 // and the checksum

 if (len1)
  sum = crc(sum, p0, len1);

 // ignore the bytes of the checksum itself
 // if they exist, checksum the bytes between the first byte after
 // the checksum and the end checksum end

 if (len2)
  sum = crc(sum, p1+2, len2);

 // compare the computed checksum to the precomputed one
 if (sum == __checksum)
  return 1;

 return 0;
}

이는 .icf-file과 관련없이 효과를 기대할 수가 있으나, spolit range를 처리하는 과정이 번거롭습니다. 

또 다른 방법은 체크섬을 알려진 위치로 이동시키는 것입니다. 체크섬 .icf 파일을 사용하며, 여기에 다음의 행이 포함되도록 업데이트합니다. 

place at address mem:0x40 { section .checksum };

0x40은 물론 적당한 (그리고 가용한) 다른 주소로 얼마든지 대체가 가능합니다. 일반적으로 체크섬은 체크섬 대상 범위의 시작 부분 또는 끝 부분에 위치하는 것이 바람직합니다. 그 결과 하나의 체크섬 범위가 확보되며, 이는 체크섬을 진행하는 코드 상에서 처리하기가 상대적으로 용이합니다. 간섭 백터 (0x0-0x3F)는 보통 ARM 기기가 차지하고 있습니다. 그러므로 메모리 말단부에 체크섬를 배치하는 방법이 상대적으로 더 나은 방법이라고 할 수 있습니다. 0x0-0x1FFD을 채운 다음, 체크섬을 0x1FFE에 배치합니다. 

int main()
{
 // where checksumming starts
 ptr p0 = (ptr)&__checksum_begin;

 // number of bytes to checksum
 uint32_t len1 = ((ptr)&__checksum_end-p0)+1;

 // the initial value of the checksum
 uint16_t sum = 0;

 // checksum the range
 sum = crc(sum, p0, len1);

 // compare the computed checksum to the precomputed one
 if (sum == __checksum)
  return 1;

 return 0;
}

이렇게 작성한 코드의 내용이 위의 예시보다 더 분명하고, 읽기도 쉽습니다. 하지만 한 가지 단점이 있다면 .icf 파일을 수정해야 한다는 것입니다. 

ROM 바이트 테이블 버전 

오늘날 CRC로 구현되는 시스템의 상당수는 바이트 기반의 테이블을 바탕으로 하고 있습니다. ielftool 및 XLINK 상에서는 테이블 기반으로 구현이 이루어집니다. 

static const uint16_t t[256] = {
 0x0000,0x1021,0x2042,0x3063,0x4084,0x50a5,0x60c6,0x70e7,0x8108,0x9129,0xa14a,
 0xb16b,0xc18c,0xd1ad,0xe1ce,0xf1ef,0x1231,0x0210,0x3273,0x2252,0x52b5,0x4294,
 0x72f7,0x62d6,0x9339,0x8318,0xb37b,0xa35a,0xd3bd,0xc39c,0xf3ff,0xe3de,0x2462,
 0x3443,0x0420,0x1401,0x64e6,0x74c7,0x44a4,0x5485,0xa56a,0xb54b,0x8528,0x9509,
 0xe5ee,0xf5cf,0xc5ac,0xd58d,0x3653,0x2672,0x1611,0x0630,0x76d7,0x66f6,0x5695,
 0x46b4,0xb75b,0xa77a,0x9719,0x8738,0xf7df,0xe7fe,0xd79d,0xc7bc,0x48c4,0x58e5,
 0x6886,0x78a7,0x0840,0x1861,0x2802,0x3823,0xc9cc,0xd9ed,0xe98e,0xf9af,0x8948,
 0x9969,0xa90a,0xb92b,0x5af5,0x4ad4,0x7ab7,0x6a96,0x1a71,0x0a50,0x3a33,0x2a12,
 0xdbfd,0xcbdc,0xfbbf,0xeb9e,0x9b79,0x8b58,0xbb3b,0xab1a,0x6ca6,0x7c87,0x4ce4,
 0x5cc5,0x2c22,0x3c03,0x0c60,0x1c41,0xedae,0xfd8f,0xcdec,0xddcd,0xad2a,0xbd0b,
 0x8d68,0x9d49,0x7e97,0x6eb6,0x5ed5,0x4ef4,0x3e13,0x2e32,0x1e51,0x0e70,0xff9f,
 0xefbe,0xdfdd,0xcffc,0xbf1b,0xaf3a,0x9f59,0x8f78,0x9188,0x81a9,0xb1ca,0xa1eb,
 0xd10c,0xc12d,0xf14e,0xe16f,0x1080,0x00a1,0x30c2,0x20e3,0x5004,0x4025,0x7046,
 0x6067,0x83b9,0x9398,0xa3fb,0xb3da,0xc33d,0xd31c,0xe37f,0xf35e,0x02b1,0x1290,
 0x22f3,0x32d2,0x4235,0x5214,0x6277,0x7256,0xb5ea,0xa5cb,0x95a8,0x8589,0xf56e,
 0xe54f,0xd52c,0xc50d,0x34e2,0x24c3,0x14a0,0x0481,0x7466,0x6447,0x5424,0x4405,
 0xa7db,0xb7fa,0x8799,0x97b8,0xe75f,0xf77e,0xc71d,0xd73c,0x26d3,0x36f2,0x0691,
 0x16b0,0x6657,0x7676,0x4615,0x5634,0xd94c,0xc96d,0xf90e,0xe92f,0x99c8,0x89e9,
 0xb98a,0xa9ab,0x5844,0x4865,0x7806,0x6827,0x18c0,0x08e1,0x3882,0x28a3,0xcb7d,
 0xdb5c,0xeb3f,0xfb1e,0x8bf9,0x9bd8,0xabbb,0xbb9a,0x4a75,0x5a54,0x6a37,0x7a16,
 0x0af1,0x1ad0,0x2ab3,0x3a92,0xfd2e,0xed0f,0xdd6c,0xcd4d,0xbdaa,0xad8b,0x9de8,
 0x8dc9,0x7c26,0x6c07,0x5c64,0x4c45,0x3ca2,0x2c83,0x1ce0,0x0cc1,0xef1f,0xff3e,
 0xcf5d,0xdf7c,0xaf9b,0xbfba,0x8fd9,0x9ff8,0x6e17,0x7e36,0x4e55,0x5e74,0x2e93,
 0x3eb2,0x0ed1,0x1ef0
};

uint16_t crc(uint16_t sum, ptr p, uint32_t len)
{
 while (len--)
  sum = t[(sum >> 8) ^ *p++] ^ (sum << 8);
 return sum;
}

 

Williams는 기본적인 CRC 알고리즘이 어떻게 표 기반의 것으로 바뀌는 지에 대해 매우 상세하게 설명하고 있습니다. 이 과정에는 몇 가지 중간 단계가 있는데, CRC의 작동 원리에 관심이 있으신 분들이라면 아마 이러한 중간 단계에 흥미가 있으실 것입니다.  이 표 기반의 버전은 정확하게 위의 코드와 동일한 CRC를 계산해 냅니다(2 개의 0을 처리한 후). 

Cortex-M3 상에서 표 기반의 버전은 552 바이트로 컴파일 됩니다(하이 밸런스드 최적화). 이 중에서 512 CRC 표 자체가 소비합니다. 각각의 체크섬 바이트는 약 15 사이클을 필요로 합니다. 따라서 표 기반의 버전은 기본 버전에 비해 훨씬 빠른 속도를 지니게 됩니다. 그러나 용량이 눈에 띄게 증가한다는 단점이 있습니다. 

RAM 바이트 테이블 버전 

프로그램 내에서 표를 생성하는 역시 당연히 가능합니다. 이 과정에서는 상대적으로 적은ROM 공간을 사용합니다. (왜냐하면, 표를 생성하는 코드는 표 자체보다 유의한 수준으로 작기 때문입니다.)  그러나 더 많은 RAM 공간을 필요로 합니다. (왜냐하면, 표는 런타임에서 작성될 필요가 있기 때문입니다). 

void construct_crc_table(uint16_t poly, void * space)
{
 uint16_t * crc_table = (uint16_t *)space;

 for (uint16_t i = 0; i < 256 ; ++i)
 {
  uint16_t r = i << 8;

  for (int j = 0 ; j < 8 ; ++j)
   r = (r & 0x8000) ? (r << 1) ^ poly : (r << 1);

  crc_table[i] = r;
 }
}

uint16_t crc(void * table, uint16_t sum, ptr p, uint32_t len)
{
 uint16_t * t = (uint16_t *)table;

 while (len--)
  sum = t[(sum >> 8) ^ *p++] ^ (sum << 8);

 return sum;
}

Cortex-M3 상에서 RAM 기반의 버전은 74 바이트로 컴파일 됩니다(하이 밸런스드 최적화). 표는 RAM 상에 구축되어야 하며, 이를 위해서는 RAM  상에서 연속으로 512 바이트가 필요합니다. 그러나 이러한 정도의 용량을 제공할 수 없는 시스템도 있을 수 있습니다. 표를 스택이나 힙 상에 구축하는 것도 가능하며, 글로벌 변수를 사용할 수도 있습니다. 어떤 방식을 사용할 것인지는 상황에 따라 정하면 되는 것이지요. 

RAM 자원이 많지 않을 경우 시스템 기동 시에 표를 구축하는 방법도 있습니다. 초기화 변수의 초기화가 발생하기 전에 구축하는 것으로, 이때 초기화 변수 등의 다른 자료가 위치하게 되는 어드레스를 이용하는 방식입니다. 이어서 체크섬 루틴이 임무를 수행한 다음에 변수 초기화를 정상적으로 수행합니다. 표는 삭제되는 것이지요. 이와 같은 방식을 사용하는 경우에는 초기화 후에는 절대로 표가 생성되거나 사용되지 않도록 특히 주의를 기울이지 않으면 안 됩니다. 

RAM 버전에서는 체크섬 작업 별로 서로 다른 표를 사용할 수도 있습니다. 이것은 실제로는 발생할 가능성이 낮은 경우이지만 동일한 프로그램에 대해 다른 체크섬 polynomial을 사용할 수가 있는 것입니다. 

표는 엔트리 당 96 회의 사이클을 사용하여 구축됩니다. 체크섬 된 각각의 바이트에 대해서 약 14 사이클이 소요되는데, 이는 속도 측면에서 ROM-테이블 버전과 거의 동일합니다. 

ROM nibble table 버전 

여기서 한 가지 알 수 있는 사실은 표에서 256 개의 엔트리 항목을 사용하는 경우 상당한 문제가 될 수 있다는 점입니다. 체크섬 엔트리 사이즈가 2 byte인 경우, 필연적으로 512 바이트의 테이블 공간이 소요됩니다. 만일에 엔트리 개수를 줄이는 경우, 전체적인 소요 공간은 줄어들 수가 있지만, 표에 대한 look up 동작이 더 많이 이루어져야 합니다. 

이보다 작은 대안으로 자연스럽게 떠오르는 것이 바로 4 비트, 즉 니블(nibble) 입니다. 니블 기반의 표는 16 개의 엔트리 만을 지니며, 따라서 체크섬 엔트리가 2 바이트인 경우 필요한 공간은 32 바이트가 됩니다. 바이트 대신 니블을 사용하는 경우 하나의 바이트를 처리하기 위해 두 개의 니블을 look up 해야 합니다. 

static const uint16_t t[] = {
 0x0000, 0x1021, 0x2042, 0x3063, 0x4084, 0x50a5, 0x60c6, 0x70e7,
 0x8108, 0x9129, 0xa14a, 0xb16b, 0xc18c, 0xd1ad, 0xe1ce, 0xf1ef,
};

uint16_t crc_nibble_rom(uint16_t sum, ptr p, uint32_t len)
{
 while (len--) {
  // hi nibble
  sum = t[(sum>>12)^(*p >> 4)]^(sum<<4);

  // lo nibble
  sum = t[(sum>>12)^(*p++ & 0xF)]^(sum<<4);
 }

 return sum;
}

Cortex-M3에서 니블 기반의 ROM 버전을 컴파일 하면 88 바이트가 됩니다(하이 밸런스). 각 바이트 당 필요한 사이클 수는 19회 입니다. 추가적인 RAM 은 필요치 않습니다. 

RAM nibble table 버전 

물론 이에 대응하는 니블 기반 RAM 버전도 존재합니다. 

void
construct_nibble_table(uint16_t poly, void * space)
{
 uint16_t * crc_table = (uint16_t *)space;

 for (uint16_t i = 0; i < 16 ; ++i) {
  uint16_t r = i << 12;

  for (int j = 0 ; j < 4 ; ++j)
   r = (r & 0x8000) ? (r << 1) ^ poly : (r << 1);

  crc_table[i] = r;
 }
}

uint16_t crc_nibble_ram(void * table, uint16_t sum, ptr p, uint32_t len)
{
 uint16_t * t = (uint16_t *)table;

 while (len--) {
  // hi nibble
  sum = t[(sum>>12)^(*p >> 4)]^(sum<<4);

  // lo nibble
  sum = t[(sum>>12)^(*p++ & 0xF)]^(sum<<4);
 }

 return sum;
}

 

Cortex-M3에서 니블 기반의 RAM 버전을 컴파일 하면 96 바이트가 됩니다(하이 밸런스). 이때 테이블이 필요로 하는 공간은 연속 32 바이트입니다. 바이트 기반의 RAM 버전에서 256 바이트를 필요로 했던 것을 생각하면, 소요 공간이 크게 줄어든 것이지요. RAM 니블 테이블을 구축하기 위해서는 52 사이클/엔트리가 필요합니다. 이것은 바이트 기반의 버전에 비해 거의 절반에 불과한 것입니다. 각각의 엔트리를 처리하는 데에 소요되는 비트 수가 절반으로 줄어들기 때문이지요. 각각의 바이트를 체크섬 하기 위해 필요한 사이클 수는 19회 입니다. 이렇게 되면 ROM 기반의 니블 버전과 동일해 지지만 바이트 기반의 버전에 비해서는 훨씬 못 미치게 됩니다. 

ROM 이용량(코드 및 const 테이블의 용량) 

lookup 테이블에서 필요로 하는 RAM 메모리(스택 이용량 미포함)  

CpB   Cycles per Byte,        how many cycles crc of one byte needs
CpTE  Cycles per Table Entry, how many cycles one table entry needs to be constructed

                      ROM use   RAM use   CpB   CpTE   64k-cycles   64k-time@74MHz
basic crc                70         -     125     -      8.19M          110 ms
byte oriented ROM       552         -      15     -       983k         13.3 ms
byte oriented RAM        74       512      14    96       918k*        12.4 ms*
nibble oriented ROM      88         -      19     -      1.25M         16.8 ms
nibble oriented RAM      96        32      19    52      1.25M*        16.8 ms*

* 테이블 구축은 제외 

RAM 버전은 ROM 버전과 비교할 때 크게 불리한 점이 하나 있습니다. 바로 lookup 테이블을 구축해야 한다는 것이지요. 

Table type   Entries   Cycles/entry   Time@74MHz
Nibble         16           52          0.01 ms
Byte          256           96          0.33 ms

만일에 표를 복수의 체크섬 작업을 위해서 사용할 수가 있는 경우(메모리가 해방되지 않고 계속 유지되는 경우를 가정), 표를 구축하는 데에 소요되는 자원은 여러 차례 작업을 반복하면서 상쇄될 수가 있습니다. 메모리의 해방이 이루어지거나, 체크섬 작업을 한 번만 수행하는 경우 표를 구성하는 데에 소요되는 자원은 체크섬에 소요되는 비용으로 인식되어야 할 것입니다. 

RAM 버전은 장점도 지니고 있는데, 바로 서로 다른 polynomial을 사용하여 복수의 표를 구성할 수가 있다는 점입니다(추가 표 구성 또는 기존 표에 오버라이팅). 동일한 프로그램에 둘 이상의 polynomial을 사용하는 것은 매우 희귀한 경우에 해당하지만, 그렇다고 이런 경우가 없는 것도 아닙니다. 

더 큰 인덱스 타입 

니블이나 바이트 단위의 인덱싱을 하지 않는, 더 큰 테이블을 쓸 수도 있습니다. 좀 더 큰 테이블을 사용하게 되면 사이클 요구량이 줄어듭니다. 테이블 lookup을 할 일이 그만큼 줄어들기 때문입니다. 하지만 대신 막대한 양의 자원이 소요되며(16비트 인덱스 crc16 테이블의 경우 RAM 용량 128k 소요), endianess를 처리해야 합니다. 이와 같은 방식은 아주 특수한 경우라면 적절히 사용할 수가 있겠지만, 본문에서 다루고 있는 범위에서는 벗어납니다. 

구현 방식의 선택 

눈 앞의 프로젝트에 있어 가장 ‘최선’의 선택은 체크섬 하고자 하는 대상이 무엇인지, 그리고 체크섬 루틴의 실행 빈도는 얼마나 되는지에 따라 정해 질 것입니다. 가장 일반적인 경우로 생각할 수 있는 것이 바로 기동 시에 ROM을 체크섬하거나, 플래쉬를 업데이트 할 때에 체크섬 하는 것입니다. CRC 구현 방식을 선택할 때에는 두 가지 요인에 유의해야 하는데, 바로 구현 결과물의 용량, 그리고 바이트의 처리 속도가 얼마나 빠른가 입니다. 이러한 구현 결과물은 일정 선 이상의 용량을 넘어서는 안 되며, 동시에 속도도 일정 수준 이상이 되어야 합니다. 구현 결과물의 속도가 어느 정도 확보가 되면, 가급적 그 용량을 줄이는 것이 최선입니다. 구현 결과물이 가용한 공간 내에 수용될 수 있다면, 가급적이면 속도를 높이는 것을 권장합니다. 

기본 CRC 알고리즘에서는 64k의 체크섬을 110ms (74MHz)의 속도로 끝낼 수가 있습니다. 이를 위해 70 바이트의 ROM이 소요되며, RAM은 소요되지 않습니다(단, 스택에 몇 바이트 정도는 필요합니다.) 만일에 이 정도로 충분하다면 다른 방식을 일부러 시도해 볼 필요는 없습니다. 속도도 충분하고, 더 작은 대안도 존재하지 않기 때문입니다. 

반면, 니블 기반의 ROM 버전은 더 크기는 하나 18 byte 정도의 크기 차이 밖에 없으며, 다른 추가적인 자원은 필요로 하지 않으나 속도는 기본적으로 6배가 더 빠릅니다. 소요 시간이 85% 줄어드는 대신, ROM을 18 바이트 더 투입할 가치가 있을까요? 대부분의 경우 그럴 가치가 충분히 있습니다. 

이와 거의 마찬가지로 byte 기반의 ROM 버전은 니블 기반  ROM 버전에 비해 464 바이트가 더 큽니다. 대신 바이트 당 사이클 요구 횟수가 약 20%가 줄어듭니다. 소요 시간이 줄어드는 대신, ROM을 464 바이트 더 투입할 가치가 있을까요? 대부분의 경우 그만한 가치는 없을 것입니다. 

바이트 기반 버전을 사용하고 싶지만 552 바이트의 ROM 용량을 ROM 버전을 위해 확보하기 어렵더라도 바이트 기반의 RAM 버전에 사용할 74 바이트는 확보가 가능하며, RAM 상에서 연속 512 바이트에 접근이 가능할 경우, RAM 버전이 대안이 될 수도 있을 것입니다. 이렇게 소요 시간이 줄어드는 대신, ROM을 512 바이트 더 투입할 가치가 있을까요? (투입은 아마 일시적으로 일어나게 될 것입니다.) 대부분의 경우 그만한 가치는 없을 것입니다. RAM이 그렇게 넘쳐나는 시스템은 상대적으로 많지 않으니까요. 

니블 기반 ROM 버전은 여러가지 상쇄 효과를 종합해 보았을 때에 전부는 아니더라도 대부분의 경우 가장 적절한 대안이 될 것입니다. 크기나 적당히 작고, 속도도 적절하니 말입니다. 

부록 A 

본문 내 crc16 예시를 CRC32 버전으로 옮기면 다음과 같습니다. 

CRC32의 값은 0x4C11DB7(실제로는 0x14C11DB7이나 가장 큰 비트는 32비트 값에 들어갈 수 없으므로 제거합니다). 

기본 버전 

uint32_t
crc_impl(uint32_t sum, ptr p, uint32_t len)
{
while (len--)
{
uint8_t byte = *p++;

for (int i = 0; i < 8; ++i)
{
uint32_t osum = sum;

sum <<= 1;

if (byte & 0x80)
sum |= 1 ;

if (osum & 0x80000000)
sum ^= 0x4C11DB7; // the polynominal

byte <<= 1;
}
}
return sum;
}

static const uint8_t zeroes[] = { 0, 0, 0, 0 };

uint32_t
crc(uint32_t sum, ptr p, uint32_t len)
{
return crc_impl(crc_impl(sum, p, len), (ptr)zeroes, 4);
}

 

ROM 바이트 테이블 버전 

static const uint32_t t[256] = {
0x00000000, 0x04c11db7, 0x09823b6e, 0x0d4326d9, 0x130476dc, 0x17c56b6b,
0x1a864db2, 0x1e475005, 0x2608edb8, 0x22c9f00f, 0x2f8ad6d6, 0x2b4bcb61,
0x350c9b64, 0x31cd86d3, 0x3c8ea00a, 0x384fbdbd, 0x4c11db70, 0x48d0c6c7,
0x4593e01e, 0x4152fda9, 0x5f15adac, 0x5bd4b01b, 0x569796c2, 0x52568b75,
0x6a1936c8, 0x6ed82b7f, 0x639b0da6, 0x675a1011, 0x791d4014, 0x7ddc5da3,
0x709f7b7a, 0x745e66cd, 0x9823b6e0, 0x9ce2ab57, 0x91a18d8e, 0x95609039,
0x8b27c03c, 0x8fe6dd8b, 0x82a5fb52, 0x8664e6e5, 0xbe2b5b58, 0xbaea46ef,
0xb7a96036, 0xb3687d81, 0xad2f2d84, 0xa9ee3033, 0xa4ad16ea, 0xa06c0b5d,
0xd4326d90, 0xd0f37027, 0xddb056fe, 0xd9714b49, 0xc7361b4c, 0xc3f706fb,
0xceb42022, 0xca753d95, 0xf23a8028, 0xf6fb9d9f, 0xfbb8bb46, 0xff79a6f1,
0xe13ef6f4, 0xe5ffeb43, 0xe8bccd9a, 0xec7dd02d, 0x34867077, 0x30476dc0,
0x3d044b19, 0x39c556ae, 0x278206ab, 0x23431b1c, 0x2e003dc5, 0x2ac12072,
0x128e9dcf, 0x164f8078, 0x1b0ca6a1, 0x1fcdbb16, 0x018aeb13, 0x054bf6a4,
0x0808d07d, 0x0cc9cdca, 0x7897ab07, 0x7c56b6b0, 0x71159069, 0x75d48dde,
0x6b93dddb, 0x6f52c06c, 0x6211e6b5, 0x66d0fb02, 0x5e9f46bf, 0x5a5e5b08,
0x571d7dd1, 0x53dc6066, 0x4d9b3063, 0x495a2dd4, 0x44190b0d, 0x40d816ba,
0xaca5c697, 0xa864db20, 0xa527fdf9, 0xa1e6e04e, 0xbfa1b04b, 0xbb60adfc,
0xb6238b25, 0xb2e29692, 0x8aad2b2f, 0x8e6c3698, 0x832f1041, 0x87ee0df6,
0x99a95df3, 0x9d684044, 0x902b669d, 0x94ea7b2a, 0xe0b41de7, 0xe4750050,
0xe9362689, 0xedf73b3e, 0xf3b06b3b, 0xf771768c, 0xfa325055, 0xfef34de2,
0xc6bcf05f, 0xc27dede8, 0xcf3ecb31, 0xcbffd686, 0xd5b88683, 0xd1799b34,
0xdc3abded, 0xd8fba05a, 0x690ce0ee, 0x6dcdfd59, 0x608edb80, 0x644fc637,
0x7a089632, 0x7ec98b85, 0x738aad5c, 0x774bb0eb, 0x4f040d56, 0x4bc510e1,
0x46863638, 0x42472b8f, 0x5c007b8a, 0x58c1663d, 0x558240e4, 0x51435d53,
0x251d3b9e, 0x21dc2629, 0x2c9f00f0, 0x285e1d47, 0x36194d42, 0x32d850f5,
0x3f9b762c, 0x3b5a6b9b, 0x0315d626, 0x07d4cb91, 0x0a97ed48, 0x0e56f0ff,
0x1011a0fa, 0x14d0bd4d, 0x19939b94, 0x1d528623, 0xf12f560e, 0xf5ee4bb9,
0xf8ad6d60, 0xfc6c70d7, 0xe22b20d2, 0xe6ea3d65, 0xeba91bbc, 0xef68060b,
0xd727bbb6, 0xd3e6a601, 0xdea580d8, 0xda649d6f, 0xc423cd6a, 0xc0e2d0dd,
0xcda1f604, 0xc960ebb3, 0xbd3e8d7e, 0xb9ff90c9, 0xb4bcb610, 0xb07daba7,
0xae3afba2, 0xaafbe615, 0xa7b8c0cc, 0xa379dd7b, 0x9b3660c6, 0x9ff77d71,
0x92b45ba8, 0x9675461f, 0x8832161a, 0x8cf30bad, 0x81b02d74, 0x857130c3,
0x5d8a9099, 0x594b8d2e, 0x5408abf7, 0x50c9b640, 0x4e8ee645, 0x4a4ffbf2,
0x470cdd2b, 0x43cdc09c, 0x7b827d21, 0x7f436096, 0x7200464f, 0x76c15bf8,
0x68860bfd, 0x6c47164a, 0x61043093, 0x65c52d24, 0x119b4be9, 0x155a565e,
0x18197087, 0x1cd86d30, 0x029f3d35, 0x065e2082, 0x0b1d065b, 0x0fdc1bec,
0x3793a651, 0x3352bbe6, 0x3e119d3f, 0x3ad08088, 0x2497d08d, 0x2056cd3a,
0x2d15ebe3, 0x29d4f654, 0xc5a92679, 0xc1683bce, 0xcc2b1d17, 0xc8ea00a0,
0xd6ad50a5, 0xd26c4d12, 0xdf2f6bcb, 0xdbee767c, 0xe3a1cbc1, 0xe760d676,
0xea23f0af, 0xeee2ed18, 0xf0a5bd1d, 0xf464a0aa, 0xf9278673, 0xfde69bc4,
0x89b8fd09, 0x8d79e0be, 0x803ac667, 0x84fbdbd0, 0x9abc8bd5, 0x9e7d9662,
0x933eb0bb, 0x97ffad0c, 0xafb010b1, 0xab710d06, 0xa6322bdf, 0xa2f33668,
0xbcb4666d, 0xb8757bda, 0xb5365d03, 0xb1f740b4,
};

uint32_t crc(uint32_t sum, ptr p, uint32_t len)
{
while (len--)
{
uint8_t i = (sum >> 24) ^ *p++;
sum = t[i] ^ (sum << 8);
}

return sum;
}

 

RAM 바이트 테이블 버전 

void construct_crc_table(uint32_t poly, void * space)
{
 uint32_t * crc_table = (uint32_t *)space;

 for (uint32_t i = 0; i < 256 ; ++i)
 {
  uint32_t r = i << 24;

  for (int j = 0 ; j < 8 ; ++j)
   r = (r & 0x80000000) ? (r << 1) ^ poly : (r << 1);

  crc_table[i] = r;
 }
}

uint32_t crc_ram_table(void * table, uint32_t sum, ptr p, uint32_t len)
{
 uint32_t * t = (uint32_t *)table;

 while (len--)
 {
  uint8_t i = (sum >> 24) ^ *p++;
  sum = t[i] ^ (sum << 8);
 }

 return sum;
}

 

ROM nibble table 버전 

static const uint32_t t[16] = {
 0x00000000, 0x04c11db7, 0x09823b6e, 0x0d4326d9,
 0x130476dc, 0x17c56b6b, 0x1a864db2, 0x1e475005,
 0x2608edb8, 0x22c9f00f, 0x2f8ad6d6, 0x2b4bcb61,
 0x350c9b64, 0x31cd86d3, 0x3c8ea00a, 0x384fbdbd,
};

uint32_t crc(uint32_t sum, ptr p, uint32_t len)
{
 while (len--) {
  // hi nibble
  sum = t[(sum>>28)^(*p >> 4)]^(sum<<4);
  // lo nibble
  sum = t[(sum>>28)^(*p++ & 0xF)]^(sum<<4);
 }
 return sum;
}

 

RAM nibble table 버전 

void
construct_nibble_table(uint32_t poly, void * space)
{
 uint32_t * crc_table = (uint32_t *)space;
 for (uint32_t i = 0; i < 16 ; ++i) {
  uint32_t r = i << 28;
  for (int j = 0 ; j < 4 ; ++j)
   r = (r & 0x80000000) ? (r << 1) ^ poly : (r << 1);
  crc_table[i] = r;
 }
}

uint32_t crc(void * table, uint32_t sum, ptr p, uint32_t len)
{
 uint32_t * t = (uint32_t *)table;
 while (len--) {
  // hi nibble
  sum = t[(sum>>28)^(*p >> 4)]^(sum<<4);
  // lo nibble
  sum = t[(sum>>28)^(*p++ & 0xF)]^(sum<<4);
 }
 return sum;
}

 

부록 B 

반사/미러링을 위한 코드 

경우에 따라서는 crc가 매칭되도록 하기 위해 바이트를 반사(reflect) 할 필요가 있습니다(이것은 crc가 생성될 때에 반사/미러링 crc 하드웨어를 사용하는 것을 가정했기 때문일 수가 있습니다. 이제 이것을 소프트웨어 상에서 검증해야 하는 것입니다.) 

static uint8_t nibb[] =
 {
   0, // 0 = 0000 = 0000 =  0
   8, // 1 = 0001 = 1000 =  8
   4, // 2 = 0010 = 0100 =  4
  12, // 3 = 0011 = 1100 =  C
   2, // 4 = 0100 = 0010 =  2
  10, // 5 = 0101 = 1010 =  A
   6, // 6 = 0110 = 0110 =  6
  14, // 7 = 0111 = 1110 =  E
   1, // 8 = 1000 = 0001 =  1
   9, // 9 = 1001 = 1001 =  9
   5, // 10 = 1010 = 0101 = 5
  13, // 11 = 1011 = 1101 = D
   3, // 12 = 1100 = 0011 = 3
  11, // 13 = 1101 = 1011 = E
   7, // 14 = 1110 = 0111 = 7
  15  // 15 = 1111 = 1111 = F
};

uint8_t mirror8(uint8_t byte)
 {
  return (nibb[byte & 0xF] << 4) | (nibb[byte >> 4]);
 }

uint16_t mirror16(uint16_t hw)
 {
  return (mirror8(hw & 0xFF) << 8) | mirror8(hw >> 8);
 }

void generate_mirror_byte_table(void * space)
 {
  uint8_t * mirror = (uint8_t *)space;
  
  for (uint16_t i = 0 ; i < 256 ; ++i)
    mirror[i] = (nib[i & 0xF] << 4) | nib[i >> 4];
 }

만일 미러링 테이블을 위해 256 바이트 정도의 여유가 있다면 그대로 사용하시면 됩니다. 만일 이것이 불가능하다면 mirror8을 사용하십시오. RAM 소요량이 없으며, 패널티로 미러링 된 바이트 당 6 사이클 정도가 필요합니다. 

 

부록 C 

초기값을 위한 코드 

일부 CRC 알고리즘에서는 0이 아닌 초기값을 사용하기도 합니다. 표 기반, 그리고 기본 알고리즘에서는 초기 값을 서로 다르게 사용합니다. 그러므로 선택된 CRC 루틴에 대한 초기 호출 시 공급되는 초기값은 같을 수가 없습니다. 

// this is for indirect / prefixed values
// call this with the initial value and use
// the returned value instead of the initial value
// when calling a table driven (but not the basic!)
// crc routine for the first time
uint16_t fixup_table(uint16_t sum)
 {
  uint16_t crc = crc_table[(sum >> 8) & 0xFF];
  crc = crc_table[(crc >> 8) ^ (sum & 0xFF)] ^ (crc << 8);
  return crc;
 }

// this is for direct / non prefixed values
// call this with the initial value and use
// the returned value instead of the initial value
// when calling the basic (but not the table driven!)
// crc routine for the first time
uint16_t fixup_basic(uint16_t init)
 {
  for (uint16_t i = 0 ; i < 16 ; ++i)
  {
   uint16_t bit = init & 1;

   if (bit)
     init ^= 0x1021; // poly, change as needed or make it a parameter

   init >>= 1;

   if (bit)
     init |= 0x8000;
  }
  return init;
 }

 

부록 D 

CRC 표 출력을 위한 코드 

아래 코드는 CRC를 사용하는 프로그램에서 사용하기 위한 것은 아닙니다. 대신, 출력물인 테이블 선언을 생성하기 위해 실행하는 것으로, 이러한 출력물은 CRC를 사용하는 프로그램의 코드 내에 삽입됩니다. 

프로그램은 현 상태에서 바이트 또는 니블 테이블을 출력할 수가 있으며, 이는 16 또는 32 비트 polynomial을 사용하는 것이 가능합니다. 새로운 CRC 알고리즘을 추가하는 방법은 사실 간단합니다. 

  • 명칭을 CrcType enum에 추가합니다. 
  • enum을 사이즈와 polynomial을 설정하는 스위치(switch)에 추가합니다. 

코드는 16 및 32 비트 polynomial 미 16 또는 256 항목의 테이블을 대상으로만 시험된 것입니다. 다른 구성도 가능하나, 어느 정도 코드의 확장이 이루어져야 할 것입니다. 

#include <stdio.h>
#include <stdlib.h>

typedef unsigned char * ptr;
typedef unsigned char uint8_t;
typedef unsigned short uint16_t;
typedef unsigned long uint32_t;

typedef struct crc_config
 {
  uint32_t mCrcMask;
  uint32_t mValueMask;
  uint32_t mPoly;
  uint16_t mElements;
  uint8_t mSize;
  uint8_t mInitialShiftCount;
  uint8_t mBitLimit;
  uint8_t mIndent;
 } crc_config;

typedef enum { kByteTable, kNibbleTable } TableType;
typedef enum { kCrc16, kCrc32 } CrcType;

uint32_t entry(uint32_t i, crc_config const * cc)
 {
  uint32_t r = i << cc->mInitialShiftCount;
  uint32_t m = cc->mCrcMask;
  uint32_t p = cc->mPoly;
  uint8_t l = cc->mBitLimit;

  for (int j = 0 ; j < l ; ++j)
   r = (r & m) ? ((r << 1) ^ p) : (r << 1);

  r &= cc->mValueMask;

  return r;
 }

void fill_in_crc_object(TableType table, CrcType crc, crc_config * cc)
 {
  // setup table type related values
  switch (table)
  {
  case kByteTable: cc->mBitLimit = 8; break;
  case kNibbleTable: cc->mBitLimit = 4; break;
  default:
   printf("'%d' is not a valid table type\n", table);
   abort();
  }

  cc->mElements = (1u << cc->mBitLimit);

  // setup algorithm type related values
  uint8_t size;
  uint32_t poly;

  switch (crc)
   {
   case kCrc16:
    size = 2;
    poly = 0x1021;
    break;

   case kCrc32:
    size = 4;
    poly = 0x4C11DB7;
    break;

 /* add additional crc types here */
   default:
    printf("'%d' is not a valid polynomial type\n", crc);
    abort();
   }

  cc->mSize = size;
  cc->mPoly = poly;
  uint8_t bits = size*8;

  // setup derived values
  // most significant bit set
  cc->mCrcMask           = (1u << (bits-1));

  // all bits set
  cc->mValueMask = (1u << bits)-1;

  // initial shift count
  cc->mInitialShiftCount = bits - cc->mBitLimit;

  // formatting values
  cc->mIndent = 2;
 }

void print_crc_table(crc_config * cc)
 {
  printf("static const uint%d_t t[%d] = {\n",
        cc->mSize*8, cc->mElements);

  char buf[30];

  // create the formatting string for table entries
  sprintf(buf, "0x%%0%d%s", cc->mSize*2, "lx, ");

  uint8_t isNew = 1, count = 0;

  // max number of crc values per row
  uint8_t limit = (80 - cc->mIndent) / (cc->mSize*2 + 4);

   for (uint16_t i = 0 ; i < cc->mElements ; ++i)
   {
    // fix indentation for first row entry
    if (isNew) isNew = !printf("%*s", cc->mIndent, "");

    printf(buf, entry(i, cc));

    // possibly break line
    if (++count >= limit) count = !(isNew = printf("\n"));
   }

   printf("\n};\n");
  }

main()
 {
  crc_config conf, *cc = &conf;
  fill_in_crc_object(kNibbleTable, kCrc16, cc);
  print_crc_table(cc);
  return 0;
 }

 

모든 제품 이름은 해당 소유자의 상표 또는 등록 상표입니다.

죄송하지만, 당사 사이트에서는 Internet Explorer를 지원하지 않습니다.보다 편안한 사이트를 위해 Chrome, Edge, Firefox 등과 같은 최신 브라우저를 사용해 주시길 부탁드립니다.