|
From: | Paolo Bonzini |
Subject: | Re: propose renaming gnulib memxfrm to amemxfrm (naming collision with coreutils) |
Date: | Fri, 06 Aug 2010 10:22:50 +0200 |
User-agent: | Mozilla/5.0 (X11; U; Linux x86_64; en-US; rv:1.9.1.10) Gecko/20100621 Fedora/3.0.5-1.fc13 Lightning/1.0b2pre Thunderbird/3.0.5 |
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
[Prev in Thread] | Current Thread | [Next in Thread] |