CRC-32 결과를 결합하는 방법은 무엇입니까?

Question

두 개의 숫자 X = 0xABC가 있다고 가정 해 보겠습니다. Y = 0xDE. Z에 대해 CRC-32를 계산하려고합니다. X는 Y와 연결되어 있습니다 (즉, Z = 0xABCDE).

나는 CRC (X)와 CRC (Y)를 사용할 수 있습니다. CRC (Z)는 어떻게 계산합니까?

Answer 1

crc32_combine()을 zlib에서 살펴보십시오.

기본적인 아이디어는 CRC의 선형성을 사용하는 것입니다. 0xABC00의 CRC는 0x000DE과 배타적이며 - 해당 CRCs의 배타적 논리합입니다. 사전 및 사후 처리 (독자가 추출해야하는 이유로 할 수 있음)를 무시하면 앞에 오는 0은 CRC를 변경하지 않으므로 0xDE의 CRC는 0x000DE의 CRC와 같습니다. CRC가 일 때 0xABC00의 CRC를 얻으려면 0을 더하는 효과를 계산하면됩니다. 그런 다음 두 개의 CRC를 배제하십시오.

crc32_combine()

가 O에서 N 0을 추가의 효과를 계산하기 위해 행렬 곱셈을 사용한다 (로그 ( N))는 시간이 아닌 O ( N) 시간 때문에 결합의 CRC는 관계없이 길이가 매우 빠르고 원래 메시지.