Line data Source code
1 : /*
2 : * Copyright (c) 2010, Andrea Mazzoleni. All rights reserved.
3 : *
4 : * Redistribution and use in source and binary forms, with or without
5 : * modification, are permitted provided that the following conditions
6 : * are met:
7 : *
8 : * 1. Redistributions of source code must retain the above copyright
9 : * notice, this list of conditions and the following disclaimer.
10 : *
11 : * 2. Redistributions in binary form must reproduce the above copyright
12 : * notice, this list of conditions and the following disclaimer in the
13 : * documentation and/or other materials provided with the distribution.
14 : *
15 : * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
16 : * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
17 : * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
18 : * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
19 : * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
20 : * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
21 : * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
22 : * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
23 : * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
24 : * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
25 : * POSSIBILITY OF SUCH DAMAGE.
26 : */
27 :
28 : #include "tommyhash.h"
29 :
30 : /******************************************************************************/
31 : /* hash */
32 :
33 : #include <string.h> /* for memcpy */
34 :
35 : /**
36 : * Swap endianness.
37 : * They are needed only if BigEndian.
38 : */
39 : #if defined(__GNUC__)
40 : #define tommy_swap32(x) __builtin_bswap32(x)
41 : #else
42 : tommy_inline tommy_uint32_t tommy_swap32(tommy_uint32_t v)
43 : {
44 : return ((v & 0xFF000000) >> 24) |
45 : ((v & 0x00FF0000) >> 8) |
46 : ((v & 0x0000FF00) << 8) |
47 : ((v & 0x000000FF) << 24);
48 : }
49 : #endif
50 :
51 201326801 : tommy_inline tommy_uint32_t tommy_le_uint32_read(const void* ptr)
52 : {
53 : tommy_uint32_t v;
54 201326801 : memcpy(&v, ptr, sizeof(v));
55 : #if defined(WORDS_BIGENDIAN) || defined(__BIG_ENDIAN__) || \
56 : (defined(__BYTE_ORDER__) && __BYTE_ORDER__ == __ORDER_BIG_ENDIAN__)
57 : v = tommy_swap32(v);
58 : #endif
59 201326801 : return v;
60 : }
61 :
62 : #define tommy_rot(x, k) \
63 : (((x) << (k)) | ((x) >> (32 - (k))))
64 :
65 : #define tommy_mix(a, b, c) \
66 : do { \
67 : a -= c; a ^= tommy_rot(c, 4); c += b; \
68 : b -= a; b ^= tommy_rot(a, 6); a += c; \
69 : c -= b; c ^= tommy_rot(b, 8); b += a; \
70 : a -= c; a ^= tommy_rot(c, 16); c += b; \
71 : b -= a; b ^= tommy_rot(a, 19); a += c; \
72 : c -= b; c ^= tommy_rot(b, 4); b += a; \
73 : } while (0)
74 :
75 : #define tommy_final(a, b, c) \
76 : do { \
77 : c ^= b; c -= tommy_rot(b, 14); \
78 : a ^= c; a -= tommy_rot(c, 11); \
79 : b ^= a; b -= tommy_rot(a, 25); \
80 : c ^= b; c -= tommy_rot(b, 16); \
81 : a ^= c; a -= tommy_rot(c, 4); \
82 : b ^= a; b -= tommy_rot(a, 14); \
83 : c ^= b; c -= tommy_rot(b, 24); \
84 : } while (0)
85 :
86 16777239 : TOMMY_API tommy_uint32_t tommy_hash_u32(tommy_uint32_t init_val, const void* void_key, tommy_size_t key_len)
87 : {
88 16777239 : const unsigned char* key = tommy_cast(const unsigned char*, void_key);
89 : tommy_uint32_t a, b, c;
90 :
91 16777239 : a = b = c = 0xdeadbeef + ((tommy_uint32_t)key_len) + init_val;
92 :
93 33554470 : while (key_len > 12) {
94 16777231 : a += tommy_le_uint32_read(key + 0);
95 16777231 : b += tommy_le_uint32_read(key + 4);
96 16777231 : c += tommy_le_uint32_read(key + 8);
97 :
98 16777231 : tommy_mix(a, b, c);
99 :
100 16777231 : key_len -= 12;
101 16777231 : key += 12;
102 : }
103 :
104 16777239 : switch (key_len) {
105 1 : case 0 :
106 1 : return c; /* used only when called with a zero length */
107 1 : case 12 :
108 1 : c += tommy_le_uint32_read(key + 8);
109 1 : b += tommy_le_uint32_read(key + 4);
110 1 : a += tommy_le_uint32_read(key + 0);
111 1 : break;
112 1 : case 11 : c += ((tommy_uint32_t)key[10]) << 16; /* fallthrough */
113 2 : case 10 : c += ((tommy_uint32_t)key[9]) << 8; /* fallthrough */
114 3 : case 9 : c += key[8]; /* fallthrough */
115 4 : case 8 :
116 4 : b += tommy_le_uint32_read(key + 4);
117 4 : a += tommy_le_uint32_read(key + 0);
118 4 : break;
119 2 : case 7 : b += ((tommy_uint32_t)key[6]) << 16; /* fallthrough */
120 3 : case 6 : b += ((tommy_uint32_t)key[5]) << 8; /* fallthrough */
121 4 : case 5 : b += key[4]; /* fallthrough */
122 16777222 : case 4 :
123 16777222 : a += tommy_le_uint32_read(key + 0);
124 16777222 : break;
125 3 : case 3 : a += ((tommy_uint32_t)key[2]) << 16; /* fallthrough */
126 8 : case 2 : a += ((tommy_uint32_t)key[1]) << 8; /* fallthrough */
127 11 : case 1 : a += key[0]; /* fallthrough */
128 : }
129 :
130 16777238 : tommy_final(a, b, c);
131 :
132 16777238 : return c;
133 : }
134 :
135 16777239 : TOMMY_API tommy_uint64_t tommy_hash_u64(tommy_uint64_t init_val, const void* void_key, tommy_size_t key_len)
136 : {
137 16777239 : const unsigned char* key = tommy_cast(const unsigned char*, void_key);
138 : tommy_uint32_t a, b, c;
139 :
140 16777239 : a = b = c = 0xdeadbeef + ((tommy_uint32_t)key_len) + (init_val & 0xffffffff);
141 16777239 : c += init_val >> 32;
142 :
143 33554470 : while (key_len > 12) {
144 16777231 : a += tommy_le_uint32_read(key + 0);
145 16777231 : b += tommy_le_uint32_read(key + 4);
146 16777231 : c += tommy_le_uint32_read(key + 8);
147 :
148 16777231 : tommy_mix(a, b, c);
149 :
150 16777231 : key_len -= 12;
151 16777231 : key += 12;
152 : }
153 :
154 16777239 : switch (key_len) {
155 1 : case 0 :
156 1 : return c + ((tommy_uint64_t)b << 32); /* used only when called with a zero length */
157 1 : case 12 :
158 1 : c += tommy_le_uint32_read(key + 8);
159 1 : b += tommy_le_uint32_read(key + 4);
160 1 : a += tommy_le_uint32_read(key + 0);
161 1 : break;
162 1 : case 11 : c += ((tommy_uint32_t)key[10]) << 16; /* fallthrough */
163 2 : case 10 : c += ((tommy_uint32_t)key[9]) << 8; /* fallthrough */
164 3 : case 9 : c += key[8]; /* fallthrough */
165 4 : case 8 :
166 4 : b += tommy_le_uint32_read(key + 4);
167 4 : a += tommy_le_uint32_read(key + 0);
168 4 : break;
169 2 : case 7 : b += ((tommy_uint32_t)key[6]) << 16; /* fallthrough */
170 3 : case 6 : b += ((tommy_uint32_t)key[5]) << 8; /* fallthrough */
171 4 : case 5 : b += key[4]; /* fallthrough */
172 16777222 : case 4 :
173 16777222 : a += tommy_le_uint32_read(key + 0);
174 16777222 : break;
175 3 : case 3 : a += ((tommy_uint32_t)key[2]) << 16; /* fallthrough */
176 8 : case 2 : a += ((tommy_uint32_t)key[1]) << 8; /* fallthrough */
177 11 : case 1 : a += key[0]; /* fallthrough */
178 : }
179 :
180 16777238 : tommy_final(a, b, c);
181 :
182 16777238 : return c + ((tommy_uint64_t)b << 32);
183 : }
184 :
185 16777239 : TOMMY_API tommy_uint32_t tommy_strhash_u32(tommy_uint32_t init_val, const void* void_key)
186 : {
187 16777239 : const unsigned char* key = tommy_cast(const unsigned char*, void_key);
188 : tommy_uint32_t a, b, c;
189 16777239 : tommy_uint32_t m[3] = { 0xff, 0xff00, 0xff0000 };
190 :
191 16777239 : a = b = c = 0xdeadbeef + init_val;
192 : /* this is different than original lookup3 and the result won't match */
193 :
194 16777232 : while (1) {
195 33554471 : tommy_uint32_t v = tommy_le_uint32_read(key);
196 :
197 33554471 : if (tommy_haszero_u32(v)) {
198 16777229 : if (v & m[0]) {
199 16777227 : a += v & m[0];
200 16777227 : if (v & m[1]) {
201 16777224 : a += v & m[1];
202 16777224 : if (v & m[2])
203 16777219 : a += v & m[2];
204 : }
205 : }
206 :
207 16777229 : break;
208 : }
209 :
210 16777242 : a += v;
211 :
212 16777242 : v = tommy_le_uint32_read(key + 4);
213 :
214 16777242 : if (tommy_haszero_u32(v)) {
215 6 : if (v & m[0]) {
216 4 : b += v & m[0];
217 4 : if (v & m[1]) {
218 3 : b += v & m[1];
219 3 : if (v & m[2])
220 2 : b += v & m[2];
221 : }
222 : }
223 :
224 6 : break;
225 : }
226 :
227 16777236 : b += v;
228 :
229 16777236 : v = tommy_le_uint32_read(key + 8);
230 :
231 16777236 : if (tommy_haszero_u32(v)) {
232 4 : if (v & m[0]) {
233 3 : c += v & m[0];
234 3 : if (v & m[1]) {
235 2 : c += v & m[1];
236 2 : if (v & m[2])
237 1 : c += v & m[2];
238 : }
239 : }
240 :
241 4 : break;
242 : }
243 :
244 16777232 : c += v;
245 :
246 16777232 : tommy_mix(a, b, c);
247 :
248 16777232 : key += 12;
249 : }
250 :
251 : /* for lengths that are multipliers of 12 we already have called mix */
252 : /* this is different than the original lookup3 and the result won't match */
253 :
254 16777239 : tommy_final(a, b, c);
255 :
256 16777239 : return c;
257 : }
258 :
|
