On 08/06/2010 01:29 AM, Paul Eggert wrote:
1) why bother with memxfrm as a tie-breaker? isn't memcmp good enough?
If two keys K1 and K2 compare equal, their random hashes are supposed
to compare equal too. So if memcoll(K1,K2)==0, the random hashes must
be the same. Hence we can't just do a memcmp on K1 and K2; we need to
do a memcmp on strxfrm(K1) and strxfrm(K2).
I see. In practice, this is because "you cannot separate straße and
strasse".
2) maybe there's something cheaper than md5 that can be used? For
example you could compare a^x and b^x where x is the output of a fast
32-bit random number generator?
That wouldn't be sufficiently random, even for non-cryptographic
purposes, since keys that are natively nearby would tend to sort near
to each other after being exclusive-ORed.
You're right, keys that differ only in the leading or trailing bits
would tend to stay respectively very far and very near, though you
cannot say anything about the order.
But I see your point: perhaps there is something faster than MD5 for
this sort of thing, and which is "secure" enough. Perhaps the
ISAAC / ISAAC64 code that is already in GNU coreutils would work
for that?
ISAAC is a RNG, so wouldn't that have the same problem above? You
definitely need to use a hash function, it's just that you do not need a
cryptographic one.
Paolo
