Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 1 | // Copyright 2014 the V8 project authors. All rights reserved. |
| 2 | // Use of this source code is governed by a BSD-style license that can be |
| 3 | // found in the LICENSE file. |
| 4 | // |
| 5 | // This also contains public domain code from MurmurHash. From the |
| 6 | // MurmurHash header: |
| 7 | // |
| 8 | // MurmurHash3 was written by Austin Appleby, and is placed in the public |
| 9 | // domain. The author hereby disclaims copyright to this source code. |
| 10 | |
| 11 | #include "src/base/functional.h" |
| 12 | |
| 13 | #include <limits> |
| 14 | |
| 15 | #include "src/base/bits.h" |
| 16 | |
| 17 | namespace v8 { |
| 18 | namespace base { |
| 19 | |
| 20 | namespace { |
| 21 | |
| 22 | // Thomas Wang, Integer Hash Functions. |
| 23 | // https://gist.github.com/badboy/6267743 |
| 24 | template <typename T> |
| 25 | V8_INLINE size_t hash_value_unsigned(T v) { |
| 26 | switch (sizeof(T)) { |
| 27 | case 4: { |
| 28 | // "32 bit Mix Functions" |
| 29 | v = ~v + (v << 15); // v = (v << 15) - v - 1; |
| 30 | v = v ^ (v >> 12); |
| 31 | v = v + (v << 2); |
| 32 | v = v ^ (v >> 4); |
| 33 | v = v * 2057; // v = (v + (v << 3)) + (v << 11); |
| 34 | v = v ^ (v >> 16); |
| 35 | return static_cast<size_t>(v); |
| 36 | } |
| 37 | case 8: { |
| 38 | switch (sizeof(size_t)) { |
| 39 | case 4: { |
| 40 | // "64 bit to 32 bit Hash Functions" |
| 41 | v = ~v + (v << 18); // v = (v << 18) - v - 1; |
| 42 | v = v ^ (v >> 31); |
| 43 | v = v * 21; // v = (v + (v << 2)) + (v << 4); |
| 44 | v = v ^ (v >> 11); |
| 45 | v = v + (v << 6); |
| 46 | v = v ^ (v >> 22); |
| 47 | return static_cast<size_t>(v); |
| 48 | } |
| 49 | case 8: { |
| 50 | // "64 bit Mix Functions" |
| 51 | v = ~v + (v << 21); // v = (v << 21) - v - 1; |
| 52 | v = v ^ (v >> 24); |
| 53 | v = (v + (v << 3)) + (v << 8); // v * 265 |
| 54 | v = v ^ (v >> 14); |
| 55 | v = (v + (v << 2)) + (v << 4); // v * 21 |
| 56 | v = v ^ (v >> 28); |
| 57 | v = v + (v << 31); |
| 58 | return static_cast<size_t>(v); |
| 59 | } |
| 60 | } |
| 61 | } |
| 62 | } |
| 63 | UNREACHABLE(); |
| 64 | return static_cast<size_t>(v); |
| 65 | } |
| 66 | |
| 67 | } // namespace |
| 68 | |
| 69 | |
| 70 | // This code was taken from MurmurHash. |
| 71 | size_t hash_combine(size_t seed, size_t value) { |
| 72 | #if V8_HOST_ARCH_32_BIT |
| 73 | const uint32_t c1 = 0xcc9e2d51; |
| 74 | const uint32_t c2 = 0x1b873593; |
| 75 | |
| 76 | value *= c1; |
| 77 | value = bits::RotateRight32(value, 15); |
| 78 | value *= c2; |
| 79 | |
| 80 | seed ^= value; |
| 81 | seed = bits::RotateRight32(seed, 13); |
| 82 | seed = seed * 5 + 0xe6546b64; |
| 83 | #else |
| 84 | const uint64_t m = V8_UINT64_C(0xc6a4a7935bd1e995); |
| 85 | const uint32_t r = 47; |
| 86 | |
| 87 | value *= m; |
| 88 | value ^= value >> r; |
| 89 | value *= m; |
| 90 | |
| 91 | seed ^= value; |
| 92 | seed *= m; |
| 93 | #endif // V8_HOST_ARCH_32_BIT |
| 94 | return seed; |
| 95 | } |
| 96 | |
| 97 | |
| 98 | size_t hash_value(unsigned int v) { return hash_value_unsigned(v); } |
| 99 | |
| 100 | |
| 101 | size_t hash_value(unsigned long v) { // NOLINT(runtime/int) |
| 102 | return hash_value_unsigned(v); |
| 103 | } |
| 104 | |
| 105 | |
| 106 | size_t hash_value(unsigned long long v) { // NOLINT(runtime/int) |
| 107 | return hash_value_unsigned(v); |
| 108 | } |
| 109 | |
| 110 | } // namespace base |
| 111 | } // namespace v8 |