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; fallthrough; 72 case 6: b |= ((u64)end[5]) << 40; fallthrough; 73 case 5: b |= ((u64)end[4]) << 32; fallthrough; 74 case 4: b |= le32_to_cpup(data); break; 75 case 3: b |= ((u64)end[2]) << 16; fallthrough; 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; fallthrough; 105 case 6: b |= ((u64)end[5]) << 40; fallthrough; 106 case 5: b |= ((u64)end[4]) << 32; fallthrough; 107 case 4: b |= get_unaligned_le32(end); break; 108 case 3: b |= ((u64)end[2]) << 16; fallthrough; 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; fallthrough; 272 case 6: b |= ((u64)end[5]) << 40; fallthrough; 273 case 5: b |= ((u64)end[4]) << 32; fallthrough; 274 case 4: b |= le32_to_cpup(data); break; 275 case 3: b |= ((u64)end[2]) << 16; fallthrough; 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; fallthrough; 305 case 6: b |= ((u64)end[5]) << 40; fallthrough; 306 case 5: b |= ((u64)end[4]) << 32; fallthrough; 307 case 4: b |= get_unaligned_le32(end); break; 308 case 3: b |= ((u64)end[2]) << 16; fallthrough; 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; fallthrough; 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; fallthrough; 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