lib/siphash.c

   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; /* fall through */
  72         case 6: b |= ((u64)end[5]) << 40; /* fall through */
  73         case 5: b |= ((u64)end[4]) << 32; /* fall through */
  74         case 4: b |= le32_to_cpup(data); break;
  75         case 3: b |= ((u64)end[2]) << 16; /* fall through */
  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; /* 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 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; /* 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 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; /* fall through */
 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; /* 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 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