wide_divide.h

Go to the documentation of this file.

#pragma once

 
#include "fl/stl/int.h"
#include "fl/stl/compiler_control.h"
#include "fl/stl/noexcept.h"

#ifndef FL_FIXED_POINT_NARROW_DIVIDE
#if __cplusplus < 201402L
#define FL_FIXED_POINT_NARROW_DIVIDE 0
#elif defined(__arm__) && defined(__ARM_FEATURE_IDIV) && \
    (__ARM_FEATURE_IDIV + 0) == 1
#define FL_FIXED_POINT_NARROW_DIVIDE 1
#elif defined(__riscv_div) && defined(__riscv_xlen) && (__riscv_xlen + 0) == 32
#define FL_FIXED_POINT_NARROW_DIVIDE 1
#else
#define FL_FIXED_POINT_NARROW_DIVIDE 0
#endif
#endif

#if __cplusplus >= 201402L
#define FL_FIXED_POINT_DIVIDE_INLINE constexpr FASTLED_FORCE_INLINE
#else
#define FL_FIXED_POINT_DIVIDE_INLINE FASTLED_FORCE_INLINE
#endif
 
namespace fl {
 
namespace detail {

FL_FIXED_POINT_DIVIDE_INLINE int fixedPointLeadingZeros(u32 value) FL_NO_EXCEPT {
#if defined(__GNUC__) || defined(__clang__)
    // One CLZ instruction on every core this file's fast path is enabled for.
    return value == 0 ? 32 : __builtin_clz(value);
#else
    int count = 0;
    while (count < 32 && (value & 0x80000000u) == 0u) {
        value <<= 1;
        ++count;
    }
    return count;
#endif
}
 
}  // namespace detail

FL_FIXED_POINT_DIVIDE_INLINE u32 divide64By32(u32 hi, u32 lo,
                                             u32 divisor) FL_NO_EXCEPT {
    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;
}
 
}  // namespace fl