openMSX
DivModBySame.hh
Go to the documentation of this file.
1 #ifndef DIVISIONBYCONST_HH
2 #define DIVISIONBYCONST_HH
3 
4 #include <cassert>
5 #include <cstdint>
6 #include <utility>
7 
8 namespace openmsx {
9 
25 {
26 public:
27  void setDivisor(uint32_t divisor);
28  [[nodiscard]] inline uint32_t getDivisor() const { return divisor; }
29 
30  [[nodiscard]] uint32_t div(uint64_t dividend) const
31  {
32  #if defined __x86_64 && !defined _MSC_VER
33  uint64_t t = (__uint128_t(dividend) * m + a) >> 64;
34  return t >> s;
35  #else
36  return divinC(dividend);
37  #endif
38  }
39 
40  [[nodiscard]] inline uint32_t divinC(uint64_t dividend) const
41  {
42  uint64_t t1 = uint64_t(uint32_t(dividend)) * uint32_t(m);
43  uint64_t t2 = (dividend >> 32) * uint32_t(m);
44  uint64_t t3 = uint32_t(dividend) * (m >> 32);
45  uint64_t t4 = (dividend >> 32) * (m >> 32);
46 
47  uint64_t s1 = uint64_t(uint32_t(a)) + uint32_t(t1);
48  uint64_t s2 = (s1 >> 32) + (a >> 32) + (t1 >> 32) + t2;
49  uint64_t s3 = uint64_t(uint32_t(s2)) + uint32_t(t3);
50  uint64_t s4 = (s3 >> 32) + (s2 >> 32) + (t3 >> 32) + t4;
51 
52  uint64_t result = s4 >> s;
53  #ifdef DEBUG
54  // we don't even want this overhead in devel builds
55  assert(result == uint32_t(result));
56  #endif
57  return uint32_t(result);
58  }
59 
60  [[nodiscard]] std::pair<uint32_t, uint32_t> divMod(uint64_t dividend) const
61  {
62  assert(uint32_t(divisor) == divisor); // must fit in 32-bit
63  uint64_t q = div(dividend);
64  assert(uint32_t(q) == q); // must fit in 32 bit
65  // result fits in 32-bit, so no 64-bit calculations required
66  uint32_t r = uint32_t(dividend) - uint32_t(q) * uint32_t(divisor);
67  return {q, r};
68  }
69 
70  [[nodiscard]] uint32_t mod(uint64_t dividend) const
71  {
72  auto [q, r] = divMod(dividend);
73  (void)q;
74  return r;
75  }
76 
77 private:
78  uint64_t m;
79  uint64_t a;
80  uint32_t s;
81  uint32_t divisor; // only used by mod() and getDivisor()
82 };
83 
84 } // namespace openmsx
85 
86 #endif // DIVISIONBYCONST_HH
openmsx::DivModBySame::getDivisor
uint32_t getDivisor() const
Definition: DivModBySame.hh:28
openmsx::DivModBySame
Helper class to divide multiple times by the same number.
Definition: DivModBySame.hh:25
t
TclObject t
Definition: TclObject_test.cc:264
openmsx::DivModBySame::mod
uint32_t mod(uint64_t dividend) const
Definition: DivModBySame.hh:70
openmsx::DivModBySame::divMod
std::pair< uint32_t, uint32_t > divMod(uint64_t dividend) const
Definition: DivModBySame.hh:60
openmsx::DivModBySame::divinC
uint32_t divinC(uint64_t dividend) const
Definition: DivModBySame.hh:40
openmsx::DivModBySame::setDivisor
void setDivisor(uint32_t divisor)
Definition: DivModBySame.cc:7
openmsx::DivModBySame::div
uint32_t div(uint64_t dividend) const
Definition: DivModBySame.hh:30
openmsx
Thanks to enen for testing this on a real cartridge:
Definition: Autofire.cc:5