1 /*
2  * Copyright (c) 2022, Meta
3  *
4  * SPDX-License-Identifier: Apache-2.0
5  */
6 
7 #include <stddef.h>
8 #include <stdint.h>
9 #include <zephyr/toolchain.h>
10 #include <zephyr/sys/util.h>
11 
murmur_32_scramble(uint32_t k)12 static inline uint32_t murmur_32_scramble(uint32_t k)
13 {
14 	k *= 0xcc9e2d51;
15 	k = (k << 15) | (k >> 17);
16 	k *= 0x1b873593;
17 
18 	return k;
19 }
20 
21 #define _LOOP(_GET) \
22 	for (; n >= sizeof(uint32_t); n -= sizeof(uint32_t), str += sizeof(uint32_t)) { \
23 		k =  _GET; \
24 		h ^= murmur_32_scramble(k); \
25 		h = (h << 13) | (h >> 19); \
26 		h = h * 5 + 0xe6546b64; \
27 	}
28 
sys_hash32_murmur3(const char * str,size_t n)29 uint32_t sys_hash32_murmur3(const char *str, size_t n)
30 {
31 	uint32_t k;
32 	/* seed of 0 */
33 	uint32_t h = 0;
34 	const size_t len = n;
35 
36 	if (IS_ALIGNED(str, sizeof(uint32_t))) {
37 		_LOOP(*(const uint32_t *)str);
38 	} else {
39 		_LOOP(UNALIGNED_GET((const uint32_t *)str));
40 	}
41 
42 	for (k = 0; n != 0; --n, ++str) {
43 		k <<= 8;
44 		k |= *str;
45 	}
46 
47 	h ^= murmur_32_scramble(k);
48 
49 	h ^= len;
50 	h ^= h >> 16;
51 	h *= 0x85ebca6b;
52 	h ^= h >> 13;
53 	h *= 0xc2b2ae35;
54 	h ^= h >> 16;
55 
56 	return h;
57 }
58