• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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; fallthrough;
67 	case 6: b |= ((u64)end[5]) << 40; fallthrough;
68 	case 5: b |= ((u64)end[4]) << 32; fallthrough;
69 	case 4: b |= le32_to_cpup(data); break;
70 	case 3: b |= ((u64)end[2]) << 16; fallthrough;
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; fallthrough;
100 	case 6: b |= ((u64)end[5]) << 40; fallthrough;
101 	case 5: b |= ((u64)end[4]) << 32; fallthrough;
102 	case 4: b |= get_unaligned_le32(end); break;
103 	case 3: b |= ((u64)end[2]) << 16; fallthrough;
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; fallthrough;
267 	case 6: b |= ((u64)end[5]) << 40; fallthrough;
268 	case 5: b |= ((u64)end[4]) << 32; fallthrough;
269 	case 4: b |= le32_to_cpup(data); break;
270 	case 3: b |= ((u64)end[2]) << 16; fallthrough;
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; fallthrough;
300 	case 6: b |= ((u64)end[5]) << 40; fallthrough;
301 	case 5: b |= ((u64)end[4]) << 32; fallthrough;
302 	case 4: b |= get_unaligned_le32(end); break;
303 	case 3: b |= ((u64)end[2]) << 16; fallthrough;
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; fallthrough;
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; fallthrough;
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