CRC-16 계산방법에 따른 계산속도 비교 – ATMEGA 2560
CRC를 계산하는 방법은 크게 2가지 방법이 있다. 첫 번째 방법은, CRC계산을 곧이 곧대로 정직하게, 꿋꿋하게 처음부터 끝까지 한자리씩 밀어내며 계산하는 방법이다. 두 번째 방법은, 들어올 수 있는 모든 데이터에 대해 미리 CRC연산을 한 표(Lookup Table)를 참조해 가며 계산을 진행 하는 것이다.
그동안 몇 번에 걸친 실험 결과로 사용할 수 있는 메모리가 충분하다면, 계산하는 것 보다 읽어오는게 훨씬 나은 방법이라는 사실은 이미 알고 있었다. 그러던 중, 마이크로칩 스튜디오에 포함된 라이브러리들을 확인하다가 마이크로칩에서 제공하는 CRC-16 계산 라이브러리가 있는 것을 발견했다.
제조사에서 직접 만들어서 배포하는 라이브러리라면 MCU에 가장 최적화된 알고리즘을 사용했을 것이다. 가장 최적화된 알고리즘을 사용한다면, 읽어오는것 보다 더 빠른 결과가 나올 수 있지 않을까? 하는 생각이 머리속을 스쳐 지나갔고, 직접 시험해 보기로 마음을 먹었다.
시험준비
오실로스코프를 이용해 시작 타이밍과 종료 타이밍을 측정하기로 했다. 임의의 디지털 출력 포트 2개를 골라, 코드가 시작되는 순간과 종료되는 순간을 표시해 주면 연산에 걸린 실제 시간을 측정할 수 있을 것이다.
직접 만든 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.623us | 2.3us |
결론
결과는 매우 놀라웠다. 첫 번째는, 사용한 라이브러리에 따라 동작 속도의 차이가 이렇게 클 줄 몰랐고 두 번째는, 내가 짠 허접한 코드가 어셈블리어까지 동원된 제조사 라이브러리의 동작 속도보다 더 빨랐기 때문이다.
동일한 기능을 하는 코드지만, 동작속도는 무려 16배의 차이가 난다. CRC 계산을 사용하는 시리얼 통신을 구현한다고 했을 때, 메시지 길이가 1000Byte면, 어휴.. 동작 시간의 차이는 더 벌어지게 된다. 잘 최적화 된 코드는 그렇지 않은 코드에 비해 압도적인 효율을 보인다. 비록 공부를 겸해서 직접 만들고 구현은 해 보았지만, 왠만한 기능은 잘 뒤져서 나보다 더 똑똑한 사람들이 잘 만들어놓은 라이브러리를 가져다 쓰는게 최선의 방법일 것이다.
그리고 알고리즘을 잘 짜놨다고 해도, 메모리를 써 가며 미리 계산한 값들을 참조해 가며 계산하는게 더 빠르다. 장착된 메모리는 최대한 사용해 주는 것이 성능 향상에 유리하다. 한 번이라도 연산을 줄이면 고스란히 동작속도로 돌아오게 된다. 메모리의 여유가 없다면 어쩔 수 없겠지만, 있으면 최대한 활용하는 방향으로 가는 것이 좋다.
결국, 좋은 라이브러리라는것은 연산을 최소화 하고, 같은 연산을 하더라도 걸리는 시간을 최소화 하는 것이다. 결국 수학적 능력이 필요하다. 식을 간소화 해서 정리하는 방법을 아는것은 좋은 알고리즘을 만드는데에 필수적이다. 결국, 이놈의 수학은 끝까지 내 발목을 잡아댄다
🔄 갱신 내역
- — 최초 게시 (http://i.am/eqmaker)
- — 블로그 이전 및 1차 수정
- — 블로그 이전 및 2차 수정