[libvirt] [PATCH] Replace hashing algorithm with murmurhash
Daniel P. Berrange
berrange at redhat.com
Wed Jan 25 17:19:17 UTC 2012
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 :|
More information about the libvir-list
mailing list