common/albit.h

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