[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

bug#6789: propose renaming gnulib memxfrm to amemxfrm (naming collision

From: Paolo Bonzini
Subject: bug#6789: 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: 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.


reply via email to

[Prev in Thread] Current Thread [Next in Thread]