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 173261622 : 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 2600977624 : running_hash += c;
32 2600977624 : running_hash += (running_hash << 10);
33 2600977624 : running_hash ^= (running_hash >> 6);
34 : return running_hash;
35 : }
36 :
37 : uint32_t StringHasher::GetHashCore(uint32_t running_hash) {
38 207159171 : running_hash += (running_hash << 3);
39 207159171 : running_hash ^= (running_hash >> 11);
40 207159171 : running_hash += (running_hash << 15);
41 207159171 : int32_t hash = static_cast<int32_t>(running_hash & String::kHashBitMask);
42 207159171 : int32_t mask = (hash - 1) >> 31;
43 207159171 : 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 170385857 : const Char* end = &chars[length];
52 2340861888 : while (chars != end) {
53 2170476031 : 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 313313414 : raw_running_hash_ = AddCharacterCore(raw_running_hash_, c);
62 : }
63 :
64 79544734 : bool StringHasher::UpdateIndex(uint16_t c) {
65 : DCHECK(is_array_index_);
66 79544734 : if (!TryAddIndexChar(&array_index_, c)) {
67 61821109 : is_array_index_ = false;
68 61821109 : return false;
69 : }
70 17723625 : is_array_index_ = array_index_ != 0 || length_ == 1;
71 17723625 : return is_array_index_;
72 : }
73 :
74 : template <typename Char>
75 79866138 : inline void StringHasher::AddCharacters(const Char* chars, int length) {
76 : DCHECK(sizeof(Char) == 1 || sizeof(Char) == 2);
77 : int i = 0;
78 79866138 : if (is_array_index_) {
79 83499281 : for (; i < length; i++) {
80 66076657 : AddCharacter(chars[i]);
81 66076657 : if (!UpdateIndex(chars[i])) {
82 48858294 : i++;
83 48858294 : break;
84 : }
85 : }
86 : }
87 79866129 : raw_running_hash_ =
88 79866129 : ComputeRunningHash(raw_running_hash_, &chars[i], length - i);
89 79866129 : }
90 :
91 : template <typename schar>
92 94488686 : 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 94488686 : if (IsInRange(length, 1, String::kMaxArrayIndexSize)) {
104 141907184 : if (IsDecimalDigit(chars[0]) && (length == 1 || chars[0] != '0')) {
105 4010423 : uint32_t index = chars[0] - '0';
106 : int i = 1;
107 10024190 : do {
108 13992874 : if (i == length) {
109 3968136 : uint32_t result = MakeArrayIndexHash(index, length);
110 : DCHECK_EQ(expected, result);
111 : return result;
112 : }
113 10024190 : } while (TryAddIndexChar(&index, chars[i++]));
114 : }
115 23535094 : } else if (length > String::kMaxHashCalcLength) {
116 : // String hash of a large string is simply the length.
117 : uint32_t result =
118 274 : (length << String::kHashShift) | String::kIsNotArrayIndexMask;
119 : DCHECK_EQ(result, expected);
120 274 : return result;
121 : }
122 :
123 : // Non-array-index hash.
124 : uint32_t hash =
125 90519728 : ComputeRunningHash(static_cast<uint32_t>(seed), chars, length);
126 :
127 : uint32_t result =
128 90519728 : (GetHashCore(hash) << String::kHashShift) | String::kIsNotArrayIndexMask;
129 : DCHECK_EQ(result, expected);
130 90519728 : return result;
131 : }
132 :
133 : IteratingStringHasher::IteratingStringHasher(int len, uint64_t seed)
134 : : StringHasher(len, seed) {}
135 :
136 79898755 : uint32_t IteratingStringHasher::Hash(String string, uint64_t seed) {
137 : IteratingStringHasher hasher(string->length(), seed);
138 : // Nothing to do.
139 79898755 : if (hasher.has_trivial_hash()) return hasher.GetHashField();
140 79831811 : ConsString cons_string = String::VisitFlat(&hasher, string);
141 79831786 : if (cons_string.is_null()) return hasher.GetHashField();
142 110005 : hasher.VisitConsString(cons_string);
143 110005 : return hasher.GetHashField();
144 : }
145 :
146 : void IteratingStringHasher::VisitOneByteString(const uint8_t* chars,
147 : int length) {
148 77770243 : AddCharacters(chars, length);
149 : }
150 :
151 : void IteratingStringHasher::VisitTwoByteString(const uint16_t* chars,
152 : int length) {
153 2051156 : 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_
|
