openMSX
DivModBySame.cc
Go to the documentation of this file.
1 #include "DivModBySame.hh"
2 #include "Math.hh"
3 #include "uint128.hh"
4 
5 namespace openmsx {
6 
7 void DivModBySame::setDivisor(uint32_t divisor_)
8 {
9  //assert(divisor_ < 0x8000000000000000ull); // when divisor is uint64_t
10  divisor = divisor_;
11 
12  // reduce divisor until it becomes odd
13  uint32_t n = 0;
14  uint64_t t = divisor;
15  while (!(t & 1)) {
16  t >>= 1;
17  ++n;
18  }
19  if (t == 1) {
20  m = 0xffffffffffffffffull;
21  a = m;
22  s = 0;
23  } else {
24  // Generate m, s for algorithm 0. Based on: Granlund, T.; Montgomery,
25  // P.L.: "Division by Invariant Integers using Multiplication".
26  // SIGPLAN Notices, Vol. 29, June 1994, page 61.
27  uint32_t l = Math::log2p1(t);
28  uint64_t j = 0xffffffffffffffffull % t;
29  uint128 k = (uint128(1) << (64 + l)) / (0xffffffffffffffffull - j);
30  uint128 m_low = (uint128(1) << (64 + l)) / t;
31  uint128 m_high = ((uint128(1) << (64 + l)) + k) / t;
32  while (((m_low >> 1) < (m_high >> 1)) && (l > 0)) {
33  m_low >>= 1;
34  m_high >>= 1;
35  --l;
36  }
37  if ((m_high >> 64) == 0) {
38  m = toUint64(m_high);
39  s = l;
40  a = 0;
41  } else {
42  // Generate m, s for algorithm 1. Based on: Magenheimer, D.J.; et al:
43  // "Integer Multiplication and Division on the HP Precision Architecture".
44  // IEEE Transactions on Computers, Vol 37, No. 8, August 1988, page 980.
45  s = Math::log2p1(t) - 1;
46  uint128 m_low2 = (uint128(1) << (64 + s)) / t;
47  uint64_t r = toUint64((uint128(1) << (64 + s)) % t);
48  m = toUint64(m_low2 + ((r <= (t >> 1)) ? 0 : 1));
49  a = m;
50  }
51  // reduce multiplier to smallest possible
52  while (!(m & 1)) {
53  m >>= 1;
54  a >>= 1;
55  s--;
56  }
57  }
58  // adjust multiplier for reduction of even divisors
59  s += n;
60 }
61 
62 } // namespace openmsx
Unsigned 128-bit integer type.
Definition: uint128.hh:21
uint64_t toUint64(const uint128 &a)
Definition: uint128.hh:233
Thanks to enen for testing this on a real cartridge:
Definition: Autofire.cc:5
constexpr T log2p1(T x) noexcept
Returns the number of bits needed to store the value &#39;x&#39;, that is: for x==0 : 0 for x!=0 : 1 + floor(...
Definition: Math.hh:38
TclObject t
void setDivisor(uint32_t divisor)
Definition: DivModBySame.cc:7