7 #if !defined(__GNUC__) && (defined(_WIN32) || defined(_WIN64))
15 little = __ORDER_LITTLE_ENDIAN__,
16 big = __ORDER_BIG_ENDIAN__,
17 native = __BYTE_ORDER__
22 /* This doesn't support mixed-endian. */
24 constexpr bool IsLittleEndian() noexcept
26 static_assert(sizeof(char) < sizeof(int), "char is too big");
28 constexpr int test_val{1};
29 return static_cast<const char&>(test_val) ? true : false;
31 } // namespace detail_
36 native = detail_::IsLittleEndian() ? little : big
41 /* Define popcount (population count/count 1 bits) and countr_zero (count
42 * trailing zero bits, starting from the lsb) methods, for various integer
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); }
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_
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); }
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; }
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.
76 template<typename T, size_t = std::numeric_limits<T>::digits>
77 struct fast_utype { };
79 struct fast_utype<T,8> { using type = std::uint_fast8_t; };
81 struct fast_utype<T,16> { using type = std::uint_fast16_t; };
83 struct fast_utype<T,32> { using type = std::uint_fast32_t; };
85 struct fast_utype<T,64> { using type = std::uint_fast64_t; };
88 constexpr T repbits(unsigned char bits) noexcept
91 for(size_t i{1};i < sizeof(T);++i)
92 ret = (ret<<8) | bits;
95 } // namespace detail_
98 constexpr std::enable_if_t<std::is_integral<T>::value && std::is_unsigned<T>::value,
99 int> popcount(T val) noexcept
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)};
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);
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)
120 unsigned long idx{std::numeric_limits<T>::digits};
121 _BitScanForward(&idx, static_cast<uint32_t>(v));
122 return static_cast<int>(idx);
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)
130 unsigned long idx{std::numeric_limits<T>::digits};
132 _BitScanForward64(&idx, v);
134 if(!_BitScanForward(&idx, static_cast<uint32_t>(v)))
136 if(_BitScanForward(&idx, static_cast<uint32_t>(v>>32)))
140 return static_cast<int>(idx);
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))); }
155 #endif /* AL_BIT_H */