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