arch/common/xsimd_common_bit.hpp

0001 /****************************************************************
0002  * Partial backport of `__cpp_lib_bitops == 201907L` from C++20 *
0003  ****************************************************************/
0004
0005 #ifndef XSIMD_BIT_HPP
0006 #define XSIMD_BIT_HPP
0007
0008 #include "../../config/xsimd_config.hpp"
0009
0010 #if XSIMD_CPP_VERSION > 202002L
0011
0012 #include <version>
0013
0014 #if __cpp_lib_bitops >= 201907L
0015
0016 #include <bit>
0017
0018 namespace xsimd
0019 {
0020     namespace detail
0021     {
0022         using std::countl_one;
0023         using std::countl_zero;
0024         using std::countr_one;
0025         using std::countr_zero;
0026         using std::popcount;
0027     }
0028 }
0029
0030 #endif
0031
0032 #else
0033
0034 #include <climits>
0035 #include <type_traits>
0036
0037 #ifdef __has_builtin
0038 #define XSIMD_HAS_BUILTIN(x) __has_builtin(x)
0039 #else
0040 #define XSIMD_HAS_BUILTIN(x) 0
0041 #endif
0042
0043 #ifdef _MSC_VER
0044 #include <intrin.h>
0045 #endif
0046
0047 namespace xsimd
0048 {
0049     namespace detail
0050     {
0051         // FIXME: We could do better by dispatching to the appropriate popcount instruction
0052         // depending on the arch.
0053
0054         template <class T, class = std::enable_if_t<std::is_unsigned<T>::value>>
0055         XSIMD_INLINE int popcount(T x) noexcept
0056         {
0057 #if XSIMD_HAS_BUILTIN(__builtin_popcountg)
0058             return __builtin_popcountg(x);
0059 #else
0060             XSIMD_IF_CONSTEXPR(sizeof(T) == 1)
0061             {
0062 #if XSIMD_HAS_BUILTIN(__builtin_popcount)
0063                 return __builtin_popcount(x);
0064 #elif defined(_MSC_VER)
0065                 return __popcnt(x);
0066 #else
0067                 // https://graphics.stanford.edu/~seander/bithacks.html#CountBitsSet64
0068                 return ((uint64_t)x * 0x200040008001ULL & 0x111111111111111ULL) % 0xf;
0069 #endif
0070             }
0071             else XSIMD_IF_CONSTEXPR(sizeof(T) == 2)
0072             {
0073 #if XSIMD_HAS_BUILTIN(__builtin_popcount)
0074                 return __builtin_popcount(x);
0075 #elif defined(_MSC_VER)
0076                 return __popcnt16(x);
0077 #else
0078                 // https://graphics.stanford.edu/~seander/bithacks.html#CountBitsSet64
0079                 constexpr unsigned long long msb12 = 0x1001001001001ULL;
0080                 constexpr unsigned long long mask5 = 0x84210842108421ULL;
0081
0082                 unsigned int v = (unsigned int)x;
0083
0084                 return ((v & 0xfff) * msb12 & mask5) % 0x1f
0085                     + (((v & 0xfff000) >> 12) * msb12 & mask5) % 0x1f;
0086 #endif
0087             }
0088             else XSIMD_IF_CONSTEXPR(sizeof(T) == 4)
0089             {
0090 #if XSIMD_HAS_BUILTIN(__builtin_popcount)
0091                 return __builtin_popcount(x);
0092 #elif defined(_MSC_VER)
0093                 return __popcnt(x);
0094 #else
0095                 // https://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel
0096                 x = x - ((x >> 1) & (T) ~(T)0 / 3);
0097                 x = (x & (T) ~(T)0 / 15 * 3) + ((x >> 2) & (T) ~(T)0 / 15 * 3);
0098                 x = (x + (x >> 4)) & (T) ~(T)0 / 255 * 15;
0099                 return (x * ((T) ~(T)0 / 255)) >> (sizeof(T) - 1) * CHAR_BIT;
0100 #endif
0101             }
0102             else
0103             {
0104                 // sizeof(T) == 8
0105 #if XSIMD_HAS_BUILTIN(__builtin_popcountll)
0106                 return __builtin_popcountll(x);
0107 #elif XSIMD_HAS_BUILTIN(__builtin_popcount)
0108                 return __builtin_popcount((unsigned int)x) + __builtin_popcount((unsigned int)(x >> 32));
0109 #elif defined(_MSC_VER)
0110 #ifdef _M_X64
0111                 return (int)__popcnt64(x);
0112 #else
0113                 return (int)(__popcnt((unsigned int)x) + __popcnt((unsigned int)(x >> 32)));
0114 #endif
0115 #else
0116                 // https://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel
0117                 x = x - ((x >> 1) & (T) ~(T)0 / 3);
0118                 x = (x & (T) ~(T)0 / 15 * 3) + ((x >> 2) & (T) ~(T)0 / 15 * 3);
0119                 x = (x + (x >> 4)) & (T) ~(T)0 / 255 * 15;
0120                 return (x * ((T) ~(T)0 / 255)) >> (sizeof(T) - 1) * CHAR_BIT;
0121 #endif
0122             }
0123 #endif
0124         }
0125
0126         template <class T, class = std::enable_if_t<std::is_unsigned<T>::value>>
0127         XSIMD_INLINE int countl_zero(T x) noexcept
0128         {
0129 #if XSIMD_HAS_BUILTIN(__builtin_clzg)
0130             return __builtin_clzg(x, (int)(sizeof(T) * CHAR_BIT));
0131 #else
0132             if (x == 0)
0133                 return sizeof(T) * CHAR_BIT;
0134
0135             XSIMD_IF_CONSTEXPR(sizeof(T) <= 4)
0136             {
0137 #if XSIMD_HAS_BUILTIN(__builtin_clz)
0138                 return __builtin_clz((unsigned int)x) - (4 - sizeof(T)) * CHAR_BIT;
0139 #elif defined(_MSC_VER)
0140                 unsigned long index;
0141                 _BitScanReverse(&index, (unsigned long)x);
0142                 return sizeof(T) * CHAR_BIT - index - 1;
0143 #else
0144                 x |= x >> 1;
0145                 x |= x >> 2;
0146                 x |= x >> 4;
0147                 XSIMD_IF_CONSTEXPR(sizeof(T) >= 2)
0148                 {
0149                     x |= x >> 8;
0150                 }
0151                 XSIMD_IF_CONSTEXPR(sizeof(T) >= 4)
0152                 {
0153                     x |= x >> 16;
0154                 }
0155                 return sizeof(T) * CHAR_BIT - popcount(x);
0156 #endif
0157             }
0158             else
0159             {
0160                 // sizeof(T) == 8
0161 #if XSIMD_HAS_BUILTIN(__builtin_clzll)
0162                 return __builtin_clzll((unsigned long long)x);
0163 #elif defined(_MSC_VER) && defined(_M_X64)
0164                 unsigned long index;
0165                 _BitScanReverse64(&index, (unsigned long long)x);
0166                 return sizeof(T) * CHAR_BIT - index - 1;
0167 #else
0168                 x |= x >> 1;
0169                 x |= x >> 2;
0170                 x |= x >> 4;
0171                 x |= x >> 8;
0172                 x |= x >> 16;
0173                 x |= x >> 32;
0174                 return sizeof(T) * CHAR_BIT - popcount(x);
0175 #endif
0176             }
0177 #endif
0178         }
0179
0180         template <class T, class = std::enable_if_t<std::is_unsigned<T>::value>>
0181         XSIMD_INLINE int countl_one(T x) noexcept
0182         {
0183             return countl_zero(T(~x));
0184         }
0185
0186         template <class T, class = std::enable_if_t<std::is_unsigned<T>::value>>
0187         XSIMD_INLINE int countr_zero(T x) noexcept
0188         {
0189 #if XSIMD_HAS_BUILTIN(__builtin_ctzg)
0190             return __builtin_ctzg(x, (int)(sizeof(T) * CHAR_BIT));
0191 #else
0192             if (x == 0)
0193                 return sizeof(T) * CHAR_BIT;
0194
0195             XSIMD_IF_CONSTEXPR(sizeof(T) <= 4)
0196             {
0197 #if XSIMD_HAS_BUILTIN(__builtin_ctz)
0198                 return __builtin_ctz((unsigned int)x);
0199 #elif defined(_MSC_VER)
0200                 unsigned long index;
0201                 _BitScanForward(&index, (unsigned long)x);
0202                 return index;
0203 #endif
0204             }
0205             else
0206             {
0207                 // sizeof(T) == 8
0208 #if XSIMD_HAS_BUILTIN(__builtin_ctzll)
0209                 return __builtin_ctzll((unsigned long long)x);
0210 #elif defined(_MSC_VER) && defined(_M_X64)
0211                 unsigned long index;
0212                 _BitScanForward64(&index, (unsigned long long)x);
0213                 return index;
0214 #endif
0215             }
0216
0217             // https://graphics.stanford.edu/~seander/bithacks.html#ZerosOnRightMultLookup
0218             return popcount((T)((x & -x) - 1));
0219 #endif
0220         }
0221
0222         template <class T, class = std::enable_if_t<std::is_unsigned<T>::value>>
0223         XSIMD_INLINE int countr_one(T x) noexcept
0224         {
0225             return countr_zero(T(~x));
0226         }
0227
0228     }
0229 }
0230
0231 #endif
0232 #endif