diff options
author | Chris Robinson <[email protected]> | 2021-01-22 04:58:42 -0800 |
---|---|---|
committer | Chris Robinson <[email protected]> | 2021-01-22 04:58:42 -0800 |
commit | da59ad51057ce7343e3db4632e8679e1e537779d (patch) | |
tree | 6b4c1f5bd5d6b4bd4b83b9bc290e63ca837f8bc0 /common/albit.h | |
parent | 5ff5fd8eccbdc5888b350059cb1f341a33ddf05f (diff) |
Make PopCount and CountTrailingZeros more standard-like
Diffstat (limited to 'common/albit.h')
-rw-r--r-- | common/albit.h | 108 |
1 files changed, 108 insertions, 0 deletions
diff --git a/common/albit.h b/common/albit.h index 225c0b89..c54bb31a 100644 --- a/common/albit.h +++ b/common/albit.h @@ -1,6 +1,12 @@ #ifndef AL_BIT_H #define AL_BIT_H +#include <limits> +#include <type_traits> +#if !defined(__GNUC__) && (defined(_WIN32) || defined(_WIN64)) +#include <intrin.h> +#endif + namespace al { #ifdef __BYTE_ORDER__ @@ -30,6 +36,108 @@ enum class endian { }; #endif + +/* Define popcount (population count/count 1 bits) and countr_zero (count + * trailing zero bits, starting from the lsb) methods, for various integer + * types. + */ +#ifdef __GNUC__ + +namespace detail_ { + inline int popcount(unsigned long long val) noexcept { return __builtin_popcountll(val); } + inline int popcount(unsigned long val) noexcept { return __builtin_popcountl(val); } + inline int popcount(unsigned int val) noexcept { return __builtin_popcount(val); } + + inline int countr_zero(unsigned long long val) noexcept { return __builtin_ctzll(val); } + inline int countr_zero(unsigned long val) noexcept { return __builtin_ctzl(val); } + inline int countr_zero(unsigned int val) noexcept { return __builtin_ctz(val); } +} // namespace detail_ + +template<typename T> +inline std::enable_if_t<std::is_integral<T>::value && std::is_unsigned<T>::value, +int> popcount(T v) noexcept { return detail_::popcount(v); } + +template<typename T> +inline std::enable_if_t<std::is_integral<T>::value && std::is_unsigned<T>::value, +int> countr_zero(T val) noexcept +{ return val ? detail_::countr_zero(val) : std::numeric_limits<T>::digits; } + +#else + +/* There be black magics here. The popcount method is derived from + * https://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel + * while the ctz-utilizing-popcount algorithm is shown here + * http://www.hackersdelight.org/hdcodetxt/ntz.c.txt + * as the ntz2 variant. These likely aren't the most efficient methods, but + * they're good enough if the GCC built-ins aren't available. + */ +namespace detail_ { + template<typename T> + constexpr T repbits(unsigned char bits) noexcept + { + T ret{bits}; + for(size_t i{1};i < sizeof(T);++i) + ret = (ret<<8) | bits; + return ret; + } +} // namespace detail_ + +template<typename T> +constexpr std::enable_if_t<std::is_integral<T>::value && std::is_unsigned<T>::value, +int> popcount(T v) noexcept +{ + constexpr T m55{detail_::repbits<T>(0x55)}; + constexpr T m33{detail_::repbits<T>(0x33)}; + constexpr T m0f{detail_::repbits<T>(0x0f)}; + constexpr T m01{detail_::repbits<T>(0x01)}; + + v = v - ((v >> 1) & m55); + v = (v & m33) + ((v >> 2) & m33); + v = (v + (v >> 4)) & m0f; + return static_cast<int>((v * m01) >> ((sizeof(T)-1)*8)); +} + +#if defined(_WIN64) + +template<typename T> +inline std::enable_if_t<std::is_integral<T>::value && std::is_unsigned<T>::value, +int> countr_zero(T v) +{ + unsigned long idx{std::numeric_limits<T>::digits}; + if /*constexpr*/(std::numeric_limits<T>::digits <= 32) + _BitScanForward(&idx, static_cast<uint32_t>(v)); + else // std::numeric_limits<T>::digits > 32 + _BitScanForward64(&idx, v); + return static_cast<int>(idx); +} + +#elif defined(_WIN32) + +template<typename T> +inline std::enable_if_t<std::is_integral<T>::value && std::is_unsigned<T>::value, +int> countr_zero(T v) +{ + unsigned long idx{std::numeric_limits<T>::digits}; + if /*constexpr*/(std::numeric_limits<T>::digits <= 32) + _BitScanForward(&idx, static_cast<uint32_t>(v)); + else if(!_BitScanForward(&idx, static_cast<uint32_t>(v))) + { + if(_BitScanForward(&idx, static_cast<uint32_t>(v>>32))) + idx += 32; + } + return static_cast<int>(idx); +} + +#else + +template<typename T> +constexpr std::enable_if_t<std::is_integral<T>::value && std::is_unsigned<T>::value, +int> countr_zero(T value) +{ return popcount(static_cast<T>(~value & (value - 1))); } + +#endif +#endif + } // namespace al #endif /* AL_BIT_H */ |