ceph/src/boost/boost/intrusive/detail/math.hpp

   1 /////////////////////////////////////////////////////////////////////////////
   2 //
   3 // (C) Copyright Ion Gaztanaga  2014-2014
   4 //
   5 // Distributed under the Boost Software License, Version 1.0.
   6 //    (See accompanying file LICENSE_1_0.txt or copy at
   7 //          http://www.boost.org/LICENSE_1_0.txt)
   8 //
   9 // See http://www.boost.org/libs/intrusive for documentation.
  10 //
  11 /////////////////////////////////////////////////////////////////////////////
  12
  13 #ifndef BOOST_INTRUSIVE_DETAIL_MATH_HPP
  14 #define BOOST_INTRUSIVE_DETAIL_MATH_HPP
  15
  16 #ifndef BOOST_CONFIG_HPP
  17 #  include <boost/config.hpp>
  18 #endif
  19
  20 #if defined(BOOST_HAS_PRAGMA_ONCE)
  21 #  pragma once
  22 #endif
  23
  24 #include <cstddef>
  25 #include <climits>
  26 #include <boost/intrusive/detail/mpl.hpp>
  27
  28 namespace boost {
  29 namespace intrusive {
  30 namespace detail {
  31
  32 ///////////////////////////
  33 // floor_log2  Dispatcher
  34 ////////////////////////////
  35
  36 #if defined(_MSC_VER) && (_MSC_VER >= 1300)
  37
  38    }}} //namespace boost::intrusive::detail
  39
  40    //Use _BitScanReverseXX intrinsics
  41
  42    #if defined(_M_X64) || defined(_M_AMD64) || defined(_M_IA64)   //64 bit target
  43       #define BOOST_INTRUSIVE_BSR_INTRINSIC_64_BIT
  44    #endif
  45
  46    #ifndef __INTRIN_H_   // Avoid including any windows system header
  47       #ifdef __cplusplus
  48       extern "C" {
  49       #endif // __cplusplus
  50
  51       #if defined(BOOST_INTRUSIVE_BSR_INTRINSIC_64_BIT)   //64 bit target
  52          unsigned char _BitScanReverse64(unsigned long *index, unsigned __int64 mask);
  53          #pragma intrinsic(_BitScanReverse64)
  54       #else //32 bit target
  55          unsigned char _BitScanReverse(unsigned long *index, unsigned long mask);
  56          #pragma intrinsic(_BitScanReverse)
  57       #endif
  58
  59       #ifdef __cplusplus
  60       }
  61       #endif // __cplusplus
  62    #endif // __INTRIN_H_
  63
  64    #ifdef BOOST_INTRUSIVE_BSR_INTRINSIC_64_BIT
  65       #define BOOST_INTRUSIVE_BSR_INTRINSIC _BitScanReverse64
  66       #undef BOOST_INTRUSIVE_BSR_INTRINSIC_64_BIT
  67    #else
  68       #define BOOST_INTRUSIVE_BSR_INTRINSIC _BitScanReverse
  69    #endif
  70
  71    namespace boost {
  72    namespace intrusive {
  73    namespace detail {
  74
  75    inline std::size_t floor_log2 (std::size_t x)
  76    {
  77       unsigned long log2;
  78       BOOST_INTRUSIVE_BSR_INTRINSIC( &log2, (unsigned long)x );
  79       return log2;
  80    }
  81
  82    #undef BOOST_INTRUSIVE_BSR_INTRINSIC
  83
  84 #elif defined(__GNUC__) && ((__GNUC__ >= 4) || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)) //GCC >=3.4
  85
  86    //Compile-time error in case of missing specialization
  87    template<class Uint>
  88    struct builtin_clz_dispatch;
  89
  90    #if defined(BOOST_HAS_LONG_LONG)
  91    template<>
  92    struct builtin_clz_dispatch< ::boost::ulong_long_type >
  93    {
  94       static ::boost::ulong_long_type call(::boost::ulong_long_type n)
  95       {  return __builtin_clzll(n); }
  96    };
  97    #endif
  98
  99    template<>
 100    struct builtin_clz_dispatch<unsigned long>
 101    {
 102       static unsigned long call(unsigned long n)
 103       {  return __builtin_clzl(n); }
 104    };
 105
 106    template<>
 107    struct builtin_clz_dispatch<unsigned int>
 108    {
 109       static unsigned int call(unsigned int n)
 110       {  return __builtin_clz(n); }
 111    };
 112
 113    inline std::size_t floor_log2(std::size_t n)
 114    {
 115       return sizeof(std::size_t)*CHAR_BIT - std::size_t(1) - builtin_clz_dispatch<std::size_t>::call(n);
 116    }
 117
 118 #else //Portable methods
 119
 120 ////////////////////////////
 121 // Generic method
 122 ////////////////////////////
 123
 124    inline std::size_t floor_log2_get_shift(std::size_t n, true_ )//power of two size_t
 125    {  return n >> 1;  }
 126
 127    inline std::size_t floor_log2_get_shift(std::size_t n, false_ )//non-power of two size_t
 128    {  return (n >> 1) + ((n & 1u) & (n != 1)); }
 129
 130    template<std::size_t N>
 131    inline std::size_t floor_log2 (std::size_t x, integral_constant<std::size_t, N>)
 132    {
 133       const std::size_t Bits = N;
 134       const bool Size_t_Bits_Power_2= !(Bits & (Bits-1));
 135
 136       std::size_t n = x;
 137       std::size_t log2 = 0;
 138
 139       std::size_t remaining_bits = Bits;
 140       std::size_t shift = floor_log2_get_shift(remaining_bits, bool_<Size_t_Bits_Power_2>());
 141       while(shift){
 142          std::size_t tmp = n >> shift;
 143          if (tmp){
 144             log2 += shift, n = tmp;
 145          }
 146          shift = floor_log2_get_shift(shift, bool_<Size_t_Bits_Power_2>());
 147       }
 148
 149       return log2;
 150    }
 151
 152    ////////////////////////////
 153    // DeBruijn method
 154    ////////////////////////////
 155
 156    //Taken from:
 157    //http://stackoverflow.com/questions/11376288/fast-computing-of-log2-for-64-bit-integers
 158    //Thanks to Desmond Hume
 159
 160    inline std::size_t floor_log2 (std::size_t v, integral_constant<std::size_t, 32>)
 161    {
 162       static const int MultiplyDeBruijnBitPosition[32] =
 163       {
 164          0, 9, 1, 10, 13, 21, 2, 29, 11, 14, 16, 18, 22, 25, 3, 30,
 165          8, 12, 20, 28, 15, 17, 24, 7, 19, 27, 23, 6, 26, 5, 4, 31
 166       };
 167
 168       v |= v >> 1;
 169       v |= v >> 2;
 170       v |= v >> 4;
 171       v |= v >> 8;
 172       v |= v >> 16;
 173
 174       return MultiplyDeBruijnBitPosition[(std::size_t)(v * 0x07C4ACDDU) >> 27];
 175    }
 176
 177    inline std::size_t floor_log2 (std::size_t v, integral_constant<std::size_t, 64>)
 178    {
 179       static const std::size_t MultiplyDeBruijnBitPosition[64] = {
 180       63,  0, 58,  1, 59, 47, 53,  2,
 181       60, 39, 48, 27, 54, 33, 42,  3,
 182       61, 51, 37, 40, 49, 18, 28, 20,
 183       55, 30, 34, 11, 43, 14, 22,  4,
 184       62, 57, 46, 52, 38, 26, 32, 41,
 185       50, 36, 17, 19, 29, 10, 13, 21,
 186       56, 45, 25, 31, 35, 16,  9, 12,
 187       44, 24, 15,  8, 23,  7,  6,  5};
 188
 189       v |= v >> 1;
 190       v |= v >> 2;
 191       v |= v >> 4;
 192       v |= v >> 8;
 193       v |= v >> 16;
 194       v |= v >> 32;
 195       return MultiplyDeBruijnBitPosition[((std::size_t)((v - (v >> 1))*0x07EDD5E59A4E28C2ULL)) >> 58];
 196    }
 197
 198
 199    inline std::size_t floor_log2 (std::size_t x)
 200    {
 201       const std::size_t Bits = sizeof(std::size_t)*CHAR_BIT;
 202       return floor_log2(x, integral_constant<std::size_t, Bits>());
 203    }
 204
 205 #endif
 206
 207 //Thanks to Laurent de Soras in
 208 //http://www.flipcode.com/archives/Fast_log_Function.shtml
 209 inline float fast_log2 (float val)
 210 {
 211    union caster_t
 212    {
 213       unsigned x;
 214       float val;
 215    } caster;
 216
 217    caster.val = val;
 218    unsigned x = caster.x;
 219    const int log_2 = int((x >> 23) & 255) - 128;
 220    x &= ~(unsigned(255u) << 23u);
 221    x += unsigned(127) << 23u;
 222    caster.x = x;
 223    val = caster.val;
 224    //1+log2(m), m ranging from 1 to 2
 225    //3rd degree polynomial keeping first derivate continuity.
 226    //For less precision the line can be commented out
 227    val = ((-1.f/3.f) * val + 2.f) * val - (2.f/3.f);
 228    return val + static_cast<float>(log_2);
 229 }
 230
 231 inline bool is_pow2(std::size_t x)
 232 {  return (x & (x-1)) == 0;  }
 233
 234 template<std::size_t N>
 235 struct static_is_pow2
 236 {
 237    static const bool value = (N & (N-1)) == 0;
 238 };
 239
 240 inline std::size_t ceil_log2 (std::size_t x)
 241 {
 242    return static_cast<std::size_t>(!(is_pow2)(x)) + floor_log2(x);
 243 }
 244
 245 inline std::size_t ceil_pow2 (std::size_t x)
 246 {
 247    return std::size_t(1u) << (ceil_log2)(x);
 248 }
 249
 250 inline std::size_t previous_or_equal_pow2(std::size_t x)
 251 {
 252    return std::size_t(1u) << floor_log2(x);
 253 }
 254
 255 template<class SizeType, std::size_t N>
 256 struct numbits_eq
 257 {
 258    static const bool value = sizeof(SizeType)*CHAR_BIT == N;
 259 };
 260
 261 template<class SizeType, class Enabler = void >
 262 struct sqrt2_pow_max;
 263
 264 template <class SizeType>
 265 struct sqrt2_pow_max<SizeType, typename voider<typename enable_if< numbits_eq<SizeType, 32> >::type>::type>
 266 {
 267    static const SizeType value = 0xb504f334;
 268    static const std::size_t pow   = 31;
 269 };
 270
 271 #ifndef BOOST_NO_INT64_T
 272
 273 template <class SizeType>
 274 struct sqrt2_pow_max<SizeType, typename voider<typename enable_if< numbits_eq<SizeType, 64> >::type>::type>
 275 {
 276    static const SizeType value = 0xb504f333f9de6484ull;
 277    static const std::size_t pow   = 63;
 278 };
 279
 280 #endif   //BOOST_NO_INT64_T
 281
 282 // Returns floor(pow(sqrt(2), x * 2 + 1)).
 283 // Defined for X from 0 up to the number of bits in size_t minus 1.
 284 inline std::size_t sqrt2_pow_2xplus1 (std::size_t x)
 285 {
 286    const std::size_t value = (std::size_t)sqrt2_pow_max<std::size_t>::value;
 287    const std::size_t pow   = (std::size_t)sqrt2_pow_max<std::size_t>::pow;
 288    return (value >> (pow - x)) + 1;
 289 }
 290
 291 } //namespace detail
 292 } //namespace intrusive
 293 } //namespace boost
 294
 295 #endif //BOOST_INTRUSIVE_DETAIL_MATH_HPP