CRC32 implementation.

[Russel Winder]

The documentation for the hash/crc32 package states:


// Far and away the most common CRC-32 polynomial.
// Used by ethernet (IEEE 802.3), v.42, fddi, gzip, zip, png,
mpeg-2, ...

http://golang.org/pkg/hash/crc32/


My understanding is that CRC32/MPEG-2 is not the same as the CRC32 used
in zip and elsewhere. Zip CRC32 is little endian and uses a final flip
mask. MPEG-2 CRC32 is big endian and no final flip mask.

Is the claim here in the Go documentation that this Go CRC2
implementation is appropriate backed by tests for use with MPEG-2?
Looking at the crc32_test.go file I would say no and that the claim of
the comment is actually wrong.

cf. http://reveng.sourceforge.net/crc-catalogue/all.htm

--
Russel.
=============================================================================
Dr Russel Winder t: +44 20 7585 2200 voip: sip:russel...@ekiga.net
41 Buckmaster Road m: +44 7770 465 077 xmpp: rus...@winder.org.uk
London SW11 1EN, UK w: www.russel.org.uk skype: russel_winder

[Nigel Tao]

On Wed, Nov 12, 2014 at 12:50 AM, Russel Winder <rus...@winder.org.uk> wrote:
> My understanding is that CRC32/MPEG-2 is not the same as the CRC32 used
> in zip and elsewhere. Zip CRC32 is little endian and uses a final flip
> mask. MPEG-2 CRC32 is big endian and no final flip mask.

I haven't looked at CRC32 (as in the algorithm, not Go's
implementation) in a while, but it could be that Go's crc32.IEEE is
merely an (endian-independent) polynomial. For MPEG-2, crc32.IEEE
could still apply as:

h = crc32.ChecksumIEEE(data)
// MPEG-2 is big-endian.
b := [4]byte{
uint8(h>>24),
uint8(h>>16),
uint8(h>>8),
uint8(h>>0),
}

I don't know if that code is right for MPEG-2, but if it is, I don't
see anything wrong with the doc comment for crc32.IEEE.

If you can share code that implements what MPEG-2 needs, then I can be
more specific about whether or not the crc32.IEEE doc comment is
wrong.

[Nigel Tao]

On Wed, Nov 12, 2014 at 4:11 PM, Nigel Tao <nige...@golang.org> wrote:
> If you can share code that implements what MPEG-2 needs, then I can be
> more specific about whether or not the crc32.IEEE doc comment is
> wrong.

Ah, on further reading,
http://www.lammertbies.nl/forum/viewtopic.php?t=1398 suggests that
you're right. I've sent out https://codereview.appspot.com/170520043

[Nick Patavalis]

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

On Tuesday, November 11, 2014 3:51:19 PM UTC+2, Russel Winder wrote:

The documentation for the hash/crc32 package states:


// Far and away the most common CRC-32 polynomial.
// Used by ethernet (IEEE 802.3), v.42, fddi, gzip, zip, png,
mpeg-2, ...

http://golang.org/pkg/hash/crc32/


My understanding is that CRC32/MPEG-2 is not the same as the CRC32 used
in zip and elsewhere. Zip CRC32 is little endian and uses a final flip
mask. MPEG-2 CRC32 is big endian and no final flip mask.

Is the claim here in the Go documentation that this Go CRC2
implementation is appropriate backed by tests for use with MPEG-2?
Looking at the crc32_test.go file I would say no and that the claim of
the comment is actually wrong.

cf.  http://reveng.sourceforge.net/crc-catalogue/all.htm

--
Russel.
=============================================================================

Dr Russel Winder      t: +44 20 7585 2200   voip: sip:russ...@ekiga.net

[Russel Winder]

http://reveng.sourceforge.net/crc-catalogue/all.htm

provides some lovely gory detail ;-)

Not to mention the 1 test case.

There is also: http://www.tty1.net/pycrc/index_en.html