1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
|
#pragma once
#include <util/system/compiler.h>
#include <util/system/types.h>
#if defined(_MSC_VER) && defined(_M_X64)
#include <intrin.h>
#endif
/**
* Calculates the number of buckets for the hash table that will hold the given
* number of elements.
*
* @param elementCount Number of elements that the hash table will hold.
* @returns Number of buckets, a prime number that is
* greater or equal to `elementCount`.
*/
Y_CONST_FUNCTION
unsigned long HashBucketCount(unsigned long elementCount);
namespace NPrivate {
/// Implementation of algorithm 4.1 from: Torbjörn Granlund and Peter L. Montgomery. 1994. Division by invariant integers using multiplication.
/// @see https://gmplib.org/~tege/divcnst-pldi94.pdf
template <typename TDivisor, typename TDividend, typename MulUnsignedUpper>
class TReciprocalDivisor {
static_assert(sizeof(TDivisor) <= sizeof(TDividend), "TDivisor and TDividend should have the same size");
public:
constexpr TReciprocalDivisor() noexcept = default;
constexpr TReciprocalDivisor(TDividend reciprocal, ui8 reciprocalShift, i8 hint, TDivisor divisor) noexcept
: Reciprocal(reciprocal)
, Divisor(divisor)
, ReciprocalShift(reciprocalShift)
, Hint(hint)
{
}
/// Return (dividend % Divisor)
Y_FORCE_INLINE TDividend Remainder(TDividend dividend) const noexcept {
if (Y_UNLIKELY(Divisor == 1)) {
return 0;
}
TDividend r = dividend - Quotent(dividend) * Divisor;
return r;
}
Y_FORCE_INLINE TDivisor operator()() const noexcept {
return Divisor;
}
Y_FORCE_INLINE static constexpr TReciprocalDivisor One() noexcept {
return {1u, 0u, -1, 1u};
}
private:
/// returns (dividend / Divisor)
Y_FORCE_INLINE TDividend Quotent(TDividend dividend) const noexcept {
const TDividend t = MulUnsignedUpper{}(dividend, Reciprocal);
const TDividend q = (t + ((dividend - t) >> 1)) >> ReciprocalShift;
return q;
}
public:
TDividend Reciprocal = 0;
TDivisor Divisor = 0;
ui8 ReciprocalShift = 0;
i8 Hint = 0; ///< Additional data: needless for division, but useful for the adjacent divisors search
};
template <typename T, typename TExtended, size_t shift>
struct TMulUnsignedUpper {
/// Return the high bits of the product of two unsigned integers.
Y_FORCE_INLINE T operator()(T a, T b) const noexcept {
return (static_cast<TExtended>(a) * static_cast<TExtended>(b)) >> shift;
}
};
#if defined(_32_)
using THashDivisor = ::NPrivate::TReciprocalDivisor<ui32, ui32, TMulUnsignedUpper<ui32, ui64, 32>>;
#else
#if defined(Y_HAVE_INT128)
using THashDivisor = ::NPrivate::TReciprocalDivisor<ui32, ui64, TMulUnsignedUpper<ui64, unsigned __int128, 64>>;
#elif defined(_MSC_VER) && defined(_M_X64)
struct TMulUnsignedUpperVCIntrin {
/// Return the high 64 bits of the product of two 64-bit unsigned integers.
Y_FORCE_INLINE ui64 operator()(ui64 a, ui64 b) const noexcept {
return __umulh(a, b);
}
};
using THashDivisor = ::NPrivate::TReciprocalDivisor<ui32, ui64, TMulUnsignedUpperVCIntrin>;
#else
template <typename TDivisor, typename TDividend>
class TNaiveDivisor {
public:
constexpr TNaiveDivisor() noexcept = default;
constexpr TNaiveDivisor(TDivisor divisor) noexcept
: Divisor(divisor)
{
}
constexpr TNaiveDivisor(TDividend reciprocal, ui8 reciprocalShift, i8 hint, TDivisor divisor) noexcept
: TNaiveDivisor(divisor)
{
Y_UNUSED(reciprocal);
Y_UNUSED(reciprocalShift);
Y_UNUSED(hint);
}
Y_FORCE_INLINE TDividend Remainder(TDividend dividend) const noexcept {
return dividend % Divisor;
}
Y_FORCE_INLINE TDivisor operator()() const noexcept {
return Divisor;
}
Y_FORCE_INLINE static constexpr TNaiveDivisor One() noexcept {
return {1u};
}
public:
TDivisor Divisor = 0;
static constexpr i8 Hint = -1;
};
using THashDivisor = ::NPrivate::TNaiveDivisor<ui32, ui64>;
#endif
#endif
} // namespace NPrivate
Y_CONST_FUNCTION
::NPrivate::THashDivisor HashBucketCountExt(unsigned long elementCount);
Y_CONST_FUNCTION
::NPrivate::THashDivisor HashBucketCountExt(unsigned long elementCount, int hint);
|
