multiprecision/detail/bitscan.hpp

0001 ///////////////////////////////////////////////////////////////
0002 //  Copyright 2013 John Maddock. Distributed under the Boost
0003 //  Software License, Version 1.0. (See accompanying file
0004 //  LICENSE_1_0.txt or copy at https://www.boost.org/LICENSE_1_0.txt
0005 //
0006 // Comparison operators for cpp_int_backend:
0007 //
0008 #ifndef BOOST_MP_DETAIL_BITSCAN_HPP
0009 #define BOOST_MP_DETAIL_BITSCAN_HPP
0010
0011 #include <cstdint>
0012 #include <climits>
0013 #include <type_traits>
0014 #include <boost/multiprecision/detail/endian.hpp>
0015 #include <boost/multiprecision/detail/standalone_config.hpp>
0016
0017 #if (defined(BOOST_MSVC) || (defined(__clang__) && defined(__c2__)) || (defined(BOOST_INTEL) && defined(_MSC_VER))) && (defined(_M_IX86) || defined(_M_X64))
0018 #include <intrin.h>
0019 #endif
0020
0021 namespace boost { namespace multiprecision { namespace detail {
0022
0023 template <class Unsigned>
0024 inline BOOST_MP_CXX14_CONSTEXPR std::size_t find_lsb_default(Unsigned mask)
0025 {
0026    std::size_t result = 0;
0027    while (!(mask & 1u))
0028    {
0029       mask >>= 1;
0030       ++result;
0031    }
0032    return result;
0033 }
0034
0035 template <class Unsigned>
0036 inline BOOST_MP_CXX14_CONSTEXPR std::size_t find_msb_default(Unsigned mask)
0037 {
0038    std::size_t index = 0;
0039    while (mask)
0040    {
0041       ++index;
0042       mask >>= 1;
0043    }
0044    return --index;
0045 }
0046
0047 template <class Unsigned>
0048 inline BOOST_MP_CXX14_CONSTEXPR std::size_t find_lsb(Unsigned mask, const std::integral_constant<int, 0>&)
0049 {
0050    return find_lsb_default(mask);
0051 }
0052
0053 template <class Unsigned>
0054 inline BOOST_MP_CXX14_CONSTEXPR std::size_t find_msb(Unsigned mask, const std::integral_constant<int, 0>&)
0055 {
0056    return find_msb_default(mask);
0057 }
0058
0059 #if (defined(BOOST_MSVC) || (defined(__clang__) && defined(__c2__)) || (defined(BOOST_INTEL) && defined(_MSC_VER))) && (defined(_M_IX86) || defined(_M_X64))
0060
0061 #pragma intrinsic(_BitScanForward, _BitScanReverse)
0062
0063 BOOST_FORCEINLINE std::size_t find_lsb(unsigned long mask, const std::integral_constant<int, 1>&)
0064 {
0065    unsigned long result;
0066    _BitScanForward(&result, mask);
0067    return result;
0068 }
0069
0070 BOOST_FORCEINLINE std::size_t find_msb(unsigned long mask, const std::integral_constant<int, 1>&)
0071 {
0072    unsigned long result;
0073    _BitScanReverse(&result, mask);
0074    return result;
0075 }
0076 #ifdef _M_X64
0077
0078 #pragma intrinsic(_BitScanForward64, _BitScanReverse64)
0079
0080 BOOST_FORCEINLINE std::size_t find_lsb(unsigned __int64 mask, const std::integral_constant<int, 2>&)
0081 {
0082    unsigned long result;
0083    _BitScanForward64(&result, mask);
0084    return result;
0085 }
0086 template <class Unsigned>
0087 BOOST_FORCEINLINE std::size_t find_msb(Unsigned mask, const std::integral_constant<int, 2>&)
0088 {
0089    unsigned long result;
0090    _BitScanReverse64(&result, mask);
0091    return result;
0092 }
0093 #endif
0094
0095 template <class Unsigned>
0096 BOOST_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR std::size_t find_lsb(Unsigned mask)
0097 {
0098    using ui_type = typename boost::multiprecision::detail::make_unsigned<Unsigned>::type;
0099    using tag_type = typename std::conditional<
0100        sizeof(Unsigned) <= sizeof(unsigned long),
0101        std::integral_constant<int, 1>,
0102 #ifdef _M_X64
0103        typename std::conditional<
0104            sizeof(Unsigned) <= sizeof(__int64),
0105            std::integral_constant<int, 2>,
0106            std::integral_constant<int, 0> >::type
0107 #else
0108        std::integral_constant<int, 0>
0109 #endif
0110        >::type;
0111 #ifndef BOOST_MP_NO_CONSTEXPR_DETECTION
0112    if (BOOST_MP_IS_CONST_EVALUATED(mask))
0113    {
0114       return find_lsb_default(mask);
0115    }
0116    else
0117 #endif
0118       return find_lsb(static_cast<ui_type>(mask), tag_type());
0119 }
0120
0121 template <class Unsigned>
0122 BOOST_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR std::size_t find_msb(Unsigned mask)
0123 {
0124    using ui_type = typename boost::multiprecision::detail::make_unsigned<Unsigned>::type;
0125    using tag_type = typename std::conditional<
0126        sizeof(Unsigned) <= sizeof(unsigned long),
0127        std::integral_constant<int, 1>,
0128 #ifdef _M_X64
0129        typename std::conditional<
0130            sizeof(Unsigned) <= sizeof(__int64),
0131            std::integral_constant<int, 2>,
0132            std::integral_constant<int, 0> >::type
0133 #else
0134        std::integral_constant<int, 0>
0135 #endif
0136        >::type;
0137 #ifndef BOOST_MP_NO_CONSTEXPR_DETECTION
0138    if (BOOST_MP_IS_CONST_EVALUATED(mask))
0139    {
0140       return find_msb_default(mask);
0141    }
0142    else
0143 #endif
0144       return find_msb(static_cast<ui_type>(mask), tag_type());
0145 }
0146
0147 #elif defined(BOOST_GCC) || defined(__clang__) || (defined(BOOST_INTEL) && defined(__GNUC__))
0148
0149 BOOST_FORCEINLINE std::size_t find_lsb(std::size_t mask, std::integral_constant<int, 1> const&)
0150 {
0151    return static_cast<std::size_t>(__builtin_ctz(static_cast<unsigned int>(mask)));
0152 }
0153 BOOST_FORCEINLINE std::size_t find_lsb(unsigned long mask, std::integral_constant<int, 2> const&)
0154 {
0155    return static_cast<std::size_t>(__builtin_ctzl(static_cast<unsigned long>(mask)));
0156 }
0157 BOOST_FORCEINLINE std::size_t find_lsb(unsigned long long mask, std::integral_constant<int, 3> const&)
0158 {
0159    return static_cast<std::size_t>(__builtin_ctzll(static_cast<unsigned long long>(mask)));
0160 }
0161 BOOST_FORCEINLINE std::size_t find_msb(std::size_t mask, std::integral_constant<int, 1> const&)
0162 {
0163    return static_cast<std::size_t>(static_cast<std::size_t>(sizeof(unsigned) * static_cast<std::size_t>(CHAR_BIT) - 1u) - static_cast<std::size_t>(__builtin_clz(static_cast<unsigned int>(mask))));
0164 }
0165 BOOST_FORCEINLINE std::size_t find_msb(unsigned long mask, std::integral_constant<int, 2> const&)
0166 {
0167    return static_cast<std::size_t>(static_cast<std::size_t>(sizeof(unsigned long) * static_cast<std::size_t>(CHAR_BIT) - 1u) - static_cast<std::size_t>(__builtin_clzl(static_cast<unsigned long>(mask))));
0168 }
0169 BOOST_FORCEINLINE std::size_t find_msb(unsigned long long mask, std::integral_constant<int, 3> const&)
0170 {
0171    return static_cast<std::size_t>(static_cast<std::size_t>(sizeof(unsigned long long) * static_cast<std::size_t>(CHAR_BIT) - 1u) - static_cast<std::size_t>(__builtin_clzll(static_cast<unsigned long long>(mask))));
0172 }
0173 #ifdef BOOST_HAS_INT128
0174
0175 BOOST_FORCEINLINE std::size_t find_msb(uint128_type mask, std::integral_constant<int, 0> const&)
0176 {
0177    union
0178    {
0179       uint128_type    v;
0180       std::uint64_t sv[2];
0181    } val;
0182    val.v = mask;
0183 #if BOOST_MP_ENDIAN_LITTLE_BYTE
0184    if (val.sv[1])
0185       return find_msb(val.sv[1], std::integral_constant<int, 3>()) + 64;
0186    return find_msb(val.sv[0], std::integral_constant<int, 3>());
0187 #else
0188    if (val.sv[0])
0189       return find_msb(val.sv[0], std::integral_constant<int, 3>()) + 64;
0190    return find_msb(val.sv[1], std::integral_constant<int, 3>());
0191 #endif
0192 }
0193 BOOST_FORCEINLINE std::size_t find_lsb(uint128_type mask, std::integral_constant<int, 0> const&)
0194 {
0195    union
0196    {
0197       uint128_type    v;
0198       std::uint64_t sv[2];
0199    } val;
0200    val.v = mask;
0201 #if BOOST_MP_ENDIAN_LITTLE_BYTE
0202    if (val.sv[0] == 0)
0203       return find_lsb(val.sv[1], std::integral_constant<int, 3>()) + 64;
0204    return find_lsb(val.sv[0], std::integral_constant<int, 3>());
0205 #else
0206    if (val.sv[1] == 0)
0207       return find_lsb(val.sv[0], std::integral_constant<int, 3>()) + 64;
0208    return find_lsb(val.sv[1], std::integral_constant<int, 3>());
0209 #endif
0210 }
0211 #endif
0212
0213 template <class Unsigned>
0214 BOOST_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR std::size_t find_lsb(Unsigned mask)
0215 {
0216    using ui_type = typename boost::multiprecision::detail::make_unsigned<Unsigned>::type;
0217    using tag_type = typename std::conditional<
0218        sizeof(Unsigned) <= sizeof(unsigned),
0219        std::integral_constant<int, 1>,
0220        typename std::conditional<
0221            sizeof(Unsigned) <= sizeof(unsigned long),
0222            std::integral_constant<int, 2>,
0223            typename std::conditional<
0224                sizeof(Unsigned) <= sizeof(unsigned long long),
0225                std::integral_constant<int, 3>,
0226                std::integral_constant<int, 0> >::type>::type>::type;
0227 #ifndef BOOST_MP_NO_CONSTEXPR_DETECTION
0228    if (BOOST_MP_IS_CONST_EVALUATED(mask))
0229    {
0230       return find_lsb_default(mask);
0231    }
0232    else
0233 #endif
0234    return find_lsb(static_cast<ui_type>(mask), tag_type());
0235 }
0236 template <class Unsigned>
0237 BOOST_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR std::size_t find_msb(Unsigned mask)
0238 {
0239    using ui_type = typename boost::multiprecision::detail::make_unsigned<Unsigned>::type;
0240    using tag_type = typename std::conditional<
0241        sizeof(Unsigned) <= sizeof(unsigned),
0242        std::integral_constant<int, 1>,
0243        typename std::conditional<
0244            sizeof(Unsigned) <= sizeof(unsigned long),
0245            std::integral_constant<int, 2>,
0246            typename std::conditional<
0247                sizeof(Unsigned) <= sizeof(unsigned long long),
0248                std::integral_constant<int, 3>,
0249                std::integral_constant<int, 0> >::type>::type>::type;
0250 #ifndef BOOST_MP_NO_CONSTEXPR_DETECTION
0251    if (BOOST_MP_IS_CONST_EVALUATED(mask))
0252    {
0253       return find_msb_default(mask);
0254    }
0255    else
0256 #endif
0257       return find_msb(static_cast<ui_type>(mask), tag_type());
0258 }
0259 #elif defined(BOOST_INTEL)
0260 BOOST_FORCEINLINE std::size_t find_lsb(std::size_t mask, std::integral_constant<int, 1> const&)
0261 {
0262    return _bit_scan_forward(mask);
0263 }
0264 BOOST_FORCEINLINE std::size_t find_msb(std::size_t mask, std::integral_constant<int, 1> const&)
0265 {
0266    return _bit_scan_reverse(mask);
0267 }
0268 template <class Unsigned>
0269 BOOST_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR std::size_t find_lsb(Unsigned mask)
0270 {
0271    using ui_type = typename boost::multiprecision::detail::make_unsigned<Unsigned>::type;
0272    using tag_type = typename std::conditional<
0273        sizeof(Unsigned) <= sizeof(unsigned),
0274        std::integral_constant<int, 1>,
0275        std::integral_constant<int, 0> >::type;
0276 #ifndef BOOST_MP_NO_CONSTEXPR_DETECTION
0277    if (BOOST_MP_IS_CONST_EVALUATED(mask))
0278    {
0279       return find_lsb_default(mask);
0280    }
0281    else
0282 #endif
0283       return find_lsb(static_cast<ui_type>(mask), tag_type());
0284 }
0285 template <class Unsigned>
0286 BOOST_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR std::size_t find_msb(Unsigned mask)
0287 {
0288    using ui_type = typename boost::multiprecision::detail::make_unsigned<Unsigned>::type;
0289    using tag_type = typename std::conditional<
0290        sizeof(Unsigned) <= sizeof(unsigned),
0291        std::integral_constant<int, 1>,
0292        std::integral_constant<int, 0> >::type;
0293 #ifndef BOOST_MP_NO_CONSTEXPR_DETECTION
0294    if (BOOST_MP_IS_CONST_EVALUATED(mask))
0295    {
0296       return find_msb_default(mask);
0297    }
0298    else
0299 #endif
0300       return find_msb(static_cast<ui_type>(mask), tag_type());
0301 }
0302 #else
0303 template <class Unsigned>
0304 BOOST_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR std::size_t find_lsb(Unsigned mask)
0305 {
0306    return find_lsb(mask, std::integral_constant<int, 0>());
0307 }
0308 template <class Unsigned>
0309 BOOST_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR std::size_t find_msb(Unsigned mask)
0310 {
0311    return find_msb(mask, std::integral_constant<int, 0>());
0312 }
0313 #endif
0314
0315 }}} // namespace boost::multiprecision::detail
0316
0317 #endif