1// Copyright 2017 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#ifndef V8_STRINGS_STRING_HASHER_INL_H_
6#define V8_STRINGS_STRING_HASHER_INL_H_
7
8#include "src/strings/string-hasher.h"
9
10// Comment inserted to prevent header reordering.
11#include <type_traits>
12
13#include "src/objects/name-inl.h"
14#include "src/objects/objects.h"
15#include "src/objects/string.h"
16#include "src/strings/char-predicates-inl.h"
17#include "src/utils/utils-inl.h"
18
19namespace v8 {
20namespace internal {
21
22uint32_t StringHasher::AddCharacterCore(uint32_t running_hash, uint16_t c) {
23  running_hash += c;
24  running_hash += (running_hash << 10);
25  running_hash ^= (running_hash >> 6);
26  return running_hash;
27}
28
29uint32_t StringHasher::GetHashCore(uint32_t running_hash) {
30  running_hash += (running_hash << 3);
31  running_hash ^= (running_hash >> 11);
32  running_hash += (running_hash << 15);
33  int32_t hash = static_cast<int32_t>(running_hash & String::HashBits::kMax);
34  // Ensure that the hash is kZeroHash, if the computed value is 0.
35  int32_t mask = (hash - 1) >> 31;
36  running_hash |= (kZeroHash & mask);
37  return running_hash;
38}
39
40uint32_t StringHasher::GetTrivialHash(int length) {
41  DCHECK_GT(length, String::kMaxHashCalcLength);
42  // The hash of a large string is simply computed from the length.
43  // Ensure that the max length is small enough to be encoded without losing
44  // information.
45  STATIC_ASSERT(String::kMaxLength <= String::HashBits::kMax);
46  uint32_t hash = static_cast<uint32_t>(length);
47  return String::CreateHashFieldValue(hash, String::HashFieldType::kHash);
48}
49
50template <typename char_t>
51uint32_t StringHasher::HashSequentialString(const char_t* chars_raw, int length,
52                                            uint64_t seed) {
53  STATIC_ASSERT(std::is_integral<char_t>::value);
54  STATIC_ASSERT(sizeof(char_t) <= 2);
55  using uchar = typename std::make_unsigned<char_t>::type;
56  const uchar* chars = reinterpret_cast<const uchar*>(chars_raw);
57  DCHECK_LE(0, length);
58  DCHECK_IMPLIES(0 < length, chars != nullptr);
59  if (length >= 1) {
60    if (IsDecimalDigit(chars[0]) && (length == 1 || chars[0] != '0')) {
61      if (length <= String::kMaxArrayIndexSize) {
62        // Possible array index; try to compute the array index hash.
63        uint32_t index = chars[0] - '0';
64        int i = 1;
65        do {
66          if (i == length) {
67            return MakeArrayIndexHash(index, length);
68          }
69        } while (TryAddArrayIndexChar(&index, chars[i++]));
70      }
71      // The following block wouldn't do anything on 32-bit platforms,
72      // because kMaxArrayIndexSize == kMaxIntegerIndexSize there, and
73      // if we wanted to compile it everywhere, then {index_big} would
74      // have to be a {size_t}, which the Mac compiler doesn't like to
75      // implicitly cast to uint64_t for the {TryAddIndexChar} call.
76#if V8_HOST_ARCH_64_BIT
77      // No "else" here: if the block above was entered and fell through,
78      // we'll have to take this branch.
79      if (length <= String::kMaxIntegerIndexSize) {
80        // Not an array index, but it could still be an integer index.
81        // Perform a regular hash computation, and additionally check
82        // if there are non-digit characters.
83        String::HashFieldType type = String::HashFieldType::kIntegerIndex;
84        uint32_t running_hash = static_cast<uint32_t>(seed);
85        uint64_t index_big = 0;
86        const uchar* end = &chars[length];
87        while (chars != end) {
88          if (type == String::HashFieldType::kIntegerIndex &&
89              !TryAddIntegerIndexChar(&index_big, *chars)) {
90            type = String::HashFieldType::kHash;
91          }
92          running_hash = AddCharacterCore(running_hash, *chars++);
93        }
94        uint32_t hash =
95            String::CreateHashFieldValue(GetHashCore(running_hash), type);
96        if (Name::ContainsCachedArrayIndex(hash)) {
97          // The hash accidentally looks like a cached index. Fix that by
98          // setting a bit that looks like a longer-than-cacheable string
99          // length.
100          hash |= (String::kMaxCachedArrayIndexLength + 1)
101                  << String::ArrayIndexLengthBits::kShift;
102        }
103        DCHECK(!Name::ContainsCachedArrayIndex(hash));
104        return hash;
105      }
106#endif
107    }
108    // No "else" here: if the first character was a decimal digit, we might
109    // still have to take this branch.
110    if (length > String::kMaxHashCalcLength) {
111      return GetTrivialHash(length);
112    }
113  }
114
115  // Non-index hash.
116  uint32_t running_hash = static_cast<uint32_t>(seed);
117  const uchar* end = &chars[length];
118  while (chars != end) {
119    running_hash = AddCharacterCore(running_hash, *chars++);
120  }
121
122  return String::CreateHashFieldValue(GetHashCore(running_hash),
123                                      String::HashFieldType::kHash);
124}
125
126std::size_t SeededStringHasher::operator()(const char* name) const {
127  return StringHasher::HashSequentialString(
128      name, static_cast<int>(strlen(name)), hashseed_);
129}
130
131}  // namespace internal
132}  // namespace v8
133
134#endif  // V8_STRINGS_STRING_HASHER_INL_H_
135