divide64By32()

FL_FIXED_POINT_DIVIDE_INLINE u32 fl::divide64By32	(	u32	hi,
		u32	lo,
		u32	divisor )

(hi:lo) / divisor, for a quotient that fits 32 bits.

Knuth's Algorithm D over two base-2^16 digits, which is what lets a 64-bit numerator be divided using the 32-bit divider twice. The two correction loops run at most twice each and usually not at all; they are what make the base-2^16 estimate exact rather than approximate.

Defined, not undefined, on the two inputs the wide path leaves to the compiler: a zero divisor and a quotient too large for 32 bits both return 0xFFFFFFFF. That is a deliberate difference and is not something a caller may rely on – the wide path wraps instead – so operator/'s contract is unchanged and the divergence is pinned by a test rather than left to be discovered.

Kept out of #if FL_FIXED_POINT_NARROW_DIVIDE on purpose. Gating the definition would leave it compiled by no host and tested by nothing, which is how simd_noop.hpp went two rounds of tuning against a build that excluded it (FastLED#4216).

Definition at line 120 of file wide_divide.h.

                                                                       {
    constexpr u32 kBase = 65536u;
    if (divisor == 0u || hi >= divisor) {
        return 0xFFFFFFFFu;
    }
 
    // Normalising the divisor is what makes the digit estimate below good to
    // within one, which is the whole reason two corrections suffice.
    const int shift = detail::fixedPointLeadingZeros(divisor);
    const u32 d = divisor << shift;
    const u32 d_high = d >> 16;
    const u32 d_low = d & 0xFFFFu;
 
    // A shift of 32 is undefined, so the unshifted case is spelled out rather
    // than folded in with a mask.
    const u32 n_high = shift == 0 ? hi : ((hi << shift) | (lo >> (32 - shift)));
    const u32 n_low = lo << shift;
    const u32 n_low_high = n_low >> 16;
    const u32 n_low_low = n_low & 0xFFFFu;
 
    u32 quotient_high = n_high / d_high;
    u32 remainder = n_high - quotient_high * d_high;
    while (quotient_high >= kBase ||
           static_cast<u64>(quotient_high) * d_low >
               static_cast<u64>(kBase) * remainder + n_low_high) {
        --quotient_high;
        remainder += d_high;
        if (remainder >= kBase) {
            break;
        }
    }
 
    // Deliberate 32-bit wraparound: the true value needs 33 bits and the
    // low 32 are the ones the next digit is taken from.
    const u32 partial =
        static_cast<u32>(n_high * kBase + n_low_high - quotient_high * d);
 
    u32 quotient_low = partial / d_high;
    remainder = partial - quotient_low * d_high;
    while (quotient_low >= kBase ||
           static_cast<u64>(quotient_low) * d_low >
               static_cast<u64>(kBase) * remainder + n_low_low) {
        --quotient_low;
        remainder += d_high;
        if (remainder >= kBase) {
            break;
        }
    }
 
    return quotient_high * kBase + quotient_low;
}

References fl::detail::fixedPointLeadingZeros(), FL_FIXED_POINT_DIVIDE_INLINE, and FL_NO_EXCEPT.

Referenced by fl::s16x16::operator/(), and fl::u16x16::operator/().

Here is the call graph for this function:

Here is the caller graph for this function: