Jon Ashburn | fc1031e | 2015-11-17 15:31:02 -0700 | [diff] [blame] | 1 | |
| 2 | /** |
| 3 | * `murmurhash.h' - murmurhash |
| 4 | * |
| 5 | * copyright (c) 2014 joseph werle <joseph.werle@gmail.com> |
Jon Ashburn | 23d36b1 | 2016-02-02 17:47:28 -0700 | [diff] [blame] | 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 | * |
Jon Ashburn | 23d36b1 | 2016-02-02 17:47:28 -0700 | [diff] [blame] | 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. |
Jon Ashburn | fc1031e | 2015-11-17 15:31:02 -0700 | [diff] [blame] | 28 | */ |
| 29 | |
| 30 | #include <stdlib.h> |
| 31 | #include <stdio.h> |
| 32 | #include <stdint.h> |
| 33 | #include "murmurhash.h" |
| 34 | |
Jon Ashburn | 23d36b1 | 2016-02-02 17:47:28 -0700 | [diff] [blame] | 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 |
Jon Ashburn | fc1031e | 2015-11-17 15:31:02 -0700 | [diff] [blame] | 49 | |
Jon Ashburn | 23d36b1 | 2016-02-02 17:47:28 -0700 | [diff] [blame] | 50 | h = seed; |
Jon Ashburn | fc1031e | 2015-11-17 15:31:02 -0700 | [diff] [blame] | 51 | |
Jon Ashburn | 23d36b1 | 2016-02-02 17:47:28 -0700 | [diff] [blame] | 52 | chunks = (const uint32_t *)(d + l * 4); // body |
| 53 | tail = (const uint8_t *)(d + l * 4); // last 8 byte chunk of `key' |
Jon Ashburn | fc1031e | 2015-11-17 15:31:02 -0700 | [diff] [blame] | 54 | |
Jon Ashburn | 23d36b1 | 2016-02-02 17:47:28 -0700 | [diff] [blame] | 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]; |
Jon Ashburn | fc1031e | 2015-11-17 15:31:02 -0700 | [diff] [blame] | 59 | |
Jon Ashburn | 23d36b1 | 2016-02-02 17:47:28 -0700 | [diff] [blame] | 60 | // encode next 4 byte chunk of `key' |
| 61 | k *= c1; |
| 62 | k = (k << r1) | (k >> (32 - r1)); |
| 63 | k *= c2; |
Jon Ashburn | fc1031e | 2015-11-17 15:31:02 -0700 | [diff] [blame] | 64 | |
Jon Ashburn | 23d36b1 | 2016-02-02 17:47:28 -0700 | [diff] [blame] | 65 | // append to hash |
| 66 | h ^= k; |
| 67 | h = (h << r2) | (h >> (32 - r2)); |
| 68 | h = h * m + n; |
| 69 | } |
Jon Ashburn | fc1031e | 2015-11-17 15:31:02 -0700 | [diff] [blame] | 70 | |
Jon Ashburn | 23d36b1 | 2016-02-02 17:47:28 -0700 | [diff] [blame] | 71 | k = 0; |
Jon Ashburn | fc1031e | 2015-11-17 15:31:02 -0700 | [diff] [blame] | 72 | |
Jon Ashburn | 23d36b1 | 2016-02-02 17:47:28 -0700 | [diff] [blame] | 73 | // remainder |
| 74 | switch (len & 3) { // `len % 4' |
| 75 | case 3: |
| 76 | k ^= (tail[2] << 16); |
| 77 | case 2: |
| 78 | k ^= (tail[1] << 8); |
Jon Ashburn | fc1031e | 2015-11-17 15:31:02 -0700 | [diff] [blame] | 79 | |
| 80 | case 1: |
Jon Ashburn | 23d36b1 | 2016-02-02 17:47:28 -0700 | [diff] [blame] | 81 | k ^= tail[0]; |
| 82 | k *= c1; |
| 83 | k = (k << r1) | (k >> (32 - r1)); |
| 84 | k *= c2; |
| 85 | h ^= k; |
| 86 | } |
Jon Ashburn | fc1031e | 2015-11-17 15:31:02 -0700 | [diff] [blame] | 87 | |
Jon Ashburn | 23d36b1 | 2016-02-02 17:47:28 -0700 | [diff] [blame] | 88 | h ^= len; |
Jon Ashburn | fc1031e | 2015-11-17 15:31:02 -0700 | [diff] [blame] | 89 | |
Jon Ashburn | 23d36b1 | 2016-02-02 17:47:28 -0700 | [diff] [blame] | 90 | h ^= (h >> 16); |
| 91 | h *= 0x85ebca6b; |
| 92 | h ^= (h >> 13); |
| 93 | h *= 0xc2b2ae35; |
| 94 | h ^= (h >> 16); |
Jon Ashburn | fc1031e | 2015-11-17 15:31:02 -0700 | [diff] [blame] | 95 | |
Jon Ashburn | 23d36b1 | 2016-02-02 17:47:28 -0700 | [diff] [blame] | 96 | return h; |
Jon Ashburn | fc1031e | 2015-11-17 15:31:02 -0700 | [diff] [blame] | 97 | } |