functional.cc 2.64 KB
Newer Older
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
// Copyright 2014 the V8 project authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
//
// This also contains public domain code from MurmurHash. From the
// MurmurHash header:
//
// MurmurHash3 was written by Austin Appleby, and is placed in the public
// domain. The author hereby disclaims copyright to this source code.

#include "src/base/functional.h"

#include <limits>

#include "src/base/bits.h"

namespace v8 {
namespace base {

namespace {

22 23
// Thomas Wang, Integer Hash Functions.
// https://gist.github.com/badboy/6267743
24
template <typename T>
25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61
V8_INLINE size_t hash_value_unsigned(T v) {
  switch (sizeof(T)) {
    case 4: {
      // "32 bit Mix Functions"
      v = ~v + (v << 15);  // v = (v << 15) - v - 1;
      v = v ^ (v >> 12);
      v = v + (v << 2);
      v = v ^ (v >> 4);
      v = v * 2057;  // v = (v + (v << 3)) + (v << 11);
      v = v ^ (v >> 16);
      return static_cast<size_t>(v);
    }
    case 8: {
      switch (sizeof(size_t)) {
        case 4: {
          // "64 bit to 32 bit Hash Functions"
          v = ~v + (v << 18);  // v = (v << 18) - v - 1;
          v = v ^ (v >> 31);
          v = v * 21;  // v = (v + (v << 2)) + (v << 4);
          v = v ^ (v >> 11);
          v = v + (v << 6);
          v = v ^ (v >> 22);
          return static_cast<size_t>(v);
        }
        case 8: {
          // "64 bit Mix Functions"
          v = ~v + (v << 21);  // v = (v << 21) - v - 1;
          v = v ^ (v >> 24);
          v = (v + (v << 3)) + (v << 8);  // v * 265
          v = v ^ (v >> 14);
          v = (v + (v << 2)) + (v << 4);  // v * 21
          v = v ^ (v >> 28);
          v = v + (v << 31);
          return static_cast<size_t>(v);
        }
      }
    }
62
  }
63
  UNREACHABLE();
64 65 66 67 68 69 70 71
}

}  // namespace


// This code was taken from MurmurHash.
size_t hash_combine(size_t seed, size_t value) {
#if V8_HOST_ARCH_32_BIT
72 73
  const uint32_t c1 = 0xCC9E2D51;
  const uint32_t c2 = 0x1B873593;
74 75 76 77 78 79 80

  value *= c1;
  value = bits::RotateRight32(value, 15);
  value *= c2;

  seed ^= value;
  seed = bits::RotateRight32(seed, 13);
81
  seed = seed * 5 + 0xE6546B64;
82
#else
83
  const uint64_t m = uint64_t{0xC6A4A7935BD1E995};
84 85 86 87 88 89 90 91 92 93 94 95 96
  const uint32_t r = 47;

  value *= m;
  value ^= value >> r;
  value *= m;

  seed ^= value;
  seed *= m;
#endif  // V8_HOST_ARCH_32_BIT
  return seed;
}


97
size_t hash_value(unsigned int v) { return hash_value_unsigned(v); }
98 99


100 101 102 103 104 105 106 107 108 109 110
size_t hash_value(unsigned long v) {  // NOLINT(runtime/int)
  return hash_value_unsigned(v);
}


size_t hash_value(unsigned long long v) {  // NOLINT(runtime/int)
  return hash_value_unsigned(v);
}

}  // namespace base
}  // namespace v8