]> git.proxmox.com Git - ceph.git/blame - ceph/src/boost/libs/multiprecision/include/boost/multiprecision/cpp_int/multiply.hpp
projects / ceph.git / blame
? search:
summary | shortlog | log | commit | commitdiff | tree
blob | blame (incremental) | history | HEAD
bump version to 12.2.2-pve1
[ceph.git] / ceph / src / boost / libs / multiprecision / include / boost / multiprecision / cpp_int / multiply.hpp
CommitLineData
7c673cae
FG		 1///////////////////////////////////////////////////////////////
2// Copyright 2012 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_CPP_INT_MUL_HPP
9#define BOOST_MP_CPP_INT_MUL_HPP
10
11namespace boost{ namespace multiprecision{ namespace backends{
12
13#ifdef _MSC_VER
14#pragma warning(push)
15#pragma warning(disable:4127) // conditional expression is constant
16#endif
17
18 template <unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1, unsigned MinBits2, unsigned MaxBits2, cpp_integer_type SignType2, cpp_int_check_type Checked2, class Allocator2>
19inline typename enable_if_c<!is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value && !is_trivial_cpp_int<cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2> >::value >::type
20 eval_multiply(
21 cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& result,
22 const cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>& a,
23 const limb_type& val) BOOST_MP_NOEXCEPT_IF((is_non_throwing_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value))
24{
25 if(!val)
26 {
27 result = static_cast<limb_type>(0);
28 return;
29 }
30 if((void*)&a != (void*)&result)
31 result.resize(a.size(), a.size());
32 double_limb_type carry = 0;
33 typename cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>::limb_pointer p = result.limbs();
34 typename cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>::limb_pointer pe = result.limbs() + result.size();
35 typename cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>::const_limb_pointer pa = a.limbs();
36 while(p != pe)
37 {
38 carry += static_cast<double_limb_type>(*pa) * static_cast<double_limb_type>(val);
39#ifdef __MSVC_RUNTIME_CHECKS
40 *p = static_cast<limb_type>(carry & ~static_cast<limb_type>(0));
41#else
42 *p = static_cast<limb_type>(carry);
43#endif
44 carry >>= cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>::limb_bits;
45 ++p, ++pa;
46 }
47 if(carry)
48 {
49 unsigned i = result.size();
50 result.resize(i + 1, i + 1);
51 if(cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>::variable || (result.size() > i))
52 result.limbs()[i] = static_cast<limb_type>(carry);
53 }
54 result.sign(a.sign());
55 if(!cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>::variable)
56 result.normalize();
57}
58
59//
60// resize_for_carry forces a resize of the underlying buffer only if a previous request
61// for "required" elements could possibly have failed, *and* we have checking enabled.
62// This will cause an overflow error inside resize():
63//
64template <unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1>
65inline void resize_for_carry(cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& /*result*/, unsigned /*required*/){}
66
67template <unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1>
68inline void resize_for_carry(cpp_int_backend<MinBits1, MaxBits1, SignType1, checked, void>& result, unsigned required)
69{
70 if(result.size() != required)
71 result.resize(required, required);
72}
73
74template <unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1, unsigned MinBits2, unsigned MaxBits2, cpp_integer_type SignType2, cpp_int_check_type Checked2, class Allocator2, unsigned MinBits3, unsigned MaxBits3, cpp_integer_type SignType3, cpp_int_check_type Checked3, class Allocator3>
75inline typename enable_if_c<!is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value && !is_trivial_cpp_int<cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2> >::value && !is_trivial_cpp_int<cpp_int_backend<MinBits3, MaxBits3, SignType3, Checked3, Allocator3> >::value >::type
76 eval_multiply(
77 cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& result,
78 const cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>& a,
79 const cpp_int_backend<MinBits3, MaxBits3, SignType3, Checked3, Allocator3>& b) BOOST_MP_NOEXCEPT_IF((is_non_throwing_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value))
80{
81 // Very simple long multiplication, only usable for small numbers of limb_type's
82 // but that's the typical use case for this type anyway:
83 //
84 // Special cases first:
85 //
86 unsigned as = a.size();
87 unsigned bs = b.size();
88 typename cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>::const_limb_pointer pa = a.limbs();
89 typename cpp_int_backend<MinBits3, MaxBits3, SignType3, Checked3, Allocator3>::const_limb_pointer pb = b.limbs();
90 if(as == 1)
91 {
92 bool s = b.sign() != a.sign();
93 if(bs == 1)
94 {
95 result = static_cast<double_limb_type>(*pa) * static_cast<double_limb_type>(*pb);
96 }
97 else
98 {
99 limb_type l = *pa;
100 eval_multiply(result, b, l);
101 }
102 result.sign(s);
103 return;
104 }
105 if(bs == 1)
106 {
107 bool s = b.sign() != a.sign();
108 limb_type l = *pb;
109 eval_multiply(result, a, l);
110 result.sign(s);
111 return;
112 }
113
114 if((void*)&result == (void*)&a)
115 {
116 cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> t(a);
117 eval_multiply(result, t, b);
118 return;
119 }
120 if((void*)&result == (void*)&b)
121 {
122 cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> t(b);
123 eval_multiply(result, a, t);
124 return;
125 }
126
127 result.resize(as + bs, as + bs - 1);
128 typename cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>::limb_pointer pr = result.limbs();
129
130 static const double_limb_type limb_max = ~static_cast<limb_type>(0u);
131 static const double_limb_type double_limb_max = ~static_cast<double_limb_type>(0u);
132 BOOST_STATIC_ASSERT(double_limb_max - 2 * limb_max >= limb_max * limb_max);
133
134 double_limb_type carry = 0;
135 std::memset(pr, 0, result.size() * sizeof(limb_type));
136 for(unsigned i = 0; i < as; ++i)
137 {
138 unsigned inner_limit = cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>::variable ? bs : (std::min)(result.size() - i, bs);
139 for(unsigned j = 0; j < inner_limit; ++j)
140 {
141 BOOST_ASSERT(i+j < result.size());
142#if (!defined(__GLIBCXX__) && !defined(__GLIBCPP__)) || !BOOST_WORKAROUND(BOOST_GCC_VERSION, <= 50100)
143 BOOST_ASSERT(!std::numeric_limits<double_limb_type>::is_specialized
144 || ((std::numeric_limits<double_limb_type>::max)() - carry
145 >
146 static_cast<double_limb_type>(cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>::max_limb_value) * static_cast<double_limb_type>(cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>::max_limb_value)));
147#endif
148 carry += static_cast<double_limb_type>(pa[i]) * static_cast<double_limb_type>(pb[j]);
149 BOOST_ASSERT(!std::numeric_limits<double_limb_type>::is_specialized || ((std::numeric_limits<double_limb_type>::max)() - carry >= pr[i+j]));
150 carry += pr[i + j];
151#ifdef __MSVC_RUNTIME_CHECKS
152 pr[i + j] = static_cast<limb_type>(carry & ~static_cast<limb_type>(0));
153#else
154 pr[i + j] = static_cast<limb_type>(carry);
155#endif
156 carry >>= cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>::limb_bits;
157 BOOST_ASSERT(carry <= (cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>::max_limb_value));
158 }
159 resize_for_carry(result, as + bs); // May throw if checking is enabled
160 if(cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>::variable || (i + bs < result.size()))
161 pr[i + bs] = static_cast<limb_type>(carry);
162 carry = 0;
163 }
164 result.normalize();
165 //
166 // Set the sign of the result:
167 //
168 result.sign(a.sign() != b.sign());
169}
170
171template <unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1, unsigned MinBits2, unsigned MaxBits2, cpp_integer_type SignType2, cpp_int_check_type Checked2, class Allocator2>
172BOOST_MP_FORCEINLINE typename enable_if_c<!is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value && !is_trivial_cpp_int<cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2> >::value >::type
173 eval_multiply(
174 cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& result,
175 const cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>& a) BOOST_MP_NOEXCEPT_IF((is_non_throwing_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value))
176{
177 eval_multiply(result, result, a);
178}
179
180template <unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1>
181BOOST_MP_FORCEINLINE typename enable_if_c<!is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value>::type
182 eval_multiply(cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& result, const limb_type& val) BOOST_MP_NOEXCEPT_IF((is_non_throwing_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value))
183{
184 eval_multiply(result, result, val);
185}
186
187template <unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1, unsigned MinBits2, unsigned MaxBits2, cpp_integer_type SignType2, cpp_int_check_type Checked2, class Allocator2>
188BOOST_MP_FORCEINLINE typename enable_if_c<!is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value && !is_trivial_cpp_int<cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2> >::value >::type
189 eval_multiply(
190 cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& result,
191 const cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>& a,
192 const double_limb_type& val) BOOST_MP_NOEXCEPT_IF((is_non_throwing_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value))
193{
194 if(val <= (std::numeric_limits<limb_type>::max)())
195 {
196 eval_multiply(result, a, static_cast<limb_type>(val));
197 }
198 else
199 {
200#if defined(BOOST_LITTLE_ENDIAN) && !defined(BOOST_MP_TEST_NO_LE)
201 cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> t(val);
202#else
203 cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> t;
204 t = val;
205#endif
206 eval_multiply(result, a, t);
207 }
208}
209
210template <unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1>
211BOOST_MP_FORCEINLINE typename enable_if_c<!is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value>::type
212 eval_multiply(cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& result, const double_limb_type& val) BOOST_MP_NOEXCEPT_IF((is_non_throwing_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value))
213{
214 eval_multiply(result, result, val);
215}
216
217template <unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1, unsigned MinBits2, unsigned MaxBits2, cpp_integer_type SignType2, cpp_int_check_type Checked2, class Allocator2>
218BOOST_MP_FORCEINLINE typename enable_if_c<!is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value && !is_trivial_cpp_int<cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2> >::value >::type
219 eval_multiply(
220 cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& result,
221 const cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>& a,
222 const signed_limb_type& val) BOOST_MP_NOEXCEPT_IF((is_non_throwing_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value))
223{
224 if(val > 0)
225 eval_multiply(result, a, static_cast<limb_type>(val));
226 else
227 {
228 eval_multiply(result, a, static_cast<limb_type>(boost::multiprecision::detail::unsigned_abs(val)));
229 result.negate();
230 }
231}
232
233template <unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1>
234BOOST_MP_FORCEINLINE typename enable_if_c<!is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value>::type
235 eval_multiply(cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& result, const signed_limb_type& val) BOOST_MP_NOEXCEPT_IF((is_non_throwing_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value))
236{
237 eval_multiply(result, result, val);
238}
239
240template <unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1, unsigned MinBits2, unsigned MaxBits2, cpp_integer_type SignType2, cpp_int_check_type Checked2, class Allocator2>
241inline typename enable_if_c<!is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value && !is_trivial_cpp_int<cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2> >::value >::type
242 eval_multiply(
243 cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& result,
244 const cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>& a,
245 const signed_double_limb_type& val) BOOST_MP_NOEXCEPT_IF((is_non_throwing_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value))
246{
247 if(val > 0)
248 {
249 if(val <= (std::numeric_limits<limb_type>::max)())
250 {
251 eval_multiply(result, a, static_cast<limb_type>(val));
252 return;
253 }
254 }
255 else if(val >= -static_cast<signed_double_limb_type>((std::numeric_limits<limb_type>::max)()))
256 {
257 eval_multiply(result, a, static_cast<limb_type>(boost::multiprecision::detail::unsigned_abs(val)));
258 result.negate();
259 return;
260 }
261#if defined(BOOST_LITTLE_ENDIAN) && !defined(BOOST_MP_TEST_NO_LE)
262 cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> t(val);
263#else
264 cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> t;
265 t = val;
266#endif
267 eval_multiply(result, a, t);
268}
269
270template <unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1>
271BOOST_MP_FORCEINLINE typename enable_if_c<!is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value>::type
272 eval_multiply(cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& result, const signed_double_limb_type& val) BOOST_MP_NOEXCEPT_IF((is_non_throwing_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value))
273{
274 eval_multiply(result, result, val);
275}
276
277//
278// Now over again for trivial cpp_int's:
279//
280template <unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1>
281BOOST_MP_FORCEINLINE typename enable_if_c<
282 is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value
283 && is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value
284 && (is_signed_number<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value
285 || is_signed_number<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value)
286 >::type
287 eval_multiply(
288 cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& result,
289 const cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& o) BOOST_MP_NOEXCEPT_IF((is_non_throwing_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value))
290{
291 *result.limbs() = detail::checked_multiply(*result.limbs(), *o.limbs(), typename cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>::checked_type());
292 result.sign(result.sign() != o.sign());
293 result.normalize();
294}
295
296template <unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1>
297BOOST_MP_FORCEINLINE typename enable_if_c<
298 is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value
299 && is_unsigned_number<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value
300 >::type
301 eval_multiply(
302 cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& result,
303 const cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& o) BOOST_MP_NOEXCEPT_IF((is_non_throwing_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value))
304{
305 *result.limbs() = detail::checked_multiply(*result.limbs(), *o.limbs(), typename cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>::checked_type());
306 result.normalize();
307}
308
309template <unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1>
310BOOST_MP_FORCEINLINE typename enable_if_c<
311 is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value
312 && is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value
313 && (is_signed_number<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value
314 || is_signed_number<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value)
315 >::type
316 eval_multiply(
317 cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& result,
318 const cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& a,
319 const cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& b) BOOST_MP_NOEXCEPT_IF((is_non_throwing_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value))
320{
321 *result.limbs() = detail::checked_multiply(*a.limbs(), *b.limbs(), typename cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>::checked_type());
322 result.sign(a.sign() != b.sign());
323 result.normalize();
324}
325
326template <unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1>
327BOOST_MP_FORCEINLINE typename enable_if_c<
328 is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value
329 && is_unsigned_number<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value
330 >::type
331 eval_multiply(
332 cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& result,
333 const cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& a,
334 const cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& b) BOOST_MP_NOEXCEPT_IF((is_non_throwing_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value))
335{
336 *result.limbs() = detail::checked_multiply(*a.limbs(), *b.limbs(), typename cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>::checked_type());
337 result.normalize();
338}
339
340//
341// Special routines for multiplying two integers to obtain a multiprecision result:
342//
343template <unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1>
344BOOST_MP_FORCEINLINE typename enable_if_c<
345 !is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value
346 >::type
347 eval_multiply(
348 cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& result,
349 signed_double_limb_type a, signed_double_limb_type b)
350{
351 static const signed_double_limb_type mask = ~static_cast<limb_type>(0);
352 static const unsigned limb_bits = sizeof(limb_type) * CHAR_BIT;
353 bool s = false;
354 double_limb_type w, x, y, z;
355 if(a < 0)
356 {
357 a = -a;
358 s = true;
359 }
360 if(b < 0)
361 {
362 b = -b;
363 s = !s;
364 }
365 w = a & mask;
366 x = a >> limb_bits;
367 y = b & mask;
368 z = b >> limb_bits;
369
370 result.resize(4, 4);
371 limb_type* pr = result.limbs();
372
373 double_limb_type carry = w * y;
374#ifdef __MSVC_RUNTIME_CHECKS
375 pr[0] = static_cast<limb_type>(carry & ~static_cast<limb_type>(0));
376 carry >>= limb_bits;
377 carry += w * z + x * y;
378 pr[1] = static_cast<limb_type>(carry & ~static_cast<limb_type>(0));
379 carry >>= limb_bits;
380 carry += x * z;
381 pr[2] = static_cast<limb_type>(carry & ~static_cast<limb_type>(0));
382 pr[3] = static_cast<limb_type>(carry >> limb_bits);
383#else
384 pr[0] = static_cast<limb_type>(carry);
385 carry >>= limb_bits;
386 carry += w * z + x * y;
387 pr[1] = static_cast<limb_type>(carry);
388 carry >>= limb_bits;
389 carry += x * z;
390 pr[2] = static_cast<limb_type>(carry);
391 pr[3] = static_cast<limb_type>(carry >> limb_bits);
392#endif
393 result.sign(s);
394 result.normalize();
395}
396
397template <unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1>
398BOOST_MP_FORCEINLINE typename enable_if_c<
399 !is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value
400 >::type
401 eval_multiply(
402 cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& result,
403 double_limb_type a, double_limb_type b)
404{
405 static const signed_double_limb_type mask = ~static_cast<limb_type>(0);
406 static const unsigned limb_bits = sizeof(limb_type) * CHAR_BIT;
407
408 double_limb_type w, x, y, z;
409 w = a & mask;
410 x = a >> limb_bits;
411 y = b & mask;
412 z = b >> limb_bits;
413
414 result.resize(4, 4);
415 limb_type* pr = result.limbs();
416
417 double_limb_type carry = w * y;
418#ifdef __MSVC_RUNTIME_CHECKS
419 pr[0] = static_cast<limb_type>(carry & ~static_cast<limb_type>(0));
420 carry >>= limb_bits;
421 carry += w * z;
422 pr[1] = static_cast<limb_type>(carry & ~static_cast<limb_type>(0));
423 carry >>= limb_bits;
424 pr[2] = static_cast<limb_type>(carry & ~static_cast<limb_type>(0));
425 carry = x * y + pr[1];
426 pr[1] = static_cast<limb_type>(carry & ~static_cast<limb_type>(0));
427 carry >>= limb_bits;
428 carry += pr[2] + x * z;
429 pr[2] = static_cast<limb_type>(carry & ~static_cast<limb_type>(0));
430 pr[3] = static_cast<limb_type>(carry >> limb_bits);
431#else
432 pr[0] = static_cast<limb_type>(carry);
433 carry >>= limb_bits;
434 carry += w * z;
435 pr[1] = static_cast<limb_type>(carry);
436 carry >>= limb_bits;
437 pr[2] = static_cast<limb_type>(carry);
438 carry = x * y + pr[1];
439 pr[1] = static_cast<limb_type>(carry);
440 carry >>= limb_bits;
441 carry += pr[2] + x * z;
442 pr[2] = static_cast<limb_type>(carry);
443 pr[3] = static_cast<limb_type>(carry >> limb_bits);
444#endif
445 result.sign(false);
446 result.normalize();
447}
448
449template <unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1,
450 unsigned MinBits2, unsigned MaxBits2, cpp_integer_type SignType2, cpp_int_check_type Checked2, class Allocator2>
451BOOST_MP_FORCEINLINE typename enable_if_c<
452 !is_trivial_cpp_int<cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::value
453 && is_trivial_cpp_int<cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2> >::value
454 && is_trivial_cpp_int<cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2> >::value
455 >::type
456 eval_multiply(
457 cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& result,
458 cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2> const& a,
459 cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2> const& b)
460{
461 typedef typename boost::multiprecision::detail::canonical<typename cpp_int_backend<MinBits2, MaxBits2, SignType2, Checked2, Allocator2>::local_limb_type, cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1> >::type canonical_type;
462 eval_multiply(result, static_cast<canonical_type>(*a.limbs()), static_cast<canonical_type>(*b.limbs()));
463 result.sign(a.sign() != b.sign());
464}
465
466template <unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1, class SI>
467BOOST_MP_FORCEINLINE typename enable_if_c<is_signed<SI>::value && (sizeof(SI) <= sizeof(signed_double_limb_type) / 2)>::type
468 eval_multiply(
469 cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& result,
470 SI a, SI b)
471{
472 result = static_cast<signed_double_limb_type>(a) * static_cast<signed_double_limb_type>(b);
473}
474
475template <unsigned MinBits1, unsigned MaxBits1, cpp_integer_type SignType1, cpp_int_check_type Checked1, class Allocator1, class UI>
476BOOST_MP_FORCEINLINE typename enable_if_c<is_unsigned<UI>::value && (sizeof(UI) <= sizeof(signed_double_limb_type) / 2)>::type
477 eval_multiply(
478 cpp_int_backend<MinBits1, MaxBits1, SignType1, Checked1, Allocator1>& result,
479 UI a, UI b)
480{
481 result = static_cast<double_limb_type>(a) * static_cast<double_limb_type>(b);
482}
483
484#ifdef _MSC_VER
485#pragma warning(pop)
486#endif
487
488}}} // namespaces
489
490#endif
Ceph