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 https://www.boost.org/LICENSE_1_0.txt
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 <cstdint>
12#include <climits>
13#include <type_traits>
14#include <boost/multiprecision/detail/endian.hpp>
15#include <boost/multiprecision/detail/standalone_config.hpp>
16
17#if (defined(BOOST_MSVC) || (defined(__clang__) && defined(__c2__)) || (defined(BOOST_INTEL) && defined(_MSC_VER))) && (defined(_M_IX86) || defined(_M_X64))
18#include <intrin.h>
19#endif
20
21namespace boost { namespace multiprecision { namespace detail {
22
23template <class Unsigned>
24inline BOOST_MP_CXX14_CONSTEXPR std::size_t find_lsb_default(Unsigned mask)
25{
26 std::size_t result = 0;
27 while (!(mask & 1u))
28 {
29 mask >>= 1;
30 ++result;
31 }
32 return result;
33}
34
35template <class Unsigned>
36inline BOOST_MP_CXX14_CONSTEXPR std::size_t find_msb_default(Unsigned mask)
37{
38 std::size_t index = 0;
39 while (mask)
40 {
41 ++index;
42 mask >>= 1;
43 }
44 return --index;
45}
46
47template <class Unsigned>
48inline BOOST_MP_CXX14_CONSTEXPR std::size_t find_lsb(Unsigned mask, const std::integral_constant<int, 0>&)
49{
50 return find_lsb_default(mask);
51}
52
53template <class Unsigned>
54inline BOOST_MP_CXX14_CONSTEXPR std::size_t find_msb(Unsigned mask, const std::integral_constant<int, 0>&)
55{
56 return find_msb_default(mask);
57}
58
59#if (defined(BOOST_MSVC) || (defined(__clang__) && defined(__c2__)) || (defined(BOOST_INTEL) && defined(_MSC_VER))) && (defined(_M_IX86) || defined(_M_X64))
60
61#pragma intrinsic(_BitScanForward, _BitScanReverse)
62
63BOOST_FORCEINLINE std::size_t find_lsb(unsigned long mask, const std::integral_constant<int, 1>&)
64{
65 unsigned long result;
66 _BitScanForward(&result, mask);
67 return result;
68}
69
70BOOST_FORCEINLINE std::size_t find_msb(unsigned long mask, const std::integral_constant<int, 1>&)
71{
72 unsigned long result;
73 _BitScanReverse(&result, mask);
74 return result;
75}
76#ifdef _M_X64
77
78#pragma intrinsic(_BitScanForward64, _BitScanReverse64)
79
80BOOST_FORCEINLINE std::size_t find_lsb(unsigned __int64 mask, const std::integral_constant<int, 2>&)
81{
82 unsigned long result;
83 _BitScanForward64(&result, mask);
84 return result;
85}
86template <class Unsigned>
87BOOST_FORCEINLINE std::size_t find_msb(Unsigned mask, const std::integral_constant<int, 2>&)
88{
89 unsigned long result;
90 _BitScanReverse64(&result, mask);
91 return result;
92}
93#endif
94
95template <class Unsigned>
96BOOST_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR std::size_t find_lsb(Unsigned mask)
97{
98 using ui_type = typename boost::multiprecision::detail::make_unsigned<Unsigned>::type;
99 using tag_type = typename std::conditional<
100 sizeof(Unsigned) <= sizeof(unsigned long),
101 std::integral_constant<int, 1>,
102#ifdef _M_X64
103 typename std::conditional<
104 sizeof(Unsigned) <= sizeof(__int64),
105 std::integral_constant<int, 2>,
106 std::integral_constant<int, 0> >::type
107#else
108 std::integral_constant<int, 0>
109#endif
110 >::type;
111#ifndef BOOST_MP_NO_CONSTEXPR_DETECTION
112 if (BOOST_MP_IS_CONST_EVALUATED(mask))
113 {
114 return find_lsb_default(mask);
115 }
116 else
117#endif
118 return find_lsb(static_cast<ui_type>(mask), tag_type());
119}
120
121template <class Unsigned>
122BOOST_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR std::size_t find_msb(Unsigned mask)
123{
124 using ui_type = typename boost::multiprecision::detail::make_unsigned<Unsigned>::type;
125 using tag_type = typename std::conditional<
126 sizeof(Unsigned) <= sizeof(unsigned long),
127 std::integral_constant<int, 1>,
128#ifdef _M_X64
129 typename std::conditional<
130 sizeof(Unsigned) <= sizeof(__int64),
131 std::integral_constant<int, 2>,
132 std::integral_constant<int, 0> >::type
133#else
134 std::integral_constant<int, 0>
135#endif
136 >::type;
137#ifndef BOOST_MP_NO_CONSTEXPR_DETECTION
138 if (BOOST_MP_IS_CONST_EVALUATED(mask))
139 {
140 return find_msb_default(mask);
141 }
142 else
143#endif
144 return find_msb(static_cast<ui_type>(mask), tag_type());
145}
146
147#elif defined(BOOST_GCC) || defined(__clang__) || (defined(BOOST_INTEL) && defined(__GNUC__))
148
149BOOST_FORCEINLINE std::size_t find_lsb(std::size_t mask, std::integral_constant<int, 1> const&)
150{
151 return static_cast<std::size_t>(__builtin_ctz(static_cast<unsigned int>(mask)));
152}
153BOOST_FORCEINLINE std::size_t find_lsb(unsigned long mask, std::integral_constant<int, 2> const&)
154{
155 return static_cast<std::size_t>(__builtin_ctzl(static_cast<unsigned long>(mask)));
156}
157BOOST_FORCEINLINE std::size_t find_lsb(unsigned long long mask, std::integral_constant<int, 3> const&)
158{
159 return static_cast<std::size_t>(__builtin_ctzll(static_cast<unsigned long long>(mask)));
160}
161BOOST_FORCEINLINE std::size_t find_msb(std::size_t mask, std::integral_constant<int, 1> const&)
162{
163 return static_cast<std::size_t>(static_cast<std::size_t>(sizeof(unsigned) * static_cast<std::size_t>(CHAR_BIT) - 1u) - static_cast<std::size_t>(__builtin_clz(static_cast<unsigned int>(mask))));
164}
165BOOST_FORCEINLINE std::size_t find_msb(unsigned long mask, std::integral_constant<int, 2> const&)
166{
167 return static_cast<std::size_t>(static_cast<std::size_t>(sizeof(unsigned long) * static_cast<std::size_t>(CHAR_BIT) - 1u) - static_cast<std::size_t>(__builtin_clzl(static_cast<unsigned long>(mask))));
168}
169BOOST_FORCEINLINE std::size_t find_msb(unsigned long long mask, std::integral_constant<int, 3> const&)
170{
171 return static_cast<std::size_t>(static_cast<std::size_t>(sizeof(unsigned long long) * static_cast<std::size_t>(CHAR_BIT) - 1u) - static_cast<std::size_t>(__builtin_clzll(static_cast<unsigned long long>(mask))));
172}
173#ifdef BOOST_HAS_INT128
174
175BOOST_FORCEINLINE std::size_t find_msb(uint128_type mask, std::integral_constant<int, 0> const&)
176{
177 union
178 {
179 uint128_type v;
180 std::uint64_t sv[2];
181 } val;
182 val.v = mask;
183#if BOOST_MP_ENDIAN_LITTLE_BYTE
184 if (val.sv[1])
185 return find_msb(mask: val.sv[1], std::integral_constant<int, 3>()) + 64;
186 return find_msb(mask: val.sv[0], std::integral_constant<int, 3>());
187#else
188 if (val.sv[0])
189 return find_msb(val.sv[0], std::integral_constant<int, 3>()) + 64;
190 return find_msb(val.sv[1], std::integral_constant<int, 3>());
191#endif
192}
193BOOST_FORCEINLINE std::size_t find_lsb(uint128_type mask, std::integral_constant<int, 0> const&)
194{
195 union
196 {
197 uint128_type v;
198 std::uint64_t sv[2];
199 } val;
200 val.v = mask;
201#if BOOST_MP_ENDIAN_LITTLE_BYTE
202 if (val.sv[0] == 0)
203 return find_lsb(mask: val.sv[1], std::integral_constant<int, 3>()) + 64;
204 return find_lsb(mask: val.sv[0], std::integral_constant<int, 3>());
205#else
206 if (val.sv[1] == 0)
207 return find_lsb(val.sv[0], std::integral_constant<int, 3>()) + 64;
208 return find_lsb(val.sv[1], std::integral_constant<int, 3>());
209#endif
210}
211#endif
212
213template <class Unsigned>
214BOOST_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR std::size_t find_lsb(Unsigned mask)
215{
216 using ui_type = typename boost::multiprecision::detail::make_unsigned<Unsigned>::type;
217 using tag_type = typename std::conditional<
218 sizeof(Unsigned) <= sizeof(unsigned),
219 std::integral_constant<int, 1>,
220 typename std::conditional<
221 sizeof(Unsigned) <= sizeof(unsigned long),
222 std::integral_constant<int, 2>,
223 typename std::conditional<
224 sizeof(Unsigned) <= sizeof(unsigned long long),
225 std::integral_constant<int, 3>,
226 std::integral_constant<int, 0> >::type>::type>::type;
227#ifndef BOOST_MP_NO_CONSTEXPR_DETECTION
228 if (BOOST_MP_IS_CONST_EVALUATED(mask))
229 {
230 return find_lsb_default(mask);
231 }
232 else
233#endif
234 return find_lsb(static_cast<ui_type>(mask), tag_type());
235}
236template <class Unsigned>
237BOOST_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR std::size_t find_msb(Unsigned mask)
238{
239 using ui_type = typename boost::multiprecision::detail::make_unsigned<Unsigned>::type;
240 using tag_type = typename std::conditional<
241 sizeof(Unsigned) <= sizeof(unsigned),
242 std::integral_constant<int, 1>,
243 typename std::conditional<
244 sizeof(Unsigned) <= sizeof(unsigned long),
245 std::integral_constant<int, 2>,
246 typename std::conditional<
247 sizeof(Unsigned) <= sizeof(unsigned long long),
248 std::integral_constant<int, 3>,
249 std::integral_constant<int, 0> >::type>::type>::type;
250#ifndef BOOST_MP_NO_CONSTEXPR_DETECTION
251 if (BOOST_MP_IS_CONST_EVALUATED(mask))
252 {
253 return find_msb_default(mask);
254 }
255 else
256#endif
257 return find_msb(static_cast<ui_type>(mask), tag_type());
258}
259#elif defined(BOOST_INTEL)
260BOOST_FORCEINLINE std::size_t find_lsb(std::size_t mask, std::integral_constant<int, 1> const&)
261{
262 return _bit_scan_forward(mask);
263}
264BOOST_FORCEINLINE std::size_t find_msb(std::size_t mask, std::integral_constant<int, 1> const&)
265{
266 return _bit_scan_reverse(mask);
267}
268template <class Unsigned>
269BOOST_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR std::size_t find_lsb(Unsigned mask)
270{
271 using ui_type = typename boost::multiprecision::detail::make_unsigned<Unsigned>::type;
272 using tag_type = typename std::conditional<
273 sizeof(Unsigned) <= sizeof(unsigned),
274 std::integral_constant<int, 1>,
275 std::integral_constant<int, 0> >::type;
276#ifndef BOOST_MP_NO_CONSTEXPR_DETECTION
277 if (BOOST_MP_IS_CONST_EVALUATED(mask))
278 {
279 return find_lsb_default(mask);
280 }
281 else
282#endif
283 return find_lsb(static_cast<ui_type>(mask), tag_type());
284}
285template <class Unsigned>
286BOOST_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR std::size_t find_msb(Unsigned mask)
287{
288 using ui_type = typename boost::multiprecision::detail::make_unsigned<Unsigned>::type;
289 using tag_type = typename std::conditional<
290 sizeof(Unsigned) <= sizeof(unsigned),
291 std::integral_constant<int, 1>,
292 std::integral_constant<int, 0> >::type;
293#ifndef BOOST_MP_NO_CONSTEXPR_DETECTION
294 if (BOOST_MP_IS_CONST_EVALUATED(mask))
295 {
296 return find_msb_default(mask);
297 }
298 else
299#endif
300 return find_msb(static_cast<ui_type>(mask), tag_type());
301}
302#else
303template <class Unsigned>
304BOOST_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR std::size_t find_lsb(Unsigned mask)
305{
306 return find_lsb(mask, std::integral_constant<int, 0>());
307}
308template <class Unsigned>
309BOOST_FORCEINLINE BOOST_MP_CXX14_CONSTEXPR std::size_t find_msb(Unsigned mask)
310{
311 return find_msb(mask, std::integral_constant<int, 0>());
312}
313#endif
314
315}}} // namespace boost::multiprecision::detail
316
317#endif
318

source code of boost/libs/multiprecision/include/boost/multiprecision/detail/bitscan.hpp