boost/multiprecision/detail/bitscan.hpp

   1 ///////////////////////////////////////////////////////////////
   2 //  Copyright 2013 John Maddock. Distributed under the Boost
   3 //  Software License, Version 1.0. (See accompanying file
   4 //  LICENSE_1_0.txt or copy at https://www.boost.org/LICENSE_1_0.txt
   5 //
   6 // Comparison operators for cpp_int_backend:
   7 //
   8 #ifndef BOOST_MP_DETAIL_BITSCAN_HPP
   9 #define BOOST_MP_DETAIL_BITSCAN_HPP
  10
  11 #include <boost/predef/other/endian.h>
  12 #include <boost/cstdint.hpp>
  13
  14 #if (defined(BOOST_MSVC) || (defined(__clang__) && defined(__c2__)) || (defined(BOOST_INTEL) && defined(_MSC_VER))) && (defined(_M_IX86) || defined(_M_X64))
  15 #include <intrin.h>
  16 #endif
  17
  18 namespace boost { namespace multiprecision { namespace detail {
  19
  20 template <class Unsigned>
  21 inline BOOST_MP_CXX14_CONSTEXPR unsigned find_lsb_default(Unsigned mask)
  22 {
  23    unsigned result = 0;
  24    while (!(mask & 1u))
  25    {
  26       mask >>= 1;
  27       ++result;
  28    }
  29    return result;
  30 }
  31
  32 template <class Unsigned>
  33 inline BOOST_MP_CXX14_CONSTEXPR unsigned find_msb_default(Unsigned mask)
  34 {
  35    unsigned index = 0;
  36    while (mask)
  37    {
  38       ++index;
  39       mask >>= 1;
  40    }
  41    return --index;
  42 }
  43
  44 template <class Unsigned>
  45 inline BOOST_MP_CXX14_CONSTEXPR unsigned find_lsb(Unsigned mask, const mpl::int_<0>&)
  46 {
  47    return find_lsb_default(mask);
  48 }
  49
  50 template <class Unsigned>
  51 inline BOOST_MP_CXX14_CONSTEXPR unsigned find_msb(Unsigned mask, const mpl::int_<0>&)
  52 {
  53    return find_msb_default(mask);
  54 }
  55
  56 #if (defined(BOOST_MSVC) || (defined(__clang__) && defined(__c2__)) || (defined(BOOST_INTEL) && defined(_MSC_VER))) && (defined(_M_IX86) || defined(_M_X64))
  57
  58 #pragma intrinsic(_BitScanForward, _BitScanReverse)
  59
  60 BOOST_FORCEINLINE unsigned find_lsb(unsigned long mask, const mpl::int_<1>&)
  61 {
  62    unsigned long result;
  63    _BitScanForward(&result, mask);
  64    return result;
  65 }
  66
  67 BOOST_FORCEINLINE unsigned find_msb(unsigned long mask, const mpl::int_<1>&)
  68 {
  69    unsigned long result;
  70    _BitScanReverse(&result, mask);
  71    return result;
  72 }
  73 #ifdef _M_X64
  74
  75 #pragma intrinsic(_BitScanForward64, _BitScanReverse64)
  76
  77 BOOST_FORCEINLINE unsigned find_lsb(unsigned __int64 mask, const mpl::int_<2>&)
  78 {
  79    unsigned long result;
  80    _BitScanForward64(&result, mask);
  81    return result;
  82 }
  83 template <class Unsigned>
  84 BOOST_FORCEINLINE unsigned find_msb(Unsigned mask, const mpl::int_<2>&)
  85 {
  86    unsigned long result;
  87    _BitScanReverse64(&result, mask);
  88    return result;
  89 }
  90 #endif
  91
  92 template <class Unsigned>
  93 BOOST_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR unsigned find_lsb(Unsigned mask)
  94 {
  95    typedef typename make_unsigned<Unsigned>::type ui_type;
  96    typedef typename mpl::if_c<
  97        sizeof(Unsigned) <= sizeof(unsigned long),
  98        mpl::int_<1>,
  99 #ifdef _M_X64
 100        typename mpl::if_c<
 101            sizeof(Unsigned) <= sizeof(__int64),
 102            mpl::int_<2>,
 103            mpl::int_<0> >::type
 104 #else
 105        mpl::int_<0>
 106 #endif
 107        >::type tag_type;
 108 #ifndef BOOST_MP_NO_CONSTEXPR_DETECTION
 109    if (BOOST_MP_IS_CONST_EVALUATED(mask))
 110    {
 111       return find_lsb_default(mask);
 112    }
 113    else
 114 #endif
 115       return find_lsb(static_cast<ui_type>(mask), tag_type());
 116 }
 117
 118 template <class Unsigned>
 119 BOOST_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR unsigned find_msb(Unsigned mask)
 120 {
 121    typedef typename make_unsigned<Unsigned>::type ui_type;
 122    typedef typename mpl::if_c<
 123        sizeof(Unsigned) <= sizeof(unsigned long),
 124        mpl::int_<1>,
 125 #ifdef _M_X64
 126        typename mpl::if_c<
 127            sizeof(Unsigned) <= sizeof(__int64),
 128            mpl::int_<2>,
 129            mpl::int_<0> >::type
 130 #else
 131        mpl::int_<0>
 132 #endif
 133        >::type tag_type;
 134 #ifndef BOOST_MP_NO_CONSTEXPR_DETECTION
 135    if (BOOST_MP_IS_CONST_EVALUATED(mask))
 136    {
 137       return find_msb_default(mask);
 138    }
 139    else
 140 #endif
 141       return find_msb(static_cast<ui_type>(mask), tag_type());
 142 }
 143
 144 #elif defined(BOOST_GCC) || defined(__clang__) || (defined(BOOST_INTEL) && defined(__GNUC__))
 145
 146 BOOST_FORCEINLINE unsigned find_lsb(unsigned mask, mpl::int_<1> const&)
 147 {
 148    return __builtin_ctz(mask);
 149 }
 150 BOOST_FORCEINLINE unsigned find_lsb(unsigned long mask, mpl::int_<2> const&)
 151 {
 152    return __builtin_ctzl(mask);
 153 }
 154 BOOST_FORCEINLINE unsigned find_lsb(boost::ulong_long_type mask, mpl::int_<3> const&)
 155 {
 156    return __builtin_ctzll(mask);
 157 }
 158 BOOST_FORCEINLINE unsigned find_msb(unsigned mask, mpl::int_<1> const&)
 159 {
 160    return sizeof(unsigned) * CHAR_BIT - 1 - __builtin_clz(mask);
 161 }
 162 BOOST_FORCEINLINE unsigned find_msb(unsigned long mask, mpl::int_<2> const&)
 163 {
 164    return sizeof(unsigned long) * CHAR_BIT - 1 - __builtin_clzl(mask);
 165 }
 166 BOOST_FORCEINLINE unsigned find_msb(boost::ulong_long_type mask, mpl::int_<3> const&)
 167 {
 168    return sizeof(boost::ulong_long_type) * CHAR_BIT - 1 - __builtin_clzll(mask);
 169 }
 170 #ifdef BOOST_HAS_INT128
 171
 172 __extension__ typedef unsigned __int128 uint128_type;
 173
 174 BOOST_FORCEINLINE unsigned find_msb(uint128_type mask, mpl::int_<0> const&)
 175 {
 176    union
 177    {
 178       uint128_type    v;
 179       boost::uint64_t sv[2];
 180    } val;
 181    val.v = mask;
 182 #if BOOST_ENDIAN_LITTLE_BYTE
 183    if (val.sv[1])
 184       return find_msb(val.sv[1], mpl::int_<3>()) + 64;
 185    return find_msb(val.sv[0], mpl::int_<3>());
 186 #else
 187    if (val.sv[0])
 188       return find_msb(val.sv[0], mpl::int_<3>()) + 64;
 189    return find_msb(val.sv[1], mpl::int_<3>());
 190 #endif
 191 }
 192 BOOST_FORCEINLINE unsigned find_lsb(uint128_type mask, mpl::int_<0> const&)
 193 {
 194    union
 195    {
 196       uint128_type    v;
 197       boost::uint64_t sv[2];
 198    } val;
 199    val.v = mask;
 200 #if BOOST_ENDIAN_LITTLE_BYTE
 201    if (val.sv[0] == 0)
 202       return find_lsb(val.sv[1], mpl::int_<3>()) + 64;
 203    return find_lsb(val.sv[0], mpl::int_<3>());
 204 #else
 205    if (val.sv[1] == 0)
 206       return find_lsb(val.sv[0], mpl::int_<3>()) + 64;
 207    return find_lsb(val.sv[1], mpl::int_<3>());
 208 #endif
 209 }
 210 #endif
 211
 212 template <class Unsigned>
 213 BOOST_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR unsigned find_lsb(Unsigned mask)
 214 {
 215    typedef typename make_unsigned<Unsigned>::type ui_type;
 216    typedef typename mpl::if_c<
 217        sizeof(Unsigned) <= sizeof(unsigned),
 218        mpl::int_<1>,
 219        typename mpl::if_c<
 220            sizeof(Unsigned) <= sizeof(unsigned long),
 221            mpl::int_<2>,
 222            typename mpl::if_c<
 223                sizeof(Unsigned) <= sizeof(boost::ulong_long_type),
 224                mpl::int_<3>,
 225                mpl::int_<0> >::type>::type>::type tag_type;
 226 #ifndef BOOST_MP_NO_CONSTEXPR_DETECTION
 227    if (BOOST_MP_IS_CONST_EVALUATED(mask))
 228    {
 229       return find_lsb_default(mask);
 230    }
 231    else
 232 #endif
 233    return find_lsb(static_cast<ui_type>(mask), tag_type());
 234 }
 235 template <class Unsigned>
 236 BOOST_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR unsigned find_msb(Unsigned mask)
 237 {
 238    typedef typename make_unsigned<Unsigned>::type ui_type;
 239    typedef typename mpl::if_c<
 240        sizeof(Unsigned) <= sizeof(unsigned),
 241        mpl::int_<1>,
 242        typename mpl::if_c<
 243            sizeof(Unsigned) <= sizeof(unsigned long),
 244            mpl::int_<2>,
 245            typename mpl::if_c<
 246                sizeof(Unsigned) <= sizeof(boost::ulong_long_type),
 247                mpl::int_<3>,
 248                mpl::int_<0> >::type>::type>::type tag_type;
 249 #ifndef BOOST_MP_NO_CONSTEXPR_DETECTION
 250    if (BOOST_MP_IS_CONST_EVALUATED(mask))
 251    {
 252       return find_msb_default(mask);
 253    }
 254    else
 255 #endif
 256       return find_msb(static_cast<ui_type>(mask), tag_type());
 257 }
 258 #elif defined(BOOST_INTEL)
 259 BOOST_FORCEINLINE unsigned find_lsb(unsigned mask, mpl::int_<1> const&)
 260 {
 261    return _bit_scan_forward(mask);
 262 }
 263 BOOST_FORCEINLINE unsigned find_msb(unsigned mask, mpl::int_<1> const&)
 264 {
 265    return _bit_scan_reverse(mask);
 266 }
 267 template <class Unsigned>
 268 BOOST_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR unsigned find_lsb(Unsigned mask)
 269 {
 270    typedef typename make_unsigned<Unsigned>::type ui_type;
 271    typedef typename mpl::if_c<
 272        sizeof(Unsigned) <= sizeof(unsigned),
 273        mpl::int_<1>,
 274        mpl::int_<0> >::type tag_type;
 275 #ifndef BOOST_MP_NO_CONSTEXPR_DETECTION
 276    if (BOOST_MP_IS_CONST_EVALUATED(mask))
 277    {
 278       return find_lsb_default(mask);
 279    }
 280    else
 281 #endif
 282       return find_lsb(static_cast<ui_type>(mask), tag_type());
 283 }
 284 template <class Unsigned>
 285 BOOST_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR unsigned find_msb(Unsigned mask)
 286 {
 287    typedef typename make_unsigned<Unsigned>::type ui_type;
 288    typedef typename mpl::if_c<
 289        sizeof(Unsigned) <= sizeof(unsigned),
 290        mpl::int_<1>,
 291        mpl::int_<0> >::type tag_type;
 292 #ifndef BOOST_MP_NO_CONSTEXPR_DETECTION
 293    if (BOOST_MP_IS_CONST_EVALUATED(mask))
 294    {
 295       return find_msb_default(mask);
 296    }
 297    else
 298 #endif
 299       return find_msb(static_cast<ui_type>(mask), tag_type());
 300 }
 301 #else
 302 template <class Unsigned>
 303 BOOST_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR unsigned find_lsb(Unsigned mask)
 304 {
 305    return find_lsb(mask, mpl::int_<0>());
 306 }
 307 template <class Unsigned>
 308 BOOST_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR unsigned find_msb(Unsigned mask)
 309 {
 310    return find_msb(mask, mpl::int_<0>());
 311 }
 312 #endif
 313
 314 }}} // namespace boost::multiprecision::detail
 315
 316 #endif