1 ///////////////////////////////////////////////////////////////
2 // Copyright 2013 John Maddock. Distributed under the Boost
3 // Software License, Version 1.0. (See accompanying file
4 // LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_
5 //
6 // Comparison operators for cpp_int_backend:
7 //
8 #ifndef BOOST_MP_DETAIL_BITSCAN_HPP
9 #define BOOST_MP_DETAIL_BITSCAN_HPP
10
11 #include <boost/detail/endian.hpp>
12
13 #if (defined(BOOST_MSVC) || (defined(__clang__) && defined(__c2__)) || (defined(BOOST_INTEL) && defined(_MSC_VER))) && (defined(_M_IX86) || defined(_M_X64))
14 #include <intrin.h>
15 #endif
16
17 namespace boost{ namespace multiprecision{ namespace detail{
18
19 template <class Unsigned>
find_lsb(Unsigned mask,const mpl::int_<0> &)20 inline unsigned find_lsb(Unsigned mask, const mpl::int_<0>&)
21 {
22 unsigned result = 0;
23 while(!(mask & 1u))
24 {
25 mask >>= 1;
26 ++result;
27 }
28 return result;
29 }
30
31 template <class Unsigned>
find_msb(Unsigned mask,const mpl::int_<0> &)32 inline unsigned find_msb(Unsigned mask, const mpl::int_<0>&)
33 {
34 unsigned index = 0;
35 while(mask)
36 {
37 ++index;
38 mask >>= 1;
39 }
40 return --index;
41 }
42
43 #if (defined(BOOST_MSVC) || (defined(__clang__) && defined(__c2__)) || (defined(BOOST_INTEL) && defined(_MSC_VER))) && (defined(_M_IX86) || defined(_M_X64))
44
45 #pragma intrinsic(_BitScanForward,_BitScanReverse)
46
find_lsb(unsigned long mask,const mpl::int_<1> &)47 BOOST_FORCEINLINE unsigned find_lsb(unsigned long mask, const mpl::int_<1>&)
48 {
49 unsigned long result;
50 _BitScanForward(&result, mask);
51 return result;
52 }
53
find_msb(unsigned long mask,const mpl::int_<1> &)54 BOOST_FORCEINLINE unsigned find_msb(unsigned long mask, const mpl::int_<1>&)
55 {
56 unsigned long result;
57 _BitScanReverse(&result, mask);
58 return result;
59 }
60 #ifdef _M_X64
61
62 #pragma intrinsic(_BitScanForward64,_BitScanReverse64)
63
find_lsb(unsigned __int64 mask,const mpl::int_<2> &)64 BOOST_FORCEINLINE unsigned find_lsb(unsigned __int64 mask, const mpl::int_<2>&)
65 {
66 unsigned long result;
67 _BitScanForward64(&result, mask);
68 return result;
69 }
70 template <class Unsigned>
find_msb(Unsigned mask,const mpl::int_<2> &)71 BOOST_FORCEINLINE unsigned find_msb(Unsigned mask, const mpl::int_<2>&)
72 {
73 unsigned long result;
74 _BitScanReverse64(&result, mask);
75 return result;
76 }
77 #endif
78
79 template <class Unsigned>
find_lsb(Unsigned mask)80 BOOST_FORCEINLINE unsigned find_lsb(Unsigned mask)
81 {
82 typedef typename make_unsigned<Unsigned>::type ui_type;
83 typedef typename mpl::if_c<
84 sizeof(Unsigned) <= sizeof(unsigned long),
85 mpl::int_<1>,
86 #ifdef _M_X64
87 typename mpl::if_c<
88 sizeof(Unsigned) <= sizeof(__int64),
89 mpl::int_<2>,
90 mpl::int_<0>
91 >::type
92 #else
93 mpl::int_<0>
94 #endif
95 >::type tag_type;
96 return find_lsb(static_cast<ui_type>(mask), tag_type());
97 }
98
99 template <class Unsigned>
find_msb(Unsigned mask)100 BOOST_FORCEINLINE unsigned find_msb(Unsigned mask)
101 {
102 typedef typename make_unsigned<Unsigned>::type ui_type;
103 typedef typename mpl::if_c<
104 sizeof(Unsigned) <= sizeof(unsigned long),
105 mpl::int_<1>,
106 #ifdef _M_X64
107 typename mpl::if_c<
108 sizeof(Unsigned) <= sizeof(__int64),
109 mpl::int_<2>,
110 mpl::int_<0>
111 >::type
112 #else
113 mpl::int_<0>
114 #endif
115 >::type tag_type;
116 return find_msb(static_cast<ui_type>(mask), tag_type());
117 }
118
119 #elif defined(BOOST_GCC) || defined(__clang__) || (defined(BOOST_INTEL) && defined(__GNUC__))
120
find_lsb(unsigned mask,mpl::int_<1> const &)121 BOOST_FORCEINLINE unsigned find_lsb(unsigned mask, mpl::int_<1> const&)
122 {
123 return __builtin_ctz(mask);
124 }
find_lsb(unsigned long mask,mpl::int_<2> const &)125 BOOST_FORCEINLINE unsigned find_lsb(unsigned long mask, mpl::int_<2> const&)
126 {
127 return __builtin_ctzl(mask);
128 }
find_lsb(boost::ulong_long_type mask,mpl::int_<3> const &)129 BOOST_FORCEINLINE unsigned find_lsb(boost::ulong_long_type mask, mpl::int_<3> const&)
130 {
131 return __builtin_ctzll(mask);
132 }
find_msb(unsigned mask,mpl::int_<1> const &)133 BOOST_FORCEINLINE unsigned find_msb(unsigned mask, mpl::int_<1> const&)
134 {
135 return sizeof(unsigned) * CHAR_BIT - 1 - __builtin_clz(mask);
136 }
find_msb(unsigned long mask,mpl::int_<2> const &)137 BOOST_FORCEINLINE unsigned find_msb(unsigned long mask, mpl::int_<2> const&)
138 {
139 return sizeof(unsigned long) * CHAR_BIT - 1 - __builtin_clzl(mask);
140 }
find_msb(boost::ulong_long_type mask,mpl::int_<3> const &)141 BOOST_FORCEINLINE unsigned find_msb(boost::ulong_long_type mask, mpl::int_<3> const&)
142 {
143 return sizeof(boost::ulong_long_type) * CHAR_BIT - 1 - __builtin_clzll(mask);
144 }
145 #ifdef BOOST_HAS_INT128
146
147 __extension__ typedef unsigned __int128 uint128_type;
148
find_msb(uint128_type mask,mpl::int_<0> const &)149 BOOST_FORCEINLINE unsigned find_msb(uint128_type mask, mpl::int_<0> const&)
150 {
151 union { uint128_type v; boost::uint64_t sv[2]; } val;
152 val.v = mask;
153 #ifdef BOOST_LITTLE_ENDIAN
154 if(val.sv[1])
155 return find_msb(val.sv[1], mpl::int_<3>()) + 64;
156 return find_msb(val.sv[0], mpl::int_<3>());
157 #else
158 if(val.sv[0])
159 return find_msb(val.sv[0], mpl::int_<3>()) + 64;
160 return find_msb(val.sv[1], mpl::int_<3>());
161 #endif
162 }
find_lsb(uint128_type mask,mpl::int_<0> const &)163 BOOST_FORCEINLINE unsigned find_lsb(uint128_type mask, mpl::int_<0> const&)
164 {
165 union { uint128_type v; boost::uint64_t sv[2]; } val;
166 val.v = mask;
167 #ifdef BOOST_LITTLE_ENDIAN
168 if(val.sv[0] == 0)
169 return find_lsb(val.sv[1], mpl::int_<3>()) + 64;
170 return find_lsb(val.sv[0], mpl::int_<3>());
171 #else
172 if(val.sv[1] == 0)
173 return find_lsb(val.sv[0], mpl::int_<3>()) + 64;
174 return find_lsb(val.sv[1], mpl::int_<3>());
175 #endif
176 }
177 #endif
178
179 template <class Unsigned>
find_lsb(Unsigned mask)180 BOOST_FORCEINLINE unsigned find_lsb(Unsigned mask)
181 {
182 typedef typename make_unsigned<Unsigned>::type ui_type;
183 typedef typename mpl::if_c<
184 sizeof(Unsigned) <= sizeof(unsigned),
185 mpl::int_<1>,
186 typename mpl::if_c<
187 sizeof(Unsigned) <= sizeof(unsigned long),
188 mpl::int_<2>,
189 typename mpl::if_c<
190 sizeof(Unsigned) <= sizeof(boost::ulong_long_type),
191 mpl::int_<3>,
192 mpl::int_<0>
193 >::type
194 >::type
195 >::type tag_type;
196 return find_lsb(static_cast<ui_type>(mask), tag_type());
197 }
198 template <class Unsigned>
find_msb(Unsigned mask)199 BOOST_FORCEINLINE unsigned find_msb(Unsigned mask)
200 {
201 typedef typename make_unsigned<Unsigned>::type ui_type;
202 typedef typename mpl::if_c<
203 sizeof(Unsigned) <= sizeof(unsigned),
204 mpl::int_<1>,
205 typename mpl::if_c<
206 sizeof(Unsigned) <= sizeof(unsigned long),
207 mpl::int_<2>,
208 typename mpl::if_c<
209 sizeof(Unsigned) <= sizeof(boost::ulong_long_type),
210 mpl::int_<3>,
211 mpl::int_<0>
212 >::type
213 >::type
214 >::type tag_type;
215 return find_msb(static_cast<ui_type>(mask), tag_type());
216 }
217 #elif defined(BOOST_INTEL)
find_lsb(unsigned mask,mpl::int_<1> const &)218 BOOST_FORCEINLINE unsigned find_lsb(unsigned mask, mpl::int_<1> const&)
219 {
220 return _bit_scan_forward(mask);
221 }
find_msb(unsigned mask,mpl::int_<1> const &)222 BOOST_FORCEINLINE unsigned find_msb(unsigned mask, mpl::int_<1> const&)
223 {
224 return _bit_scan_reverse(mask);
225 }
226 template <class Unsigned>
find_lsb(Unsigned mask)227 BOOST_FORCEINLINE unsigned find_lsb(Unsigned mask)
228 {
229 typedef typename make_unsigned<Unsigned>::type ui_type;
230 typedef typename mpl::if_c<
231 sizeof(Unsigned) <= sizeof(unsigned),
232 mpl::int_<1>,
233 mpl::int_<0>
234 >::type tag_type;
235 return find_lsb(static_cast<ui_type>(mask), tag_type());
236 }
237 template <class Unsigned>
find_msb(Unsigned mask)238 BOOST_FORCEINLINE unsigned find_msb(Unsigned mask)
239 {
240 typedef typename make_unsigned<Unsigned>::type ui_type;
241 typedef typename mpl::if_c<
242 sizeof(Unsigned) <= sizeof(unsigned),
243 mpl::int_<1>,
244 mpl::int_<0>
245 >::type tag_type;
246 return find_msb(static_cast<ui_type>(mask), tag_type());
247 }
248 #else
249 template <class Unsigned>
find_lsb(Unsigned mask)250 BOOST_FORCEINLINE unsigned find_lsb(Unsigned mask)
251 {
252 return find_lsb(mask, mpl::int_<0>());
253 }
254 template <class Unsigned>
find_msb(Unsigned mask)255 BOOST_FORCEINLINE unsigned find_msb(Unsigned mask)
256 {
257 return find_msb(mask, mpl::int_<0>());
258 }
259 #endif
260
261 }}}
262
263 #endif
264
265