lib/xxhash.c

   1 // SPDX-License-Identifier: (GPL-2.0 or BSD-2-Clause)
   2 /*
   3  * xxHash - Extremely Fast Hash algorithm
   4  * Copyright (C) 2012-2016, Yann Collet.
   5  *
   6  * You can contact the author at:
   7  * - xxHash homepage: http://cyan4973.github.io/xxHash/
   8  * - xxHash source repository: https://github.com/Cyan4973/xxHash
   9  */
  10
  11 #include <asm/unaligned.h>
  12 #include <linux/errno.h>
  13 #include <linux/compiler.h>
  14 #include <linux/kernel.h>
  15 #include <linux/compat.h>
  16 #include <linux/string.h>
  17 #include <linux/xxhash.h>
  18
  19 /*-*************************************
  20  * Macros
  21  **************************************/
  22 #define xxh_rotl32(x, r) ((x << r) | (x >> (32 - r)))
  23 #define xxh_rotl64(x, r) ((x << r) | (x >> (64 - r)))
  24
  25 #ifdef __LITTLE_ENDIAN
  26 # define XXH_CPU_LITTLE_ENDIAN 1
  27 #else
  28 # define XXH_CPU_LITTLE_ENDIAN 0
  29 #endif
  30
  31 /*-*************************************
  32  * Constants
  33  **************************************/
  34 static const uint32_t PRIME32_1 = 2654435761U;
  35 static const uint32_t PRIME32_2 = 2246822519U;
  36 static const uint32_t PRIME32_3 = 3266489917U;
  37 static const uint32_t PRIME32_4 =  668265263U;
  38 static const uint32_t PRIME32_5 =  374761393U;
  39
  40 static const uint64_t PRIME64_1 = 11400714785074694791ULL;
  41 static const uint64_t PRIME64_2 = 14029467366897019727ULL;
  42 static const uint64_t PRIME64_3 =  1609587929392839161ULL;
  43 static const uint64_t PRIME64_4 =  9650029242287828579ULL;
  44 static const uint64_t PRIME64_5 =  2870177450012600261ULL;
  45
  46 /*-**************************
  47  *  Utils
  48  ***************************/
  49 void xxh32_copy_state(struct xxh32_state *dst, const struct xxh32_state *src)
  50 {
  51         memcpy(dst, src, sizeof(*dst));
  52 }
  53 EXPORT_SYMBOL(xxh32_copy_state);
  54
  55 void xxh64_copy_state(struct xxh64_state *dst, const struct xxh64_state *src)
  56 {
  57         memcpy(dst, src, sizeof(*dst));
  58 }
  59 EXPORT_SYMBOL(xxh64_copy_state);
  60
  61 /*-***************************
  62  * Simple Hash Functions
  63  ****************************/
  64 static uint32_t xxh32_round(uint32_t seed, const uint32_t input)
  65 {
  66         seed += input * PRIME32_2;
  67         seed = xxh_rotl32(seed, 13);
  68         seed *= PRIME32_1;
  69         return seed;
  70 }
  71
  72 uint32_t xxh32(const void *input, const size_t len, const uint32_t seed)
  73 {
  74         const uint8_t *p = (const uint8_t *)input;
  75         const uint8_t *b_end = p + len;
  76         uint32_t h32;
  77
  78         if (len >= 16) {
  79                 const uint8_t *const limit = b_end - 16;
  80                 uint32_t v1 = seed + PRIME32_1 + PRIME32_2;
  81                 uint32_t v2 = seed + PRIME32_2;
  82                 uint32_t v3 = seed + 0;
  83                 uint32_t v4 = seed - PRIME32_1;
  84
  85                 do {
  86                         v1 = xxh32_round(v1, get_unaligned_le32(p));
  87                         p += 4;
  88                         v2 = xxh32_round(v2, get_unaligned_le32(p));
  89                         p += 4;
  90                         v3 = xxh32_round(v3, get_unaligned_le32(p));
  91                         p += 4;
  92                         v4 = xxh32_round(v4, get_unaligned_le32(p));
  93                         p += 4;
  94                 } while (p <= limit);
  95
  96                 h32 = xxh_rotl32(v1, 1) + xxh_rotl32(v2, 7) +
  97                         xxh_rotl32(v3, 12) + xxh_rotl32(v4, 18);
  98         } else {
  99                 h32 = seed + PRIME32_5;
 100         }
 101
 102         h32 += (uint32_t)len;
 103
 104         while (p + 4 <= b_end) {
 105                 h32 += get_unaligned_le32(p) * PRIME32_3;
 106                 h32 = xxh_rotl32(h32, 17) * PRIME32_4;
 107                 p += 4;
 108         }
 109
 110         while (p < b_end) {
 111                 h32 += (*p) * PRIME32_5;
 112                 h32 = xxh_rotl32(h32, 11) * PRIME32_1;
 113                 p++;
 114         }
 115
 116         h32 ^= h32 >> 15;
 117         h32 *= PRIME32_2;
 118         h32 ^= h32 >> 13;
 119         h32 *= PRIME32_3;
 120         h32 ^= h32 >> 16;
 121
 122         return h32;
 123 }
 124 EXPORT_SYMBOL(xxh32);
 125
 126 static uint64_t xxh64_round(uint64_t acc, const uint64_t input)
 127 {
 128         acc += input * PRIME64_2;
 129         acc = xxh_rotl64(acc, 31);
 130         acc *= PRIME64_1;
 131         return acc;
 132 }
 133
 134 static uint64_t xxh64_merge_round(uint64_t acc, uint64_t val)
 135 {
 136         val = xxh64_round(0, val);
 137         acc ^= val;
 138         acc = acc * PRIME64_1 + PRIME64_4;
 139         return acc;
 140 }
 141
 142 uint64_t xxh64(const void *input, const size_t len, const uint64_t seed)
 143 {
 144         const uint8_t *p = (const uint8_t *)input;
 145         const uint8_t *const b_end = p + len;
 146         uint64_t h64;
 147
 148         if (len >= 32) {
 149                 const uint8_t *const limit = b_end - 32;
 150                 uint64_t v1 = seed + PRIME64_1 + PRIME64_2;
 151                 uint64_t v2 = seed + PRIME64_2;
 152                 uint64_t v3 = seed + 0;
 153                 uint64_t v4 = seed - PRIME64_1;
 154
 155                 do {
 156                         v1 = xxh64_round(v1, get_unaligned_le64(p));
 157                         p += 8;
 158                         v2 = xxh64_round(v2, get_unaligned_le64(p));
 159                         p += 8;
 160                         v3 = xxh64_round(v3, get_unaligned_le64(p));
 161                         p += 8;
 162                         v4 = xxh64_round(v4, get_unaligned_le64(p));
 163                         p += 8;
 164                 } while (p <= limit);
 165
 166                 h64 = xxh_rotl64(v1, 1) + xxh_rotl64(v2, 7) +
 167                         xxh_rotl64(v3, 12) + xxh_rotl64(v4, 18);
 168                 h64 = xxh64_merge_round(h64, v1);
 169                 h64 = xxh64_merge_round(h64, v2);
 170                 h64 = xxh64_merge_round(h64, v3);
 171                 h64 = xxh64_merge_round(h64, v4);
 172
 173         } else {
 174                 h64  = seed + PRIME64_5;
 175         }
 176
 177         h64 += (uint64_t)len;
 178
 179         while (p + 8 <= b_end) {
 180                 const uint64_t k1 = xxh64_round(0, get_unaligned_le64(p));
 181
 182                 h64 ^= k1;
 183                 h64 = xxh_rotl64(h64, 27) * PRIME64_1 + PRIME64_4;
 184                 p += 8;
 185         }
 186
 187         if (p + 4 <= b_end) {
 188                 h64 ^= (uint64_t)(get_unaligned_le32(p)) * PRIME64_1;
 189                 h64 = xxh_rotl64(h64, 23) * PRIME64_2 + PRIME64_3;
 190                 p += 4;
 191         }
 192
 193         while (p < b_end) {
 194                 h64 ^= (*p) * PRIME64_5;
 195                 h64 = xxh_rotl64(h64, 11) * PRIME64_1;
 196                 p++;
 197         }
 198
 199         h64 ^= h64 >> 33;
 200         h64 *= PRIME64_2;
 201         h64 ^= h64 >> 29;
 202         h64 *= PRIME64_3;
 203         h64 ^= h64 >> 32;
 204
 205         return h64;
 206 }
 207 EXPORT_SYMBOL(xxh64);
 208
 209 /*-**************************************************
 210  * Advanced Hash Functions
 211  ***************************************************/
 212 void xxh32_reset(struct xxh32_state *statePtr, const uint32_t seed)
 213 {
 214         /* use a local state for memcpy() to avoid strict-aliasing warnings */
 215         struct xxh32_state state;
 216
 217         memset(&state, 0, sizeof(state));
 218         state.v1 = seed + PRIME32_1 + PRIME32_2;
 219         state.v2 = seed + PRIME32_2;
 220         state.v3 = seed + 0;
 221         state.v4 = seed - PRIME32_1;
 222         memcpy(statePtr, &state, sizeof(state));
 223 }
 224 EXPORT_SYMBOL(xxh32_reset);
 225
 226 void xxh64_reset(struct xxh64_state *statePtr, const uint64_t seed)
 227 {
 228         /* use a local state for memcpy() to avoid strict-aliasing warnings */
 229         struct xxh64_state state;
 230
 231         memset(&state, 0, sizeof(state));
 232         state.v1 = seed + PRIME64_1 + PRIME64_2;
 233         state.v2 = seed + PRIME64_2;
 234         state.v3 = seed + 0;
 235         state.v4 = seed - PRIME64_1;
 236         memcpy(statePtr, &state, sizeof(state));
 237 }
 238 EXPORT_SYMBOL(xxh64_reset);
 239
 240 int xxh32_update(struct xxh32_state *state, const void *input, const size_t len)
 241 {
 242         const uint8_t *p = (const uint8_t *)input;
 243         const uint8_t *const b_end = p + len;
 244
 245         if (input == NULL)
 246                 return -EINVAL;
 247
 248         state->total_len_32 += (uint32_t)len;
 249         state->large_len |= (len >= 16) | (state->total_len_32 >= 16);
 250
 251         if (state->memsize + len < 16) { /* fill in tmp buffer */
 252                 memcpy((uint8_t *)(state->mem32) + state->memsize, input, len);
 253                 state->memsize += (uint32_t)len;
 254                 return 0;
 255         }
 256
 257         if (state->memsize) { /* some data left from previous update */
 258                 const uint32_t *p32 = state->mem32;
 259
 260                 memcpy((uint8_t *)(state->mem32) + state->memsize, input,
 261                         16 - state->memsize);
 262
 263                 state->v1 = xxh32_round(state->v1, get_unaligned_le32(p32));
 264                 p32++;
 265                 state->v2 = xxh32_round(state->v2, get_unaligned_le32(p32));
 266                 p32++;
 267                 state->v3 = xxh32_round(state->v3, get_unaligned_le32(p32));
 268                 p32++;
 269                 state->v4 = xxh32_round(state->v4, get_unaligned_le32(p32));
 270                 p32++;
 271
 272                 p += 16-state->memsize;
 273                 state->memsize = 0;
 274         }
 275
 276         if (p <= b_end - 16) {
 277                 const uint8_t *const limit = b_end - 16;
 278                 uint32_t v1 = state->v1;
 279                 uint32_t v2 = state->v2;
 280                 uint32_t v3 = state->v3;
 281                 uint32_t v4 = state->v4;
 282
 283                 do {
 284                         v1 = xxh32_round(v1, get_unaligned_le32(p));
 285                         p += 4;
 286                         v2 = xxh32_round(v2, get_unaligned_le32(p));
 287                         p += 4;
 288                         v3 = xxh32_round(v3, get_unaligned_le32(p));
 289                         p += 4;
 290                         v4 = xxh32_round(v4, get_unaligned_le32(p));
 291                         p += 4;
 292                 } while (p <= limit);
 293
 294                 state->v1 = v1;
 295                 state->v2 = v2;
 296                 state->v3 = v3;
 297                 state->v4 = v4;
 298         }
 299
 300         if (p < b_end) {
 301                 memcpy(state->mem32, p, (size_t)(b_end-p));
 302                 state->memsize = (uint32_t)(b_end-p);
 303         }
 304
 305         return 0;
 306 }
 307 EXPORT_SYMBOL(xxh32_update);
 308
 309 uint32_t xxh32_digest(const struct xxh32_state *state)
 310 {
 311         const uint8_t *p = (const uint8_t *)state->mem32;
 312         const uint8_t *const b_end = (const uint8_t *)(state->mem32) +
 313                 state->memsize;
 314         uint32_t h32;
 315
 316         if (state->large_len) {
 317                 h32 = xxh_rotl32(state->v1, 1) + xxh_rotl32(state->v2, 7) +
 318                         xxh_rotl32(state->v3, 12) + xxh_rotl32(state->v4, 18);
 319         } else {
 320                 h32 = state->v3 /* == seed */ + PRIME32_5;
 321         }
 322
 323         h32 += state->total_len_32;
 324
 325         while (p + 4 <= b_end) {
 326                 h32 += get_unaligned_le32(p) * PRIME32_3;
 327                 h32 = xxh_rotl32(h32, 17) * PRIME32_4;
 328                 p += 4;
 329         }
 330
 331         while (p < b_end) {
 332                 h32 += (*p) * PRIME32_5;
 333                 h32 = xxh_rotl32(h32, 11) * PRIME32_1;
 334                 p++;
 335         }
 336
 337         h32 ^= h32 >> 15;
 338         h32 *= PRIME32_2;
 339         h32 ^= h32 >> 13;
 340         h32 *= PRIME32_3;
 341         h32 ^= h32 >> 16;
 342
 343         return h32;
 344 }
 345 EXPORT_SYMBOL(xxh32_digest);
 346
 347 int xxh64_update(struct xxh64_state *state, const void *input, const size_t len)
 348 {
 349         const uint8_t *p = (const uint8_t *)input;
 350         const uint8_t *const b_end = p + len;
 351
 352         if (input == NULL)
 353                 return -EINVAL;
 354
 355         state->total_len += len;
 356
 357         if (state->memsize + len < 32) { /* fill in tmp buffer */
 358                 memcpy(((uint8_t *)state->mem64) + state->memsize, input, len);
 359                 state->memsize += (uint32_t)len;
 360                 return 0;
 361         }
 362
 363         if (state->memsize) { /* tmp buffer is full */
 364                 uint64_t *p64 = state->mem64;
 365
 366                 memcpy(((uint8_t *)p64) + state->memsize, input,
 367                         32 - state->memsize);
 368
 369                 state->v1 = xxh64_round(state->v1, get_unaligned_le64(p64));
 370                 p64++;
 371                 state->v2 = xxh64_round(state->v2, get_unaligned_le64(p64));
 372                 p64++;
 373                 state->v3 = xxh64_round(state->v3, get_unaligned_le64(p64));
 374                 p64++;
 375                 state->v4 = xxh64_round(state->v4, get_unaligned_le64(p64));
 376
 377                 p += 32 - state->memsize;
 378                 state->memsize = 0;
 379         }
 380
 381         if (p + 32 <= b_end) {
 382                 const uint8_t *const limit = b_end - 32;
 383                 uint64_t v1 = state->v1;
 384                 uint64_t v2 = state->v2;
 385                 uint64_t v3 = state->v3;
 386                 uint64_t v4 = state->v4;
 387
 388                 do {
 389                         v1 = xxh64_round(v1, get_unaligned_le64(p));
 390                         p += 8;
 391                         v2 = xxh64_round(v2, get_unaligned_le64(p));
 392                         p += 8;
 393                         v3 = xxh64_round(v3, get_unaligned_le64(p));
 394                         p += 8;
 395                         v4 = xxh64_round(v4, get_unaligned_le64(p));
 396                         p += 8;
 397                 } while (p <= limit);
 398
 399                 state->v1 = v1;
 400                 state->v2 = v2;
 401                 state->v3 = v3;
 402                 state->v4 = v4;
 403         }
 404
 405         if (p < b_end) {
 406                 memcpy(state->mem64, p, (size_t)(b_end-p));
 407                 state->memsize = (uint32_t)(b_end - p);
 408         }
 409
 410         return 0;
 411 }
 412 EXPORT_SYMBOL(xxh64_update);
 413
 414 uint64_t xxh64_digest(const struct xxh64_state *state)
 415 {
 416         const uint8_t *p = (const uint8_t *)state->mem64;
 417         const uint8_t *const b_end = (const uint8_t *)state->mem64 +
 418                 state->memsize;
 419         uint64_t h64;
 420
 421         if (state->total_len >= 32) {
 422                 const uint64_t v1 = state->v1;
 423                 const uint64_t v2 = state->v2;
 424                 const uint64_t v3 = state->v3;
 425                 const uint64_t v4 = state->v4;
 426
 427                 h64 = xxh_rotl64(v1, 1) + xxh_rotl64(v2, 7) +
 428                         xxh_rotl64(v3, 12) + xxh_rotl64(v4, 18);
 429                 h64 = xxh64_merge_round(h64, v1);
 430                 h64 = xxh64_merge_round(h64, v2);
 431                 h64 = xxh64_merge_round(h64, v3);
 432                 h64 = xxh64_merge_round(h64, v4);
 433         } else {
 434                 h64  = state->v3 + PRIME64_5;
 435         }
 436
 437         h64 += (uint64_t)state->total_len;
 438
 439         while (p + 8 <= b_end) {
 440                 const uint64_t k1 = xxh64_round(0, get_unaligned_le64(p));
 441
 442                 h64 ^= k1;
 443                 h64 = xxh_rotl64(h64, 27) * PRIME64_1 + PRIME64_4;
 444                 p += 8;
 445         }
 446
 447         if (p + 4 <= b_end) {
 448                 h64 ^= (uint64_t)(get_unaligned_le32(p)) * PRIME64_1;
 449                 h64 = xxh_rotl64(h64, 23) * PRIME64_2 + PRIME64_3;
 450                 p += 4;
 451         }
 452
 453         while (p < b_end) {
 454                 h64 ^= (*p) * PRIME64_5;
 455                 h64 = xxh_rotl64(h64, 11) * PRIME64_1;
 456                 p++;
 457         }
 458
 459         h64 ^= h64 >> 33;
 460         h64 *= PRIME64_2;
 461         h64 ^= h64 >> 29;
 462         h64 *= PRIME64_3;
 463         h64 ^= h64 >> 32;
 464
 465         return h64;
 466 }
 467 EXPORT_SYMBOL(xxh64_digest);