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
 13static 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
 22static __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
 33void 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}