1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
|
/**
* `murmurhash.h' - murmurhash
*
* copyright (c) 2014 joseph werle <joseph.werle@gmail.com>
* Copyright (c) 2015-2016 The Khronos Group Inc.
* Copyright (c) 2015-2016 Valve Corporation
* Copyright (c) 2015-2016 LunarG, Inc.
*
* Permission is hereby granted, free of charge, to any person obtaining a copy
* of this software and/or associated documentation files (the "Materials"), to
* deal in the Materials without restriction, including without limitation the
* rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
* sell copies of the Materials, and to permit persons to whom the Materials are
* furnished to do so, subject to the following conditions:
*
* The above copyright notice(s) and this permission notice shall be included in
* all copies or substantial portions of the Materials.
*
* THE MATERIALS ARE PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
* IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
* FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
*
* IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM,
* DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR
* OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE MATERIALS OR THE
* USE OR OTHER DEALINGS IN THE MATERIALS.
*/
#include <stdlib.h>
#include <stdio.h>
#include <stdint.h>
#include "murmurhash.h"
uint32_t murmurhash(const char *key, size_t len, uint32_t seed) {
uint32_t c1 = 0xcc9e2d51;
uint32_t c2 = 0x1b873593;
uint32_t r1 = 15;
uint32_t r2 = 13;
uint32_t m = 5;
uint32_t n = 0xe6546b64;
uint32_t h = 0;
uint32_t k = 0;
uint8_t *d = (uint8_t *)key; // 32 bit extract from `key'
const uint32_t *chunks = NULL;
const uint8_t *tail = NULL; // tail - last 8 bytes
int i = 0;
int l = (int)len / 4; // chunk length
h = seed;
chunks = (const uint32_t *)(d + l * 4); // body
tail = (const uint8_t *)(d + l * 4); // last 8 byte chunk of `key'
// for each 4 byte chunk of `key'
for (i = -l; i != 0; ++i) {
// next 4 byte chunk of `key'
k = chunks[i];
// encode next 4 byte chunk of `key'
k *= c1;
k = (k << r1) | (k >> (32 - r1));
k *= c2;
// append to hash
h ^= k;
h = (h << r2) | (h >> (32 - r2));
h = h * m + n;
}
k = 0;
// remainder
switch (len & 3) { // `len % 4'
case 3:
k ^= (tail[2] << 16);
// fall through
case 2:
k ^= (tail[1] << 8);
// fall through
case 1:
k ^= tail[0];
k *= c1;
k = (k << r1) | (k >> (32 - r1));
k *= c2;
h ^= k;
}
h ^= len;
h ^= (h >> 16);
h *= 0x85ebca6b;
h ^= (h >> 13);
h *= 0xc2b2ae35;
h ^= (h >> 16);
return h;
}
|