OXYGENHUB
◆ main openmsx / src / utils / DivModBySame.hh
2.5 KiB · C++ · last changed chore(): initial commit 1 month ago source blame history raw
1 
#ifndef DIVISIONBYCONST_HH
2 
#define DIVISIONBYCONST_HH
3
4 
#include "narrow.hh"
5 
#include <cassert>
6 
#include <cstdint>
7 
#include <utility>
8
9 
namespace openmsx {
10
11 
/** Helper class to divide multiple times by the same number.
12 
 * Binary division can be performed by:
13 
 *   - multiplication by a magic number
14 
 *   - followed by an addition of a magic number
15 
 *   - followed by a right shift over some magic number of bits
16 
 * These magic constants only depend on the divisor, but they are quite
17 
 * expensive to calculate.
18 
 * However if you know you will divide many times by the same number this
19 
 * algorithm does make sense and can result in a big speedup, especially on
20 
 * CPUs which lack a hardware division instruction (like ARM).
21 
 *
22 
 * If the divisor is a compile-time constant, it's even faster to use
23 
 * the DivModByConst utility class.
24 
 */
25 
class DivModBySame
26 
{
27 
public:
28 
	void setDivisor(uint32_t divisor);
29 
	[[nodiscard]] uint32_t getDivisor() const { return divisor; }
30
31 
	[[nodiscard]] uint32_t div(uint64_t dividend) const
32 
	{
33 
	#if defined __x86_64 && !defined _MSC_VER
34 
		auto t = narrow_cast<uint64_t>((__uint128_t(dividend) * m + a) >> 64);
35 
		return narrow_cast<uint32_t>(t >> s);
36 
	#else
37 
		return divInC(dividend);
38 
	#endif
39 
	}
40
41 
	[[nodiscard]] uint32_t divInC(uint64_t dividend) const
42 
	{
43 
		uint64_t t1 = uint64_t(uint32_t(dividend)) * uint32_t(m);
44 
		uint64_t t2 = (dividend >> 32) * uint32_t(m);
45 
		uint64_t t3 = uint32_t(dividend) * (m >> 32);
46 
		uint64_t t4 = (dividend >> 32) * (m >> 32);
47
48 
		uint64_t s1 = uint64_t(uint32_t(a)) + uint32_t(t1);
49 
		uint64_t s2 = (s1 >> 32) + (a >> 32) + (t1 >> 32) + t2;
50 
		uint64_t s3 = uint64_t(uint32_t(s2)) + uint32_t(t3);
51 
		uint64_t s4 = (s3 >> 32) + (s2 >> 32) + (t3 >> 32) + t4;
52
53 
		uint64_t result = s4 >> s;
54 
	#ifdef DEBUG
55 
		// we don't even want this overhead in devel builds
56 
		assert(result == uint32_t(result));
57 
	#endif
58 
		return uint32_t(result);
59 
	}
60
61 
	[[nodiscard]] std::pair<uint32_t, uint32_t> divMod(uint64_t dividend) const
62 
	{
63 
		assert(uint32_t(divisor) == divisor); // must fit in 32-bit
64 
		uint64_t q = div(dividend);
65 
		assert(uint32_t(q) == q); // must fit in 32 bit
66 
		// result fits in 32-bit, so no 64-bit calculations required
67 
		uint32_t r = uint32_t(dividend) - uint32_t(q) * uint32_t(divisor);
68 
		return {uint32_t(q), r};
69 
	}
70
71 
	[[nodiscard]] uint32_t mod(uint64_t dividend) const
72 
	{
73 
		auto [q, r] = divMod(dividend);
74 
		(void)q;
75 
		return r;
76 
	}
77
78 
private:
79 
	uint64_t m = 0;
80 
	uint64_t a = 0;
81 
	uint32_t s = 0;
82 
	uint32_t divisor= 0; // only used by mod() and getDivisor()
83 
};
84
85 
} // namespace openmsx
86
87 
#endif // DIVISIONBYCONST_HH