CRC16-CITT - 아두이노에 올리기 위한 C 코드.

개발 관련/기타,연구

CRC16-CITT - 아두이노에 올리기 위한 C 코드.

snoworca 2014. 10. 5. 14:47

우선 CRC 와 CRC CITT 에 대한 설명은 아래 두 사이트에서 볼 수 있다.

CRC(cyclic redundancy check) 에 관한 설명, 위키 링크(클릭)

보통 구글링을 하면 나오는 CRC 코드는 CRC 값 계산을 위한 테이블을 미리 생성하거나 코드에 포함시키기 때문에 아두이노에 올리기에 부담스럽다. 아두이노 UNO 의 메모리 크기는 달랑 2Kbyte 밖에 안 되는데 CRC 값 계산을 위한 테이블은 이론상 512byte 씩이나 되기 때문이다. (실제로는 좀 더 작은 크기를 점유하고 있다.)

SRAM을 직접 연결하거나 메모리 쉴드를 달면 조금 나아지겠지만, 일단 그냥 올리기에는 부담스러운 것이 사실이다. 그래서 인터넷 이곳 저곳에서 긁어온 코드를 조금 느리더라도 아래 코드처럼 직접 계산하도록 하였다. (추후에 시간이 되면 좀 더 빠르게 개선해봐야겠다.)

CRC16 CITT:

// CRC16-CITT Polynomial
#define POLY	0x1021

//아래 주석을 해제하면, 미리 정의된 CRC Table 을 사용한다.
//#define USE_CRC_TABLE 
const unsigned short crc16Table[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
};
  
/**
* CRC Table 의 값을 계산하여 가져온다.
*  만약 USE_CRC_TABLE 이 #define 으로 정의되어 있다면 
* 미리 생성된 CRC 테이블에서 값을 즉시 가져온다.
 * @param index CRC Table 의 인덱스.
 * @return 값.
 */
unsigned short getCRCTableEle(unsigned short index)
{
    #ifdef USE_CRC_TABLE
       return crc16Table[index];
    #else
       unsigned short tableEle  = ((unsigned short)index<<8);
       for(char i=0; i<8; i++)
       tableEle =  (tableEle & 0x8000L)?(tableEle << 1) ^ POLY:(tableEle << 1);
       return tableEle;
    #endif
}

/**
 * 버퍼를 입력 받아 CRC 값을 생성한다.
 * @param buf 버퍼
 * @param len 버퍼의 길이
 * @return CRC 값.
 */
unsigned short genCRC(unsigned char *buf, int len)
{
    unsigned short crc = 0;
    for(int counter = 0; counter < len; counter++)
        crc = (crc<<8) ^ getCRCTableEle(((crc>>8) ^ *buf++)&0x00FF);
    return crc;
}

문득 이 방법이 CRC 테이블을 사용하는 것에 비하여 성능이 어느정도 떨어지는지 조금 궁금하여 아래 테스트 코드를 추가하여 간략하게 테스트를 해보았다.

CRC16 성능 테스트 (Arduino):

void updateCRC(unsigned short *updateCRC, unsigned char value)
{
    (*updateCRC) = (*updateCRC<<8) ^ getCRCTableEle(((*updateCRC>>8) ^ value)&0x00FF);
}

/**
 * 0을 반환하면 값이 정상이다.
 */
unsigned short error(unsigned short acceptedCRC,unsigned short checkCRC) 
{
    updateCRC(&checkCRC, (acceptedCRC & 0xFF00) >> 8);
    updateCRC(&checkCRC, acceptedCRC & 0x00FF);
    return checkCRC;
}

long total = 0, count = 0, startMs = 0, endMs = 0;
unsigned char	sendPayload[BUFFER_SIZE];
unsigned char	receivedPayload[BUFFER_SIZE];
void setup() {                
  Serial.begin(9600);
}
void loop() {
    srand(analogRead(0));
    // 랜덤한 값을 넣는다
    for(int i = 0; i < BUFFER_SIZE; ++i) {
        sendPayload[i] = ((unsigned char)rand() % 0xff);
    }
    unsigned short sendCRC, receivedCRC;
    sendCRC = genCRC(sendPayload, BUFFER_SIZE);
    for(int i = 0; i < BUFFER_SIZE; ++i) 
        receivedPayload[i] = sendPayload[i];
    // 값을 랜덤하게 다르게 한다.
    if(sendPayload[0] % 2 == 0) 
        receivedPayload[rand() % BUFFER_SIZE] = ((unsigned char)rand() % 0xff); 
    startMs = millis();
    receivedCRC = genCRC(receivedPayload, BUFFER_SIZE);    
    endMs = millis() - startMs;
    ++count;
    total += endMs;
    unsigned short errorCode = error(sendCRC, receivedCRC);
    // if(count == 1000) 을 제거하면 값들이 출력되는 것을 볼 수 있다.
    if(count == 1000) {
      Serial.print("\nBuffer length  : ");
      Serial.println(BUFFER_SIZE);
      Serial.print("Latency average : ");
      Serial.println( ((double)total / (double)count),5);
      Serial.print("Last send CRC : 0x");
      Serial.println((const char*)String(sendCRC,HEX).c_str());
      Serial.print("Last received CRC : 0x");
      Serial.println((const char*)String(receivedCRC,HEX).c_str());
      Serial.print("Last received CRC error : ");
      Serial.println((const char*)((errorCode == 0)?"OK":(String("error - 0x") + String(errorCode,HEX))).c_str());
    } 
}

CRC 값을 생성하는 함수에 32, 64, 128, 256, 512 바이트 버퍼 값을 넣어서 실행 시간을 확인하도록 하였다.

하지만, 이 테스트 방법에는 두 가지의 큰 문제점이 있다.

첫 번째로 32byte 부터 64byte 크기의 버퍼를 넣었을 때, CRC 생성 함수 실행 시간이 0ms 가 나올수도 있고 1ms 가 나올수도 있다는 것이다. 아두이노에서 micro 나 nano 시간을 구하기도 어렵다. 그래서 genCRC 함수를 1000번 실행시켜서 그 평균을 구하도록 하였다(...) genCRC 함수 호출이 1ms 미만으로 이루어지는 경우가 많다면 평균 시간이 점점 낮아질 것이다.

두 번째 문제는 결과의 정확도와 신뢰성이다. 이 것을 위해서 CRC 테이블의 모든 값을 훑는 테스트를 하는 것이 가장 좋지만, 대충 성능을 비교하도록 하는 것이기 때문에 간단하게 테스트를 돌려 보았다.

결과는 아래와 같다.

A 는 미리 생성된 CRC 테이블을 사용하지 않은 것이고,

B 는 미리 생성된 CRC 테이블을 사용한 것이다.

A의 바이너리 스케치 사이즈 : 7,478 바이트 (최대 32,256 바이트)

B 의 바이너리 스케치 사이즈 : 7,880 바이트 (최대 32,256 바이트)

402byte 차이가 난다.

예상대로 성능차이가 꽤 많이 생긴다.

하지만 CRC 테이블을 사용하면 그만큼의 메모리를 점유한다는 것도 잊지 말자.

저작자표시