intrusive/detail/math.hpp

0001 /////////////////////////////////////////////////////////////////////////////
0002 //
0003 // (C) Copyright Ion Gaztanaga  2014-2014
0004 //
0005 // Distributed under the Boost Software License, Version 1.0.
0006 //    (See accompanying file LICENSE_1_0.txt or copy at
0007 //          http://www.boost.org/LICENSE_1_0.txt)
0008 //
0009 // See http://www.boost.org/libs/intrusive for documentation.
0010 //
0011 /////////////////////////////////////////////////////////////////////////////
0012
0013 #ifndef BOOST_INTRUSIVE_DETAIL_MATH_HPP
0014 #define BOOST_INTRUSIVE_DETAIL_MATH_HPP
0015
0016 #ifndef BOOST_CONFIG_HPP
0017 #  include <boost/config.hpp>
0018 #endif
0019
0020 #if defined(BOOST_HAS_PRAGMA_ONCE)
0021 #  pragma once
0022 #endif
0023
0024 #include <cstddef>
0025 #include <climits>
0026 #include <boost/intrusive/detail/mpl.hpp>
0027 #include <cstring>
0028
0029 namespace boost {
0030 namespace intrusive {
0031 namespace detail {
0032
0033 ///////////////////////////
0034 // floor_log2  Dispatcher
0035 ////////////////////////////
0036
0037 #if defined(_MSC_VER) && (_MSC_VER >= 1300)
0038
0039    }}} //namespace boost::intrusive::detail
0040
0041    //Use _BitScanReverseXX intrinsics
0042
0043    #if defined(_M_X64) || defined(_M_AMD64) || defined(_M_IA64)   //64 bit target
0044       #define BOOST_INTRUSIVE_BSR_INTRINSIC_64_BIT
0045    #endif
0046
0047    #ifndef __INTRIN_H_   // Avoid including any windows system header
0048       #ifdef __cplusplus
0049       extern "C" {
0050       #endif // __cplusplus
0051
0052       #if defined(BOOST_INTRUSIVE_BSR_INTRINSIC_64_BIT)   //64 bit target
0053          unsigned char _BitScanReverse64(unsigned long *index, unsigned __int64 mask);
0054          #pragma intrinsic(_BitScanReverse64)
0055       #else //32 bit target
0056          unsigned char _BitScanReverse(unsigned long *index, unsigned long mask);
0057          #pragma intrinsic(_BitScanReverse)
0058       #endif
0059
0060       #ifdef __cplusplus
0061       }
0062       #endif // __cplusplus
0063    #endif // __INTRIN_H_
0064
0065    #ifdef BOOST_INTRUSIVE_BSR_INTRINSIC_64_BIT
0066       #define BOOST_INTRUSIVE_BSR_INTRINSIC _BitScanReverse64
0067       #undef BOOST_INTRUSIVE_BSR_INTRINSIC_64_BIT
0068    #else
0069       #define BOOST_INTRUSIVE_BSR_INTRINSIC _BitScanReverse
0070    #endif
0071
0072    namespace boost {
0073    namespace intrusive {
0074    namespace detail {
0075
0076    inline std::size_t floor_log2 (std::size_t x)
0077    {
0078       unsigned long log2;
0079       BOOST_INTRUSIVE_BSR_INTRINSIC( &log2, x );
0080       return static_cast<std::size_t>(log2);
0081    }
0082
0083    #undef BOOST_INTRUSIVE_BSR_INTRINSIC
0084
0085 #elif defined(__GNUC__) && ((__GNUC__ >= 4) || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)) //GCC >=3.4
0086
0087    //Compile-time error in case of missing specialization
0088    template<class Uint>
0089    struct builtin_clz_dispatch;
0090
0091    #if defined(BOOST_HAS_LONG_LONG)
0092    template<>
0093    struct builtin_clz_dispatch< ::boost::ulong_long_type >
0094    {
0095       static ::boost::ulong_long_type call(::boost::ulong_long_type n)
0096       {  return (::boost::ulong_long_type)__builtin_clzll(n); }
0097    };
0098    #endif
0099
0100    template<>
0101    struct builtin_clz_dispatch<unsigned long>
0102    {
0103       static unsigned long call(unsigned long n)
0104       {  return (unsigned long)__builtin_clzl(n); }
0105    };
0106
0107    template<>
0108    struct builtin_clz_dispatch<unsigned int>
0109    {
0110       static unsigned int call(unsigned int n)
0111       {  return (unsigned int)__builtin_clz(n); }
0112    };
0113
0114    inline std::size_t floor_log2(std::size_t n)
0115    {
0116       return sizeof(std::size_t)*CHAR_BIT - std::size_t(1) - builtin_clz_dispatch<std::size_t>::call(n);
0117    }
0118
0119 #else //Portable methods
0120
0121 ////////////////////////////
0122 // Generic method
0123 ////////////////////////////
0124
0125    inline std::size_t floor_log2_get_shift(std::size_t n, true_ )//power of two size_t
0126    {  return n >> 1;  }
0127
0128    inline std::size_t floor_log2_get_shift(std::size_t n, false_ )//non-power of two size_t
0129    {  return (n >> 1) + ((n & 1u) & (n != 1)); }
0130
0131    template<std::size_t N>
0132    inline std::size_t floor_log2 (std::size_t x, integral_constant<std::size_t, N>)
0133    {
0134       const std::size_t Bits = N;
0135       const bool Size_t_Bits_Power_2= !(Bits & (Bits-1));
0136
0137       std::size_t n = x;
0138       std::size_t log2 = 0;
0139
0140       std::size_t remaining_bits = Bits;
0141       std::size_t shift = floor_log2_get_shift(remaining_bits, bool_<Size_t_Bits_Power_2>());
0142       while(shift){
0143          std::size_t tmp = n >> shift;
0144          if (tmp){
0145             log2 += shift, n = tmp;
0146          }
0147          shift = floor_log2_get_shift(shift, bool_<Size_t_Bits_Power_2>());
0148       }
0149
0150       return log2;
0151    }
0152
0153    inline std::size_t floor_log2 (std::size_t x)
0154    {
0155       const std::size_t Bits = sizeof(std::size_t)*CHAR_BIT;
0156       return floor_log2(x, integral_constant<std::size_t, Bits>());
0157    }
0158
0159 #endif
0160
0161 //Thanks to Laurent de Soras in
0162 //http://www.flipcode.com/archives/Fast_log_Function.shtml
0163 inline float fast_log2 (float val)
0164 {
0165    unsigned x;
0166    std::memcpy(&x, &val, sizeof(float));
0167    const int log_2 = int((x >> 23) & 255) - 128;
0168    x &= ~(unsigned(255u) << 23u);
0169    x += unsigned(127) << 23u;
0170    std::memcpy(&val, &x, sizeof(float));
0171    //1+log2(m), m ranging from 1 to 2
0172    //3rd degree polynomial keeping first derivate continuity.
0173    //For less precision the line can be commented out
0174    val = ((-1.f/3.f) * val + 2.f) * val - (2.f/3.f);
0175    return val + static_cast<float>(log_2);
0176 }
0177
0178 inline bool is_pow2(std::size_t x)
0179 {  return (x & (x-1)) == 0;  }
0180
0181 template<std::size_t N>
0182 struct static_is_pow2
0183 {
0184    static const bool value = (N & (N-1)) == 0;
0185 };
0186
0187 inline std::size_t ceil_log2 (std::size_t x)
0188 {
0189    return static_cast<std::size_t>(!(is_pow2)(x)) + floor_log2(x);
0190 }
0191
0192 inline std::size_t ceil_pow2 (std::size_t x)
0193 {
0194    return std::size_t(1u) << (ceil_log2)(x);
0195 }
0196
0197 inline std::size_t previous_or_equal_pow2(std::size_t x)
0198 {
0199    return std::size_t(1u) << floor_log2(x);
0200 }
0201
0202 template<class SizeType, std::size_t N>
0203 struct numbits_eq
0204 {
0205    static const bool value = sizeof(SizeType)*CHAR_BIT == N;
0206 };
0207
0208 template<class SizeType, class Enabler = void >
0209 struct sqrt2_pow_max;
0210
0211 template <class SizeType>
0212 struct sqrt2_pow_max<SizeType, typename voider<typename enable_if< numbits_eq<SizeType, 32> >::type>::type>
0213 {
0214    static const SizeType value = 0xb504f334;
0215    static const std::size_t pow   = 31;
0216 };
0217
0218 #ifndef BOOST_NO_INT64_T
0219
0220 template <class SizeType>
0221 struct sqrt2_pow_max<SizeType, typename voider<typename enable_if< numbits_eq<SizeType, 64> >::type>::type>
0222 {
0223    static const SizeType value = 0xb504f333f9de6484ull;
0224    static const std::size_t pow   = 63;
0225 };
0226
0227 #endif   //BOOST_NO_INT64_T
0228
0229 // Returns floor(pow(sqrt(2), x * 2 + 1)).
0230 // Defined for X from 0 up to the number of bits in size_t minus 1.
0231 inline std::size_t sqrt2_pow_2xplus1 (std::size_t x)
0232 {
0233    const std::size_t value = (std::size_t)sqrt2_pow_max<std::size_t>::value;
0234    const std::size_t pow   = (std::size_t)sqrt2_pow_max<std::size_t>::pow;
0235    return (value >> (pow - x)) + 1;
0236 }
0237
0238 } //namespace detail
0239 } //namespace intrusive
0240 } //namespace boost
0241
0242 #endif //BOOST_INTRUSIVE_DETAIL_MATH_HPP