]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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 enable_if< numbits_eq<SizeType, 32> >::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 enable_if< numbits_eq<SizeType, 64> >::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 |