bug-gnulib
[Top][All Lists]
Advanced

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

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


From: Paolo Bonzini
Subject: Re: propose renaming gnulib memxfrm to amemxfrm (naming collision with coreutils)
Date: Thu, 05 Aug 2010 04:58:26 +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/05/2010 01:44 AM, Simon Josefsson wrote:
Paul Eggert<address@hidden>  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



reply via email to

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