1 /*
2 *
3 * Copyright 2015 gRPC authors.
4 *
5 * Licensed under the Apache License, Version 2.0 (the "License");
6 * you may not use this file except in compliance with the License.
7 * You may obtain a copy of the License at
8 *
9 * http://www.apache.org/licenses/LICENSE-2.0
10 *
11 * Unless required by applicable law or agreed to in writing, software
12 * distributed under the License is distributed on an "AS IS" BASIS,
13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 * See the License for the specific language governing permissions and
15 * limitations under the License.
16 *
17 */
18
19 #include <grpc/support/port_platform.h>
20
21 #include "src/core/lib/gpr/murmur_hash.h"
22
23 #include <string.h>
24
25 #define ROTL32(x, r) (((x) << (r)) | ((x) >> (32 - (r))))
26
27 #define FMIX32(h) \
28 (h) ^= (h) >> 16; \
29 (h) *= 0x85ebca6b; \
30 (h) ^= (h) >> 13; \
31 (h) *= 0xc2b2ae35; \
32 (h) ^= (h) >> 16;
33
gpr_murmur_hash3(const void * key,size_t len,uint32_t seed)34 uint32_t gpr_murmur_hash3(const void* key, size_t len, uint32_t seed) {
35 uint32_t h1 = seed;
36 uint32_t k1;
37
38 const uint32_t c1 = 0xcc9e2d51;
39 const uint32_t c2 = 0x1b873593;
40
41 const uint8_t* keyptr = static_cast<const uint8_t*>(key);
42 const size_t bsize = sizeof(k1);
43 const size_t nblocks = len / bsize;
44
45 /* body */
46 for (size_t i = 0; i < nblocks; i++, keyptr += bsize) {
47 memcpy(&k1, keyptr, bsize);
48
49 k1 *= c1;
50 k1 = ROTL32(k1, 15);
51 k1 *= c2;
52
53 h1 ^= k1;
54 h1 = ROTL32(h1, 13);
55 h1 = h1 * 5 + 0xe6546b64;
56 }
57
58 k1 = 0;
59
60 /* tail */
61 switch (len & 3) {
62 case 3:
63 k1 ^= (static_cast<uint32_t>(keyptr[2])) << 16;
64 /* fallthrough */
65 case 2:
66 k1 ^= (static_cast<uint32_t>(keyptr[1])) << 8;
67 /* fallthrough */
68 case 1:
69 k1 ^= keyptr[0];
70 k1 *= c1;
71 k1 = ROTL32(k1, 15);
72 k1 *= c2;
73 h1 ^= k1;
74 };
75
76 /* finalization */
77 h1 ^= static_cast<uint32_t>(len);
78 FMIX32(h1);
79 return h1;
80 }
81