CODEWITHSUNDEEP
ethernetcrc32
Tushar
Tushar

Reputation: 499

How to combine CRC-32 results?

Let's say I have two numbers X = 0xABC; Y = 0xDE. I want to calculate CRC-32 over Z, which is X concatenated to Y i.e. Z = 0xABCDE.

I have CRC(X) and CRC(Y) available. How can I compute CRC(Z) ?

Upvotes: 6

Views: 2441

Answers (1)

Mark Adler
Mark Adler

Reputation: 112492

Take a look at crc32_combine() in zlib for the approach.

The basic idea is to use the linearity of CRCs. The CRC of 0xABC00 exclusive-or'ed with 0x000DE is the exclusive-or of their corresponding CRCs. If I ignore the pre and post-processing (which I can for reasons that are left to the reader to derive), leading zeros do not change the CRC, so the CRC of 0xDE is the same as the CRC of 0x000DE. So all I need to do is calculate the effect of appending zeros when starting with the CRC of 0xABC, in order to get the CRC of 0xABC00. Then exclusive-or those two CRCs.

crc32_combine() uses matrix multiplication to compute the effect of appending n zeros in O(log(n)) time instead of O(n) time, so combining CRCs is very fast regardless of the lengths of the original messages.

Upvotes: 5

Related Questions