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 #ifndef CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS
__siphash_aligned(const void * data,size_t len,const siphash_key_t * key)53 u64 __siphash_aligned(const void *data, size_t len, const siphash_key_t *key)
54 {
55 	const u8 *end = data + len - (len % sizeof(u64));
56 	const u8 left = len & (sizeof(u64) - 1);
57 	u64 m;
58 	PREAMBLE(len)
59 	for (; data != end; data += sizeof(u64)) {
60 		m = le64_to_cpup(data);
61 		v3 ^= m;
62 		SIPROUND;
63 		SIPROUND;
64 		v0 ^= m;
65 	}
66 #if defined(CONFIG_DCACHE_WORD_ACCESS) && BITS_PER_LONG == 64
67 	if (left)
68 		b |= le64_to_cpu((__force __le64)(load_unaligned_zeropad(data) &
69 						  bytemask_from_count(left)));
70 #else
71 	switch (left) {
72 	case 7: b |= ((u64)end[6]) << 48; fallthrough;
73 	case 6: b |= ((u64)end[5]) << 40; fallthrough;
74 	case 5: b |= ((u64)end[4]) << 32; fallthrough;
75 	case 4: b |= le32_to_cpup(data); break;
76 	case 3: b |= ((u64)end[2]) << 16; fallthrough;
77 	case 2: b |= le16_to_cpup(data); break;
78 	case 1: b |= end[0];
79 	}
80 #endif
81 	POSTAMBLE
82 }
83 EXPORT_SYMBOL(__siphash_aligned);
84 #endif
85 
__siphash_unaligned(const void * data,size_t len,const siphash_key_t * key)86 u64 __siphash_unaligned(const void *data, size_t len, const siphash_key_t *key)
87 {
88 	const u8 *end = data + len - (len % sizeof(u64));
89 	const u8 left = len & (sizeof(u64) - 1);
90 	u64 m;
91 	PREAMBLE(len)
92 	for (; data != end; data += sizeof(u64)) {
93 		m = get_unaligned_le64(data);
94 		v3 ^= m;
95 		SIPROUND;
96 		SIPROUND;
97 		v0 ^= m;
98 	}
99 #if defined(CONFIG_DCACHE_WORD_ACCESS) && BITS_PER_LONG == 64
100 	if (left)
101 		b |= le64_to_cpu((__force __le64)(load_unaligned_zeropad(data) &
102 						  bytemask_from_count(left)));
103 #else
104 	switch (left) {
105 	case 7: b |= ((u64)end[6]) << 48; fallthrough;
106 	case 6: b |= ((u64)end[5]) << 40; fallthrough;
107 	case 5: b |= ((u64)end[4]) << 32; fallthrough;
108 	case 4: b |= get_unaligned_le32(end); break;
109 	case 3: b |= ((u64)end[2]) << 16; fallthrough;
110 	case 2: b |= get_unaligned_le16(end); break;
111 	case 1: b |= end[0];
112 	}
113 #endif
114 	POSTAMBLE
115 }
116 EXPORT_SYMBOL(__siphash_unaligned);
117 
118 /**
119  * siphash_1u64 - compute 64-bit siphash PRF value of a u64
120  * @first: first u64
121  * @key: the siphash key
122  */
siphash_1u64(const u64 first,const siphash_key_t * key)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  */
siphash_2u64(const u64 first,const u64 second,const siphash_key_t * key)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  */
siphash_3u64(const u64 first,const u64 second,const u64 third,const siphash_key_t * key)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  */
siphash_4u64(const u64 first,const u64 second,const u64 third,const u64 forth,const siphash_key_t * key)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 
siphash_1u32(const u32 first,const siphash_key_t * key)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 
siphash_3u32(const u32 first,const u32 second,const u32 third,const siphash_key_t * key)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 #ifndef CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS
__hsiphash_aligned(const void * data,size_t len,const hsiphash_key_t * key)254 u32 __hsiphash_aligned(const void *data, size_t len, const hsiphash_key_t *key)
255 {
256 	const u8 *end = data + len - (len % sizeof(u64));
257 	const u8 left = len & (sizeof(u64) - 1);
258 	u64 m;
259 	HPREAMBLE(len)
260 	for (; data != end; data += sizeof(u64)) {
261 		m = le64_to_cpup(data);
262 		v3 ^= m;
263 		HSIPROUND;
264 		v0 ^= m;
265 	}
266 #if defined(CONFIG_DCACHE_WORD_ACCESS) && BITS_PER_LONG == 64
267 	if (left)
268 		b |= le64_to_cpu((__force __le64)(load_unaligned_zeropad(data) &
269 						  bytemask_from_count(left)));
270 #else
271 	switch (left) {
272 	case 7: b |= ((u64)end[6]) << 48; fallthrough;
273 	case 6: b |= ((u64)end[5]) << 40; fallthrough;
274 	case 5: b |= ((u64)end[4]) << 32; fallthrough;
275 	case 4: b |= le32_to_cpup(data); break;
276 	case 3: b |= ((u64)end[2]) << 16; fallthrough;
277 	case 2: b |= le16_to_cpup(data); break;
278 	case 1: b |= end[0];
279 	}
280 #endif
281 	HPOSTAMBLE
282 }
283 EXPORT_SYMBOL(__hsiphash_aligned);
284 #endif
285 
__hsiphash_unaligned(const void * data,size_t len,const hsiphash_key_t * key)286 u32 __hsiphash_unaligned(const void *data, size_t len,
287 			 const hsiphash_key_t *key)
288 {
289 	const u8 *end = data + len - (len % sizeof(u64));
290 	const u8 left = len & (sizeof(u64) - 1);
291 	u64 m;
292 	HPREAMBLE(len)
293 	for (; data != end; data += sizeof(u64)) {
294 		m = get_unaligned_le64(data);
295 		v3 ^= m;
296 		HSIPROUND;
297 		v0 ^= m;
298 	}
299 #if defined(CONFIG_DCACHE_WORD_ACCESS) && BITS_PER_LONG == 64
300 	if (left)
301 		b |= le64_to_cpu((__force __le64)(load_unaligned_zeropad(data) &
302 						  bytemask_from_count(left)));
303 #else
304 	switch (left) {
305 	case 7: b |= ((u64)end[6]) << 48; fallthrough;
306 	case 6: b |= ((u64)end[5]) << 40; fallthrough;
307 	case 5: b |= ((u64)end[4]) << 32; fallthrough;
308 	case 4: b |= get_unaligned_le32(end); break;
309 	case 3: b |= ((u64)end[2]) << 16; fallthrough;
310 	case 2: b |= get_unaligned_le16(end); break;
311 	case 1: b |= end[0];
312 	}
313 #endif
314 	HPOSTAMBLE
315 }
316 EXPORT_SYMBOL(__hsiphash_unaligned);
317 
318 /**
319  * hsiphash_1u32 - compute 64-bit hsiphash PRF value of a u32
320  * @first: first u32
321  * @key: the hsiphash key
322  */
hsiphash_1u32(const u32 first,const hsiphash_key_t * key)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  */
hsiphash_2u32(const u32 first,const u32 second,const hsiphash_key_t * key)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  */
hsiphash_3u32(const u32 first,const u32 second,const u32 third,const hsiphash_key_t * key)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  */
hsiphash_4u32(const u32 first,const u32 second,const u32 third,const u32 forth,const hsiphash_key_t * key)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 #ifndef CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS
__hsiphash_aligned(const void * data,size_t len,const hsiphash_key_t * key)422 u32 __hsiphash_aligned(const void *data, size_t len, const hsiphash_key_t *key)
423 {
424 	const u8 *end = data + len - (len % sizeof(u32));
425 	const u8 left = len & (sizeof(u32) - 1);
426 	u32 m;
427 	HPREAMBLE(len)
428 	for (; data != end; data += sizeof(u32)) {
429 		m = le32_to_cpup(data);
430 		v3 ^= m;
431 		HSIPROUND;
432 		v0 ^= m;
433 	}
434 	switch (left) {
435 	case 3: b |= ((u32)end[2]) << 16; fallthrough;
436 	case 2: b |= le16_to_cpup(data); break;
437 	case 1: b |= end[0];
438 	}
439 	HPOSTAMBLE
440 }
441 EXPORT_SYMBOL(__hsiphash_aligned);
442 #endif
443 
__hsiphash_unaligned(const void * data,size_t len,const hsiphash_key_t * key)444 u32 __hsiphash_unaligned(const void *data, size_t len,
445 			 const hsiphash_key_t *key)
446 {
447 	const u8 *end = data + len - (len % sizeof(u32));
448 	const u8 left = len & (sizeof(u32) - 1);
449 	u32 m;
450 	HPREAMBLE(len)
451 	for (; data != end; data += sizeof(u32)) {
452 		m = get_unaligned_le32(data);
453 		v3 ^= m;
454 		HSIPROUND;
455 		v0 ^= m;
456 	}
457 	switch (left) {
458 	case 3: b |= ((u32)end[2]) << 16; fallthrough;
459 	case 2: b |= get_unaligned_le16(end); break;
460 	case 1: b |= end[0];
461 	}
462 	HPOSTAMBLE
463 }
464 EXPORT_SYMBOL(__hsiphash_unaligned);
465 
466 /**
467  * hsiphash_1u32 - compute 32-bit hsiphash PRF value of a u32
468  * @first: first u32
469  * @key: the hsiphash key
470  */
hsiphash_1u32(const u32 first,const hsiphash_key_t * key)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  */
hsiphash_2u32(const u32 first,const u32 second,const hsiphash_key_t * key)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  */
hsiphash_3u32(const u32 first,const u32 second,const u32 third,const hsiphash_key_t * key)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  */
hsiphash_4u32(const u32 first,const u32 second,const u32 third,const u32 forth,const hsiphash_key_t * key)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