Subject: [Boost-commit] svn:boost r60963 - sandbox/xint/boost/xint/src
From: pbristow_at_[hidden]
Date: 2010-03-31 09:25:58
Author: pbristow
Date: 2010-03-31 09:25:56 EDT (Wed, 31 Mar 2010)
New Revision: 60963
URL: http://svn.boost.org/trac/boost/changeset/60963
Log:
Chad updates from xint2.zip
Text files modified:
sandbox/xint/boost/xint/src/compare.cpp | 6
sandbox/xint/boost/xint/src/data_t.cpp | 27 ++--
sandbox/xint/boost/xint/src/gcd.cpp | 10 +
sandbox/xint/boost/xint/src/integer.cpp | 18 +-
sandbox/xint/boost/xint/src/modular.cpp | 8
sandbox/xint/boost/xint/src/monty.cpp | 8
sandbox/xint/boost/xint/src/operators.cpp | 24 ++-
sandbox/xint/boost/xint/src/powers.cpp | 8
sandbox/xint/boost/xint/src/primes.cpp | 2
sandbox/xint/boost/xint/src/primitives.cpp | 75 +++++-------
sandbox/xint/boost/xint/src/random.cpp | 234 ++++++++++++++++++---------------------
sandbox/xint/boost/xint/src/roots.cpp | 7 +
12 files changed, 207 insertions(+), 220 deletions(-)
Modified: sandbox/xint/boost/xint/src/compare.cpp
==============================================================================
--- sandbox/xint/boost/xint/src/compare.cpp (original)
+++ sandbox/xint/boost/xint/src/compare.cpp 2010-03-31 09:25:56 EDT (Wed, 31 Mar 2010)
@@ -38,7 +38,7 @@
if (b1data->mLength != b2data->mLength) {
answer=((b1data->mLength < b2data->mLength) ? -1 : 1);
} else {
- for (int x = b1data->mLength - 1; x >= 0; --x) {
+ for (int x = int(b1data->mLength) - 1; x >= 0; --x) {
if (b1data->digits[x] != b2data->digits[x]) {
answer=((b1data->digits[x] < b2data->digits[x]) ? -1 : 1);
break;
@@ -49,8 +49,6 @@
return answer;
}
-} // namespace xint
-
bool operator!(const xint::integer &num1) { return num1.sign()==0; }
bool operator==(const xint::integer &num1, const xint::integer &num2) { return xint::compare(num1, num2)==0; }
bool operator!=(const xint::integer& num1, const xint::integer& num2) { return xint::compare(num1, num2)!=0; }
@@ -58,3 +56,5 @@
bool operator>(const xint::integer& num1, const xint::integer& num2) { return xint::compare(num1, num2)>0; }
bool operator<=(const xint::integer& num1, const xint::integer& num2) { return xint::compare(num1, num2)<=0; }
bool operator>=(const xint::integer& num1, const xint::integer& num2) { return xint::compare(num1, num2)>=0; }
+
+} // namespace xint
Modified: sandbox/xint/boost/xint/src/data_t.cpp
==============================================================================
--- sandbox/xint/boost/xint/src/data_t.cpp (original)
+++ sandbox/xint/boost/xint/src/data_t.cpp 2010-03-31 09:25:56 EDT (Wed, 31 Mar 2010)
@@ -45,7 +45,7 @@
digits=&mStorage[0];
#endif
} catch (std::bad_alloc&) {
- throw std::overflow_error("Out of memory allocating xint::integer");
+ throw xint::overflow_error("Out of memory allocating xint::integer");
}
}
memcpy(digits, c->digits, mLength*sizeof(digit_t));
@@ -82,7 +82,7 @@
skipLeadingZeros();
}
-void data_t::alloc(int newcount, bool copydigits) {
+void data_t::alloc(size_t newcount, bool copydigits) {
if (digits==mQuickDigits && newcount<=QuickDigits::count) {
if (!copydigits) zero(digits, QuickDigits::count);
else zero(digits+mLength, (newcount-mLength));
@@ -112,7 +112,7 @@
#endif
} catch (std::bad_alloc&) {
digits=mQuickDigits; // Might allow for recovery in some cases
- throw std::overflow_error("Out of memory allocating xint::integer");
+ throw xint::overflow_error("Out of memory allocating xint::integer");
}
memcpy(digits, mQuickDigits, mLength*sizeof(digit_t));
@@ -123,7 +123,7 @@
try {
newDigits=new digit_t[newcount];
} catch (std::bad_alloc&) {
- throw std::overflow_error("Out of memory allocating xint::integer");
+ throw xint::overflow_error("Out of memory allocating xint::integer");
}
if (copydigits) {
@@ -140,7 +140,7 @@
try {
mStorage.resize(newcount);
} catch (std::bad_alloc&) {
- throw std::overflow_error("Out of memory allocating xint::integer");
+ throw xint::overflow_error("Out of memory allocating xint::integer");
}
digits=&mStorage[0];
if (!copydigits) zero(digits, newcount);
@@ -150,7 +150,7 @@
}
}
-void data_t::copy(const data_t *c, int extraDigits) {
+void data_t::copy(const data_t *c, size_t extraDigits) {
alloc(c->mLength+extraDigits);
mLength=c->mLength;
@@ -205,7 +205,7 @@
// Now add the digits, starting at the least-significant digit.
digit_t carry=0;
- int x=0;
+ size_t x=0;
for (; x<addend.mLength; ++x) {
doubledigit_t t=doubledigit_t(digits[x])+addend.digits[x]+carry;
if (t>=digit_overflowbit) { carry=1; t-=digit_overflowbit; } else carry=0;
@@ -230,7 +230,8 @@
// size of the longest operand, so we've already got enough room.
// Now subtract the digits, starting at the least-significant one.
- int borrow=0, x;
+ size_t x;
+ int borrow=0;
doubledigit_t t;
for (x=0; x<subtrahend.mLength; ++x) {
t=(digits[x]+digit_overflowbit)-subtrahend.digits[x]-borrow;
@@ -248,12 +249,12 @@
skipLeadingZeros();
}
-void data_t::shift_left(int byBits) {
+void data_t::shift_left(size_t byBits) {
assert(mCopies==1);
assert(byBits>0);
- int bytes=byBits / bits_per_digit, bits=byBits % bits_per_digit;
- int oldLength=mLength;
+ size_t bytes=byBits / bits_per_digit, bits=byBits % bits_per_digit;
+ size_t oldLength=mLength;
realloc(mLength+bytes+1);
@@ -276,11 +277,11 @@
skipLeadingZeros();
}
-void data_t::shift_right(int byBits) {
+void data_t::shift_right(size_t byBits) {
assert(mCopies==1);
assert(byBits>0);
- int bytes=byBits / bits_per_digit, bits=byBits % bits_per_digit,
+ size_t bytes=byBits / bits_per_digit, bits=byBits % bits_per_digit,
bits2 = bits_per_digit - bits;
if (bytes >= mLength) {
Modified: sandbox/xint/boost/xint/src/gcd.cpp
==============================================================================
--- sandbox/xint/boost/xint/src/gcd.cpp (original)
+++ sandbox/xint/boost/xint/src/gcd.cpp 2010-03-31 09:25:56 EDT (Wed, 31 Mar 2010)
@@ -55,6 +55,11 @@
num1._throw_if_nan();
num2._throw_if_nan();
+ int sign1=num1.sign(), sign2=num2.sign();
+ if (sign1==0 && sign2==0) return integer::zero();
+ else if (sign1==0) return num2;
+ else if (sign2==0) return num1;
+
integer n(abs(num1)), m(abs(num2));
size_t k=0;
@@ -79,7 +84,10 @@
else return integer(not_a_number());
}
- if (n.sign() < 0) {
+ int sign=n.sign();
+ if (sign==0) {
+ return integer(not_a_number());
+ } else if (n.sign() < 0) {
integer _n(n);
_n._set_negative(false);
Modified: sandbox/xint/boost/xint/src/integer.cpp
==============================================================================
--- sandbox/xint/boost/xint/src/integer.cpp (original)
+++ sandbox/xint/boost/xint/src/integer.cpp 2010-03-31 09:25:56 EDT (Wed, 31 Mar 2010)
@@ -14,6 +14,10 @@
#include "../xint.hpp"
#include "../xint_data_t.hpp"
+#ifdef XINT_THREADSAFE
+ #define XINT_DISABLE_COPY_ON_WRITE
+#endif
+
namespace xint {
const integer *integer::cZero=0, *integer::cOne=0;
@@ -44,14 +48,14 @@
try {
data=new detail::data_t(init);
} catch (std::bad_alloc&) {
- throw std::overflow_error("Out of memory allocating xint::integer");
+ throw xint::overflow_error("Out of memory allocating xint::integer");
}
_attach();
}
void integer::_init(const integer &c) {
- #ifdef XINT_THREADSAFE
- data=(c.data ? new data_t(c.data) : 0);
+ #ifdef XINT_DISABLE_COPY_ON_WRITE
+ data=(c.data ? new detail::data_t(c.data) : 0);
#else
data=c.data;
#endif
@@ -65,7 +69,7 @@
try {
data=new detail::data_t;
} catch (std::bad_alloc&) {
- throw std::overflow_error("Out of memory allocating xint::integer");
+ throw xint::overflow_error("Out of memory allocating xint::integer");
}
_attach();
@@ -94,7 +98,7 @@
_attach();
}
} catch (std::bad_alloc&) {
- throw std::overflow_error("Out of memory allocating xint::integer");
+ throw xint::overflow_error("Out of memory allocating xint::integer");
}
}
@@ -157,8 +161,8 @@
integer& integer::operator=(const integer &c) {
_detach();
- #ifdef XINT_THREADSAFE
- data=(c.data ? new data_t(c.data) : 0);
+ #ifdef XINT_DISABLE_COPY_ON_WRITE
+ data=(c.data ? new detail::data_t(c.data) : 0);
#else
data=c.data;
#endif
Modified: sandbox/xint/boost/xint/src/modular.cpp
==============================================================================
--- sandbox/xint/boost/xint/src/modular.cpp (original)
+++ sandbox/xint/boost/xint/src/modular.cpp 2010-03-31 09:25:56 EDT (Wed, 31 Mar 2010)
@@ -51,15 +51,15 @@
} else {
integer p(abs(n));
- int length=exponent._get_length(), lastBitCount=0;
+ size_t length=exponent._get_length(), lastBitCount=0;
detail::digit_t ee(exponent._get_digit(length-1));
while (ee != 0) { ee >>= 1; ++lastBitCount; }
- for (int eIndex=0; eIndex < length; ++eIndex) {
+ for (size_t eIndex=0; eIndex < length; ++eIndex) {
detail::digit_t e(exponent._get_digit(eIndex));
- int bitCount(eIndex == length-1 ? lastBitCount :
- detail::bits_per_digit);
+ int bitCount(int(eIndex == length-1 ? lastBitCount :
+ detail::bits_per_digit));
while (bitCount-- > 0) {
if (e & 0x01) answer=mulmod(answer, p, modulus);
p=sqrmod(p, modulus);
Modified: sandbox/xint/boost/xint/src/monty.cpp
==============================================================================
--- sandbox/xint/boost/xint/src/monty.cpp (original)
+++ sandbox/xint/boost/xint/src/monty.cpp 2010-03-31 09:25:56 EDT (Wed, 31 Mar 2010)
@@ -84,10 +84,10 @@
// nPrime0 is nPrime mod B, or digit zero of nPrime
const integer B(digit_overflowbit);
- const int L(n._get_length()), L1(L-1);
+ const size_t L(n._get_length()), L1(L-1);
integer t=a*b;
- int i=0;
+ size_t i=0;
do {
digit_t mi=digit_t(doubledigit_t(t._get_digit(i))*nPrime0);
@@ -166,7 +166,7 @@
integer aa=a*r%n, aSquared=a*a%n;
vxint_t rval;
- rval.reserve(ddPowerOfTwo(k));
+ rval.reserve(size_t(ddPowerOfTwo(k)));
rval.push_back(integer::one()); // Anything to the zeroth power is one
rval.push_back(aa); // Anything to the first power is itself
@@ -253,7 +253,7 @@
} else {
std::pair<int, int> tu=tuTable[i];
- int s=k-tu.first;
+ size_t s=k-tu.first;
while (s-- > 0) pp=montgomeryMultiplyMod(pp, pp, n, nPrime0);
pp=montgomeryMultiplyMod(pp, oddPowersOfAa[tu.second], n, nPrime0);
Modified: sandbox/xint/boost/xint/src/operators.cpp
==============================================================================
--- sandbox/xint/boost/xint/src/operators.cpp (original)
+++ sandbox/xint/boost/xint/src/operators.cpp 2010-03-31 09:25:56 EDT (Wed, 31 Mar 2010)
@@ -13,13 +13,17 @@
#include "../xint.hpp"
-const xint::integer& operator+(const xint::integer& a) { return a; }
-xint::integer operator-(const xint::integer& a) { return xint::negate(a); }
-xint::integer operator+(const xint::integer& num1, const xint::integer& num2) { return xint::add(num1, num2); }
-xint::integer operator-(const xint::integer& num1, const xint::integer& num2) { return xint::subtract(num1, num2); }
-xint::integer operator*(const xint::integer& num1, const xint::integer& num2) { return xint::multiply(num1, num2); }
-xint::integer operator/(const xint::integer& num1, const xint::integer& num2) { return xint::divide(num1, num2); }
-xint::integer operator%(const xint::integer& num1, const xint::integer& num2) { return xint::mod(num1, num2); }
-xint::integer operator&(const xint::integer& n1, const xint::integer& n2) { return xint::bitwise_and(n1, n2); }
-xint::integer operator|(const xint::integer& n1, const xint::integer& n2) { return xint::bitwise_or(n1, n2); }
-xint::integer operator^(const xint::integer& n1, const xint::integer& n2) { return xint::bitwise_xor(n1, n2); }
+namespace xint {
+
+const integer& operator+(const integer& a) { return a; }
+integer operator-(const integer& a) { return negate(a); }
+integer operator+(const integer& num1, const integer& num2) { return add(num1, num2); }
+integer operator-(const integer& num1, const integer& num2) { return subtract(num1, num2); }
+integer operator*(const integer& num1, const integer& num2) { return multiply(num1, num2); }
+integer operator/(const integer& num1, const integer& num2) { return divide(num1, num2); }
+integer operator%(const integer& num1, const integer& num2) { return mod(num1, num2); }
+integer operator&(const integer& n1, const integer& n2) { return bitwise_and(n1, n2); }
+integer operator|(const integer& n1, const integer& n2) { return bitwise_or(n1, n2); }
+integer operator^(const integer& n1, const integer& n2) { return bitwise_xor(n1, n2); }
+
+} // namespace xint
Modified: sandbox/xint/boost/xint/src/powers.cpp
==============================================================================
--- sandbox/xint/boost/xint/src/powers.cpp (original)
+++ sandbox/xint/boost/xint/src/powers.cpp 2010-03-31 09:25:56 EDT (Wed, 31 Mar 2010)
@@ -46,7 +46,7 @@
std::vector<doubledigit_t> a(ndata->mLength*2+1, 0);
doubledigit_t *adigit=&a[0];
- int i, j;
+ size_t i, j;
integer addend;
data_t *addenddata=addend._get_data();
addenddata->alloc(ndata->mLength*2+1);
@@ -86,15 +86,15 @@
integer pow(const integer& n, const integer& exponent) {
bool neg=(n.sign() < 0 && exponent.odd());
- int length=exponent._get_length(), lastBitCount=0;
+ size_t length=exponent._get_length(), lastBitCount=0;
digit_t ee(exponent._get_digit(length-1));
while (ee != 0) { ee >>= 1; ++lastBitCount; }
integer p(abs(n)), answer=integer::one();
- for (int eIndex=0; eIndex < length; ++eIndex) {
+ for (size_t eIndex=0; eIndex < length; ++eIndex) {
digit_t e(exponent._get_digit(eIndex));
- int bitCount(eIndex == length-1 ? lastBitCount : bits_per_digit);
+ int bitCount(int(eIndex == length-1 ? lastBitCount : bits_per_digit));
while (bitCount-- > 0) {
if (e & 0x01) answer*=p;
p=sqr(p);
Modified: sandbox/xint/boost/xint/src/primes.cpp
==============================================================================
--- sandbox/xint/boost/xint/src/primes.cpp (original)
+++ sandbox/xint/boost/xint/src/primes.cpp 2010-03-31 09:25:56 EDT (Wed, 31 Mar 2010)
@@ -87,7 +87,7 @@
// Run the number through the Miller-Rabin Probabilistic Test of Primality
// a few times to see if it's actually (probably) prime.
for (int count=0; count<5; ++count) {
- int k=random<int>();
+ unsigned int k=detail::get_random();
int isP=isProbablePrimeBaseB(n, abs(k), callback);
if (isP <= 0) return isP;
}
Modified: sandbox/xint/boost/xint/src/primitives.cpp
==============================================================================
--- sandbox/xint/boost/xint/src/primitives.cpp (original)
+++ sandbox/xint/boost/xint/src/primitives.cpp 2010-03-31 09:25:56 EDT (Wed, 31 Mar 2010)
@@ -33,58 +33,45 @@
}
integer add(const integer& n1, const integer& n2) {
- if (n1.sign()==0) return n2;
- if (n2.sign()==0) return n1;
-
- bool swapped=false;
- const data_t *n1data=n1._get_data(), *n2data=n2._get_data();
- if (n1data->mLength < n2data->mLength) { swapped=true; std::swap(n1data, n2data); }
-
- integer r;
- data_t *rdata=r._get_data();
- rdata->copy(n1data, 1);
-
- if (n1.sign() != n2.sign()) {
- int level=n2data->mLength;
-
- integer _n2(swapped ? n1 : n2);
- _n2._make_unique();
- _n2._get_data()->invert();
-
- rdata->add(_n2._get_data());
-
- if (rdata->mLength > level) {
- --rdata->digits[level];
- rdata->skipLeadingZeros();
- } else rdata->invert();
+ int sign1=n1.sign(), sign2=n2.sign();
+ if (sign1 != sign2) {
+ if (sign1==0) return n2;
+ else if (sign2==0) return n1;
+ else return subtract(n1, -n2);
} else {
+ const data_t *n1data=n1._get_data(), *n2data=n2._get_data();
+ if (n1data->mLength < n2data->mLength) std::swap(n1data, n2data);
+
+ integer r;
+ data_t *rdata=r._get_data();
+ rdata->copy(n1data, 1);
rdata->add(*n2data);
+ return r;
}
- return r;
}
integer subtract(const integer& n1, const integer& n2) {
- if ((n1.sign() < 0) != (n2.sign() < 0)) {
- return add(n1, -n2);
- } else if (n1.sign() < 0) {
- return -subtract(-n1, -n2);
- }
-
- // Signs are both guaranteed positive now.
-
- if (n1 < n2) {
- return -subtract(n2, n1);
+ int sign1=n1.sign(), sign2=n2.sign();
+ if (sign1 != sign2) {
+ if (sign1 == 0) return -n2;
+ else if (sign2 == 0) return n1;
+ else return add(n1, -n2);
} else {
+ bool invert=(sign1 == (n1 < n2 ? 1 : -1));
+ const data_t *n1data=n1._get_data(), *n2data=n2._get_data();
+ if (invert) std::swap(n1data, n2data);
+
integer r;
data_t *rdata=r._get_data();
- rdata->copy(n1._get_data());
- rdata->subtract(*n2._get_data());
- return r;
+ rdata->copy(n1data);
+ rdata->subtract(*n2data);
+ return (invert ? -r : r);
}
}
integer multiply(const integer& n, const integer& by) {
- if (n.sign()==0 || by.sign()==0) return integer::zero();
+ int nsign=n.sign(), bysign=by.sign();
+ if (nsign==0 || bysign==0) return integer::zero();
const data_t *ndata=n._get_data(), *bydata=by._get_data();
if (ndata == bydata) return sqr(n);
@@ -123,7 +110,7 @@
}
}
- answer._set_negative(n.sign() != by.sign());
+ answer._set_negative(nsign != bysign);
answer._get_data()->skipLeadingZeros();
return answer;
}
@@ -142,7 +129,7 @@
const doubledigit_t lomask(digit_mask);
const doubledigit_t himask(doubledigit_t(digit_mask) << bits_per_digit);
- int m = d1data->mLength - 1;
+ int m = int(d1data->mLength) - 1;
const digit_t *d1p=d1data->digits+m;
digit_t *qp=qdata->digits+m;
for (int i = m; i >= 0; --i, --d1p, --qp) {
@@ -161,7 +148,7 @@
std::pair<integer, integer> subDivide(integer d1, integer d2) {
const data_t *ndata=d1._get_data(), *bydata=d2._get_data();
const digit_t *nDigits = ndata->digits, *byDigits = bydata->digits;
- int nMSD = ndata->mLength-1, byMSD = bydata->mLength-1;
+ size_t nMSD = ndata->mLength-1, byMSD = bydata->mLength-1;
// The normalization step
digit_t d = static_cast<digit_t>(digit_overflowbit /
@@ -186,7 +173,7 @@
// has the same number of digits as the divisor; if what remains is greater
// than the divisor, then we start there, otherwise that one's zero and we
// start on the next lower one.
- int highestQuotientDigit=(nMSD - byMSD);
+ size_t highestQuotientDigit=(nMSD - byMSD);
integer nTest(d1);
nTest -= integer::one();
nTest >>= (bits_per_digit * highestQuotientDigit);
@@ -196,7 +183,7 @@
data_t *qdata=quotient._get_data();
qdata->alloc(highestQuotientDigit + 1);
- for (int j = highestQuotientDigit; j >= 0; --j) {
+ for (int j = int(highestQuotientDigit); j >= 0; --j) {
doubledigit_t q = (nDigits[nMSD] > byDigits[byMSD] ?
doubledigit_t(nDigits[nMSD]) / byDigits[byMSD] :
((doubledigit_t(nDigits[nMSD]) << bits_per_digit) +
Modified: sandbox/xint/boost/xint/src/random.cpp
==============================================================================
--- sandbox/xint/boost/xint/src/random.cpp (original)
+++ sandbox/xint/boost/xint/src/random.cpp 2010-03-31 09:25:56 EDT (Wed, 31 Mar 2010)
@@ -17,8 +17,7 @@
#include <vector>
#include <sstream>
#include <fstream>
-
-#include <boost/crc.hpp>
+#include <ctime>
#include <boost/random/mersenne_twister.hpp>
#ifdef XINT_THREADSAFE
@@ -40,10 +39,9 @@
namespace {
class generator_t {
- typedef boost::mt19937 internal_generator_t;
-
public:
- typedef internal_generator_t::result_type result_type;
+ typedef base_random_generator::result_type result_type;
+ typedef boost::mt19937 default_random_t;
#ifdef XINT_THREADSAFE
generator_t() { mLock.lock(); init(); }
@@ -52,166 +50,152 @@
generator_t() { init(); }
#endif
- void seed_manual(const std::string& bytes);
- bool seed_secure();
- void seed_fallback();
- result_type operator()();
+ result_type operator()() { return mGeneratorFn(); }
+
+ static void set_generator(random_t g, base_random_generator *p) {
+ mGeneratorObj.reset(p);
+ mGeneratorFn=g;
+ }
private:
- class SeedGenerator {
- public:
- SeedGenerator(const std::string& seedstring): mString(seedstring.substr(0,
- cSeedMaximumBytes)), mNumber(0) { }
- internal_generator_t::result_type operator()() {
- std::ostringstream s1;
- s1 << mNumber++ << mString;
- std::string s2=s1.str();
-
- boost::crc_32_type crc;
- crc.process_bytes(s2.c_str(), s2.length());
- return crc.checksum();
+ void init() {
+ if (!mGeneratorFn) {
+ typedef default_random_t T;
+ mDefaultGenerator.reset(new T(boost::uint32_t(time(0)+clock())));
+ random_generator<T> *obj=new random_generator<T>(*mDefaultGenerator);
+ set_generator(*obj, obj);
}
+ }
- #ifdef XINT_SECURE
- static char zero(char) { return 0; }
-
- ~SeedGenerator() {
- mNumber=0;
- std::transform(mString.begin(), mString.end(), mString.begin(),
- zero);
- }
- #endif
-
- private:
- static const size_t cSeedMaximumBytes=4096;
-
- std::string mString;
- int mNumber;
- };
-
- void init();
-
- static internal_generator_t *mGen;
- static bool mSeeded;
+ static random_t mGeneratorFn;
+ static std::auto_ptr<base_random_generator> mGeneratorObj;
+ static std::auto_ptr<default_random_t> mDefaultGenerator;
#ifdef XINT_THREADSAFE
static boost::mutex mLock;
#endif
};
-generator_t::internal_generator_t *generator_t::mGen=0;
-bool generator_t::mSeeded=false;
+std::auto_ptr<base_random_generator> generator_t::mGeneratorObj;
+std::auto_ptr<generator_t::default_random_t> generator_t::mDefaultGenerator;
+random_t generator_t::mGeneratorFn;
#ifdef XINT_THREADSAFE
boost::mutex generator_t::mLock;
#endif
-void generator_t::seed_manual(const std::string& bytes) {
- SeedGenerator gen(bytes);
- mGen->seed(gen);
- mSeeded=true;
+} // namespace
+
+namespace detail {
+
+void set_random_generator(random_t fn, base_random_generator *obj) {
+ generator_t::set_generator(fn, obj);
+}
+
+unsigned int get_random() {
+ generator_t gen;
+ return gen();
}
-bool generator_t::seed_secure() {
- const int cBitsRequested=256,
- cBytesRequested=cBitsRequested / std::numeric_limits<char>::digits;
- bool success=false;
-
- #ifdef _WIN32
- // This should work under WinXP, Vista, and Win7. No guarantees about
- // future compatibility, but I doubt that Microsoft will get rid of it
- // (it's too useful), and I doubt that they'll change it now that it's
- // well-known (it would break too many programs). We could also use the
- // rand_s function in more recent versions of Visual C++, but that
- // causes compatibility problems with older versions of Windows.
+} // namespace detail
+
+////////////////////////////////////////////////////////////////////////////////
+// The secure random generator
+
+#ifdef _WIN32
+ struct strong_random_generator::impl_t {
typedef BOOLEAN (WINAPI *RtlGenRandomFn)(PVOID, ULONG);
- HMODULE dll=LoadLibrary(_T("Advapi32.dll"));
- if (dll != 0) {
- RtlGenRandomFn RtlGenRandom=RtlGenRandomFn(GetProcAddress(dll,
- "SystemFunction036"));
- if (RtlGenRandom != 0) {
- std::vector<char> buffer(cBytesRequested, '\0');
- if (RtlGenRandom(&buffer[0], cBytesRequested)) {
- char *c=&buffer[0];
- seed_manual(std::string(c, c+cBytesRequested));
- success=true;
- }
+ typedef DWORD result_type;
+
+ impl_t(): dll(0), fn(0) {
+ // This should work under WinXP, Vista, and Win7. No guarantees about
+ // future compatibility, but I doubt that Microsoft will get rid of it
+ // (it's too useful), and I doubt that they'll change it now that it's
+ // well-known (it would break too many programs). We could also use the
+ // rand_s function in more recent versions of Visual C++, but that
+ // causes compatibility problems with older versions of Windows.
+ dll=LoadLibrary(_T("Advapi32.dll"));
+ if (dll != 0) fn=RtlGenRandomFn(GetProcAddress(dll, "SystemFunction036"));
+ if (fn == 0) {
+ destroy();
+ throw no_strong_random();
}
- FreeLibrary(dll);
- }
- #else
- // This should be supported under most non-Windows systems. Note that
- // we're using /dev/urandom, not /dev/random -- /dev/random is more
- // secure, but it can be VERY slow.
- std::ifstream rng("/dev/urandom");
- if (rng) {
- std::string rstr;
- for (int i=0; i < cBytesRequested; ++i)
- rstr.push_back(rng.get());
- seed_manual(rstr);
- success=true;
}
- #endif
- return success;
-}
+ ~impl_t() { destroy(); }
-void generator_t::seed_fallback() {
- // No cryptographically-secure device available. Fall back onto the
- // system clock. It's not much, but it's portable, fast, and will
- // provide at least a *little* entropy.
- std::ostringstream out;
- out << time(0) << clock();
- seed_manual(out.str());
-}
+ result_type operator()() {
+ result_type r=0;
+ if (!fn(&r, sizeof(result_type)))
+ throw no_strong_random("RtlGenRandom failed");
+ return r;
+ }
-generator_t::result_type generator_t::operator()() {
- if (!mSeeded)
- if (!seed_secure())
- seed_fallback();
- return (*mGen)();
-}
+ void destroy() { if (dll) FreeLibrary(dll); }
-void generator_t::init() {
- if (!mGen) mGen=new internal_generator_t();
-}
+ HMODULE dll;
+ RtlGenRandomFn fn;
+ };
-} // namespace
+ double strong_random_generator::entropy() const { return 32; }
+#else
+ struct strong_random_generator::impl_t {
+ typedef unsigned char result_type;
+
+ impl_t(): rng("/dev/urandom", std::ios::binary) {
+ // This should be supported under most non-Windows systems. Note
+ // that we're using /dev/urandom, not /dev/random -- /dev/random is
+ // more secure, but it can be VERY slow.
+ if (!rng) throw no_strong_random();
+ }
-bool seed_secure() {
- generator_t gen;
- return gen.seed_secure();
-}
+ result_type operator()() {
+ int r=rng.get();
+ if (r==EOF) throw no_strong_random("/dev/urandom returned EOF");
+ return static_cast<result_type>(r);
+ }
-void seed_fallback() {
- generator_t gen;
- gen.seed_fallback();
-}
+ std::ifstream rng;
+ };
-void seed_manual(const std::string& value) {
- generator_t gen;
- gen.seed_manual(value);
-}
+ double strong_random_generator::entropy() const { return 8; }
+#endif
+
+const bool strong_random_generator::has_fixed_range = true;
+const strong_random_generator::result_type strong_random_generator::min_value =
+ (std::numeric_limits<impl_t::result_type>::min)();
+const strong_random_generator::result_type strong_random_generator::max_value =
+ (std::numeric_limits<impl_t::result_type>::max)();
+strong_random_generator::strong_random_generator(): impl(new impl_t) { }
+strong_random_generator::~strong_random_generator() { delete impl; }
+strong_random_generator::result_type strong_random_generator::operator()() {
+ return (*impl)(); }
+strong_random_generator::result_type strong_random_generator::min
+ BOOST_PREVENT_MACRO_SUBSTITUTION () const { return min_value; }
+strong_random_generator::result_type strong_random_generator::max
+ BOOST_PREVENT_MACRO_SUBSTITUTION () const { return max_value; }
+////////////////////////////////////////////////////////////////////////////////
// Returns a positive (unless told otherwise) integer between zero and
// (1<<bits)-1, inclusive
-integer random_by_size(size_t bits, bool highBitOn, bool lowBitOn, bool canBeNegative) {
+integer random_by_size(size_t bits, bool highBitOn, bool lowBitOn, bool
+ canBeNegative)
+{
if (bits<=0) return integer::zero();
generator_t randomGenerator;
-
const size_t cBitsPerIteration=std::numeric_limits<generator_t::result_type>::digits;
// Grab a set of random bits, of at least the specified size
- int iterations = (bits+cBitsPerIteration-1) / cBitsPerIteration;
+ size_t iterations = (bits+cBitsPerIteration-1) / cBitsPerIteration;
std::vector<generator_t::result_type> v;
- for (int i=0; i<iterations; ++i) v.push_back(randomGenerator());
+ for (size_t i=0; i<iterations; ++i) v.push_back(randomGenerator());
const char *vptr=(const char *)&v[0], *vptr_end=vptr+(v.size() * sizeof(generator_t::result_type));
integer p=from_binary(std::string(vptr, vptr_end));
// Trim it to the proper length
- int index=(bits/bits_per_digit);
+ size_t index=(bits/bits_per_digit);
digit_t mask=(digit_t(1) << (bits % bits_per_digit))-1;
if (mask==0) { mask=digit_mask; --index; }
p._get_data()->digits[index] &= mask;
@@ -226,10 +210,4 @@
return p;
}
-template <>
-integer random<integer>(const integer& lowest, const integer& highest) {
- integer range(abs(highest-lowest+1));
- return lowest+(random_by_size(log2(range)) % range);
-}
-
} // namespace xint
Modified: sandbox/xint/boost/xint/src/roots.cpp
==============================================================================
--- sandbox/xint/boost/xint/src/roots.cpp (original)
+++ sandbox/xint/boost/xint/src/roots.cpp 2010-03-31 09:25:56 EDT (Wed, 31 Mar 2010)
@@ -17,7 +17,12 @@
namespace xint {
integer sqrt(const integer& n) {
- if (n.sign() <= 0) return integer::zero();
+ if (n.sign() < 0) {
+ if (exceptions_allowed()) throw cannot_represent("library cannot "
+ "represent imaginary values (tried to take sqrt of negative "
+ "number)");
+ else return integer(not_a_number());
+ } else if (n.sign() == 0) return integer::zero();
// Initial guess is half the length of n, in bits
integer guess;