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 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 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 */ 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 #ifndef CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS 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 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 */ 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 #ifndef CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS 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 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 */ 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