Chris@16: ///////////////////////////////////////////////////////////////
Chris@16: //  Copyright 2013 John Maddock. Distributed under the Boost
Chris@16: //  Software License, Version 1.0. (See accompanying file
Chris@16: //  LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_
Chris@16: //
Chris@16: // Comparison operators for cpp_int_backend:
Chris@16: //
Chris@16: #ifndef BOOST_MP_DETAIL_BITSCAN_HPP
Chris@16: #define BOOST_MP_DETAIL_BITSCAN_HPP
Chris@16: 
Chris@101: #if defined(BOOST_MSVC) && (defined(_M_IX86) || defined(_M_X64))
Chris@101: #include <Intrin.h>
Chris@101: #endif
Chris@101: 
Chris@16: namespace boost{ namespace multiprecision{ namespace detail{
Chris@16: 
Chris@16: template <class Unsigned>
Chris@16: inline unsigned find_lsb(Unsigned mask, const mpl::int_<0>&)
Chris@16: {
Chris@16:    unsigned result = 0;
Chris@16:    while(!(mask & 1u))
Chris@16:    {
Chris@16:       mask >>= 1;
Chris@16:       ++result;
Chris@16:    }
Chris@16:    return result;
Chris@16: }
Chris@16: 
Chris@16: template <class Unsigned>
Chris@16: inline unsigned find_msb(Unsigned mask, const mpl::int_<0>&)
Chris@16: {
Chris@16:    unsigned index = 0;
Chris@16:    while(mask)
Chris@16:    {
Chris@16:       ++index;
Chris@16:       mask >>= 1;
Chris@16:    }
Chris@16:    return --index;
Chris@16: }
Chris@16: 
Chris@16: #if defined(BOOST_MSVC) && (defined(_M_IX86) || defined(_M_X64))
Chris@101: 
Chris@101: #pragma intrinsic(_BitScanForward,_BitScanReverse)
Chris@101: 
Chris@16: BOOST_FORCEINLINE unsigned find_lsb(unsigned long mask, const mpl::int_<1>&)
Chris@16: {
Chris@16:    unsigned long result;
Chris@16:    _BitScanForward(&result, mask);
Chris@16:    return result;
Chris@16: }
Chris@16: 
Chris@16: BOOST_FORCEINLINE unsigned find_msb(unsigned long mask, const mpl::int_<1>&)
Chris@16: {
Chris@16:    unsigned long result;
Chris@16:    _BitScanReverse(&result, mask);
Chris@16:    return result;
Chris@16: }
Chris@16: #ifdef _M_X64
Chris@101: 
Chris@101: #pragma intrinsic(_BitScanForward64,_BitScanReverse64)
Chris@101: 
Chris@16: BOOST_FORCEINLINE unsigned find_lsb(unsigned __int64 mask, const mpl::int_<2>&)
Chris@16: {
Chris@16:    unsigned long result;
Chris@16:    _BitScanForward64(&result, mask);
Chris@16:    return result;
Chris@16: }
Chris@16: template <class Unsigned>
Chris@16: BOOST_FORCEINLINE unsigned find_msb(Unsigned mask, const mpl::int_<2>&)
Chris@16: {
Chris@16:    unsigned long result;
Chris@16:    _BitScanReverse64(&result, mask);
Chris@16:    return result;
Chris@16: }
Chris@16: #endif
Chris@16: 
Chris@16: template <class Unsigned>
Chris@16: BOOST_FORCEINLINE unsigned find_lsb(Unsigned mask)
Chris@16: {
Chris@16:    typedef typename make_unsigned<Unsigned>::type ui_type;
Chris@16:    typedef typename mpl::if_c<
Chris@16:       sizeof(Unsigned) <= sizeof(unsigned long),
Chris@16:       mpl::int_<1>,
Chris@16: #ifdef _M_X64
Chris@16:       typename mpl::if_c<
Chris@16:          sizeof(Unsigned) <= sizeof(__int64),
Chris@16:          mpl::int_<2>,
Chris@16:          mpl::int_<0>
Chris@16:       >::type
Chris@16: #else
Chris@16:       mpl::int_<0>
Chris@16: #endif
Chris@16:    >::type tag_type;
Chris@16:    return find_lsb(static_cast<ui_type>(mask), tag_type());
Chris@16: }
Chris@16: 
Chris@16: template <class Unsigned>
Chris@16: BOOST_FORCEINLINE unsigned find_msb(Unsigned mask)
Chris@16: {
Chris@16:    typedef typename make_unsigned<Unsigned>::type ui_type;
Chris@16:    typedef typename mpl::if_c<
Chris@16:       sizeof(Unsigned) <= sizeof(unsigned long),
Chris@16:       mpl::int_<1>,
Chris@16: #ifdef _M_X64
Chris@16:       typename mpl::if_c<
Chris@16:          sizeof(Unsigned) <= sizeof(__int64),
Chris@16:          mpl::int_<2>,
Chris@16:          mpl::int_<0>
Chris@16:       >::type
Chris@16: #else
Chris@16:       mpl::int_<0>
Chris@16: #endif
Chris@16:    >::type tag_type;
Chris@16:    return find_msb(static_cast<ui_type>(mask), tag_type());
Chris@16: }
Chris@16: 
Chris@16: #elif defined(BOOST_GCC) || defined(__clang__) || (defined(BOOST_INTEL) && defined(__GNUC__))
Chris@16: 
Chris@16: BOOST_FORCEINLINE unsigned find_lsb(unsigned mask, mpl::int_<1> const&)
Chris@16: {
Chris@16:    return __builtin_ctz(mask);
Chris@16: }
Chris@16: BOOST_FORCEINLINE unsigned find_lsb(unsigned long mask, mpl::int_<2> const&)
Chris@16: {
Chris@16:    return __builtin_ctzl(mask);
Chris@16: }
Chris@16: BOOST_FORCEINLINE unsigned find_lsb(unsigned long long mask, mpl::int_<3> const&)
Chris@16: {
Chris@16:    return __builtin_ctzll(mask);
Chris@16: }
Chris@16: BOOST_FORCEINLINE unsigned find_msb(unsigned mask, mpl::int_<1> const&)
Chris@16: {
Chris@16:    return sizeof(unsigned) * CHAR_BIT - 1 - __builtin_clz(mask);
Chris@16: }
Chris@16: BOOST_FORCEINLINE unsigned find_msb(unsigned long mask, mpl::int_<2> const&)
Chris@16: {
Chris@16:    return sizeof(unsigned long) * CHAR_BIT - 1 - __builtin_clzl(mask);
Chris@16: }
Chris@16: BOOST_FORCEINLINE unsigned find_msb(unsigned long long mask, mpl::int_<3> const&)
Chris@16: {
Chris@16:    return sizeof(unsigned long long) * CHAR_BIT - 1 - __builtin_clzll(mask);
Chris@16: }
Chris@16: 
Chris@16: template <class Unsigned>
Chris@16: BOOST_FORCEINLINE unsigned find_lsb(Unsigned mask)
Chris@16: {
Chris@16:    typedef typename make_unsigned<Unsigned>::type ui_type;
Chris@16:    typedef typename mpl::if_c<
Chris@16:       sizeof(Unsigned) <= sizeof(unsigned),
Chris@16:       mpl::int_<1>,
Chris@16:       typename mpl::if_c<
Chris@16:          sizeof(Unsigned) <= sizeof(unsigned long),
Chris@16:          mpl::int_<2>,
Chris@16:          typename mpl::if_c<
Chris@16:             sizeof(Unsigned) <= sizeof(unsigned long long),
Chris@16:             mpl::int_<3>,
Chris@16:             mpl::int_<0>
Chris@16:          >::type
Chris@16:       >::type
Chris@16:    >::type tag_type;
Chris@16:    return find_lsb(static_cast<ui_type>(mask), tag_type());
Chris@16: }
Chris@16: template <class Unsigned>
Chris@16: BOOST_FORCEINLINE unsigned find_msb(Unsigned mask)
Chris@16: {
Chris@16:    typedef typename make_unsigned<Unsigned>::type ui_type;
Chris@16:    typedef typename mpl::if_c<
Chris@16:       sizeof(Unsigned) <= sizeof(unsigned),
Chris@16:       mpl::int_<1>,
Chris@16:       typename mpl::if_c<
Chris@16:          sizeof(Unsigned) <= sizeof(unsigned long),
Chris@16:          mpl::int_<2>,
Chris@16:          typename mpl::if_c<
Chris@16:             sizeof(Unsigned) <= sizeof(unsigned long long),
Chris@16:             mpl::int_<3>,
Chris@16:             mpl::int_<0>
Chris@16:          >::type
Chris@16:       >::type
Chris@16:    >::type tag_type;
Chris@16:    return find_msb(static_cast<ui_type>(mask), tag_type());
Chris@16: }
Chris@16: #elif defined(BOOST_INTEL)
Chris@16: BOOST_FORCEINLINE unsigned find_lsb(unsigned mask, mpl::int_<1> const&)
Chris@16: {
Chris@16:    return _bit_scan_forward(mask);
Chris@16: }
Chris@16: BOOST_FORCEINLINE unsigned find_msb(unsigned mask, mpl::int_<1> const&)
Chris@16: {
Chris@16:    return _bit_scan_reverse(mask);
Chris@16: }
Chris@16: template <class Unsigned>
Chris@16: BOOST_FORCEINLINE unsigned find_lsb(Unsigned mask)
Chris@16: {
Chris@16:    typedef typename make_unsigned<Unsigned>::type ui_type;
Chris@16:    typedef typename mpl::if_c<
Chris@16:       sizeof(Unsigned) <= sizeof(unsigned),
Chris@16:       mpl::int_<1>,
Chris@16:       mpl::int_<0>
Chris@16:    >::type tag_type;
Chris@16:    return find_lsb(static_cast<ui_type>(mask), tag_type());
Chris@16: }
Chris@16: template <class Unsigned>
Chris@16: BOOST_FORCEINLINE unsigned find_msb(Unsigned mask)
Chris@16: {
Chris@16:    typedef typename make_unsigned<Unsigned>::type ui_type;
Chris@16:    typedef typename mpl::if_c<
Chris@16:       sizeof(Unsigned) <= sizeof(unsigned),
Chris@16:       mpl::int_<1>,
Chris@16:       mpl::int_<0>
Chris@16:    >::type tag_type;
Chris@16:    return find_msb(static_cast<ui_type>(mask), tag_type());
Chris@16: }
Chris@16: #else
Chris@16: template <class Unsigned>
Chris@16: BOOST_FORCEINLINE unsigned find_lsb(Unsigned mask)
Chris@16: {
Chris@16:    return find_lsb(mask, mpl::int_<0>());
Chris@16: }
Chris@16: template <class Unsigned>
Chris@16: BOOST_FORCEINLINE unsigned find_msb(Unsigned mask)
Chris@16: {
Chris@16:    return find_msb(mask, mpl::int_<0>());
Chris@16: }
Chris@16: #endif
Chris@16: 
Chris@16: }}}
Chris@16: 
Chris@16: #endif
Chris@16: