[src/trunk]: src Add MurmurHash2 -- a non-cryptographic hash function by Aust...

[rmind <rmind%NetBSD.org@localhost>]

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