Subject: [Boost-commit] svn:boost r49491 - in sandbox/mp_math: boost/mp_math boost/mp_math/mp_int boost/mp_math/mp_int/detail libs/mp_math/test
From: baraclese_at_[hidden]
Date: 2008-10-30 12:20:21
Author: baraclese
Date: 2008-10-30 12:20:19 EDT (Thu, 30 Oct 2008)
New Revision: 49491
URL: http://svn.boost.org/trac/boost/changeset/49491
Log:
* rename mp_int<>::used_ to mp_int<>::size_
* replace char*, wchar_t* ctors with a templatized version
* remove fast_montgomery_reduce
* add include of <boost/static_assert.hpp> to traits.hpp
* replace size_type typename with std::size_t in mp_int_traits<>
* add fused multiply add function to primitive_ops<>
* use this new function in montgomery_reduce()
* move serialization functionality into <boost/mp_math/mp_int_serialization.hpp>
* throw bad_alloc in mp_int<>::grow_capacity()
* misc style fixes
Added:
sandbox/mp_math/boost/mp_math/mp_int_serialization.hpp (contents, props changed)
Text files modified:
sandbox/mp_math/boost/mp_math/mp_int/add.hpp | 32 +++---
sandbox/mp_math/boost/mp_math/mp_int/ctors.hpp | 63 ++++---------
sandbox/mp_math/boost/mp_math/mp_int/detail/modular_reduction.hpp | 173 ++++++++-------------------------------
sandbox/mp_math/boost/mp_math/mp_int/detail/primitive_ops.hpp | 31 +++++++
sandbox/mp_math/boost/mp_math/mp_int/div.hpp | 16 +-
sandbox/mp_math/boost/mp_math/mp_int/mod.hpp | 4
sandbox/mp_math/boost/mp_math/mp_int/modpow_ctx.hpp | 15 +-
sandbox/mp_math/boost/mp_math/mp_int/mp_int.hpp | 129 ++++++++++++-----------------
sandbox/mp_math/boost/mp_math/mp_int/mul.hpp | 92 ++++++++++-----------
sandbox/mp_math/boost/mp_math/mp_int/operators.hpp | 56 ++++++------
sandbox/mp_math/boost/mp_math/mp_int/pow.hpp | 6
sandbox/mp_math/boost/mp_math/mp_int/sqr.hpp | 24 ++--
sandbox/mp_math/boost/mp_math/mp_int/string_conversion.hpp | 32 +++---
sandbox/mp_math/boost/mp_math/mp_int/sub.hpp | 10 +-
sandbox/mp_math/boost/mp_math/mp_int/traits.hpp | 26 +++---
sandbox/mp_math/libs/mp_math/test/serialization.cpp | 1
16 files changed, 297 insertions(+), 413 deletions(-)
Modified: sandbox/mp_math/boost/mp_math/mp_int/add.hpp
==============================================================================
--- sandbox/mp_math/boost/mp_math/mp_int/add.hpp (original)
+++ sandbox/mp_math/boost/mp_math/mp_int/add.hpp 2008-10-30 12:20:19 EDT (Thu, 30 Oct 2008)
@@ -8,11 +8,11 @@
{
if (is_positive())
{
- grow_capacity(used_ + 1);
+ grow_capacity(size_ + 1);
const digit_type carry =
- ops_type::add_single_digit(digits_, digits_, used_, b);
+ ops_type::add_single_digit(digits_, digits_, size_, b);
if (carry)
- digits_[used_++] = carry;
+ push(carry);
}
else
{
@@ -24,7 +24,7 @@
}
else
{
- if (used_ == 1) // example: -1 + 5 = 4
+ if (size_ == 1) // example: -1 + 5 = 4
digits_[0] = b - digits_[0];
else // example -11 + 5 = -6
{
@@ -45,7 +45,7 @@
const mp_int* y;
// x will point to the number with the most digits
- if (used_ > rhs.used_)
+ if (size_ > rhs.size_)
{
x = this;
y = &rhs;
@@ -56,32 +56,32 @@
y = this;
}
- grow_capacity(x->used_ + 1);
+ grow_capacity(x->size_ + 1);
digit_type carry = ops_type::add_digits(digits_,
x->digits_,
- y->digits_, y->used_);
+ y->digits_, y->size_);
- size_type n = ops_type::ripple_carry(digits_ + y->used_,
- x->digits_ + y->used_,
- x->used_ - y->used_, carry);
- n += y->used_;
+ size_type n = ops_type::ripple_carry(digits_ + y->size_,
+ x->digits_ + y->size_,
+ x->size_ - y->size_, carry);
+ n += y->size_;
- if (n < x->used_) // this implies that there is no carry left
+ if (n < x->size_) // this implies that there is no carry left
{
if (x != this)
{
- std::memcpy(digits_ + n, x->digits_ + n, sizeof(digit_type) * (x->used_ - n));
- used_ = x->used_;
+ std::memcpy(digits_ + n, x->digits_ + n, sizeof(digit_type) * (x->size_ - n));
+ size_ = x->size_;
}
return;
}
- else if (carry) // at this point n equals x->used_
+ else if (carry) // at this point n equals x->size_
{
digits_[n] = carry;
++n;
}
- used_ = n;
+ size_ = n;
}
Modified: sandbox/mp_math/boost/mp_math/mp_int/ctors.hpp
==============================================================================
--- sandbox/mp_math/boost/mp_math/mp_int/ctors.hpp (original)
+++ sandbox/mp_math/boost/mp_math/mp_int/ctors.hpp 2008-10-30 12:20:19 EDT (Thu, 30 Oct 2008)
@@ -7,7 +7,7 @@
mp_int<A,T>::mp_int()
:
digits_(0),
- used_(0),
+ size_(0),
capacity_(0)
{
}
@@ -19,7 +19,7 @@
typename enable_if<is_integral<IntegralT> >::type*)
:
digits_(0),
- used_(0),
+ size_(0),
capacity_(0)
{
detail::integral_ops<IntegralT>::assign(*this, b);
@@ -29,7 +29,7 @@
template<typename RandomAccessIterator>
void mp_int<A,T>::init(RandomAccessIterator c, RandomAccessIterator last)
{
- assert(used_ == 0);
+ assert(size_ == 0);
if (c == last)
{
@@ -87,7 +87,7 @@
RandomAccessIterator last,
std::ios_base::fmtflags f)
{
- assert(used_ == 0);
+ assert(size_ == 0);
if (c == last)
{
@@ -161,61 +161,40 @@
mp_int<A,T>::mp_int(RandomAccessIterator first, RandomAccessIterator last)
:
digits_(0),
- used_(0),
+ size_(0),
capacity_(0)
{
init(first, last);
}
template<class A, class T>
-mp_int<A,T>::mp_int(const char* s)
+template<typename charT>
+mp_int<A,T>::mp_int(const charT* s)
:
digits_(0),
- used_(0),
+ size_(0),
capacity_(0)
{
- init(s, s + std::strlen(s));
+ init(s, s + std::char_traits<charT>::length(s));
}
template<class A, class T>
-mp_int<A,T>::mp_int(const char* s, std::ios_base::fmtflags f)
+template<typename charT>
+mp_int<A,T>::mp_int(const charT* s, std::ios_base::fmtflags f)
:
digits_(0),
- used_(0),
+ size_(0),
capacity_(0)
{
- init(s, s + std::strlen(s), f);
+ init(s, s + std::char_traits<charT>::length(s), f);
}
-
-#ifndef BOOST_NO_CWCHAR
-template<class A, class T>
-mp_int<A,T>::mp_int(const wchar_t* s)
-:
- digits_(0),
- used_(0),
- capacity_(0)
-{
- init(s, s + std::wcslen(s));
-}
-
- template<class A, class T>
-mp_int<A,T>::mp_int(const wchar_t* s, std::ios_base::fmtflags f)
-:
- digits_(0),
- used_(0),
- capacity_(0)
-{
- init(s, s + std::wcslen(s), f);
-}
-#endif
-
template<class A, class T>
template<typename charT, class traits, class Alloc>
mp_int<A,T>::mp_int(const std::basic_string<charT,traits,Alloc>& s)
:
digits_(0),
- used_(0),
+ size_(0),
capacity_(0)
{
init(s.begin(), s.end());
@@ -227,7 +206,7 @@
std::ios_base::fmtflags f)
:
digits_(0),
- used_(0),
+ size_(0),
capacity_(0)
{
init(s.begin(), s.end(), f);
@@ -237,10 +216,10 @@
template<class A, class T>
mp_int<A,T>::mp_int(const mp_int& copy)
{
- digits_ = this->allocate(copy.used_);
- std::memcpy(digits_, copy.digits_, copy.used_ * sizeof(digit_type));
- used_ = copy.used_;
- set_capacity(copy.used_);
+ digits_ = this->allocate(copy.size_);
+ std::memcpy(digits_, copy.digits_, copy.size_ * sizeof(digit_type));
+ size_ = copy.size_;
+ set_capacity(copy.size_);
set_sign(copy.sign());
}
@@ -249,11 +228,11 @@
mp_int<A,T>::mp_int(mp_int&& copy)
:
digits_(copy.digits_),
- used_(copy.used_),
+ size_(copy.size_),
capacity_(copy.capacity_) // this copies capacity and sign
{
copy.digits_ = 0;
- copy.used_ = 0;
+ copy.size_ = 0;
copy.capacity_ = 0;
}
#endif
Modified: sandbox/mp_math/boost/mp_math/mp_int/detail/modular_reduction.hpp
==============================================================================
--- sandbox/mp_math/boost/mp_math/mp_int/detail/modular_reduction.hpp (original)
+++ sandbox/mp_math/boost/mp_math/mp_int/detail/modular_reduction.hpp 2008-10-30 12:20:19 EDT (Thu, 30 Oct 2008)
@@ -55,78 +55,61 @@
x.sub_smaller_magnitude(m);
}
-/* computes xR**-1 == x (mod N) via Montgomery Reduction */
+/* computes xR**-1 == x (mod m) via Montgomery Reduction */
template<class A, class T>
void montgomery_reduce(mp_int<A,T>& x,
- const mp_int<A,T>& n,
+ const mp_int<A,T>& m,
typename mp_int<A,T>::digit_type rho)
{
- typedef typename mp_int<A,T>::digit_type digit_type;
- typedef typename mp_int<A,T>::word_type word_type;
- typedef typename mp_int<A,T>::size_type size_type;
+ typedef typename mp_int<A,T>::digit_type digit_type;
+ typedef typename mp_int<A,T>::word_type word_type;
+ typedef typename mp_int<A,T>::size_type size_type;
+ typedef typename mp_int<A,T>::iterator iterator;
+ typedef typename mp_int<A,T>::const_iterator const_iterator;
- const size_type digs = n.size() * 2 + 1;
+ const size_type num = m.size() * 2 + 1;
- x.grow_capacity(digs);
+ x.grow_capacity(num);
std::memset(x.digits() + x.size(), 0, (x.capacity() - x.size()) * sizeof(digit_type));
- x.set_size(digs);
+ x.set_size(num);
- // TODO rewrite both for loops in terms of const_iterator nd = n.begin();...
- for (size_type i = 0; i < n.size(); ++i)
+ for (size_type i = 0; i < m.size(); ++i)
{
// mu = x[i] * rho (mod base)
// The value of rho must be precalculated such that it equals -1/n0 mod b
- // this allows the following inner loop to reduce the input one digit at a
- // time.
- const digit_type mu = static_cast<word_type>(x[i]) * rho;
+ // this allows multiply_add_digits to reduce the input one digit at a time.
+ const digit_type mu = x[i] * rho;
// x = x + mu * m * base**i
- // alias for digits of the modulus
- const digit_type* tmpn = n.digits();
-
- // alias for the digits of x
- digit_type* tmpx = x.digits() + i;
-
- digit_type carry = 0;
+ digit_type carry =
+ mp_int<A,T>::ops_type::multiply_add_digits(x.digits() + i,
+ m.digits(),
+ mu,
+ x.digits() + i,
+ m.size());
- // Multiply and add in place
- for (size_type j = 0; j < n.size(); ++j)
- {
- // compute product and sum
- const word_type r = static_cast<word_type>(mu)
- * static_cast<word_type>(*tmpn++)
- + static_cast<word_type>(carry)
- + static_cast<word_type>(*tmpx);
-
- carry = static_cast<digit_type>(r >> mp_int<A,T>::digit_bits);
-
- *tmpx++ = r;
- }
// At this point the i'th digit of x should be zero
-
- // propagate carries upwards as required
- while (carry)
- {
- const word_type r = static_cast<word_type>(*tmpx) + carry;
- *tmpx++ = r;
- carry = r >> mp_int<A,T>::digit_bits;
- }
+
+ mp_int<A,T>::ops_type::ripple_carry(x.digits() + i + m.size(),
+ x.digits() + i + m.size(),
+ num,
+ carry);
}
- // at this point the n.used'th least significant digits of x are all zero
- // which means we can shift x to the right by n.used digits and the residue is
+ // at this point the m.size least significant digits of x are all zero which
+ // means we can shift x to the right by m.size digits and the residue is
// unchanged.
- // x = x/base**n.size()
+ // x = x/base**m.size()
x.clamp();
if (x.is_zero())
x.set_sign(1);
- x.shift_digits_right(n.size());
+ x.shift_digits_right(m.size());
- if (x.compare_magnitude(n) != -1)
- x.sub_smaller_magnitude(n);
+ if (x.compare_magnitude(m) != -1)
+ x.sub_smaller_magnitude(m);
}
// shifts with subtractions when the result is greater than n.
@@ -155,93 +138,6 @@
}
}
-/* computes xR**-1 == x (mod N) via Montgomery Reduction
- *
- * This is an optimized implementation of montgomery_reduce
- * which uses the comba method to quickly calculate the columns of the
- * reduction.
- *
- * Based on Algorithm 14.32 on pp.601 of HAC.
-*/
-template<class A, class T>
-void fast_montgomery_reduce(mp_int<A,T>& x,
- const mp_int<A,T>& n,
- typename mp_int<A,T>::digit_type rho)
-{
- typedef typename mp_int<A,T>::digit_type digit_type;
- typedef typename mp_int<A,T>::word_type word_type;
- typedef typename mp_int<A,T>::size_type size_type;
-
- word_type W[512];
-
- x.grow_capacity(n.used_ + 1);
-
- for (size_type i = 0; i < x.size(); ++i)
- W[i] = x[i];
-
- // zero the high words of W[a->used..m->used*2]
- std::memset(W + x.size(), 0, (n.size() * 2 + 1) * sizeof(word_type));
-
- // now we proceed to zero successive digits
- // from the least significant upwards
- for (size_type i = 0; i < n.size(); ++i)
- {
- // mu = ai * m' mod b
- //
- // We avoid a double precision multiplication (which isn't required) by
- // casting the value down to a mp_digit. Note this requires that W[ix-1]
- // have the carry cleared (see after the inner loop)
- const digit_type mu = static_cast<digit_type>(W[i])
- * static_cast<word_type>(rho);
-
- /* a = a + mu * m * b**i
- *
- * This is computed in place and on the fly. The multiplication
- * by b**i is handled by offseting which columns the results
- * are added to.
- *
- * Note the comba method normally doesn't handle carries in the
- * inner loop In this case we fix the carry from the previous
- * column since the Montgomery reduction requires digits of the
- * result (so far) [see above] to work. This is
- * handled by fixing up one carry after the inner loop. The
- * carry fixups are done in order so after these loops the
- * first m->used words of W[] have the carries fixed
- */
- /* inner loop */
- for (size_type j = 0; j < n.size(); ++j)
- W[i+j] += static_cast<word_type>(mu) * static_cast<word_type>(n[j]);
-
- // now fix carry for next digit, W[ix+1]
- W[i + 1] += W[i] >> static_cast<word_type>(mp_int<A,T>::valid_bits);
- }
-
- // now we have to propagate the carries and shift the words downward [all
- // those least significant digits we zeroed].
-
- // now fix rest of carries
- for (size_type i = n.size() + 1; i <= n.size() * 2 + 1; ++i)
- W[i] += W[i-1] >> static_cast<word_type>(mp_int<A,T>::valid_bits);
-
- // copy out, A = A/b**n
- //
- // The result is A/b**n but instead of converting from an array of word_type
- // to digit_type than calling mp_rshd we just copy them in the right order
- for (size_type i = 0; i < n.size() + 1; ++i)
- x[i] = static_cast<digit_type>(W[n.size() + i]);
-
- // set the max used and clamp
- x.set_size(n.size() + 1);
- x.clamp();
- if (x.is_zero())
- x.set_sign(1);
-
- // if A >= m then A = A - m
- if (x.compare_magnitude(n) != -1)
- x.sub_smaller_magnitude(n);
-}
-
-
// reduce "x" modulo "n" using the Diminished Radix algorithm.
// Based on algorithm from the paper
//
@@ -262,6 +158,7 @@
typedef typename mp_int<A,T>::digit_type digit_type;
typedef typename mp_int<A,T>::word_type word_type;
typedef typename mp_int<A,T>::size_type size_type;
+ typedef typename mp_int<A,T>::iterator iterator;
const size_type m = n.size();
@@ -273,11 +170,11 @@
digit_type mu = 0;
// compute (r mod B**m) + k * [r/B**m] inline and inplace
- for (size_type i = 0; i < m; ++i)
+ for (iterator d = x.begin(); d != x.begin() + m; ++d)
{
- const word_type r = static_cast<word_type>(x[m+i])
- * static_cast<word_type>(k) + x[i] + mu;
- x[i] = static_cast<digit_type>(r);
+ const word_type r = static_cast<word_type>(*(d + m))
+ * static_cast<word_type>(k) + *d + mu;
+ *d = static_cast<digit_type>(r);
mu = static_cast<digit_type>(r >> static_cast<word_type>(mp_int<A,T>::digit_bits));
}
Modified: sandbox/mp_math/boost/mp_math/mp_int/detail/primitive_ops.hpp
==============================================================================
--- sandbox/mp_math/boost/mp_math/mp_int/detail/primitive_ops.hpp (original)
+++ sandbox/mp_math/boost/mp_math/mp_int/detail/primitive_ops.hpp 2008-10-30 12:20:19 EDT (Thu, 30 Oct 2008)
@@ -102,6 +102,15 @@
// z = x * x;
static void comba_sqr(digit_type* z, const digit_type* x, size_type x_size);
+
+ // MADD ------------------------------------
+
+ // z = w * x + y
+ static digit_type multiply_add_digits(digit_type* z,
+ const digit_type* w,
+ digit_type x,
+ const digit_type* y,
+ size_type n);
};
@@ -501,6 +510,28 @@
*z = static_cast<digit_type>(acc);
}
+template<typename D, typename W, typename S>
+typename basic_primitive_ops<D,W,S>::digit_type
+basic_primitive_ops<D,W,S>::multiply_add_digits(digit_type* z,
+ const digit_type* w,
+ digit_type x,
+ const digit_type* y,
+ size_type n)
+{
+ word_type carry = 0;
+ while (n--)
+ {
+ const word_type r = static_cast<word_type>(*w++)
+ * static_cast<word_type>(x)
+ + static_cast<word_type>(*y++)
+ + carry;
+
+ *z++ = static_cast<digit_type>(r);
+ carry = r >> digit_bits;
+ }
+
+ return static_cast<digit_type>(carry);
+}
Modified: sandbox/mp_math/boost/mp_math/mp_int/div.hpp
==============================================================================
--- sandbox/mp_math/boost/mp_math/mp_int/div.hpp (original)
+++ sandbox/mp_math/boost/mp_math/mp_int/div.hpp 2008-10-30 12:20:19 EDT (Thu, 30 Oct 2008)
@@ -187,9 +187,9 @@
}
mp_int q;
- q.grow_capacity(used_ + 2);
- q.used_ = used_ + 2;
- std::memset(q.digits_, 0, q.used_ * sizeof(digit_type));
+ q.grow_capacity(size_ + 2);
+ q.size_ = size_ + 2;
+ std::memset(q.digits_, 0, q.size_ * sizeof(digit_type));
mp_int x(*this);
mp_int y(rhs);
@@ -211,8 +211,8 @@
norm = 0;
// note hac does 0 based, so if used==5 then its 0,1,2,3,4, e.g. use 4
- const size_type n = x.used_ - 1;
- const size_type t = y.used_ - 1;
+ const size_type n = x.size_ - 1;
+ const size_type t = y.size_ - 1;
// find leading digit of the quotient
// while (x >= y*beta**(n-t)) do { q[n-t] += 1; x -= y*beta**(n-t) }
@@ -231,7 +231,7 @@
// step 3. for i from n down to (t + 1)
for (size_type i = n; i >= (t + 1); i--)
{
- if (i > x.used_)
+ if (i > x.size_)
continue;
// step 3.1 if xi == yt then set q{i-t-1} to beta-1,
@@ -266,14 +266,14 @@
t1.zero();
t1[0] = (t == 0) ? 0 : y[t - 1];
t1[1] = y[t];
- t1.used_ = 2;
+ t1.size_ = 2;
t1.multiply_by_digit(q[i - t - 1]);
// find right hand
t2[0] = (i < 2) ? 0 : x[i - 2];
t2[1] = (i == 0) ? 0 : x[i - 1];
t2[2] = x[i];
- t2.used_ = 3;
+ t2.size_ = 3;
} while (t1.compare_magnitude(t2) == 1);
// step 3.3 x = x - q{i-t-1} * y * beta**{i-t-1}
Modified: sandbox/mp_math/boost/mp_math/mp_int/mod.hpp
==============================================================================
--- sandbox/mp_math/boost/mp_math/mp_int/mod.hpp (original)
+++ sandbox/mp_math/boost/mp_math/mp_int/mod.hpp 2008-10-30 12:20:19 EDT (Thu, 30 Oct 2008)
@@ -8,12 +8,12 @@
void mp_int<A,T>::modulo_2_to_the_power_of(size_type b)
{
// if modulus >= *this then return
- if (b >= used_ * valid_bits)
+ if (b >= size_ * valid_bits)
return;
// zero digits above the last digit of the modulus
const size_type offset = (b / valid_bits) + ((b % valid_bits) == 0 ? 0 : 1);
- std::memset(digits_ + offset, 0, sizeof(digit_type) * (used_ - offset));
+ std::memset(digits_ + offset, 0, sizeof(digit_type) * (size_ - offset));
// clear remaining high bits
const digit_type mask = (1 << (static_cast<digit_type>(b % valid_bits))) - 1;
Modified: sandbox/mp_math/boost/mp_math/mp_int/modpow_ctx.hpp
==============================================================================
--- sandbox/mp_math/boost/mp_math/mp_int/modpow_ctx.hpp (original)
+++ sandbox/mp_math/boost/mp_math/mp_int/modpow_ctx.hpp 2008-10-30 12:20:19 EDT (Thu, 30 Oct 2008)
@@ -141,14 +141,13 @@
{
assert(m.is_odd());
- /* fast inversion mod 2**k
- *
- * Based on the fact that
- *
- * XA = 1 (mod 2**n) => (X(2-XA)) A = 1 (mod 2**2n)
- * => 2*X*A - X*X*A*A = 1
- * => 2*(1) - (1) = 1
- */
+ // fast inversion mod 2**k
+ //
+ // Based on the fact that
+ //
+ // XA = 1 (mod 2**n) => (X(2-XA)) A = 1 (mod 2**2n)
+ // => 2*X*A - X*X*A*A = 1
+ // => 2*(1) - (1) = 1
const digit_type b = m[0];
static const typename mp_int<A,T>::size_type S =
Modified: sandbox/mp_math/boost/mp_math/mp_int/mp_int.hpp
==============================================================================
--- sandbox/mp_math/boost/mp_math/mp_int/mp_int.hpp (original)
+++ sandbox/mp_math/boost/mp_math/mp_int/mp_int.hpp 2008-10-30 12:20:19 EDT (Thu, 30 Oct 2008)
@@ -18,8 +18,6 @@
#include <boost/config.hpp>
#include <boost/random.hpp>
-#include <boost/serialization/split_member.hpp>
-#include <boost/serialization/string.hpp>
#include <boost/type_traits/is_integral.hpp>
#include <boost/utility/enable_if.hpp>
#include <boost/mp_math/mp_int/detail/string_conversion_constants.hpp>
@@ -41,22 +39,20 @@
:
Allocator::template rebind<typename Traits::digit_type>::other
{
- typedef Allocator allocator_type;
- typedef Traits traits_type;
- typedef typename traits_type::size_type size_type;
+ typedef Allocator allocator_type;
+ typedef Traits traits_type;
+ typedef typename Allocator::size_type size_type;
mp_int();
template<typename IntegralT>
mp_int(IntegralT, typename enable_if<is_integral<IntegralT> >::type* dummy = 0);
- mp_int(const char*);
- mp_int(const char*, std::ios_base::fmtflags);
+ template<typename charT>
+ mp_int(const charT*);
- #ifndef BOOST_NO_CWCHAR
- mp_int(const wchar_t*);
- mp_int(const wchar_t*, std::ios_base::fmtflags);
- #endif
+ template<typename charT>
+ mp_int(const charT*, std::ios_base::fmtflags);
template<typename charT, class traits, class Alloc>
mp_int(const std::basic_string<charT,traits,Alloc>&);
@@ -190,7 +186,7 @@
operator unspecified_bool_type() const
{
- return is_zero() ? 0 : &mp_int::used_;
+ return is_zero() ? 0 : &mp_int::size_;
}
bool is_even() const { return (digits_[0] & digit_type(1)) == 0; }
@@ -235,9 +231,9 @@
std::ios_base::fmtflags f);
iterator begin() { return digits_; }
- iterator end () { return digits_ + used_; }
+ iterator end () { return digits_ + size_; }
const_iterator begin() const { return digits_; }
- const_iterator end () const { return digits_ + used_; }
+ const_iterator end () const { return digits_ + size_; }
reverse_iterator rbegin() { return reverse_iterator(end()); }
reverse_iterator rend () { return reverse_iterator(begin()); }
const_reverse_iterator rbegin() const { return const_reverse_iterator(end()); }
@@ -248,19 +244,19 @@
digit_type& at(size_type i)
{
- if (i >= used_)
+ if (i >= size_)
throw std::out_of_range("mp_int::at: array subscript out of range");
return digits_[i];
}
const digit_type& at(size_type i) const
{
- if (i >= used_)
+ if (i >= size_)
throw std::out_of_range("mp_int::at: array subscript out of range");
return digits_[i];
}
- void push(digit_type x) { digits_[used_++] = x; }
- void pop() { --used_; }
+ void push(digit_type x) { digits_[size_++] = x; }
+ void pop() { --size_; }
void zero();
@@ -268,9 +264,9 @@
void print(bool all=false) const;
bool test_invariants() const;
- bool is_uninitialized() const { return used_ == 0U; }
+ bool is_uninitialized() const { return size_ == 0U; }
- size_type size() const { return used_; }
+ size_type size() const { return size_; }
size_type capacity() const
{
return capacity_ & ~sign_bit;
@@ -282,7 +278,7 @@
capacity_ |= c;
}
- void set_size(size_type s) { used_ = s; }
+ void set_size(size_type s) { size_ = s; }
int sign() const
{
@@ -365,24 +361,8 @@
private:
- friend class boost::serialization::access;
- template<class Archive>
- void save(Archive & ar, const unsigned int /*version*/) const
- {
- const std::string s = to_string<std::string>(std::ios_base::hex);
- ar & s;
- }
- template<class Archive>
- void load(Archive & ar, const unsigned int /*version*/)
- {
- std::string s;
- ar & s;
- assign(s, std::ios_base::hex);
- }
- BOOST_SERIALIZATION_SPLIT_MEMBER()
-
digit_type* digits_;
- size_type used_, capacity_;
+ size_type size_, capacity_;
};
@@ -393,19 +373,19 @@
using std::cout;
if (is_negative())
cout << '-';
- cout << used_ << "{";
- for (size_type i = 0; i < used_; ++i)
+ cout << size_ << "{";
+ for (size_type i = 0; i < size_; ++i)
{
cout << static_cast<word_type>(digits_[i]);
- if (i < used_ - 1)
+ if (i < size_ - 1)
cout << ",";
}
cout << "}";
if (all)
{
- cout << capacity() - used_ << "{";
- for (size_type i = used_; i < capacity(); ++i)
+ cout << capacity() - size_ << "{";
+ for (size_type i = size_; i < capacity(); ++i)
{
cout << static_cast<word_type>(digits_[i]);
if (i < capacity() - 1)
@@ -419,11 +399,11 @@
template<class A, class T>
bool mp_int<A,T>::test_invariants() const
{
- if (used_) // don't test uninitialized mp_ints
+ if (size_) // don't test uninitialized mp_ints
{
- if (used_ > capacity())
+ if (size_ > capacity())
return false;
- if (digits_[used_-1] == 0U)
+ if (digits_[size_-1] == 0U)
return false;
if (is_zero() && sign() != 1)
return false;
@@ -440,8 +420,8 @@
mp_int(rhs).swap(*this);
else
{
- std::memcpy(digits_, rhs.digits_, rhs.used_ * sizeof(digit_type));
- used_ = rhs.used_;
+ std::memcpy(digits_, rhs.digits_, rhs.size_ * sizeof(digit_type));
+ size_ = rhs.size_;
set_sign(rhs.sign());
}
}
@@ -456,7 +436,7 @@
{
this->deallocate(digits_, capacity());
digits_ = 0;
- used_ = 0;
+ size_ = 0;
capacity_ = 0;
swap(rhs);
}
@@ -475,7 +455,7 @@
template<class A, class T>
mp_int<A,T>& mp_int<A,T>::operator = (const char* s)
{
- used_ = 0;
+ size_ = 0;
init(s, s + std::strlen(s));
return *this;
}
@@ -484,7 +464,7 @@
template<class A, class T>
mp_int<A,T>& mp_int<A,T>::operator = (const wchar_t* s)
{
- used_ = 0;
+ size_ = 0;
init(s, s + std::wcslen(s));
return *this;
}
@@ -494,7 +474,7 @@
template<typename charT, class traits, class Alloc>
mp_int<A,T>& mp_int<A,T>::operator = (const std::basic_string<charT,traits,Alloc>& s)
{
- used_ = 0;
+ size_ = 0;
init(s.begin(), s.end());
return *this;
}
@@ -530,7 +510,7 @@
mp_int<A,T>::assign(RandomAccessIterator first, RandomAccessIterator last,
std::ios_base::fmtflags f)
{
- used_ = 0;
+ size_ = 0;
init(first, last, f);
}
@@ -543,7 +523,7 @@
#endif
{
std::swap(digits_, other.digits_);
- std::swap(used_, other.used_);
+ std::swap(size_, other.size_);
std::swap(capacity_, other.capacity_);
}
@@ -617,7 +597,7 @@
{
grow_capacity(1);
digits_[0] = 0;
- used_ = 1;
+ size_ = 1;
set_sign(1);
}
@@ -626,11 +606,13 @@
{
if (capacity() < n)
{
+ if (n >= sign_bit)
+ throw std::bad_alloc();
const size_type new_cap = capacity() + capacity();
if (new_cap > n)
n = new_cap;
digit_type* d = this->allocate(n, digits_);
- std::memcpy(d, digits_, sizeof(digit_type) * used_);
+ std::memcpy(d, digits_, sizeof(digit_type) * size_);
this->deallocate(digits_, capacity());
digits_ = d;
set_capacity(n);
@@ -638,19 +620,18 @@
}
// This is used to ensure that leading zero digits are trimmed.
-// Typically very fast.
template<class A, class T>
void mp_int<A,T>::clamp()
{
- // decrease used_ while the most significant digit is zero.
- while (used_ > 1 && digits_[used_-1] == 0)
- --used_;
+ // decrease size_ while the most significant digit is zero.
+ while (size_ > 1 && digits_[size_-1] == 0)
+ --size_;
}
template<class A, class T>
inline bool mp_int<A,T>::is_zero() const
{
- return used_ == 1 && digits_[0] == 0;
+ return size_ == 1 && digits_[0] == 0;
}
// disregards the sign of the numbers
@@ -661,10 +642,10 @@
int mp_int<A,T>::compare_magnitude(const mp_int& rhs) const
{
// compare based on # of non-zero digits
- if (used_ > rhs.used_)
+ if (size_ > rhs.size_)
return 1;
- if (used_ < rhs.used_)
+ if (size_ < rhs.size_)
return -1;
// compare based on digits
@@ -688,7 +669,7 @@
return -1;
// compare based on magnitude
- if (used_ > 1)
+ if (size_ > 1)
return 1;
// compare the only digit of *this to d
@@ -726,14 +707,14 @@
if (b <= 0)
return;
- grow_capacity(used_ + b);
+ grow_capacity(size_ + b);
- std::memmove(digits_ + b, digits_, used_ * sizeof(digit_type));
+ std::memmove(digits_ + b, digits_, size_ * sizeof(digit_type));
// zero the lower digits
std::memset(digits_, 0, b * sizeof(digit_type));
- used_ += b;
+ size_ += b;
}
// {A,B,C,D,E} shifted right by 2 digits becomes
@@ -744,20 +725,20 @@
if (b <= 0)
return;
- if (used_ <= b)
+ if (size_ <= b)
{
zero();
return;
}
// shift the digits down
- std::memmove(digits_, digits_ + b, (used_ - b) * sizeof(digit_type));
+ std::memmove(digits_, digits_ + b, (size_ - b) * sizeof(digit_type));
// zero the top digits
- std::memset(digits_ + used_ - b, 0, b * sizeof(digit_type));
+ std::memset(digits_ + size_ - b, 0, b * sizeof(digit_type));
// remove excess digits
- used_ -= b;
+ size_ -= b;
}
template<class A, class T>
@@ -765,10 +746,10 @@
mp_int<A,T>::precision() const
{
// get number of digits and add that
- size_type r = (used_ - 1) * valid_bits;
+ size_type r = (size_ - 1) * valid_bits;
// take the last digit and count the bits in it
- digit_type q = digits_[used_ - 1];
+ digit_type q = digits_[size_ - 1];
while (q > 0U)
{
++r;
@@ -791,7 +772,7 @@
// scan lower digits until non-zero
size_type x = 0;
- while (x < used_ && digits_[x] == 0)
+ while (x < size_ && digits_[x] == 0)
++x;
digit_type q = digits_[x];
x *= valid_bits;
Modified: sandbox/mp_math/boost/mp_math/mp_int/mul.hpp
==============================================================================
--- sandbox/mp_math/boost/mp_math/mp_int/mul.hpp (original)
+++ sandbox/mp_math/boost/mp_math/mp_int/mul.hpp 2008-10-30 12:20:19 EDT (Thu, 30 Oct 2008)
@@ -16,44 +16,40 @@
return;
// make sure we can hold the result
- grow_capacity(used_ + 1);
+ grow_capacity(size_ + 1);
- const digit_type carry = ops_type::multiply_by_digit(digits_, digits_, used_, x);
+ const digit_type carry = ops_type::multiply_by_digit(digits_, digits_, size_, x);
if (carry)
- digits_[used_++] = carry;
+ push(carry);
}
/* *this *= 2 */
template<class A, class T>
void mp_int<A,T>::multiply_by_2()
{
- grow_capacity(used_ + 1);
+ grow_capacity(size_ + 1);
digit_type carry = 0;
- for (size_type x = 0; x < used_; ++x)
+ for (iterator d = begin(); d != end(); ++d)
{
- /* get what will be the *next* carry bit from the
- * MSB of the current digit
- */
- const digit_type rr =
- digits_[x] >> (static_cast<digit_type>(valid_bits - 1));
+ // get what will be the *next* carry bit from the
+ // MSB of the current digit
+ const digit_type rr = *d >> (static_cast<digit_type>(valid_bits - 1));
- /* now shift up this digit, add in the carry [from the previous] */
- digits_[x] = (digits_[x] << digit_type(1)) | carry;
+ // now shift up this digit, add in the carry [from the previous]
+ *d = (*d << digit_type(1)) | carry;
- /* copy the carry that would be from the source
- * digit into the next iteration
- */
+ // copy the carry that would be from the source
+ // digit into the next iteration
carry = rr;
}
- /* new leading digit? */
+ // new leading digit?
if (carry)
{
- /* add a MSB which is always 1 at this point */
- digits_[used_] = 1;
- ++used_;
+ // add a MSB which is always 1 at this point
+ push(1);
}
}
@@ -67,7 +63,7 @@
template<class A, class T>
void mp_int<A,T>::toom_cook_mul(const mp_int& b)
{
- const size_type B = std::min(used_, b.used_) / 3;
+ const size_type B = std::min(size_, b.size_) / 3;
// a = a2 * B**2 + a1 * B + a0
mp_int a0(*this);
@@ -221,25 +217,25 @@
mp_int x0, x1, y0, y1, /*tmp,*/ x0y0, x1y1;
// min # of digits
- const size_type B = std::min(used_, b.used_) / 2;
+ const size_type B = std::min(size_, b.size_) / 2;
// allocate memory
x0.grow_capacity(B);
- x1.grow_capacity(used_ + b.used_);
+ x1.grow_capacity(size_ + b.size_);
y0.grow_capacity(B);
- y1.grow_capacity(b.used_ - B + 1);
+ y1.grow_capacity(b.size_ - B + 1);
- // set used_ count
- x0.used_ = y0.used_ = B;
- x1.used_ = used_ - B;
- y1.used_ = b.used_ - B;
+ // set size_ count
+ x0.size_ = y0.size_ = B;
+ x1.size_ = size_ - B;
+ y1.size_ = b.size_ - B;
// copy digits over
static const size_type s = sizeof(digit_type);
std::memcpy(x0.digits_, digits_, s * B);
std::memcpy(y0.digits_, b.digits_, s * B);
- std::memcpy(x1.digits_, digits_ + B, s * ( used_ - B));
- std::memcpy(y1.digits_, b.digits_ + B, s * (b.used_ - B));
+ std::memcpy(x1.digits_, digits_ + B, s * ( size_ - B));
+ std::memcpy(y1.digits_, b.digits_ + B, s * (b.size_ - B));
// only need to clamp the lower words since by definition the
// upper words x1/y1 must have a known number of digits
@@ -283,34 +279,34 @@
tmp.grow_capacity(digs);
// zero allocated digits
std::memset(tmp.digits_, 0, sizeof(digit_type) * digs);
- tmp.used_ = digs;
+ tmp.size_ = digs;
// compute the digits of the product directly
- for (size_type i = 0; i < used_; ++i)
+ for (size_type i = 0; i < size_; ++i)
{
digit_type carry = 0;
// limit ourselves to making digs digits of output
- const size_type pb = std::min(b.used_, digs - i);
+ const size_type pb = std::min(b.size_, digs - i);
// compute the columns of the output and propagate the carry
for (size_type j = 0; j < pb; ++j)
{
// compute the column as a word_type
- const word_type r = static_cast<word_type>(tmp.digits_[i+j])
+ const word_type r = static_cast<word_type>(tmp[i+j])
+ static_cast<word_type>(digits_[i])
- * static_cast<word_type>(b.digits_[j])
+ * static_cast<word_type>(b[j])
+ static_cast<word_type>(carry);
// the new column is the lower part of the result
- tmp.digits_[i+j] = static_cast<digit_type>(r);
+ tmp[i+j] = static_cast<digit_type>(r);
// get the carry word from the result
carry = static_cast<digit_type>(r >> static_cast<word_type>(valid_bits));
}
// set carry if it is placed below digs
if (i + pb < digs)
- tmp.digits_[i+pb] = carry;
+ tmp[i+pb] = carry;
}
tmp.clamp();
@@ -321,23 +317,23 @@
// FIXME no routine seems to use this
//
-// multiplies |a| * |b| and does not compute the lower digs digits
+// multiplies |a| * |b| and does not compute the lower num digits
// [meant to get the higher part of the product]
template<class A, class T>
-void mp_int<A,T>::mul_high_digits(const mp_int& b, size_type digs)
+void mp_int<A,T>::mul_high_digits(const mp_int& b, size_type num)
{
mp_int tmp;
- tmp.grow_capacity(used_ + b.used_ + 1);
- tmp.used_ = used_ + b.used_ + 1;
- std::memset(tmp.digits_, 0, sizeof(digit_type) * tmp.used_);
+ tmp.grow_capacity(size_ + b.size_ + 1);
+ tmp.size_ = size_ + b.size_ + 1;
+ std::memset(tmp.digits_, 0, sizeof(digit_type) * tmp.size_);
- for (size_type i = 0; i < used_; ++i)
+ for (size_type i = 0; i < size_; ++i)
{
- digit_type* dst = tmp.digits_ + digs;
- digit_type* z = b.digits_ + (digs - i);
+ iterator dst = tmp.begin() + num;
+ const_iterator z = b.begin() + (num - i);
digit_type carry = 0;
- for (size_type j = digs - i; j < b.used_; ++j)
+ for (size_type j = num - i; j < b.size_; ++j)
{
const word_type r = static_cast<word_type>(*dst)
+ static_cast<word_type>(digits_[i])
@@ -361,7 +357,7 @@
// this is a modified version of fast_s_mul_digs that only produces
-// output digits *above* digs. See the comments for fast_s_mul_digs
+// output digits *above* num. See the comments for fast_s_mul_digs
// to see how it works.
//
// This is used in the Barrett reduction since for one of the multiplications
@@ -369,8 +365,8 @@
//
// Based on Algorithm 14.12 on pp.595 of HAC.
template<class A, class T>
-void mp_int<A,T>::fast_mul_high_digits(const mp_int& b, size_type digs)
+void mp_int<A,T>::fast_mul_high_digits(const mp_int& b, size_type num)
{
- mul_high_digits(b, digs);
+ mul_high_digits(b, num);
}
Modified: sandbox/mp_math/boost/mp_math/mp_int/operators.hpp
==============================================================================
--- sandbox/mp_math/boost/mp_math/mp_int/operators.hpp (original)
+++ sandbox/mp_math/boost/mp_math/mp_int/operators.hpp 2008-10-30 12:20:19 EDT (Thu, 30 Oct 2008)
@@ -305,7 +305,7 @@
template<class A, class T>
mp_int<A,T>& mp_int<A,T>::operator <<= (size_type b)
{
- grow_capacity(used_ + b/valid_bits + 1);
+ grow_capacity(size_ + b/valid_bits + 1);
/* shift by as many digits in the bit count */
if (b >= static_cast<size_type>(valid_bits))
@@ -323,7 +323,7 @@
const digit_type shift = valid_bits - d;
digit_type carry = 0;
- for (size_type i = 0; i < used_; ++i)
+ for (size_type i = 0; i < size_; ++i)
{
/* get the higher bits of the current word */
const digit_type carry_cur = (digits_[i] >> shift) & mask;
@@ -336,7 +336,7 @@
}
if (carry)
- digits_[used_++] = carry;
+ digits_[size_++] = carry;
}
clamp();
@@ -383,15 +383,15 @@
}
else // |*this| < |rhs|
{
- grow_capacity(rhs.used_);
+ grow_capacity(rhs.size_);
set_sign(rhs.sign());
x = &rhs;
y = this;
}
- ops_type::sub_smaller_magnitude(digits_, x->digits_, x->used_,
- y->digits_, y->used_);
- used_ = x->used_;
+ ops_type::sub_smaller_magnitude(digits_, x->digits_, x->size_,
+ y->digits_, y->size_);
+ size_ = x->size_;
clamp();
if (is_zero())
@@ -418,17 +418,17 @@
}
else // |*this| < |rhs|
{
- grow_capacity(rhs.used_);
+ grow_capacity(rhs.size_);
// result has opposite sign from *this
set_sign(is_positive() ? -1 : 1);
x = &rhs;
y = this;
}
- ops_type::sub_smaller_magnitude(digits_, x->digits_, x->used_,
- y->digits_, y->used_);
+ ops_type::sub_smaller_magnitude(digits_, x->digits_, x->size_,
+ y->digits_, y->size_);
- used_ = x->used_;
+ size_ = x->size_;
clamp();
if (is_zero())
@@ -447,7 +447,7 @@
}
const int neg = (sign() == rhs.sign()) ? 1 : -1;
- const size_type min = std::min(used_, rhs.used_);
+ const size_type min = std::min(size_, rhs.size_);
if (min >= traits_type::toom_mul_cutoff)
toom_cook_mul(rhs);
@@ -456,22 +456,22 @@
else
{
mp_int tmp;
- tmp.grow_capacity(used_ + rhs.used_);
+ tmp.grow_capacity(size_ + rhs.size_);
- if (used_ == rhs.used_)
- ops_type::comba_mul(tmp.digits(), digits(), rhs.digits(), used_);
+ if (size_ == rhs.size_)
+ ops_type::comba_mul(tmp.digits(), digits(), rhs.digits(), size_);
else
{
// always multiply larger by smaller number
const mp_int* a = this;
const mp_int* b = &rhs;
- if (a->used_ < b->used_)
+ if (a->size_ < b->size_)
std::swap(a, b);
- ops_type::comba_mul(tmp.digits(), a->digits(), a->used_, b->digits(), b->used_);
+ ops_type::comba_mul(tmp.digits(), a->digits(), a->size_, b->digits(), b->size_);
}
- tmp.used_ = used_ + rhs.used_;
+ tmp.size_ = size_ + rhs.size_;
tmp.clamp();
swap(tmp);
}
@@ -505,16 +505,16 @@
mp_int tmp;
const mp_int* x;
- if (used_ > rhs.used_)
+ if (size_ > rhs.size_)
{
tmp = *this;
- px = rhs.used_;
+ px = rhs.size_;
x = &rhs;
}
else
{
tmp = rhs;
- px = used_;
+ px = size_;
x = this;
}
@@ -534,16 +534,16 @@
mp_int tmp;
const mp_int *x;
- if (used_ > rhs.used_)
+ if (size_ > rhs.size_)
{
tmp = *this;
- px = rhs.used_;
+ px = rhs.size_;
x = &rhs;
}
else
{
tmp = rhs;
- px = used_;
+ px = size_;
x = this;
}
@@ -551,7 +551,7 @@
tmp[i] &= (*x)[i];
/* zero digits above the last from the smallest mp_int */
- std::memset(tmp.digits_ + px, 0, (tmp.used_ - px) * sizeof(digit_type));
+ std::memset(tmp.digits_ + px, 0, (tmp.size_ - px) * sizeof(digit_type));
tmp.clamp();
swap(tmp);
@@ -565,16 +565,16 @@
mp_int tmp;
const mp_int *x;
- if (used_ > rhs.used_)
+ if (size_ > rhs.size_)
{
tmp = *this;
- px = rhs.used_;
+ px = rhs.size_;
x = &rhs;
}
else
{
tmp = rhs;
- px = used_;
+ px = size_;
x = this;
}
Modified: sandbox/mp_math/boost/mp_math/mp_int/pow.hpp
==============================================================================
--- sandbox/mp_math/boost/mp_math/mp_int/pow.hpp (original)
+++ sandbox/mp_math/boost/mp_math/mp_int/pow.hpp 2008-10-30 12:20:19 EDT (Thu, 30 Oct 2008)
@@ -11,11 +11,11 @@
{
grow_capacity(b / digit_bits + 1);
- // set the used count of where the bit will go
- used_ = b / digit_bits + 1;
+ // set size_ to where the bit will go
+ size_ = b / digit_bits + 1;
// set all bits to zero
- std::memset(digits_, 0, used_ * sizeof(digit_type));
+ std::memset(digits_, 0, size_ * sizeof(digit_type));
// put the single bit in its place
digits_[b / digit_bits] = digit_type(1) << (b % digit_bits);
Modified: sandbox/mp_math/boost/mp_math/mp_int/sqr.hpp
==============================================================================
--- sandbox/mp_math/boost/mp_math/mp_int/sqr.hpp (original)
+++ sandbox/mp_math/boost/mp_math/mp_int/sqr.hpp 2008-10-30 12:20:19 EDT (Thu, 30 Oct 2008)
@@ -9,7 +9,7 @@
{
mp_int w0, w1, w2, w3, w4, tmp1, a0, a1, a2;
- const size_type B = used_ / 3;
+ const size_type B = size_ / 3;
/* a = a2 * B**2 + a1 * B + a0 */
a0 = *this;
@@ -130,22 +130,22 @@
mp_int x0, x1, tmp, tmp2, x0x0, x1x1;
/* min # of digits divided in two */
- const size_type B = used_ >> 1;
+ const size_type B = size_ >> 1;
/* init copy all the temps */
x0.grow_capacity(B);
- x1.grow_capacity(used_ - B);
+ x1.grow_capacity(size_ - B);
/* init temps */
x0x0.grow_capacity(B * 2);
- x1x1.grow_capacity((used_ - B) * 2);
+ x1x1.grow_capacity((size_ - B) * 2);
/* now shift the digits */
std::memcpy(x0.digits_, digits_, B * sizeof(digit_type));
- std::memcpy(x1.digits_, digits_ + B, (used_ - B) * sizeof(digit_type));
+ std::memcpy(x1.digits_, digits_ + B, (size_ - B) * sizeof(digit_type));
- x0.used_ = B;
- x1.used_ = used_ - B;
+ x0.size_ = B;
+ x1.size_ = size_ - B;
x0.clamp();
@@ -175,11 +175,11 @@
void mp_int<A,T>::comba_sqr()
{
mp_int tmp;
- tmp.grow_capacity(used_ + used_);
+ tmp.grow_capacity(size_ + size_);
- ops_type::comba_sqr(tmp.digits(), digits(), used_);
+ ops_type::comba_sqr(tmp.digits(), digits(), size_);
- tmp.used_ = used_ + used_;
+ tmp.size_ = size_ + size_;
tmp.clamp();
swap(tmp);
@@ -189,9 +189,9 @@
template<class A, class T>
void mp_int<A,T>::sqr()
{
- if (used_ >= traits_type::toom_sqr_cutoff)
+ if (size_ >= traits_type::toom_sqr_cutoff)
toom_sqr();
- else if (used_ >= traits_type::karatsuba_sqr_cutoff)
+ else if (size_ >= traits_type::karatsuba_sqr_cutoff)
karatsuba_sqr();
else
comba_sqr();
Modified: sandbox/mp_math/boost/mp_math/mp_int/string_conversion.hpp
==============================================================================
--- sandbox/mp_math/boost/mp_math/mp_int/string_conversion.hpp (original)
+++ sandbox/mp_math/boost/mp_math/mp_int/string_conversion.hpp 2008-10-30 12:20:19 EDT (Thu, 30 Oct 2008)
@@ -24,7 +24,7 @@
// low level from string conversion routine
// Requires:
-// - used_ = 0
+// - size_ = 0
// - first and last must point into string without sign prefix and without base
// prefix (like 0x)
// - radix is 8, 10 or 16
@@ -32,7 +32,7 @@
template<typename Iter>
void mp_int<A,T>::from_string(Iter first, Iter last, unsigned radix)
{
- assert(used_ == 0);
+ assert(size_ == 0);
assert(first != last);
const detail::string_conversion_constants<mp_int> sc(radix);
@@ -64,14 +64,14 @@
if (offset >= valid_bits)
{
- digits_[used_++] = result;
+ digits_[size_++] = result;
offset -= valid_bits;
result = static_cast<digit_type>(x >> (sc.radix_storage_bits - offset));
}
}
- if (result || !used_)
- digits_[used_++] = result;
+ if (result || !size_)
+ digits_[size_++] = result;
clamp();
if (is_zero())
@@ -104,18 +104,18 @@
}
// then use multi precision routines to convert this digit to binary
- if (used_)
+ if (size_)
{
- digit_type carry = ops_type::multiply_by_digit(digits_, digits_, used_,
+ digit_type carry = ops_type::multiply_by_digit(digits_, digits_, size_,
sc.max_power_value);
- carry += ops_type::add_single_digit(digits_, digits_, used_, result);
+ carry += ops_type::add_single_digit(digits_, digits_, size_, result);
if (carry)
- digits_[used_++] = carry;
+ digits_[size_++] = carry;
}
else
- digits_[used_++] = result;
+ digits_[size_++] = result;
}
// one last round for the remaining decimal digits
@@ -133,18 +133,18 @@
radix_power *= 10U;
}
- if (used_)
+ if (size_)
{
- digit_type carry = ops_type::multiply_by_digit(digits_, digits_, used_,
+ digit_type carry = ops_type::multiply_by_digit(digits_, digits_, size_,
static_cast<digit_type>(radix_power));
- carry += ops_type::add_single_digit(digits_, digits_, used_, result);
+ carry += ops_type::add_single_digit(digits_, digits_, size_, result);
if (carry)
- digits_[used_++] = carry;
+ digits_[size_++] = carry;
}
else
- digits_[used_++] = result;
+ digits_[size_++] = result;
}
}
}
@@ -174,7 +174,7 @@
StringT s;
- if (!used_)
+ if (!size_)
return s;
digit_type radix;
Modified: sandbox/mp_math/boost/mp_math/mp_int/sub.hpp
==============================================================================
--- sandbox/mp_math/boost/mp_math/mp_int/sub.hpp (original)
+++ sandbox/mp_math/boost/mp_math/mp_int/sub.hpp 2008-10-30 12:20:19 EDT (Thu, 30 Oct 2008)
@@ -14,7 +14,7 @@
return;
}
- if (used_ == 1)
+ if (size_ == 1)
{
if (digits_[0] < b) // example: 2 - 6 = -4
{
@@ -26,9 +26,9 @@
}
else
{
- ops_type::subtract_single_digit(digits_, digits_, used_, b);
- if (!digits_[used_-1])
- --used_;
+ ops_type::subtract_single_digit(digits_, digits_, size_, b);
+ if (!digits_[size_-1])
+ --size_;
}
}
@@ -36,7 +36,7 @@
template<class A, class T>
inline void mp_int<A,T>::sub_smaller_magnitude(const mp_int& rhs)
{
- ops_type::sub_smaller_magnitude(digits_, digits_, used_, rhs.digits_, rhs.used_);
+ ops_type::sub_smaller_magnitude(digits_, digits_, size_, rhs.digits_, rhs.size_);
clamp();
}
Modified: sandbox/mp_math/boost/mp_math/mp_int/traits.hpp
==============================================================================
--- sandbox/mp_math/boost/mp_math/mp_int/traits.hpp (original)
+++ sandbox/mp_math/boost/mp_math/mp_int/traits.hpp 2008-10-30 12:20:19 EDT (Thu, 30 Oct 2008)
@@ -8,6 +8,7 @@
#include <cstddef> // size_t
#include <boost/config.hpp>
+#include <boost/static_assert.hpp>
#include <boost/mpl/back.hpp>
#include <boost/mpl/bool.hpp>
#include <boost/mpl/deref.hpp>
@@ -69,23 +70,22 @@
std::numeric_limits<Digit>::digits <= std::numeric_limits<Word>::digits/2
);
- typedef std::size_t size_type; // TODO should prolly get size_type from allocator_type
- typedef Digit digit_type;
- typedef Word word_type;
-
- static size_type toom_mul_cutoff;
- static size_type toom_sqr_cutoff;
- static size_type karatsuba_mul_cutoff;
- static size_type karatsuba_sqr_cutoff;
+ typedef Digit digit_type;
+ typedef Word word_type;
+
+ static std::size_t toom_mul_cutoff;
+ static std::size_t toom_sqr_cutoff;
+ static std::size_t karatsuba_mul_cutoff;
+ static std::size_t karatsuba_sqr_cutoff;
};
#define BMPINT_init(S) template<typename D, typename W>\
- typename mp_int_traits<D,W>::S mp_int_traits<D,W>::
-BMPINT_init(size_type )toom_mul_cutoff = 350;
-BMPINT_init(size_type )toom_sqr_cutoff = 400;
-BMPINT_init(size_type )karatsuba_mul_cutoff = 80;
-BMPINT_init(size_type )karatsuba_sqr_cutoff = 120;
+ S mp_int_traits<D,W>::
+BMPINT_init(std::size_t)toom_mul_cutoff = 350;
+BMPINT_init(std::size_t)toom_sqr_cutoff = 400;
+BMPINT_init(std::size_t)karatsuba_mul_cutoff = 80;
+BMPINT_init(std::size_t)karatsuba_sqr_cutoff = 120;
#undef BMPINT_init
Added: sandbox/mp_math/boost/mp_math/mp_int_serialization.hpp
==============================================================================
--- (empty file)
+++ sandbox/mp_math/boost/mp_math/mp_int_serialization.hpp 2008-10-30 12:20:19 EDT (Thu, 30 Oct 2008)
@@ -0,0 +1,37 @@
+#include <boost/mp_math/mp_int/mp_int_fwd.hpp>
+#include <boost/serialization/split_free.hpp>
+#include <boost/serialization/string.hpp>
+
+namespace boost {
+namespace serialization {
+
+template<class Archive, class A, class T>
+void save(Archive& ar,
+ const boost::mp_math::mp_int<A,T>& x,
+ const unsigned int /*version*/)
+{
+ const std::string s = x.template to_string<std::string>(std::ios_base::hex);
+ ar & s;
+}
+
+template<class Archive, class A, class T>
+void load(Archive& ar,
+ boost::mp_math::mp_int<A,T>& x,
+ const unsigned int /*version*/)
+{
+ std::string s;
+ ar & s;
+ x.template assign(s, std::ios_base::hex);
+}
+
+template<class Archive, class A, class T>
+inline void serialize(Archive& ar,
+ boost::mp_math::mp_int<A,T>& x,
+ const unsigned int version)
+{
+ boost::serialization::split_free(ar, x, version);
+}
+
+} // namespace serialization
+} // namespace boost
+
Modified: sandbox/mp_math/libs/mp_math/test/serialization.cpp
==============================================================================
--- sandbox/mp_math/libs/mp_math/test/serialization.cpp (original)
+++ sandbox/mp_math/libs/mp_math/test/serialization.cpp 2008-10-30 12:20:19 EDT (Thu, 30 Oct 2008)
@@ -8,6 +8,7 @@
#include <boost/archive/text_iarchive.hpp>
#include <boost/test/unit_test.hpp>
#include "prerequisite.hpp"
+#include <boost/mp_math/mp_int_serialization.hpp>
BOOST_AUTO_TEST_CASE_TEMPLATE(test_serialization1, mp_int_type, mp_int_types)
{