]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | /////////////////////////////////////////////////////////////////////////////// |
2 | // Copyright 2011 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_0.txt) | |
5 | ||
6 | #ifndef BOOST_MATH_MP_TOMMATH_BACKEND_HPP | |
7 | #define BOOST_MATH_MP_TOMMATH_BACKEND_HPP | |
8 | ||
9 | #include <boost/multiprecision/number.hpp> | |
10 | #include <boost/multiprecision/rational_adaptor.hpp> | |
11 | #include <boost/multiprecision/detail/integer_ops.hpp> | |
12 | #include <boost/math/special_functions/fpclassify.hpp> | |
13 | #include <boost/cstdint.hpp> | |
14 | #include <boost/scoped_array.hpp> | |
15 | #include <boost/functional/hash_fwd.hpp> | |
16 | #include <tommath.h> | |
17 | #include <cmath> | |
18 | #include <limits> | |
19 | #include <climits> | |
20 | ||
21 | namespace boost{ namespace multiprecision{ namespace backends{ | |
22 | ||
23 | namespace detail{ | |
24 | ||
25 | inline void check_tommath_result(unsigned v) | |
26 | { | |
27 | if(v != MP_OKAY) | |
28 | { | |
29 | BOOST_THROW_EXCEPTION(std::runtime_error(mp_error_to_string(v))); | |
30 | } | |
31 | } | |
32 | ||
33 | } | |
34 | ||
35 | struct tommath_int; | |
36 | ||
37 | void eval_multiply(tommath_int& t, const tommath_int& o); | |
38 | void eval_add(tommath_int& t, const tommath_int& o); | |
39 | ||
40 | struct tommath_int | |
41 | { | |
42 | typedef mpl::list<boost::int32_t, boost::long_long_type> signed_types; | |
43 | typedef mpl::list<boost::uint32_t, boost::ulong_long_type> unsigned_types; | |
44 | typedef mpl::list<long double> float_types; | |
45 | ||
46 | tommath_int() | |
47 | { | |
48 | detail::check_tommath_result(mp_init(&m_data)); | |
49 | } | |
50 | tommath_int(const tommath_int& o) | |
51 | { | |
52 | detail::check_tommath_result(mp_init_copy(&m_data, const_cast< ::mp_int*>(&o.m_data))); | |
53 | } | |
54 | #ifndef BOOST_NO_CXX11_RVALUE_REFERENCES | |
55 | tommath_int(tommath_int&& o) BOOST_NOEXCEPT | |
56 | { | |
57 | m_data = o.m_data; | |
58 | o.m_data.dp = 0; | |
59 | } | |
60 | tommath_int& operator = (tommath_int&& o) | |
61 | { | |
62 | mp_exch(&m_data, &o.m_data); | |
63 | return *this; | |
64 | } | |
65 | #endif | |
66 | tommath_int& operator = (const tommath_int& o) | |
67 | { | |
68 | if(m_data.dp == 0) | |
69 | detail::check_tommath_result(mp_init(&m_data)); | |
70 | if(o.m_data.dp) | |
71 | detail::check_tommath_result(mp_copy(const_cast< ::mp_int*>(&o.m_data), &m_data)); | |
72 | return *this; | |
73 | } | |
74 | tommath_int& operator = (boost::ulong_long_type i) | |
75 | { | |
76 | if(m_data.dp == 0) | |
77 | detail::check_tommath_result(mp_init(&m_data)); | |
78 | boost::ulong_long_type mask = ((1uLL << std::numeric_limits<unsigned>::digits) - 1); | |
79 | unsigned shift = 0; | |
80 | ::mp_int t; | |
81 | detail::check_tommath_result(mp_init(&t)); | |
82 | mp_zero(&m_data); | |
83 | while(i) | |
84 | { | |
85 | detail::check_tommath_result(mp_set_int(&t, static_cast<unsigned>(i & mask))); | |
86 | if(shift) | |
87 | detail::check_tommath_result(mp_mul_2d(&t, shift, &t)); | |
88 | detail::check_tommath_result((mp_add(&m_data, &t, &m_data))); | |
89 | shift += std::numeric_limits<unsigned>::digits; | |
90 | i >>= std::numeric_limits<unsigned>::digits; | |
91 | } | |
92 | mp_clear(&t); | |
93 | return *this; | |
94 | } | |
95 | tommath_int& operator = (boost::long_long_type i) | |
96 | { | |
97 | if(m_data.dp == 0) | |
98 | detail::check_tommath_result(mp_init(&m_data)); | |
99 | bool neg = i < 0; | |
100 | *this = boost::multiprecision::detail::unsigned_abs(i); | |
101 | if(neg) | |
102 | detail::check_tommath_result(mp_neg(&m_data, &m_data)); | |
103 | return *this; | |
104 | } | |
105 | // | |
106 | // Note that although mp_set_int takes an unsigned long as an argument | |
107 | // it only sets the first 32-bits to the result, and ignores the rest. | |
108 | // So use uint32_t as the largest type to pass to this function. | |
109 | // | |
110 | tommath_int& operator = (boost::uint32_t i) | |
111 | { | |
112 | if(m_data.dp == 0) | |
113 | detail::check_tommath_result(mp_init(&m_data)); | |
114 | detail::check_tommath_result((mp_set_int(&m_data, i))); | |
115 | return *this; | |
116 | } | |
117 | tommath_int& operator = (boost::int32_t i) | |
118 | { | |
119 | if(m_data.dp == 0) | |
120 | detail::check_tommath_result(mp_init(&m_data)); | |
121 | bool neg = i < 0; | |
122 | *this = boost::multiprecision::detail::unsigned_abs(i); | |
123 | if(neg) | |
124 | detail::check_tommath_result(mp_neg(&m_data, &m_data)); | |
125 | return *this; | |
126 | } | |
127 | tommath_int& operator = (long double a) | |
128 | { | |
129 | using std::frexp; | |
130 | using std::ldexp; | |
131 | using std::floor; | |
132 | ||
133 | if(m_data.dp == 0) | |
134 | detail::check_tommath_result(mp_init(&m_data)); | |
135 | ||
136 | if (a == 0) { | |
137 | detail::check_tommath_result(mp_set_int(&m_data, 0)); | |
138 | return *this; | |
139 | } | |
140 | ||
141 | if (a == 1) { | |
142 | detail::check_tommath_result(mp_set_int(&m_data, 1)); | |
143 | return *this; | |
144 | } | |
145 | ||
146 | BOOST_ASSERT(!(boost::math::isinf)(a)); | |
147 | BOOST_ASSERT(!(boost::math::isnan)(a)); | |
148 | ||
149 | int e; | |
150 | long double f, term; | |
151 | detail::check_tommath_result(mp_set_int(&m_data, 0u)); | |
152 | ::mp_int t; | |
153 | detail::check_tommath_result(mp_init(&t)); | |
154 | ||
155 | f = frexp(a, &e); | |
156 | ||
157 | static const int shift = std::numeric_limits<int>::digits - 1; | |
158 | ||
159 | while(f) | |
160 | { | |
161 | // extract int sized bits from f: | |
162 | f = ldexp(f, shift); | |
163 | term = floor(f); | |
164 | e -= shift; | |
165 | detail::check_tommath_result(mp_mul_2d(&m_data, shift, &m_data)); | |
166 | if(term > 0) | |
167 | { | |
168 | detail::check_tommath_result(mp_set_int(&t, static_cast<int>(term))); | |
169 | detail::check_tommath_result(mp_add(&m_data, &t, &m_data)); | |
170 | } | |
171 | else | |
172 | { | |
173 | detail::check_tommath_result(mp_set_int(&t, static_cast<int>(-term))); | |
174 | detail::check_tommath_result(mp_sub(&m_data, &t, &m_data)); | |
175 | } | |
176 | f -= term; | |
177 | } | |
178 | if(e > 0) | |
179 | detail::check_tommath_result(mp_mul_2d(&m_data, e, &m_data)); | |
180 | else if(e < 0) | |
181 | { | |
182 | tommath_int t2; | |
183 | detail::check_tommath_result(mp_div_2d(&m_data, -e, &m_data, &t2.data())); | |
184 | } | |
185 | mp_clear(&t); | |
186 | return *this; | |
187 | } | |
188 | tommath_int& operator = (const char* s) | |
189 | { | |
190 | // | |
191 | // We don't use libtommath's own routine because it doesn't error check the input :-( | |
192 | // | |
193 | if(m_data.dp == 0) | |
194 | detail::check_tommath_result(mp_init(&m_data)); | |
195 | std::size_t n = s ? std::strlen(s) : 0; | |
196 | *this = static_cast<boost::uint32_t>(0u); | |
197 | unsigned radix = 10; | |
198 | bool isneg = false; | |
199 | if(n && (*s == '-')) | |
200 | { | |
201 | --n; | |
202 | ++s; | |
203 | isneg = true; | |
204 | } | |
205 | if(n && (*s == '0')) | |
206 | { | |
207 | if((n > 1) && ((s[1] == 'x') || (s[1] == 'X'))) | |
208 | { | |
209 | radix = 16; | |
210 | s +=2; | |
211 | n -= 2; | |
212 | } | |
213 | else | |
214 | { | |
215 | radix = 8; | |
216 | n -= 1; | |
217 | } | |
218 | } | |
219 | if(n) | |
220 | { | |
221 | if(radix == 8 || radix == 16) | |
222 | { | |
223 | unsigned shift = radix == 8 ? 3 : 4; | |
224 | unsigned block_count = DIGIT_BIT / shift; | |
225 | unsigned block_shift = shift * block_count; | |
226 | boost::ulong_long_type val, block; | |
227 | while(*s) | |
228 | { | |
229 | block = 0; | |
230 | for(unsigned i = 0; (i < block_count); ++i) | |
231 | { | |
232 | if(*s >= '0' && *s <= '9') | |
233 | val = *s - '0'; | |
234 | else if(*s >= 'a' && *s <= 'f') | |
235 | val = 10 + *s - 'a'; | |
236 | else if(*s >= 'A' && *s <= 'F') | |
237 | val = 10 + *s - 'A'; | |
238 | else | |
239 | val = 400; | |
240 | if(val > radix) | |
241 | { | |
242 | BOOST_THROW_EXCEPTION(std::runtime_error("Unexpected content found while parsing character string.")); | |
243 | } | |
244 | block <<= shift; | |
245 | block |= val; | |
246 | if(!*++s) | |
247 | { | |
248 | // final shift is different: | |
249 | block_shift = (i + 1) * shift; | |
250 | break; | |
251 | } | |
252 | } | |
253 | detail::check_tommath_result(mp_mul_2d(&data(), block_shift, &data())); | |
254 | if(data().used) | |
255 | data().dp[0] |= block; | |
256 | else | |
257 | *this = block; | |
258 | } | |
259 | } | |
260 | else | |
261 | { | |
262 | // Base 10, we extract blocks of size 10^9 at a time, that way | |
263 | // the number of multiplications is kept to a minimum: | |
264 | boost::uint32_t block_mult = 1000000000; | |
265 | while(*s) | |
266 | { | |
267 | boost::uint32_t block = 0; | |
268 | for(unsigned i = 0; i < 9; ++i) | |
269 | { | |
270 | boost::uint32_t val; | |
271 | if(*s >= '0' && *s <= '9') | |
272 | val = *s - '0'; | |
273 | else | |
274 | BOOST_THROW_EXCEPTION(std::runtime_error("Unexpected character encountered in input.")); | |
275 | block *= 10; | |
276 | block += val; | |
277 | if(!*++s) | |
278 | { | |
279 | static const boost::uint32_t block_multiplier[9] = { 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000 }; | |
280 | block_mult = block_multiplier[i]; | |
281 | break; | |
282 | } | |
283 | } | |
284 | tommath_int t; | |
285 | t = block_mult; | |
286 | eval_multiply(*this, t); | |
287 | t = block; | |
288 | eval_add(*this, t); | |
289 | } | |
290 | } | |
291 | } | |
292 | if(isneg) | |
293 | this->negate(); | |
294 | return *this; | |
295 | } | |
296 | std::string str(std::streamsize /*digits*/, std::ios_base::fmtflags f)const | |
297 | { | |
298 | BOOST_ASSERT(m_data.dp); | |
299 | int base = 10; | |
300 | if((f & std::ios_base::oct) == std::ios_base::oct) | |
301 | base = 8; | |
302 | else if((f & std::ios_base::hex) == std::ios_base::hex) | |
303 | base = 16; | |
304 | // | |
305 | // sanity check, bases 8 and 16 are only available for positive numbers: | |
306 | // | |
307 | if((base != 10) && m_data.sign) | |
308 | BOOST_THROW_EXCEPTION(std::runtime_error("Formatted output in bases 8 or 16 is only available for positive numbers")); | |
309 | int s; | |
310 | detail::check_tommath_result(mp_radix_size(const_cast< ::mp_int*>(&m_data), base, &s)); | |
311 | boost::scoped_array<char> a(new char[s+1]); | |
312 | detail::check_tommath_result(mp_toradix_n(const_cast< ::mp_int*>(&m_data), a.get(), base, s+1)); | |
313 | std::string result = a.get(); | |
314 | if((base != 10) && (f & std::ios_base::showbase)) | |
315 | { | |
316 | int pos = result[0] == '-' ? 1 : 0; | |
317 | const char* pp = base == 8 ? "0" : "0x"; | |
318 | result.insert(static_cast<std::string::size_type>(pos), pp); | |
319 | } | |
320 | if((f & std::ios_base::showpos) && (result[0] != '-')) | |
321 | result.insert(static_cast<std::string::size_type>(0), 1, '+'); | |
322 | return result; | |
323 | } | |
324 | ~tommath_int() | |
325 | { | |
326 | if(m_data.dp) | |
327 | mp_clear(&m_data); | |
328 | } | |
329 | void negate() | |
330 | { | |
331 | BOOST_ASSERT(m_data.dp); | |
332 | mp_neg(&m_data, &m_data); | |
333 | } | |
334 | int compare(const tommath_int& o)const | |
335 | { | |
336 | BOOST_ASSERT(m_data.dp && o.m_data.dp); | |
337 | return mp_cmp(const_cast< ::mp_int*>(&m_data), const_cast< ::mp_int*>(&o.m_data)); | |
338 | } | |
339 | template <class V> | |
340 | int compare(V v)const | |
341 | { | |
342 | tommath_int d; | |
343 | tommath_int t(*this); | |
344 | detail::check_tommath_result(mp_shrink(&t.data())); | |
345 | d = v; | |
346 | return t.compare(d); | |
347 | } | |
348 | ::mp_int& data() | |
349 | { | |
350 | BOOST_ASSERT(m_data.dp); | |
351 | return m_data; | |
352 | } | |
353 | const ::mp_int& data()const | |
354 | { | |
355 | BOOST_ASSERT(m_data.dp); | |
356 | return m_data; | |
357 | } | |
358 | void swap(tommath_int& o)BOOST_NOEXCEPT | |
359 | { | |
360 | mp_exch(&m_data, &o.data()); | |
361 | } | |
362 | protected: | |
363 | ::mp_int m_data; | |
364 | }; | |
365 | ||
366 | #define BOOST_MP_TOMMATH_BIT_OP_CHECK(x)\ | |
367 | if(SIGN(&x.data()))\ | |
368 | BOOST_THROW_EXCEPTION(std::runtime_error("Bitwise operations on libtommath negative valued integers are disabled as they produce unpredictable results")) | |
369 | ||
370 | int eval_get_sign(const tommath_int& val); | |
371 | ||
372 | inline void eval_add(tommath_int& t, const tommath_int& o) | |
373 | { | |
374 | detail::check_tommath_result(mp_add(&t.data(), const_cast< ::mp_int*>(&o.data()), &t.data())); | |
375 | } | |
376 | inline void eval_subtract(tommath_int& t, const tommath_int& o) | |
377 | { | |
378 | detail::check_tommath_result(mp_sub(&t.data(), const_cast< ::mp_int*>(&o.data()), &t.data())); | |
379 | } | |
380 | inline void eval_multiply(tommath_int& t, const tommath_int& o) | |
381 | { | |
382 | detail::check_tommath_result(mp_mul(&t.data(), const_cast< ::mp_int*>(&o.data()), &t.data())); | |
383 | } | |
384 | inline void eval_divide(tommath_int& t, const tommath_int& o) | |
385 | { | |
386 | using default_ops::eval_is_zero; | |
387 | tommath_int temp; | |
388 | if(eval_is_zero(o)) | |
389 | BOOST_THROW_EXCEPTION(std::overflow_error("Integer division by zero")); | |
390 | detail::check_tommath_result(mp_div(&t.data(), const_cast< ::mp_int*>(&o.data()), &t.data(), &temp.data())); | |
391 | } | |
392 | inline void eval_modulus(tommath_int& t, const tommath_int& o) | |
393 | { | |
394 | using default_ops::eval_is_zero; | |
395 | if(eval_is_zero(o)) | |
396 | BOOST_THROW_EXCEPTION(std::overflow_error("Integer division by zero")); | |
397 | bool neg = eval_get_sign(t) < 0; | |
398 | bool neg2 = eval_get_sign(o) < 0; | |
399 | detail::check_tommath_result(mp_mod(&t.data(), const_cast< ::mp_int*>(&o.data()), &t.data())); | |
400 | if((neg != neg2) && (eval_get_sign(t) != 0)) | |
401 | { | |
402 | t.negate(); | |
403 | detail::check_tommath_result(mp_add(&t.data(), const_cast< ::mp_int*>(&o.data()), &t.data())); | |
404 | t.negate(); | |
405 | } | |
406 | else if(neg && (t.compare(o) == 0)) | |
407 | { | |
408 | mp_zero(&t.data()); | |
409 | } | |
410 | } | |
411 | template <class UI> | |
412 | inline void eval_left_shift(tommath_int& t, UI i) | |
413 | { | |
414 | detail::check_tommath_result(mp_mul_2d(&t.data(), static_cast<unsigned>(i), &t.data())); | |
415 | } | |
416 | template <class UI> | |
417 | inline void eval_right_shift(tommath_int& t, UI i) | |
418 | { | |
419 | using default_ops::eval_increment; | |
420 | using default_ops::eval_decrement; | |
421 | bool neg = eval_get_sign(t) < 0; | |
422 | tommath_int d; | |
423 | if(neg) | |
424 | eval_increment(t); | |
425 | detail::check_tommath_result(mp_div_2d(&t.data(), static_cast<unsigned>(i), &t.data(), &d.data())); | |
426 | if(neg) | |
427 | eval_decrement(t); | |
428 | } | |
429 | template <class UI> | |
430 | inline void eval_left_shift(tommath_int& t, const tommath_int& v, UI i) | |
431 | { | |
432 | detail::check_tommath_result(mp_mul_2d(const_cast< ::mp_int*>(&v.data()), static_cast<unsigned>(i), &t.data())); | |
433 | } | |
434 | /* | |
435 | template <class UI> | |
436 | inline void eval_right_shift(tommath_int& t, const tommath_int& v, UI i) | |
437 | { | |
438 | tommath_int d; | |
439 | detail::check_tommath_result(mp_div_2d(const_cast< ::mp_int*>(&v.data()), static_cast<unsigned long>(i), &t.data(), &d.data())); | |
440 | } | |
441 | */ | |
442 | inline void eval_bitwise_and(tommath_int& result, const tommath_int& v) | |
443 | { | |
444 | BOOST_MP_TOMMATH_BIT_OP_CHECK(result); | |
445 | BOOST_MP_TOMMATH_BIT_OP_CHECK(v); | |
446 | detail::check_tommath_result(mp_and(&result.data(), const_cast< ::mp_int*>(&v.data()), &result.data())); | |
447 | } | |
448 | ||
449 | inline void eval_bitwise_or(tommath_int& result, const tommath_int& v) | |
450 | { | |
451 | BOOST_MP_TOMMATH_BIT_OP_CHECK(result); | |
452 | BOOST_MP_TOMMATH_BIT_OP_CHECK(v); | |
453 | detail::check_tommath_result(mp_or(&result.data(), const_cast< ::mp_int*>(&v.data()), &result.data())); | |
454 | } | |
455 | ||
456 | inline void eval_bitwise_xor(tommath_int& result, const tommath_int& v) | |
457 | { | |
458 | BOOST_MP_TOMMATH_BIT_OP_CHECK(result); | |
459 | BOOST_MP_TOMMATH_BIT_OP_CHECK(v); | |
460 | detail::check_tommath_result(mp_xor(&result.data(), const_cast< ::mp_int*>(&v.data()), &result.data())); | |
461 | } | |
462 | ||
463 | inline void eval_add(tommath_int& t, const tommath_int& p, const tommath_int& o) | |
464 | { | |
465 | detail::check_tommath_result(mp_add(const_cast< ::mp_int*>(&p.data()), const_cast< ::mp_int*>(&o.data()), &t.data())); | |
466 | } | |
467 | inline void eval_subtract(tommath_int& t, const tommath_int& p, const tommath_int& o) | |
468 | { | |
469 | detail::check_tommath_result(mp_sub(const_cast< ::mp_int*>(&p.data()), const_cast< ::mp_int*>(&o.data()), &t.data())); | |
470 | } | |
471 | inline void eval_multiply(tommath_int& t, const tommath_int& p, const tommath_int& o) | |
472 | { | |
473 | detail::check_tommath_result(mp_mul(const_cast< ::mp_int*>(&p.data()), const_cast< ::mp_int*>(&o.data()), &t.data())); | |
474 | } | |
475 | inline void eval_divide(tommath_int& t, const tommath_int& p, const tommath_int& o) | |
476 | { | |
477 | using default_ops::eval_is_zero; | |
478 | tommath_int d; | |
479 | if(eval_is_zero(o)) | |
480 | BOOST_THROW_EXCEPTION(std::overflow_error("Integer division by zero")); | |
481 | detail::check_tommath_result(mp_div(const_cast< ::mp_int*>(&p.data()), const_cast< ::mp_int*>(&o.data()), &t.data(), &d.data())); | |
482 | } | |
483 | inline void eval_modulus(tommath_int& t, const tommath_int& p, const tommath_int& o) | |
484 | { | |
485 | using default_ops::eval_is_zero; | |
486 | if(eval_is_zero(o)) | |
487 | BOOST_THROW_EXCEPTION(std::overflow_error("Integer division by zero")); | |
488 | bool neg = eval_get_sign(p) < 0; | |
489 | bool neg2 = eval_get_sign(o) < 0; | |
490 | detail::check_tommath_result(mp_mod(const_cast< ::mp_int*>(&p.data()), const_cast< ::mp_int*>(&o.data()), &t.data())); | |
491 | if((neg != neg2) && (eval_get_sign(t) != 0)) | |
492 | { | |
493 | t.negate(); | |
494 | detail::check_tommath_result(mp_add(&t.data(), const_cast< ::mp_int*>(&o.data()), &t.data())); | |
495 | t.negate(); | |
496 | } | |
497 | else if(neg && (t.compare(o) == 0)) | |
498 | { | |
499 | mp_zero(&t.data()); | |
500 | } | |
501 | } | |
502 | ||
503 | inline void eval_bitwise_and(tommath_int& result, const tommath_int& u, const tommath_int& v) | |
504 | { | |
505 | BOOST_MP_TOMMATH_BIT_OP_CHECK(u); | |
506 | BOOST_MP_TOMMATH_BIT_OP_CHECK(v); | |
507 | detail::check_tommath_result(mp_and(const_cast< ::mp_int*>(&u.data()), const_cast< ::mp_int*>(&v.data()), &result.data())); | |
508 | } | |
509 | ||
510 | inline void eval_bitwise_or(tommath_int& result, const tommath_int& u, const tommath_int& v) | |
511 | { | |
512 | BOOST_MP_TOMMATH_BIT_OP_CHECK(u); | |
513 | BOOST_MP_TOMMATH_BIT_OP_CHECK(v); | |
514 | detail::check_tommath_result(mp_or(const_cast< ::mp_int*>(&u.data()), const_cast< ::mp_int*>(&v.data()), &result.data())); | |
515 | } | |
516 | ||
517 | inline void eval_bitwise_xor(tommath_int& result, const tommath_int& u, const tommath_int& v) | |
518 | { | |
519 | BOOST_MP_TOMMATH_BIT_OP_CHECK(u); | |
520 | BOOST_MP_TOMMATH_BIT_OP_CHECK(v); | |
521 | detail::check_tommath_result(mp_xor(const_cast< ::mp_int*>(&u.data()), const_cast< ::mp_int*>(&v.data()), &result.data())); | |
522 | } | |
523 | /* | |
524 | inline void eval_complement(tommath_int& result, const tommath_int& u) | |
525 | { | |
526 | // | |
527 | // Although this code works, it doesn't really do what the user might expect.... | |
528 | // and it's hard to see how it ever could. Disabled for now: | |
529 | // | |
530 | result = u; | |
531 | for(int i = 0; i < result.data().used; ++i) | |
532 | { | |
533 | result.data().dp[i] = MP_MASK & ~(result.data().dp[i]); | |
534 | } | |
535 | // | |
536 | // We now need to pad out the left of the value with 1's to round up to a whole number of | |
537 | // CHAR_BIT * sizeof(mp_digit) units. Otherwise we'll end up with a very strange number of | |
538 | // bits set! | |
539 | // | |
540 | unsigned shift = result.data().used * DIGIT_BIT; // How many bits we're actually using | |
541 | // How many bits we actually need, reduced by one to account for a mythical sign bit: | |
542 | int padding = result.data().used * std::numeric_limits<mp_digit>::digits - shift - 1; | |
543 | while(padding >= std::numeric_limits<mp_digit>::digits) | |
544 | padding -= std::numeric_limits<mp_digit>::digits; | |
545 | ||
546 | // Create a mask providing the extra bits we need and add to result: | |
547 | tommath_int mask; | |
548 | mask = static_cast<boost::long_long_type>((1u << padding) - 1); | |
549 | eval_left_shift(mask, shift); | |
550 | add(result, mask); | |
551 | } | |
552 | */ | |
553 | inline bool eval_is_zero(const tommath_int& val) | |
554 | { | |
555 | return mp_iszero(&val.data()); | |
556 | } | |
557 | inline int eval_get_sign(const tommath_int& val) | |
558 | { | |
559 | return mp_iszero(&val.data()) ? 0 : SIGN(&val.data()) ? -1 : 1; | |
560 | } | |
561 | template <class A> | |
562 | inline void eval_convert_to(A* result, const tommath_int& val) | |
563 | { | |
564 | *result = boost::lexical_cast<A>(val.str(0, std::ios_base::fmtflags(0))); | |
565 | } | |
566 | inline void eval_convert_to(char* result, const tommath_int& val) | |
567 | { | |
568 | *result = static_cast<char>(boost::lexical_cast<int>(val.str(0, std::ios_base::fmtflags(0)))); | |
569 | } | |
570 | inline void eval_convert_to(unsigned char* result, const tommath_int& val) | |
571 | { | |
572 | *result = static_cast<unsigned char>(boost::lexical_cast<unsigned>(val.str(0, std::ios_base::fmtflags(0)))); | |
573 | } | |
574 | inline void eval_convert_to(signed char* result, const tommath_int& val) | |
575 | { | |
576 | *result = static_cast<signed char>(boost::lexical_cast<int>(val.str(0, std::ios_base::fmtflags(0)))); | |
577 | } | |
578 | inline void eval_abs(tommath_int& result, const tommath_int& val) | |
579 | { | |
580 | detail::check_tommath_result(mp_abs(const_cast< ::mp_int*>(&val.data()), &result.data())); | |
581 | } | |
582 | inline void eval_gcd(tommath_int& result, const tommath_int& a, const tommath_int& b) | |
583 | { | |
584 | detail::check_tommath_result(mp_gcd(const_cast< ::mp_int*>(&a.data()), const_cast< ::mp_int*>(&b.data()), const_cast< ::mp_int*>(&result.data()))); | |
585 | } | |
586 | inline void eval_lcm(tommath_int& result, const tommath_int& a, const tommath_int& b) | |
587 | { | |
588 | detail::check_tommath_result(mp_lcm(const_cast< ::mp_int*>(&a.data()), const_cast< ::mp_int*>(&b.data()), const_cast< ::mp_int*>(&result.data()))); | |
589 | } | |
590 | inline void eval_powm(tommath_int& result, const tommath_int& base, const tommath_int& p, const tommath_int& m) | |
591 | { | |
592 | if(eval_get_sign(p) < 0) | |
593 | { | |
594 | BOOST_THROW_EXCEPTION(std::runtime_error("powm requires a positive exponent.")); | |
595 | } | |
596 | detail::check_tommath_result(mp_exptmod(const_cast< ::mp_int*>(&base.data()), const_cast< ::mp_int*>(&p.data()), const_cast< ::mp_int*>(&m.data()), &result.data())); | |
597 | } | |
598 | ||
599 | ||
600 | inline void eval_qr(const tommath_int& x, const tommath_int& y, | |
601 | tommath_int& q, tommath_int& r) | |
602 | { | |
603 | detail::check_tommath_result(mp_div(const_cast< ::mp_int*>(&x.data()), const_cast< ::mp_int*>(&y.data()), &q.data(), &r.data())); | |
604 | } | |
605 | ||
606 | inline unsigned eval_lsb(const tommath_int& val) | |
607 | { | |
608 | int c = eval_get_sign(val); | |
609 | if(c == 0) | |
610 | { | |
611 | BOOST_THROW_EXCEPTION(std::range_error("No bits were set in the operand.")); | |
612 | } | |
613 | if(c < 0) | |
614 | { | |
615 | BOOST_THROW_EXCEPTION(std::range_error("Testing individual bits in negative values is not supported - results are undefined.")); | |
616 | } | |
617 | return mp_cnt_lsb(const_cast< ::mp_int*>(&val.data())); | |
618 | } | |
619 | ||
620 | inline unsigned eval_msb(const tommath_int& val) | |
621 | { | |
622 | int c = eval_get_sign(val); | |
623 | if(c == 0) | |
624 | { | |
625 | BOOST_THROW_EXCEPTION(std::range_error("No bits were set in the operand.")); | |
626 | } | |
627 | if(c < 0) | |
628 | { | |
629 | BOOST_THROW_EXCEPTION(std::range_error("Testing individual bits in negative values is not supported - results are undefined.")); | |
630 | } | |
631 | return mp_count_bits(const_cast< ::mp_int*>(&val.data())) - 1; | |
632 | } | |
633 | ||
634 | template <class Integer> | |
635 | inline typename enable_if<is_unsigned<Integer>, Integer>::type eval_integer_modulus(const tommath_int& x, Integer val) | |
636 | { | |
637 | static const mp_digit m = (static_cast<mp_digit>(1) << DIGIT_BIT) - 1; | |
638 | if(val <= m) | |
639 | { | |
640 | mp_digit d; | |
641 | detail::check_tommath_result(mp_mod_d(const_cast< ::mp_int*>(&x.data()), static_cast<mp_digit>(val), &d)); | |
642 | return d; | |
643 | } | |
644 | else | |
645 | { | |
646 | return default_ops::eval_integer_modulus(x, val); | |
647 | } | |
648 | } | |
649 | template <class Integer> | |
650 | inline typename enable_if<is_signed<Integer>, Integer>::type eval_integer_modulus(const tommath_int& x, Integer val) | |
651 | { | |
652 | return eval_integer_modulus(x, boost::multiprecision::detail::unsigned_abs(val)); | |
653 | } | |
654 | ||
655 | inline std::size_t hash_value(const tommath_int& val) | |
656 | { | |
657 | std::size_t result = 0; | |
658 | std::size_t len = val.data().used; | |
659 | for(std::size_t i = 0; i < len; ++i) | |
660 | boost::hash_combine(result, val.data().dp[i]); | |
661 | boost::hash_combine(result, val.data().sign); | |
662 | return result; | |
663 | } | |
664 | ||
665 | } // namespace backends | |
666 | ||
667 | using boost::multiprecision::backends::tommath_int; | |
668 | ||
669 | template<> | |
670 | struct number_category<tommath_int> : public mpl::int_<number_kind_integer>{}; | |
671 | ||
672 | typedef number<tommath_int > tom_int; | |
673 | typedef rational_adaptor<tommath_int> tommath_rational; | |
674 | typedef number<tommath_rational> tom_rational; | |
675 | ||
676 | }} // namespaces | |
677 | ||
678 | namespace std{ | |
679 | ||
680 | template<boost::multiprecision::expression_template_option ExpressionTemplates> | |
681 | class numeric_limits<boost::multiprecision::number<boost::multiprecision::tommath_int, ExpressionTemplates> > | |
682 | { | |
683 | typedef boost::multiprecision::number<boost::multiprecision::tommath_int, ExpressionTemplates> number_type; | |
684 | public: | |
685 | BOOST_STATIC_CONSTEXPR bool is_specialized = true; | |
686 | // | |
687 | // Largest and smallest numbers are bounded only by available memory, set | |
688 | // to zero: | |
689 | // | |
690 | static number_type (min)() | |
691 | { | |
692 | return number_type(); | |
693 | } | |
694 | static number_type (max)() | |
695 | { | |
696 | return number_type(); | |
697 | } | |
698 | static number_type lowest() { return (min)(); } | |
699 | BOOST_STATIC_CONSTEXPR int digits = INT_MAX; | |
700 | BOOST_STATIC_CONSTEXPR int digits10 = (INT_MAX / 1000) * 301L; | |
701 | BOOST_STATIC_CONSTEXPR int max_digits10 = digits10 + 3; | |
702 | BOOST_STATIC_CONSTEXPR bool is_signed = true; | |
703 | BOOST_STATIC_CONSTEXPR bool is_integer = true; | |
704 | BOOST_STATIC_CONSTEXPR bool is_exact = true; | |
705 | BOOST_STATIC_CONSTEXPR int radix = 2; | |
706 | static number_type epsilon() { return number_type(); } | |
707 | static number_type round_error() { return number_type(); } | |
708 | BOOST_STATIC_CONSTEXPR int min_exponent = 0; | |
709 | BOOST_STATIC_CONSTEXPR int min_exponent10 = 0; | |
710 | BOOST_STATIC_CONSTEXPR int max_exponent = 0; | |
711 | BOOST_STATIC_CONSTEXPR int max_exponent10 = 0; | |
712 | BOOST_STATIC_CONSTEXPR bool has_infinity = false; | |
713 | BOOST_STATIC_CONSTEXPR bool has_quiet_NaN = false; | |
714 | BOOST_STATIC_CONSTEXPR bool has_signaling_NaN = false; | |
715 | BOOST_STATIC_CONSTEXPR float_denorm_style has_denorm = denorm_absent; | |
716 | BOOST_STATIC_CONSTEXPR bool has_denorm_loss = false; | |
717 | static number_type infinity() { return number_type(); } | |
718 | static number_type quiet_NaN() { return number_type(); } | |
719 | static number_type signaling_NaN() { return number_type(); } | |
720 | static number_type denorm_min() { return number_type(); } | |
721 | BOOST_STATIC_CONSTEXPR bool is_iec559 = false; | |
722 | BOOST_STATIC_CONSTEXPR bool is_bounded = false; | |
723 | BOOST_STATIC_CONSTEXPR bool is_modulo = false; | |
724 | BOOST_STATIC_CONSTEXPR bool traps = false; | |
725 | BOOST_STATIC_CONSTEXPR bool tinyness_before = false; | |
726 | BOOST_STATIC_CONSTEXPR float_round_style round_style = round_toward_zero; | |
727 | }; | |
728 | ||
729 | #ifndef BOOST_NO_INCLASS_MEMBER_INITIALIZATION | |
730 | ||
731 | template <boost::multiprecision::expression_template_option ExpressionTemplates> | |
732 | BOOST_CONSTEXPR_OR_CONST int numeric_limits<boost::multiprecision::number<boost::multiprecision::tommath_int, ExpressionTemplates> >::digits; | |
733 | template <boost::multiprecision::expression_template_option ExpressionTemplates> | |
734 | BOOST_CONSTEXPR_OR_CONST int numeric_limits<boost::multiprecision::number<boost::multiprecision::tommath_int, ExpressionTemplates> >::digits10; | |
735 | template <boost::multiprecision::expression_template_option ExpressionTemplates> | |
736 | BOOST_CONSTEXPR_OR_CONST int numeric_limits<boost::multiprecision::number<boost::multiprecision::tommath_int, ExpressionTemplates> >::max_digits10; | |
737 | template <boost::multiprecision::expression_template_option ExpressionTemplates> | |
738 | BOOST_CONSTEXPR_OR_CONST bool numeric_limits<boost::multiprecision::number<boost::multiprecision::tommath_int, ExpressionTemplates> >::is_signed; | |
739 | template <boost::multiprecision::expression_template_option ExpressionTemplates> | |
740 | BOOST_CONSTEXPR_OR_CONST bool numeric_limits<boost::multiprecision::number<boost::multiprecision::tommath_int, ExpressionTemplates> >::is_integer; | |
741 | template <boost::multiprecision::expression_template_option ExpressionTemplates> | |
742 | BOOST_CONSTEXPR_OR_CONST bool numeric_limits<boost::multiprecision::number<boost::multiprecision::tommath_int, ExpressionTemplates> >::is_exact; | |
743 | template <boost::multiprecision::expression_template_option ExpressionTemplates> | |
744 | BOOST_CONSTEXPR_OR_CONST int numeric_limits<boost::multiprecision::number<boost::multiprecision::tommath_int, ExpressionTemplates> >::radix; | |
745 | template <boost::multiprecision::expression_template_option ExpressionTemplates> | |
746 | BOOST_CONSTEXPR_OR_CONST int numeric_limits<boost::multiprecision::number<boost::multiprecision::tommath_int, ExpressionTemplates> >::min_exponent; | |
747 | template <boost::multiprecision::expression_template_option ExpressionTemplates> | |
748 | BOOST_CONSTEXPR_OR_CONST int numeric_limits<boost::multiprecision::number<boost::multiprecision::tommath_int, ExpressionTemplates> >::min_exponent10; | |
749 | template <boost::multiprecision::expression_template_option ExpressionTemplates> | |
750 | BOOST_CONSTEXPR_OR_CONST int numeric_limits<boost::multiprecision::number<boost::multiprecision::tommath_int, ExpressionTemplates> >::max_exponent; | |
751 | template <boost::multiprecision::expression_template_option ExpressionTemplates> | |
752 | BOOST_CONSTEXPR_OR_CONST int numeric_limits<boost::multiprecision::number<boost::multiprecision::tommath_int, ExpressionTemplates> >::max_exponent10; | |
753 | template <boost::multiprecision::expression_template_option ExpressionTemplates> | |
754 | BOOST_CONSTEXPR_OR_CONST bool numeric_limits<boost::multiprecision::number<boost::multiprecision::tommath_int, ExpressionTemplates> >::has_infinity; | |
755 | template <boost::multiprecision::expression_template_option ExpressionTemplates> | |
756 | BOOST_CONSTEXPR_OR_CONST bool numeric_limits<boost::multiprecision::number<boost::multiprecision::tommath_int, ExpressionTemplates> >::has_quiet_NaN; | |
757 | template <boost::multiprecision::expression_template_option ExpressionTemplates> | |
758 | BOOST_CONSTEXPR_OR_CONST bool numeric_limits<boost::multiprecision::number<boost::multiprecision::tommath_int, ExpressionTemplates> >::has_signaling_NaN; | |
759 | template <boost::multiprecision::expression_template_option ExpressionTemplates> | |
760 | BOOST_CONSTEXPR_OR_CONST float_denorm_style numeric_limits<boost::multiprecision::number<boost::multiprecision::tommath_int, ExpressionTemplates> >::has_denorm; | |
761 | template <boost::multiprecision::expression_template_option ExpressionTemplates> | |
762 | BOOST_CONSTEXPR_OR_CONST bool numeric_limits<boost::multiprecision::number<boost::multiprecision::tommath_int, ExpressionTemplates> >::has_denorm_loss; | |
763 | template <boost::multiprecision::expression_template_option ExpressionTemplates> | |
764 | BOOST_CONSTEXPR_OR_CONST bool numeric_limits<boost::multiprecision::number<boost::multiprecision::tommath_int, ExpressionTemplates> >::is_iec559; | |
765 | template <boost::multiprecision::expression_template_option ExpressionTemplates> | |
766 | BOOST_CONSTEXPR_OR_CONST bool numeric_limits<boost::multiprecision::number<boost::multiprecision::tommath_int, ExpressionTemplates> >::is_bounded; | |
767 | template <boost::multiprecision::expression_template_option ExpressionTemplates> | |
768 | BOOST_CONSTEXPR_OR_CONST bool numeric_limits<boost::multiprecision::number<boost::multiprecision::tommath_int, ExpressionTemplates> >::is_modulo; | |
769 | template <boost::multiprecision::expression_template_option ExpressionTemplates> | |
770 | BOOST_CONSTEXPR_OR_CONST bool numeric_limits<boost::multiprecision::number<boost::multiprecision::tommath_int, ExpressionTemplates> >::traps; | |
771 | template <boost::multiprecision::expression_template_option ExpressionTemplates> | |
772 | BOOST_CONSTEXPR_OR_CONST bool numeric_limits<boost::multiprecision::number<boost::multiprecision::tommath_int, ExpressionTemplates> >::tinyness_before; | |
773 | template <boost::multiprecision::expression_template_option ExpressionTemplates> | |
774 | BOOST_CONSTEXPR_OR_CONST float_round_style numeric_limits<boost::multiprecision::number<boost::multiprecision::tommath_int, ExpressionTemplates> >::round_style; | |
775 | ||
776 | #endif | |
777 | } | |
778 | ||
779 | #endif |