Re: Looking for high-quality hashing function for dynamic linker

Eric Benson <eb@kaleida.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
] names? 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? If so, does anyone have a larger-than-29-bit CRC
] implementation? Does anyone have any references to relevant research?


Good hash functions and CRCs are closely related to signature in
cryptography. So you might want to have a look at
cryptographic-quality checksums, like MD2 or MD5 (don't think these
are two random suggestions: these are just the only two I know since
I'm no crypto-expert or anything). Anyway, code for MD5 is widely
available (it's used by PGP) and I can send it to you (I only have a
32bit-clean version so it doesn't work right on the alpha (which
means: it doesn't give the correct result even though it does its job
as a hash function)). MD5 checksums are 128bits long and supposed to
be of very high quality without requiring too much work (I believe
it's mostly based on bit twiddling).




Stefan
--

Return to the comp.compilers page.
Search the comp.compilers archives again.