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