aboutsummaryrefslogtreecommitdiffstats
path: root/common/albit.h
diff options
context:
space:
mode:
authorChris Robinson <[email protected]>2021-01-22 04:58:42 -0800
committerChris Robinson <[email protected]>2021-01-22 04:58:42 -0800
commitda59ad51057ce7343e3db4632e8679e1e537779d (patch)
tree6b4c1f5bd5d6b4bd4b83b9bc290e63ca837f8bc0 /common/albit.h
parent5ff5fd8eccbdc5888b350059cb1f341a33ddf05f (diff)
Make PopCount and CountTrailingZeros more standard-like
Diffstat (limited to 'common/albit.h')
-rw-r--r--common/albit.h108
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 */