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 176403467 : 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 2626581775 : running_hash += c;
32 2626581775 : running_hash += (running_hash << 10);
33 2626581775 : running_hash ^= (running_hash >> 6);
34 : return running_hash;
35 : }
36 :
37 : uint32_t StringHasher::GetHashCore(uint32_t running_hash) {
38 209585201 : running_hash += (running_hash << 3);
39 209585201 : running_hash ^= (running_hash >> 11);
40 209585201 : running_hash += (running_hash << 15);
41 209585201 : int32_t hash = static_cast<int32_t>(running_hash & String::kHashBitMask);
42 209585201 : int32_t mask = (hash - 1) >> 31;
43 209585201 : 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 172796542 : const Char* end = &chars[length];
52 2366679146 : while (chars != end) {
53 2193882604 : 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 318055870 : raw_running_hash_ = AddCharacterCore(raw_running_hash_, c);
62 : }
63 :
64 81604535 : bool StringHasher::UpdateIndex(uint16_t c) {
65 : DCHECK(is_array_index_);
66 81604535 : if (!TryAddIndexChar(&array_index_, c)) {
67 62937695 : is_array_index_ = false;
68 62937695 : return false;
69 : }
70 18666840 : is_array_index_ = array_index_ != 0 || length_ == 1;
71 18666840 : return is_array_index_;
72 : }
73 :
74 : template <typename Char>
75 81417137 : inline void StringHasher::AddCharacters(const Char* chars, int length) {
76 : DCHECK(sizeof(Char) == 1 || sizeof(Char) == 2);
77 : int i = 0;
78 81417137 : if (is_array_index_) {
79 86466533 : for (; i < length; i++) {
80 68097307 : AddCharacter(chars[i]);
81 68097307 : if (!UpdateIndex(chars[i])) {
82 49934900 : i++;
83 49934900 : break;
84 : }
85 : }
86 : }
87 81417141 : raw_running_hash_ =
88 81417141 : ComputeRunningHash(raw_running_hash_, &chars[i], length - i);
89 81417141 : }
90 :
91 : template <typename schar>
92 95353192 : 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 95353192 : if (IsInRange(length, 1, String::kMaxArrayIndexSize)) {
104 142929738 : if (IsDecimalDigit(chars[0]) && (length == 1 || chars[0] != '0')) {
105 4015372 : uint32_t index = chars[0] - '0';
106 : int i = 1;
107 10025852 : do {
108 13999369 : if (i == length) {
109 3972969 : uint32_t result = MakeArrayIndexHash(index, length);
110 : DCHECK_EQ(expected, result);
111 : return result;
112 : }
113 10025852 : } while (TryAddIndexChar(&index, chars[i++]));
114 : }
115 23888323 : } 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 91379401 : ComputeRunningHash(static_cast<uint32_t>(seed), chars, length);
126 :
127 : uint32_t result =
128 91379401 : (GetHashCore(hash) << String::kHashShift) | String::kIsNotArrayIndexMask;
129 : DCHECK_EQ(result, expected);
130 91379401 : return result;
131 : }
132 :
133 : IteratingStringHasher::IteratingStringHasher(int len, uint64_t seed)
134 : : StringHasher(len, seed) {}
135 :
136 81450181 : uint32_t IteratingStringHasher::Hash(String string, uint64_t seed) {
137 : IteratingStringHasher hasher(string->length(), seed);
138 : // Nothing to do.
139 81450181 : if (hasher.has_trivial_hash()) return hasher.GetHashField();
140 81382589 : ConsString cons_string = String::VisitFlat(&hasher, string);
141 81382697 : if (cons_string.is_null()) return hasher.GetHashField();
142 110088 : hasher.VisitConsString(cons_string);
143 110088 : return hasher.GetHashField();
144 : }
145 :
146 : void IteratingStringHasher::VisitOneByteString(const uint8_t* chars,
147 : int length) {
148 79321132 : AddCharacters(chars, length);
149 : }
150 :
151 : void IteratingStringHasher::VisitTwoByteString(const uint16_t* chars,
152 : int length) {
153 2051201 : 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_
|
