ATMEGA 2560의 CRC-16 계산과 처리 속도 비교

테이블 참조, 기본제공 함수, 직접만든 함수의 CRC-16 계산 속도를 비교해 본다.

CRC 삽질 어언 한달.. ㅜㅜ
직접 만든 CRC-16 계산기와
Microchip 에서 제공하는 CRC-16 계산 라이브러리
그리고 전통적인 방법의 테이블 기반 CRC-16 계산방법의 계산 결과 차이를 알아보기 위해 16MHz ATMETA 2560에서 CRC 연산을 수행해 보았다.

직접 만든 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;
}

Microchip 제공 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바이트의 문자열에 대한 CRC 계산 결과는?

@ATMEGA 2560 16MHz	총 소요시간	바이트당 소요시간
직접 만든거	193.122us	38.6us
Microchip 라이브러리	15.498us	3.1us
테이블 기반	11.623	2.3us

결론

1. 똑똑한 사람들이 만든, 훌륭한 라이브러리들을 잘 찾아서 쓰자.
2. 잘 최적화 된 어셈블리 코드는 성능향상에 최고다.
3. 동일한 기능을 하지만, 동작속도가 16배 차이가 난다.
4. 메모리가 허락하는 한, 계산보다는 저장된 값 불러다 쓰는게 이득이다.
5. 이놈의 수학은 끝까지 내 발목을 잡는다... ㅜㅜ

이 글은 2022. 1. 12. 10:15 에 작성 되었습니다.