Re: Uh, this is *not* a 64-bit CRC ...

On Mon, Mar 05, 2001 at 02:00:59PM -0500, Tom Lane wrote:
> ncm(at)zembu(dot)com (Nathan Myers) writes:
> > The CRC-64 code used in the SWISS-PROT genetic database is (now) at:
> > ftp://ftp.ebi.ac.uk/pub/software/swissprot/Swissknife/old/SPcrc.tar.gz
>
> > From the README:
>
> > The code in this package has been derived from the BTLib package
> > obtained from Christian Iseli <chris(at)ludwig-alpha(dot)unil(dot)ch>.
> > From his mail:
>
> > The reference is: W. H. Press, S. A. Teukolsky, W. T. Vetterling, and
> > B. P. Flannery, "Numerical recipes in C", 2nd ed., Cambridge University
> > Press. Pages 896ff.
>
> > The generator polynomial is x64 + x4 + x3 + x1 + 1.
>
> Nathan (or anyone else with a copy of "Numerical recipes in C", which
> I'm embarrassed to admit I don't own), is there any indication in there
> that anyone spent any effort on choosing that particular generator
> polynomial? As far as I can see, it violates one of the standard
> guidelines for choosing a polynomial, namely that it be a multiple of
> (x + 1) ... which in modulo-2 land is equivalent to having an even
> number of terms, which this ain't got. See Ross Williams'
> A PAINLESS GUIDE TO CRC ERROR DETECTION ALGORITHMS, available from
> ftp://ftp.rocksoft.com/papers/crc_v3.txt among other places, which is
> by far the most thorough and readable thing I've ever seen on CRCs.
>
> I spent some time digging around the net for standard CRC64 polynomials,
> and the only thing I could find that looked like it might have been
> picked by someone who understood what they were doing is in the DLT
> (digital linear tape) standard, ECMA-182 (available from
> http://www.ecma.ch/ecma1/STAND/ECMA-182.HTM):
>
> x^64 + x^62 + x^57 + x^55 + x^54 + x^53 + x^52 + x^47 + x^46 + x^45 +
> x^40 + x^39 + x^38 + x^37 + x^35 + x^33 + x^32 + x^31 + x^29 + x^27 +
> x^24 + x^23 + x^22 + x^21 + x^19 + x^17 + x^13 + x^12 + x^10 + x^9 +
> x^7 + x^4 + x + 1

I'm sorry to have taken so long to reply.

The polynomial chosen for SWISS-PROT turns out to be presented, in
Numerical Recipes, just as an example of a primitive polynomial of
that degree; no assertion is made about its desirability for error
checking. It is (in turn) drawn from E. J. Watson, "Mathematics of
Computation", vol. 16, pp368-9.

Having (x + 1) as a factor guarantees to catch all errors in which
an odd number of bits have been changed. Presumably you are then
infinitesimally less likely to catch all errors in which an even
number of bits have been changed.

I would have posted the ECMA-182 polynomial if I had found it. (That
was good searching!) One hopes that the ECMA polynomial was chosen more
carefully than entirely at random. High-degree codes are often chosen
by Monte Carlo methods, by applying statistical tests to randomly-chosen
values, because the search space is so large.

I have verified that Tom transcribed the polynomial correctly from
the PDF image. The ECMA document doesn't say whether their polynomial
is applied "bit-reversed", but the check would be equally strong either
way.

Nathan Myers
ncm(at)zembu(dot)com