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