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 */
42 uint32_t
murmur3_32_hash(const void * data,size_t len,uint32_t seed)43 murmur3_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 */
103 uint32_t
murmur3_32_hash32(const uint32_t * data,size_t count,uint32_t seed)104 murmur3_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