테이블 참조 기법을 사용한 CRC 계산 속도와, Microchip에서 제공하는 CRC 계산 라이브러리, 그리고 직접 만든 CRC 계산 함수의 처리 속도를 비교해 본다.
CRC를 계산하는 방법은 크게 2가지 방법이 있다. 첫 번째 방법은, CRC계산을 곧이 곧대로 정직하게, 꾿꾿하게 처음부터 끝까지 한자리씩 밀어내며 계산하는 방법이다. 두 번째 방법은, 들어올 수 있는 모든 데이터에 대해 미리 CRC연산을 한 표(룩업 테이블)를 참조해 가며 계산을 진행 하는 것이다.
그동안 몇 번에 걸친 실험 결과로, 메모리가 충분 하다면 계산보다는 읽어오는게 훨씬 나은 선택이라는 사실은 이미 알고 있었다. 그러던 중, 마이크로칩 스튜디오의 소스들을 보다가, 마이크로칩에서 제공하는 CRC-16 계산 라이브러리가 있는 것을 발견했다. 이 MCU를 직접 만든 사람들이 만들어 놓은 알고리즘이라 한다면, 다른 결과가 나올 수 있지 않을까? 하는 생각이 머리속을 스쳐 지나갔고, 직접 시험해 보기로 마음을 먹었다.
시험준비
직접 만든 CRC-16 계산기
uint16_t CRC16_Compute(uint8_t *datastream, uint16_t numberofbyte, uint16_t poly, uint16_t initval)
{
for (uint16_t i=0; i<numberofbyte+2; i++)
{
for (uint8_t j=8; j>0; j--)
{
if (initval & 0x8000)
{
initval = initval << 1;
initval = (((i>=numberofbyte) ? 0 : datastream[i]) & (1<<(j-1))) ? (initval | 1) : initval;
initval = initval ^ poly;
}
else
{
initval = initval << 1;
initval = (((i>=numberofbyte) ? 0 : datastream[i]) & (1<<(j-1))) ? (initval | 1) : initval;
}
}
}
return initval;
}
마이크로칩 제공 CRC-16 라이브러리
Copyright (c) 2002, 2003, 2004 Marek Michalkiewicz
Copyright (c) 2005, 2007 Joerg Wunsch
Copyright (c) 2013 Dave Hylands
Copyright (c) 2013 Frederic Nadeau
All rights reserved.
_crc_xmodem_update(uint16_t __crc, uint8_t __data)
{
uint16_t __ret; /* %B0:%A0 (alias for __crc) */
uint8_t __tmp1; /* %1 */
uint8_t __tmp2; /* %2 */
/* %3 __data */
__asm__ __volatile__ (
"eor %B0,%3" "\n\t" /* crc.hi ^ data */
"mov __tmp_reg__,%B0" "\n\t"
"swap __tmp_reg__" "\n\t" /* swap(crc.hi ^ data) */
/* Calculate the ret.lo of the CRC. */
"mov %1,__tmp_reg__" "\n\t"
"andi %1,0x0f" "\n\t"
"eor %1,%B0" "\n\t"
"mov %2,%B0" "\n\t"
"eor %2,__tmp_reg__" "\n\t"
"lsl %2" "\n\t"
"andi %2,0xe0" "\n\t"
"eor %1,%2" "\n\t" /* __tmp1 is now ret.lo. */
/* Calculate the ret.hi of the CRC. */
"mov %2,__tmp_reg__" "\n\t"
"eor %2,%B0" "\n\t"
"andi %2,0xf0" "\n\t"
"lsr %2" "\n\t"
"mov __tmp_reg__,%B0" "\n\t"
"lsl __tmp_reg__" "\n\t"
"rol %2" "\n\t"
"lsr %B0" "\n\t"
"lsr %B0" "\n\t"
"lsr %B0" "\n\t"
"andi %B0,0x1f" "\n\t"
"eor %B0,%2" "\n\t"
"eor %B0,%A0" "\n\t" /* ret.hi is now ready. */
"mov %A0,%1" "\n\t" /* ret.lo is now ready. */
: "=d" (__ret), "=d" (__tmp1), "=d" (__tmp2)
: "r" (__data), "0" (__crc)
: "r0"
);
return __ret;
}
직접 만든 테이블 기반 CRC-16 계산기
uint16_t CRC16_get(uint8_t *datastream, uint16_t numberofbyte, uint16_t *crctbl)
{
uint16_t rtn=0;
for (uint16_t i=0; i<numberofbyte; i++)
rtn = ((rtn << 8) ^ crctbl[ ((rtn>>8) ^ (0xff & datastream[i])) ]);
return rtn;
}
시험 결과
{0x10, 0x20, 0x30, 0x40, 0x50} 라는 동일한 5바이트의 문자열을 입력으로 주어, 계산을 완료하는데 걸리는 시간을 오실로스코프를 이용해 측정 했다.
| @ATMEGA 2560 16MHz | 총 소요시간 | 바이트당 소요시간 |
| 직접 만든거 | 193.122us | 38.6us |
| Microchip 라이브러리 | 15.498us | 3.1us |
| 테이블 기반 | 11.623 | 2.3us |
결론
결과는 매우 놀라웠다. 첫 번째는, 사용한 라이브러리에 따라 동작속도의 차이가 이렇게 클 줄 몰랐고 두 번째는, 내가 짠 허접한 코드가 어셈블리어까지 동원된 라이브러리의 동작 속도보다 더 빨랐기 때문이다.
동일한 기능을 하는 코드지만, 동작속도는 무려 16배의 차이가 난다. CRC 계산을 사용하는 시리얼 통신을 구현한다고 했을 때, 메시지 길이가 1000Byte면, 어휴.. 동작 시간의 차이는 더 벌어지게 된다. 잘 최적화 된 코드는 그렇지 않은 코드에 비해 압도적인 효율을 보인다. 비록 공부를 겸해서 직접 만들고 구현은 해 보았지만, 왠만한 기능은 잘 뒤져서 나보다 더 똑똑한 사람들이 잘 만들어 놓은 라이브러리를 가져다 쓰는게 최선의 방법일 것이다.
그리고 알고리즘을 잘 짜 놨다고 해도, 메모리를 써 가며 미리 계산한 값들을 참조해 가며 계산하는게 더 빠르다. 장착된 메모리는 최대한 사용해 주는 것이 성능 향상에 유리하다. 한 번 이라도 연산을 줄이면 고스란히 동작속도로 돌아오게 된다.
좋은 라이브러리라고 하면, 연산을 최소화 하는 방법일 것이다. 결국 수학적 능력이 필요하다. 식을 간소화 해서 정리하는 방법을 알아야 좋은 알고리즘을 만들 수 있는데, 이놈의 수학은 끝까지 내 발목을 잡아댄다
작성 : 2022. 1. 12. 10:15 / 수정 : 2024. 12. 06