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