Chris@102: /////////////////////////////////////////////////////////////////////////////
Chris@102: //
Chris@102: // (C) Copyright Ion Gaztanaga  2014-2014
Chris@102: //
Chris@102: // Distributed under the Boost Software License, Version 1.0.
Chris@102: //    (See accompanying file LICENSE_1_0.txt or copy at
Chris@102: //          http://www.boost.org/LICENSE_1_0.txt)
Chris@102: //
Chris@102: // See http://www.boost.org/libs/intrusive for documentation.
Chris@102: //
Chris@102: /////////////////////////////////////////////////////////////////////////////
Chris@102: 
Chris@102: #ifndef BOOST_INTRUSIVE_DETAIL_MATH_HPP
Chris@102: #define BOOST_INTRUSIVE_DETAIL_MATH_HPP
Chris@102: 
Chris@102: #ifndef BOOST_CONFIG_HPP
Chris@102: #  include <boost/config.hpp>
Chris@102: #endif
Chris@102: 
Chris@102: #if defined(BOOST_HAS_PRAGMA_ONCE)
Chris@102: #  pragma once
Chris@102: #endif
Chris@102: 
Chris@102: #include <cstddef>
Chris@102: #include <climits>
Chris@102: 
Chris@102: namespace boost {
Chris@102: namespace intrusive {
Chris@102: namespace detail {
Chris@102: 
Chris@102: ///////////////////////////
Chris@102: // floor_log2  Dispatcher
Chris@102: ////////////////////////////
Chris@102: 
Chris@102: #if defined(_MSC_VER) && (_MSC_VER >= 1300)
Chris@102: 
Chris@102:    }}} //namespace boost::intrusive::detail
Chris@102: 
Chris@102:    //Use _BitScanReverseXX intrinsics
Chris@102: 
Chris@102:    #if defined(_M_X64) || defined(_M_AMD64) || defined(_M_IA64)   //64 bit target
Chris@102:       #define BOOST_INTRUSIVE_BSR_INTRINSIC_64_BIT
Chris@102:    #endif
Chris@102: 
Chris@102:    #ifndef __INTRIN_H_   // Avoid including any windows system header
Chris@102:       #ifdef __cplusplus
Chris@102:       extern "C" {
Chris@102:       #endif // __cplusplus
Chris@102: 
Chris@102:       #if defined(BOOST_INTRUSIVE_BSR_INTRINSIC_64_BIT)   //64 bit target
Chris@102:          unsigned char _BitScanReverse64(unsigned long *index, unsigned __int64 mask);
Chris@102:          #pragma intrinsic(_BitScanReverse64)
Chris@102:       #else //32 bit target
Chris@102:          unsigned char _BitScanReverse(unsigned long *index, unsigned long mask);
Chris@102:          #pragma intrinsic(_BitScanReverse)
Chris@102:       #endif
Chris@102: 
Chris@102:       #ifdef __cplusplus
Chris@102:       }
Chris@102:       #endif // __cplusplus
Chris@102:    #endif // __INTRIN_H_
Chris@102: 
Chris@102:    #ifdef BOOST_INTRUSIVE_BSR_INTRINSIC_64_BIT
Chris@102:       #define BOOST_INTRUSIVE_BSR_INTRINSIC _BitScanReverse64
Chris@102:       #undef BOOST_INTRUSIVE_BSR_INTRINSIC_64_BIT
Chris@102:    #else
Chris@102:       #define BOOST_INTRUSIVE_BSR_INTRINSIC _BitScanReverse
Chris@102:    #endif
Chris@102: 
Chris@102:    namespace boost {
Chris@102:    namespace intrusive {
Chris@102:    namespace detail {
Chris@102: 
Chris@102:    inline std::size_t floor_log2 (std::size_t x)
Chris@102:    {
Chris@102:       unsigned long log2;
Chris@102:       BOOST_INTRUSIVE_BSR_INTRINSIC( &log2, (unsigned long)x );
Chris@102:       return log2;
Chris@102:    }
Chris@102: 
Chris@102:    #undef BOOST_INTRUSIVE_BSR_INTRINSIC
Chris@102: 
Chris@102: #elif defined(__GNUC__) && ((__GNUC__ >= 4) || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)) //GCC >=3.4
Chris@102: 
Chris@102:    //Compile-time error in case of missing specialization
Chris@102:    template<class Uint>
Chris@102:    struct builtin_clz_dispatch;
Chris@102: 
Chris@102:    #if defined(BOOST_HAS_LONG_LONG)
Chris@102:    template<>
Chris@102:    struct builtin_clz_dispatch< ::boost::ulong_long_type >
Chris@102:    {
Chris@102:       static ::boost::ulong_long_type call(::boost::ulong_long_type n)
Chris@102:       {  return __builtin_clzll(n); }
Chris@102:    };
Chris@102:    #endif
Chris@102: 
Chris@102:    template<>
Chris@102:    struct builtin_clz_dispatch<unsigned long>
Chris@102:    {
Chris@102:       static unsigned long call(unsigned long n)
Chris@102:       {  return __builtin_clzl(n); }
Chris@102:    };
Chris@102: 
Chris@102:    template<>
Chris@102:    struct builtin_clz_dispatch<unsigned int>
Chris@102:    {
Chris@102:       static unsigned int call(unsigned int n)
Chris@102:       {  return __builtin_clz(n); }
Chris@102:    };
Chris@102: 
Chris@102:    inline std::size_t floor_log2(std::size_t n)
Chris@102:    {
Chris@102:       return sizeof(std::size_t)*CHAR_BIT - std::size_t(1) - builtin_clz_dispatch<std::size_t>::call(n);
Chris@102:    }
Chris@102: 
Chris@102: #else //Portable methods
Chris@102: 
Chris@102: ////////////////////////////
Chris@102: // Generic method
Chris@102: ////////////////////////////
Chris@102: 
Chris@102:    inline std::size_t floor_log2_get_shift(std::size_t n, true_ )//power of two size_t
Chris@102:    {  return n >> 1;  }
Chris@102: 
Chris@102:    inline std::size_t floor_log2_get_shift(std::size_t n, false_ )//non-power of two size_t
Chris@102:    {  return (n >> 1) + ((n & 1u) & (n != 1)); }
Chris@102: 
Chris@102:    template<std::size_t N>
Chris@102:    inline std::size_t floor_log2 (std::size_t x, integer<std::size_t, N>)
Chris@102:    {
Chris@102:       const std::size_t Bits = N;
Chris@102:       const bool Size_t_Bits_Power_2= !(Bits & (Bits-1));
Chris@102: 
Chris@102:       std::size_t n = x;
Chris@102:       std::size_t log2 = 0;
Chris@102: 
Chris@102:       std::size_t remaining_bits = Bits;
Chris@102:       std::size_t shift = floor_log2_get_shift(remaining_bits, bool_<Size_t_Bits_Power_2>());
Chris@102:       while(shift){
Chris@102:          std::size_t tmp = n >> shift;
Chris@102:          if (tmp){
Chris@102:             log2 += shift, n = tmp;
Chris@102:          }
Chris@102:          shift = floor_log2_get_shift(shift, bool_<Size_t_Bits_Power_2>());
Chris@102:       }
Chris@102: 
Chris@102:       return log2;
Chris@102:    }
Chris@102: 
Chris@102:    ////////////////////////////
Chris@102:    // DeBruijn method
Chris@102:    ////////////////////////////
Chris@102: 
Chris@102:    //Taken from:
Chris@102:    //http://stackoverflow.com/questions/11376288/fast-computing-of-log2-for-64-bit-integers
Chris@102:    //Thanks to Desmond Hume
Chris@102: 
Chris@102:    inline std::size_t floor_log2 (std::size_t v, integer<std::size_t, 32>)
Chris@102:    {
Chris@102:       static const int MultiplyDeBruijnBitPosition[32] =
Chris@102:       {
Chris@102:          0, 9, 1, 10, 13, 21, 2, 29, 11, 14, 16, 18, 22, 25, 3, 30,
Chris@102:          8, 12, 20, 28, 15, 17, 24, 7, 19, 27, 23, 6, 26, 5, 4, 31
Chris@102:       };
Chris@102: 
Chris@102:       v |= v >> 1;
Chris@102:       v |= v >> 2;
Chris@102:       v |= v >> 4;
Chris@102:       v |= v >> 8;
Chris@102:       v |= v >> 16;
Chris@102: 
Chris@102:       return MultiplyDeBruijnBitPosition[(std::size_t)(v * 0x07C4ACDDU) >> 27];
Chris@102:    }
Chris@102: 
Chris@102:    inline std::size_t floor_log2 (std::size_t v, integer<std::size_t, 64>)
Chris@102:    {
Chris@102:       static const std::size_t MultiplyDeBruijnBitPosition[64] = {
Chris@102:       63,  0, 58,  1, 59, 47, 53,  2,
Chris@102:       60, 39, 48, 27, 54, 33, 42,  3,
Chris@102:       61, 51, 37, 40, 49, 18, 28, 20,
Chris@102:       55, 30, 34, 11, 43, 14, 22,  4,
Chris@102:       62, 57, 46, 52, 38, 26, 32, 41,
Chris@102:       50, 36, 17, 19, 29, 10, 13, 21,
Chris@102:       56, 45, 25, 31, 35, 16,  9, 12,
Chris@102:       44, 24, 15,  8, 23,  7,  6,  5};
Chris@102: 
Chris@102:       v |= v >> 1;
Chris@102:       v |= v >> 2;
Chris@102:       v |= v >> 4;
Chris@102:       v |= v >> 8;
Chris@102:       v |= v >> 16;
Chris@102:       v |= v >> 32;
Chris@102:       return MultiplyDeBruijnBitPosition[((std::size_t)((v - (v >> 1))*0x07EDD5E59A4E28C2ULL)) >> 58];
Chris@102:    }
Chris@102: 
Chris@102: 
Chris@102:    inline std::size_t floor_log2 (std::size_t x)
Chris@102:    {
Chris@102:       const std::size_t Bits = sizeof(std::size_t)*CHAR_BIT;
Chris@102:       return floor_log2(x, integer<std::size_t, Bits>());
Chris@102:    }
Chris@102: 
Chris@102: #endif
Chris@102: 
Chris@102: //Thanks to Laurent de Soras in
Chris@102: //http://www.flipcode.com/archives/Fast_log_Function.shtml
Chris@102: inline float fast_log2 (float val)
Chris@102: {
Chris@102:    union caster_t
Chris@102:    {
Chris@102:       unsigned x;
Chris@102:       float val;
Chris@102:    } caster;
Chris@102: 
Chris@102:    caster.val = val;
Chris@102:    unsigned x = caster.x;
Chris@102:    const int log_2 = int((x >> 23) & 255) - 128;
Chris@102:    x &= ~(unsigned(255u) << 23u);
Chris@102:    x += unsigned(127) << 23u;
Chris@102:    caster.x = x;
Chris@102:    val = caster.val;
Chris@102:    //1+log2(m), m ranging from 1 to 2
Chris@102:    //3rd degree polynomial keeping first derivate continuity.
Chris@102:    //For less precision the line can be commented out
Chris@102:    val = ((-1.f/3.f) * val + 2.f) * val - (2.f/3.f);
Chris@102:    return val + static_cast<float>(log_2);
Chris@102: }
Chris@102: 
Chris@102: inline std::size_t ceil_log2 (std::size_t x)
Chris@102: {
Chris@102:    return static_cast<std::size_t>((x & (x-1)) != 0) + floor_log2(x);
Chris@102: }
Chris@102: 
Chris@102: template<class SizeType, std::size_t N>
Chris@102: struct numbits_eq
Chris@102: {
Chris@102:    static const bool value = sizeof(SizeType)*CHAR_BIT == N;
Chris@102: };
Chris@102: 
Chris@102: template<class SizeType, class Enabler = void >
Chris@102: struct sqrt2_pow_max;
Chris@102: 
Chris@102: template <class SizeType>
Chris@102: struct sqrt2_pow_max<SizeType, typename enable_if< numbits_eq<SizeType, 32> >::type>
Chris@102: {
Chris@102:    static const SizeType value = 0xb504f334;
Chris@102:    static const std::size_t pow   = 31;
Chris@102: };
Chris@102: 
Chris@102: #ifndef BOOST_NO_INT64_T
Chris@102: 
Chris@102: template <class SizeType>
Chris@102: struct sqrt2_pow_max<SizeType, typename enable_if< numbits_eq<SizeType, 64> >::type>
Chris@102: {
Chris@102:    static const SizeType value = 0xb504f333f9de6484ull;
Chris@102:    static const std::size_t pow   = 63;
Chris@102: };
Chris@102: 
Chris@102: #endif   //BOOST_NO_INT64_T
Chris@102: 
Chris@102: // Returns floor(pow(sqrt(2), x * 2 + 1)).
Chris@102: // Defined for X from 0 up to the number of bits in size_t minus 1.
Chris@102: inline std::size_t sqrt2_pow_2xplus1 (std::size_t x)
Chris@102: {
Chris@102:    const std::size_t value = (std::size_t)sqrt2_pow_max<std::size_t>::value;
Chris@102:    const std::size_t pow   = (std::size_t)sqrt2_pow_max<std::size_t>::pow;
Chris@102:    return (value >> (pow - x)) + 1;
Chris@102: }
Chris@102: 
Chris@102: } //namespace detail
Chris@102: } //namespace intrusive
Chris@102: } //namespace boost
Chris@102: 
Chris@102: #endif //BOOST_INTRUSIVE_DETAIL_MATH_HPP