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