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