1/* $NetBSD: murmurhash.c,v 1.8 2019/08/20 15:17:02 para 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.8 2019/08/20 15:17:02 para Exp $"); 18 19#include <lib/libkern/libkern.h> 20 21#else 22 23#if defined(LIBC_SCCS) && !defined(lint) 24__RCSID("$NetBSD: murmurhash.c,v 1.8 2019/08/20 15:17:02 para Exp $"); 25#endif /* LIBC_SCCS and not lint */ 26 27#include "namespace.h" 28#include <string.h> 29 30#endif 31 32#include <sys/types.h> 33#include <sys/param.h> 34#include <sys/hash.h> 35 36#if !defined(_KERNEL) && !defined(_STANDALONE) 37#ifdef __weak_alias 38__weak_alias(murmurhash2,_murmurhash2) 39#endif 40#endif 41 42uint32_t 43murmurhash2(const void *key, size_t len, uint32_t seed) 44{ 45 /* 46 * Note: 'm' and 'r' are mixing constants generated offline. 47 * They're not really 'magic', they just happen to work well. 48 * Initialize the hash to a 'random' value. 49 */ 50 const uint32_t m = 0x5bd1e995; 51 const int r = 24; 52 53 const uint8_t *data = key; 54 uint32_t h = seed ^ (uint32_t)len; 55 56 if (__predict_true(ALIGNED_POINTER(key, uint32_t))) { 57 while (len >= sizeof(uint32_t)) { 58 uint32_t k; 59 60 ALIGNED_POINTER_LOAD(&k, data, uint32_t); 61 k = htole32(k); 62 63 k *= m; 64 k ^= k >> r; 65 k *= m; 66 67 h *= m; 68 h ^= k; 69 70 data += sizeof(uint32_t); 71 len -= sizeof(uint32_t); 72 } 73 } else { 74 while (len >= sizeof(uint32_t)) { 75 uint32_t k; 76 77 k = data[0]; 78 k |= data[1] << 8; 79 k |= data[2] << 16; 80 k |= data[3] << 24; 81 82 k *= m; 83 k ^= k >> r; 84 k *= m; 85 86 h *= m; 87 h ^= k; 88 89 data += sizeof(uint32_t); 90 len -= sizeof(uint32_t); 91 } 92 } 93 94 /* Handle the last few bytes of the input array. */ 95 switch (len) { 96 case 3: 97 h ^= data[2] << 16; 98 /* FALLTHROUGH */ 99 case 2: 100 h ^= data[1] << 8; 101 /* FALLTHROUGH */ 102 case 1: 103 h ^= data[0]; 104 h *= m; 105 } 106 107 /* 108 * Do a few final mixes of the hash to ensure the last few 109 * bytes are well-incorporated. 110 */ 111 h ^= h >> 13; 112 h *= m; 113 h ^= h >> 15; 114 115 return h; 116} 117