|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r49480 - sandbox/mp_math/boost/mp_math/mp_int
From: baraclese_at_[hidden]
Date: 2008-10-28 17:59:31
Author: baraclese
Date: 2008-10-28 17:59:30 EDT (Tue, 28 Oct 2008)
New Revision: 49480
URL: http://svn.boost.org/trac/boost/changeset/49480
Log:
* Store sign in the high bit of capacity_.
* A few more comment fixes.
Text files modified:
sandbox/mp_math/boost/mp_math/mp_int/add.hpp | 6 +-
sandbox/mp_math/boost/mp_math/mp_int/ctors.hpp | 23 +++----
sandbox/mp_math/boost/mp_math/mp_int/div.hpp | 17 +++--
sandbox/mp_math/boost/mp_math/mp_int/mod.hpp | 2
sandbox/mp_math/boost/mp_math/mp_int/mp_int.hpp | 115 +++++++++++++++++++++------------------
sandbox/mp_math/boost/mp_math/mp_int/mul.hpp | 4
sandbox/mp_math/boost/mp_math/mp_int/operators.hpp | 24 +++----
sandbox/mp_math/boost/mp_math/mp_int/sqr.hpp | 2
sandbox/mp_math/boost/mp_math/mp_int/string_conversion.hpp | 2
sandbox/mp_math/boost/mp_math/mp_int/sub.hpp | 6 +-
10 files changed, 104 insertions(+), 97 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-28 17:59:30 EDT (Tue, 28 Oct 2008)
@@ -20,7 +20,7 @@
{
digits_[0] -= b;
if (is_zero())
- sign_ = 1;
+ set_sign(1);
}
else
{
@@ -28,9 +28,9 @@
digits_[0] = b - digits_[0];
else // example -11 + 5 = -6
{
- sign_ = 1;
+ set_sign(1);
sub_digit(b);
- sign_ = -1;
+ set_sign(-1);
}
}
}
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-28 17:59:30 EDT (Tue, 28 Oct 2008)
@@ -8,8 +8,7 @@
:
digits_(0),
used_(0),
- capacity_(0),
- sign_(1)
+ capacity_(0)
{
}
@@ -34,7 +33,7 @@
if (c == last)
{
- sign_ = 1;
+ set_sign(1);
return;
}
@@ -77,7 +76,7 @@
else
throw std::invalid_argument("mp_int ctor: malformed string");
- sign_ = sign;
+ set_sign(sign);
from_string(c, last, radix);
}
@@ -92,13 +91,13 @@
if (c == last)
{
- sign_ = 1;
+ set_sign(1);
return;
}
if (*c == '-')
{
- sign_ = -1;
+ set_sign(-1);
++c;
}
else
@@ -110,7 +109,7 @@
else
throw std::invalid_argument("mp_int<>::init: expected a '+' sign");
}
- sign_ = 1;
+ set_sign(1);
}
const bool uppercase = f & std::ios_base::uppercase;
@@ -241,8 +240,8 @@
digits_ = this->allocate(copy.used_);
std::memcpy(digits_, copy.digits_, copy.used_ * sizeof(digit_type));
used_ = copy.used_;
- capacity_ = copy.used_;
- sign_ = copy.sign_;
+ set_capacity(copy.used_);
+ set_sign(copy.sign());
}
#ifdef BOOST_HAS_RVALUE_REFS
@@ -251,13 +250,11 @@
:
digits_(copy.digits_),
used_(copy.used_),
- capacity_(copy.capacity_),
- sign_(copy.sign_)
+ capacity_(copy.capacity_) // this copies capacity and sign
{
copy.digits_ = 0;
copy.used_ = 0;
copy.capacity_ = 0;
- copy.sign_ = 1;
}
#endif
@@ -265,6 +262,6 @@
template<class A, class T>
mp_int<A,T>::~mp_int()
{
- this->deallocate(digits_, capacity_);
+ this->deallocate(digits_, capacity());
}
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-28 17:59:30 EDT (Tue, 28 Oct 2008)
@@ -44,7 +44,7 @@
clamp();
if (is_zero())
- sign_ = 1;
+ set_sign(1);
return static_cast<digit_type>(w);
}
@@ -65,7 +65,7 @@
}
clamp();
if (is_zero())
- sign_ = 1;
+ set_sign(1);
}
// divide by three (based on routine from MPI and the GMP manual)
@@ -156,7 +156,7 @@
}
clamp();
if (is_zero())
- sign_ = 1;
+ set_sign(1);
}
// integer signed division.
@@ -195,8 +195,9 @@
mp_int y(rhs);
// fix the sign
- const int neg = (sign_ == rhs.sign_) ? 1 : -1;
- x.sign_ = y.sign_ = 1;
+ const int neg = (sign() == rhs.sign()) ? 1 : -1;
+ x.set_sign(1);
+ y.set_sign(1);
// normalize both x and y, ensure that y >= beta/2, [beta == 2**valid_bits]
size_type norm = y.precision() % valid_bits;
@@ -282,7 +283,7 @@
x -= t1;
// if x < 0 then { x = x + y*beta**{i-t-1}; q{i-t-1} -= 1; }
- if (x.sign_ == -1)
+ if (x.is_negative())
{
t1 = y;
t1.shift_digits_left(i - t -1);
@@ -295,11 +296,11 @@
// now q is the quotient and x is the remainder [which we have to normalize]
// get sign before writing to *this
- x.sign_ = x.is_zero() ? 1 : sign_;
+ x.set_sign(x.is_zero() ? 1 : sign());
q.clamp();
swap(q);
- sign_ = neg;
+ set_sign(neg);
if (remainder)
{
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-28 17:59:30 EDT (Tue, 28 Oct 2008)
@@ -21,6 +21,6 @@
clamp();
if (is_zero())
- sign_ = 1;
+ set_sign(1);
}
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-28 17:59:30 EDT (Tue, 28 Oct 2008)
@@ -184,20 +184,20 @@
private:
- typedef int mp_int::*unspecified_bool_type;
+ typedef size_type mp_int::*unspecified_bool_type;
public:
operator unspecified_bool_type() const
{
- return is_zero() ? 0 : &mp_int::sign_;
+ return is_zero() ? 0 : &mp_int::used_;
}
bool is_even() const { return (digits_[0] & digit_type(1)) == 0; }
bool is_odd () const { return (digits_[0] & digit_type(1)) == 1; }
- bool is_positive() const { return sign_ == 1; }
- bool is_negative() const { return sign_ == -1; }
+ bool is_positive() const { return sign() == 1; }
+ bool is_negative() const { return sign() == -1; }
template<class StringT>
StringT to_string(std::ios_base::fmtflags f = std::ios_base::dec) const;
@@ -224,6 +224,9 @@
//1 << (std::numeric_limits<word_type>::digits - 2 * valid_bits + 1);
static const digit_type digit_max = static_cast<digit_type>(-1);
+ static const size_type sign_bit =
+ size_type(1) << (std::numeric_limits<size_type>::digits - 1U);
+
template<typename RandomAccessIterator>
void init(RandomAccessIterator first, RandomAccessIterator last);
@@ -265,17 +268,36 @@
void print(bool all=false) const;
bool test_invariants() const;
- bool is_uninitialized() const { return digits_ == 0; }
+ bool is_uninitialized() const { return used_ == 0U; }
size_type size() const { return used_; }
- size_type capacity() const { return capacity_; }
+ size_type capacity() const
+ {
+ return capacity_ & ~sign_bit;
+ }
+
+ void set_capacity(size_type c)
+ {
+ capacity_ &= sign_bit;
+ capacity_ |= c;
+ }
void set_size(size_type s) { used_ = s; }
- int sign() const { return sign_; }
- void set_sign(int s) { sign_ = s; }
+ int sign() const
+ {
+ return (capacity_ & sign_bit) ? -1 : 1;
+ }
+
+ void set_sign(int s)
+ {
+ if (s == 1)
+ capacity_ &= ~sign_bit;
+ else
+ capacity_ |= sign_bit;
+ }
- digit_type* digits() { return digits_; }
+ digit_type* digits() { return digits_; }
const digit_type* digits() const { return digits_; }
void grow_capacity(size_type n);
@@ -361,7 +383,6 @@
digit_type* digits_;
size_type used_, capacity_;
- int sign_;
};
@@ -383,11 +404,11 @@
if (all)
{
- cout << capacity_ - used_ << "{";
- for (size_type i = used_; i < capacity_; ++i)
+ cout << capacity() - used_ << "{";
+ for (size_type i = used_; i < capacity(); ++i)
{
cout << static_cast<word_type>(digits_[i]);
- if (i < capacity_ - 1)
+ if (i < capacity() - 1)
cout << ",";
}
cout << "}";
@@ -400,13 +421,11 @@
{
if (used_) // don't test uninitialized mp_ints
{
- if (used_ > capacity_)
- return false;
- if (digits_[used_-1] == 0)
+ if (used_ > capacity())
return false;
- if (sign_ != 1 && sign_ != -1)
+ if (digits_[used_-1] == 0U)
return false;
- if (is_zero() && sign_ != 1)
+ if (is_zero() && sign() != 1)
return false;
}
return true;
@@ -417,13 +436,13 @@
{
if (this != &rhs)
{
- if ((capacity_ == 0) || (capacity_ < rhs.capacity_))
+ if ((capacity() == 0) || (capacity() < rhs.capacity()))
mp_int(rhs).swap(*this);
else
{
std::memcpy(digits_, rhs.digits_, rhs.used_ * sizeof(digit_type));
used_ = rhs.used_;
- sign_ = rhs.sign_;
+ set_sign(rhs.sign());
}
}
return *this;
@@ -435,11 +454,10 @@
{
if (this != &rhs)
{
- this->deallocate(digits_, capacity_);
+ this->deallocate(digits_, capacity());
digits_ = 0;
used_ = 0;
capacity_ = 0;
- sign_ = 1;
swap(rhs);
}
return *this;
@@ -527,7 +545,6 @@
std::swap(digits_, other.digits_);
std::swap(used_, other.used_);
std::swap(capacity_, other.capacity_);
- std::swap(sign_, other.sign_);
}
template<class A, class T>
@@ -601,34 +618,31 @@
grow_capacity(1);
digits_[0] = 0;
used_ = 1;
- sign_ = 1;
+ set_sign(1);
}
template<class A, class T>
void mp_int<A,T>::grow_capacity(size_type n)
{
- if (capacity_ < n)
+ if (capacity() < n)
{
- const size_type new_cap = capacity_ + capacity_;
+ 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_);
- this->deallocate(digits_, capacity_);
+ this->deallocate(digits_, capacity());
digits_ = d;
- capacity_ = n;
+ set_capacity(n);
}
}
-/* trim unused digits
- *
- * This is used to ensure that leading zero digits are trimmed.
- * Typically very fast.
- */
+// 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. */
+ // decrease used_ while the most significant digit is zero.
while (used_ > 1 && digits_[used_-1] == 0)
--used_;
}
@@ -646,14 +660,14 @@
template<class A, class T>
int mp_int<A,T>::compare_magnitude(const mp_int& rhs) const
{
- /* compare based on # of non-zero digits */
+ // compare based on # of non-zero digits
if (used_ > rhs.used_)
return 1;
if (used_ < rhs.used_)
return -1;
- /* compare based on digits */
+ // compare based on digits
const_reverse_iterator d = rbegin();
const_reverse_iterator d2 = rhs.rbegin();
for (; d != rend(); ++d, ++d2)
@@ -669,15 +683,15 @@
template<class A, class T>
int mp_int<A,T>::compare_to_digit(digit_type d) const
{
- /* compare based on sign */
+ // compare based on sign
if (is_negative())
return -1;
- /* compare based on magnitude */
+ // compare based on magnitude
if (used_ > 1)
return 1;
- /* compare the only digit of *this to d */
+ // compare the only digit of *this to d
if (digits_[0] > d)
return 1;
else if (digits_[0] < d)
@@ -689,8 +703,7 @@
template<class A, class T>
int mp_int<A,T>::compare(const mp_int& rhs) const
{
- /* compare based on sign */
- if (sign_ != rhs.sign_)
+ if (sign() != rhs.sign())
{
if (is_negative())
return -1;
@@ -698,9 +711,8 @@
return 1;
}
- /* compare digits */
if (is_negative())
- /* if negative compare opposite direction */
+ // if negative compare opposite direction
return rhs.compare_magnitude(*this);
else
return compare_magnitude(rhs);
@@ -738,13 +750,13 @@
return;
}
- /* shift the digits down */
+ // shift the digits down
std::memmove(digits_, digits_ + b, (used_ - b) * sizeof(digit_type));
- /* zero the top digits */
+ // zero the top digits
std::memset(digits_ + used_ - b, 0, b * sizeof(digit_type));
- /* remove excess digits */
+ // remove excess digits
used_ -= b;
}
@@ -752,10 +764,10 @@
typename mp_int<A,T>::size_type
mp_int<A,T>::precision() const
{
- /* get number of digits and add that */
+ // get number of digits and add that
size_type r = (used_ - 1) * valid_bits;
- /* take the last digit and count the bits in it */
+ // take the last digit and count the bits in it
digit_type q = digits_[used_ - 1];
while (q > 0U)
{
@@ -765,7 +777,7 @@
return r;
}
-/* Counts the number of lsbs which are zero before the first one bit */
+// Counts the number of lsbs which are zero before the first one bit
template<class A, class T>
typename mp_int<A,T>::size_type
mp_int<A,T>::count_lsb() const
@@ -774,18 +786,17 @@
4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0
};
- /* easy out */
if (is_zero())
return 0;
- /* scan lower digits until non-zero */
+ // scan lower digits until non-zero
size_type x = 0;
while (x < used_ && digits_[x] == 0)
++x;
digit_type q = digits_[x];
x *= valid_bits;
- /* now scan this digit until a 1 is found */
+ // now scan this digit until a 1 is found
if ((q & 1) == 0)
{
digit_type qq;
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-28 17:59:30 EDT (Tue, 28 Oct 2008)
@@ -315,7 +315,7 @@
tmp.clamp();
if (tmp.is_zero())
- tmp.sign_ = 1;
+ tmp.set_sign(1);
swap(tmp);
}
@@ -355,7 +355,7 @@
tmp.clamp();
if (tmp.is_zero())
- tmp.sign_ = 1;
+ tmp.set_sign(1);
swap(tmp);
}
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-28 17:59:30 EDT (Tue, 28 Oct 2008)
@@ -8,7 +8,7 @@
inline bool
operator == (const mp_int<A,T>& lhs, const mp_int<A,T>& rhs)
{
- return lhs.sign_ == rhs.sign_ && lhs.used_ == rhs.used_ &&
+ return lhs.sign() == rhs.sign() && lhs.size() == rhs.size() &&
std::equal(lhs.begin(), lhs.end(), rhs.begin());
}
@@ -20,8 +20,7 @@
bool
operator < (const mp_int<A,T>& lhs, const mp_int<A,T>& rhs)
{
- /* compare based on sign */
- if (lhs.sign_ != rhs.sign_)
+ if (lhs.sign() != rhs.sign())
{
if (lhs.is_negative())
return true;
@@ -34,7 +33,6 @@
if (lhs.size() > rhs.size())
return false;
- /* compare digits */
if (lhs.is_negative())
return std::lexicographical_compare(
rhs.rbegin(), rhs.rend(), lhs.rbegin(), lhs.rend());
@@ -357,7 +355,7 @@
inline mp_int<A,T>& mp_int<A,T>::operator - ()
{
if (!is_zero())
- sign_ = sign_ == 1 ? -1 : 1;
+ set_sign(sign() == 1 ? -1 : 1);
return *this;
}
@@ -369,7 +367,7 @@
template<class A, class T>
mp_int<A,T>& mp_int<A,T>::operator += (const mp_int<A,T>& rhs)
{
- if (sign_ == rhs.sign_)
+ if (sign() == rhs.sign())
add_magnitude(rhs);
else
{
@@ -386,7 +384,7 @@
else // |*this| < |rhs|
{
grow_capacity(rhs.used_);
- sign_ = rhs.sign_;
+ set_sign(rhs.sign());
x = &rhs;
y = this;
}
@@ -397,7 +395,7 @@
clamp();
if (is_zero())
- sign_ = 1;
+ set_sign(1);
}
return *this;
}
@@ -406,7 +404,7 @@
template<class A, class T>
mp_int<A,T>& mp_int<A,T>::operator -= (const mp_int<A,T>& rhs)
{
- if (sign_ != rhs.sign_)
+ if (sign() != rhs.sign())
// add magnitudes, and use the sign of *this.
add_magnitude(rhs);
else
@@ -422,7 +420,7 @@
{
grow_capacity(rhs.used_);
// result has opposite sign from *this
- sign_ = is_positive() ? -1 : 1;
+ set_sign(is_positive() ? -1 : 1);
x = &rhs;
y = this;
}
@@ -434,7 +432,7 @@
clamp();
if (is_zero())
- sign_ = 1;
+ set_sign(1);
}
return *this;
}
@@ -448,7 +446,7 @@
return *this;
}
- const int neg = (sign_ == rhs.sign_) ? 1 : -1;
+ const int neg = (sign() == rhs.sign()) ? 1 : -1;
const size_type min = std::min(used_, rhs.used_);
if (min >= traits_type::toom_mul_cutoff)
@@ -478,7 +476,7 @@
swap(tmp);
}
- sign_ = is_zero() ? 1 : neg;
+ set_sign(is_zero() ? 1 : neg);
return *this;
}
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-28 17:59:30 EDT (Tue, 28 Oct 2008)
@@ -195,6 +195,6 @@
karatsuba_sqr();
else
comba_sqr();
- sign_ = 1;
+ set_sign(1);
}
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-28 17:59:30 EDT (Tue, 28 Oct 2008)
@@ -75,7 +75,7 @@
clamp();
if (is_zero())
- sign_ = 1;
+ set_sign(1);
}
else // radix can only be 10 at this point
{
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-28 17:59:30 EDT (Tue, 28 Oct 2008)
@@ -8,9 +8,9 @@
{
if (is_negative())
{
- sign_ = 1;
+ set_sign(1);
add_digit(b);
- sign_ = -1;
+ set_sign(-1);
return;
}
@@ -19,7 +19,7 @@
if (digits_[0] < b) // example: 2 - 6 = -4
{
digits_[0] = b - digits_[0];
- sign_ = -1;
+ set_sign(-1);
}
else // example: 8 - 7 = 1 or 5 - 5 = 0
digits_[0] -= b;
Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk