[libvirt] [PATCH] Replace hashing algorithm with murmurhash

[Daniel P. Berrange]

On Wed, Jan 25, 2012 at 10:16:05AM -0700, Eric Blake wrote:
> On 01/25/2012 09:55 AM, Eric Blake wrote:
> >>>> +
> >>>> +    return le32toh(r);
> >>>
> >>> <endian.h>, and thus le32toh(), is not yet standardized (although POSIX
> >>> will be adding it in the future), nor is it currently provided by
> >>> gnulib.  We'd have to get that fixed first.
> >>
> >> The le32toh call was only here because the code I copied wanted to be
> >> endian neutral. I don't think libvirt really cares if its hash codes
> >> are endian neutral, so I trivially just removed the le32toh call and
> >> avoid the problem of endian.h
> > 
> > Agreed - we aren't sharing hash values over the wire, so all hash values
> > within a particular libvirtd process will be the same endianness,
> > without having to waste time on swapping bytes around.
> 
> Actually, the more I think about this, the more I have to wonder:  Does
> the incoming alignment affect the output hash?  That is, if I do
> 
> int i;
> char array[12];
> for (i = 0; i < 4; i++) {
>     strcpy(array + i, "12345678");
>     printf("%x\n", (int) virHashStrCode(array + i, 0));
> }
> 
> do I get the same values for all four iterations, on both little- and
> big-endian architectures?  If not, then the byte-rearranging really is
> important to the algorithm (that is, the algorithm is operating on
> 4-byte quantities, but must build up those quantities from 1-byte
> quantities regardless of starting alignment, so endianness looks like it
> plays a role in doing the conversion correctly).

Consulting the original CPP code, I believe we're fine without it

  https://code.google.com/p/smhasher/source/browse/trunk/MurmurHash3.cpp


// Block read - if your platform needs to do endian-swapping or can only
// handle aligned reads, do the conversion here

FORCE_INLINE uint32_t getblock ( const uint32_t * p, int i )
{
  return p[i];
}

FORCE_INLINE uint64_t getblock ( const uint64_t * p, int i )
{
  return p[i];
}


Daniel
-- 
|: http://berrange.com      -o-    http://www.flickr.com/photos/dberrange/ :|
|: http://libvirt.org              -o-             http://virt-manager.org :|
|: http://autobuild.org       -o-         http://search.cpan.org/~danberr/ :|
|: http://entangle-photo.org       -o-       http://live.gnome.org/gtk-vnc :|