1/*-
2 * Copyright (c) 2014 Dag-Erling Sm��rgrav
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 * 1. Redistributions of source code must retain the above copyright
9 *    notice, this list of conditions and the following disclaimer.
10 * 2. Redistributions in binary form must reproduce the above copyright
11 *    notice, this list of conditions and the following disclaimer in the
12 *    documentation and/or other materials provided with the distribution.
13 *
14 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
15 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
16 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
17 * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
18 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
19 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
20 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
21 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
22 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
23 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
24 * SUCH DAMAGE.
25 */
26
27#include <sys/hash.h>
28#include <sys/endian.h>
29#include <sys/stdint.h>
30#include <sys/types.h>
31
32#define rol32(i32, n) ((i32) << (n) | (i32) >> (32 - (n)))
33
34/*
35 * Simple implementation of the Murmur3-32 hash function.
36 *
37 * This implementation is slow but safe.  It can be made significantly
38 * faster if the caller guarantees that the input is correctly aligned for
39 * 32-bit reads, and slightly faster yet if the caller guarantees that the
40 * length of the input is always a multiple of 4 bytes.
41 */
42uint32_t
43murmur3_32_hash(const void *data, size_t len, uint32_t seed)
44{
45	const uint8_t *bytes;
46	uint32_t hash, k;
47	size_t res;
48
49	/* initialization */
50	bytes = data;
51	res = len;
52	hash = seed;
53
54	/* main loop */
55	while (res >= 4) {
56		/* replace with le32toh() if input is aligned */
57		k = le32dec(bytes);
58		bytes += 4;
59		res -= 4;
60		k *= 0xcc9e2d51;
61		k = rol32(k, 15);
62		k *= 0x1b873593;
63		hash ^= k;
64		hash = rol32(hash, 13);
65		hash *= 5;
66		hash += 0xe6546b64;
67	}
68
69	/* remainder */
70	/* remove if input length is a multiple of 4 */
71	if (res > 0) {
72		k = 0;
73		switch (res) {
74		case 3:
75			k |= bytes[2] << 16;
76		case 2:
77			k |= bytes[1] << 8;
78		case 1:
79			k |= bytes[0];
80			k *= 0xcc9e2d51;
81			k = rol32(k, 15);
82			k *= 0x1b873593;
83			hash ^= k;
84			break;
85		}
86	}
87
88	/* finalize */
89	hash ^= (uint32_t)len;
90	hash ^= hash >> 16;
91	hash *= 0x85ebca6b;
92	hash ^= hash >> 13;
93	hash *= 0xc2b2ae35;
94	hash ^= hash >> 16;
95	return (hash);
96}
97
98/*
99 * Simplified version of the above optimized for aligned sequences of
100 * 32-bit words.  The count argument is the number of words, not the
101 * length in bytes.
102 */
103uint32_t
104murmur3_32_hash32(const uint32_t *data, size_t count, uint32_t seed)
105{
106	uint32_t hash, k;
107	size_t res;
108
109	/* iterate */
110	for (res = count, hash = seed; res > 0; res--, data++) {
111		k = le32toh(*data);
112		k *= 0xcc9e2d51;
113		k = rol32(k, 15);
114		k *= 0x1b873593;
115		hash ^= k;
116		hash = rol32(hash, 13);
117		hash *= 5;
118		hash += 0xe6546b64;
119	}
120
121	/* finalize */
122	hash ^= (uint32_t)count;
123	hash ^= hash >> 16;
124	hash *= 0x85ebca6b;
125	hash ^= hash >> 13;
126	hash *= 0xc2b2ae35;
127	hash ^= hash >> 16;
128	return (hash);
129}
130