Hi, Thanks for the patch, comment are embedded.
Yaniv Izik Eidus wrote: > >From 2379eec91c22fd02eca59496ccceb5f86d50e7fe Mon Sep 17 00:00:00 2001 > From: Izik Eidus <iei...@redhat.com> > Date: Tue, 29 Dec 2009 05:18:51 +0200 > Subject: [PATCH] spice: add new modifed murmur2 hash function. > > optimized for spice usage > > Signed-off-by: Izik Eidus <iei...@redhat.com> > --- > common/murmur_hash2a.h | 176 > ++++++++++++++++++++++++++++++++++++++++++++++++ > 1 files changed, 176 insertions(+), 0 deletions(-) > create mode 100644 common/murmur_hash2a.h > > diff --git a/common/murmur_hash2a.h b/common/murmur_hash2a.h > new file mode 100644 > index 0000000..394314a > --- /dev/null > +++ b/common/murmur_hash2a.h > @@ -0,0 +1,176 @@ > +/* > + Copyright (C) 2009 Red Hat, Inc. > + > + This program is free software; you can redistribute it and/or > + modify it under the terms of the GNU General Public License as > + published by the Free Software Foundation; either version 2 of > + the License, or (at your option) any later version. > + > + This program is distributed in the hope that it will be useful, > + but WITHOUT ANY WARRANTY; without even the implied warranty of > + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the > + GNU General Public License for more details. > + > + You should have received a copy of the GNU General Public License > + along with this program. If not, see <http://www.gnu.org/licenses/>. > +*/ > + > +//Some modifications by Red Hat any bug is probably our fault > + > +//----------------------------------------------------------------------------- > +// MurmurHash2A, by Austin Appleby > + > +// This is a variant of MurmurHash2 modified to use the Merkle-Damgard > +// construction. Bulk speed should be identical to Murmur2, small-key speed > +// will be 10%-20% slower due to the added overhead at the end of the hash. > + > +// This variant fixes a minor issue where null keys were more likely to > +// collide with each other than expected, and also makes the algorithm > +// more amenable to incremental implementations. All other caveats from > +// MurmurHash2 still apply. > + > +#ifndef __MURMUR_HASH2A_H > +#define __MURMUR_HASH2A_H > + > +#ifdef __GNUC__ > + > +#include <stdint.h> > + > +#else > + > +#ifdef QXLDD > +#include <windef.h> > +#include "os_dep.h" > +#else > +#include <stddef.h> > +#include <basetsd.h> > +#endif > + > +typedef UINT32 uint32_t; > +typedef UINT16 uint16_t; > +typedef UINT8 uint8_t; > + > +#endif > + > +#define mmix(h,k) { k *= m; k ^= k >> r; k *= m; h *= m; h ^= k; } > + > +#ifdef QXLDD > +_inline unsigned int MurmurHash2A(const void * key, int len, unsigned int > seed ) > +#else > +inline unsigned int MurmurHash2A(const void * key, int len, unsigned int > seed ) > +#endif > It is needed only by the driver so we need only the _inline version. > +{ > + const unsigned int m = 0x5bd1e995; > + const int r = 24; > + unsigned int l = len; > + unsigned int t = 0; > + > + const unsigned char * data = (const unsigned char *)key; > + > + unsigned int h = seed; > + > + while (len >= 4) { > + unsigned int k = *(unsigned int*)data; > + > + mmix(h,k); > + > + data += 4; > + len -= 4; > + } > + > + switch (len) { > + case 3: t ^= data[2] << 16; > + case 2: t ^= data[1] << 8; > + case 1: t ^= data[0]; > + }; > + > + mmix(h,t); > + mmix(h,l); > + > + h ^= h >> 13; > + h *= m; > + h ^= h >> 15; > + > + return h; > +} > + > +#ifdef QXLDD > +_inline unsigned int MurmurHash2AJump3(const void * key, int len, unsigned > int seed ) > +#else > +inline unsigned int MurmurHash2AJump3(const void * key, int len, unsigned > int seed ) > +#endif > +{ > + const unsigned int m = 0x5bd1e995; > + const int r = 24; > + unsigned int l = len; > 1. It is needed only by the driver so we need only the _inline version. 2. key and len. this function expect to receive array of uint32_t so change "const void * key" to "const uint32_t * key" and len to be number of uint32_t element in the array. 3. use uint32_t, uint16_t, and uint8_t types. > + > + const unsigned char * data = (const unsigned char *)key; > + > + unsigned int h = seed; > + > + while (len >= 16) { > + unsigned int k = *(unsigned int*)data; > + unsigned int tmp; > + > + data += 4; > + tmp = *(unsigned int *)data; > + k = k << 8; > + k |= (unsigned char)tmp; > + mmix(h,k); > + > + k = tmp << 8; > + k = k & 0xffff0000; > + data += 4; > + tmp = *(unsigned int *)data; > + k |= (unsigned char)((unsigned int)tmp >> 8); > need to be (uint16_t) (tmp >> 8)); > + mmix(h,k); > + > + data += 4; > + k = *(unsigned int *)data; > + k = k << 8; > + k |= (unsigned char)tmp; > + mmix(h,k); > + > + data += 4; > + len -= 16; > + } > + > + while (len >= 4) { > after changing (2) this will be while (len) { > + unsigned int k = *(unsigned int*)data; > This loop need to skip MSB byte. > + > + mmix(h,k); > + > + data += 4; > + len -= 4; > + } > + > + h *= m; > + mmix(h,l); > + > + h ^= h >> 13; > + h *= m; > + h ^= h >> 15; > + > + return h; > +} > + > + > +#ifdef QXLDD > +_inline uint32_t murmurhash2a(const void *key, size_t length, uint32_t > initval) > +#else > +inline uint32_t murmurhash2a(const void *key, size_t length, uint32_t > initval) > +#endif > +{ > + return MurmurHash2A(key, length, initval); > +} > + > +#ifdef QXLDD > +_inline uint32_t murmurhash2ajump3(const void *key, size_t length, uint32_t > initval) > +#else > +inline uint32_t murmurhash2ajump3(const void *key, size_t length, uint32_t > initval) > +#endif > +{ > + return MurmurHash2AJump3(key, length, initval); > +} > +#endif > + > ------------------------------------------------------------------------------ This SF.Net email is sponsored by the Verizon Developer Community Take advantage of Verizon's best-in-class app development support A streamlined, 14 day to market process makes app distribution fast and easy Join now and get one step closer to millions of Verizon customers http://p.sf.net/sfu/verizon-dev2dev _______________________________________________ Spice-space-devel mailing list Spice-space-devel@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/spice-space-devel
