Module Name: src
Committed By: rmind
Date: Sun Jul 8 01:21:12 UTC 2012
Modified Files:
src/common/lib/libc: Makefile.inc
src/lib/libc: shlib_version
src/lib/libc/hash: Makefile.inc
Added Files:
src/common/lib/libc/hash/murmurhash: murmurhash.c
Log Message:
Add MurmurHash2 -- a non-cryptographic hash function by Austin Appleby.
The code is taken from the upstream and is in the public domain.
OK christos@
To generate a diff of this commit:
cvs rdiff -u -r1.11 -r1.12 src/common/lib/libc/Makefile.inc
cvs rdiff -u -r0 -r1.1 src/common/lib/libc/hash/murmurhash/murmurhash.c
cvs rdiff -u -r1.231 -r1.232 src/lib/libc/shlib_version
cvs rdiff -u -r1.11 -r1.12 src/lib/libc/hash/Makefile.inc
Please note that diffs are not public domain; they are subject to the
copyright notices on the relevant files.
Modified files:
Index: src/common/lib/libc/Makefile.inc
diff -u src/common/lib/libc/Makefile.inc:1.11 src/common/lib/libc/Makefile.inc:1.12
--- src/common/lib/libc/Makefile.inc:1.11 Thu Jun 16 16:39:14 2011
+++ src/common/lib/libc/Makefile.inc Sun Jul 8 01:21:12 2012
@@ -1,8 +1,8 @@
-# $NetBSD: Makefile.inc,v 1.11 2011/06/16 16:39:14 joerg Exp $
+# $NetBSD: Makefile.inc,v 1.12 2012/07/08 01:21:12 rmind Exp $
COMMON_DIR:=${.PARSEDIR}
COMMON_CODEDIRS=atomic gen gmon inet md net quad stdlib string sys
-COMMON_CODEDIRS+=hash/sha1 hash/sha2 hash/rmd160
+COMMON_CODEDIRS+=hash/sha1 hash/sha2 hash/rmd160 hash/murmurhash
.if defined(COMMON_MACHINE_ARCH) && !empty(COMMON_MACHINE_ARCH) && \
exists(${COMMON_DIR}/arch/${COMMON_MACHINE_ARCH})
Index: src/lib/libc/shlib_version
diff -u src/lib/libc/shlib_version:1.231 src/lib/libc/shlib_version:1.232
--- src/lib/libc/shlib_version:1.231 Thu Mar 8 21:59:28 2012
+++ src/lib/libc/shlib_version Sun Jul 8 01:21:11 2012
@@ -1,4 +1,4 @@
-# $NetBSD: shlib_version,v 1.231 2012/03/08 21:59:28 joerg Exp $
+# $NetBSD: shlib_version,v 1.232 2012/07/08 01:21:11 rmind Exp $
# Remember to update distrib/sets/lists/base/shl.* when changing
#
# things we wish to do on next major version bump:
@@ -31,4 +31,4 @@
# - remove gets(); it is finally dead in c11.
# - make __cerror (spelled CERROR) hidden again
major=12
-minor=183
+minor=184
Index: src/lib/libc/hash/Makefile.inc
diff -u src/lib/libc/hash/Makefile.inc:1.11 src/lib/libc/hash/Makefile.inc:1.12
--- src/lib/libc/hash/Makefile.inc:1.11 Fri Oct 27 18:29:21 2006
+++ src/lib/libc/hash/Makefile.inc Sun Jul 8 01:21:12 2012
@@ -1,4 +1,4 @@
-# $NetBSD: Makefile.inc,v 1.11 2006/10/27 18:29:21 drochner Exp $
+# $NetBSD: Makefile.inc,v 1.12 2012/07/08 01:21:12 rmind Exp $
# $OpenBSD: Makefile.inc,v 1.5 1997/07/17 06:02:42 millert Exp $
# hash functions
@@ -9,3 +9,4 @@
.include "${.CURDIR}/hash/sha1/Makefile.inc"
.include "${.CURDIR}/hash/sha2/Makefile.inc"
+.include "${.CURDIR}/hash/murmurhash/Makefile.inc"
Added files:
Index: src/common/lib/libc/hash/murmurhash/murmurhash.c
diff -u /dev/null src/common/lib/libc/hash/murmurhash/murmurhash.c:1.1
--- /dev/null Sun Jul 8 01:21:12 2012
+++ src/common/lib/libc/hash/murmurhash/murmurhash.c Sun Jul 8 01:21:12 2012
@@ -0,0 +1,77 @@
+/* $NetBSD: murmurhash.c,v 1.1 2012/07/08 01:21:12 rmind Exp $ */
+
+/*
+ * MurmurHash2 -- from the original code:
+ *
+ * "MurmurHash2 was written by Austin Appleby, and is placed in the public
+ * domain. The author hereby disclaims copyright to this source code."
+ *
+ * References:
+ * http://code.google.com/p/smhasher/
+ * https://sites.google.com/site/murmurhash/
+ */
+
+#include <sys/cdefs.h>
+#include <sys/types.h>
+#include <sys/hash.h>
+
+#if defined(_KERNEL) || defined(_STANDALONE)
+__KERNEL_RCSID(0, "$NetBSD: murmurhash.c,v 1.1 2012/07/08 01:21:12 rmind Exp $");
+#else
+__RCSID("$NetBSD: murmurhash.c,v 1.1 2012/07/08 01:21:12 rmind Exp $");
+#endif
+
+uint32_t
+murmurhash2(const void *key, size_t len, uint32_t seed)
+{
+ /*
+ * Note: 'm' and 'r' are mixing constants generated offline.
+ * They're not really 'magic', they just happen to work well.
+ * Initialize the hash to a 'random' value.
+ */
+ const uint32_t m = 0x5bd1e995;
+ const int r = 24;
+
+ const uint8_t *data = (const uint8_t *)key;
+ uint32_t h = seed ^ len;
+
+ while (len >= sizeof(uint32_t)) {
+ uint32_t k;
+
+ k = data[0];
+ k |= data[1] << 8;
+ k |= data[2] << 16;
+ k |= data[3] << 24;
+
+ k *= m;
+ k ^= k >> r;
+ k *= m;
+
+ h *= m;
+ h ^= k;
+
+ data += sizeof(uint32_t);
+ len -= sizeof(uint32_t);
+ }
+
+ /* 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;
+}
