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. */
50int 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
126NO_SANITIZE("alignment")
127uint64_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
186NO_SANITIZE("alignment")
187uint64_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
252const 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. */
326int 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
363int 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