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> hash_value_unsigned(T v)25V8_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 } 65 66 } // namespace 67 68 69 // This code was taken from MurmurHash. hash_combine(size_t seed,size_t value)70size_t hash_combine(size_t seed, size_t value) { 71 #if V8_HOST_ARCH_32_BIT 72 const uint32_t c1 = 0xCC9E2D51; 73 const uint32_t c2 = 0x1B873593; 74 75 value *= c1; 76 value = bits::RotateRight32(value, 15); 77 value *= c2; 78 79 seed ^= value; 80 seed = bits::RotateRight32(seed, 13); 81 seed = seed * 5 + 0xE6546B64; 82 #else 83 const uint64_t m = uint64_t{0xC6A4A7935BD1E995}; 84 const uint32_t r = 47; 85 86 value *= m; 87 value ^= value >> r; 88 value *= m; 89 90 seed ^= value; 91 seed *= m; 92 #endif // V8_HOST_ARCH_32_BIT 93 return seed; 94 } 95 96 hash_value(unsigned int v)97size_t hash_value(unsigned int v) { return hash_value_unsigned(v); } 98 99 hash_value(unsigned long v)100size_t hash_value(unsigned long v) { // NOLINT(runtime/int) 101 return hash_value_unsigned(v); 102 } 103 104 hash_value(unsigned long long v)105size_t hash_value(unsigned long long v) { // NOLINT(runtime/int) 106 return hash_value_unsigned(v); 107 } 108 109 } // namespace base 110 } // namespace v8 111