Home | History | Annotate | Download | only in base 
      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       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.
     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 
     98 size_t hash_value(unsigned int v) { return hash_value_unsigned(v); }
     99 
    100 
    101 size_t hash_value(unsigned long v) {  // NOLINT(runtime/int)
    102   return hash_value_unsigned(v);
    103 }
    104 
    105 
    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