string-hasher-inl.h 4.85 KB
Newer Older
1 2 3 4
// Copyright 2017 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.

5 6
#ifndef V8_STRINGS_STRING_HASHER_INL_H_
#define V8_STRINGS_STRING_HASHER_INL_H_
7

8
#include "src/strings/string-hasher.h"
9

10 11
#include <type_traits>

12
#include "src/objects/objects.h"
13
#include "src/objects/string-inl.h"
14
#include "src/strings/char-predicates-inl.h"
15
#include "src/utils/utils-inl.h"
16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

namespace v8 {
namespace internal {

uint32_t StringHasher::AddCharacterCore(uint32_t running_hash, uint16_t c) {
  running_hash += c;
  running_hash += (running_hash << 10);
  running_hash ^= (running_hash >> 6);
  return running_hash;
}

uint32_t StringHasher::GetHashCore(uint32_t running_hash) {
  running_hash += (running_hash << 3);
  running_hash ^= (running_hash >> 11);
  running_hash += (running_hash << 15);
31 32 33
  int32_t hash = static_cast<int32_t>(running_hash & String::kHashBitMask);
  int32_t mask = (hash - 1) >> 31;
  return running_hash | (kZeroHash & mask);
34 35
}

36 37
uint32_t StringHasher::GetTrivialHash(int length) {
  DCHECK_GT(length, String::kMaxHashCalcLength);
38 39 40 41
  // The hash of a large string is simply computed from the length.
  // Ensure that the max length is small enough to be shifted without losing
  // information.
  STATIC_ASSERT(base::bits::CountLeadingZeros32(String::kMaxLength) >=
42
                String::kHashShift);
43 44
  uint32_t hash = static_cast<uint32_t>(length);
  return (hash << String::kHashShift) | String::kIsNotIntegerIndexMask;
45 46
}

47 48
template <typename char_t>
uint32_t StringHasher::HashSequentialString(const char_t* chars_raw, int length,
Yang Guo's avatar
Yang Guo committed
49
                                            uint64_t seed) {
50 51
  STATIC_ASSERT(std::is_integral<char_t>::value);
  STATIC_ASSERT(sizeof(char_t) <= 2);
52 53
  using uchar = typename std::make_unsigned<char_t>::type;
  const uchar* chars = reinterpret_cast<const uchar*>(chars_raw);
54 55 56
  DCHECK_LE(0, length);
  DCHECK_IMPLIES(0 < length, chars != nullptr);
  if (length >= 1) {
57
    if (IsDecimalDigit(chars[0]) && (length == 1 || chars[0] != '0')) {
58 59
      if (length <= String::kMaxArrayIndexSize) {
        // Possible array index; try to compute the array index hash.
60
        uint32_t index = chars[0] - '0';
61 62 63 64 65
        int i = 1;
        do {
          if (i == length) {
            return MakeArrayIndexHash(index, length);
          }
66
        } while (TryAddArrayIndexChar(&index, chars[i++]));
67 68 69 70 71 72 73 74 75 76 77 78 79 80 81
      }
      // The following block wouldn't do anything on 32-bit platforms,
      // because kMaxArrayIndexSize == kMaxIntegerIndexSize there, and
      // if we wanted to compile it everywhere, then {index_big} would
      // have to be a {size_t}, which the Mac compiler doesn't like to
      // implicitly cast to uint64_t for the {TryAddIndexChar} call.
#if V8_HOST_ARCH_64_BIT
      // No "else" here: if the block above was entered and fell through,
      // we'll have to take this branch.
      if (length <= String::kMaxIntegerIndexSize) {
        // Not an array index, but it could still be an integer index.
        // Perform a regular hash computation, and additionally check
        // if there are non-digit characters.
        uint32_t is_integer_index = 0;
        uint32_t running_hash = static_cast<uint32_t>(seed);
82
        uint64_t index_big = 0;
83
        const uchar* end = &chars[length];
84
        while (chars != end) {
85 86
          if (is_integer_index == 0 &&
              !TryAddIntegerIndexChar(&index_big, *chars)) {
87 88 89
            is_integer_index = String::kIsNotIntegerIndexMask;
          }
          running_hash = AddCharacterCore(running_hash, *chars++);
90
        }
91 92 93 94 95 96 97 98 99 100 101
        uint32_t hash = (GetHashCore(running_hash) << String::kHashShift) |
                        is_integer_index;
        if (Name::ContainsCachedArrayIndex(hash)) {
          // The hash accidentally looks like a cached index. Fix that by
          // setting a bit that looks like a longer-than-cacheable string
          // length.
          hash |= (String::kMaxCachedArrayIndexLength + 1)
                  << String::ArrayIndexLengthBits::kShift;
        }
        DCHECK(!Name::ContainsCachedArrayIndex(hash));
        return hash;
102 103 104 105 106 107 108
      }
#endif
    }
    // No "else" here: if the first character was a decimal digit, we might
    // still have to take this branch.
    if (length > String::kMaxHashCalcLength) {
      return GetTrivialHash(length);
109 110 111
    }
  }

112
  // Non-index hash.
113
  uint32_t running_hash = static_cast<uint32_t>(seed);
114
  const uchar* end = &chars[length];
115 116 117
  while (chars != end) {
    running_hash = AddCharacterCore(running_hash, *chars++);
  }
118

119
  return (GetHashCore(running_hash) << String::kHashShift) |
120
         String::kIsNotIntegerIndexMask;
121 122
}

123 124 125 126 127
std::size_t SeededStringHasher::operator()(const char* name) const {
  return StringHasher::HashSequentialString(
      name, static_cast<int>(strlen(name)), hashseed_);
}

128 129 130
}  // namespace internal
}  // namespace v8

131
#endif  // V8_STRINGS_STRING_HASHER_INL_H_