|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r54224 - in sandbox/mp_math: boost/mp_math/integer boost/mp_math/integer/detail/base/asm/asm boost/mp_math/integer/detail/base/asm/x86 libs/mp_math/test/unbounded/signed
From: baraclese_at_[hidden]
Date: 2009-06-22 15:50:44
Author: baraclese
Date: 2009-06-22 15:50:42 EDT (Mon, 22 Jun 2009)
New Revision: 54224
URL: http://svn.boost.org/trac/boost/changeset/54224
Log:
* fix svn commit glitches of last commit
Added:
sandbox/mp_math/boost/mp_math/integer/detail/base/asm/x86/
sandbox/mp_math/boost/mp_math/integer/detail/base/asm/x86/gnu_386_primitive_ops.hpp (contents, props changed)
Removed:
sandbox/mp_math/boost/mp_math/integer/detail/base/asm/asm/
sandbox/mp_math/libs/mp_math/test/unbounded/signed/traits.cpp
Text files modified:
sandbox/mp_math/boost/mp_math/integer/prime.hpp | 117 +++++++++++++--------------
sandbox/mp_math/boost/mp_math/integer/random.hpp | 166 ++++++++++++++++++++--------------------
2 files changed, 139 insertions(+), 144 deletions(-)
Added: sandbox/mp_math/boost/mp_math/integer/detail/base/asm/x86/gnu_386_primitive_ops.hpp
==============================================================================
--- (empty file)
+++ sandbox/mp_math/boost/mp_math/integer/detail/base/asm/x86/gnu_386_primitive_ops.hpp 2009-06-22 15:50:42 EDT (Mon, 22 Jun 2009)
@@ -0,0 +1,76 @@
+// Copyright Kevin Sopp 2008 - 2009.
+// Distributed under the Boost Software License, Version 1.0.
+// (See accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+template<>
+struct primitive_ops<unsigned int, unsigned int, unsigned int>
+:
+ basic_primitive_ops<unsigned int,unsigned int,unsigned int>
+{
+ typedef unsigned int dword;
+ static unsigned int add_digits (dword* x, const dword* y, dword n);
+ static unsigned int subtract_digits(dword* x, const dword* y, dword n);
+};
+
+
+template<>
+inline
+unsigned int
+primitive_ops<unsigned int, unsigned int, unsigned int>::
+add_digits(dword* x, const dword* y, dword n)
+{
+ dword carry = 0;
+
+ __asm__ __volatile__(
+ "clc \n\t"
+ "0: \n\t"
+ "mov (%[y]), %%eax \n\t"
+ "adc %%eax, (%[x]) \n\t"
+ "lea 4(%[y]), %[y] \n\t" // increment pointer
+ "lea 4(%[x]), %[x] \n\t" // increment pointer
+ "loop 0b \n\t"
+ "adc $0, %[carry] "
+ :
+ [carry] "=m" (carry)
+ :
+ [y] "r" (y),
+ [x] "r" (x),
+ [n] "c" (n)
+ :
+ "cc", "memory", "%eax"
+ );
+
+ return carry;
+}
+
+template<>
+inline
+unsigned int
+primitive_ops<unsigned int, unsigned int, unsigned int>::
+subtract_digits(dword* x, const dword* y, dword n)
+{
+ dword carry = 0;
+
+ __asm__ __volatile__(
+ "clc \n\t"
+ "0: \n\t"
+ "mov (%[y]), %%eax \n\t"
+ "sbb %%eax, (%[x]) \n\t"
+ "lea 4(%[y]), %[y] \n\t"
+ "lea 4(%[x]), %[x] \n\t"
+ "loop 0b \n\t"
+ "adc $0, %[carry] "
+ :
+ [carry] "=m" (carry)
+ :
+ [y] "r" (y),
+ [x] "r" (x),
+ [n] "c" (n)
+ :
+ "cc", "memory", "%eax"
+ );
+
+ return carry;
+}
+
Modified: sandbox/mp_math/boost/mp_math/integer/prime.hpp
==============================================================================
--- sandbox/mp_math/boost/mp_math/integer/prime.hpp (original)
+++ sandbox/mp_math/boost/mp_math/integer/prime.hpp 2009-06-22 15:50:42 EDT (Mon, 22 Jun 2009)
@@ -1,13 +1,14 @@
-// Copyright Kevin Sopp 2008.
+// Copyright Kevin Sopp 2008 - 2009.
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)
-#ifndef BOOST_MP_MATH_MP_INT_PRIME_HPP
-#define BOOST_MP_MATH_MP_INT_PRIME_HPP
+#ifndef BOOST_MP_MATH_INTEGER_PRIME_HPP
+#define BOOST_MP_MATH_INTEGER_PRIME_HPP
-#include <boost/mp_math/mp_int/mp_int_fwd.hpp>
-#include <boost/mp_math/mp_int/detail/prime_tab.hpp>
+#include <boost/mp_math/integer/random.hpp>
+#include <boost/mp_math/integer/detail/multiplier.hpp>
+#include <boost/mp_math/integer/detail/prime_tab.hpp>
namespace boost {
@@ -23,17 +24,16 @@
{
typedef bool result_type;
- template<class A, class T>
- bool operator()(const mp_int<A,T>& p) const;
+ template<class ApInt>
+ bool operator()(const ApInt& p) const;
};
-template<class A, class T>
-bool primality_division_test::operator()(const mp_int<A,T>& p) const
+template<class ApInt>
+bool primality_division_test::operator()(const ApInt& p) const
{
- typedef typename mp_int<A,T>::traits_type traits;
- typedef typename traits::digit_type digit_type;
- typedef detail::prime_tab<digit_type> prime_tab;
+ typedef typename ApInt::digit_type digit_type;
+ typedef detail::prime_tab<digit_type> prime_tab;
if (p.is_even())
{
@@ -43,19 +43,14 @@
return true;
}
- mp_int<A,T> tmp;
for (int i = 0; i < prime_tab::num_primes; ++i)
{
- /* what is x mod prime_tab[i] */
- tmp = p;
- const digit_type r =
- tmp.divide_by_digit(
- static_cast<digit_type>(prime_tab::values[i]));
+ const digit_type small_prime = static_cast<digit_type>(prime_tab::values[i]);
+ const ApInt remainder = p % small_prime;
- /* is the residue zero? */
- if (r == 0)
+ if (remainder == digit_type(0))
{
- if (p != prime_tab::values[i])
+ if (p != small_prime)
return false;
else
return true; // definitely prime
@@ -77,12 +72,12 @@
// returns true if p is probably prime
// NOTE: may return true for carmichael numbers
template<
- class Distribution = uniform_mp_int<>
+ class Distribution = uniform_integer<>
>
class primality_fermat_test
{
const unsigned int rounds_;
-
+
public:
typedef Distribution distribution_type;
@@ -93,37 +88,37 @@
rounds_(rounds)
{}
- template<class Engine, class A, class T>
- bool operator()(Engine& e, const mp_int<A,T>& p) const;
+ template<class Engine, class ApInt>
+ bool operator()(Engine& e, const ApInt& p) const;
};
template<class Distribution>
-template<class Engine, class A, class T>
+template<class Engine, class ApInt>
bool
primality_fermat_test<Distribution>::operator()
- (Engine& eng, const mp_int<A,T>& p) const
+ (Engine& eng, const ApInt& p) const
{
- typedef typename mp_int<A,T>::digit_type digit_type;
-
+ typedef typename ApInt::digit_type digit_type;
+
const digit_type one = 1;
- const mp_int<A,T> p1(p-one);
-
+ const ApInt p1(p-one);
+
distribution_type rng(digit_type(2), p1);
- modpow_ctx<A,T> ctx;
+ modpow_ctx<ApInt> ctx;
for (unsigned int i = 0; i < rounds_; ++i)
{
- mp_int<A,T> base = rng(eng);
+ ApInt base = rng(eng);
+
+ base |= one; // test only odd bases
- base.set_least_significant_bit(); // test only odd bases
-
- const mp_int<A,T> tmp = modpow(base, p1, p, &ctx);
+ const ApInt tmp = modpow(base, p1, p, &ctx);
if (tmp != one)
return false; // definitely composite!
}
-
+
return true;
}
@@ -134,7 +129,7 @@
// The probability that a composite number is reported as prime
// is less than 1/(4**k) where k is the number of rounds
template<
- class Distribution = uniform_mp_int<>
+ class Distribution = uniform_integer<>
>
class primality_miller_rabin_test
{
@@ -156,8 +151,8 @@
{}
// p must be odd
- template<class Engine, class A, class T>
- bool operator()(Engine& e, const mp_int<A,T>& p) const;
+ template<class Engine, class ApInt>
+ bool operator()(Engine& e, const ApInt& p) const;
// return the recommended number of rounds for numbers of size 'bits'
// so that the probability of error is lower than 2^-96
@@ -182,10 +177,10 @@
template<class Distribution>
-template<class Engine, class A, class T>
+template<class Engine, class ApInt>
bool
primality_miller_rabin_test<Distribution>::operator()
- (Engine& eng, const mp_int<A,T>& p) const
+ (Engine& eng, const ApInt& p) const
{
assert(p.is_odd());
@@ -194,27 +189,27 @@
r = rounds_;
else
r = recommended_number_of_rounds(p.precision());
-
- mp_int<A,T> n = abs(p);
+
+ ApInt n = abs(p);
--n;
- const typename mp_int<A,T>::size_type s = n.count_lsb();
+ const typename ApInt::size_type s = n.count_trailing_zero_bits();
n >>= s; // p-1 / 2**s
- const typename mp_int<A,T>::digit_type one = 1;
- const mp_int<A,T> p_minus_one(p-one);
+ const typename ApInt::digit_type one = 1;
+ const ApInt p_minus_one(p - one);
distribution_type rng(one, p_minus_one);
- modpow_ctx<A,T> ctx;
+ modpow_ctx<ApInt> ctx;
for (unsigned int i = 0; i < r; ++i)
{
- const mp_int<A,T> base = rng(eng);
- mp_int<A,T> y = modpow(base, n, p, &ctx);
-
- for (typename mp_int<A,T>::size_type j = 0; j < s; ++j)
+ const ApInt base = rng(eng);
+ ApInt y = modpow(base, n, p, &ctx);
+
+ for (typename ApInt::size_type j = 0; j < s; ++j)
{
const bool b = (y != one) && (y != p_minus_one);
- y.sqr();
+ y *= y;
y %= p;
if (b && (y == one))
return false;
@@ -227,8 +222,8 @@
template<class Distribution>
unsigned int
-primality_miller_rabin_test<Distribution>::recommended_number_of_rounds(
- unsigned bits)
+primality_miller_rabin_test<Distribution>::
+recommended_number_of_rounds(unsigned bits)
{
int i;
@@ -246,8 +241,8 @@
-template<class A, class T, class PrimalityTest>
-inline bool is_prime(const mp_int<A,T>& x, PrimalityTest f = PrimalityTest())
+template<class ApInt, class PrimalityTest>
+inline bool is_prime(const ApInt& x, PrimalityTest f = PrimalityTest())
{
return f(x);
}
@@ -255,7 +250,7 @@
template<
class PrimalityTest,
- class Dist = uniform_mp_int_bits<>
+ class Dist = uniform_integer_bits<>
>
struct prime_generator
{
@@ -287,7 +282,7 @@
do
{
candidate = dist(eng);
- candidate.set_least_significant_bit(); // make odd
+ candidate |= typename result_type::digit_type(1); // make odd
} while (!is_prime(candidate, test_));
return candidate;
@@ -297,7 +292,7 @@
// A prime p is called safe if (p-1)/2 is also prime
template<
class PrimalityTest,
- class Dist = uniform_mp_int_bits<>
+ class Dist = uniform_integer_bits<>
>
struct safe_prime_generator
{
@@ -332,7 +327,7 @@
do
{
p = prime_gen(eng);
- p.multiply_by_2();
+ detail::multiplier<result_type>::multiply_by_2(p);
++p;
} while (!is_prime(p, test_));
// Catch extremely rare case, this occurs if the carry from ++p ripples
Modified: sandbox/mp_math/boost/mp_math/integer/random.hpp
==============================================================================
--- sandbox/mp_math/boost/mp_math/integer/random.hpp (original)
+++ sandbox/mp_math/boost/mp_math/integer/random.hpp 2009-06-22 15:50:42 EDT (Mon, 22 Jun 2009)
@@ -1,185 +1,185 @@
-// Copyright Kevin Sopp 2008.
+// Copyright Kevin Sopp 2008 - 2009.
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)
-/*#ifndef BOOST_MP_MATH_MP_INT_RANDOM_HPP
-#define BOOST_MP_MATH_MP_INT_RANDOM_HPP
+#ifndef BOOST_MP_MATH_INTEGER_RANDOM_HPP
+#define BOOST_MP_MATH_INTEGER_RANDOM_HPP
+
+#include <boost/random.hpp>
+#include <boost/mp_math/integer/integer_fwd.hpp>
namespace boost {
namespace mp_math {
-template<class A, class T>
-struct mp_int;
-
-*/
-
// this class is modeled after boost::uniform_int
// in fact it uses boost::uniform_int internally
-template<class MpInt = mp_int<> >
-struct uniform_mp_int
+template<class Integer = integer<> >
+struct uniform_integer
{
- typedef MpInt input_type;
- typedef MpInt result_type;
+ typedef Integer input_type;
+ typedef Integer result_type;
// is min() and max() known at compile time?
static const bool has_fixed_range = false;
- uniform_mp_int(const MpInt& min, const MpInt& max)
+ uniform_integer(const Integer& min, const Integer& max)
:
min_(min),
max_(max),
- d_(0, MpInt::digit_max)
+ d_(0, Integer::traits_type::max_digit_value)
{}
result_type min() const { return min_; }
result_type max() const { return max_; }
void reset() { d_.reset(); }
-
+
template<class Engine>
result_type operator()(Engine& e);
-
+
private:
- MpInt min_, max_;
- uniform_int<typename MpInt::digit_type> d_;
+ Integer min_, max_;
+ uniform_int<typename Integer::digit_type> d_;
};
-template<class MpInt>
-const bool uniform_mp_int<MpInt>::has_fixed_range;
+template<class Integer>
+const bool uniform_integer<Integer>::has_fixed_range;
-template<class MpInt>
+template<class Integer>
template<class Engine>
-typename uniform_mp_int<MpInt>::result_type
-uniform_mp_int<MpInt>::operator()(Engine& e)
+typename uniform_integer<Integer>::result_type
+uniform_integer<Integer>::operator()(Engine& e)
{
result_type tmp;
- tmp.grow_capacity(max_.size());
-
+ tmp.reserve(max_.size());
+
for (typename result_type::size_type i = 0; i < max_.size(); ++i)
tmp[i] = d_(e);
-
+
tmp.set_size(max_.size());
tmp.clamp();
-
+
if (tmp > max_)
- tmp %= max_;
+ tmp %= max_; // TODO tmp.truncate(max_.precision()), tmp -= max_!
return tmp;
}
-template<class MpInt = mp_int<> >
-struct uniform_mp_int_bits
+template<class Integer = integer<> >
+struct uniform_integer_bits
{
- typedef MpInt input_type;
- typedef MpInt result_type;
+ typedef Integer input_type;
+ typedef Integer result_type;
+ typedef typename Integer::size_type size_type;
static const bool has_fixed_range = false;
- explicit uniform_mp_int_bits(typename MpInt::size_type bits)
+ explicit uniform_integer_bits(size_type bits)
:
- d_(0, MpInt::digit_max),
+ d_(0, Integer::traits_type::max_digit_value),
bits_(bits)
{}
result_type min() const;
result_type max() const;
- typename MpInt::size_type precision() const { return bits_; }
+ size_type precision() const { return bits_; }
void reset() { d_.reset(); }
-
+
template<class Engine>
result_type operator()(Engine& e);
-
+
private:
- uniform_int<typename MpInt::digit_type> d_;
- typename MpInt::size_type bits_;
+ uniform_int<typename Integer::digit_type> d_;
+ size_type bits_;
};
-template<class MpInt>
-const bool uniform_mp_int_bits<MpInt>::has_fixed_range;
+template<class Integer>
+const bool uniform_integer_bits<Integer>::has_fixed_range;
-template<class MpInt>
+template<class Integer>
template<class Engine>
-typename uniform_mp_int_bits<MpInt>::result_type
-uniform_mp_int_bits<MpInt>::operator()(Engine& e)
+typename uniform_integer_bits<Integer>::result_type
+uniform_integer_bits<Integer>::operator()(Engine& e)
{
result_type tmp;
- const typename MpInt::size_type offset = bits_ / MpInt::valid_bits + 1;
+ const size_type offset = bits_ / Integer::traits_type::radix_bits + 1;
- tmp.grow_capacity(offset);
+ tmp.reserve(offset);
- for (typename result_type::size_type i = 0; i < offset; ++i)
+ for (size_type i = 0; i < offset; ++i)
tmp[i] = d_(e);
-
+
tmp.set_size(offset);
- const typename MpInt::digit_type mask =
- (~typename MpInt::digit_type(0))
- << (bits_ % MpInt::valid_bits);
+ const typename Integer::digit_type mask =
+ (~typename Integer::digit_type(0))
+ << (bits_ % Integer::traits_type::radix_bits);
tmp[offset-1] &= ~mask;
-
+
tmp.set_bit(bits_-1); // make exactly bits_ bits long
-
+ tmp.clamp_high_digit();
+
return tmp;
}
-template<class MpInt>
-typename uniform_mp_int_bits<MpInt>::result_type
-uniform_mp_int_bits<MpInt>::min() const
+template<class Integer>
+typename uniform_integer_bits<Integer>::result_type
+uniform_integer_bits<Integer>::min() const
{
result_type tmp;
-
- const typename MpInt::size_type offset =
- bits_ / MpInt::valid_bits + 1;
-
- tmp.grow_capacity(offset);
-
+
+ const size_type offset = bits_ / Integer::traits_type::radix_bits + 1;
+
+ tmp.reserve(offset);
+
std::memset(tmp.digits(), 0,
- offset * sizeof(typename MpInt::digit_type));
-
+ offset * sizeof(typename Integer::digit_type));
+
tmp.set_size(offset);
tmp.set_bit(bits_ - 1);
-
+ tmp.clamp_high_digit();
+
return tmp;
}
-template<class MpInt>
-typename uniform_mp_int_bits<MpInt>::result_type
-uniform_mp_int_bits<MpInt>::max() const
+template<class Integer>
+typename uniform_integer_bits<Integer>::result_type
+uniform_integer_bits<Integer>::max() const
{
result_type tmp;
- const typename MpInt::size_type offset =
- bits_ / MpInt::valid_bits + 1;
-
- tmp.grow_capacity(offset);
-
- for (typename result_type::size_type i = 0; i < offset; ++i)
- tmp[i] = MpInt::digit_max;
-
+ const typename Integer::size_type offset =
+ bits_ / Integer::traits_type::radix_bits + 1;
+
+ tmp.reserve(offset);
+
+ for (size_type i = 0; i < offset; ++i)
+ tmp[i] = Integer::traits_type::max_digit_value;
+
tmp.set_size(offset);
- const typename MpInt::digit_type mask =
- (~typename MpInt::digit_type(0))
- << (bits_ % MpInt::valid_bits);
+ const typename Integer::digit_type mask =
+ (~typename Integer::digit_type(0))
+ << (bits_ % Integer::traits_type::radix_bits);
tmp[offset-1] &= ~mask;
+ tmp.clamp_high_digit();
return tmp;
}
-/*
-} // namespace boost
-} // namespace mp_math
+}
+}
#endif
-*/
+
Deleted: sandbox/mp_math/libs/mp_math/test/unbounded/signed/traits.cpp
==============================================================================
--- sandbox/mp_math/libs/mp_math/test/unbounded/signed/traits.cpp 2009-06-22 15:50:42 EDT (Mon, 22 Jun 2009)
+++ (empty file)
@@ -1,39 +0,0 @@
-// Copyright Kevin Sopp 2008.
-// Distributed under the Boost Software License, Version 1.0.
-// (See accompanying file LICENSE_1_0.txt or copy at
-// http://www.boost.org/LICENSE_1_0.txt)
-
-#include <vector>
-#include <boost/test/unit_test.hpp>
-#include <boost/mp_math/mp_int.hpp>
-
-BOOST_AUTO_TEST_CASE(check_digit_type_and_word_type)
-{
- typedef boost::mp_math::mp_int<> mp_int_type;
-
- std::vector<int> x;
- x.push_back(std::numeric_limits<unsigned char>::digits);
- x.push_back(std::numeric_limits<unsigned short>::digits);
- x.push_back(std::numeric_limits<unsigned int>::digits);
- x.push_back(std::numeric_limits<unsigned long int>::digits);
- #ifdef BOOST_HAS_LONG_LONG
- x.push_back(std::numeric_limits<unsigned long long int>::digits);
- #endif
-
- const int word_type_digits = x.back();
-
- std::vector<int>::const_reverse_iterator it;
- for (it = x.rbegin(); it != x.rend(); ++it)
- {
- if (*it <= word_type_digits / 2)
- break;
- }
-
- const int digit_type_digits = *it;
-
- BOOST_CHECK_EQUAL(digit_type_digits,
- std::numeric_limits<mp_int_type::digit_type>::digits);
- BOOST_CHECK_EQUAL(word_type_digits,
- std::numeric_limits<mp_int_type::word_type>::digits);
-}
-
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