summaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
authorKay Sievers <kay@vrfy.org>2013-12-23 02:46:39 +0100
committerKay Sievers <kay@vrfy.org>2013-12-23 02:55:06 +0100
commit57d0e6b2731ab695d14b7cf496832ba416cc43d3 (patch)
tree05ecec164b8aa0a2d95fb5f53a3b7a110b137d67 /src
parent91d53e2b896ed3b1e76c3117a7acb74e4edc921f (diff)
libudev: ship the original MurmurHash2.[ch] file
Diffstat (limited to 'src')
-rw-r--r--src/libudev/libudev-util.c58
-rw-r--r--src/shared/MurmurHash2.c86
-rw-r--r--src/shared/MurmurHash2.h33
3 files changed, 121 insertions, 56 deletions
diff --git a/src/libudev/libudev-util.c b/src/libudev/libudev-util.c
index b5b9db67fc..c940e06f71 100644
--- a/src/libudev/libudev-util.c
+++ b/src/libudev/libudev-util.c
@@ -36,6 +36,7 @@
#include "libudev.h"
#include "libudev-private.h"
#include "utf8.h"
+#include "MurmurHash2.h"
/**
* SECTION:libudev-util
@@ -396,64 +397,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 */
diff --git a/src/shared/MurmurHash2.c b/src/shared/MurmurHash2.c
new file mode 100644
index 0000000000..2f4149dbe9
--- /dev/null
+++ b/src/shared/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/shared/MurmurHash2.h b/src/shared/MurmurHash2.h
new file mode 100644
index 0000000000..93362dd485
--- /dev/null
+++ b/src/shared/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_