common/albit.h

   1 #ifndef AL_BIT_H
   2 #define AL_BIT_H
   3
   4 #include <cstdint>
   5 #include <limits>
   6 #include <type_traits>
   7 #if !defined(__GNUC__) && (defined(_WIN32) || defined(_WIN64))
   8 #include <intrin.h>
   9 #endif
  10
  11 namespace al {
  12
  13 #ifdef __BYTE_ORDER__
  14 enum class endian {
  15     little = __ORDER_LITTLE_ENDIAN__,
  16     big = __ORDER_BIG_ENDIAN__,
  17     native = __BYTE_ORDER__
  18 };
  19
  20 #else
  21
  22 /* This doesn't support mixed-endian. */
  23 namespace detail_ {
  24 constexpr bool IsLittleEndian() noexcept
  25 {
  26     static_assert(sizeof(char) < sizeof(int), "char is too big");
  27
  28     constexpr int test_val{1};
  29     return static_cast<const char&>(test_val) ? true : false;
  30 }
  31 } // namespace detail_
  32
  33 enum class endian {
  34     big = 0,
  35     little = 1,
  36     native = detail_::IsLittleEndian() ? little : big
  37 };
  38 #endif
  39
  40
  41 /* Define popcount (population count/count 1 bits) and countr_zero (count
  42  * trailing zero bits, starting from the lsb) methods, for various integer
  43  * types.
  44  */
  45 #ifdef __GNUC__
  46
  47 namespace detail_ {
  48     inline int popcount(unsigned long long val) noexcept { return __builtin_popcountll(val); }
  49     inline int popcount(unsigned long val) noexcept { return __builtin_popcountl(val); }
  50     inline int popcount(unsigned int val) noexcept { return __builtin_popcount(val); }
  51
  52     inline int countr_zero(unsigned long long val) noexcept { return __builtin_ctzll(val); }
  53     inline int countr_zero(unsigned long val) noexcept { return __builtin_ctzl(val); }
  54     inline int countr_zero(unsigned int val) noexcept { return __builtin_ctz(val); }
  55 } // namespace detail_
  56
  57 template<typename T>
  58 inline std::enable_if_t<std::is_integral<T>::value && std::is_unsigned<T>::value,
  59 int> popcount(T v) noexcept { return detail_::popcount(v); }
  60
  61 template<typename T>
  62 inline std::enable_if_t<std::is_integral<T>::value && std::is_unsigned<T>::value,
  63 int> countr_zero(T val) noexcept
  64 { return val ? detail_::countr_zero(val) : std::numeric_limits<T>::digits; }
  65
  66 #else
  67
  68 /* There be black magics here. The popcount method is derived from
  69  * https://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel
  70  * while the ctz-utilizing-popcount algorithm is shown here
  71  * http://www.hackersdelight.org/hdcodetxt/ntz.c.txt
  72  * as the ntz2 variant. These likely aren't the most efficient methods, but
  73  * they're good enough if the GCC built-ins aren't available.
  74  */
  75 namespace detail_ {
  76     template<typename T, size_t = std::numeric_limits<T>::digits>
  77     struct fast_utype { };
  78     template<typename T>
  79     struct fast_utype<T,8> { using type = std::uint_fast8_t; };
  80     template<typename T>
  81     struct fast_utype<T,16> { using type = std::uint_fast16_t; };
  82     template<typename T>
  83     struct fast_utype<T,32> { using type = std::uint_fast32_t; };
  84     template<typename T>
  85     struct fast_utype<T,64> { using type = std::uint_fast64_t; };
  86
  87     template<typename T>
  88     constexpr T repbits(unsigned char bits) noexcept
  89     {
  90         T ret{bits};
  91         for(size_t i{1};i < sizeof(T);++i)
  92             ret = (ret<<8) | bits;
  93         return ret;
  94     }
  95 } // namespace detail_
  96
  97 template<typename T>
  98 constexpr std::enable_if_t<std::is_integral<T>::value && std::is_unsigned<T>::value,
  99 int> popcount(T val) noexcept
 100 {
 101     using fast_type = typename detail_::fast_utype<T>::type;
 102     constexpr fast_type b01010101{detail_::repbits<fast_type>(0x55)};
 103     constexpr fast_type b00110011{detail_::repbits<fast_type>(0x33)};
 104     constexpr fast_type b00001111{detail_::repbits<fast_type>(0x0f)};
 105     constexpr fast_type b00000001{detail_::repbits<fast_type>(0x01)};
 106
 107     fast_type v{fast_type{val} - ((fast_type{val} >> 1) & b01010101)};
 108     v = (v & b00110011) + ((v >> 2) & b00110011);
 109     v = (v + (v >> 4)) & b00001111;
 110     return static_cast<int>(((v * b00000001) >> ((sizeof(T)-1)*8)) & 0xff);
 111 }
 112
 113 #ifdef _WIN32
 114
 115 template<typename T>
 116 inline std::enable_if_t<std::is_integral<T>::value && std::is_unsigned<T>::value
 117     && std::numeric_limits<T>::digits <= 32,
 118 int> countr_zero(T v)
 119 {
 120     unsigned long idx{std::numeric_limits<T>::digits};
 121     _BitScanForward(&idx, static_cast<uint32_t>(v));
 122     return static_cast<int>(idx);
 123 }
 124
 125 template<typename T>
 126 inline std::enable_if_t<std::is_integral<T>::value && std::is_unsigned<T>::value
 127     && 32 < std::numeric_limits<T>::digits && std::numeric_limits<T>::digits <= 64,
 128 int> countr_zero(T v)
 129 {
 130     unsigned long idx{std::numeric_limits<T>::digits};
 131 #ifdef _WIN64
 132     _BitScanForward64(&idx, v);
 133 #else
 134     if(!_BitScanForward(&idx, static_cast<uint32_t>(v)))
 135     {
 136         if(_BitScanForward(&idx, static_cast<uint32_t>(v>>32)))
 137             idx += 32;
 138     }
 139 #endif /* _WIN64 */
 140     return static_cast<int>(idx);
 141 }
 142
 143 #else
 144
 145 template<typename T>
 146 constexpr std::enable_if_t<std::is_integral<T>::value && std::is_unsigned<T>::value,
 147 int> countr_zero(T value)
 148 { return popcount(static_cast<T>(~value & (value - 1))); }
 149
 150 #endif
 151 #endif
 152
 153 } // namespace al
 154
 155 #endif /* AL_BIT_H */