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