1#ifndef DIVMODBYCONST_HH
2#define DIVMODBYCONST_HH
28 while ((divisor & 1) == 0) {
32 return {divisor, shift};
54 while (((m_low >> 1) < (m_high >> 1)) && (l > 0)) {
59 return {m_low, m_high, l};
63[[nodiscard]]
static constexpr uint64_t mla64(uint64_t a, uint64_t b, uint64_t c)
67 uint64_t t1 = uint64_t(uint32_t(a)) * uint32_t(b);
68 uint64_t t2 = (a >> 32) * uint32_t(b);
69 uint64_t t3 = uint32_t(a) * (b >> 32);
70 uint64_t t4 = (a >> 32) * (b >> 32);
72 uint64_t s1 = uint64_t(uint32_t(c)) + uint32_t(t1);
73 uint64_t s2 = (s1 >> 32) + (c >> 32) + (t1 >> 32) + t2;
74 uint64_t s3 = uint64_t(uint32_t(s2)) + uint32_t(t3);
75 uint64_t s4 = (s3 >> 32) + (s2 >> 32) + (t3 >> 32) + t4;
79template<u
int32_t DIVISOR>
83 constexpr auto r0 =
reduce0(DIVISOR);
84 if constexpr (r0.divisor == 1) {
86 constexpr uint32_t shift = r0.shift;
87 return [=](uint64_t dividend) {
88 return dividend >> shift;
91 constexpr uint32_t
L = std::bit_width(r0.divisor);
92 constexpr uint64_t J = 0xffffffffffffffffull % r0.divisor;
94 constexpr uint128 k =
L64 / (0xffffffffffffffffull - J);
96 constexpr uint128 m_high = (
L64 + k) / r0.divisor;
97 constexpr auto r2 =
reduce2(m_low, m_high,
L);
99 if constexpr (high64(r2.m_high) == 0) {
101 constexpr auto r1 =
reduce1(low64(r2.m_high), r0.shift + r2.l);
103 constexpr uint64_t mul = r1.m;
104 constexpr uint32_t shift = r1.s;
105 return [=](uint64_t dividend) {
106 return mla64(dividend, mul, 0) >> shift;
110 constexpr uint32_t
S = std::bit_width(r0.divisor) - 1;
112 constexpr uint128 dq = S64 / r0.divisor;
113 constexpr uint128 dr = S64 % r0.divisor;
114 constexpr uint64_t M = low64(dq) + (low64(dr) > (r0.divisor / 2));
115 constexpr auto r1 =
reduce1(M,
S + r0.shift);
117 constexpr uint64_t mul = r1.m;
118 constexpr uint32_t shift = r1.s;
119 return [=](uint64_t dividend) {
120 return mla64(dividend, mul, mul) >> shift;
131 [[nodiscard]]
constexpr uint32_t
div(uint64_t dividend)
const
136 uint64_t result = dividend / DIVISOR;
138 auto algorithm = DivModByConstPrivate::getAlgorithm<DIVISOR>();
139 uint64_t result = algorithm(dividend);
143 assert(result == uint32_t(result));
145 return uint32_t(result);
148 [[nodiscard]]
constexpr uint32_t
mod(uint64_t dividend)
const
151 uint64_t result = dividend % DIVISOR;
153 uint64_t result = dividend - DIVISOR *
div(dividend);
157 assert(result == uint32_t(result));
159 return uint32_t(result);
Unsigned 128-bit integer type.
Utility class to optimize 64-bit divide/module by a 32-bit constant.
constexpr auto getAlgorithm()
constexpr Reduce1Result reduce1(uint64_t m, uint32_t s)
constexpr Reduce2Result reduce2(uint128 m_low, uint128 m_high, uint32_t l)
constexpr Reduce0Result reduce0(uint32_t divisor)
EndianT< uint64_t, ConvLittle< BIG > > L64
constexpr uint32_t div(uint64_t dividend) const
constexpr uint32_t mod(uint64_t dividend) const