CRC32 of an appended block

Question

I'm computing CRC32 in a rolling fashion on the contents of a file. If the file has 3 blocks ABC, CRC32 is computed linearly CRC(CRC(CRC(A, 0xffffffff), B), C). This is done with code that looks like:

uint32_t crc32(unsigned char const *buf, uint32_t buf_size, uint32_t crc32) {
     for (int i = 0; i < buf_size; i++)
         crc32 = (crc32 >> 8) ^ table[(crc32 ^ buf[i]) & 0xff];
     return crc32;
 }

Even though I write entire content ABC at once, computing the CRC as above(which gets verified at the server), read is normally done on a specific block. So, I would like to track CRC32 of each individual block as it is written.

Based on my limited understanding of how CRC32 polynomial works,

A mod G  = CRC1
AB mod G = CRC2

If I want CRC32 of B, I'm thinking following should do the trick:

(CRC2 - CRC1) mod G  
or
(CRC2 ^ CRC1) mod G

Of course, following code doesn't work.

uint32_t
crc32sw_diff(uint32_t crc1, uint32_t crc2)
 {
     uint32_t delta = crc1 ^ crc2;
     return crc32(&delta, 4, 0xffffffff);
 }

Other option is probably to compute CRC32 of individual blocks and combine it with something like zlib's crc32_combine() to get CRC32 of entire file.

Nothing wrong, I just happen to stumble upon it when my 'diff' method didn't work and was just curious how to fix the diff. — srai, Oct 17 '22 at 18:24
It is not clear from your question what you're trying to do. Do you want the CRC of `B`, given the CRCs of `A` and `AB`? — Mark Adler, Oct 17 '22 at 21:27
Correct. Likewise, given the CRC of AB and ABC, I would like to get the CRC of C and so on. — srai, Oct 18 '22 at 00:11

score 1 · Accepted Answer · answered Oct 18 '22 at 03:25

See this answer for how CRC combination works. CRC(A) ^ CRC(B) is not equal to CRC(AB). However (for pure CRCs) using the notation that AB is the concatenated message of A followed by B, and 0 meaning an equal length message will all zeros, then CRC(A0) ^ CRC(0B) is equal to CRC(AB).

This also means that CRC(A0) ^ CRC(AB) == CRC(0B). Since CRC(0B) == CRC(B) (feeding zeros doesn't change a pure CRC), you can find it using crc32_combine() from zlib.

So, crc32_combine(crca, crcab, lenb) will return crcb.

CRC32 of an appended block

1 Answers1