common/lib/libc/hash/murmurhash/murmurhash.c

   1 /*      $NetBSD: murmurhash.c,v 1.6 2013/10/26 21:06:38 rmind Exp $     */
   2
   3 /*
   4  * MurmurHash2 -- from the original code:
   5  *
   6  * "MurmurHash2 was written by Austin Appleby, and is placed in the public
   7  * domain. The author hereby disclaims copyright to this source code."
   8  *
   9  * References:
  10  *      http://code.google.com/p/smhasher/
  11  *      https://sites.google.com/site/murmurhash/
  12  */
  13
  14 #include <sys/cdefs.h>
  15
  16 #if defined(_KERNEL) || defined(_STANDALONE)
  17 __KERNEL_RCSID(0, "$NetBSD: murmurhash.c,v 1.6 2013/10/26 21:06:38 rmind Exp $");
  18
  19 #else
  20
  21 #if defined(LIBC_SCCS) && !defined(lint)
  22 __RCSID("$NetBSD: murmurhash.c,v 1.6 2013/10/26 21:06:38 rmind Exp $");
  23 #endif /* LIBC_SCCS and not lint */
  24
  25 #include "namespace.h"
  26 #endif
  27
  28 #include <sys/types.h>
  29 #include <sys/param.h>
  30 #include <sys/hash.h>
  31
  32 #if !defined(_KERNEL) && !defined(_STANDALONE)
  33 #ifdef __weak_alias
  34 __weak_alias(murmurhash2,_murmurhash2)
  35 #endif
  36 #endif
  37
  38 uint32_t
  39 murmurhash2(const void *key, size_t len, uint32_t seed)
  40 {
  41         /*
  42          * Note: 'm' and 'r' are mixing constants generated offline.
  43          * They're not really 'magic', they just happen to work well.
  44          * Initialize the hash to a 'random' value.
  45          */
  46         const uint32_t m = 0x5bd1e995;
  47         const int r = 24;
  48
  49         const uint8_t *data = key;
  50         uint32_t h = seed ^ (uint32_t)len;
  51
  52         if (__predict_true(ALIGNED_POINTER(key, uint32_t))) {
  53                 while (len >= sizeof(uint32_t)) {
  54                         uint32_t k = *(const uint32_t *)data;
  55
  56                         k *= m;
  57                         k ^= k >> r;
  58                         k *= m;
  59
  60                         h *= m;
  61                         h ^= k;
  62
  63                         data += sizeof(uint32_t);
  64                         len -= sizeof(uint32_t);
  65                 }
  66         } else {
  67                 while (len >= sizeof(uint32_t)) {
  68                         uint32_t k;
  69
  70                         k  = data[0];
  71                         k |= data[1] << 8;
  72                         k |= data[2] << 16;
  73                         k |= data[3] << 24;
  74
  75                         k *= m;
  76                         k ^= k >> r;
  77                         k *= m;
  78
  79                         h *= m;
  80                         h ^= k;
  81
  82                         data += sizeof(uint32_t);
  83                         len -= sizeof(uint32_t);
  84                 }
  85         }
  86
  87         /* Handle the last few bytes of the input array. */
  88         switch (len) {
  89         case 3:
  90                 h ^= data[2] << 16;
  91                 /* FALLTHROUGH */
  92         case 2:
  93                 h ^= data[1] << 8;
  94                 /* FALLTHROUGH */
  95         case 1:
  96                 h ^= data[0];
  97                 h *= m;
  98         }
  99
 100         /*
 101          * Do a few final mixes of the hash to ensure the last few
 102          * bytes are well-incorporated.
 103          */
 104         h ^= h >> 13;
 105         h *= m;
 106         h ^= h >> 15;
 107
 108         return h;
 109 }