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