Line data    Source code

       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   832372855 :       v = ~v + (v << 15);  // v = (v << 15) - v - 1;
      30   832372855 :       v = v ^ (v >> 12);
      31   832372855 :       v = v + (v << 2);
      32   832372855 :       v = v ^ (v >> 4);
      33   832372855 :       v = v * 2057;  // v = (v + (v << 3)) + (v << 11);
      34   832372855 :       v = v ^ (v >> 16);
      35   832372855 :       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   938363257 :           v = ~v + (v << 21);  // v = (v << 21) - v - 1;
      52   938363257 :           v = v ^ (v >> 24);
      53   938363257 :           v = (v + (v << 3)) + (v << 8);  // v * 265
      54   938363257 :           v = v ^ (v >> 14);
      55   938363257 :           v = (v + (v << 2)) + (v << 4);  // v * 21
      56   938363257 :           v = v ^ (v >> 28);
      57   938363257 :           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.
      70  1318546818 : size_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  1318546818 :   value *= m;
      87  1318546818 :   value ^= value >> r;
      88  1318546818 :   value *= m;
      89             : 
      90  1318546818 :   seed ^= value;
      91  1318546818 :   seed *= m;
      92             : #endif  // V8_HOST_ARCH_32_BIT
      93  1318546818 :   return seed;
      94             : }
      95             : 
      96             : 
      97  1664745710 : size_t hash_value(unsigned int v) { return hash_value_unsigned(v); }
      98             : 
      99             : 
     100   938361209 : size_t hash_value(unsigned long v) {  // NOLINT(runtime/int)
     101   938361209 :   return hash_value_unsigned(v);
     102             : }
     103             : 
     104             : 
     105        2048 : size_t hash_value(unsigned long long v) {  // NOLINT(runtime/int)
     106        2048 :   return hash_value_unsigned(v);
     107             : }
     108             : 
     109             : }  // namespace base
     110             : }  // namespace v8