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
29 namespace boost {
30 namespace intrusive {
31 namespace 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
floor_log2(std::size_t x)76 inline std::size_t floor_log2 (std::size_t x)
77 {
78 unsigned long log2;
79 BOOST_INTRUSIVE_BSR_INTRINSIC( &log2, (unsigned long)x );
80 return 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 __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 __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 __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 ////////////////////////////
154 // DeBruijn method
155 ////////////////////////////
156
157 //Taken from:
158 //http://stackoverflow.com/questions/11376288/fast-computing-of-log2-for-64-bit-integers
159 //Thanks to Desmond Hume
160
161 inline std::size_t floor_log2 (std::size_t v, integral_constant<std::size_t, 32>)
162 {
163 static const int MultiplyDeBruijnBitPosition[32] =
164 {
165 0, 9, 1, 10, 13, 21, 2, 29, 11, 14, 16, 18, 22, 25, 3, 30,
166 8, 12, 20, 28, 15, 17, 24, 7, 19, 27, 23, 6, 26, 5, 4, 31
167 };
168
169 v |= v >> 1;
170 v |= v >> 2;
171 v |= v >> 4;
172 v |= v >> 8;
173 v |= v >> 16;
174
175 return MultiplyDeBruijnBitPosition[(std::size_t)(v * 0x07C4ACDDU) >> 27];
176 }
177
178 inline std::size_t floor_log2 (std::size_t v, integral_constant<std::size_t, 64>)
179 {
180 static const std::size_t MultiplyDeBruijnBitPosition[64] = {
181 63, 0, 58, 1, 59, 47, 53, 2,
182 60, 39, 48, 27, 54, 33, 42, 3,
183 61, 51, 37, 40, 49, 18, 28, 20,
184 55, 30, 34, 11, 43, 14, 22, 4,
185 62, 57, 46, 52, 38, 26, 32, 41,
186 50, 36, 17, 19, 29, 10, 13, 21,
187 56, 45, 25, 31, 35, 16, 9, 12,
188 44, 24, 15, 8, 23, 7, 6, 5};
189
190 v |= v >> 1;
191 v |= v >> 2;
192 v |= v >> 4;
193 v |= v >> 8;
194 v |= v >> 16;
195 v |= v >> 32;
196 return MultiplyDeBruijnBitPosition[((std::size_t)((v - (v >> 1))*0x07EDD5E59A4E28C2ULL)) >> 58];
197 }
198
199
200 inline std::size_t floor_log2 (std::size_t x)
201 {
202 const std::size_t Bits = sizeof(std::size_t)*CHAR_BIT;
203 return floor_log2(x, integral_constant<std::size_t, Bits>());
204 }
205
206 #endif
207
208 //Thanks to Laurent de Soras in
209 //http://www.flipcode.com/archives/Fast_log_Function.shtml
fast_log2(float val)210 inline float fast_log2 (float val)
211 {
212 float f = val;
213 unsigned x;
214 std::memcpy(&x, &val, sizeof(f));
215 const int log_2 = int((x >> 23) & 255) - 128;
216 x &= ~(unsigned(255u) << 23u);
217 x += unsigned(127) << 23u;
218 std::memcpy(&val, &x, sizeof(f));
219 //1+log2(m), m ranging from 1 to 2
220 //3rd degree polynomial keeping first derivate continuity.
221 //For less precision the line can be commented out
222 val = ((-1.f/3.f) * val + 2.f) * val - (2.f/3.f);
223 return val + static_cast<float>(log_2);
224 }
225
is_pow2(std::size_t x)226 inline bool is_pow2(std::size_t x)
227 { return (x & (x-1)) == 0; }
228
229 template<std::size_t N>
230 struct static_is_pow2
231 {
232 static const bool value = (N & (N-1)) == 0;
233 };
234
ceil_log2(std::size_t x)235 inline std::size_t ceil_log2 (std::size_t x)
236 {
237 return static_cast<std::size_t>(!(is_pow2)(x)) + floor_log2(x);
238 }
239
ceil_pow2(std::size_t x)240 inline std::size_t ceil_pow2 (std::size_t x)
241 {
242 return std::size_t(1u) << (ceil_log2)(x);
243 }
244
previous_or_equal_pow2(std::size_t x)245 inline std::size_t previous_or_equal_pow2(std::size_t x)
246 {
247 return std::size_t(1u) << floor_log2(x);
248 }
249
250 template<class SizeType, std::size_t N>
251 struct numbits_eq
252 {
253 static const bool value = sizeof(SizeType)*CHAR_BIT == N;
254 };
255
256 template<class SizeType, class Enabler = void >
257 struct sqrt2_pow_max;
258
259 template <class SizeType>
260 struct sqrt2_pow_max<SizeType, typename voider<typename enable_if< numbits_eq<SizeType, 32> >::type>::type>
261 {
262 static const SizeType value = 0xb504f334;
263 static const std::size_t pow = 31;
264 };
265
266 #ifndef BOOST_NO_INT64_T
267
268 template <class SizeType>
269 struct sqrt2_pow_max<SizeType, typename voider<typename enable_if< numbits_eq<SizeType, 64> >::type>::type>
270 {
271 static const SizeType value = 0xb504f333f9de6484ull;
272 static const std::size_t pow = 63;
273 };
274
275 #endif //BOOST_NO_INT64_T
276
277 // Returns floor(pow(sqrt(2), x * 2 + 1)).
278 // Defined for X from 0 up to the number of bits in size_t minus 1.
sqrt2_pow_2xplus1(std::size_t x)279 inline std::size_t sqrt2_pow_2xplus1 (std::size_t x)
280 {
281 const std::size_t value = (std::size_t)sqrt2_pow_max<std::size_t>::value;
282 const std::size_t pow = (std::size_t)sqrt2_pow_max<std::size_t>::pow;
283 return (value >> (pow - x)) + 1;
284 }
285
286 } //namespace detail
287 } //namespace intrusive
288 } //namespace boost
289
290 #endif //BOOST_INTRUSIVE_DETAIL_MATH_HPP
291