LXR linux/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
  52u64 __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}
  82EXPORT_SYMBOL(__siphash_aligned);
  83
  84#ifndef CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS
  85u64 __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}
 115EXPORT_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 */
 123u64 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}
 132EXPORT_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 */
 140u64 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}
 153EXPORT_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 */
 162u64 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}
 180EXPORT_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 */
 190u64 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}
 212EXPORT_SYMBOL(siphash_4u64);
 213
 214u64 siphash_1u32(const u32 first, const siphash_key_t *key)
 215{
 216        PREAMBLE(4)
 217        b |= first;
 218        POSTAMBLE
 219}
 220EXPORT_SYMBOL(siphash_1u32);
 221
 222u64 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}
 234EXPORT_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
 253u32 __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}
 282EXPORT_SYMBOL(__hsiphash_aligned);
 283
 284#ifndef CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS
 285u32 __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}
 315EXPORT_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 */
 323u32 hsiphash_1u32(const u32 first, const hsiphash_key_t *key)
 324{
 325        HPREAMBLE(4)
 326        b |= first;
 327        HPOSTAMBLE
 328}
 329EXPORT_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 */
 337u32 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}
 346EXPORT_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 */
 355u32 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}
 366EXPORT_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 */
 376u32 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}
 390EXPORT_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
 421u32 __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}
 440EXPORT_SYMBOL(__hsiphash_aligned);
 441
 442#ifndef CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS
 443u32 __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}
 463EXPORT_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 */
 471u32 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}
 479EXPORT_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 */
 487u32 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}
 498EXPORT_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 */
 507u32 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}
 522EXPORT_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 */
 532u32 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}
 550EXPORT_SYMBOL(hsiphash_4u32);
 551#endif
 552