Boost logo

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