clang-format: no single-line case
[awesomized/libmemcached] / src / libhashkit / murmur3.cc
1 /*
2 +--------------------------------------------------------------------+
3 | libmemcached - C/C++ Client Library for memcached |
4 +--------------------------------------------------------------------+
5 | Redistribution and use in source and binary forms, with or without |
6 | modification, are permitted under the terms of the BSD license. |
7 | You should have received a copy of the license in a bundled file |
8 | named LICENSE; in case you did not receive a copy you can review |
9 | the terms online at: https://opensource.org/licenses/BSD-3-Clause |
10 +--------------------------------------------------------------------+
11 | Copyright (c) 2006-2014 Brian Aker https://datadifferential.com/ |
12 | Copyright (c) 2020 Michael Wallner <mike@php.net> |
13 +--------------------------------------------------------------------+
14 */
15
16 #include "libhashkit/hashkitcon.h"
17
18 #include "libhashkit/murmur3.h"
19
20 //-----------------------------------------------------------------------------
21 // Platform-specific functions and macros
22
23 #ifdef __GNUC__
24 # define FORCE_INLINE __attribute__((always_inline)) inline
25 #else
26 # define FORCE_INLINE inline
27 #endif
28
29 static FORCE_INLINE uint32_t rotl32(uint32_t x, int8_t r) {
30 return (x << r) | (x >> (32 - r));
31 }
32
33 #define ROTL32(x, y) rotl32(x, y)
34
35 //-----------------------------------------------------------------------------
36 // Block read - if your platform needs to do endian-swapping or can only
37 // handle aligned reads, do the conversion here
38
39 #include <cassert>
40 #include <cstring>
41 template<typename T>
42 static inline T getblock(const T *blocks, int i) {
43 T b;
44 memcpy(&b, ((const uint8_t *) blocks) + i * sizeof(T), sizeof(T));
45 return b;
46 }
47
48 //-----------------------------------------------------------------------------
49 // Finalization mix - force all bits of a hash block to avalanche
50
51 static FORCE_INLINE uint32_t fmix32(uint32_t h) {
52 h ^= h >> 16;
53 h *= 0x85ebca6b;
54 h ^= h >> 13;
55 h *= 0xc2b2ae35;
56 h ^= h >> 16;
57
58 return h;
59 }
60
61 //-----------------------------------------------------------------------------
62
63 void MurmurHash3_x86_32(const void *key, int len, uint32_t seed, void *out) {
64 const uint8_t *data = (const uint8_t *) key;
65 const int nblocks = len / 4;
66 int i;
67
68 uint32_t h1 = seed;
69
70 uint32_t c1 = 0xcc9e2d51;
71 uint32_t c2 = 0x1b873593;
72
73 //----------
74 // body
75
76 const uint32_t *blocks = (const uint32_t *) (data + nblocks * 4);
77
78 for (i = -nblocks; i; i++) {
79 uint32_t k1 = getblock(blocks, i);
80 #if WORDS_BIGENDIAN
81 k1 = BYTESWAP_32(k1);
82 #endif
83
84 k1 *= c1;
85 k1 = ROTL32(k1, 15);
86 k1 *= c2;
87
88 h1 ^= k1;
89 h1 = ROTL32(h1, 13);
90 h1 = h1 * 5 + 0xe6546b64;
91 }
92
93 //----------
94 // tail
95
96 const uint8_t *tail = (const uint8_t *) (data + nblocks * 4);
97
98 uint32_t k1 = 0;
99 memcpy(&k1, tail, len & 3);
100 #if WORDS_BIGENDIAN
101 k1 = BYTESWAP_32(k1);
102 #endif
103
104 k1 *= c1;
105 k1 = ROTL32(k1, 15);
106 k1 *= c2;
107 h1 ^= k1;
108
109 //----------
110 // finalization
111
112 h1 ^= len;
113
114 h1 = fmix32(h1);
115
116 *(uint32_t *) out = h1;
117 }