Source-Changes-HG archive
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index][Old Index]
[src/trunk]: src Add MurmurHash2 -- a non-cryptographic hash function by Aust...
details: https://anonhg.NetBSD.org/src/rev/07ccd501751a
branches: trunk
changeset: 780030:07ccd501751a
user: rmind <rmind%NetBSD.org@localhost>
date: Sun Jul 08 01:21:11 2012 +0000
description:
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@
diffstat:
common/lib/libc/Makefile.inc | 4 +-
common/lib/libc/hash/murmurhash/murmurhash.c | 77 ++++++++++++++++++++++++++++
lib/libc/hash/Makefile.inc | 3 +-
lib/libc/shlib_version | 4 +-
4 files changed, 83 insertions(+), 5 deletions(-)
diffs (124 lines):
diff -r 92c1df930c70 -r 07ccd501751a common/lib/libc/Makefile.inc
--- a/common/lib/libc/Makefile.inc Sun Jul 08 00:59:34 2012 +0000
+++ b/common/lib/libc/Makefile.inc Sun Jul 08 01:21:11 2012 +0000
@@ -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})
diff -r 92c1df930c70 -r 07ccd501751a common/lib/libc/hash/murmurhash/murmurhash.c
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/common/lib/libc/hash/murmurhash/murmurhash.c Sun Jul 08 01:21:11 2012 +0000
@@ -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;
+}
diff -r 92c1df930c70 -r 07ccd501751a lib/libc/hash/Makefile.inc
--- a/lib/libc/hash/Makefile.inc Sun Jul 08 00:59:34 2012 +0000
+++ b/lib/libc/hash/Makefile.inc Sun Jul 08 01:21:11 2012 +0000
@@ -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"
diff -r 92c1df930c70 -r 07ccd501751a lib/libc/shlib_version
--- a/lib/libc/shlib_version Sun Jul 08 00:59:34 2012 +0000
+++ b/lib/libc/shlib_version Sun Jul 08 01:21:11 2012 +0000
@@ -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
Home |
Main Index |
Thread Index |
Old Index