common/albit.h

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