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
15namespace v8 {
16namespace internal {
17
18StringHasher::StringHasher(int length, uint64_t seed)
19 : length_(length),
20 raw_running_hash_(static_cast<uint32_t>(seed)),
21 array_index_(0),
22 is_array_index_(IsInRange(length, 1, String::kMaxArrayIndexSize)) {
23 DCHECK(FLAG_randomize_hashes || raw_running_hash_ == 0);
24}
25
26bool StringHasher::has_trivial_hash() {
27 return length_ > String::kMaxHashCalcLength;
28}
29
30uint32_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
37uint32_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 int32_t hash = static_cast<int32_t>(running_hash & String::kHashBitMask);
42 int32_t mask = (hash - 1) >> 31;
43 return running_hash | (kZeroHash & mask);
44}
45
46template <typename Char>
47uint32_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 const Char* end = &chars[length];
52 while (chars != end) {
53 running_hash = AddCharacterCore(running_hash, *chars++);
54 }
55 return running_hash;
56}
57
58void 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 raw_running_hash_ = AddCharacterCore(raw_running_hash_, c);
62}
63
64bool StringHasher::UpdateIndex(uint16_t c) {
65 DCHECK(is_array_index_);
66 if (!TryAddIndexChar(&array_index_, c)) {
67 is_array_index_ = false;
68 return false;
69 }
70 is_array_index_ = array_index_ != 0 || length_ == 1;
71 return is_array_index_;
72}
73
74template <typename Char>
75inline void StringHasher::AddCharacters(const Char* chars, int length) {
76 DCHECK(sizeof(Char) == 1 || sizeof(Char) == 2);
77 int i = 0;
78 if (is_array_index_) {
79 for (; i < length; i++) {
80 AddCharacter(chars[i]);
81 if (!UpdateIndex(chars[i])) {
82 i++;
83 break;
84 }
85 }
86 }
87 raw_running_hash_ =
88 ComputeRunningHash(raw_running_hash_, &chars[i], length - i);
89}
90
91template <typename schar>
92uint32_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 if (IsInRange(length, 1, String::kMaxArrayIndexSize)) {
104 if (IsDecimalDigit(chars[0]) && (length == 1 || chars[0] != '0')) {
105 uint32_t index = chars[0] - '0';
106 int i = 1;
107 do {
108 if (i == length) {
109 uint32_t result = MakeArrayIndexHash(index, length);
110 DCHECK_EQ(expected, result);
111 return result;
112 }
113 } while (TryAddIndexChar(&index, chars[i++]));
114 }
115 } else if (length > String::kMaxHashCalcLength) {
116 // String hash of a large string is simply the length.
117 uint32_t result =
118 (length << String::kHashShift) | String::kIsNotArrayIndexMask;
119 DCHECK_EQ(result, expected);
120 return result;
121 }
122
123 // Non-array-index hash.
124 uint32_t hash =
125 ComputeRunningHash(static_cast<uint32_t>(seed), chars, length);
126
127 uint32_t result =
128 (GetHashCore(hash) << String::kHashShift) | String::kIsNotArrayIndexMask;
129 DCHECK_EQ(result, expected);
130 return result;
131}
132
133IteratingStringHasher::IteratingStringHasher(int len, uint64_t seed)
134 : StringHasher(len, seed) {}
135
136uint32_t IteratingStringHasher::Hash(String string, uint64_t seed) {
137 IteratingStringHasher hasher(string->length(), seed);
138 // Nothing to do.
139 if (hasher.has_trivial_hash()) return hasher.GetHashField();
140 ConsString cons_string = String::VisitFlat(&hasher, string);
141 if (cons_string.is_null()) return hasher.GetHashField();
142 hasher.VisitConsString(cons_string);
143 return hasher.GetHashField();
144}
145
146void IteratingStringHasher::VisitOneByteString(const uint8_t* chars,
147 int length) {
148 AddCharacters(chars, length);
149}
150
151void IteratingStringHasher::VisitTwoByteString(const uint16_t* chars,
152 int length) {
153 AddCharacters(chars, length);
154}
155
156std::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_
165