This is an automated email from the ASF dual-hosted git repository. xiaoxiang781216 pushed a commit to branch master in repository https://gitbox.apache.org/repos/asf/nuttx.git
commit 3b05ebeb10a26721f67be6fec14c667f9f190a69 Author: ouyangxiangzhen <[email protected]> AuthorDate: Fri Nov 13 17:19:00 2026 +0800 lib/math32: replace the udiv_soft loop with the s-parameterized invdiv_udiv128 Replace the 128-step soft-division loop of invdiv_udiv_soft() with the non-looped invdiv_udiv128() and compute the u64 invariant multiplier with it. One 128-by-64 division implementation now serves every path, and the division becomes constant-foldable: with a literal divisor the compiler evaluates the whole setup to a literal magic number, so div64_const() and div64_const32() cost one multiply and a shift at run time instead of keeping a division. A loop cannot be folded that way; this is the reason the loop goes. * invdiv_udiv128(hi, lo, d, s): the __int128 single expression when available, otherwise invdiv_udiv128_soft(), the two-digit Knuth-D expansion in base 2^32 -- long division by hand with the quotient's two digits and their rounding written out step by step. It contains no loop on any target. * The normalizer s = clz(d) is passed in and derived from l as the branch-free 64 - l - (((d - 1) & d) == 0), l = ceil(log2 d). * The old invdiv_init_param_dispatch64() closed form and the d <= 2^32 split are gone: KD2 is exact for every divisor. Verified: invdiv_udiv128 differential 2,713,524 boundary/random samples x (-O0/-O1/-O2/-Os) 0 mismatch on both arms; the invdiv_init_param64() + invdiv_u64() battery 4,000,998 samples 0 mismatch against n/d for d in [2, 2^63), the inherited d >= 2^63 shift band counted as before; t_divconst dispatch fails=0. Constant folding, measured with the NuttX arm-none-eabi-gcc 10.3.1 flags for cortex-m0 at -O2 and without CONFIG_DEBUG_NOOPT: a thread that returns div64_const(n, 1000), div64_const(n, 1000003) and div64_const32(n, 1000) compiles to 23 instructions each with no division helper among the undefined symbols, and div64_const(n, 4096) compiles to 6 instructions with no undefined symbol at all. The one runtime difference is the one-time setup cost of invdiv_init_param64() for d <= 2^32 (10.52 -> 14.09 ns/op; the setup runs once per divisor). Assisted-By: mimo-v2.6-pro Signed-off-by: ouyangxiangzhen <[email protected]> --- include/nuttx/lib/math32.h | 164 ++++++++++++++++++++++++++++++--------------- 1 file changed, 109 insertions(+), 55 deletions(-) diff --git a/include/nuttx/lib/math32.h b/include/nuttx/lib/math32.h index e5db10b7039..5aed59b089d 100644 --- a/include/nuttx/lib/math32.h +++ b/include/nuttx/lib/math32.h @@ -470,39 +470,101 @@ uint64_t invdiv_u32(uint32_t n, FAR const invdiv_param32_t *ip) return (t1 + t2) >> sh; } -/* Helper function to do n bits integer division. */ +/* One Knuth-D correction step: while qv*v0v exceeds rv*2^32 + lx, step + * qv back one and return v1v to rv. A normalized divisor bounds it to + * two per digit, one when qv was clamped to b-1; the rv < 2^32 guard is + * exact. The arguments are evaluated more than once. + */ -#define invdiv_udiv_soft(arr, n, q, d) \ +#define KD2_CORR(qv, rv, v1v, v0v, lx) \ do \ -{ \ - uint32_t idx; \ - uint32_t bits_per_idx = sizeof(uint64_t) * 8; \ - uint32_t bits_max = bits_per_idx * n; \ - uint64_t reminder = 0ull; \ - uint64_t high_rem = 0ull; \ - for (idx = 0; idx < bits_max; idx++) \ - { \ - uint32_t bits = bits_max - idx - 1; \ - uint32_t bits_idx = bits / bits_per_idx; \ - uint32_t bits_idx_off = bits % bits_per_idx; \ - reminder <<= 1u; \ - reminder |= ((arr)[bits_idx] >> bits_idx_off) & 1u; \ - if (reminder >= (d)) \ - { \ - reminder -= (d); \ - q[bits_idx] |= (1ull << bits_idx_off); \ - } \ - else if (high_rem != 0) \ - { \ - uint64_t c = 0ull - (d); \ - high_rem -= 1; \ - reminder += c; \ - q[bits_idx] |= (1ull << bits_idx_off); \ - } \ - high_rem += (reminder >> (bits_per_idx - 1)) & 1u; \ - } \ -} \ -while(0) + { \ + uint64_t c_ = ((rv) < (1ULL << 32)) && \ + ((qv) * (v0v) > (((rv) << 32) | (lx))); \ + (qv) -= c_; \ + (rv) += c_ * (v1v); \ + } \ +while (0) + +/**************************************************************************** + * Name: invdiv_udiv128_soft + * + * Description: + * Divide (hi*2^64 + lo) by d for hi < d, where the quotient fits 64 + * bits and is returned whole. s = clz(d) is supplied by the caller. + * + * Input Parameters: + * hi - The high 64 bits of the dividend. + * lo - The low 64 bits of the dividend. + * d - The divisor. + * s - The normalizer, clz(d). + * + * Returned Value: + * floor((hi*2^64 + lo) / d); hi < d is a precondition. + * + ****************************************************************************/ + +static inline_function uint64_t +invdiv_udiv128_soft(uint64_t hi, uint64_t lo, uint64_t d, int s) +{ + /* Hand long division in base b = 2^32 (Knuth, TAOCP vol. 2, 4.3.1, + * algorithm D): + * + * D = d<<s = v1*b + v0 + * N<<s = nh*b^2 + l1*b + l0 + * Q = floor(N / d) = q1*b + q0 + * + * One quotient digit, with u the next dividend digit: + * + * q = min(floor(nh / v1), b-1) trial quotient + * r = nh - q*v1 + * while (q*v0 > r*b + u) normalized d: <= 2 times + * { q--; r += v1; } + * nh = r*b + u - q*v0 subtract, bring down + * + * KD2_CORR() is one while-step; three slots per digit hold the + * theorem-B bound without a branch. Round 1 takes u = l1, round 2 + * u = l0; the digits assemble Q = q1*b + q0. Only Q is wanted. + */ + + uint64_t dv = d << s; + uint64_t v1 = dv >> 32; + uint64_t v0 = dv & UINT32_MAX; + + /* s == 0 would make lo >> (64 - s) a 64-bit shift (UB). */ + + uint64_t nh = s ? ((hi << s) | (lo >> (64 - s))) : hi; + uint64_t nl = lo << s; + uint64_t l1 = nl >> 32; + uint64_t l0 = nl & UINT32_MAX; + uint64_t q1; + uint64_t r1; + uint64_t R; + uint64_t q0; + uint64_t r0; + + /* digit 1 */ + + q1 = nh / v1; + q1 = q1 > UINT32_MAX ? UINT32_MAX : q1; + r1 = nh - q1 * v1; + KD2_CORR(q1, r1, v1, v0, l1); + KD2_CORR(q1, r1, v1, v0, l1); + KD2_CORR(q1, r1, v1, v0, l1); + + R = ((r1 << 32) | l1) - q1 * v0; + + /* digit 2 */ + + q0 = R / v1; + q0 = q0 > UINT32_MAX ? UINT32_MAX : q0; + r0 = R - q0 * v1; + KD2_CORR(q0, r0, v1, v0, l0); + KD2_CORR(q0, r0, v1, v0, l0); + KD2_CORR(q0, r0, v1, v0, l0); + + return (q1 << 32) + q0; +} /* UMULH: high 64 bits of a * b. One instruction inline when the * compiler has a native 128-bit multiply; otherwise one out-of-line copy @@ -529,11 +591,18 @@ uint64_t up_umulh64(uint64_t a, uint64_t b); * Name: invdiv_init_param64 * * Description: - * Calculate the triple (multiplier, right shift number 1, right shift - * number 2) during initialization. + * Calculate the invariant-division parameters from the divisor: the + * multiplier is floor((2^l - d) * 2^64 / d) + 1 + * through the single 128-by-64 division invdiv_udiv128(), with + * l = ceil(log2 d). The division's normalizer s = clz(d) is the + * branch-free 64 - l - (((d - 1) & d) == 0): l is one more than + * floor(log2 d) exactly when d is not a power of two (d >= 2 makes + * the bare bit test exact). * * Input Parameters: - * d - The divisor (unsigned integer), d != 0 and d != 1 is required. + * d - The divisor (unsigned integer), d != 0 and d != 1 is required; + * d > 2^63 keeps the pre-existing undefined behavior of the + * 1 << l setup (d == 2^63 is in contract). * * Output Parameters: * ip - The invariant division parameter to be cached. @@ -548,29 +617,14 @@ void invdiv_init_param64(uint64_t d, FAR invdiv_param64_t *ip) DEBUGASSERT(d > 1); -#ifndef __INT128_DEFINED - /* If the compiler do not support UINT128 */ - - uint64_t q[2]; - uint64_t mres[2]; - - /* Calculate the mult via 2^64 * (2^l - d) / d + 1 - * It is equal to ((2^l - d) << 64) / d + 1. So... - */ - - mres[1] = t; - mres[0] = 0; - q[0] = 0; - q[1] = 0; - - /* Then, do the 128-bit division. */ - - invdiv_udiv_soft(mres, 2, q, d); - - ip->mult = q[0] + 1; -#else +#ifdef __INT128_DEFINED _uint128_t one128 = 1; + ip->mult = (one128 << 64) * t / d + 1; +#else + int s = 64 - l - (((d - 1) & d) == 0); /* = clz(d) */ + + ip->mult = invdiv_udiv128_soft(t, 0, d, s) + 1; #endif ip->shift = l - 1; }
