chiark / gitweb /
libudev: ship the original MurmurHash2.[ch] file
authorKay Sievers <kay@vrfy.org>
Mon, 23 Dec 2013 01:46:39 +0000 (02:46 +0100)
committerKay Sievers <kay@vrfy.org>
Mon, 23 Dec 2013 01:55:06 +0000 (02:55 +0100)
Makefile.am
README
src/libudev/libudev-util.c
src/shared/MurmurHash2.c [new file with mode: 0644]
src/shared/MurmurHash2.h [new file with mode: 0644]

index 66d3911..e1a7361 100644 (file)
@@ -755,6 +755,8 @@ libsystemd_shared_la_SOURCES = \
        src/shared/fileio.c \
        src/shared/fileio.h \
        src/shared/output-mode.h \
+       src/shared/MurmurHash2.c \
+       src/shared/MurmurHash2.h \
        src/shared/MurmurHash3.c \
        src/shared/MurmurHash3.h \
        src/shared/acpi-fpdt.h \
diff --git a/README b/README
index a8a519a..b4c4743 100644 (file)
--- a/README
+++ b/README
@@ -31,7 +31,7 @@ AUTHOR:
 LICENSE:
         LGPLv2.1+ for all code
         - except sd-daemon.[ch] and sd-readahead.[ch] which are MIT
-        - except src/shared/MurmurHash3.c which is Public Domain
+        - except src/shared/MurmurHash[23].c which is Public Domain
         - except src/journal/lookup3.c which is Public Domain
         - except src/udev/* which is (currently still) GPLv2, GPLv2+
 
index b5b9db6..c940e06 100644 (file)
@@ -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 (file)
index 0000000..2f4149d
--- /dev/null
@@ -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 (file)
index 0000000..93362dd
--- /dev/null
@@ -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_