Imported Upstream version 1.57.0upstream/1.57.0

1 files changed, 271 insertions, 0 deletions

diff --git a/boost/intrusive/detail/math.hpp b/boost/intrusive/detail/math.hpp
new file mode 100644
index 0000000000..f212ae743f
--- /dev/null
+++ b/boost/intrusive/detail/math.hpp
@@ -0,0 +1,271 @@
+/////////////////////////////////////////////////////////////////////////////
+//
+// (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
+
+#if defined(_MSC_VER)
+#  pragma once
+#endif
+
+#include <cstddef>
+#include <climits>
+
+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<unsigned long long>
+   {
+      static unsigned long long call(unsigned long long 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, integer<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, integer<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, integer<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, integer<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 std::size_t ceil_log2 (std::size_t x)
+{
+   return static_cast<std::size_t>((x & (x-1)) != 0) + 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