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 |
Views: | Raw Message | Whole Thread | Download mbox | Resend email |
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
From | Date | Subject | |
---|---|---|---|
Next Message | Ian Lance Taylor | 2001-03-05 19:35:56 | Re: WAL-based allocation of XIDs is insecure |
Previous Message | Tom Lane | 2001-03-05 18:31:50 | WAL-based allocation of XIDs is insecure |