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 201326801 : tommy_inline tommy_uint32_t tommy_le_uint32_read(const void* ptr)
34 : {
35 : /* allow unaligned read on Intel x86 and x86_64 platforms */
36 : #if defined(__i386__) || defined(_M_IX86) || defined(_X86_) || defined(__x86_64__) || defined(_M_X64)
37 : /* defines from http://predef.sourceforge.net/ */
38 201326801 : return *(const tommy_uint32_t*)ptr;
39 : #else
40 : const unsigned char* ptr8 = tommy_cast(const unsigned char*, ptr);
41 : return ptr8[0] + ((tommy_uint32_t)ptr8[1] << 8) + ((tommy_uint32_t)ptr8[2] << 16) + ((tommy_uint32_t)ptr8[3] << 24);
42 : #endif
43 : }
44 :
45 : #define tommy_rot(x, k) \
46 : (((x) << (k)) | ((x) >> (32 - (k))))
47 :
48 : #define tommy_mix(a, b, c) \
49 : do { \
50 : a -= c; a ^= tommy_rot(c, 4); c += b; \
51 : b -= a; b ^= tommy_rot(a, 6); a += c; \
52 : c -= b; c ^= tommy_rot(b, 8); b += a; \
53 : a -= c; a ^= tommy_rot(c, 16); c += b; \
54 : b -= a; b ^= tommy_rot(a, 19); a += c; \
55 : c -= b; c ^= tommy_rot(b, 4); b += a; \
56 : } while (0)
57 :
58 : #define tommy_final(a, b, c) \
59 : do { \
60 : c ^= b; c -= tommy_rot(b, 14); \
61 : a ^= c; a -= tommy_rot(c, 11); \
62 : b ^= a; b -= tommy_rot(a, 25); \
63 : c ^= b; c -= tommy_rot(b, 16); \
64 : a ^= c; a -= tommy_rot(c, 4); \
65 : b ^= a; b -= tommy_rot(a, 14); \
66 : c ^= b; c -= tommy_rot(b, 24); \
67 : } while (0)
68 :
69 16777239 : tommy_uint32_t tommy_hash_u32(tommy_uint32_t init_val, const void* void_key, tommy_size_t key_len)
70 : {
71 16777239 : const unsigned char* key = tommy_cast(const unsigned char*, void_key);
72 : tommy_uint32_t a, b, c;
73 :
74 16777239 : a = b = c = 0xdeadbeef + ((tommy_uint32_t)key_len) + init_val;
75 :
76 50331709 : while (key_len > 12) {
77 16777231 : a += tommy_le_uint32_read(key + 0);
78 16777231 : b += tommy_le_uint32_read(key + 4);
79 16777231 : c += tommy_le_uint32_read(key + 8);
80 :
81 16777231 : tommy_mix(a, b, c);
82 :
83 16777231 : key_len -= 12;
84 16777231 : key += 12;
85 : }
86 :
87 16777239 : switch (key_len) {
88 : case 0 :
89 1 : return c; /* used only when called with a zero length */
90 : case 12 :
91 1 : c += tommy_le_uint32_read(key + 8);
92 1 : b += tommy_le_uint32_read(key + 4);
93 1 : a += tommy_le_uint32_read(key + 0);
94 1 : break;
95 1 : case 11 : c += ((tommy_uint32_t)key[10]) << 16; /* fallthrough */
96 2 : case 10 : c += ((tommy_uint32_t)key[9]) << 8; /* fallthrough */
97 3 : case 9 : c += key[8]; /* fallthrough */
98 : case 8 :
99 4 : b += tommy_le_uint32_read(key + 4);
100 4 : a += tommy_le_uint32_read(key + 0);
101 4 : break;
102 2 : case 7 : b += ((tommy_uint32_t)key[6]) << 16; /* fallthrough */
103 3 : case 6 : b += ((tommy_uint32_t)key[5]) << 8; /* fallthrough */
104 4 : case 5 : b += key[4]; /* fallthrough */
105 : case 4 :
106 16777222 : a += tommy_le_uint32_read(key + 0);
107 16777222 : break;
108 3 : case 3 : a += ((tommy_uint32_t)key[2]) << 16; /* fallthrough */
109 8 : case 2 : a += ((tommy_uint32_t)key[1]) << 8; /* fallthrough */
110 11 : case 1 : a += key[0]; /* fallthrough */
111 : }
112 :
113 16777238 : tommy_final(a, b, c);
114 :
115 16777238 : return c;
116 : }
117 :
118 16777239 : tommy_uint64_t tommy_hash_u64(tommy_uint64_t init_val, const void* void_key, tommy_size_t key_len)
119 : {
120 16777239 : const unsigned char* key = tommy_cast(const unsigned char*, void_key);
121 : tommy_uint32_t a, b, c;
122 :
123 16777239 : a = b = c = 0xdeadbeef + ((tommy_uint32_t)key_len) + (init_val & 0xffffffff);
124 16777239 : c += init_val >> 32;
125 :
126 50331709 : while (key_len > 12) {
127 16777231 : a += tommy_le_uint32_read(key + 0);
128 16777231 : b += tommy_le_uint32_read(key + 4);
129 16777231 : c += tommy_le_uint32_read(key + 8);
130 :
131 16777231 : tommy_mix(a, b, c);
132 :
133 16777231 : key_len -= 12;
134 16777231 : key += 12;
135 : }
136 :
137 16777239 : switch (key_len) {
138 : case 0 :
139 1 : return c + ((tommy_uint64_t)b << 32); /* used only when called with a zero length */
140 : case 12 :
141 1 : c += tommy_le_uint32_read(key + 8);
142 1 : b += tommy_le_uint32_read(key + 4);
143 1 : a += tommy_le_uint32_read(key + 0);
144 1 : break;
145 1 : case 11 : c += ((tommy_uint32_t)key[10]) << 16; /* fallthrough */
146 2 : case 10 : c += ((tommy_uint32_t)key[9]) << 8; /* fallthrough */
147 3 : case 9 : c += key[8]; /* fallthrough */
148 : case 8 :
149 4 : b += tommy_le_uint32_read(key + 4);
150 4 : a += tommy_le_uint32_read(key + 0);
151 4 : break;
152 2 : case 7 : b += ((tommy_uint32_t)key[6]) << 16; /* fallthrough */
153 3 : case 6 : b += ((tommy_uint32_t)key[5]) << 8; /* fallthrough */
154 4 : case 5 : b += key[4]; /* fallthrough */
155 : case 4 :
156 16777222 : a += tommy_le_uint32_read(key + 0);
157 16777222 : break;
158 3 : case 3 : a += ((tommy_uint32_t)key[2]) << 16; /* fallthrough */
159 8 : case 2 : a += ((tommy_uint32_t)key[1]) << 8; /* fallthrough */
160 11 : case 1 : a += key[0]; /* fallthrough */
161 : }
162 :
163 16777238 : tommy_final(a, b, c);
164 :
165 16777238 : return c + ((tommy_uint64_t)b << 32);
166 : }
167 :
168 16777239 : tommy_uint32_t tommy_strhash_u32(tommy_uint64_t init_val, const void* void_key)
169 : {
170 16777239 : const unsigned char* key = tommy_cast(const unsigned char*, void_key);
171 : tommy_uint32_t a, b, c;
172 16777239 : tommy_uint32_t m[3] = { 0xff, 0xff00, 0xff0000 };
173 :
174 16777239 : a = b = c = 0xdeadbeef + init_val;
175 : /* this is different than original lookup3 and the result won't match */
176 :
177 : while (1) {
178 33554471 : tommy_uint32_t v = tommy_le_uint32_read(key);
179 :
180 33554471 : if (tommy_haszero_u32(v)) {
181 16777229 : if (v & m[0]) {
182 16777227 : a += v & m[0];
183 16777227 : if (v & m[1]) {
184 16777224 : a += v & m[1];
185 16777224 : if (v & m[2])
186 16777219 : a += v & m[2];
187 : }
188 : }
189 :
190 16777229 : break;
191 : }
192 :
193 16777242 : a += v;
194 :
195 16777242 : v = tommy_le_uint32_read(key + 4);
196 :
197 16777242 : if (tommy_haszero_u32(v)) {
198 6 : if (v & m[0]) {
199 4 : b += v & m[0];
200 4 : if (v & m[1]) {
201 3 : b += v & m[1];
202 3 : if (v & m[2])
203 2 : b += v & m[2];
204 : }
205 : }
206 :
207 6 : break;
208 : }
209 :
210 16777236 : b += v;
211 :
212 16777236 : v = tommy_le_uint32_read(key + 8);
213 :
214 16777236 : if (tommy_haszero_u32(v)) {
215 4 : if (v & m[0]) {
216 3 : c += v & m[0];
217 3 : if (v & m[1]) {
218 2 : c += v & m[1];
219 2 : if (v & m[2])
220 1 : c += v & m[2];
221 : }
222 : }
223 :
224 4 : break;
225 : }
226 :
227 16777232 : c += v;
228 :
229 16777232 : tommy_mix(a, b, c);
230 :
231 16777232 : key += 12;
232 16777232 : }
233 :
234 : /* for lengths that are multiplers of 12 we already have called mix */
235 : /* this is different than the original lookup3 and the result won't match */
236 :
237 16777239 : tommy_final(a, b, c);
238 :
239 16777239 : return c;
240 : }
241 :
|