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 } 156