Fixed-point compile-time log2

fixed-log2.hpp

// A quick and dirty hack to caluclate 32-bit fixed-point log2 at compile-time
// for defining constants and doing template metaprogramming where a fractional
// result is required.
// Apart from the static assertion, this code can be used even in C++98.
//
// NOTE: The first argument to `FixedPointLog2` should already be in fixed-point
//       form (e.g. in order to calculate the log2 of 3 with the result in the
//       form s15.16, you should use `FixedPointLog2<(3 << 16), 16>`.

#include <stddef.h>
#include <stdint.h>

namespace detail
{
    template<bool ScaleNext, uint32_t X, int32_t Y, uint32_t Mask>
    struct Log2ScaleUp
    {
    private:
        typedef Log2ScaleUp<(X < Mask), (X << 1), (Y - int32_t(Mask)), Mask> Next;

    public:
        static const uint32_t x = Next::x;
        static const int32_t y = Next::y;
    };

    template<uint32_t X, int32_t Y, uint32_t Mask>
    struct Log2ScaleUp<false, X, Y, Mask>
    {
        static const uint32_t x = X;
        static const int32_t y = Y;
    };

    template<bool ScaleNext, uint32_t X, int32_t Y, uint32_t Mask1, uint64_t Mask2>
    struct Log2ScaleDown
    {
    private:
        static const uint32_t NX = X >> 1;
        typedef Log2ScaleDown<(NX >= Mask2), NX, (Y + Mask1), Mask1, Mask2> Next;

    public:
        static const uint32_t x = Next::x;
        static const int32_t y = Next::y;
    };

    template<uint32_t X, int32_t Y, uint32_t Mask1, uint64_t Mask2>
    struct Log2ScaleDown<false, X, Y, Mask1, Mask2>
    {
        static const uint32_t x = X;
        static const int32_t y = Y;
    };

    template<uint64_t Z, int32_t Y, int32_t B, uint64_t Mask, size_t FracBits>
    struct Log2Adjust
    {
    private:
        static const uint64_t NZ = (Z * Z) >> FracBits;

    public:
        static const int32_t value = Log2Adjust<
            (NZ >> (NZ >= Mask ? 1 : 0)),
            (Y + (NZ >= Mask ? B : 0)),
            (B >> 1), Mask, FracBits>::value;
    };

    template<uint64_t Z, int32_t Y, uint64_t Mask, size_t FracBits>
    struct Log2Adjust<Z, Y, 0, Mask, FracBits>
    {
        static const int32_t value = Y;
    };
} // namespace detail

template<uint32_t X, size_t FracBits>
class FixedPointLog2
{
    static_assert(X != 0, "");
    static_assert(FracBits > 0 && FracBits < 32, "");

    static const uint32_t MASK1 = uint32_t(1) << FracBits;
    static const uint64_t MASK2 = uint64_t(2) << FracBits;

    typedef detail::Log2ScaleUp<(X < MASK1), X, 0, MASK1> ScaledUp;
    typedef detail::Log2ScaleDown<(ScaledUp::x >= MASK2), ScaledUp::x, ScaledUp::y, MASK1, MASK2> ScaledDown;

public:
    static const int32_t value = detail::Log2Adjust<
        ScaledDown::x, ScaledDown::y, int32_t(MASK1 >> 1), MASK2, FracBits>::value;
};