Re: propose renaming gnulib memxfrm to amemxfrm (naming collision with coreutils)

[Paolo Bonzini]

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