1#ifndef DIVISIONBYCONST_HH
2#define DIVISIONBYCONST_HH
29 [[nodiscard]]
inline uint32_t
getDivisor()
const {
return divisor; }
31 [[nodiscard]] uint32_t
div(uint64_t dividend)
const
33 #if defined __x86_64 && !defined _MSC_VER
34 auto t = narrow_cast<uint64_t>((__uint128_t(dividend) * m + a) >> 64);
35 return narrow_cast<uint32_t>(
t >> s);
41 [[nodiscard]]
inline uint32_t
divInC(uint64_t dividend)
const
43 uint64_t t1 = uint64_t(uint32_t(dividend)) * uint32_t(m);
44 uint64_t t2 = (dividend >> 32) * uint32_t(m);
45 uint64_t t3 = uint32_t(dividend) * (m >> 32);
46 uint64_t t4 = (dividend >> 32) * (m >> 32);
48 uint64_t s1 = uint64_t(uint32_t(a)) + uint32_t(t1);
49 uint64_t s2 = (s1 >> 32) + (a >> 32) + (t1 >> 32) + t2;
50 uint64_t s3 = uint64_t(uint32_t(s2)) + uint32_t(t3);
51 uint64_t s4 = (s3 >> 32) + (s2 >> 32) + (t3 >> 32) + t4;
53 uint64_t result = s4 >> s;
56 assert(result == uint32_t(result));
58 return uint32_t(result);
61 [[nodiscard]] std::pair<uint32_t, uint32_t>
divMod(uint64_t dividend)
const
63 assert(uint32_t(divisor) == divisor);
64 uint64_t q =
div(dividend);
65 assert(uint32_t(q) == q);
67 uint32_t r = uint32_t(dividend) - uint32_t(q) * uint32_t(divisor);
68 return {uint32_t(q), r};
71 [[nodiscard]] uint32_t
mod(uint64_t dividend)
const
73 auto [q, r] =
divMod(dividend);
Helper class to divide multiple times by the same number.
uint32_t div(uint64_t dividend) const
uint32_t mod(uint64_t dividend) const
uint32_t divInC(uint64_t dividend) const
uint32_t getDivisor() const
std::pair< uint32_t, uint32_t > divMod(uint64_t dividend) const
void setDivisor(uint32_t divisor)
This file implemented 3 utility functions: