openMSX
DivModBySame.cc
Go to the documentation of this file.
1#include "DivModBySame.hh"
2#include "uint128.hh"
3#include <bit>
4
5namespace openmsx {
6
7void 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 = narrow<uint32_t>(std::bit_width(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 = narrow<uint32_t>(std::bit_width(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
TclObject t
void setDivisor(uint32_t divisor)
Definition: DivModBySame.cc:7
Unsigned 128-bit integer type.
Definition: uint128.hh:26
This file implemented 3 utility functions:
Definition: Autofire.cc:9