Line data Source code
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_STRING_HASHER_INL_H_
6 : #define V8_STRING_HASHER_INL_H_
7 :
8 : #include "src/string-hasher.h"
9 :
10 : #include "src/char-predicates-inl.h"
11 : #include "src/objects.h"
12 : #include "src/objects/string-inl.h"
13 : #include "src/utils-inl.h"
14 :
15 : namespace v8 {
16 : namespace internal {
17 :
18 : StringHasher::StringHasher(int length, uint64_t seed)
19 : : length_(length),
20 : raw_running_hash_(static_cast<uint32_t>(seed)),
21 : array_index_(0),
22 152516649 : is_array_index_(IsInRange(length, 1, String::kMaxArrayIndexSize)) {
23 : DCHECK(FLAG_randomize_hashes || raw_running_hash_ == 0);
24 : }
25 :
26 : bool StringHasher::has_trivial_hash() {
27 : return length_ > String::kMaxHashCalcLength;
28 : }
29 :
30 : uint32_t StringHasher::AddCharacterCore(uint32_t running_hash, uint16_t c) {
31 2604252729 : running_hash += c;
32 2604252729 : running_hash += (running_hash << 10);
33 2604252729 : running_hash ^= (running_hash >> 6);
34 : return running_hash;
35 : }
36 :
37 : uint32_t StringHasher::GetHashCore(uint32_t running_hash) {
38 202108235 : running_hash += (running_hash << 3);
39 202108235 : running_hash ^= (running_hash >> 11);
40 202108235 : running_hash += (running_hash << 15);
41 202108235 : int32_t hash = static_cast<int32_t>(running_hash & String::kHashBitMask);
42 202108235 : int32_t mask = (hash - 1) >> 31;
43 202108235 : return running_hash | (kZeroHash & mask);
44 : }
45 :
46 : template <typename Char>
47 : uint32_t StringHasher::ComputeRunningHash(uint32_t running_hash,
48 : const Char* chars, int length) {
49 : DCHECK_LE(0, length);
50 : DCHECK_IMPLIES(0 < length, chars != nullptr);
51 166472548 : const Char* end = &chars[length];
52 2368752741 : while (chars != end) {
53 2202280193 : running_hash = AddCharacterCore(running_hash, *chars++);
54 : }
55 : return running_hash;
56 : }
57 :
58 : void StringHasher::AddCharacter(uint16_t c) {
59 : // Use the Jenkins one-at-a-time hash function to update the hash
60 : // for the given character.
61 256358664 : raw_running_hash_ = AddCharacterCore(raw_running_hash_, c);
62 : }
63 :
64 54516795 : bool StringHasher::UpdateIndex(uint16_t c) {
65 : DCHECK(is_array_index_);
66 54516795 : if (!TryAddIndexChar(&array_index_, c)) {
67 51169020 : is_array_index_ = false;
68 51169020 : return false;
69 : }
70 3347775 : is_array_index_ = array_index_ != 0 || length_ == 1;
71 3347775 : return is_array_index_;
72 : }
73 :
74 : template <typename Char>
75 69766517 : inline void StringHasher::AddCharacters(const Char* chars, int length) {
76 : DCHECK(sizeof(Char) == 1 || sizeof(Char) == 2);
77 : int i = 0;
78 69766517 : if (is_array_index_) {
79 3334765 : for (; i < length; i++) {
80 41565316 : AddCharacter(chars[i]);
81 41565316 : if (!UpdateIndex(chars[i])) {
82 38230540 : i++;
83 38230540 : break;
84 : }
85 : }
86 : }
87 69766506 : raw_running_hash_ =
88 69766506 : ComputeRunningHash(raw_running_hash_, &chars[i], length - i);
89 69766506 : }
90 :
91 : template <typename schar>
92 101339976 : uint32_t StringHasher::HashSequentialString(const schar* chars, int length,
93 : uint64_t seed) {
94 : #ifdef DEBUG
95 : StringHasher hasher(length, seed);
96 : if (!hasher.has_trivial_hash()) hasher.AddCharacters(chars, length);
97 : uint32_t expected = hasher.GetHashField();
98 : #endif
99 :
100 : // Check whether the string is a valid array index. In that case, compute the
101 : // array index hash. It'll fall through to compute a regular string hash from
102 : // the start if it turns out that the string isn't a valid array index.
103 101339976 : if (IsInRange(length, 1, String::kMaxArrayIndexSize)) {
104 153141562 : if (IsDecimalDigit(chars[0]) && (length == 1 || chars[0] != '0')) {
105 4675494 : uint32_t index = chars[0] - '0';
106 : int i = 1;
107 12554509 : do {
108 17188319 : if (i == length) {
109 4633262 : uint32_t result = MakeArrayIndexHash(index, length);
110 : DCHECK_EQ(expected, result);
111 : return result;
112 : }
113 12554509 : } while (TryAddIndexChar(&index, chars[i++]));
114 : }
115 24769195 : } else if (length > String::kMaxHashCalcLength) {
116 : // String hash of a large string is simply the length.
117 : uint32_t result =
118 124 : (length << String::kHashShift) | String::kIsNotArrayIndexMask;
119 : DCHECK_EQ(result, expected);
120 124 : return result;
121 : }
122 :
123 : // Non-array-index hash.
124 : uint32_t hash =
125 96706042 : ComputeRunningHash(static_cast<uint32_t>(seed), chars, length);
126 :
127 : uint32_t result =
128 96706042 : (GetHashCore(hash) << String::kHashShift) | String::kIsNotArrayIndexMask;
129 : DCHECK_EQ(result, expected);
130 96706042 : return result;
131 : }
132 :
133 : IteratingStringHasher::IteratingStringHasher(int len, uint64_t seed)
134 : : StringHasher(len, seed) {}
135 :
136 69784676 : uint32_t IteratingStringHasher::Hash(String string, uint64_t seed) {
137 : IteratingStringHasher hasher(string->length(), seed);
138 : // Nothing to do.
139 69784676 : if (hasher.has_trivial_hash()) return hasher.GetHashField();
140 69718407 : ConsString cons_string = String::VisitFlat(&hasher, string);
141 69718515 : if (cons_string.is_null()) return hasher.GetHashField();
142 123681 : hasher.VisitConsString(cons_string);
143 123681 : return hasher.GetHashField();
144 : }
145 :
146 : void IteratingStringHasher::VisitOneByteString(const uint8_t* chars,
147 : int length) {
148 67670478 : AddCharacters(chars, length);
149 : }
150 :
151 : void IteratingStringHasher::VisitTwoByteString(const uint16_t* chars,
152 : int length) {
153 2051138 : AddCharacters(chars, length);
154 : }
155 :
156 : std::size_t SeededStringHasher::operator()(const char* name) const {
157 : return StringHasher::HashSequentialString(
158 : name, static_cast<int>(strlen(name)), hashseed_);
159 : }
160 :
161 : } // namespace internal
162 : } // namespace v8
163 :
164 : #endif // V8_STRING_HASHER_INL_H_
|
