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