Created
May 10, 2024 15:05
-
-
Save iscgar/e3206bbdc183c1947487987f978992ca to your computer and use it in GitHub Desktop.
Fixed-point compile-time log2
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// 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; | |
}; |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment