CRC32 vs CRC32C?

Question

What is the difference of CRC32 and CRC32C? I know CRC32 for a long time, but just heard CRC32C today. Are they basically the same method (i.e. both results in the same hash for a given data)?

Solution

The CRC32 found in zip and a lot of other places uses the polynomial 0x04C11DB7; its reversed form 0xEDB88320 is perhaps better known, being often found in little-endian implementations.

CRC32C uses a different polynomial (0x1EDC6F41, reversed 0x82F63B78) but otherwise the computation is the same. The results are different, naturally. This is also known as the Castagnoli CRC32 and most conspicuously found in newer Intel CPUs which can compute a full 32-bit CRC step in 3 cycles. That is the reason why the CRC32C is becoming more popular, since it allows advanced implementations that effectively process one 32-bit word per cycle despite the three-cycle latency (by processing 3 streams of data in parallel and using linear algebra to combine the results).

Comments

[jww]

Is there a way to convert between CRC32 and CRC32C? Looking at some kernel patches with comments, it may be possible but its not explained.

[DarthGizka]

@jww: If it is possible at all then it must be at least as complicated as stitching CRCs for consecutive blocks together (like computing a 'virtual preimage'). I've never seen an algorithm like that, although its utility would be obvious (like using the hardware instructions for CRC32C and converting the result to the standard (zip) CRC32). The best way to get answers quickly would be to post this as a question in its own right. My +1 is a given. ;-)

[ZachB]

Minor: the crc32 instruction can process 8 bytes (64 bits), so with its 3-cycle latency, the sequential throughput is ~2.67 bytes/cycle, and the optimal 3x parallel version is close to 8 bytes/cycle.

[Hi-Angel]

Worth noting the instruction is part of SSE4.2 .