CRC stuff - npat-efault/musings GitHub Wiki

https://groups.google.com/d/topic/golang-nuts/6HAJOaJOT9c/discussion :

Date: Wed, 12 Nov 2014 02:04:03 -0800 (PST)
From: Nick Patavalis <[email protected]>
To: [email protected]
Subject: Re: CRC32 implementation.

Maybe this goes a bit off-topic, but anyway...

In CRC calculations (regardless of bit-length), apart from the polynomial used, other factors also play a role in the calculated result. Namely:

1. The bit ordering
2. The initial CRC register value
3. The final XOR value (if any)

(1) has to do with what you consider the most significant bit in each byte / word to be. That is, which bit in the CRC word corresponds to the X^0 term. The most usual way to calculate a CRC (what most protocols use) is in bit-reversed order: Bit-31 (for a CRC-32) corresponds to the X^0 term. This has to do with the fact that, often, hardware emits bytes / words LSBit-first, and you want the CRC to be transmitted highest order factor first, and to have neighboring factors kept together. Naturally this is not universal: The are protocols that use CRCs in non-bit-reversed mode.

(2) has to do with what value in the CRC register you start the calculation with. Vanila CRC says it should be 0x0 (the obvious choice). Most protocols, though, use an all-ones value, as it protects an initial streak of zeros in the message better.

(3) has to do with whether you XOR the final calculated CRC value with something (other than 0) or not. Again all ones is the most common case (protects final zero-parts of the message) but not universal.

The CRC32 implementation in the standard library, uses the IEEE polynomial, in bit-reversed order, with initial value 0xFFFFFFFF and final XOR value 0xFFFFFFFF. It is adequate for every protocol that uses the IEEE polynomial and the same calculation same parameters.

Recently I needed a CRC-16 implementation. In the 16-bit case there is a myriad (ok, maybe myriad is an exaggeration, but certainly many) of legacy / proprietary protocols that do CRC calculations in almost every conceivable way. So I needed something a bit more general. I based my code on crc32.go of the standard lib. If you wish you can see the result here:

https://github.com/npat-efault/gohacks/blob/master/crc16/crc16.go

In it you will see how the issues mentioned are reflected in the code (in the CRC16 case, which is not very different that the CRC32 one).

/npat