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#include <cstring>
28
29namespace boost {
30namespace intrusive {
31namespace detail {
32
33///////////////////////////
34// floor_log2 Dispatcher
35////////////////////////////
36
37#if defined(_MSC_VER) && (_MSC_VER >= 1300)
38
39 }}} //namespace boost::intrusive::detail
40
41 //Use _BitScanReverseXX intrinsics
42
43 #if defined(_M_X64) || defined(_M_AMD64) || defined(_M_IA64) //64 bit target
44 #define BOOST_INTRUSIVE_BSR_INTRINSIC_64_BIT
45 #endif
46
47 #ifndef __INTRIN_H_ // Avoid including any windows system header
48 #ifdef __cplusplus
49 extern "C" {
50 #endif // __cplusplus
51
52 #if defined(BOOST_INTRUSIVE_BSR_INTRINSIC_64_BIT) //64 bit target
53 unsigned char _BitScanReverse64(unsigned long *index, unsigned __int64 mask);
54 #pragma intrinsic(_BitScanReverse64)
55 #else //32 bit target
56 unsigned char _BitScanReverse(unsigned long *index, unsigned long mask);
57 #pragma intrinsic(_BitScanReverse)
58 #endif
59
60 #ifdef __cplusplus
61 }
62 #endif // __cplusplus
63 #endif // __INTRIN_H_
64
65 #ifdef BOOST_INTRUSIVE_BSR_INTRINSIC_64_BIT
66 #define BOOST_INTRUSIVE_BSR_INTRINSIC _BitScanReverse64
67 #undef BOOST_INTRUSIVE_BSR_INTRINSIC_64_BIT
68 #else
69 #define BOOST_INTRUSIVE_BSR_INTRINSIC _BitScanReverse
70 #endif
71
72 namespace boost {
73 namespace intrusive {
74 namespace detail {
75
76 inline std::size_t floor_log2 (std::size_t x)
77 {
78 unsigned long log2;
79 BOOST_INTRUSIVE_BSR_INTRINSIC( &log2, x );
80 return static_cast<std::size_t>(log2);
81 }
82
83 #undef BOOST_INTRUSIVE_BSR_INTRINSIC
84
85#elif defined(__GNUC__) && ((__GNUC__ >= 4) || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)) //GCC >=3.4
86
87 //Compile-time error in case of missing specialization
88 template<class Uint>
89 struct builtin_clz_dispatch;
90
91 #if defined(BOOST_HAS_LONG_LONG)
92 template<>
93 struct builtin_clz_dispatch< ::boost::ulong_long_type >
94 {
95 static ::boost::ulong_long_type call(::boost::ulong_long_type n)
96 { return (::boost::ulong_long_type)__builtin_clzll(n); }
97 };
98 #endif
99
100 template<>
101 struct builtin_clz_dispatch<unsigned long>
102 {
103 static unsigned long call(unsigned long n)
104 { return (unsigned long)__builtin_clzl(n); }
105 };
106
107 template<>
108 struct builtin_clz_dispatch<unsigned int>
109 {
110 static unsigned int call(unsigned int n)
111 { return (unsigned int)__builtin_clz(n); }
112 };
113
114 inline std::size_t floor_log2(std::size_t n)
115 {
116 return sizeof(std::size_t)*CHAR_BIT - std::size_t(1) - builtin_clz_dispatch<std::size_t>::call(n);
117 }
118
119#else //Portable methods
120
121////////////////////////////
122// Generic method
123////////////////////////////
124
125 inline std::size_t floor_log2_get_shift(std::size_t n, true_ )//power of two size_t
126 { return n >> 1; }
127
128 inline std::size_t floor_log2_get_shift(std::size_t n, false_ )//non-power of two size_t
129 { return (n >> 1) + ((n & 1u) & (n != 1)); }
130
131 template<std::size_t N>
132 inline std::size_t floor_log2 (std::size_t x, integral_constant<std::size_t, N>)
133 {
134 const std::size_t Bits = N;
135 const bool Size_t_Bits_Power_2= !(Bits & (Bits-1));
136
137 std::size_t n = x;
138 std::size_t log2 = 0;
139
140 std::size_t remaining_bits = Bits;
141 std::size_t shift = floor_log2_get_shift(remaining_bits, bool_<Size_t_Bits_Power_2>());
142 while(shift){
143 std::size_t tmp = n >> shift;
144 if (tmp){
145 log2 += shift, n = tmp;
146 }
147 shift = floor_log2_get_shift(shift, bool_<Size_t_Bits_Power_2>());
148 }
149
150 return log2;
151 }
152
153 inline std::size_t floor_log2 (std::size_t x)
154 {
155 const std::size_t Bits = sizeof(std::size_t)*CHAR_BIT;
156 return floor_log2(x, integral_constant<std::size_t, Bits>());
157 }
158
159#endif
160
161//Thanks to Laurent de Soras in
162//http://www.flipcode.com/archives/Fast_log_Function.shtml
163inline float fast_log2 (float val)
164{
165 unsigned x;
166 std::memcpy(dest: &x, src: &val, n: sizeof(float));
167 const int log_2 = int((x >> 23) & 255) - 128;
168 x &= ~(unsigned(255u) << 23u);
169 x += unsigned(127) << 23u;
170 std::memcpy(dest: &val, src: &x, n: sizeof(float));
171 //1+log2(m), m ranging from 1 to 2
172 //3rd degree polynomial keeping first derivate continuity.
173 //For less precision the line can be commented out
174 val = ((-1.f/3.f) * val + 2.f) * val - (2.f/3.f);
175 return val + static_cast<float>(log_2);
176}
177
178inline bool is_pow2(std::size_t x)
179{ return (x & (x-1)) == 0; }
180
181template<std::size_t N>
182struct static_is_pow2
183{
184 static const bool value = (N & (N-1)) == 0;
185};
186
187inline std::size_t ceil_log2 (std::size_t x)
188{
189 return static_cast<std::size_t>(!(is_pow2)(x)) + floor_log2(n: x);
190}
191
192inline std::size_t ceil_pow2 (std::size_t x)
193{
194 return std::size_t(1u) << (ceil_log2)(x);
195}
196
197inline std::size_t previous_or_equal_pow2(std::size_t x)
198{
199 return std::size_t(1u) << floor_log2(n: x);
200}
201
202template<class SizeType, std::size_t N>
203struct numbits_eq
204{
205 static const bool value = sizeof(SizeType)*CHAR_BIT == N;
206};
207
208template<class SizeType, class Enabler = void >
209struct sqrt2_pow_max;
210
211template <class SizeType>
212struct sqrt2_pow_max<SizeType, typename voider<typename enable_if< numbits_eq<SizeType, 32> >::type>::type>
213{
214 static const SizeType value = 0xb504f334;
215 static const std::size_t pow = 31;
216};
217
218#ifndef BOOST_NO_INT64_T
219
220template <class SizeType>
221struct sqrt2_pow_max<SizeType, typename voider<typename enable_if< numbits_eq<SizeType, 64> >::type>::type>
222{
223 static const SizeType value = 0xb504f333f9de6484ull;
224 static const std::size_t pow = 63;
225};
226
227#endif //BOOST_NO_INT64_T
228
229// Returns floor(pow(sqrt(2), x * 2 + 1)).
230// Defined for X from 0 up to the number of bits in size_t minus 1.
231inline std::size_t sqrt2_pow_2xplus1 (std::size_t x)
232{
233 const std::size_t value = (std::size_t)sqrt2_pow_max<std::size_t>::value;
234 const std::size_t pow = (std::size_t)sqrt2_pow_max<std::size_t>::pow;
235 return (value >> (pow - x)) + 1;
236}
237
238} //namespace detail
239} //namespace intrusive
240} //namespace boost
241
242#endif //BOOST_INTRUSIVE_DETAIL_MATH_HPP
243

source code of boost/libs/intrusive/include/boost/intrusive/detail/math.hpp