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 return static_cast<size_t>(v); 65 } 66 67 } // namespace 68 69 70 // This code was taken from MurmurHash. hash_combine(size_t seed,size_t value)71size_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 hash_value(unsigned int v)98size_t hash_value(unsigned int v) { return hash_value_unsigned(v); } 99 100 hash_value(unsigned long v)101size_t hash_value(unsigned long v) { // NOLINT(runtime/int) 102 return hash_value_unsigned(v); 103 } 104 105 hash_value(unsigned long long v)106size_t hash_value(unsigned long long v) { // NOLINT(runtime/int) 107 return hash_value_unsigned(v); 108 } 109 110 } // namespace base 111 } // namespace v8 112