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/char-predicates-inl.h"
9 : #include "src/objects.h"
10 : #include "src/string-hasher.h"
11 :
12 : namespace v8 {
13 : namespace internal {
14 :
15 : StringHasher::StringHasher(int length, uint32_t seed)
16 : : length_(length),
17 : raw_running_hash_(seed),
18 : array_index_(0),
19 194151244 : is_array_index_(0 < length_ && length_ <= String::kMaxArrayIndexSize),
20 405090403 : is_first_char_(true) {
21 : DCHECK(FLAG_randomize_hashes || raw_running_hash_ == 0);
22 : }
23 :
24 : bool StringHasher::has_trivial_hash() {
25 : return length_ > String::kMaxHashCalcLength;
26 : }
27 :
28 : uint32_t StringHasher::AddCharacterCore(uint32_t running_hash, uint16_t c) {
29 2442656346 : running_hash += c;
30 2442656346 : running_hash += (running_hash << 10);
31 2442656346 : running_hash ^= (running_hash >> 6);
32 : return running_hash;
33 : }
34 :
35 : uint32_t StringHasher::GetHashCore(uint32_t running_hash) {
36 217320001 : running_hash += (running_hash << 3);
37 217320001 : running_hash ^= (running_hash >> 11);
38 217320001 : running_hash += (running_hash << 15);
39 217320001 : if ((running_hash & String::kHashBitMask) == 0) {
40 : return kZeroHash;
41 : }
42 : return running_hash;
43 : }
44 :
45 : uint32_t StringHasher::ComputeRunningHash(uint32_t running_hash,
46 : const uc16* chars, int length) {
47 : DCHECK_NOT_NULL(chars);
48 : DCHECK_GE(length, 0);
49 125 : for (int i = 0; i < length; ++i) {
50 125 : running_hash = AddCharacterCore(running_hash, *chars++);
51 : }
52 : return running_hash;
53 : }
54 :
55 : uint32_t StringHasher::ComputeRunningHashOneByte(uint32_t running_hash,
56 : const char* chars,
57 : int length) {
58 : DCHECK_NOT_NULL(chars);
59 : DCHECK_GE(length, 0);
60 69552 : for (int i = 0; i < length; ++i) {
61 69552 : uint16_t c = static_cast<uint16_t>(*chars++);
62 : running_hash = AddCharacterCore(running_hash, c);
63 : }
64 : return running_hash;
65 : }
66 :
67 : void StringHasher::AddCharacter(uint16_t c) {
68 : // Use the Jenkins one-at-a-time hash function to update the hash
69 : // for the given character.
70 4760177420 : raw_running_hash_ = AddCharacterCore(raw_running_hash_, c);
71 : }
72 :
73 157944461 : bool StringHasher::UpdateIndex(uint16_t c) {
74 : DCHECK(is_array_index_);
75 315888922 : if (!IsDecimalDigit(c)) {
76 144420430 : is_array_index_ = false;
77 144420430 : return false;
78 : }
79 : int d = c - '0';
80 13524031 : if (is_first_char_) {
81 4082025 : is_first_char_ = false;
82 4082025 : if (d == 0 && length_ > 1) {
83 12863 : is_array_index_ = false;
84 12863 : return false;
85 : }
86 : }
87 13511168 : if (array_index_ > 429496729U - ((d + 3) >> 3)) {
88 3000 : is_array_index_ = false;
89 3000 : return false;
90 : }
91 13508168 : array_index_ = array_index_ * 10 + d;
92 13508168 : return true;
93 : }
94 :
95 : template <typename Char>
96 201162690 : inline void StringHasher::AddCharacters(const Char* chars, int length) {
97 : DCHECK(sizeof(Char) == 1 || sizeof(Char) == 2);
98 : int i = 0;
99 201162690 : if (is_array_index_) {
100 13503218 : for (; i < length; i++) {
101 141153379 : AddCharacter(chars[i]);
102 141153379 : if (!UpdateIndex(chars[i])) {
103 127650165 : i++;
104 127650165 : break;
105 : }
106 : }
107 : }
108 1913998606 : for (; i < length; i++) {
109 : DCHECK(!is_array_index_);
110 1913998606 : AddCharacter(chars[i]);
111 : }
112 201162694 : }
113 :
114 : template <typename schar>
115 130302892 : uint32_t StringHasher::HashSequentialString(const schar* chars, int length,
116 : uint32_t seed) {
117 : StringHasher hasher(length, seed);
118 130302892 : if (!hasher.has_trivial_hash()) hasher.AddCharacters(chars, length);
119 130302945 : return hasher.GetHashField();
120 : }
121 :
122 : IteratingStringHasher::IteratingStringHasher(int len, uint32_t seed)
123 : : StringHasher(len, seed) {}
124 :
125 63848352 : uint32_t IteratingStringHasher::Hash(String* string, uint32_t seed) {
126 : IteratingStringHasher hasher(string->length(), seed);
127 : // Nothing to do.
128 63848352 : if (hasher.has_trivial_hash()) return hasher.GetHashField();
129 63803987 : ConsString* cons_string = String::VisitFlat(&hasher, string);
130 63804153 : if (cons_string == nullptr) return hasher.GetHashField();
131 1664856 : hasher.VisitConsString(cons_string);
132 1664856 : return hasher.GetHashField();
133 : }
134 :
135 : void IteratingStringHasher::VisitOneByteString(const uint8_t* chars,
136 : int length) {
137 68071599 : AddCharacters(chars, length);
138 : }
139 :
140 : void IteratingStringHasher::VisitTwoByteString(const uint16_t* chars,
141 : int length) {
142 2584113 : AddCharacters(chars, length);
143 : }
144 :
145 : } // namespace internal
146 : } // namespace v8
147 :
148 : #endif // V8_STRING_HASHER_INL_H_
|
