Skip site navigation (1) Skip section navigation (2)

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

From: Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us>
To: pgsql-hackers(at)postgresql(dot)org
Subject: Re: Uh, this is *not* a 64-bit CRC ...
Date: 2001-03-05 19:00:59
Message-ID: 20276.983818859@sss.pgh.pa.us (view raw or flat)
Thread:
Lists: pgsql-hackers
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 probably going to go with this one unless someone can come up with
an authoritative source for another one.

			regards, tom lane

In response to

Responses

pgsql-hackers by date

Next:From: Ian Lance TaylorDate: 2001-03-05 19:35:56
Subject: Re: WAL-based allocation of XIDs is insecure
Previous:From: Tom LaneDate: 2001-03-05 18:31:50
Subject: WAL-based allocation of XIDs is insecure

Privacy Policy | About PostgreSQL
Copyright © 1996-2014 The PostgreSQL Global Development Group