deps/v8/src/strings/string-hasher-inl.h - main - githubmirror/node

deps/v8/src/strings/string-hasher-inl.h
369 строк13 KB
Joyee Cheung
build,test: test array index hash collision
24 апр 2026, 19:01
24 апр 2026, 19:01fff9a8a
// Copyright 2017 the V8 project authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#ifndef V8_STRINGS_STRING_HASHER_INL_H_
#define V8_STRINGS_STRING_HASHER_INL_H_

#include "src/strings/string-hasher.h"
// Include the non-inl header before the rest of the headers.

// Comment inserted to prevent header reordering.
#include <type_traits>

#include "src/common/globals.h"
#include "src/objects/name-inl.h"
#include "src/objects/string-inl.h"
#include "src/strings/char-predicates-inl.h"
#include "src/utils/utils-inl.h"
#include "src/utils/utils.h"
#include "third_party/rapidhash-v8/rapidhash.h"

namespace v8 {
namespace internal {

namespace detail {
V8_EXPORT_PRIVATE uint64_t HashConvertingTo8Bit(const uint16_t* chars,
                                                uint32_t length, uint64_t seed,
                                                const uint64_t secret[3]);

template <typename T>
uint32_t ConvertRawHashToUsableHash(T raw_hash) {
  // Limit to the supported bits.
  const int32_t hash = static_cast<int32_t>(raw_hash & String::HashBits::kMax);
  // Ensure that the hash is kZeroHash, if the computed value is 0.
  return hash == 0 ? StringHasher::kZeroHash : hash;
}

V8_INLINE bool IsOnly8Bit(const uint16_t* chars, unsigned len) {
  // For small strings, use a simple scalar loop to avoid SIMD overhead.
  // Threshold of 16 is chosen to balance setup cost vs benefit.
  if (len <= 16) {
    for (unsigned i = 0; i < len; i++) {
      if (chars[i] > 0xFF) {
        return false;
      }
    }
    return true;
  }
  // For larger strings, use the non-inlined SIMD implementation.
  return IsOnly8BitSIMD(chars, len);
}

V8_INLINE uint64_t GetRapidHash(const uint8_t* chars, uint32_t length,
                                uint64_t seed, const uint64_t secret[3]) {
  return rapidhash(chars, length, seed, secret);
}

V8_INLINE uint64_t GetRapidHash(const uint16_t* chars, uint32_t length,
                                uint64_t seed, const uint64_t secret[3]) {
  // For 2-byte strings we need to preserve the same hash for strings in just
  // the latin-1 range.
  if (V8_UNLIKELY(IsOnly8Bit(chars, length))) {
    return detail::HashConvertingTo8Bit(chars, length, seed, secret);
  }
  return rapidhash(reinterpret_cast<const uint8_t*>(chars), 2 * length, seed,
                   secret);
}

template <typename uchar>
V8_INLINE uint32_t GetUsableRapidHash(const uchar* chars, uint32_t length,
                                      uint64_t seed, const uint64_t secret[3]) {
  return ConvertRawHashToUsableHash(GetRapidHash(chars, length, seed, secret));
}

}  // namespace detail

void RunningStringHasher::AddCharacter(uint16_t c) {
  running_hash_ += c;
  running_hash_ += (running_hash_ << 10);
  running_hash_ ^= (running_hash_ >> 6);
}

uint32_t RunningStringHasher::Finalize() {
  running_hash_ += (running_hash_ << 3);
  running_hash_ ^= (running_hash_ >> 11);
  running_hash_ += (running_hash_ << 15);
  return detail::ConvertRawHashToUsableHash(running_hash_);
}

uint32_t StringHasher::GetTrivialHash(uint32_t length) {
  DCHECK_GT(length, String::kMaxHashCalcLength);
  // The hash of a large string is simply computed from the length.
  // Ensure that the max length is small enough to be encoded without losing
  // information.
  static_assert(String::kMaxLength <= String::HashBits::kMax);
  uint32_t hash = length;
  return String::CreateHashFieldValue(hash, String::HashFieldType::kHash);
}

uint32_t StringHasher::MakeArrayIndexHash(uint32_t value, uint32_t length) {
  // For array indexes mix the length into the hash as an array index could
  // be zero.
  DCHECK_LE(length, String::kMaxArrayIndexSize);
  DCHECK(TenToThe(String::kMaxCachedArrayIndexLength) <
         (1 << String::kArrayIndexValueBits));

  value <<= String::ArrayIndexValueBits::kShift;
  value |= length << String::ArrayIndexLengthBits::kShift;

  DCHECK(String::IsIntegerIndex(value));
  DCHECK_EQ(length <= String::kMaxCachedArrayIndexLength,
            Name::ContainsCachedArrayIndex(value));
  return value;
}

uint32_t StringHasher::DecodeArrayIndexFromHashField(uint32_t raw_hash_field) {
  DCHECK(String::ContainsCachedArrayIndex(raw_hash_field) ||
         String::IsIntegerIndex(raw_hash_field));
  return String::ArrayIndexValueBits::decode(raw_hash_field);
}

#ifdef V8_ENABLE_SEEDED_ARRAY_INDEX_HASH
uint32_t StringHasher::SeedArrayIndexValue(uint32_t value,
                                           const HashSeed seed) {
  uint32_t m1 = seed.m1();
  uint32_t m2 = seed.m2();
  uint32_t m3 = seed.m3();
  constexpr uint32_t kShift = Name::kArrayIndexHashShift;
  constexpr uint32_t kMask = Name::kArrayIndexValueMask;
  // 3-round xorshift-multiply.
  uint32_t x = value;
  x ^= x >> kShift;
  x = (x * m1) & kMask;
  x ^= x >> kShift;
  x = (x * m2) & kMask;
  x ^= x >> kShift;
  x = (x * m3) & kMask;
  x ^= x >> kShift;
  return x;
}

uint32_t StringHasher::UnseedArrayIndexValue(uint32_t value,
                                             const HashSeed seed) {
  uint32_t m1_inv = seed.m1_inv();
  uint32_t m2_inv = seed.m2_inv();
  uint32_t m3_inv = seed.m3_inv();
  uint32_t x = value;
  constexpr uint32_t kShift = Name::kArrayIndexHashShift;
  constexpr uint32_t kMask = Name::kArrayIndexValueMask;
  // 3-round xorshift-multiply (inverse).
  // Xorshift is an involution when kShift is at least half of the value width.
  x ^= x >> kShift;
  x = (x * m3_inv) & kMask;
  x ^= x >> kShift;
  x = (x * m2_inv) & kMask;
  x ^= x >> kShift;
  x = (x * m1_inv) & kMask;
  x ^= x >> kShift;
  return x;
}
#endif  // V8_ENABLE_SEEDED_ARRAY_INDEX_HASH

uint32_t StringHasher::MakeArrayIndexHash(
    uint32_t value, uint32_t length, [[maybe_unused]] const HashSeed seed) {
#ifdef V8_ENABLE_SEEDED_ARRAY_INDEX_HASH
  value = SeedArrayIndexValue(value, seed);
#endif
  return MakeArrayIndexHash(value, length);
}

uint32_t StringHasher::DecodeArrayIndexFromHashField(
    uint32_t raw_hash_field, [[maybe_unused]] const HashSeed seed) {
  uint32_t value = DecodeArrayIndexFromHashField(raw_hash_field);
#ifdef V8_ENABLE_SEEDED_ARRAY_INDEX_HASH
  value = UnseedArrayIndexValue(value, seed);
#endif
  return value;
}

namespace detail {

enum IndexParseResult { kSuccess, kNonIndex, kOverflow };

// The array index type depends on the architecture, so that the multiplication
// in TryParseArrayIndex stays fast.
#if V8_HOST_ARCH_64_BIT
using ArrayIndexT = uint64_t;
#else
using ArrayIndexT = uint32_t;
#endif

template <typename uchar>
V8_INLINE IndexParseResult TryParseArrayIndex(const uchar* chars,
                                              uint32_t length, uint32_t& i,
                                              ArrayIndexT& index) {
  DCHECK_GT(length, 0);
  DCHECK_LE(length, String::kMaxIntegerIndexSize);

  // The leading character can only be a zero for the string "0"; otherwise this
  // isn't a valid index string.
  index = chars[0] - '0';
  i = 1;
  if (index > 9) return kNonIndex;
  if (index == 0) {
    if (length > 1) return kNonIndex;
    DCHECK_EQ(length, 1);
    return kSuccess;
  }

  if (length > String::kMaxArrayIndexSize) return kOverflow;

  // TODO(leszeks): Use SIMD for this loop.
  for (; i < length; i++) {
    uchar c = chars[i];
    uint32_t val = c - '0';
    if (val > 9) return kNonIndex;
    index = (10 * index) + val;
  }
  if constexpr (sizeof(index) == sizeof(uint64_t)) {
    // If we have a large type for index, we'll never overflow it, so we can
    // have a simple comparison for array index overflow.
    if (index > String::kMaxArrayIndex) {
      return kOverflow;
    }
  } else {
    DCHECK(sizeof(index) == sizeof(uint32_t));
    // If index is a 32-bit int, we have to get a bit creative with the overflow
    // check.
    if (V8_UNLIKELY(length == String::kMaxArrayIndexSize)) {
      // If length is String::kMaxArrayIndexSize, and we know there is no zero
      // prefix, the minimum valid value is 1 followed by length - 1 zeros. If
      // our value is smaller than this, then we overflowed.
      //
      // Additionally, String::kMaxArrayIndex is UInt32Max - 1, so we can fold
      // in a check that index < UInt32Max by adding 1 to both sides, making
      // index = UInt32Max overflows, and only then checking for overflow.
      constexpr uint32_t kMinValidValue =
          TenToThe(String::kMaxArrayIndexSize - 1);
      if (index + 1 < kMinValidValue + 1) {
        // We won't try an integer index if there is overflow, so just return
        // non-index.
        DCHECK(String::kMaxArrayIndexSize == String::kMaxIntegerIndexSize);
        return kNonIndex;
      }
    }
  }
  DCHECK_LT(index, TenToThe(length));
  DCHECK_GE(index, TenToThe(length - 1));
  return kSuccess;
}

// The following function wouldn't do anything on 32-bit platforms, because
// kMaxArrayIndexSize == kMaxIntegerIndexSize there.
#if V8_HOST_ARCH_64_BIT
template <typename uchar>
V8_INLINE IndexParseResult TryParseIntegerIndex(const uchar* chars,
                                                uint32_t length, uint32_t i,
                                                ArrayIndexT index) {
  DCHECK_GT(length, 0);
  DCHECK_LE(length, String::kMaxIntegerIndexSize);
  DCHECK_GT(i, 0);
  DCHECK_GT(index, 0);
  DCHECK_LT(index, kMaxSafeIntegerUint64);

  for (; i < length; i++) {
    // We should never be anywhere near overflowing, so we can just do
    // one range check at the end.
    static_assert(kMaxSafeIntegerUint64 < (kMaxUInt64 / 100));
    DCHECK_LT(index, kMaxUInt64 / 100);

    uchar c = chars[i];
    uint32_t val = c - '0';
    if (val > 9) return kNonIndex;
    index = (10 * index) + val;
  }
  if (index > kMaxSafeIntegerUint64) return kOverflow;

  return kSuccess;
}
#else
static_assert(String::kMaxArrayIndexSize == String::kMaxIntegerIndexSize);
#endif

}  // namespace detail

template <typename char_t>
uint32_t StringHasher::HashSequentialString(const char_t* chars_raw,
                                            uint32_t length,
                                            const HashSeed seed) {
  static_assert(std::is_integral_v<char_t>);
  static_assert(sizeof(char_t) <= 2);
  using uchar = std::make_unsigned_t<char_t>;
  const uchar* chars = reinterpret_cast<const uchar*>(chars_raw);
  DCHECK_IMPLIES(length > 0, chars != nullptr);
  if (length >= 1) {
    if (length <= String::kMaxIntegerIndexSize) {
      // Possible array or integer index; try to compute the array index hash.
      static_assert(String::kMaxArrayIndexSize <= String::kMaxIntegerIndexSize);

      detail::ArrayIndexT index;
      uint32_t i;
      switch (detail::TryParseArrayIndex(chars, length, i, index)) {
        case detail::kSuccess: {
          DCHECK_LE(index, String::kMaxArrayIndex);
          return StringHasher::MakeArrayIndexHash(static_cast<uint32_t>(index),
                                                  length, seed);
        }
        case detail::kNonIndex:
          // A non-index result from TryParseArrayIndex means we don't need to
          // check for integer indices.
          break;
        case detail::kOverflow: {
#if V8_HOST_ARCH_64_BIT
          // On 64-bit, we might have a valid integer index even if the value
          // overflowed an array index.
          static_assert(String::kMaxArrayIndexSize <
                        String::kMaxIntegerIndexSize);
          switch (detail::TryParseIntegerIndex(chars, length, i, index)) {
            case detail::kSuccess: {
              uint32_t hash = String::CreateHashFieldValue(
                  detail::GetUsableRapidHash(chars, length, seed.seed(),
                                             seed.secret()),
                  String::HashFieldType::kIntegerIndex);
              if (Name::ContainsCachedArrayIndex(hash)) {
                // The hash accidentally looks like a cached index. Fix that by
                // setting a bit that looks like a longer-than-cacheable string
                // length.
                hash |= (String::kMaxCachedArrayIndexLength + 1)
                        << String::ArrayIndexLengthBits::kShift;
              }
              DCHECK(!Name::ContainsCachedArrayIndex(hash));
              return hash;
            }
            case detail::kNonIndex:
            case detail::kOverflow:
              break;
          }
#else
          static_assert(String::kMaxArrayIndexSize ==
                        String::kMaxIntegerIndexSize);
#endif
          break;
        }
      }
      // If the we failed to compute an index hash, this falls through into the
      // non-index hash case.
    } else if (length > String::kMaxHashCalcLength) {
      // We should never go down this path if we might have an index value.
      static_assert(String::kMaxHashCalcLength > String::kMaxIntegerIndexSize);
      static_assert(String::kMaxHashCalcLength > String::kMaxArrayIndexSize);
      return GetTrivialHash(length);
    }
  }

  // Non-index hash.
  return String::CreateHashFieldValue(
      detail::GetUsableRapidHash(chars, length, seed.seed(), seed.secret()),
      String::HashFieldType::kHash);
}

std::size_t SeededStringHasher::operator()(const char* name) const {
  return StringHasher::HashSequentialString(
      name, static_cast<uint32_t>(strlen(name)), hashseed_);
}

}  // namespace internal
}  // namespace v8

#endif  // V8_STRINGS_STRING_HASHER_INL_H_