From 2f145f11d5d5ab979a7f5a5e3b26fc9882dc345c Mon Sep 17 00:00:00 2001 From: Matt McCutchen Date: Sat, 27 Jan 2007 16:06:13 -0500 Subject: [PATCH] Old snapshot `BigIntegerLibrary-2005.01.06.devel.bounds-checking'; see the ChangeLog file. --- BigInteger.cc | 74 +++++++++++++++++++++---------------------- BigUnsigned.cc | 59 ++++++++++++++++++++++++---------- BigUnsignedInABase.cc | 18 ++++++++--- NumberlikeArray.hh | 72 +++++++++++++++++++++++++++++++++-------- sample.cc | 14 ++++++++ 5 files changed, 165 insertions(+), 72 deletions(-) diff --git a/BigInteger.cc b/BigInteger.cc index 15173b1..471d056 100644 --- a/BigInteger.cc +++ b/BigInteger.cc @@ -67,26 +67,26 @@ BigInteger::BigInteger(unsigned long x) { sign = zero; // NumberlikeArray did the rest else { cap = 1; - blk = new Blk[1]; + blk2 = new Blk[1]; sign = positive; len = 1; - *blk = Blk(x); + blk[0] = Blk(x); } } BigInteger::BigInteger(long x) { if (x > 0) { cap = 1; - blk = new Blk[1]; + blk2 = new Blk[1]; sign = positive; len = 1; - *blk = Blk(x); + blk[0] = Blk(x); } else if (x < 0) { cap = 1; - blk = new Blk[1]; + blk2 = new Blk[1]; sign = negative; len = 1; - *blk = Blk(-x); + blk[0] = Blk(-x); } else sign = zero; } @@ -96,26 +96,26 @@ BigInteger::BigInteger(unsigned int x) { sign = zero; else { cap = 1; - blk = new Blk[1]; + blk2 = new Blk[1]; sign = positive; len = 1; - *blk = Blk(x); + blk[0] = Blk(x); } } BigInteger::BigInteger(int x) { if (x > 0) { cap = 1; - blk = new Blk[1]; + blk2 = new Blk[1]; sign = positive; len = 1; - *blk = Blk(x); + blk[0] = Blk(x); } else if (x < 0) { cap = 1; - blk = new Blk[1]; + blk2 = new Blk[1]; sign = negative; len = 1; - *blk = Blk(-x); + blk[0] = Blk(-x); } else sign = zero; } @@ -125,26 +125,26 @@ BigInteger::BigInteger(unsigned short x) { sign = zero; else { cap = 1; - blk = new Blk[1]; + blk2 = new Blk[1]; sign = positive; len = 1; - *blk = Blk(x); + blk[0] = Blk(x); } } BigInteger::BigInteger(short x) { if (x > 0) { cap = 1; - blk = new Blk[1]; + blk2 = new Blk[1]; sign = positive; len = 1; - *blk = Blk(x); + blk[0] = Blk(x); } else if (x < 0) { cap = 1; - blk = new Blk[1]; + blk2 = new Blk[1]; sign = negative; len = 1; - *blk = Blk(-x); + blk[0] = Blk(-x); } else sign = zero; } @@ -186,7 +186,7 @@ BigInteger::operator unsigned long() const { return 0; case positive: if (len == 1) - return *blk; + return blk[0]; else throw "BigInteger operator unsigned long() const: Value is too big for an unsigned long"; case negative: @@ -201,13 +201,13 @@ BigInteger::operator long() const { case zero: return 0; case positive: - if (len == 1 && (*blk & ~lMask) == 0) - return long(*blk); + if (len == 1 && (blk[0] & ~lMask) == 0) + return long(blk[0]); else throw "BigInteger operator long() const: Value is too big for a long"; case negative: - if (len == 1 && (*blk & ~lMask) == 0) - return -long(*blk); + if (len == 1 && (blk[0] & ~lMask) == 0) + return -long(blk[0]); else throw "BigInteger operator long() const: Value is too big for a long"; default: @@ -220,8 +220,8 @@ BigInteger::operator unsigned int() const { case zero: return 0; case positive: - if (len == 1 && (*blk & ~uiMask) == 0) - return (unsigned int)(*blk); + if (len == 1 && (blk[0] & ~uiMask) == 0) + return (unsigned int)(blk[0]); else throw "BigInteger operator unsigned int() const: Value is too big for an unsigned int"; case negative: @@ -236,13 +236,13 @@ BigInteger::operator int() const { case zero: return 0; case positive: - if (len == 1 && (*blk & ~iMask) == 0) - return int(*blk); + if (len == 1 && (blk[0] & ~iMask) == 0) + return int(blk[0]); else throw "BigInteger operator int() const: Value is too big for an int"; case negative: - if (len == 1 && (*blk & ~iMask) == 0) - return -int(*blk); + if (len == 1 && (blk[0] & ~iMask) == 0) + return -int(blk[0]); else throw "BigInteger operator int() const: Value is too big for an int"; default: @@ -255,8 +255,8 @@ BigInteger::operator unsigned short() const { case zero: return 0; case positive: - if (len == 1 && (*blk & ~usMask) == 0) - return (unsigned short)(*blk); + if (len == 1 && (blk[0] & ~usMask) == 0) + return (unsigned short)(blk[0]); else throw "BigInteger operator unsigned short() const: Value is too big for an unsigned short"; case negative: @@ -271,13 +271,13 @@ BigInteger::operator short() const { case zero: return 0; case positive: - if (len == 1 && (*blk & ~sMask) == 0) - return short(*blk); + if (len == 1 && (blk[0] & ~sMask) == 0) + return short(blk[0]); else throw "BigInteger operator short() const: Value is too big for a short"; case negative: - if (len == 1 && (*blk & ~sMask) == 0) - return -short(*blk); + if (len == 1 && (blk[0] & ~sMask) == 0) + return -short(blk[0]); else throw "BigInteger operator short() const: Value is too big for a short"; default: @@ -524,7 +524,7 @@ void BigInteger::operator ++() { allocate(1); sign = positive; len = 1; - *blk = 1; + blk[0] = 1; break; case positive: BigUnsigned::operator ++(); @@ -549,7 +549,7 @@ void BigInteger::operator --() { allocate(1); sign = negative; len = 1; - *blk = 1; + blk[0] = 1; break; case negative: BigUnsigned::operator ++(); diff --git a/BigUnsigned.cc b/BigUnsigned.cc index 712db98..2a61477 100644 --- a/BigUnsigned.cc +++ b/BigUnsigned.cc @@ -20,7 +20,7 @@ * Since 2005.01.06, NumberlikeArray uses `NULL' rather * than a real array if one of zero length is needed. * These constructors implicitly call NumberlikeArray's -* default constructor, which sets `blk = NULL, cap = len = 0'. +* default constructor, which sets `blk2 = NULL, cap = len = 0'. * So if the input number is zero, they can just return. * See remarks in `NumberlikeArray.hh'. */ @@ -30,7 +30,7 @@ BigUnsigned::BigUnsigned(unsigned long x) { ; // NumberlikeArray already did all the work else { cap = 1; - blk = new Blk[1]; + blk2 = new Blk[1]; len = 1; blk[0] = Blk(x); } @@ -41,7 +41,7 @@ BigUnsigned::BigUnsigned(long x) { ; else if (x > 0) { cap = 1; - blk = new Blk[1]; + blk2 = new Blk[1]; len = 1; blk[0] = Blk(x); } else @@ -53,7 +53,7 @@ BigUnsigned::BigUnsigned(unsigned int x) { ; else { cap = 1; - blk = new Blk[1]; + blk2 = new Blk[1]; len = 1; blk[0] = Blk(x); } @@ -64,7 +64,7 @@ BigUnsigned::BigUnsigned(int x) { ; else if (x > 0) { cap = 1; - blk = new Blk[1]; + blk2 = new Blk[1]; len = 1; blk[0] = Blk(x); } else @@ -76,7 +76,7 @@ BigUnsigned::BigUnsigned(unsigned short x) { ; else { cap = 1; - blk = new Blk[1]; + blk2 = new Blk[1]; len = 1; blk[0] = Blk(x); } @@ -87,7 +87,7 @@ BigUnsigned::BigUnsigned(short x) { ; else if (x > 0) { cap = 1; - blk = new Blk[1]; + blk2 = new Blk[1]; len = 1; blk[0] = Blk(x); } else @@ -392,6 +392,14 @@ void BigUnsigned::divideWithRemainder(const BigUnsigned &b, BigUnsigned &q) { if (this == &b || &q == &b || this == &q) throw "BigUnsigned::divideWithRemainder: Some two objects involved are the same"; + /*std::cout << "((( divideWithRemainder\n[ Dumps:\n*this:\n"; + dump(); + std::cout << "b:\n"; + b.dump(); + std::cout << "q:\n"; + q.dump(); + std::cout << "]\n";*/ + /* * Note that the mathematical definition of mod (I'm trusting Knuth) is somewhat * different from the way the normal C++ % operator behaves in the case of division by 0. @@ -443,19 +451,28 @@ void BigUnsigned::divideWithRemainder(const BigUnsigned &b, BigUnsigned &q) { Blk bHigh, temp; bool borrowIn, borrowOut; - // Make sure we have an extra zero block just past the value, - // but don't increase the logical length. A shifted subtraction - // (for example, subtracting 1 << 2 from 4) might stick into - // this block. - allocateAndCopy(len + 1); - blk[len] = 0; + /* + * Make sure we have an extra zero block just past the value. + * A shifted subtraction (for example, subtracting 1 << 2 from 4) + * might stick into this block. + * + * In earlier versions, `len' was not increased. But then Milan Tomic + * found out-of-bounds memory accesses. In investigating the problem, + * I got tons of warnings in this routine, which I should have expected. + * I decided to make the extra block logically part of the number so it + * would not cause confusion in the future. + */ + Index origLen = len; // original length + len++; // increased to avoid memory management worries + allocateAndCopy(len); + blk[origLen] = 0; // work2 holds part of the result of a subtraction. // (There's no work1. The name work2 is from a previous version.) - Blk *work2 = new Blk[len]; + Blk *work2 = new Blk[origLen]; // Set preliminary length for quotient and make room - q.len = len - b.len + 1; + q.len = origLen - b.len + 1; q.allocate(q.len); // Zero out the quotient for (i = 0; i < q.len; i++) @@ -499,7 +516,7 @@ void BigUnsigned::divideWithRemainder(const BigUnsigned &b, BigUnsigned &q) { borrowIn = borrowOut; j++; k++; - for (; k < len && borrowIn; j++, k++) { + for (; k < origLen && borrowIn; j++, k++) { borrowIn = (blk[k] == 0); work2[j] = blk[k] - 1; } @@ -531,7 +548,15 @@ void BigUnsigned::divideWithRemainder(const BigUnsigned &b, BigUnsigned &q) { << "\nlast block of quotient: " << q.getBlock(0) << "\nlength of remainder: " << len << "\nlast block of remainder: " << getBlock(0) - << std::endl; */ + << std::endl; + + std::cout << "[ Dumps:\n*this:\n"; + dump(); + std::cout << "b:\n"; + b.dump(); + std::cout << "q:\n"; + q.dump(); + std::cout << "]\ndivideWithRemainder )))\n"; */ } // Bitwise and diff --git a/BigUnsignedInABase.cc b/BigUnsignedInABase.cc index a450cf0..8852575 100644 --- a/BigUnsignedInABase.cc +++ b/BigUnsignedInABase.cc @@ -13,6 +13,7 @@ */ #include "BigUnsignedInABase.hh" +#include namespace { unsigned int bitLen(unsigned int x) { @@ -27,8 +28,11 @@ namespace { return (a + b - 1) / b; } } - + /*std::cout << "((( BigUnsigned ==> BigUnsignedInABase\n"; + std::cout << "[ Parameter BigUnsigned @ " << (void *)(NumberlikeArray *)(&x) + << ",\nresulting BigUnsignedInABase @ " << (void *)(NumberlikeArray *)(this) << "]" << std::endl;*/ BigUnsignedInABase::BigUnsignedInABase(const BigUnsigned &x, Base base) { + // Check the base if (base < 2) throw "BigUnsignedInABase(BigUnsigned, Base): The base must be at least 2"; @@ -40,7 +44,8 @@ BigUnsignedInABase::BigUnsignedInABase(const BigUnsigned &x, Base base) { int maxBitLenOfX = x.getLength() * 8 * sizeof(BigUnsigned::Blk); int minBitsPerDigit = bitLen(base) - 1; int maxDigitLenOfX = ceilingDiv(maxBitLenOfX, minBitsPerDigit); - allocate(maxDigitLenOfX); // Get the space + len = maxDigitLenOfX; // Another change to comply with `staying in bounds'; see `BigUnsigned::divideWithRemainder'. + allocate(len); // Get the space BigUnsigned x2(x), buBase(base); Index digitNum = 0; @@ -55,8 +60,9 @@ BigUnsignedInABase::BigUnsignedInABase(const BigUnsigned &x, Base base) { digitNum++; } - // Save the eventual length. + // Save the actual length. len = digitNum; + /*std::cout << "BigUnsigned ==> BigUnsignedInABase )))\n";*/ } BigUnsignedInABase::operator BigUnsigned() const { @@ -98,6 +104,7 @@ BigUnsignedInABase::BigUnsignedInABase(const std::string &s, Base base) { } BigUnsignedInABase::operator std::string() const { + //std::cout << "((( BigUnsignedInABase ==> std::string\n"; if (base > 36) throw "BigUnsignedInABase ==> std::string: The default string conversion routines use the symbol set 0-9, A-Z and therefore support only up to base 36. You tried a conversion with a base over 36; write your own string conversion routine."; if (len == 0) @@ -113,5 +120,8 @@ BigUnsignedInABase::operator std::string() const { else s[symbolNumInString] = char('A' + theDigit - 10); } - return std::string(s); + std::string s2(s); + delete s; + //std::cout << "BigUnsignedInABase ==> std::string )))\n"; + return s2; } diff --git a/NumberlikeArray.hh b/NumberlikeArray.hh index 79d46df..4fe2a42 100644 --- a/NumberlikeArray.hh +++ b/NumberlikeArray.hh @@ -37,6 +37,9 @@ * NumberlikeArray< whatever >::getLength; */ +/*debug*/ +#include + template class NumberlikeArray { public: @@ -46,7 +49,45 @@ class NumberlikeArray { // FIELDS Index cap; // The current allocated capacity of this NumberlikeArray (in blocks) Index len; // The actual length of the value stored in this NumberlikeArray (in blocks) - Blk *blk; // Dynamically allocated array of the blocks + Blk *blk2; // Dynamically allocated array of the blocks + + static Blk x; // trash that [] can return for out-of-range requests + + void dump() const { + std::cout << "Dumping NumberlikeArray @ " << (void *)(this) << '\n'; + std::cout << "Length " << (len) << ", capacity " << (cap) << '\n'; + for (unsigned int i = 0; i < len; i++) { + std::cout << "Block " << i << ":" << blk2[i] << '\n'; + } + } + + struct BoundsCheckingBlk { + const NumberlikeArray *na; + BoundsCheckingBlk(NumberlikeArray *na) { + this->na = na; + } + Blk & operator [](Index index) const { + if (index >= na->len) { + std::cout << "== Out-of-bounds access to block " << index << ". Affected NumberlikeArray: ==\n"; + na->dump(); + std::cout << "== End of dump. ==" << std::endl; + return x; + } else + return na->blk2[index]; + } // dangerous because it allows ``always writable'', but OK for now + /*const Blk & operator [](Index index) const { + if (index >= na->len) + std::cout << "OUT OF BOUNDS! Length " << (na->len) << ", accessed " << index << std::endl; + else + return na->blk[index]; + }*/ + /*operator Blk * () { + return na->blk2; + }*/ + }; + + BoundsCheckingBlk blk; + /* * Change made on 2005.01.06: * @@ -62,8 +103,8 @@ class NumberlikeArray { */ // MANAGEMENT - NumberlikeArray(Index c) : cap(c), len(0) { // Creates a NumberlikeArray with a capacity - blk = (cap > 0) ? (new Blk[cap]) : NULL; + NumberlikeArray(Index c) : cap(c), len(0), blk(this) { // Creates a NumberlikeArray with a capacity + blk2 = (cap > 0) ? (new Blk[cap]) : NULL; } void allocate(Index c); // Ensures the array has at least the indicated capacity, maybe discarding contents void allocateAndCopy(Index c); // Ensures the array has at least the indicated capacity, preserving its contents @@ -86,14 +127,14 @@ class NumberlikeArray { * created a real `new'-allocated zero-length array. This array would then be lost, * causing a small but annoying memory leak. */ - NumberlikeArray() : cap(0), len(0) { - blk = NULL; + NumberlikeArray() : cap(0), len(0), blk(this) { + blk2 = NULL; } NumberlikeArray(const NumberlikeArray &x); // Copy constructor void operator=(const NumberlikeArray &x); // Assignment operator NumberlikeArray(const Blk *b, Index l); // Constructor from an array of blocks ~NumberlikeArray() { // Destructor - delete [] blk; // Does nothing and causes no error if `blk' is null. + delete [] blk2; // Does nothing and causes no error if `blk' is null. } // PICKING APART @@ -127,6 +168,9 @@ class NumberlikeArray { * so other files including NumberlikeArray will be able to generate real definitions. */ +template +Blk NumberlikeArray::x = 0; + // MANAGEMENT // This routine is called to ensure the array is at least a @@ -136,10 +180,10 @@ void NumberlikeArray::allocate(Index c) { // If the requested capacity is more than the current capacity... if (c > cap) { // Delete the old number array - delete [] blk; + delete [] blk2; // Allocate the new array cap = c; - blk = new Blk[cap]; + blk2 = new Blk[cap]; } } @@ -149,10 +193,10 @@ template void NumberlikeArray::allocateAndCopy(Index c) { // If the requested capacity is more than the current capacity... if (c > cap) { - Blk *oldBlk = blk; + Blk *oldBlk = blk2; // Allocate the new number array cap = c; - blk = new Blk[cap]; + blk2 = new Blk[cap]; // Copy number blocks Index i; for (i = 0; i < len; i++) @@ -164,10 +208,10 @@ void NumberlikeArray::allocateAndCopy(Index c) { // Copy constructor template -NumberlikeArray::NumberlikeArray(const NumberlikeArray &x) : len(x.len) { +NumberlikeArray::NumberlikeArray(const NumberlikeArray &x) : len(x.len), blk(this) { // Create array cap = len; - blk = new Blk[cap]; + blk2 = new Blk[cap]; // Copy blocks Index i; for (i = 0; i < len; i++) @@ -192,9 +236,9 @@ void NumberlikeArray::operator=(const NumberlikeArray &x) { // Constructor from an array of blocks template -NumberlikeArray::NumberlikeArray(const Blk *b, Index l) : cap(l), len(l) { +NumberlikeArray::NumberlikeArray(const Blk *b, Index l) : cap(l), len(l), blk(this) { // Create array - blk = new Blk[cap]; + blk2 = new Blk[cap]; // Copy blocks Index i; for (i = 0; i < len; i++) diff --git a/sample.cc b/sample.cc index 3779ef4..a9e4d46 100644 --- a/sample.cc +++ b/sample.cc @@ -42,20 +42,30 @@ int main() { BigInteger c(a); // Copy a BigInteger. + std::cout << "here 0" << std::endl; + BigInteger d(-314159265); // c is -314159265. The `int' literal is converted to a BigInteger. // Ahem: that's too big to be an `int' literal (or even a `long' literal)! // Disillusion yourself now -- this won't compile. //BigInteger e(3141592653589793238462643383279); + std::cout << "here 1" << std::endl; + std::string s("3141592653589793238462643383279"); BigInteger f = easyStringToBI(s); // Ah. The string is converted to a BigInteger, and strings can be as long as you want. + std::cout << "here 2" << std::endl; + std::string s2 = easyBItoString(f); // You can convert the other way too. + std::cout << "here 3" << std::endl; + std::cout << f << std::endl; // f is stringified and send to std::cout. + std::cout << "here 4" << std::endl; + /* * Let's do some math! * @@ -89,11 +99,15 @@ int main() { std::cout << (g + h) << '\n' << (g - h) << '\n' << (g * h) << '\n' << (g / h) << '\n' << (g % h) << std::endl; + std::cout << "here 5" << std::endl; + BigInteger i(5), j(10), k; // These two lines do the same thing: k is set to a BigInteger containing 15. k = i + j; k.add(i, j); + std::cout << "here 6" << std::endl; + // Let's do some heavy lifting. std::cout << "Powers of 3" << std::endl; std::cout << "How many do you want?" << std::endl; -- 2.34.1