diff options
Diffstat (limited to 'src/zencore')
| -rw-r--r-- | src/zencore/include/zencore/fmtutils.h | 2 | ||||
| -rw-r--r-- | src/zencore/include/zencore/intmath.h | 32 | ||||
| -rw-r--r-- | src/zencore/intmath.cpp | 94 | ||||
| -rw-r--r-- | src/zencore/string.cpp | 10 |
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; } |