• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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_STRINGS_STRING_HASHER_INL_H_
6 #define V8_STRINGS_STRING_HASHER_INL_H_
7 
8 #include "src/strings/string-hasher.h"
9 
10 // Comment inserted to prevent header reordering.
11 #include <type_traits>
12 
13 #include "src/objects/name-inl.h"
14 #include "src/objects/objects.h"
15 #include "src/objects/string.h"
16 #include "src/strings/char-predicates-inl.h"
17 #include "src/utils/utils-inl.h"
18 
19 namespace v8 {
20 namespace internal {
21 
AddCharacterCore(uint32_t running_hash,uint16_t c)22 uint32_t StringHasher::AddCharacterCore(uint32_t running_hash, uint16_t c) {
23   running_hash += c;
24   running_hash += (running_hash << 10);
25   running_hash ^= (running_hash >> 6);
26   return running_hash;
27 }
28 
GetHashCore(uint32_t running_hash)29 uint32_t StringHasher::GetHashCore(uint32_t running_hash) {
30   running_hash += (running_hash << 3);
31   running_hash ^= (running_hash >> 11);
32   running_hash += (running_hash << 15);
33   int32_t hash = static_cast<int32_t>(running_hash & String::HashBits::kMax);
34   // Ensure that the hash is kZeroHash, if the computed value is 0.
35   int32_t mask = (hash - 1) >> 31;
36   running_hash |= (kZeroHash & mask);
37   return running_hash;
38 }
39 
GetTrivialHash(int length)40 uint32_t StringHasher::GetTrivialHash(int length) {
41   DCHECK_GT(length, String::kMaxHashCalcLength);
42   // The hash of a large string is simply computed from the length.
43   // Ensure that the max length is small enough to be encoded without losing
44   // information.
45   STATIC_ASSERT(String::kMaxLength <= String::HashBits::kMax);
46   uint32_t hash = static_cast<uint32_t>(length);
47   return String::CreateHashFieldValue(hash, String::HashFieldType::kHash);
48 }
49 
50 template <typename char_t>
HashSequentialString(const char_t * chars_raw,int length,uint64_t seed)51 uint32_t StringHasher::HashSequentialString(const char_t* chars_raw, int length,
52                                             uint64_t seed) {
53   STATIC_ASSERT(std::is_integral<char_t>::value);
54   STATIC_ASSERT(sizeof(char_t) <= 2);
55   using uchar = typename std::make_unsigned<char_t>::type;
56   const uchar* chars = reinterpret_cast<const uchar*>(chars_raw);
57   DCHECK_LE(0, length);
58   DCHECK_IMPLIES(0 < length, chars != nullptr);
59   if (length >= 1) {
60     if (IsDecimalDigit(chars[0]) && (length == 1 || chars[0] != '0')) {
61       if (length <= String::kMaxArrayIndexSize) {
62         // Possible array index; try to compute the array index hash.
63         uint32_t index = chars[0] - '0';
64         int i = 1;
65         do {
66           if (i == length) {
67             return MakeArrayIndexHash(index, length);
68           }
69         } while (TryAddArrayIndexChar(&index, chars[i++]));
70       }
71       // The following block wouldn't do anything on 32-bit platforms,
72       // because kMaxArrayIndexSize == kMaxIntegerIndexSize there, and
73       // if we wanted to compile it everywhere, then {index_big} would
74       // have to be a {size_t}, which the Mac compiler doesn't like to
75       // implicitly cast to uint64_t for the {TryAddIndexChar} call.
76 #if V8_HOST_ARCH_64_BIT
77       // No "else" here: if the block above was entered and fell through,
78       // we'll have to take this branch.
79       if (length <= String::kMaxIntegerIndexSize) {
80         // Not an array index, but it could still be an integer index.
81         // Perform a regular hash computation, and additionally check
82         // if there are non-digit characters.
83         String::HashFieldType type = String::HashFieldType::kIntegerIndex;
84         uint32_t running_hash = static_cast<uint32_t>(seed);
85         uint64_t index_big = 0;
86         const uchar* end = &chars[length];
87         while (chars != end) {
88           if (type == String::HashFieldType::kIntegerIndex &&
89               !TryAddIntegerIndexChar(&index_big, *chars)) {
90             type = String::HashFieldType::kHash;
91           }
92           running_hash = AddCharacterCore(running_hash, *chars++);
93         }
94         uint32_t hash =
95             String::CreateHashFieldValue(GetHashCore(running_hash), type);
96         if (Name::ContainsCachedArrayIndex(hash)) {
97           // The hash accidentally looks like a cached index. Fix that by
98           // setting a bit that looks like a longer-than-cacheable string
99           // length.
100           hash |= (String::kMaxCachedArrayIndexLength + 1)
101                   << String::ArrayIndexLengthBits::kShift;
102         }
103         DCHECK(!Name::ContainsCachedArrayIndex(hash));
104         return hash;
105       }
106 #endif
107     }
108     // No "else" here: if the first character was a decimal digit, we might
109     // still have to take this branch.
110     if (length > String::kMaxHashCalcLength) {
111       return GetTrivialHash(length);
112     }
113   }
114 
115   // Non-index hash.
116   uint32_t running_hash = static_cast<uint32_t>(seed);
117   const uchar* end = &chars[length];
118   while (chars != end) {
119     running_hash = AddCharacterCore(running_hash, *chars++);
120   }
121 
122   return String::CreateHashFieldValue(GetHashCore(running_hash),
123                                       String::HashFieldType::kHash);
124 }
125 
operator()126 std::size_t SeededStringHasher::operator()(const char* name) const {
127   return StringHasher::HashSequentialString(
128       name, static_cast<int>(strlen(name)), hashseed_);
129 }
130 
131 }  // namespace internal
132 }  // namespace v8
133 
134 #endif  // V8_STRINGS_STRING_HASHER_INL_H_
135