drivers/md/dm-vdo/murmurhash3.c

   1 // SPDX-License-Identifier: LGPL-2.1+
   2 /*
   3  * MurmurHash3 was written by Austin Appleby, and is placed in the public
   4  * domain. The author hereby disclaims copyright to this source code.
   5  *
   6  * Adapted by John Wiele (jwiele@redhat.com).
   7  */
   8
   9 #include "murmurhash3.h"
  10
  11 #include <linux/unaligned.h>
  12
  13 static inline u64 rotl64(u64 x, s8 r)
  14 {
  15         return (x << r) | (x >> (64 - r));
  16 }
  17
  18 #define ROTL64(x, y) rotl64(x, y)
  19
  20 /* Finalization mix - force all bits of a hash block to avalanche */
  21
  22 static __always_inline u64 fmix64(u64 k)
  23 {
  24         k ^= k >> 33;
  25         k *= 0xff51afd7ed558ccdLLU;
  26         k ^= k >> 33;
  27         k *= 0xc4ceb9fe1a85ec53LLU;
  28         k ^= k >> 33;
  29
  30         return k;
  31 }
  32
  33 void murmurhash3_128(const void *key, const int len, const u32 seed, void *out)
  34 {
  35         const u8 *data = key;
  36         const int nblocks = len / 16;
  37
  38         u64 h1 = seed;
  39         u64 h2 = seed;
  40
  41         const u64 c1 = 0x87c37b91114253d5LLU;
  42         const u64 c2 = 0x4cf5ad432745937fLLU;
  43
  44         u64 *hash_out = out;
  45
  46         /* body */
  47         int i;
  48
  49         for (i = 0; i < nblocks; i++) {
  50                 u64 k1 = get_unaligned_le64(&data[i * 16]);
  51                 u64 k2 = get_unaligned_le64(&data[i * 16 + 8]);
  52
  53                 k1 *= c1;
  54                 k1 = ROTL64(k1, 31);
  55                 k1 *= c2;
  56                 h1 ^= k1;
  57
  58                 h1 = ROTL64(h1, 27);
  59                 h1 += h2;
  60                 h1 = h1 * 5 + 0x52dce729;
  61
  62                 k2 *= c2;
  63                 k2 = ROTL64(k2, 33);
  64                 k2 *= c1;
  65                 h2 ^= k2;
  66
  67                 h2 = ROTL64(h2, 31);
  68                 h2 += h1;
  69                 h2 = h2 * 5 + 0x38495ab5;
  70         }
  71
  72         /* tail */
  73
  74         {
  75                 const u8 *tail = (const u8 *)(data + nblocks * 16);
  76
  77                 u64 k1 = 0;
  78                 u64 k2 = 0;
  79
  80                 switch (len & 15) {
  81                 case 15:
  82                         k2 ^= ((u64)tail[14]) << 48;
  83                         fallthrough;
  84                 case 14:
  85                         k2 ^= ((u64)tail[13]) << 40;
  86                         fallthrough;
  87                 case 13:
  88                         k2 ^= ((u64)tail[12]) << 32;
  89                         fallthrough;
  90                 case 12:
  91                         k2 ^= ((u64)tail[11]) << 24;
  92                         fallthrough;
  93                 case 11:
  94                         k2 ^= ((u64)tail[10]) << 16;
  95                         fallthrough;
  96                 case 10:
  97                         k2 ^= ((u64)tail[9]) << 8;
  98                         fallthrough;
  99                 case 9:
 100                         k2 ^= ((u64)tail[8]) << 0;
 101                         k2 *= c2;
 102                         k2 = ROTL64(k2, 33);
 103                         k2 *= c1;
 104                         h2 ^= k2;
 105                         fallthrough;
 106
 107                 case 8:
 108                         k1 ^= ((u64)tail[7]) << 56;
 109                         fallthrough;
 110                 case 7:
 111                         k1 ^= ((u64)tail[6]) << 48;
 112                         fallthrough;
 113                 case 6:
 114                         k1 ^= ((u64)tail[5]) << 40;
 115                         fallthrough;
 116                 case 5:
 117                         k1 ^= ((u64)tail[4]) << 32;
 118                         fallthrough;
 119                 case 4:
 120                         k1 ^= ((u64)tail[3]) << 24;
 121                         fallthrough;
 122                 case 3:
 123                         k1 ^= ((u64)tail[2]) << 16;
 124                         fallthrough;
 125                 case 2:
 126                         k1 ^= ((u64)tail[1]) << 8;
 127                         fallthrough;
 128                 case 1:
 129                         k1 ^= ((u64)tail[0]) << 0;
 130                         k1 *= c1;
 131                         k1 = ROTL64(k1, 31);
 132                         k1 *= c2;
 133                         h1 ^= k1;
 134                         break;
 135                 default:
 136                         break;
 137                 }
 138         }
 139         /* finalization */
 140
 141         h1 ^= len;
 142         h2 ^= len;
 143
 144         h1 += h2;
 145         h2 += h1;
 146
 147         h1 = fmix64(h1);
 148         h2 = fmix64(h2);
 149
 150         h1 += h2;
 151         h2 += h1;
 152
 153         put_unaligned_le64(h1, &hash_out[0]);
 154         put_unaligned_le64(h2, &hash_out[1]);
 155 }