Branch data Line data Source code
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 : 3 : u64 __siphash_aligned(const void *data, size_t len, const siphash_key_t *key) 53 : : { 54 : 3 : const u8 *end = data + len - (len % sizeof(u64)); 55 : 3 : const u8 left = len & (sizeof(u64) - 1); 56 : : u64 m; 57 : 3 : PREAMBLE(len) 58 : 3 : for (; data != end; data += sizeof(u64)) { 59 : : m = le64_to_cpup(data); 60 : 3 : v3 ^= m; 61 : 3 : SIPROUND; 62 : 3 : SIPROUND; 63 : 3 : 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 : 3 : switch (left) { 71 : 0 : case 7: b |= ((u64)end[6]) << 48; /* fall through */ 72 : 0 : case 6: b |= ((u64)end[5]) << 40; /* fall through */ 73 : 0 : case 5: b |= ((u64)end[4]) << 32; /* fall through */ 74 : 0 : case 4: b |= le32_to_cpup(data); break; 75 : 0 : case 3: b |= ((u64)end[2]) << 16; /* fall through */ 76 : 0 : case 2: b |= le16_to_cpup(data); break; 77 : 0 : case 1: b |= end[0]; 78 : : } 79 : : #endif 80 : 3 : 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; /* fall through */ 105 : : case 6: b |= ((u64)end[5]) << 40; /* fall through */ 106 : : case 5: b |= ((u64)end[4]) << 32; /* fall through */ 107 : : case 4: b |= get_unaligned_le32(end); break; 108 : : case 3: b |= ((u64)end[2]) << 16; /* fall through */ 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 : 1 : u64 siphash_1u64(const u64 first, const siphash_key_t *key) 124 : : { 125 : 1 : PREAMBLE(8) 126 : 1 : v3 ^= first; 127 : 1 : SIPROUND; 128 : 1 : SIPROUND; 129 : 1 : v0 ^= first; 130 : 1 : 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 : 0 : u64 siphash_2u64(const u64 first, const u64 second, const siphash_key_t *key) 141 : : { 142 : 0 : PREAMBLE(16) 143 : 0 : v3 ^= first; 144 : 0 : SIPROUND; 145 : 0 : SIPROUND; 146 : 0 : v0 ^= first; 147 : 0 : v3 ^= second; 148 : 0 : SIPROUND; 149 : 0 : SIPROUND; 150 : 0 : v0 ^= second; 151 : 0 : 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 : 0 : u64 siphash_3u64(const u64 first, const u64 second, const u64 third, 163 : : const siphash_key_t *key) 164 : : { 165 : 0 : PREAMBLE(24) 166 : 0 : v3 ^= first; 167 : 0 : SIPROUND; 168 : 0 : SIPROUND; 169 : 0 : v0 ^= first; 170 : 0 : v3 ^= second; 171 : 0 : SIPROUND; 172 : 0 : SIPROUND; 173 : 0 : v0 ^= second; 174 : 0 : v3 ^= third; 175 : 0 : SIPROUND; 176 : 0 : SIPROUND; 177 : 0 : v0 ^= third; 178 : 0 : 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 : 0 : u64 siphash_4u64(const u64 first, const u64 second, const u64 third, 191 : : const u64 forth, const siphash_key_t *key) 192 : : { 193 : 0 : PREAMBLE(32) 194 : 0 : v3 ^= first; 195 : 0 : SIPROUND; 196 : 0 : SIPROUND; 197 : 0 : v0 ^= first; 198 : 0 : v3 ^= second; 199 : 0 : SIPROUND; 200 : 0 : SIPROUND; 201 : 0 : v0 ^= second; 202 : 0 : v3 ^= third; 203 : 0 : SIPROUND; 204 : 0 : SIPROUND; 205 : 0 : v0 ^= third; 206 : 0 : v3 ^= forth; 207 : 0 : SIPROUND; 208 : 0 : SIPROUND; 209 : 0 : v0 ^= forth; 210 : 0 : POSTAMBLE 211 : : } 212 : : EXPORT_SYMBOL(siphash_4u64); 213 : : 214 : 0 : u64 siphash_1u32(const u32 first, const siphash_key_t *key) 215 : : { 216 : 0 : PREAMBLE(4) 217 : 0 : b |= first; 218 : 0 : POSTAMBLE 219 : : } 220 : : EXPORT_SYMBOL(siphash_1u32); 221 : : 222 : 3 : u64 siphash_3u32(const u32 first, const u32 second, const u32 third, 223 : : const siphash_key_t *key) 224 : : { 225 : 3 : u64 combined = (u64)second << 32 | first; 226 : 3 : PREAMBLE(12) 227 : 3 : v3 ^= combined; 228 : 3 : SIPROUND; 229 : 3 : SIPROUND; 230 : 3 : v0 ^= combined; 231 : 3 : b |= third; 232 : 3 : 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; /* fall through */ 272 : : case 6: b |= ((u64)end[5]) << 40; /* fall through */ 273 : : case 5: b |= ((u64)end[4]) << 32; /* fall through */ 274 : : case 4: b |= le32_to_cpup(data); break; 275 : : case 3: b |= ((u64)end[2]) << 16; /* fall through */ 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; /* fall through */ 305 : : case 6: b |= ((u64)end[5]) << 40; /* fall through */ 306 : : case 5: b |= ((u64)end[4]) << 32; /* fall through */ 307 : : case 4: b |= get_unaligned_le32(end); break; 308 : : case 3: b |= ((u64)end[2]) << 16; /* fall through */ 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 : 0 : u32 __hsiphash_aligned(const void *data, size_t len, const hsiphash_key_t *key) 422 : : { 423 : 0 : const u8 *end = data + len - (len % sizeof(u32)); 424 : 0 : const u8 left = len & (sizeof(u32) - 1); 425 : : u32 m; 426 : 0 : HPREAMBLE(len) 427 : 0 : for (; data != end; data += sizeof(u32)) { 428 : : m = le32_to_cpup(data); 429 : 0 : v3 ^= m; 430 : 0 : HSIPROUND; 431 : 0 : v0 ^= m; 432 : : } 433 : 0 : switch (left) { 434 : 0 : case 3: b |= ((u32)end[2]) << 16; /* fall through */ 435 : 0 : case 2: b |= le16_to_cpup(data); break; 436 : 0 : case 1: b |= end[0]; 437 : : } 438 : 0 : 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; /* fall through */ 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 : 0 : u32 hsiphash_1u32(const u32 first, const hsiphash_key_t *key) 472 : : { 473 : 0 : HPREAMBLE(4) 474 : 0 : v3 ^= first; 475 : 0 : HSIPROUND; 476 : 0 : v0 ^= first; 477 : 0 : 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 : 0 : u32 hsiphash_2u32(const u32 first, const u32 second, const hsiphash_key_t *key) 488 : : { 489 : 0 : HPREAMBLE(8) 490 : 0 : v3 ^= first; 491 : 0 : HSIPROUND; 492 : 0 : v0 ^= first; 493 : 0 : v3 ^= second; 494 : 0 : HSIPROUND; 495 : 0 : v0 ^= second; 496 : 0 : 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 : 0 : u32 hsiphash_3u32(const u32 first, const u32 second, const u32 third, 508 : : const hsiphash_key_t *key) 509 : : { 510 : 0 : HPREAMBLE(12) 511 : 0 : v3 ^= first; 512 : 0 : HSIPROUND; 513 : 0 : v0 ^= first; 514 : 0 : v3 ^= second; 515 : 0 : HSIPROUND; 516 : 0 : v0 ^= second; 517 : 0 : v3 ^= third; 518 : 0 : HSIPROUND; 519 : 0 : v0 ^= third; 520 : 0 : 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 : 0 : u32 hsiphash_4u32(const u32 first, const u32 second, const u32 third, 533 : : const u32 forth, const hsiphash_key_t *key) 534 : : { 535 : 0 : HPREAMBLE(16) 536 : 0 : v3 ^= first; 537 : 0 : HSIPROUND; 538 : 0 : v0 ^= first; 539 : 0 : v3 ^= second; 540 : 0 : HSIPROUND; 541 : 0 : v0 ^= second; 542 : 0 : v3 ^= third; 543 : 0 : HSIPROUND; 544 : 0 : v0 ^= third; 545 : 0 : v3 ^= forth; 546 : 0 : HSIPROUND; 547 : 0 : v0 ^= forth; 548 : 0 : HPOSTAMBLE 549 : : } 550 : : EXPORT_SYMBOL(hsiphash_4u32); 551 : : #endif