// Copyright Epic Games, Inc. All Rights Reserved.

#include <zencore/endian.h>
#include <zencore/intmath.h>

#include <zencore/testing.h>

namespace zen {

ReciprocalU64::ReciprocalU64(uint64_t Divisor)
{
	if (Divisor <= 1)
	{
		Mul	  = 0;	// Sentinel — Divide() returns Value directly.
		Shift = 0;
		return;
	}

	// m = ceil(2^(64+s) / d).  Start with s = 0; bump s only if
	// the quotient doesn't fit in 64 bits (happens when d is a
	// power of two, since 2^64 / 2^k = 2^(64-k) exactly and the
	// +1 for ceil can overflow to zero).
	for (uint32_t S = 0; S < 64; ++S)
	{
#if ZEN_PLATFORM_WINDOWS
		uint64_t Remainder = 0;
		uint64_t Quotient  = _udiv128(uint64_t(1) << S, 0, Divisor, &Remainder);
		uint64_t M		   = Quotient + (Remainder ? 1 : 0);  // ceil
#else
		unsigned __int128 Num		= (unsigned __int128)(uint64_t(1) << S) << 64;
		uint64_t		  Quotient	= uint64_t(Num / Divisor);
		uint64_t		  Remainder = uint64_t(Num % Divisor);
		uint64_t		  M			= Quotient + (Remainder ? 1 : 0);
#endif
		if (M != 0)
		{
			Mul	  = M;
			Shift = S;
			return;
		}
	}
	// Unreachable for any Divisor > 1.
	Mul	  = 0;
	Shift = 0;
}

//////////////////////////////////////////////////////////////////////////
//
// Testing related code follows...
//

#if ZEN_WITH_TESTS

void
intmath_forcelink()
{
}

TEST_SUITE_BEGIN("core.intmath");

TEST_CASE("intmath")
{
	CHECK(FloorLog2(0x00) == 0);
	CHECK(FloorLog2(0x01) == 0);
	CHECK(FloorLog2(0x0f) == 3);
	CHECK(FloorLog2(0x10) == 4);
	CHECK(FloorLog2(0x11) == 4);
	CHECK(FloorLog2(0x12) == 4);
	CHECK(FloorLog2(0x22) == 5);
	CHECK(FloorLog2(0x0001'0000) == 16);
	CHECK(FloorLog2(0x0001'000f) == 16);
	CHECK(FloorLog2(0x8000'0000) == 31);

	CHECK(FloorLog2_64(0x00ull) == 0);
	CHECK(FloorLog2_64(0x01ull) == 0);
	CHECK(FloorLog2_64(0x0full) == 3);
	CHECK(FloorLog2_64(0x10ull) == 4);
	CHECK(FloorLog2_64(0x11ull) == 4);
	CHECK(FloorLog2_64(0x0001'0000ull) == 16);
	CHECK(FloorLog2_64(0x0001'000full) == 16);
	CHECK(FloorLog2_64(0x8000'0000ull) == 31);
	CHECK(FloorLog2_64(0x0000'0001'0000'0000ull) == 32);
	CHECK(FloorLog2_64(0x8000'0000'0000'0000ull) == 63);

	CHECK(CountLeadingZeros(0x8000'0000u) == 0);
	CHECK(CountLeadingZeros(0x0000'0000u) == 32);
	CHECK(CountLeadingZeros(0x0000'0001u) == 31);
	CHECK(CountLeadingZeros(0x0000'8000u) == 16);
	CHECK(CountLeadingZeros(0x0001'0000u) == 15);

	CHECK(CountLeadingZeros64(0x8000'0000'0000'0000ull) == 0);
	CHECK(CountLeadingZeros64(0x0000'0000'0000'0000ull) == 64);
	CHECK(CountLeadingZeros64(0x0000'0000'0000'0001ull) == 63);
	CHECK(CountLeadingZeros64(0x0000'0000'8000'0000ull) == 32);
	CHECK(CountLeadingZeros64(0x0000'0001'0000'0000ull) == 31);

	CHECK(CountTrailingZeros64(0x8000'0000'0000'0000ull) == 63);
	CHECK(CountTrailingZeros64(0x0000'0000'0000'0000ull) == 64);
	CHECK(CountTrailingZeros64(0x0000'0000'0000'0001ull) == 0);
	CHECK(CountTrailingZeros64(0x0000'0000'8000'0000ull) == 31);
	CHECK(CountTrailingZeros64(0x0000'0001'0000'0000ull) == 32);

	CHECK(ByteSwap(uint16_t(0x6d72)) == 0x726d);
	CHECK(ByteSwap(uint32_t(0x2741'3965)) == 0x6539'4127);
	CHECK(ByteSwap(uint64_t(0x214d'6172'7469'6e21ull)) == 0x216e'6974'7261'4d21ull);
}

TEST_CASE("ReciprocalU64 matches integer division")
{
	uint64_t Divisors[] = {1, 2, 3, 4, 5, 7, 10, 100, 1000, 3000, 3579};

	for (uint64_t D : Divisors)
	{
		ReciprocalU64 R(D);

		uint64_t TestValues[] = {
			0,
			1,
			D - 1,
			D,
			D + 1,
			D * 2,
			D * 2 + 1,
			1'000'000,
			10'000'000,
			100'000'000,
			1'000'000'000ULL,
			10'000'000'000ULL,
			100'000'000'000ULL,
			1'000'000'000'000ULL,
			uint64_t(~0u),
		};

		for (uint64_t V : TestValues)
		{
			uint32_t Expected = uint32_t(V / D);
			uint32_t Got	  = R.Divide(V);
			CHECK_MESSAGE(Got == Expected, "V=", V, " D=", D, " expected=", Expected, " got=", Got);
		}
	}
}

TEST_CASE("ReciprocalU64 rounding division")
{
	// Verify the rounding pattern used in AbsorbBatch: (Cycle + half) / d
	uint64_t Divisors[] = {3, 4, 5, 10, 3579};

	for (uint64_t D : Divisors)
	{
		ReciprocalU64 R(D);
		uint64_t	  Half = D >> 1;

		uint64_t TestCycles[] = {0, 1, 100, 999'999, 1'000'000, 99'999'999, 1'000'000'000ULL, 50'000'000'000ULL};

		for (uint64_t Cycle : TestCycles)
		{
			uint64_t Rounded  = Cycle + Half;
			uint32_t Expected = uint32_t(Rounded / D);
			uint32_t Got	  = R.Divide(Rounded);
			CHECK_MESSAGE(Got == Expected, "Cycle=", Cycle, " D=", D, " expected=", Expected, " got=", Got);
		}
	}
}

TEST_SUITE_END();

#endif

}  // namespace zen