Skip to content

Commit aac14dd

Browse files
joyeecheungV8 LUCI CQ
joyeecheung
authored and
V8 LUCI CQ
committed
[string] add 3rd round to seeded array index hash
Since we already have 3 derived secrets, and arithmetics are relatively cheap, add a 3rd round to the xorshift-multiply seeding scheme. This brings the bias from ~3.4 to ~0.4. Bug: 477515021 Change-Id: I1ef48954bcee8768d8c90db06ac8adb02f06cebf Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/7655117 Reviewed-by: Chengzhong Wu <[email protected]> Commit-Queue: Joyee Cheung <[email protected]> Reviewed-by: Leszek Swirski <[email protected]> Cr-Commit-Position: refs/heads/main@{#105824}
1 parent 882eb6b commit aac14dd

File tree

6 files changed

+44
-14
lines changed

6 files changed

+44
-14
lines changed

‎src/codegen/code-stub-assembler.cc‎

Lines changed: 15 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -2706,43 +2706,53 @@ TNode<Uint32T> CodeStubAssembler::LoadJSReceiverIdentityHash(
27062706
#ifdef V8_ENABLE_SEEDED_ARRAY_INDEX_HASH
27072707
// Mirror C++ StringHasher::SeedArrayIndexValue.
27082708
TNode<Uint32T> CodeStubAssembler::SeedArrayIndexValue(TNode<Uint32T> value) {
2709-
// Load m1 and m2 from the hash seed byte array. In the compiled code
2709+
// Load m1, m2 and m3 from the hash seed byte array. In the compiled code
27102710
// these will always come from the read-only roots.
27112711
TNode<ByteArray> hash_seed = CAST(LoadRoot(RootIndex::kHashSeed));
27122712
intptr_t base_offset = OFFSET_OF_DATA_START(ByteArray) - kHeapObjectTag;
27132713
TNode<Uint32T> m1 = Load<Uint32T>(
27142714
hash_seed, IntPtrConstant(base_offset + HashSeed::kDerivedM1Offset));
27152715
TNode<Uint32T> m2 = Load<Uint32T>(
27162716
hash_seed, IntPtrConstant(base_offset + HashSeed::kDerivedM2Offset));
2717+
TNode<Uint32T> m3 = Load<Uint32T>(
2718+
hash_seed, IntPtrConstant(base_offset + HashSeed::kDerivedM3Offset));
27172719

27182720
TNode<Word32T> x = value;
2719-
// 2-round xorshift-multiply.
2721+
// 3-round xorshift-multiply.
27202722
x = Word32Xor(x, Word32Shr(x, Uint32Constant(Name::kArrayIndexHashShift)));
27212723
x = Word32And(Uint32Mul(Unsigned(x), m1),
27222724
Uint32Constant(Name::kArrayIndexValueMask));
27232725
x = Word32Xor(x, Word32Shr(x, Uint32Constant(Name::kArrayIndexHashShift)));
27242726
x = Word32And(Uint32Mul(Unsigned(x), m2),
27252727
Uint32Constant(Name::kArrayIndexValueMask));
27262728
x = Word32Xor(x, Word32Shr(x, Uint32Constant(Name::kArrayIndexHashShift)));
2729+
x = Word32And(Uint32Mul(Unsigned(x), m3),
2730+
Uint32Constant(Name::kArrayIndexValueMask));
2731+
x = Word32Xor(x, Word32Shr(x, Uint32Constant(Name::kArrayIndexHashShift)));
27272732

27282733
return Unsigned(x);
27292734
}
27302735

27312736
// Mirror C++ StringHasher::UnseedArrayIndexValue.
27322737
TNode<Uint32T> CodeStubAssembler::UnseedArrayIndexValue(TNode<Uint32T> value) {
2733-
// Load m1_inv and m2_inv from the hash seed byte array. In the compiled code
2734-
// these will always come from the read-only roots.
2738+
// Load m1_inv, m2_inv and m3_inv from the hash seed byte array. In the
2739+
// compiled code these will always come from the read-only roots.
27352740
TNode<ByteArray> hash_seed = CAST(LoadRoot(RootIndex::kHashSeed));
27362741
intptr_t base_offset = OFFSET_OF_DATA_START(ByteArray) - kHeapObjectTag;
27372742
TNode<Uint32T> m1_inv = Load<Uint32T>(
27382743
hash_seed, IntPtrConstant(base_offset + HashSeed::kDerivedM1InvOffset));
27392744
TNode<Uint32T> m2_inv = Load<Uint32T>(
27402745
hash_seed, IntPtrConstant(base_offset + HashSeed::kDerivedM2InvOffset));
2746+
TNode<Uint32T> m3_inv = Load<Uint32T>(
2747+
hash_seed, IntPtrConstant(base_offset + HashSeed::kDerivedM3InvOffset));
27412748

27422749
TNode<Word32T> x = value;
2743-
// 2-round xorshift-multiply (inverse).
2750+
// 3-round xorshift-multiply (inverse).
27442751
// Xorshift is an involution when kShift is at least half of the value width.
27452752
x = Word32Xor(x, Word32Shr(x, Uint32Constant(Name::kArrayIndexHashShift)));
2753+
x = Word32And(Uint32Mul(Unsigned(x), m3_inv),
2754+
Uint32Constant(Name::kArrayIndexValueMask));
2755+
x = Word32Xor(x, Word32Shr(x, Uint32Constant(Name::kArrayIndexHashShift)));
27462756
x = Word32And(Uint32Mul(Unsigned(x), m2_inv),
27472757
Uint32Constant(Name::kArrayIndexValueMask));
27482758
x = Word32Xor(x, Word32Shr(x, Uint32Constant(Name::kArrayIndexHashShift)));

‎src/numbers/hash-seed-inl.h‎

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -31,6 +31,8 @@ inline uint32_t HashSeed::m1() const { return data_->m1; }
3131
inline uint32_t HashSeed::m1_inv() const { return data_->m1_inv; }
3232
inline uint32_t HashSeed::m2() const { return data_->m2; }
3333
inline uint32_t HashSeed::m2_inv() const { return data_->m2_inv; }
34+
inline uint32_t HashSeed::m3() const { return data_->m3; }
35+
inline uint32_t HashSeed::m3_inv() const { return data_->m3_inv; }
3436
#endif // V8_ENABLE_SEEDED_ARRAY_INDEX_HASH
3537

3638
} // namespace internal

‎src/numbers/hash-seed.cc‎

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -51,6 +51,8 @@ constexpr void DeriveSecretsForArrayIndexHash(HashSeed::Data* data) {
5151
data->m1_inv = derive_multiplier_inverse(data->secrets[0]);
5252
data->m2 = derive_multiplier(data->secrets[1]);
5353
data->m2_inv = derive_multiplier_inverse(data->secrets[1]);
54+
data->m3 = derive_multiplier(data->secrets[2]);
55+
data->m3_inv = derive_multiplier_inverse(data->secrets[2]);
5456
}
5557
#endif // V8_ENABLE_SEEDED_ARRAY_INDEX_HASH
5658

@@ -75,6 +77,7 @@ const HashSeed::Data* const HashSeed::kDefaultData = &kDefaultSeed;
7577
// Compile-time verification that m * m_inv === 1 for the derived secrets.
7678
static_assert(is_modular_inverse(kDefaultSeed.m1, kDefaultSeed.m1_inv));
7779
static_assert(is_modular_inverse(kDefaultSeed.m2, kDefaultSeed.m2_inv));
80+
static_assert(is_modular_inverse(kDefaultSeed.m3, kDefaultSeed.m3_inv));
7881
#endif // V8_ENABLE_SEEDED_ARRAY_INDEX_HASH
7982

8083
// static
@@ -102,6 +105,7 @@ void HashSeed::InitializeRoots(Isolate* isolate) {
102105
DeriveSecretsForArrayIndexHash(data);
103106
DCHECK(is_modular_inverse(data->m1, data->m1_inv));
104107
DCHECK(is_modular_inverse(data->m2, data->m2_inv));
108+
DCHECK(is_modular_inverse(data->m3, data->m3_inv));
105109
#endif // V8_ENABLE_SEEDED_ARRAY_INDEX_HASH
106110
#endif // V8_USE_DEFAULT_HASHER_SECRET
107111
}

‎src/numbers/hash-seed.h‎

Lines changed: 6 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -53,6 +53,8 @@ class V8_EXPORT_PRIVATE HashSeed {
5353
uint32_t m1_inv; // modular inverse of m1 mod 2^kArrayIndexValueBits
5454
uint32_t m2; // lower kArrayIndexValueBits bits of secret[1], must be odd
5555
uint32_t m2_inv; // modular inverse of m2 mod 2^kArrayIndexValueBits
56+
uint32_t m3; // lower kArrayIndexValueBits bits of secret[2], must be odd
57+
uint32_t m3_inv; // modular inverse of m3 mod 2^kArrayIndexValueBits
5658
#endif // V8_ENABLE_SEEDED_ARRAY_INDEX_HASH
5759
};
5860

@@ -65,11 +67,15 @@ class V8_EXPORT_PRIVATE HashSeed {
6567
static constexpr int kDerivedM1InvOffset = offsetof(Data, m1_inv);
6668
static constexpr int kDerivedM2Offset = offsetof(Data, m2);
6769
static constexpr int kDerivedM2InvOffset = offsetof(Data, m2_inv);
70+
static constexpr int kDerivedM3Offset = offsetof(Data, m3);
71+
static constexpr int kDerivedM3InvOffset = offsetof(Data, m3_inv);
6872

6973
inline uint32_t m1() const;
7074
inline uint32_t m1_inv() const;
7175
inline uint32_t m2() const;
7276
inline uint32_t m2_inv() const;
77+
inline uint32_t m3() const;
78+
inline uint32_t m3_inv() const;
7379
#endif // V8_ENABLE_SEEDED_ARRAY_INDEX_HASH
7480

7581
// Generates a hash seed (from --hash-seed or the RNG) and writes it

‎src/strings/string-hasher-inl.h‎

Lines changed: 8 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -124,28 +124,34 @@ uint32_t StringHasher::SeedArrayIndexValue(uint32_t value,
124124
const HashSeed seed) {
125125
uint32_t m1 = seed.m1();
126126
uint32_t m2 = seed.m2();
127+
uint32_t m3 = seed.m3();
127128
constexpr uint32_t kShift = Name::kArrayIndexHashShift;
128129
constexpr uint32_t kMask = Name::kArrayIndexValueMask;
129-
// 2-round xorshift-multiply.
130+
// 3-round xorshift-multiply.
130131
uint32_t x = value;
131132
x ^= x >> kShift;
132133
x = (x * m1) & kMask;
133134
x ^= x >> kShift;
134135
x = (x * m2) & kMask;
135136
x ^= x >> kShift;
137+
x = (x * m3) & kMask;
138+
x ^= x >> kShift;
136139
return x;
137140
}
138141

139142
uint32_t StringHasher::UnseedArrayIndexValue(uint32_t value,
140143
const HashSeed seed) {
141144
uint32_t m1_inv = seed.m1_inv();
142145
uint32_t m2_inv = seed.m2_inv();
146+
uint32_t m3_inv = seed.m3_inv();
143147
uint32_t x = value;
144148
constexpr uint32_t kShift = Name::kArrayIndexHashShift;
145149
constexpr uint32_t kMask = Name::kArrayIndexValueMask;
146-
// 2-round xorshift-multiply.
150+
// 3-round xorshift-multiply (inverse).
147151
// Xorshift is an involution when kShift is at least half of the value width.
148152
x ^= x >> kShift;
153+
x = (x * m3_inv) & kMask;
154+
x ^= x >> kShift;
149155
x = (x * m2_inv) & kMask;
150156
x ^= x >> kShift;
151157
x = (x * m1_inv) & kMask;

‎src/strings/string-hasher.h‎

Lines changed: 9 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -79,22 +79,24 @@ class V8_EXPORT_PRIVATE StringHasher final {
7979

8080
#ifdef V8_ENABLE_SEEDED_ARRAY_INDEX_HASH
8181
// When V8_ENABLE_SEEDED_ARRAY_INDEX_HASH is enabled, the numeric value
82-
// will be scrambled with 2 rounds of xorshift-multiply.
82+
// will be scrambled with 3 rounds of xorshift-multiply.
8383
//
8484
// x ^= x >> kShift; x = (x * m1) & kMask; // round 1
8585
// x ^= x >> kShift; x = (x * m2) & kMask; // round 2
86+
// x ^= x >> kShift; x = (x * m3) & kMask; // round 3
8687
// x ^= x >> kShift; // finalize
8788
//
88-
// To decode, apply the same steps with the modular inverses of m1 and m2 in
89-
// reverse order.
89+
// To decode, apply the same steps with the modular inverses of m1, m2
90+
// and m3 in reverse order.
9091
//
91-
// x ^= x >> kShift; x = (x * m2_inv) & kMask; // round 1
92-
// x ^= x >> kShift; x = (x * m1_inv) & kMask; // round 2
92+
// x ^= x >> kShift; x = (x * m3_inv) & kMask; // round 1
93+
// x ^= x >> kShift; x = (x * m2_inv) & kMask; // round 2
94+
// x ^= x >> kShift; x = (x * m1_inv) & kMask; // round 3
9395
// x ^= x >> kShift; // finalize
9496
//
9597
// where kShift = kArrayIndexValueBits / 2, kMask = kArrayIndexValueMask,
96-
// m1, m2 (both odd) are derived from the Isolate's rapidhash secrets.
97-
// m1_inv, m2_inv (modular inverses) are precomputed so that
98+
// m1, m2, m3 (all odd) are derived from the Isolate's rapidhash secrets.
99+
// m1_inv, m2_inv, m3_inv (modular inverses) are precomputed so that
98100
// UnseedArrayIndexValue can quickly recover the original value.
99101
static V8_INLINE uint32_t SeedArrayIndexValue(uint32_t value,
100102
const HashSeed seed);

0 commit comments

Comments
 (0)