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)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.
hash_combine(size_t seed,size_t value)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 
hash_value(unsigned int v)98 size_t hash_value(unsigned int v) { return hash_value_unsigned(v); }
99 
100 
hash_value(unsigned long v)101 size_t hash_value(unsigned long v) {  // NOLINT(runtime/int)
102   return hash_value_unsigned(v);
103 }
104 
105 
hash_value(unsigned long long v)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
112