Subject: bug#6789: propose renaming gnulib memxfrm to amemxfrm (naming collision with coreutils)

From: Paolo Bonzini <[email-masked]>
Date: Thu, 05 Aug 2010 04:58:26 +0200

On 08/05/2010 01:44 AM, Simon Josefsson wrote:
> Paul Eggert<[email-masked]>  writes:
>
>> Come to think of it, looking at gnulib memxfrm gave me an idea
>> to improve the performance of GNU sort by bypassing the need for an
>> memxfrm-like function entirely.  I pushed a patch to do that at
>> <http://git.savannah.gnu.org/gitweb/?p=coreutils.git;a=commitdiff;h=2b49b140cc13cf36ec5ee5acaca5ac7bfeed6366>.
>
> I don't know this code at all, but would your approach lead to problems
> if two different strings have the same MD5 hash?  MD5 is broken, and
> finding collisions takes just seconds on normal PC.  See:
> http://en.wikipedia.org/wiki/MD5#Security

MD5 is used simply as a kind of "random key generator", so it doesn't 
matter.  I wonder two things however:

1) why bother with memxfrm as a tie-breaker? isn't memcmp good enough?

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?  It doesn't need to be cryptographic, 
I'd pick http://en.wikipedia.org/wiki/Xorshift.

Paolo