common/albit.h

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