murmurhash.c revision 1.3 
1/*	$NetBSD: murmurhash.c,v 1.3 2012/07/09 21:25:46 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.3 2012/07/09 21:25:46 rmind Exp $");
18#else
19__RCSID("$NetBSD: murmurhash.c,v 1.3 2012/07/09 21:25:46 rmind Exp $");
20#endif
21
22#include "namespace.h"
23#include <sys/types.h>
24#include <sys/hash.h>
25
26#ifdef __weak_alias
27__weak_alias(murmurhash2,_murmurhash2)
28#endif
29
30uint32_t
31murmurhash2(const void *key, size_t len, uint32_t seed)
32{
33	/*
34	 * Note: 'm' and 'r' are mixing constants generated offline.
35	 * They're not really 'magic', they just happen to work well.
36	 * Initialize the hash to a 'random' value.
37	 */
38	const uint32_t m = 0x5bd1e995;
39	const int r = 24;
40
41	const uint8_t *data = (const uint8_t *)key;
42	uint32_t h = seed ^ (uint32_t)len;
43
44	while (len >= sizeof(uint32_t)) {
45		uint32_t k;
46
47		k  = data[0];
48		k |= data[1] << 8;
49		k |= data[2] << 16;
50		k |= data[3] << 24;
51
52		k *= m;
53		k ^= k >> r;
54		k *= m;
55
56		h *= m;
57		h ^= k;
58
59		data += sizeof(uint32_t);
60		len -= sizeof(uint32_t);
61	}
62
63	/* Handle the last few bytes of the input array. */
64	switch (len) {
65	case 3:
66		h ^= data[2] << 16;
67		/* FALLTHROUGH */
68	case 2:
69		h ^= data[1] << 8;
70		/* FALLTHROUGH */
71	case 1:
72		h ^= data[0];
73		h *= m;
74	}
75
76	/*
77	 * Do a few final mixes of the hash to ensure the last few
78	 * bytes are well-incorporated.
79	 */
80	h ^= h >> 13;
81	h *= m;
82	h ^= h >> 15;
83
84	return h;
85}
86