#include "DivModBySame.hh"

#include "uint128.hh"

#include <bit>

namespace openmsx {

void DivModBySame::setDivisor(uint32_t divisor_)
{
	//assert(divisor_ < 0x8000000000000000ULL); // when divisor is uint64_t
	divisor = divisor_;
	if (divisor == 0) {
		m = a = s = 0;
		return;
	}

	// reduce divisor until it becomes odd
	uint32_t n = 0;
	uint64_t t = divisor;
	while (!(t & 1)) {
		t >>= 1;
		++n;
	}
	if (t == 1) {
		m = 0xffffffffffffffffULL;
		a = m;
		s = 0;
	} else {
		// Generate m, s for algorithm 0. Based on: Granlund, T.; Montgomery,
		// P.L.: "Division by Invariant Integers using Multiplication".
		// SIGPLAN Notices, Vol. 29, June 1994, page 61.
		auto l = narrow<uint32_t>(std::bit_width(t));
		uint64_t j = 0xffffffffffffffffULL % t;
		uint128 k = (uint128(1) << (64 + l)) / (0xffffffffffffffffULL - j);
		uint128 m_low  =  (uint128(1) << (64 + l))      / t;
		uint128 m_high = ((uint128(1) << (64 + l)) + k) / t;
		while (((m_low >> 1) < (m_high >> 1)) && (l > 0)) {
			m_low >>= 1;
			m_high >>= 1;
			--l;
		}
		if ((m_high >> 64) == 0) {
			m = low64(m_high);
			s = l;
			a = 0;
		} else {
			// Generate m, s for algorithm 1. Based on: Magenheimer, D.J.; et al:
			// "Integer Multiplication and Division on the HP Precision Architecture".
			// IEEE Transactions on Computers, Vol 37, No. 8, August 1988, page 980.
			s = narrow<uint32_t>(std::bit_width(t) - 1);
			uint128 m_low2 =   (uint128(1) << (64 + s)) / t;
			uint64_t r = low64((uint128(1) << (64 + s)) % t);
			m = low64(m_low2 + ((r <= (t >> 1)) ? 0 : 1));
			a = m;
		}
		// reduce multiplier to smallest possible
		while (!(m & 1)) {
			m >>= 1;
			a >>= 1;
			s--;
		}
	}
	// adjust multiplier for reduction of even divisors
	s += n;
}

} // namespace openmsx