diff options
Diffstat (limited to 'vendor/github.com/byzantine-lab/mcl/include/cybozu/bit_operation.hpp')
-rw-r--r-- | vendor/github.com/byzantine-lab/mcl/include/cybozu/bit_operation.hpp | 139 |
1 files changed, 139 insertions, 0 deletions
diff --git a/vendor/github.com/byzantine-lab/mcl/include/cybozu/bit_operation.hpp b/vendor/github.com/byzantine-lab/mcl/include/cybozu/bit_operation.hpp new file mode 100644 index 000000000..865c1e47d --- /dev/null +++ b/vendor/github.com/byzantine-lab/mcl/include/cybozu/bit_operation.hpp @@ -0,0 +1,139 @@ +#pragma once +/** + @file + @brief bit operation +*/ +#include <assert.h> +#include <cybozu/inttype.hpp> + +#if (CYBOZU_HOST == CYBOZU_HOST_INTEL) + #if defined(_WIN32) + #include <intrin.h> + #elif defined(__linux__) || defined(__CYGWIN__) || defined(__clang__) + #include <x86intrin.h> + #elif defined(__GNUC__) + #include <emmintrin.h> + #endif +#endif + +namespace cybozu { + +namespace bit_op_local { + +template<bool equalTo8> +struct Tag {}; + +// sizeof(T) < 8 +template<> +struct Tag<false> { + template<class T> + static inline int bsf(T x) + { +#if defined(_MSC_VER) + unsigned long out; + _BitScanForward(&out, x); +#pragma warning(suppress: 6102) + return out; +#else + return __builtin_ctz(x); +#endif + } + template<class T> + static inline int bsr(T x) + { +#if defined(_MSC_VER) + unsigned long out; + _BitScanReverse(&out, x); +#pragma warning(suppress: 6102) + return out; +#else + return __builtin_clz(x) ^ 0x1f; +#endif + } +}; + +// sizeof(T) == 8 +template<> +struct Tag<true> { + template<class T> + static inline int bsf(T x) + { +#if defined(_MSC_VER) && defined(_WIN64) + unsigned long out; + _BitScanForward64(&out, x); +#pragma warning(suppress: 6102) + return out; +#elif defined(__x86_64__) + return __builtin_ctzll(x); +#else + const uint32_t L = uint32_t(x); + if (L) return Tag<false>::bsf(L); + const uint32_t H = uint32_t(x >> 32); + return Tag<false>::bsf(H) + 32; +#endif + } + template<class T> + static inline int bsr(T x) + { +#if defined(_MSC_VER) && defined(_WIN64) + unsigned long out; + _BitScanReverse64(&out, x); +#pragma warning(suppress: 6102) + return out; +#elif defined(__x86_64__) + return __builtin_clzll(x) ^ 0x3f; +#else + const uint32_t H = uint32_t(x >> 32); + if (H) return Tag<false>::bsr(H) + 32; + const uint32_t L = uint32_t(x); + return Tag<false>::bsr(L); +#endif + } +}; + +} // bit_op_local + +template<class T> +int bsf(T x) +{ + return bit_op_local::Tag<sizeof(T) == 8>::bsf(x); +} +template<class T> +int bsr(T x) +{ + return bit_op_local::Tag<sizeof(T) == 8>::bsr(x); +} + +template<class T> +uint64_t makeBitMask64(T x) +{ + assert(x < 64); + return (uint64_t(1) << x) - 1; +} + +template<class T> +uint32_t popcnt(T x); + +template<> +inline uint32_t popcnt<uint32_t>(uint32_t x) +{ +#if defined(_MSC_VER) + return static_cast<uint32_t>(_mm_popcnt_u32(x)); +#else + return static_cast<uint32_t>(__builtin_popcount(x)); +#endif +} + +template<> +inline uint32_t popcnt<uint64_t>(uint64_t x) +{ +#if defined(__x86_64__) + return static_cast<uint32_t>(__builtin_popcountll(x)); +#elif defined(_WIN64) + return static_cast<uint32_t>(_mm_popcnt_u64(x)); +#else + return popcnt<uint32_t>(static_cast<uint32_t>(x)) + popcnt<uint32_t>(static_cast<uint32_t>(x >> 32)); +#endif +} + +} // cybozu |