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 
7 namespace openmsx {
8 
24 {
25 public:
26  void setDivisor(uint32_t divisor);
27  inline uint32_t getDivisor() const { return divisor; }
28 
29  uint32_t div(uint64_t dividend) const
30  {
31  #if defined __x86_64 && !defined _MSC_VER
32  uint64_t t = (__uint128_t(dividend) * m + a) >> 64;
33  return t >> s;
34  #else
35  return divinC(dividend);
36  #endif
37  }
38 
39  inline uint32_t divinC(uint64_t dividend) const
40  {
41  uint64_t t1 = uint64_t(uint32_t(dividend)) * uint32_t(m);
42  uint64_t t2 = (dividend >> 32) * uint32_t(m);
43  uint64_t t3 = uint32_t(dividend) * (m >> 32);
44  uint64_t t4 = (dividend >> 32) * (m >> 32);
45 
46  uint64_t s1 = uint64_t(uint32_t(a)) + uint32_t(t1);
47  uint64_t s2 = (s1 >> 32) + (a >> 32) + (t1 >> 32) + t2;
48  uint64_t s3 = uint64_t(uint32_t(s2)) + uint32_t(t3);
49  uint64_t s4 = (s3 >> 32) + (s2 >> 32) + (t3 >> 32) + t4;
50 
51  uint64_t result = s4 >> s;
52  #ifdef DEBUG
53  // we don't even want this overhead in devel builds
54  assert(result == uint32_t(result));
55  #endif
56  return uint32_t(result);
57  }
58 
59  uint32_t mod(uint64_t dividend) const
60  {
61  assert(uint32_t(divisor) == divisor); // must fit in 32-bit
62  uint64_t q = div(dividend);
63  assert(uint32_t(q) == q); // must fit in 32 bit
64  // result fits in 32-bit, so no 64-bit calculations required
65  return uint32_t(dividend) - uint32_t(q) * uint32_t(divisor);
66  }
67 
68 private:
69  uint64_t m;
70  uint64_t a;
71  uint32_t s;
72  uint32_t divisor; // only used by mod() and getDivisor()
73 };
74 
75 } // namespace openmsx
76 
77 #endif // DIVISIONBYCONST_HH
uint32_t divinC(uint64_t dividend) const
Definition: DivModBySame.hh:39
uint32_t getDivisor() const
Definition: DivModBySame.hh:27
uint32_t mod(uint64_t dividend) const
Definition: DivModBySame.hh:59
Thanks to enen for testing this on a real cartridge:
Definition: Autofire.cc:5
uint32_t div(uint64_t dividend) const
Definition: DivModBySame.hh:29
TclObject t
Helper class to divide multiple times by the same number.
Definition: DivModBySame.hh:23
void setDivisor(uint32_t divisor)
Definition: DivModBySame.cc:17