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