|Looking for high-quality hashing function for dynamic linker email@example.com (1995-07-28)|
|Re: Looking for high-quality hashing function for dynamic linker firstname.lastname@example.org (1995-08-02)|
|Re: Looking for high-quality hashing function for dynamic linker email@example.com (Stefan Monnier) (1995-08-03)|
|Re: Looking for high-quality hashing function for dynamic linker firstname.lastname@example.org (1995-08-03)|
|Re: Looking for high-quality hashing function for dynamic linker email@example.com (1995-08-03)|
|From:||firstname.lastname@example.org (Paul Haahr)|
|Organization:||NETCOM On-line services|
|Date:||Thu, 3 Aug 1995 08:45:33 GMT|
Eric Benson <email@example.com> wrote:
> Is it feasible to compute a signature consisting of a few (say, less than
> ten) 32 bit words and use this for comparison instead of the entire set of
Yes. Or, rather, if you trust your network and its checksums, it's
probably reasonable to trust checksums for this purpose.
> A false positive comparison would probably result in a severe
> malfunction so it should be extremely unlikely, say one-in-a-billion or
> less. I can spend a big chunk of CPU time in the compilation environment
> to compute this signature if necessary. I have a 29-bit CRC hash function
> already available. Is this, or some multi-word variant of it, good enough
> for my purposes?
I would suspect that two 32-bit CRCs using different polynomials would
not be 2^32 times stronger than one 32-bit checksum, so multiple CRCs
may not buy you as much as you would hope.
> [A good 32 bit hash function should give you a 1 in 4 billion chance of a
> false match. -John]
Yes. But, to be utterly paranoid, you might want to pick one of the
cryptographic checksums, such as MD5 or snefru, rather than CRC. For
some definition of better, they may be better.
> If so, does anyone have a larger-than-29-bit CRC
> implementation? Does anyone have any references to relevant research?
My favorite reference on the topic is Gerard J. Holzmann, _Design and
Validation of Computer Protocols_, Prentice-Hall 1991. He gives a
general, fast implementation of a table-driven CRC by Don Mitchell.
A while ago, I wrapped up that CRC as a Unix program, suitable for using
as a replacement to sum. It's at:
It should support polynomials up to the word length of your machine.
The code for generating the table is separate from the CRC code, so you
just have to pick a good polynomial. See Gerard's book for details on
how to do that.
Return to the
Search the comp.compilers archives again.