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