1 files changed, 94 insertions, 0 deletions
diff --git a/src/zencore/intmath.cpp b/src/zencore/intmath.cpp
index fedf76edc..b460b5b78 100644
--- a/src/zencore/intmath.cpp
+++ b/src/zencore/intmath.cpp
@@ -7,6 +7,43 @@
 
 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...
@@ -68,6 +105,63 @@ TEST_CASE("intmath")
 	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