체크섬 계산 디버깅

개요 

CRC:는 오류가 발생하기 참 쉽습니다. 정확한 바이트 시퀀스를 정확한 순서대로 처리하지 않으면 안 됩니다. 일반적인 CRC 알고리즘에서 한 가지 문제가 되는 부분이 바로 해답에 근접해 있는지 어떤 지를 알 수가 없다는 것입니다. 

만일에 polynomial 0x1021을 사용하여 0x1000-0x3FFF을 체크섬 해야 하는데 실제로는  polynomial 0x1201을 사용해  0x0100-0x3FFF을 체크섬 하게 되면 결과가 다르게 나타나는 것입니다. 그러면 두 가지 중에 하나의 에러가 발생하고 새로운 결과값을 얻게 됩니다. 이 결과값 역시 정확하지 않은 값이지만 해당 값이 원하는 값에 근접해 있는지의 여부를 전혀 알려주지 않습니다. 일치하지 않는다는 사실 만 알려주며, 이것 이외에는 아무런 정보도 얻을 수가 없습니다. 

흔히 발생하는 문제점, 그리고 이럴 해결하는 방법은 다음과 같습니다. 

1. 외부 체크섬 범위의 검증 및 프로그램 체크섬이 무엇과 매칭되는지 확인 

체크섬을 생성하는 툴에서는 해당 체크섬을 생성하는 데에 사용된 범위가 무엇인지를 알려 줄 필요가 있습니다. IAR ILINK 링커와 ielftool 툴은 모두 이러한 정보를 제공하고 있습니다. 만일에 알려주는 범위가 0x40-0x3FFB,0x4000-0x7FFF 이라고 한다면, 이들 바이트를 정확하게 체크섬 해야 합니다. 0x40-0x7FFF 이나 다른 바이트를 체크섬 해서는 안 되는 것입니다. 또 어드레스 0x3FFC-0c3FFF 상의 byte 들은 CRC로부터 배제되어 있어야만 하므로 확인이 필요합니다. 

2. 체크섬가 동일한 polynomial을 사용하는지 검증 

두 가지 체크섬에서 서로 다른 polynomial를 동일한 체크섬 범위 상에서 사용하게 되면, 서로 일치 하지 않는 것이 됩니다. CRC-16의 polynomial 값은 0x1021로 실제로는 0x11021 이지만 가장 큰(significant) 1이 16 비트에는 맞아 들어가지 않으므로 제거됩니다. 다른 표준화 CRC 값에 대해서도 마찬가지입니다. X-비트 polynomial 내의 비트 X가 설정되지만 polynomial의  X-비트 표현에는 포함되지 않습니다. 맞아 들어가지 않기 때문입니다. (bit 0 ~ bit X는 X+1 비트를 필요로 합니다. 따라서 비트 X는 X 비트 안에 들어갈 수가 없는 것입니다.) 

경우에 따라서는 polynomial가 기존의 수학적 polynomial로 표시되기도 합니다. x에서 무언가의 제곱 + x에서 이보다 낮은 제곱 등이지요. 이러한 경우 polynomial는 각각의 x가 지니는 지수(exponent)를 bit index로 하고, 해당 비트를 1로 둠으로써 해당하는 16진수로 변환할 수가 있습니다. 예: x ^ 16 + x ^ 12 + x ^ 5 + 1. 여기서 사용하는 비트는 16, 12, 5, 0 입니다. 0x10000 + 0x1000 + 0x20 + 0x1 = 0x11021 = 0x1021 = CRC-16 

3. 체크섬이 반사/미러링을 동일한 방식으로 view 하고 있는지 검증 

CRC 알고리즘에서는 가끔 씩 반사/미러링을 사용하기도 합니다. 미러링/반사는 바이트 내의 비트 순서를 반대로 하는 것입니다. 

Examples: 
mirror(0x1) = 0x80 
mirror(0x17) = 0xE8 
mirror(0xE2) = 0x47 
mirror(mirror(x)) = x 

하나의 차차차에서 반사를 사용하고 다른 하나는 사용하지 않는다고 할 경우, 대부분의 경우는 체크섬이 서로 일치하지 않습니다(회문구조 비트 시퀀스를 지니는 바이트도 바이트 시퀀스 내에 포함될 수가 있습니다.) CRC 알고리즘에서는 효과적으로 서로 다른 바이트 시퀀스를 구분해 낼 수가 있기 때문입니다. 반사/미러링은 통상적으로 미러링 테이블을 통해 처리합니다. 미러링 테이블은 256 바이트 행렬로, 각각의 인덱스에 속하는 바이트 내에 해당 인덱스의 역순(reverse)도 포함되어 있습니다. 이어서 CRC 코드에서는 미러 테이블 내에서 바이트를 lookup 합니다. 그리고 바이트 대신 테이블 엔트리를 CRC 계산에 대신 사용합니다. 

미러링/반사에 있어 한 가지 문제점은 이를 사용하면서도 미러링/반사를 사용하는지 자체를 알지 못하는 사태가 발생할 수 있다는 점입니다. 반사/미러링에 사용되는 지의 여부를 파악하기 위한 가장 쉬운 방법은 두 종류를 모두 써 보고, 그 두 결과가 매칭되는 지를 확인해 보는 것입니다. 

4. 알고리즘 내 추가 바이트 투입 

테이블 기반의 알고리즘을 사용하지 않는 경우에는 바이트 시퀀스를 처리한 다음에 추가 0-바이트를 사용해야 할 수가 있습니다. 체크섬 심볼 내의 각 바이트 당 하나의 0-바이트가 필요합니다. 테이블 기반의 알고리즘을 사용하는 경우, 바이트를 추가할 필요는 없습니다. 좀 더 자세한 내용은 Ross N. Williams의 "A PAINLESS GUIDE TO CRC ERROR DETECTION ALGORITHMS"를 참고하세요. 

5. 정확한 어드레스 공간에서 바이트 읽기 

참고: 이 부분은 프로세서 상에 복수의 어드레스 공간이 존재할 때에만 해당됩니다. 

정확한 어드레스 범위를 처리한다고 하더라도 어드레스 공간이 잘못되어 있는 경우 에러 발생의 원인이 될 수가 있습니다. CRC 알고리즘에서 사용하는 포인터가 반드시 정확한 타입의 것인지 확인하십시오. 그리고 사용되는 포인터는 정확한 어드레스 공간을 지시하고 있어야 합니다. 포인터 선언 시 다음과 같이 메모리 specifier를 사용해야 할 수도 있습니다. 

typedef __code unsigned char * CodePtr; 
 
uint16_t 
crc(uint16_t sum, CodePtr p, uint32_t len) 
{ 
. 
. 
. 
} 

6. “큰”(big) 범위에 “작은”(small) 포인터를 사용할 때에는 주의 

참고: 이것은 포인터의 종류가 여러가지가 있으며, 이중 최소한 하나가 다른 하나 이상의 메모리보다 처리할 수 있는 메모리 양이 적을 때에만 해당됩니다. 

전체 메모리에 도달할 수가 없는 포인터를 사용하고 있는 경우(대표적으로 어드레스 메모리가 64k를 초과하는 시스템에서 __near 포인터를 사용하는 경우), 마지막 어드레스에 도달하면 문제가 발생할 수가 있습니다. 16비트 포인터의 값이 0xFFFF이고, 값이 증가하면 0x10000 대신 0x0이 됩니다. 그리고 당연히, 최종적으로 잘못된 바이트가 체크섬 됩니다. 

0x4000-0x27FFF을 체크섬 하고 싶은 경우에는 모든 어드레스에 도달할 수가 있는 포인터를 써야 합니다. 작은 포인터 값을 증가시키고 참조 해제하는 과정을 0x24000 번 반복하는 것으로는 부족한 것입니다. 0x4000에서 시작하는 __near 포인터를 사용하는 경우, 범위 0x4000-0XFFFF, 0x0-0xFFFF, 0x0-0x7FFF가 체크섬 되며, 애초에 기대했던  0x4000-0x27FFF는 체크섬 되지 않습니다. 대개의 경우는 __far 또는 __huge 포인터를 사용하는 것으로 충분합니다. __near 포인터를 사용하여 0x10000 및 0x20000에서 발생하는 스위칭을 모종의 다른 방법을 통해 처리하는 방안도 있을 것이나, 더 큰 포인터를 사용하는 편이 상대적으로 안전할 것입니다. 

그럼에도 불구하고 64k 바이트 이상의 체크섬을 사용하고자 하는 것은 모종의 방법으로 64k 한계를 넘는 상황을 처리해야 한다는 것을 의미합니다. 

7. 처음에는 작게 

매칭 대상 체크섬을 얻고자 할 시에는 가급적 처음에는 작은 예시로 시작하는 것이 좋습니다. 하나의 바이트는 여러 측면에서 취급이 더 용이합니다. 테이블 기반의 버전에서는 lookup 한 번이면 되며, 클래식 버전에서는 비트 조작 반복을 한 번 만 수행하면 됩니다. 한계(boundary)를 초월하는 일도 발생하지 않으며, 두 개의 체크섬이 모두 동일한 byte를 사용하고 있는지도 쉽게 확인이 가능합니다. 

만일 polynomial, 초기 값, 미러링/반사 접근법 및 어드레스 공간이 모두 같은 경우, 체크섬은 동일합니다. 그러나 일부 경우에서는 최종 체크섬이 하나의 값으로 XOR: 되거나, 1 또는 2의 여수(complemented)가 되기도 합니다. 

1 바이트 체크섬가 매칭되는 경우, 체크섬을 확대하여 더 많은 바이트를 포함하도록 할 수도 있습니다. 이러한 과정을 통해 사용한 하나의 바이트가 특수한 성질을 지녀 우연히 체크섬이 매칭된 것은 아닌지를 확인해 볼 수가 있습니다. (예를 들여 0은 반사 관련으로는 미스매치(mismatch)를 탐지해 내지 못합니다.) 만일 복수 바이트 체크섬이 매칭이 되지 않지만 단일 바이트는 단일 바이트 체크섬으로 돌아가는 경우, 다른 바이트를 반드시 사용하도록 합니다. 

약간 더 큰 샘플을 정해, 일치할 시에는 전체 범위로 확장할 수가 있습니다. 만일 작은 샘플이 매칭되는 경우이지만 더 큰 것은 존재하지 않을 시에는 페이지 바운더리 문제(page boundary)가 있는 것은 아닌지 확인해 봐야 합니다(16비트 어드레스 바운더리를 넘어버리는 문제.) 그렇지 않으면 체크섬 위치(체크섬은 대개의 경우 체크섬에 포함되지 않습니다)에 문제가 있거나, 혹시 임의의 어드레스에 예상하지 못했던 내용이 들어있었던 것은 아닌지 확인해 봅니다. (이러한 어드레스는 체크섬 해서는 안 됩니다.) 

8. 특수 케이스 

물론 표준 방식이 통하지 않는 특수한 경우도 존재합니다(char 포인터에서 두 어드레스 사이의 바이트를 읽어 들이는 경우 등). 이러한 경우에는 표준 방식에서 어느정도 벗어난 방식을 사용해야 합니다. 여기서는 assembler help 루틴을 통해서 예상되는 순서대로 바이트에 접근할 필요가 있을 수 있습니다. 

또 다른 채움 패턴(fill pattern)을 쓰는 것도 도움이 됩니다. 상당수의 경우는 채움 패턴 0xFF을 이용합니다. 만일에 아키텍쳐 상으로 4 번에 한 번씩 바이트를 0으로 읽어 들이 경우(일부 아키텍쳐에서는 ‘고스트 바이트’를 사용), 체크섬은 절대로 하나의 체크섬(오브젝트 파일에서 생성된 것)로 매칭되지 않습니다. 0xFF을 고스트 바이트로 사용하며, 하드웨어 상에서 실제로 바이트를 읽어 들이는 부분에서는 고스트 바이트로 0x0을 사용할 것입니다. 이 경우 채움 문자열 0xFFFFFF00(그리고 해당 채움 작업이 4바이트로 정렬된 어드레스에서 시작)을 사용하는 경우, 서로 다른 체크섬 알고리즘에서 동일한 바이트가 나타나도록 해 줄 것입니다. 

만일 체크섬 범위 내에 예상하지 못한 내용을 지닌 바이트가 존재하는 경우(이유 불문). 이러한 바이트는 체크섬에서 배제하여야 합니다. 

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