ceph/src/boost/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 http://www.boost.org/LICENSE_1_
   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/detail/endian.hpp>
  12
  13 #if (defined(BOOST_MSVC) || (defined(__clang__) && defined(__c2__)) || (defined(BOOST_INTEL) && defined(_MSC_VER))) && (defined(_M_IX86) || defined(_M_X64))
  14 #include <intrin.h>
  15 #endif
  16
  17 namespace boost{ namespace multiprecision{ namespace detail{
  18
  19 template <class Unsigned>
  20 inline unsigned find_lsb(Unsigned mask, const mpl::int_<0>&)
  21 {
  22    unsigned result = 0;
  23    while(!(mask & 1u))
  24    {
  25       mask >>= 1;
  26       ++result;
  27    }
  28    return result;
  29 }
  30
  31 template <class Unsigned>
  32 inline unsigned find_msb(Unsigned mask, const mpl::int_<0>&)
  33 {
  34    unsigned index = 0;
  35    while(mask)
  36    {
  37       ++index;
  38       mask >>= 1;
  39    }
  40    return --index;
  41 }
  42
  43 #if (defined(BOOST_MSVC) || (defined(__clang__) && defined(__c2__)) || (defined(BOOST_INTEL) && defined(_MSC_VER))) && (defined(_M_IX86) || defined(_M_X64))
  44
  45 #pragma intrinsic(_BitScanForward,_BitScanReverse)
  46
  47 BOOST_FORCEINLINE unsigned find_lsb(unsigned long mask, const mpl::int_<1>&)
  48 {
  49    unsigned long result;
  50    _BitScanForward(&result, mask);
  51    return result;
  52 }
  53
  54 BOOST_FORCEINLINE unsigned find_msb(unsigned long mask, const mpl::int_<1>&)
  55 {
  56    unsigned long result;
  57    _BitScanReverse(&result, mask);
  58    return result;
  59 }
  60 #ifdef _M_X64
  61
  62 #pragma intrinsic(_BitScanForward64,_BitScanReverse64)
  63
  64 BOOST_FORCEINLINE unsigned find_lsb(unsigned __int64 mask, const mpl::int_<2>&)
  65 {
  66    unsigned long result;
  67    _BitScanForward64(&result, mask);
  68    return result;
  69 }
  70 template <class Unsigned>
  71 BOOST_FORCEINLINE unsigned find_msb(Unsigned mask, const mpl::int_<2>&)
  72 {
  73    unsigned long result;
  74    _BitScanReverse64(&result, mask);
  75    return result;
  76 }
  77 #endif
  78
  79 template <class Unsigned>
  80 BOOST_FORCEINLINE unsigned find_lsb(Unsigned mask)
  81 {
  82    typedef typename make_unsigned<Unsigned>::type ui_type;
  83    typedef typename mpl::if_c<
  84       sizeof(Unsigned) <= sizeof(unsigned long),
  85       mpl::int_<1>,
  86 #ifdef _M_X64
  87       typename mpl::if_c<
  88          sizeof(Unsigned) <= sizeof(__int64),
  89          mpl::int_<2>,
  90          mpl::int_<0>
  91       >::type
  92 #else
  93       mpl::int_<0>
  94 #endif
  95    >::type tag_type;
  96    return find_lsb(static_cast<ui_type>(mask), tag_type());
  97 }
  98
  99 template <class Unsigned>
 100 BOOST_FORCEINLINE unsigned find_msb(Unsigned mask)
 101 {
 102    typedef typename make_unsigned<Unsigned>::type ui_type;
 103    typedef typename mpl::if_c<
 104       sizeof(Unsigned) <= sizeof(unsigned long),
 105       mpl::int_<1>,
 106 #ifdef _M_X64
 107       typename mpl::if_c<
 108          sizeof(Unsigned) <= sizeof(__int64),
 109          mpl::int_<2>,
 110          mpl::int_<0>
 111       >::type
 112 #else
 113       mpl::int_<0>
 114 #endif
 115    >::type tag_type;
 116    return find_msb(static_cast<ui_type>(mask), tag_type());
 117 }
 118
 119 #elif defined(BOOST_GCC) || defined(__clang__) || (defined(BOOST_INTEL) && defined(__GNUC__))
 120
 121 BOOST_FORCEINLINE unsigned find_lsb(unsigned mask, mpl::int_<1> const&)
 122 {
 123    return __builtin_ctz(mask);
 124 }
 125 BOOST_FORCEINLINE unsigned find_lsb(unsigned long mask, mpl::int_<2> const&)
 126 {
 127    return __builtin_ctzl(mask);
 128 }
 129 BOOST_FORCEINLINE unsigned find_lsb(boost::ulong_long_type mask, mpl::int_<3> const&)
 130 {
 131    return __builtin_ctzll(mask);
 132 }
 133 BOOST_FORCEINLINE unsigned find_msb(unsigned mask, mpl::int_<1> const&)
 134 {
 135    return sizeof(unsigned) * CHAR_BIT - 1 - __builtin_clz(mask);
 136 }
 137 BOOST_FORCEINLINE unsigned find_msb(unsigned long mask, mpl::int_<2> const&)
 138 {
 139    return sizeof(unsigned long) * CHAR_BIT - 1 - __builtin_clzl(mask);
 140 }
 141 BOOST_FORCEINLINE unsigned find_msb(boost::ulong_long_type mask, mpl::int_<3> const&)
 142 {
 143    return sizeof(boost::ulong_long_type) * CHAR_BIT - 1 - __builtin_clzll(mask);
 144 }
 145 #ifdef BOOST_HAS_INT128
 146
 147 __extension__  typedef unsigned __int128 uint128_type;
 148
 149 BOOST_FORCEINLINE unsigned find_msb(uint128_type mask, mpl::int_<0> const&)
 150 {
 151    union { uint128_type v; boost::uint64_t sv[2]; } val;
 152    val.v = mask;
 153 #ifdef BOOST_LITTLE_ENDIAN
 154    if(val.sv[1])
 155       return find_msb(val.sv[1], mpl::int_<3>()) + 64;
 156    return find_msb(val.sv[0], mpl::int_<3>());
 157 #else
 158    if(val.sv[0])
 159       return find_msb(val.sv[0], mpl::int_<3>()) + 64;
 160    return find_msb(val.sv[1], mpl::int_<3>());
 161 #endif
 162 }
 163 BOOST_FORCEINLINE unsigned find_lsb(uint128_type mask, mpl::int_<0> const&)
 164 {
 165    union { uint128_type v; boost::uint64_t sv[2]; } val;
 166    val.v = mask;
 167 #ifdef BOOST_LITTLE_ENDIAN
 168    if(val.sv[0] == 0)
 169       return find_lsb(val.sv[1], mpl::int_<3>()) + 64;
 170    return find_lsb(val.sv[0], mpl::int_<3>());
 171 #else
 172    if(val.sv[1] == 0)
 173       return find_lsb(val.sv[0], mpl::int_<3>()) + 64;
 174    return find_lsb(val.sv[1], mpl::int_<3>());
 175 #endif
 176 }
 177 #endif
 178
 179 template <class Unsigned>
 180 BOOST_FORCEINLINE unsigned find_lsb(Unsigned mask)
 181 {
 182    typedef typename make_unsigned<Unsigned>::type ui_type;
 183    typedef typename mpl::if_c<
 184       sizeof(Unsigned) <= sizeof(unsigned),
 185       mpl::int_<1>,
 186       typename mpl::if_c<
 187          sizeof(Unsigned) <= sizeof(unsigned long),
 188          mpl::int_<2>,
 189          typename mpl::if_c<
 190             sizeof(Unsigned) <= sizeof(boost::ulong_long_type),
 191             mpl::int_<3>,
 192             mpl::int_<0>
 193          >::type
 194       >::type
 195    >::type tag_type;
 196    return find_lsb(static_cast<ui_type>(mask), tag_type());
 197 }
 198 template <class Unsigned>
 199 BOOST_FORCEINLINE unsigned find_msb(Unsigned mask)
 200 {
 201    typedef typename make_unsigned<Unsigned>::type ui_type;
 202    typedef typename mpl::if_c<
 203       sizeof(Unsigned) <= sizeof(unsigned),
 204       mpl::int_<1>,
 205       typename mpl::if_c<
 206          sizeof(Unsigned) <= sizeof(unsigned long),
 207          mpl::int_<2>,
 208          typename mpl::if_c<
 209             sizeof(Unsigned) <= sizeof(boost::ulong_long_type),
 210             mpl::int_<3>,
 211             mpl::int_<0>
 212          >::type
 213       >::type
 214    >::type tag_type;
 215    return find_msb(static_cast<ui_type>(mask), tag_type());
 216 }
 217 #elif defined(BOOST_INTEL)
 218 BOOST_FORCEINLINE unsigned find_lsb(unsigned mask, mpl::int_<1> const&)
 219 {
 220    return _bit_scan_forward(mask);
 221 }
 222 BOOST_FORCEINLINE unsigned find_msb(unsigned mask, mpl::int_<1> const&)
 223 {
 224    return _bit_scan_reverse(mask);
 225 }
 226 template <class Unsigned>
 227 BOOST_FORCEINLINE unsigned find_lsb(Unsigned mask)
 228 {
 229    typedef typename make_unsigned<Unsigned>::type ui_type;
 230    typedef typename mpl::if_c<
 231       sizeof(Unsigned) <= sizeof(unsigned),
 232       mpl::int_<1>,
 233       mpl::int_<0>
 234    >::type tag_type;
 235    return find_lsb(static_cast<ui_type>(mask), tag_type());
 236 }
 237 template <class Unsigned>
 238 BOOST_FORCEINLINE unsigned find_msb(Unsigned mask)
 239 {
 240    typedef typename make_unsigned<Unsigned>::type ui_type;
 241    typedef typename mpl::if_c<
 242       sizeof(Unsigned) <= sizeof(unsigned),
 243       mpl::int_<1>,
 244       mpl::int_<0>
 245    >::type tag_type;
 246    return find_msb(static_cast<ui_type>(mask), tag_type());
 247 }
 248 #else
 249 template <class Unsigned>
 250 BOOST_FORCEINLINE unsigned find_lsb(Unsigned mask)
 251 {
 252    return find_lsb(mask, mpl::int_<0>());
 253 }
 254 template <class Unsigned>
 255 BOOST_FORCEINLINE unsigned find_msb(Unsigned mask)
 256 {
 257    return find_msb(mask, mpl::int_<0>());
 258 }
 259 #endif
 260
 261 }}}
 262
 263 #endif
 264