diff options
| -rw-r--r-- | src/libudev/Makefile.am | 2 | ||||
| -rw-r--r-- | src/libudev/MurmurHash2.c | 86 | ||||
| -rw-r--r-- | src/libudev/MurmurHash2.h | 33 | ||||
| -rw-r--r-- | src/libudev/libudev-util.c | 58 |
4 files changed, 123 insertions, 56 deletions
diff --git a/src/libudev/Makefile.am b/src/libudev/Makefile.am index 5211550857..a588080d12 100644 --- a/src/libudev/Makefile.am +++ b/src/libudev/Makefile.am @@ -39,6 +39,7 @@ libudev_la_SOURCES =\ exit-status.c \ hashmap.c \ log.c \ + MurmurHash2.c \ path-util.c \ set.c \ strbuf.c \ @@ -60,6 +61,7 @@ noinst_HEADERS = \ log.h \ macro.h \ missing.h \ + MurmurHash2.h \ path-util.h \ set.h \ socket-util.h \ diff --git a/src/libudev/MurmurHash2.c b/src/libudev/MurmurHash2.c new file mode 100644 index 0000000000..2f4149dbe9 --- /dev/null +++ b/src/libudev/MurmurHash2.c @@ -0,0 +1,86 @@ +//----------------------------------------------------------------------------- +// MurmurHash2 was written by Austin Appleby, and is placed in the public +// domain. The author hereby disclaims copyright to this source code. + +// Note - This code makes a few assumptions about how your machine behaves - + +// 1. We can read a 4-byte value from any address without crashing +// 2. sizeof(int) == 4 + +// And it has a few limitations - + +// 1. It will not work incrementally. +// 2. It will not produce the same results on little-endian and big-endian +// machines. + +#include "MurmurHash2.h" + +//----------------------------------------------------------------------------- +// Platform-specific functions and macros + +// Microsoft Visual Studio + +#if defined(_MSC_VER) + +#define BIG_CONSTANT(x) (x) + +// Other compilers + +#else // defined(_MSC_VER) + +#define BIG_CONSTANT(x) (x##LLU) + +#endif // !defined(_MSC_VER) + +//----------------------------------------------------------------------------- + +uint32_t MurmurHash2 ( const void * key, int len, uint32_t seed ) +{ + // 'm' and 'r' are mixing constants generated offline. + // They're not really 'magic', they just happen to work well. + + const uint32_t m = 0x5bd1e995; + const int r = 24; + + // Initialize the hash to a 'random' value + + uint32_t h = seed ^ len; + + // Mix 4 bytes at a time into the hash + + const unsigned char * data = (const unsigned char *)key; + + while(len >= 4) + { + uint32_t k = *(uint32_t*)data; + + k *= m; + k ^= k >> r; + k *= m; + + h *= m; + h ^= k; + + data += 4; + len -= 4; + } + + // Handle the last few bytes of the input array + + switch(len) + { + case 3: h ^= data[2] << 16; + case 2: h ^= data[1] << 8; + case 1: h ^= data[0]; + h *= m; + }; + + // Do a few final mixes of the hash to ensure the last few + // bytes are well-incorporated. + + h ^= h >> 13; + h *= m; + h ^= h >> 15; + + return h; +} diff --git a/src/libudev/MurmurHash2.h b/src/libudev/MurmurHash2.h new file mode 100644 index 0000000000..93362dd485 --- /dev/null +++ b/src/libudev/MurmurHash2.h @@ -0,0 +1,33 @@ +//----------------------------------------------------------------------------- +// MurmurHash2 was written by Austin Appleby, and is placed in the public +// domain. The author hereby disclaims copyright to this source code. + +#ifndef _MURMURHASH2_H_ +#define _MURMURHASH2_H_ + +//----------------------------------------------------------------------------- +// Platform-specific functions and macros + +// Microsoft Visual Studio + +#if defined(_MSC_VER) + +typedef unsigned char uint8_t; +typedef unsigned long uint32_t; +typedef unsigned __int64 uint64_t; + +// Other compilers + +#else // defined(_MSC_VER) + +#include <stdint.h> + +#endif // !defined(_MSC_VER) + +//----------------------------------------------------------------------------- + +uint32_t MurmurHash2 ( const void * key, int len, uint32_t seed ); + +//----------------------------------------------------------------------------- + +#endif // _MURMURHASH2_H_ diff --git a/src/libudev/libudev-util.c b/src/libudev/libudev-util.c index 4d59980a70..2c31d5b1db 100644 --- a/src/libudev/libudev-util.c +++ b/src/libudev/libudev-util.c @@ -39,6 +39,7 @@ #include "libudev.h" #include "libudev-private.h" #include "utf8.h" +#include "MurmurHash2.h" /** * SECTION:libudev-util @@ -404,64 +405,9 @@ _public_ int udev_util_encode_string(const char *str, char *str_enc, size_t len) return encode_devnode_name(str, str_enc, len); } -/* - * http://sites.google.com/site/murmurhash/ - * - * All code is released to the public domain. For business purposes, - * Murmurhash is under the MIT license. - * - */ -static unsigned int murmur_hash2(const char *key, size_t len, unsigned int seed) -{ - /* - * 'm' and 'r' are mixing constants generated offline. - * They're not really 'magic', they just happen to work well. - */ - const unsigned int m = 0x5bd1e995; - const int r = 24; - - /* initialize the hash to a 'random' value */ - unsigned int h = seed ^ len; - - /* mix 4 bytes at a time into the hash */ - const unsigned char * data = (const unsigned char *)key; - - while(len >= sizeof(unsigned int)) { - unsigned int k; - - memcpy(&k, data, sizeof(k)); - k *= m; - k ^= k >> r; - k *= m; - h *= m; - h ^= k; - - data += sizeof(k); - len -= sizeof(k); - } - - /* handle the last few bytes of the input array */ - switch(len) { - case 3: - h ^= data[2] << 16; - case 2: - h ^= data[1] << 8; - case 1: - h ^= data[0]; - h *= m; - }; - - /* do a few final mixes of the hash to ensure the last few bytes are well-incorporated */ - h ^= h >> 13; - h *= m; - h ^= h >> 15; - - return h; -} - unsigned int util_string_hash32(const char *str) { - return murmur_hash2(str, strlen(str), 0); + return MurmurHash2(str, strlen(str), 0); } /* get a bunch of bit numbers out of the hash, and set the bits in our bit field */ |