Non-math-geek needs help with CRCs (binascii.crc32)

[nobody]

1) Does anyone know if the CRC32 algorithm in binascii has a name? There
seem to be a TON of different CRC32 methods; different polynomials,
different byte orders, different seeds, some flip the bits and some XOR the
result with something else.

I've been looking around and a lot of documents (RFCs, etc) refer to ISO3309
and/or ITU-T V.42 (neither of which appear to be available without paid
access), yet are often incompatible with each other. So unless they're
lying, I assume ISO3309 allows for the above variations, and specifying an
ISO3309 CRC32 doesn't narrow it down any.

2) With Python 2.4 and its signed hex(), what's the 'best'/shortest
(preferably one operation, without any if x < 0 business) way to get an
unsigned 32bit CRC?


Thanks all.

 

[Nick Craig-Wood]

1) Does anyone know if the CRC32 algorithm in binascii has a name? There
seem to be a TON of different CRC32 methods; different polynomials,
different byte orders, different seeds, some flip the bits and some XOR the
result with something else.

I've been looking around and a lot of documents (RFCs, etc) refer to ISO3309
and/or ITU-T V.42 (neither of which appear to be available without paid
access), yet are often incompatible with each other. So unless they're
lying, I assume ISO3309 allows for the above variations, and specifying an
ISO3309 CRC32 doesn't narrow it down any.

Look here

http://www.ross.net/crc/

and in particular here

http://www.repairfaq.org/filipg/LINK/F_crc_v3.html

For Ross N. Williams's thoughts on CRCs. Well worth reading IMHO.
You'll find interesting the section on the different way each CRC can
be used (reversed, reflected etc).

If you have a sample of data, its usually pretty easy to work out
which CRC it does actually use by trial and error. You can use the
code Ross provides to help.

 

[Peter Hansen]

If you have a sample of data, its usually pretty easy to work out
which CRC it does actually use by trial and error. You can use the
code Ross provides to help.

Probably _much_ easier just to check the source. (It's not
in Python, though, it's in the C source this time...)

 

[nobody]

http://www.ross.net/crc/

That doesn't seem to mention anything about poly $EDB88320, which is the
code I'm trying to a) be compatible with, b) define for future developers so
they don't have to go through this whole mess. It appears whatever Python
uses is compatible, but stating the poly by itself doesn't mean anything.

Somehow, depending on how the numbers are massaged, the old code based on
$EDB88320 is compatible with what the above site documents as $04C11DB7.

This is all very confusing..

 

[Tim Roberts]

That doesn't seem to mention anything about poly $EDB88320, which is the
code I'm trying to a) be compatible with, b) define for future developers so
they don't have to go through this whole mess. It appears whatever Python
uses is compatible, but stating the poly by itself doesn't mean anything.

Somehow, depending on how the numbers are massaged, the old code based on
$EDB88320 is compatible with what the above site documents as $04C11DB7.

Did you notice that those two numbers are mirror images of each other?
Could just be a difference in interpretation.

 

[nobody]

Somehow, depending on how the numbers are massaged, the old code based on

Did you notice that those two numbers are mirror images of each other?
Could just be a difference in interpretation.

How does one get the same result with a reflected and non-reflected
algorithm using the exact same input? Do non-hardware (UART)
implementations of the reflected algorithm ($EDB88320) reverse the data
bytes as part of the calculation to compensate?

 

[Tim Roberts]

How does one get the same result with a reflected and non-reflected
algorithm using the exact same input?

Well, what I was saying was that perhaps the two algorithms are doing their
computations in the opposite order. It's just suspicious that they are
reflections of each other.

 

[nobody]

Somehow, depending on how the numbers are massaged, the old code based
on

Well, what I was saying was that perhaps the two algorithms are doing their
computations in the opposite order. It's just suspicious that they are
reflections of each other.

Errr... according to the document referenced earlier, the reflected
algorithm is due to hardware UARTs supplying the bits in reverse order, so
hardware CRC implementations started doing their calculations in reverse,
hence the back-arsewards $EDB88320 poly. However, pretty much every
software based algorithm I've seen up to recently has been the reversed
one.. with normal data.. so no need for the backwards poly.. so I dunno WTF
is going on there.