aboutsummaryrefslogtreecommitdiff
path: root/src/zencore
diff options
context:
space:
mode:
Diffstat (limited to 'src/zencore')
-rw-r--r--src/zencore/include/zencore/fmtutils.h2
-rw-r--r--src/zencore/include/zencore/intmath.h32
-rw-r--r--src/zencore/intmath.cpp94
-rw-r--r--src/zencore/string.cpp10
4 files changed, 133 insertions, 5 deletions
diff --git a/src/zencore/include/zencore/fmtutils.h b/src/zencore/include/zencore/fmtutils.h
index a263c6f04..f062c4147 100644
--- a/src/zencore/include/zencore/fmtutils.h
+++ b/src/zencore/include/zencore/fmtutils.h
@@ -90,7 +90,7 @@ struct fmt::formatter<std::filesystem::path> : formatter<string_view>
using namespace std::literals;
zen::ExtendableStringBuilder<128> String;
- String << Path.u8string();
+ zen::PathToUtf8(Path, String);
std::string_view PathView = String.ToView();
if (PathView.starts_with("\\\\?\\"sv))
diff --git a/src/zencore/include/zencore/intmath.h b/src/zencore/include/zencore/intmath.h
index 2b59d6f4a..b9f31d57b 100644
--- a/src/zencore/include/zencore/intmath.h
+++ b/src/zencore/include/zencore/intmath.h
@@ -38,6 +38,7 @@
#if ZEN_COMPILER_MSC || ZEN_PLATFORM_WINDOWS
# pragma intrinsic(_BitScanReverse)
# pragma intrinsic(_BitScanReverse64)
+# pragma intrinsic(_umul128)
#else
inline uint8_t
_BitScanReverse(unsigned long* Index, uint32_t Mask)
@@ -205,6 +206,37 @@ Max(auto x, auto y)
//////////////////////////////////////////////////////////////////////////
+// Precomputed reciprocal for fast 64-bit unsigned division by a constant.
+// Given divisor d, stores multiplier m and shift s such that
+// x / d == MulHi64(x, m) >> s for all x in the expected range.
+//
+// Uses the "round-up" method: m = ceil(2^(64+s) / d). The extra shift
+// parameter s is bumped when d is a power of two (where ceil would
+// overflow). For small divisors s == 0 always suffices.
+struct ReciprocalU64
+{
+ uint64_t Mul = 0;
+ uint32_t Shift = 0;
+
+ ReciprocalU64() = default;
+ explicit ReciprocalU64(uint64_t Divisor);
+
+ uint32_t Divide(uint64_t Value) const
+ {
+ if (Mul == 0)
+ {
+ return uint32_t(Value); // Divisor <= 1
+ }
+#if ZEN_PLATFORM_WINDOWS
+ uint64_t Hi;
+ _umul128(Value, Mul, &Hi);
+#else
+ uint64_t Hi = uint64_t(((unsigned __int128)Value * Mul) >> 64);
+#endif
+ return uint32_t(Hi >> Shift);
+ }
+};
+
void intmath_forcelink(); // internal
} // namespace zen
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
diff --git a/src/zencore/string.cpp b/src/zencore/string.cpp
index 2691d14b8..34519b83b 100644
--- a/src/zencore/string.cpp
+++ b/src/zencore/string.cpp
@@ -56,20 +56,22 @@ bool
ToString(std::span<char> Buffer, uint64_t Num)
{
auto [Ptr, Ec] = std::to_chars(Buffer.data(), Buffer.data() + Buffer.size(), Num);
- if (Ec == std::errc{})
+ if (Ec != std::errc{} || Ptr == Buffer.data() + Buffer.size())
{
- *Ptr = '\0';
+ return false;
}
+ *Ptr = '\0';
return true;
}
bool
ToString(std::span<char> Buffer, int64_t Num)
{
auto [Ptr, Ec] = std::to_chars(Buffer.data(), Buffer.data() + Buffer.size(), Num);
- if (Ec == std::errc{})
+ if (Ec != std::errc{} || Ptr == Buffer.data() + Buffer.size())
{
- *Ptr = '\0';
+ return false;
}
+ *Ptr = '\0';
return true;
}