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