blob: 3ae58b4edad61527317f6a2b68f0343f8a654683
1 | /* Copyright (C) 2016 Jason A. Donenfeld <Jason@zx2c4.com>. All Rights Reserved. |
2 | * |
3 | * This file is provided under a dual BSD/GPLv2 license. |
4 | * |
5 | * SipHash: a fast short-input PRF |
6 | * https://131002.net/siphash/ |
7 | * |
8 | * This implementation is specifically for SipHash2-4 for a secure PRF |
9 | * and HalfSipHash1-3/SipHash1-3 for an insecure PRF only suitable for |
10 | * hashtables. |
11 | */ |
12 | |
13 | #include <linux/siphash.h> |
14 | #include <asm/unaligned.h> |
15 | |
16 | #if defined(CONFIG_DCACHE_WORD_ACCESS) && BITS_PER_LONG == 64 |
17 | #include <linux/dcache.h> |
18 | #include <asm/word-at-a-time.h> |
19 | #endif |
20 | |
21 | #define SIPROUND \ |
22 | do { \ |
23 | v0 += v1; v1 = rol64(v1, 13); v1 ^= v0; v0 = rol64(v0, 32); \ |
24 | v2 += v3; v3 = rol64(v3, 16); v3 ^= v2; \ |
25 | v0 += v3; v3 = rol64(v3, 21); v3 ^= v0; \ |
26 | v2 += v1; v1 = rol64(v1, 17); v1 ^= v2; v2 = rol64(v2, 32); \ |
27 | } while (0) |
28 | |
29 | #define PREAMBLE(len) \ |
30 | u64 v0 = 0x736f6d6570736575ULL; \ |
31 | u64 v1 = 0x646f72616e646f6dULL; \ |
32 | u64 v2 = 0x6c7967656e657261ULL; \ |
33 | u64 v3 = 0x7465646279746573ULL; \ |
34 | u64 b = ((u64)(len)) << 56; \ |
35 | v3 ^= key->key[1]; \ |
36 | v2 ^= key->key[0]; \ |
37 | v1 ^= key->key[1]; \ |
38 | v0 ^= key->key[0]; |
39 | |
40 | #define POSTAMBLE \ |
41 | v3 ^= b; \ |
42 | SIPROUND; \ |
43 | SIPROUND; \ |
44 | v0 ^= b; \ |
45 | v2 ^= 0xff; \ |
46 | SIPROUND; \ |
47 | SIPROUND; \ |
48 | SIPROUND; \ |
49 | SIPROUND; \ |
50 | return (v0 ^ v1) ^ (v2 ^ v3); |
51 | |
52 | u64 __siphash_aligned(const void *data, size_t len, const siphash_key_t *key) |
53 | { |
54 | const u8 *end = data + len - (len % sizeof(u64)); |
55 | const u8 left = len & (sizeof(u64) - 1); |
56 | u64 m; |
57 | PREAMBLE(len) |
58 | for (; data != end; data += sizeof(u64)) { |
59 | m = le64_to_cpup(data); |
60 | v3 ^= m; |
61 | SIPROUND; |
62 | SIPROUND; |
63 | v0 ^= m; |
64 | } |
65 | #if defined(CONFIG_DCACHE_WORD_ACCESS) && BITS_PER_LONG == 64 |
66 | if (left) |
67 | b |= le64_to_cpu((__force __le64)(load_unaligned_zeropad(data) & |
68 | bytemask_from_count(left))); |
69 | #else |
70 | switch (left) { |
71 | case 7: b |= ((u64)end[6]) << 48; |
72 | case 6: b |= ((u64)end[5]) << 40; |
73 | case 5: b |= ((u64)end[4]) << 32; |
74 | case 4: b |= le32_to_cpup(data); break; |
75 | case 3: b |= ((u64)end[2]) << 16; |
76 | case 2: b |= le16_to_cpup(data); break; |
77 | case 1: b |= end[0]; |
78 | } |
79 | #endif |
80 | POSTAMBLE |
81 | } |
82 | EXPORT_SYMBOL(__siphash_aligned); |
83 | |
84 | #ifndef CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS |
85 | u64 __siphash_unaligned(const void *data, size_t len, const siphash_key_t *key) |
86 | { |
87 | const u8 *end = data + len - (len % sizeof(u64)); |
88 | const u8 left = len & (sizeof(u64) - 1); |
89 | u64 m; |
90 | PREAMBLE(len) |
91 | for (; data != end; data += sizeof(u64)) { |
92 | m = get_unaligned_le64(data); |
93 | v3 ^= m; |
94 | SIPROUND; |
95 | SIPROUND; |
96 | v0 ^= m; |
97 | } |
98 | #if defined(CONFIG_DCACHE_WORD_ACCESS) && BITS_PER_LONG == 64 |
99 | if (left) |
100 | b |= le64_to_cpu((__force __le64)(load_unaligned_zeropad(data) & |
101 | bytemask_from_count(left))); |
102 | #else |
103 | switch (left) { |
104 | case 7: b |= ((u64)end[6]) << 48; |
105 | case 6: b |= ((u64)end[5]) << 40; |
106 | case 5: b |= ((u64)end[4]) << 32; |
107 | case 4: b |= get_unaligned_le32(end); break; |
108 | case 3: b |= ((u64)end[2]) << 16; |
109 | case 2: b |= get_unaligned_le16(end); break; |
110 | case 1: b |= end[0]; |
111 | } |
112 | #endif |
113 | POSTAMBLE |
114 | } |
115 | EXPORT_SYMBOL(__siphash_unaligned); |
116 | #endif |
117 | |
118 | /** |
119 | * siphash_1u64 - compute 64-bit siphash PRF value of a u64 |
120 | * @first: first u64 |
121 | * @key: the siphash key |
122 | */ |
123 | u64 siphash_1u64(const u64 first, const siphash_key_t *key) |
124 | { |
125 | PREAMBLE(8) |
126 | v3 ^= first; |
127 | SIPROUND; |
128 | SIPROUND; |
129 | v0 ^= first; |
130 | POSTAMBLE |
131 | } |
132 | EXPORT_SYMBOL(siphash_1u64); |
133 | |
134 | /** |
135 | * siphash_2u64 - compute 64-bit siphash PRF value of 2 u64 |
136 | * @first: first u64 |
137 | * @second: second u64 |
138 | * @key: the siphash key |
139 | */ |
140 | u64 siphash_2u64(const u64 first, const u64 second, const siphash_key_t *key) |
141 | { |
142 | PREAMBLE(16) |
143 | v3 ^= first; |
144 | SIPROUND; |
145 | SIPROUND; |
146 | v0 ^= first; |
147 | v3 ^= second; |
148 | SIPROUND; |
149 | SIPROUND; |
150 | v0 ^= second; |
151 | POSTAMBLE |
152 | } |
153 | EXPORT_SYMBOL(siphash_2u64); |
154 | |
155 | /** |
156 | * siphash_3u64 - compute 64-bit siphash PRF value of 3 u64 |
157 | * @first: first u64 |
158 | * @second: second u64 |
159 | * @third: third u64 |
160 | * @key: the siphash key |
161 | */ |
162 | u64 siphash_3u64(const u64 first, const u64 second, const u64 third, |
163 | const siphash_key_t *key) |
164 | { |
165 | PREAMBLE(24) |
166 | v3 ^= first; |
167 | SIPROUND; |
168 | SIPROUND; |
169 | v0 ^= first; |
170 | v3 ^= second; |
171 | SIPROUND; |
172 | SIPROUND; |
173 | v0 ^= second; |
174 | v3 ^= third; |
175 | SIPROUND; |
176 | SIPROUND; |
177 | v0 ^= third; |
178 | POSTAMBLE |
179 | } |
180 | EXPORT_SYMBOL(siphash_3u64); |
181 | |
182 | /** |
183 | * siphash_4u64 - compute 64-bit siphash PRF value of 4 u64 |
184 | * @first: first u64 |
185 | * @second: second u64 |
186 | * @third: third u64 |
187 | * @forth: forth u64 |
188 | * @key: the siphash key |
189 | */ |
190 | u64 siphash_4u64(const u64 first, const u64 second, const u64 third, |
191 | const u64 forth, const siphash_key_t *key) |
192 | { |
193 | PREAMBLE(32) |
194 | v3 ^= first; |
195 | SIPROUND; |
196 | SIPROUND; |
197 | v0 ^= first; |
198 | v3 ^= second; |
199 | SIPROUND; |
200 | SIPROUND; |
201 | v0 ^= second; |
202 | v3 ^= third; |
203 | SIPROUND; |
204 | SIPROUND; |
205 | v0 ^= third; |
206 | v3 ^= forth; |
207 | SIPROUND; |
208 | SIPROUND; |
209 | v0 ^= forth; |
210 | POSTAMBLE |
211 | } |
212 | EXPORT_SYMBOL(siphash_4u64); |
213 | |
214 | u64 siphash_1u32(const u32 first, const siphash_key_t *key) |
215 | { |
216 | PREAMBLE(4) |
217 | b |= first; |
218 | POSTAMBLE |
219 | } |
220 | EXPORT_SYMBOL(siphash_1u32); |
221 | |
222 | u64 siphash_3u32(const u32 first, const u32 second, const u32 third, |
223 | const siphash_key_t *key) |
224 | { |
225 | u64 combined = (u64)second << 32 | first; |
226 | PREAMBLE(12) |
227 | v3 ^= combined; |
228 | SIPROUND; |
229 | SIPROUND; |
230 | v0 ^= combined; |
231 | b |= third; |
232 | POSTAMBLE |
233 | } |
234 | EXPORT_SYMBOL(siphash_3u32); |
235 | |
236 | #if BITS_PER_LONG == 64 |
237 | /* Note that on 64-bit, we make HalfSipHash1-3 actually be SipHash1-3, for |
238 | * performance reasons. On 32-bit, below, we actually implement HalfSipHash1-3. |
239 | */ |
240 | |
241 | #define HSIPROUND SIPROUND |
242 | #define HPREAMBLE(len) PREAMBLE(len) |
243 | #define HPOSTAMBLE \ |
244 | v3 ^= b; \ |
245 | HSIPROUND; \ |
246 | v0 ^= b; \ |
247 | v2 ^= 0xff; \ |
248 | HSIPROUND; \ |
249 | HSIPROUND; \ |
250 | HSIPROUND; \ |
251 | return (v0 ^ v1) ^ (v2 ^ v3); |
252 | |
253 | u32 __hsiphash_aligned(const void *data, size_t len, const hsiphash_key_t *key) |
254 | { |
255 | const u8 *end = data + len - (len % sizeof(u64)); |
256 | const u8 left = len & (sizeof(u64) - 1); |
257 | u64 m; |
258 | HPREAMBLE(len) |
259 | for (; data != end; data += sizeof(u64)) { |
260 | m = le64_to_cpup(data); |
261 | v3 ^= m; |
262 | HSIPROUND; |
263 | v0 ^= m; |
264 | } |
265 | #if defined(CONFIG_DCACHE_WORD_ACCESS) && BITS_PER_LONG == 64 |
266 | if (left) |
267 | b |= le64_to_cpu((__force __le64)(load_unaligned_zeropad(data) & |
268 | bytemask_from_count(left))); |
269 | #else |
270 | switch (left) { |
271 | case 7: b |= ((u64)end[6]) << 48; |
272 | case 6: b |= ((u64)end[5]) << 40; |
273 | case 5: b |= ((u64)end[4]) << 32; |
274 | case 4: b |= le32_to_cpup(data); break; |
275 | case 3: b |= ((u64)end[2]) << 16; |
276 | case 2: b |= le16_to_cpup(data); break; |
277 | case 1: b |= end[0]; |
278 | } |
279 | #endif |
280 | HPOSTAMBLE |
281 | } |
282 | EXPORT_SYMBOL(__hsiphash_aligned); |
283 | |
284 | #ifndef CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS |
285 | u32 __hsiphash_unaligned(const void *data, size_t len, |
286 | const hsiphash_key_t *key) |
287 | { |
288 | const u8 *end = data + len - (len % sizeof(u64)); |
289 | const u8 left = len & (sizeof(u64) - 1); |
290 | u64 m; |
291 | HPREAMBLE(len) |
292 | for (; data != end; data += sizeof(u64)) { |
293 | m = get_unaligned_le64(data); |
294 | v3 ^= m; |
295 | HSIPROUND; |
296 | v0 ^= m; |
297 | } |
298 | #if defined(CONFIG_DCACHE_WORD_ACCESS) && BITS_PER_LONG == 64 |
299 | if (left) |
300 | b |= le64_to_cpu((__force __le64)(load_unaligned_zeropad(data) & |
301 | bytemask_from_count(left))); |
302 | #else |
303 | switch (left) { |
304 | case 7: b |= ((u64)end[6]) << 48; |
305 | case 6: b |= ((u64)end[5]) << 40; |
306 | case 5: b |= ((u64)end[4]) << 32; |
307 | case 4: b |= get_unaligned_le32(end); break; |
308 | case 3: b |= ((u64)end[2]) << 16; |
309 | case 2: b |= get_unaligned_le16(end); break; |
310 | case 1: b |= end[0]; |
311 | } |
312 | #endif |
313 | HPOSTAMBLE |
314 | } |
315 | EXPORT_SYMBOL(__hsiphash_unaligned); |
316 | #endif |
317 | |
318 | /** |
319 | * hsiphash_1u32 - compute 64-bit hsiphash PRF value of a u32 |
320 | * @first: first u32 |
321 | * @key: the hsiphash key |
322 | */ |
323 | u32 hsiphash_1u32(const u32 first, const hsiphash_key_t *key) |
324 | { |
325 | HPREAMBLE(4) |
326 | b |= first; |
327 | HPOSTAMBLE |
328 | } |
329 | EXPORT_SYMBOL(hsiphash_1u32); |
330 | |
331 | /** |
332 | * hsiphash_2u32 - compute 32-bit hsiphash PRF value of 2 u32 |
333 | * @first: first u32 |
334 | * @second: second u32 |
335 | * @key: the hsiphash key |
336 | */ |
337 | u32 hsiphash_2u32(const u32 first, const u32 second, const hsiphash_key_t *key) |
338 | { |
339 | u64 combined = (u64)second << 32 | first; |
340 | HPREAMBLE(8) |
341 | v3 ^= combined; |
342 | HSIPROUND; |
343 | v0 ^= combined; |
344 | HPOSTAMBLE |
345 | } |
346 | EXPORT_SYMBOL(hsiphash_2u32); |
347 | |
348 | /** |
349 | * hsiphash_3u32 - compute 32-bit hsiphash PRF value of 3 u32 |
350 | * @first: first u32 |
351 | * @second: second u32 |
352 | * @third: third u32 |
353 | * @key: the hsiphash key |
354 | */ |
355 | u32 hsiphash_3u32(const u32 first, const u32 second, const u32 third, |
356 | const hsiphash_key_t *key) |
357 | { |
358 | u64 combined = (u64)second << 32 | first; |
359 | HPREAMBLE(12) |
360 | v3 ^= combined; |
361 | HSIPROUND; |
362 | v0 ^= combined; |
363 | b |= third; |
364 | HPOSTAMBLE |
365 | } |
366 | EXPORT_SYMBOL(hsiphash_3u32); |
367 | |
368 | /** |
369 | * hsiphash_4u32 - compute 32-bit hsiphash PRF value of 4 u32 |
370 | * @first: first u32 |
371 | * @second: second u32 |
372 | * @third: third u32 |
373 | * @forth: forth u32 |
374 | * @key: the hsiphash key |
375 | */ |
376 | u32 hsiphash_4u32(const u32 first, const u32 second, const u32 third, |
377 | const u32 forth, const hsiphash_key_t *key) |
378 | { |
379 | u64 combined = (u64)second << 32 | first; |
380 | HPREAMBLE(16) |
381 | v3 ^= combined; |
382 | HSIPROUND; |
383 | v0 ^= combined; |
384 | combined = (u64)forth << 32 | third; |
385 | v3 ^= combined; |
386 | HSIPROUND; |
387 | v0 ^= combined; |
388 | HPOSTAMBLE |
389 | } |
390 | EXPORT_SYMBOL(hsiphash_4u32); |
391 | #else |
392 | #define HSIPROUND \ |
393 | do { \ |
394 | v0 += v1; v1 = rol32(v1, 5); v1 ^= v0; v0 = rol32(v0, 16); \ |
395 | v2 += v3; v3 = rol32(v3, 8); v3 ^= v2; \ |
396 | v0 += v3; v3 = rol32(v3, 7); v3 ^= v0; \ |
397 | v2 += v1; v1 = rol32(v1, 13); v1 ^= v2; v2 = rol32(v2, 16); \ |
398 | } while (0) |
399 | |
400 | #define HPREAMBLE(len) \ |
401 | u32 v0 = 0; \ |
402 | u32 v1 = 0; \ |
403 | u32 v2 = 0x6c796765U; \ |
404 | u32 v3 = 0x74656462U; \ |
405 | u32 b = ((u32)(len)) << 24; \ |
406 | v3 ^= key->key[1]; \ |
407 | v2 ^= key->key[0]; \ |
408 | v1 ^= key->key[1]; \ |
409 | v0 ^= key->key[0]; |
410 | |
411 | #define HPOSTAMBLE \ |
412 | v3 ^= b; \ |
413 | HSIPROUND; \ |
414 | v0 ^= b; \ |
415 | v2 ^= 0xff; \ |
416 | HSIPROUND; \ |
417 | HSIPROUND; \ |
418 | HSIPROUND; \ |
419 | return v1 ^ v3; |
420 | |
421 | u32 __hsiphash_aligned(const void *data, size_t len, const hsiphash_key_t *key) |
422 | { |
423 | const u8 *end = data + len - (len % sizeof(u32)); |
424 | const u8 left = len & (sizeof(u32) - 1); |
425 | u32 m; |
426 | HPREAMBLE(len) |
427 | for (; data != end; data += sizeof(u32)) { |
428 | m = le32_to_cpup(data); |
429 | v3 ^= m; |
430 | HSIPROUND; |
431 | v0 ^= m; |
432 | } |
433 | switch (left) { |
434 | case 3: b |= ((u32)end[2]) << 16; |
435 | case 2: b |= le16_to_cpup(data); break; |
436 | case 1: b |= end[0]; |
437 | } |
438 | HPOSTAMBLE |
439 | } |
440 | EXPORT_SYMBOL(__hsiphash_aligned); |
441 | |
442 | #ifndef CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS |
443 | u32 __hsiphash_unaligned(const void *data, size_t len, |
444 | const hsiphash_key_t *key) |
445 | { |
446 | const u8 *end = data + len - (len % sizeof(u32)); |
447 | const u8 left = len & (sizeof(u32) - 1); |
448 | u32 m; |
449 | HPREAMBLE(len) |
450 | for (; data != end; data += sizeof(u32)) { |
451 | m = get_unaligned_le32(data); |
452 | v3 ^= m; |
453 | HSIPROUND; |
454 | v0 ^= m; |
455 | } |
456 | switch (left) { |
457 | case 3: b |= ((u32)end[2]) << 16; |
458 | case 2: b |= get_unaligned_le16(end); break; |
459 | case 1: b |= end[0]; |
460 | } |
461 | HPOSTAMBLE |
462 | } |
463 | EXPORT_SYMBOL(__hsiphash_unaligned); |
464 | #endif |
465 | |
466 | /** |
467 | * hsiphash_1u32 - compute 32-bit hsiphash PRF value of a u32 |
468 | * @first: first u32 |
469 | * @key: the hsiphash key |
470 | */ |
471 | u32 hsiphash_1u32(const u32 first, const hsiphash_key_t *key) |
472 | { |
473 | HPREAMBLE(4) |
474 | v3 ^= first; |
475 | HSIPROUND; |
476 | v0 ^= first; |
477 | HPOSTAMBLE |
478 | } |
479 | EXPORT_SYMBOL(hsiphash_1u32); |
480 | |
481 | /** |
482 | * hsiphash_2u32 - compute 32-bit hsiphash PRF value of 2 u32 |
483 | * @first: first u32 |
484 | * @second: second u32 |
485 | * @key: the hsiphash key |
486 | */ |
487 | u32 hsiphash_2u32(const u32 first, const u32 second, const hsiphash_key_t *key) |
488 | { |
489 | HPREAMBLE(8) |
490 | v3 ^= first; |
491 | HSIPROUND; |
492 | v0 ^= first; |
493 | v3 ^= second; |
494 | HSIPROUND; |
495 | v0 ^= second; |
496 | HPOSTAMBLE |
497 | } |
498 | EXPORT_SYMBOL(hsiphash_2u32); |
499 | |
500 | /** |
501 | * hsiphash_3u32 - compute 32-bit hsiphash PRF value of 3 u32 |
502 | * @first: first u32 |
503 | * @second: second u32 |
504 | * @third: third u32 |
505 | * @key: the hsiphash key |
506 | */ |
507 | u32 hsiphash_3u32(const u32 first, const u32 second, const u32 third, |
508 | const hsiphash_key_t *key) |
509 | { |
510 | HPREAMBLE(12) |
511 | v3 ^= first; |
512 | HSIPROUND; |
513 | v0 ^= first; |
514 | v3 ^= second; |
515 | HSIPROUND; |
516 | v0 ^= second; |
517 | v3 ^= third; |
518 | HSIPROUND; |
519 | v0 ^= third; |
520 | HPOSTAMBLE |
521 | } |
522 | EXPORT_SYMBOL(hsiphash_3u32); |
523 | |
524 | /** |
525 | * hsiphash_4u32 - compute 32-bit hsiphash PRF value of 4 u32 |
526 | * @first: first u32 |
527 | * @second: second u32 |
528 | * @third: third u32 |
529 | * @forth: forth u32 |
530 | * @key: the hsiphash key |
531 | */ |
532 | u32 hsiphash_4u32(const u32 first, const u32 second, const u32 third, |
533 | const u32 forth, const hsiphash_key_t *key) |
534 | { |
535 | HPREAMBLE(16) |
536 | v3 ^= first; |
537 | HSIPROUND; |
538 | v0 ^= first; |
539 | v3 ^= second; |
540 | HSIPROUND; |
541 | v0 ^= second; |
542 | v3 ^= third; |
543 | HSIPROUND; |
544 | v0 ^= third; |
545 | v3 ^= forth; |
546 | HSIPROUND; |
547 | v0 ^= forth; |
548 | HPOSTAMBLE |
549 | } |
550 | EXPORT_SYMBOL(hsiphash_4u32); |
551 | #endif |
552 |