1 | /* |
2 | SipHash reference C implementation |
3 | |
4 | Copyright (c) 2012-2016 Jean-Philippe Aumasson |
5 | <[email protected]> |
6 | Copyright (c) 2012-2014 Daniel J. Bernstein <[email protected]> |
7 | Copyright (c) 2017 Salvatore Sanfilippo <[email protected]> |
8 | |
9 | To the extent possible under law, the author(s) have dedicated all copyright |
10 | and related and neighboring rights to this software to the public domain |
11 | worldwide. This software is distributed without any warranty. |
12 | |
13 | You should have received a copy of the CC0 Public Domain Dedication along |
14 | with this software. If not, see |
15 | <http://creativecommons.org/publicdomain/zero/1.0/>. |
16 | |
17 | ---------------------------------------------------------------------------- |
18 | |
19 | This version was modified by Salvatore Sanfilippo <[email protected]> |
20 | in the following ways: |
21 | |
22 | 1. We use SipHash 1-2. This is not believed to be as strong as the |
23 | suggested 2-4 variant, but AFAIK there are not trivial attacks |
24 | against this reduced-rounds version, and it runs at the same speed |
25 | as Murmurhash2 that we used previously, while the 2-4 variant slowed |
26 | down Redis by a 4% figure more or less. |
27 | 2. Hard-code rounds in the hope the compiler can optimize it more |
28 | in this raw from. Anyway we always want the standard 2-4 variant. |
29 | 3. Modify the prototype and implementation so that the function directly |
30 | returns an uint64_t value, the hash itself, instead of receiving an |
31 | output buffer. This also means that the output size is set to 8 bytes |
32 | and the 16 bytes output code handling was removed. |
33 | 4. Provide a case insensitive variant to be used when hashing strings that |
34 | must be considered identical by the hash table regardless of the case. |
35 | If we don't have directly a case insensitive hash function, we need to |
36 | perform a text transformation in some temporary buffer, which is costly. |
37 | 5. Remove debugging code. |
38 | 6. Modified the original test.c file to be a stand-alone function testing |
39 | the function in the new form (returning an uint64_t) using just the |
40 | relevant test vector. |
41 | */ |
42 | #include <assert.h> |
43 | #include <stdint.h> |
44 | #include <stdio.h> |
45 | #include <string.h> |
46 | #include <ctype.h> |
47 | |
48 | /* Fast tolower() alike function that does not care about locale |
49 | * but just returns a-z instead of A-Z. */ |
50 | int siptlw(int c) { |
51 | if (c >= 'A' && c <= 'Z') { |
52 | return c+('a'-'A'); |
53 | } else { |
54 | return c; |
55 | } |
56 | } |
57 | |
58 | #if defined(__has_attribute) |
59 | #if __has_attribute(no_sanitize) |
60 | #define NO_SANITIZE(sanitizer) __attribute__((no_sanitize(sanitizer))) |
61 | #endif |
62 | #endif |
63 | |
64 | #if !defined(NO_SANITIZE) |
65 | #define NO_SANITIZE(sanitizer) |
66 | #endif |
67 | |
68 | /* Test of the CPU is Little Endian and supports not aligned accesses. |
69 | * Two interesting conditions to speedup the function that happen to be |
70 | * in most of x86 servers. */ |
71 | #if defined(__X86_64__) || defined(__x86_64__) || defined (__i386__) \ |
72 | || defined (__aarch64__) || defined (__arm64__) |
73 | #define UNALIGNED_LE_CPU |
74 | #endif |
75 | |
76 | #define ROTL(x, b) (uint64_t)(((x) << (b)) | ((x) >> (64 - (b)))) |
77 | |
78 | #define U32TO8_LE(p, v) \ |
79 | (p)[0] = (uint8_t)((v)); \ |
80 | (p)[1] = (uint8_t)((v) >> 8); \ |
81 | (p)[2] = (uint8_t)((v) >> 16); \ |
82 | (p)[3] = (uint8_t)((v) >> 24); |
83 | |
84 | #define U64TO8_LE(p, v) \ |
85 | U32TO8_LE((p), (uint32_t)((v))); \ |
86 | U32TO8_LE((p) + 4, (uint32_t)((v) >> 32)); |
87 | |
88 | #ifdef UNALIGNED_LE_CPU |
89 | #define U8TO64_LE(p) (*((uint64_t*)(p))) |
90 | #else |
91 | #define U8TO64_LE(p) \ |
92 | (((uint64_t)((p)[0])) | ((uint64_t)((p)[1]) << 8) | \ |
93 | ((uint64_t)((p)[2]) << 16) | ((uint64_t)((p)[3]) << 24) | \ |
94 | ((uint64_t)((p)[4]) << 32) | ((uint64_t)((p)[5]) << 40) | \ |
95 | ((uint64_t)((p)[6]) << 48) | ((uint64_t)((p)[7]) << 56)) |
96 | #endif |
97 | |
98 | #define U8TO64_LE_NOCASE(p) \ |
99 | (((uint64_t)(siptlw((p)[0]))) | \ |
100 | ((uint64_t)(siptlw((p)[1])) << 8) | \ |
101 | ((uint64_t)(siptlw((p)[2])) << 16) | \ |
102 | ((uint64_t)(siptlw((p)[3])) << 24) | \ |
103 | ((uint64_t)(siptlw((p)[4])) << 32) | \ |
104 | ((uint64_t)(siptlw((p)[5])) << 40) | \ |
105 | ((uint64_t)(siptlw((p)[6])) << 48) | \ |
106 | ((uint64_t)(siptlw((p)[7])) << 56)) |
107 | |
108 | #define SIPROUND \ |
109 | do { \ |
110 | v0 += v1; \ |
111 | v1 = ROTL(v1, 13); \ |
112 | v1 ^= v0; \ |
113 | v0 = ROTL(v0, 32); \ |
114 | v2 += v3; \ |
115 | v3 = ROTL(v3, 16); \ |
116 | v3 ^= v2; \ |
117 | v0 += v3; \ |
118 | v3 = ROTL(v3, 21); \ |
119 | v3 ^= v0; \ |
120 | v2 += v1; \ |
121 | v1 = ROTL(v1, 17); \ |
122 | v1 ^= v2; \ |
123 | v2 = ROTL(v2, 32); \ |
124 | } while (0) |
125 | |
126 | NO_SANITIZE("alignment" ) |
127 | uint64_t siphash(const uint8_t *in, const size_t inlen, const uint8_t *k) { |
128 | #ifndef UNALIGNED_LE_CPU |
129 | uint64_t hash; |
130 | uint8_t *out = (uint8_t*) &hash; |
131 | #endif |
132 | uint64_t v0 = 0x736f6d6570736575ULL; |
133 | uint64_t v1 = 0x646f72616e646f6dULL; |
134 | uint64_t v2 = 0x6c7967656e657261ULL; |
135 | uint64_t v3 = 0x7465646279746573ULL; |
136 | uint64_t k0 = U8TO64_LE(k); |
137 | uint64_t k1 = U8TO64_LE(k + 8); |
138 | uint64_t m; |
139 | const uint8_t *end = in + inlen - (inlen % sizeof(uint64_t)); |
140 | const int left = inlen & 7; |
141 | uint64_t b = ((uint64_t)inlen) << 56; |
142 | v3 ^= k1; |
143 | v2 ^= k0; |
144 | v1 ^= k1; |
145 | v0 ^= k0; |
146 | |
147 | for (; in != end; in += 8) { |
148 | m = U8TO64_LE(in); |
149 | v3 ^= m; |
150 | |
151 | SIPROUND; |
152 | |
153 | v0 ^= m; |
154 | } |
155 | |
156 | switch (left) { |
157 | case 7: b |= ((uint64_t)in[6]) << 48; /* fall-thru */ |
158 | case 6: b |= ((uint64_t)in[5]) << 40; /* fall-thru */ |
159 | case 5: b |= ((uint64_t)in[4]) << 32; /* fall-thru */ |
160 | case 4: b |= ((uint64_t)in[3]) << 24; /* fall-thru */ |
161 | case 3: b |= ((uint64_t)in[2]) << 16; /* fall-thru */ |
162 | case 2: b |= ((uint64_t)in[1]) << 8; /* fall-thru */ |
163 | case 1: b |= ((uint64_t)in[0]); break; |
164 | case 0: break; |
165 | } |
166 | |
167 | v3 ^= b; |
168 | |
169 | SIPROUND; |
170 | |
171 | v0 ^= b; |
172 | v2 ^= 0xff; |
173 | |
174 | SIPROUND; |
175 | SIPROUND; |
176 | |
177 | b = v0 ^ v1 ^ v2 ^ v3; |
178 | #ifndef UNALIGNED_LE_CPU |
179 | U64TO8_LE(out, b); |
180 | return hash; |
181 | #else |
182 | return b; |
183 | #endif |
184 | } |
185 | |
186 | NO_SANITIZE("alignment" ) |
187 | uint64_t siphash_nocase(const uint8_t *in, const size_t inlen, const uint8_t *k) |
188 | { |
189 | #ifndef UNALIGNED_LE_CPU |
190 | uint64_t hash; |
191 | uint8_t *out = (uint8_t*) &hash; |
192 | #endif |
193 | uint64_t v0 = 0x736f6d6570736575ULL; |
194 | uint64_t v1 = 0x646f72616e646f6dULL; |
195 | uint64_t v2 = 0x6c7967656e657261ULL; |
196 | uint64_t v3 = 0x7465646279746573ULL; |
197 | uint64_t k0 = U8TO64_LE(k); |
198 | uint64_t k1 = U8TO64_LE(k + 8); |
199 | uint64_t m; |
200 | const uint8_t *end = in + inlen - (inlen % sizeof(uint64_t)); |
201 | const int left = inlen & 7; |
202 | uint64_t b = ((uint64_t)inlen) << 56; |
203 | v3 ^= k1; |
204 | v2 ^= k0; |
205 | v1 ^= k1; |
206 | v0 ^= k0; |
207 | |
208 | for (; in != end; in += 8) { |
209 | m = U8TO64_LE_NOCASE(in); |
210 | v3 ^= m; |
211 | |
212 | SIPROUND; |
213 | |
214 | v0 ^= m; |
215 | } |
216 | |
217 | switch (left) { |
218 | case 7: b |= ((uint64_t)siptlw(in[6])) << 48; /* fall-thru */ |
219 | case 6: b |= ((uint64_t)siptlw(in[5])) << 40; /* fall-thru */ |
220 | case 5: b |= ((uint64_t)siptlw(in[4])) << 32; /* fall-thru */ |
221 | case 4: b |= ((uint64_t)siptlw(in[3])) << 24; /* fall-thru */ |
222 | case 3: b |= ((uint64_t)siptlw(in[2])) << 16; /* fall-thru */ |
223 | case 2: b |= ((uint64_t)siptlw(in[1])) << 8; /* fall-thru */ |
224 | case 1: b |= ((uint64_t)siptlw(in[0])); break; |
225 | case 0: break; |
226 | } |
227 | |
228 | v3 ^= b; |
229 | |
230 | SIPROUND; |
231 | |
232 | v0 ^= b; |
233 | v2 ^= 0xff; |
234 | |
235 | SIPROUND; |
236 | SIPROUND; |
237 | |
238 | b = v0 ^ v1 ^ v2 ^ v3; |
239 | #ifndef UNALIGNED_LE_CPU |
240 | U64TO8_LE(out, b); |
241 | return hash; |
242 | #else |
243 | return b; |
244 | #endif |
245 | } |
246 | |
247 | |
248 | /* --------------------------------- TEST ------------------------------------ */ |
249 | |
250 | #ifdef SIPHASH_TEST |
251 | |
252 | const uint8_t vectors_sip64[64][8] = { |
253 | { 0x31, 0x0e, 0x0e, 0xdd, 0x47, 0xdb, 0x6f, 0x72, }, |
254 | { 0xfd, 0x67, 0xdc, 0x93, 0xc5, 0x39, 0xf8, 0x74, }, |
255 | { 0x5a, 0x4f, 0xa9, 0xd9, 0x09, 0x80, 0x6c, 0x0d, }, |
256 | { 0x2d, 0x7e, 0xfb, 0xd7, 0x96, 0x66, 0x67, 0x85, }, |
257 | { 0xb7, 0x87, 0x71, 0x27, 0xe0, 0x94, 0x27, 0xcf, }, |
258 | { 0x8d, 0xa6, 0x99, 0xcd, 0x64, 0x55, 0x76, 0x18, }, |
259 | { 0xce, 0xe3, 0xfe, 0x58, 0x6e, 0x46, 0xc9, 0xcb, }, |
260 | { 0x37, 0xd1, 0x01, 0x8b, 0xf5, 0x00, 0x02, 0xab, }, |
261 | { 0x62, 0x24, 0x93, 0x9a, 0x79, 0xf5, 0xf5, 0x93, }, |
262 | { 0xb0, 0xe4, 0xa9, 0x0b, 0xdf, 0x82, 0x00, 0x9e, }, |
263 | { 0xf3, 0xb9, 0xdd, 0x94, 0xc5, 0xbb, 0x5d, 0x7a, }, |
264 | { 0xa7, 0xad, 0x6b, 0x22, 0x46, 0x2f, 0xb3, 0xf4, }, |
265 | { 0xfb, 0xe5, 0x0e, 0x86, 0xbc, 0x8f, 0x1e, 0x75, }, |
266 | { 0x90, 0x3d, 0x84, 0xc0, 0x27, 0x56, 0xea, 0x14, }, |
267 | { 0xee, 0xf2, 0x7a, 0x8e, 0x90, 0xca, 0x23, 0xf7, }, |
268 | { 0xe5, 0x45, 0xbe, 0x49, 0x61, 0xca, 0x29, 0xa1, }, |
269 | { 0xdb, 0x9b, 0xc2, 0x57, 0x7f, 0xcc, 0x2a, 0x3f, }, |
270 | { 0x94, 0x47, 0xbe, 0x2c, 0xf5, 0xe9, 0x9a, 0x69, }, |
271 | { 0x9c, 0xd3, 0x8d, 0x96, 0xf0, 0xb3, 0xc1, 0x4b, }, |
272 | { 0xbd, 0x61, 0x79, 0xa7, 0x1d, 0xc9, 0x6d, 0xbb, }, |
273 | { 0x98, 0xee, 0xa2, 0x1a, 0xf2, 0x5c, 0xd6, 0xbe, }, |
274 | { 0xc7, 0x67, 0x3b, 0x2e, 0xb0, 0xcb, 0xf2, 0xd0, }, |
275 | { 0x88, 0x3e, 0xa3, 0xe3, 0x95, 0x67, 0x53, 0x93, }, |
276 | { 0xc8, 0xce, 0x5c, 0xcd, 0x8c, 0x03, 0x0c, 0xa8, }, |
277 | { 0x94, 0xaf, 0x49, 0xf6, 0xc6, 0x50, 0xad, 0xb8, }, |
278 | { 0xea, 0xb8, 0x85, 0x8a, 0xde, 0x92, 0xe1, 0xbc, }, |
279 | { 0xf3, 0x15, 0xbb, 0x5b, 0xb8, 0x35, 0xd8, 0x17, }, |
280 | { 0xad, 0xcf, 0x6b, 0x07, 0x63, 0x61, 0x2e, 0x2f, }, |
281 | { 0xa5, 0xc9, 0x1d, 0xa7, 0xac, 0xaa, 0x4d, 0xde, }, |
282 | { 0x71, 0x65, 0x95, 0x87, 0x66, 0x50, 0xa2, 0xa6, }, |
283 | { 0x28, 0xef, 0x49, 0x5c, 0x53, 0xa3, 0x87, 0xad, }, |
284 | { 0x42, 0xc3, 0x41, 0xd8, 0xfa, 0x92, 0xd8, 0x32, }, |
285 | { 0xce, 0x7c, 0xf2, 0x72, 0x2f, 0x51, 0x27, 0x71, }, |
286 | { 0xe3, 0x78, 0x59, 0xf9, 0x46, 0x23, 0xf3, 0xa7, }, |
287 | { 0x38, 0x12, 0x05, 0xbb, 0x1a, 0xb0, 0xe0, 0x12, }, |
288 | { 0xae, 0x97, 0xa1, 0x0f, 0xd4, 0x34, 0xe0, 0x15, }, |
289 | { 0xb4, 0xa3, 0x15, 0x08, 0xbe, 0xff, 0x4d, 0x31, }, |
290 | { 0x81, 0x39, 0x62, 0x29, 0xf0, 0x90, 0x79, 0x02, }, |
291 | { 0x4d, 0x0c, 0xf4, 0x9e, 0xe5, 0xd4, 0xdc, 0xca, }, |
292 | { 0x5c, 0x73, 0x33, 0x6a, 0x76, 0xd8, 0xbf, 0x9a, }, |
293 | { 0xd0, 0xa7, 0x04, 0x53, 0x6b, 0xa9, 0x3e, 0x0e, }, |
294 | { 0x92, 0x59, 0x58, 0xfc, 0xd6, 0x42, 0x0c, 0xad, }, |
295 | { 0xa9, 0x15, 0xc2, 0x9b, 0xc8, 0x06, 0x73, 0x18, }, |
296 | { 0x95, 0x2b, 0x79, 0xf3, 0xbc, 0x0a, 0xa6, 0xd4, }, |
297 | { 0xf2, 0x1d, 0xf2, 0xe4, 0x1d, 0x45, 0x35, 0xf9, }, |
298 | { 0x87, 0x57, 0x75, 0x19, 0x04, 0x8f, 0x53, 0xa9, }, |
299 | { 0x10, 0xa5, 0x6c, 0xf5, 0xdf, 0xcd, 0x9a, 0xdb, }, |
300 | { 0xeb, 0x75, 0x09, 0x5c, 0xcd, 0x98, 0x6c, 0xd0, }, |
301 | { 0x51, 0xa9, 0xcb, 0x9e, 0xcb, 0xa3, 0x12, 0xe6, }, |
302 | { 0x96, 0xaf, 0xad, 0xfc, 0x2c, 0xe6, 0x66, 0xc7, }, |
303 | { 0x72, 0xfe, 0x52, 0x97, 0x5a, 0x43, 0x64, 0xee, }, |
304 | { 0x5a, 0x16, 0x45, 0xb2, 0x76, 0xd5, 0x92, 0xa1, }, |
305 | { 0xb2, 0x74, 0xcb, 0x8e, 0xbf, 0x87, 0x87, 0x0a, }, |
306 | { 0x6f, 0x9b, 0xb4, 0x20, 0x3d, 0xe7, 0xb3, 0x81, }, |
307 | { 0xea, 0xec, 0xb2, 0xa3, 0x0b, 0x22, 0xa8, 0x7f, }, |
308 | { 0x99, 0x24, 0xa4, 0x3c, 0xc1, 0x31, 0x57, 0x24, }, |
309 | { 0xbd, 0x83, 0x8d, 0x3a, 0xaf, 0xbf, 0x8d, 0xb7, }, |
310 | { 0x0b, 0x1a, 0x2a, 0x32, 0x65, 0xd5, 0x1a, 0xea, }, |
311 | { 0x13, 0x50, 0x79, 0xa3, 0x23, 0x1c, 0xe6, 0x60, }, |
312 | { 0x93, 0x2b, 0x28, 0x46, 0xe4, 0xd7, 0x06, 0x66, }, |
313 | { 0xe1, 0x91, 0x5f, 0x5c, 0xb1, 0xec, 0xa4, 0x6c, }, |
314 | { 0xf3, 0x25, 0x96, 0x5c, 0xa1, 0x6d, 0x62, 0x9f, }, |
315 | { 0x57, 0x5f, 0xf2, 0x8e, 0x60, 0x38, 0x1b, 0xe5, }, |
316 | { 0x72, 0x45, 0x06, 0xeb, 0x4c, 0x32, 0x8a, 0x95, }, |
317 | }; |
318 | |
319 | |
320 | /* Test siphash using a test vector. Returns 0 if the function passed |
321 | * all the tests, otherwise 1 is returned. |
322 | * |
323 | * IMPORTANT: The test vector is for SipHash 2-4. Before running |
324 | * the test revert back the siphash() function to 2-4 rounds since |
325 | * now it uses 1-2 rounds. */ |
326 | int siphash_test(void) { |
327 | uint8_t in[64], k[16]; |
328 | int i; |
329 | int fails = 0; |
330 | |
331 | for (i = 0; i < 16; ++i) |
332 | k[i] = i; |
333 | |
334 | for (i = 0; i < 64; ++i) { |
335 | in[i] = i; |
336 | uint64_t hash = siphash(in, i, k); |
337 | const uint8_t *v = NULL; |
338 | v = (uint8_t *)vectors_sip64; |
339 | if (memcmp(&hash, v + (i * 8), 8)) { |
340 | /* printf("fail for %d bytes\n", i); */ |
341 | fails++; |
342 | } |
343 | } |
344 | |
345 | /* Run a few basic tests with the case insensitive version. */ |
346 | uint64_t h1, h2; |
347 | h1 = siphash((uint8_t*)"hello world" ,11,(uint8_t*)"1234567812345678" ); |
348 | h2 = siphash_nocase((uint8_t*)"hello world" ,11,(uint8_t*)"1234567812345678" ); |
349 | if (h1 != h2) fails++; |
350 | |
351 | h1 = siphash((uint8_t*)"hello world" ,11,(uint8_t*)"1234567812345678" ); |
352 | h2 = siphash_nocase((uint8_t*)"HELLO world" ,11,(uint8_t*)"1234567812345678" ); |
353 | if (h1 != h2) fails++; |
354 | |
355 | h1 = siphash((uint8_t*)"HELLO world" ,11,(uint8_t*)"1234567812345678" ); |
356 | h2 = siphash_nocase((uint8_t*)"HELLO world" ,11,(uint8_t*)"1234567812345678" ); |
357 | if (h1 == h2) fails++; |
358 | |
359 | if (!fails) return 0; |
360 | return 1; |
361 | } |
362 | |
363 | int main(void) { |
364 | if (siphash_test() == 0) { |
365 | printf("SipHash test: OK\n" ); |
366 | return 0; |
367 | } else { |
368 | printf("SipHash test: FAILED\n" ); |
369 | return 1; |
370 | } |
371 | } |
372 | |
373 | #endif |
374 | |