Line data Source code
1 : // SPDX-License-Identifier: BSD-2-Clause
2 : // Copyright (C) 2010 Andrea Mazzoleni
3 :
4 : #include "tommyhash.h"
5 :
6 : /******************************************************************************/
7 : /* hash */
8 :
9 : #include <string.h> /* for memcpy */
10 :
11 : /**
12 : * Swap endianness.
13 : * They are needed only if BigEndian.
14 : */
15 : #if defined(__GNUC__)
16 : #define tommy_swap32(x) __builtin_bswap32(x)
17 : #else
18 : tommy_inline tommy_uint32_t tommy_swap32(tommy_uint32_t v)
19 : {
20 : return ((v & 0xFF000000) >> 24) |
21 : ((v & 0x00FF0000) >> 8) |
22 : ((v & 0x0000FF00) << 8) |
23 : ((v & 0x000000FF) << 24);
24 : }
25 : #endif
26 :
27 12735841 : tommy_inline tommy_uint32_t tommy_le_uint32_read(const void* ptr)
28 : {
29 : tommy_uint32_t v;
30 12735841 : memcpy(&v, ptr, sizeof(v));
31 : #if defined(WORDS_BIGENDIAN) || defined(__BIG_ENDIAN__) || \
32 : (defined(__BYTE_ORDER__) && __BYTE_ORDER__ == __ORDER_BIG_ENDIAN__)
33 : v = tommy_swap32(v);
34 : #endif
35 12735841 : return v;
36 : }
37 :
38 : #define tommy_rot(x, k) \
39 : (((x) << (k)) | ((x) >> (32 - (k))))
40 :
41 : #define tommy_mix(a, b, c) \
42 : do { \
43 : a -= c; a ^= tommy_rot(c, 4); c += b; \
44 : b -= a; b ^= tommy_rot(a, 6); a += c; \
45 : c -= b; c ^= tommy_rot(b, 8); b += a; \
46 : a -= c; a ^= tommy_rot(c, 16); c += b; \
47 : b -= a; b ^= tommy_rot(a, 19); a += c; \
48 : c -= b; c ^= tommy_rot(b, 4); b += a; \
49 : } while (0)
50 :
51 : #define tommy_final(a, b, c) \
52 : do { \
53 : c ^= b; c -= tommy_rot(b, 14); \
54 : a ^= c; a -= tommy_rot(c, 11); \
55 : b ^= a; b -= tommy_rot(a, 25); \
56 : c ^= b; c -= tommy_rot(b, 16); \
57 : a ^= c; a -= tommy_rot(c, 4); \
58 : b ^= a; b -= tommy_rot(a, 14); \
59 : c ^= b; c -= tommy_rot(b, 24); \
60 : } while (0)
61 :
62 4407343 : TOMMY_API tommy_uint32_t tommy_hash_u32(tommy_uint32_t init_val, const void* void_key, tommy_size_t key_len)
63 : {
64 4407343 : const unsigned char* key = tommy_cast(const unsigned char*, void_key);
65 : tommy_uint32_t a, b, c;
66 :
67 4407343 : a = b = c = 0xdeadbeef + ((tommy_uint32_t)key_len) + init_val;
68 :
69 6697479 : while (key_len > 12) {
70 2290136 : a += tommy_le_uint32_read(key + 0);
71 2290136 : b += tommy_le_uint32_read(key + 4);
72 2290136 : c += tommy_le_uint32_read(key + 8);
73 :
74 2290136 : tommy_mix(a, b, c);
75 :
76 2290136 : key_len -= 12;
77 2290136 : key += 12;
78 : }
79 :
80 4407343 : switch (key_len) {
81 1 : case 0 :
82 1 : return c; /* used only when called with a zero length */
83 222580 : case 12 :
84 222580 : c += tommy_le_uint32_read(key + 8);
85 222580 : b += tommy_le_uint32_read(key + 4);
86 222580 : a += tommy_le_uint32_read(key + 0);
87 222580 : break;
88 236488 : case 11 : c += ((tommy_uint32_t)key[10]) << 16; /* fallthrough */
89 691096 : case 10 : c += ((tommy_uint32_t)key[9]) << 8; /* fallthrough */
90 1148830 : case 9 : c += key[8]; /* fallthrough */
91 1594846 : case 8 :
92 1594846 : b += tommy_le_uint32_read(key + 4);
93 1594846 : a += tommy_le_uint32_read(key + 0);
94 1594846 : break;
95 448713 : case 7 : b += ((tommy_uint32_t)key[6]) << 16; /* fallthrough */
96 879234 : case 6 : b += ((tommy_uint32_t)key[5]) << 8; /* fallthrough */
97 1331968 : case 5 : b += key[4]; /* fallthrough */
98 1807090 : case 4 :
99 1807090 : a += tommy_le_uint32_read(key + 0);
100 1807090 : break;
101 327356 : case 3 : a += ((tommy_uint32_t)key[2]) << 16; /* fallthrough */
102 553422 : case 2 : a += ((tommy_uint32_t)key[1]) << 8; /* fallthrough */
103 782826 : case 1 : a += key[0]; /* fallthrough */
104 : }
105 :
106 4407342 : tommy_final(a, b, c);
107 :
108 4407342 : return c;
109 : }
110 :
111 19 : TOMMY_API tommy_uint64_t tommy_hash_u64(tommy_uint64_t init_val, const void* void_key, tommy_size_t key_len)
112 : {
113 19 : const unsigned char* key = tommy_cast(const unsigned char*, void_key);
114 : tommy_uint32_t a, b, c;
115 :
116 19 : a = b = c = 0xdeadbeef + ((tommy_uint32_t)key_len) + (init_val & 0xffffffff);
117 19 : c += init_val >> 32;
118 :
119 30 : while (key_len > 12) {
120 11 : a += tommy_le_uint32_read(key + 0);
121 11 : b += tommy_le_uint32_read(key + 4);
122 11 : c += tommy_le_uint32_read(key + 8);
123 :
124 11 : tommy_mix(a, b, c);
125 :
126 11 : key_len -= 12;
127 11 : key += 12;
128 : }
129 :
130 19 : switch (key_len) {
131 1 : case 0 :
132 1 : return c + ((tommy_uint64_t)b << 32); /* used only when called with a zero length */
133 1 : case 12 :
134 1 : c += tommy_le_uint32_read(key + 8);
135 1 : b += tommy_le_uint32_read(key + 4);
136 1 : a += tommy_le_uint32_read(key + 0);
137 1 : break;
138 1 : case 11 : c += ((tommy_uint32_t)key[10]) << 16; /* fallthrough */
139 2 : case 10 : c += ((tommy_uint32_t)key[9]) << 8; /* fallthrough */
140 3 : case 9 : c += key[8]; /* fallthrough */
141 4 : case 8 :
142 4 : b += tommy_le_uint32_read(key + 4);
143 4 : a += tommy_le_uint32_read(key + 0);
144 4 : break;
145 2 : case 7 : b += ((tommy_uint32_t)key[6]) << 16; /* fallthrough */
146 3 : case 6 : b += ((tommy_uint32_t)key[5]) << 8; /* fallthrough */
147 4 : case 5 : b += key[4]; /* fallthrough */
148 5 : case 4 :
149 5 : a += tommy_le_uint32_read(key + 0);
150 5 : break;
151 2 : case 3 : a += ((tommy_uint32_t)key[2]) << 16; /* fallthrough */
152 6 : case 2 : a += ((tommy_uint32_t)key[1]) << 8; /* fallthrough */
153 8 : case 1 : a += key[0]; /* fallthrough */
154 : }
155 :
156 18 : tommy_final(a, b, c);
157 :
158 18 : return c + ((tommy_uint64_t)b << 32);
159 : }
160 :
161 72593 : TOMMY_API tommy_uint32_t tommy_strhash_u32(tommy_uint32_t init_val, const void* void_key)
162 : {
163 72593 : const unsigned char* key = tommy_cast(const unsigned char*, void_key);
164 : tommy_uint32_t a, b, c;
165 72593 : tommy_uint32_t m[3] = { 0xff, 0xff00, 0xff0000 };
166 :
167 72593 : a = b = c = 0xdeadbeef + init_val;
168 : /* this is different than original lookup3 and the result won't match */
169 :
170 16 : while (1) {
171 72609 : tommy_uint32_t v = tommy_le_uint32_read(key);
172 :
173 72609 : if (tommy_haszero_u32(v)) {
174 13 : if (v & m[0]) {
175 11 : a += v & m[0];
176 11 : if (v & m[1]) {
177 8 : a += v & m[1];
178 8 : if (v & m[2])
179 3 : a += v & m[2];
180 : }
181 : }
182 :
183 13 : break;
184 : }
185 :
186 72596 : a += v;
187 :
188 72596 : v = tommy_le_uint32_read(key + 4);
189 :
190 72596 : if (tommy_haszero_u32(v)) {
191 16939 : if (v & m[0]) {
192 16937 : b += v & m[0];
193 16937 : if (v & m[1]) {
194 2422 : b += v & m[1];
195 2422 : if (v & m[2])
196 2 : b += v & m[2];
197 : }
198 : }
199 :
200 16939 : break;
201 : }
202 :
203 55657 : b += v;
204 :
205 55657 : v = tommy_le_uint32_read(key + 8);
206 :
207 55657 : if (tommy_haszero_u32(v)) {
208 55641 : if (v & m[0]) {
209 36288 : c += v & m[0];
210 36288 : if (v & m[1]) {
211 36287 : c += v & m[1];
212 36287 : if (v & m[2])
213 1 : c += v & m[2];
214 : }
215 : }
216 :
217 55641 : break;
218 : }
219 :
220 16 : c += v;
221 :
222 16 : tommy_mix(a, b, c);
223 :
224 16 : key += 12;
225 : }
226 :
227 : /* for lengths that are multipliers of 12 we already have called mix */
228 : /* this is different than the original lookup3 and the result won't match */
229 :
230 72593 : tommy_final(a, b, c);
231 :
232 72593 : return c;
233 : }
234 :
|
