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 <asm/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
  48         const u64 *blocks = (const u64 *)(data);
  49
  50         int i;
  51
  52         for (i = 0; i < nblocks; i++) {
  53                 u64 k1 = get_unaligned_le64(&blocks[i * 2]);
  54                 u64 k2 = get_unaligned_le64(&blocks[i * 2 + 1]);
  55
  56                 k1 *= c1;
  57                 k1 = ROTL64(k1, 31);
  58                 k1 *= c2;
  59                 h1 ^= k1;
  60
  61                 h1 = ROTL64(h1, 27);
  62                 h1 += h2;
  63                 h1 = h1 * 5 + 0x52dce729;
  64
  65                 k2 *= c2;
  66                 k2 = ROTL64(k2, 33);
  67                 k2 *= c1;
  68                 h2 ^= k2;
  69
  70                 h2 = ROTL64(h2, 31);
  71                 h2 += h1;
  72                 h2 = h2 * 5 + 0x38495ab5;
  73         }
  74
  75         /* tail */
  76
  77         {
  78                 const u8 *tail = (const u8 *)(data + nblocks * 16);
  79
  80                 u64 k1 = 0;
  81                 u64 k2 = 0;
  82
  83                 switch (len & 15) {
  84                 case 15:
  85                         k2 ^= ((u64)tail[14]) << 48;
  86                         fallthrough;
  87                 case 14:
  88                         k2 ^= ((u64)tail[13]) << 40;
  89                         fallthrough;
  90                 case 13:
  91                         k2 ^= ((u64)tail[12]) << 32;
  92                         fallthrough;
  93                 case 12:
  94                         k2 ^= ((u64)tail[11]) << 24;
  95                         fallthrough;
  96                 case 11:
  97                         k2 ^= ((u64)tail[10]) << 16;
  98                         fallthrough;
  99                 case 10:
 100                         k2 ^= ((u64)tail[9]) << 8;
 101                         fallthrough;
 102                 case 9:
 103                         k2 ^= ((u64)tail[8]) << 0;
 104                         k2 *= c2;
 105                         k2 = ROTL64(k2, 33);
 106                         k2 *= c1;
 107                         h2 ^= k2;
 108                         fallthrough;
 109
 110                 case 8:
 111                         k1 ^= ((u64)tail[7]) << 56;
 112                         fallthrough;
 113                 case 7:
 114                         k1 ^= ((u64)tail[6]) << 48;
 115                         fallthrough;
 116                 case 6:
 117                         k1 ^= ((u64)tail[5]) << 40;
 118                         fallthrough;
 119                 case 5:
 120                         k1 ^= ((u64)tail[4]) << 32;
 121                         fallthrough;
 122                 case 4:
 123                         k1 ^= ((u64)tail[3]) << 24;
 124                         fallthrough;
 125                 case 3:
 126                         k1 ^= ((u64)tail[2]) << 16;
 127                         fallthrough;
 128                 case 2:
 129                         k1 ^= ((u64)tail[1]) << 8;
 130                         fallthrough;
 131                 case 1:
 132                         k1 ^= ((u64)tail[0]) << 0;
 133                         k1 *= c1;
 134                         k1 = ROTL64(k1, 31);
 135                         k1 *= c2;
 136                         h1 ^= k1;
 137                         break;
 138                 default:
 139                         break;
 140                 };
 141         }
 142         /* finalization */
 143
 144         h1 ^= len;
 145         h2 ^= len;
 146
 147         h1 += h2;
 148         h2 += h1;
 149
 150         h1 = fmix64(h1);
 151         h2 = fmix64(h2);
 152
 153         h1 += h2;
 154         h2 += h1;
 155
 156         put_unaligned_le64(h1, &hash_out[0]);
 157         put_unaligned_le64(h2, &hash_out[1]);
 158 }