From 8c16728a3d7689d8cc90028f5bc7cbf255b711d8 Mon Sep 17 00:00:00 2001 From: Matt McCutchen Date: Tue, 13 Feb 2007 15:49:57 -0500 Subject: [PATCH] Redo handling of aliased calls --> version 2007.02.13 --- BigInteger.cc | 38 +++++++++++++++---------- BigInteger.hh | 25 +++++++++-------- BigUnsigned.cc | 75 ++++++++++++++++++++++++++++++++++++-------------- BigUnsigned.hh | 45 +++++++++++++++--------------- ChangeLog | 4 +++ 5 files changed, 116 insertions(+), 71 deletions(-) diff --git a/BigInteger.cc b/BigInteger.cc index f70b021..ba49180 100644 --- a/BigInteger.cc +++ b/BigInteger.cc @@ -310,11 +310,18 @@ BigInteger::CmpRes BigInteger::compareTo(const BigInteger &x) const { // These do some messing around to determine the sign of the result, // then call one of BigUnsigned's put-heres. +// See remarks about aliased calls in BigUnsigned.cc . +#define DOTR_ALIASED(cond, op) \ + if (cond) { \ + BigInteger tmpThis; \ + tmpThis.op; \ + *this = tmpThis; \ + return; \ + } + // Addition void BigInteger::add(const BigInteger &a, const BigInteger &b) { - // Block unsafe calls - if (this == &a || this == &b) - throw "BigInteger::add: One of the arguments is the invoked object"; + DOTR_ALIASED(this == &a || this == &b, add(a, b)); // If one argument is zero, copy the other. if (a.sign == zero) operator =(b); @@ -351,9 +358,7 @@ void BigInteger::add(const BigInteger &a, const BigInteger &b) { void BigInteger::subtract(const BigInteger &a, const BigInteger &b) { // Notice that this routine is identical to BigInteger::add, // if one replaces b.sign by its opposite. - // Block unsafe calls - if (this == &a || this == &b) - throw "BigInteger::subtract: One of the arguments is the invoked object"; + DOTR_ALIASED(this == &a || this == &b, subtract(a, b)); // If a is zero, copy b and flip its sign. If b is zero, copy a. if (a.sign == zero) { BigUnsigned::operator =(b); @@ -392,9 +397,7 @@ void BigInteger::subtract(const BigInteger &a, const BigInteger &b) { // Multiplication void BigInteger::multiply(const BigInteger &a, const BigInteger &b) { - // Block unsafe calls - if (this == &a || this == &b) - throw "BigInteger::multiply: One of the arguments is the invoked object"; + DOTR_ALIASED(this == &a || this == &b, multiply(a, b)); // If one object is zero, copy zero and return. if (a.sign == zero || b.sign == zero) { sign = zero; @@ -431,9 +434,16 @@ void BigInteger::multiply(const BigInteger &a, const BigInteger &b) { * -4 -3 1 -1 */ void BigInteger::divideWithRemainder(const BigInteger &b, BigInteger &q) { - // Block unsafe calls - if (this == &b || this == &q || &b == &q) - throw "BigInteger::divideWithRemainder: One of the arguments is the invoked object"; + // Defend against aliased calls; + // same idea as in BigUnsigned::divideWithRemainder . + if (this == &q) + throw "BigInteger::divideWithRemainder: Cannot write quotient and remainder into the same variable"; + if (this == &b || &q == &b) { + BigInteger tmpB(b); + divideWithRemainder(tmpB, q); + return; + } + // Division by zero gives quotient 0 and remainder *this if (b.sign == zero) { q.len = 0; @@ -507,9 +517,7 @@ void BigInteger::divideWithRemainder(const BigInteger &b, BigInteger &q) { // Negation void BigInteger::negate(const BigInteger &a) { - // Block unsafe calls - if (this == &a) - throw "BigInteger::negate: The argument is the invoked object"; + DOTR_ALIASED(this == &a, negate(a)); // Copy a's magnitude BigUnsigned::operator =(a); // Copy the opposite of a.sign diff --git a/BigInteger.hh b/BigInteger.hh index c6bd908..7319168 100644 --- a/BigInteger.hh +++ b/BigInteger.hh @@ -92,7 +92,7 @@ class BigInteger : public BigUnsigned { // PUT-HERE OPERATIONS /* These store the result of the operation on the arguments into this. * a.add(b, c) is equivalent to, but faster than, a = b + c. - * Calls like a.operation(a, b) are unsafe and not allowed. */ + * See explanation of "put-here operations" in BigUnsigned.cc . */ public: void add (const BigInteger &a, const BigInteger &b); // Addition void subtract(const BigInteger &a, const BigInteger &b); // Subtraction @@ -103,17 +103,17 @@ class BigInteger : public BigUnsigned { * and these usually differ from the semantics of primitive-type * / and % when negatives and/or zeroes are involved. * Look in `BigInteger.cc' for details. + * `a.divideWithRemainder(b, a)' causes an exception: it doesn't make + * sense to write quotient and remainder into the same variable. */ void divideWithRemainder(const BigInteger &b, BigInteger &q); void divide(const BigInteger &a, const BigInteger &b) { - // Division, deprecated and provided for compatibility BigInteger a2(a); a2.divideWithRemainder(b, *this); // quotient now in *this // don't care about remainder left in a2 } void modulo(const BigInteger &a, const BigInteger &b) { - // Modular reduction, deprecated and provided for compatibility *this = a; BigInteger q; divideWithRemainder(b, q); @@ -196,20 +196,21 @@ inline BigInteger BigInteger::operator -() const { return ans; } -// ASSIGNMENT OPERATORS -// These create a copy of this, then invoke the appropriate -// put-here operation on this, passing the copy and x. +/* + * ASSIGNMENT OPERATORS + * + * Now the responsibility for making a temporary copy if necessary + * belongs to the put-here operations. See Assignment Operators in + * BigUnsigned.hh. + */ inline void BigInteger::operator +=(const BigInteger &x) { - BigInteger thisCopy(*this); - add(thisCopy, x); + add(*this, x); } inline void BigInteger::operator -=(const BigInteger &x) { - BigInteger thisCopy(*this); - subtract(thisCopy, x); + subtract(*this, x); } inline void BigInteger::operator *=(const BigInteger &x) { - BigInteger thisCopy(*this); - multiply(thisCopy, x); + multiply(*this, x); } inline void BigInteger::operator /=(const BigInteger &x) { // Updated for divideWithRemainder diff --git a/BigUnsigned.cc b/BigUnsigned.cc index ad96026..a68b8ac 100644 --- a/BigUnsigned.cc +++ b/BigUnsigned.cc @@ -218,11 +218,37 @@ BigUnsigned::CmpRes BigUnsigned::compareTo(const BigUnsigned &x) const { * See Section 4.3.1 of Knuth's ``The Art of Computer Programming''. */ +/* + * On most calls to put-here operations, it's safe to read the inputs little by + * little and write the outputs little by little. However, if one of the + * inputs is coming from the same variable into which the output is to be + * stored (an "aliased" call), we risk overwriting the input before we read it. + * In this case, we first compute the result into a temporary BigUnsigned + * variable and then copy it into the requested output variable *this. + * Each put-here operation uses the DOTR_ALIASED macro (Do The Right Thing on + * aliased calls) to generate code for this check. + * + * I adopted this approach on 2007.02.13 (see Assignment Operators in + * BigUnsigned.hh). Before then, put-here operations rejected aliased calls + * with an exception. I think doing the right thing is better. + * + * Some of the put-here operations can probably handle aliased calls safely + * without the extra copy because (for example) they process blocks strictly + * right-to-left. At some point I might determine which ones don't need the + * copy, but my reasoning would need to be verified very carefully. For now + * I'll leave in the copy. + */ +#define DOTR_ALIASED(cond, op) \ + if (cond) { \ + BigUnsigned tmpThis; \ + tmpThis.op; \ + *this = tmpThis; \ + return; \ + } + // Addition void BigUnsigned::add(const BigUnsigned &a, const BigUnsigned &b) { - // Block unsafe calls - if (this == &a || this == &b) - throw "BigUnsigned::add: One of the arguments is the invoked object"; + DOTR_ALIASED(this == &a || this == &b, add(a, b)); // If one argument is zero, copy the other. if (a.len == 0) { operator =(b); @@ -283,9 +309,7 @@ void BigUnsigned::add(const BigUnsigned &a, const BigUnsigned &b) { // Subtraction void BigUnsigned::subtract(const BigUnsigned &a, const BigUnsigned &b) { - // Block unsafe calls - if (this == &a || this == &b) - throw "BigUnsigned::subtract: One of the arguments is the invoked object"; + DOTR_ALIASED(this == &a || this == &b, subtract(a, b)); // If b is zero, copy a. If a is shorter than b, the result is negative. if (b.len == 0) { operator =(a); @@ -397,9 +421,7 @@ inline BigUnsigned::Blk getShiftedBlock(const BigUnsigned &num, // Multiplication void BigUnsigned::multiply(const BigUnsigned &a, const BigUnsigned &b) { - // Block unsafe calls - if (this == &a || this == &b) - throw "BigUnsigned::multiply: One of the arguments is the invoked object"; + DOTR_ALIASED(this == &a || this == &b, multiply(a, b)); // If either a or b is zero, set to zero. if (a.len == 0 || b.len == 0) { len = 0; @@ -483,11 +505,28 @@ void BigUnsigned::multiply(const BigUnsigned &a, const BigUnsigned &b) { * and provide outputs in the most convenient places so that no value ever needs * to be copied in its entirety. That way, the client can perform exactly the * copying it needs depending on where the inputs are and where it wants the output. +* A better name for this function might be "modWithQuotient", but I would rather +* not change the name now. */ void BigUnsigned::divideWithRemainder(const BigUnsigned &b, BigUnsigned &q) { - // Block unsafe calls - if (this == &b || &q == &b || this == &q) - throw "BigUnsigned::divideWithRemainder: Some two objects involved are the same"; + /* + * Defending against aliased calls is a bit tricky because we are + * writing to both *this and q. + * + * It would be silly to try to write quotient and remainder to the + * same variable. Rule that out right away. + */ + if (this == &q) + throw "BigUnsigned::divideWithRemainder: Cannot write quotient and remainder into the same variable"; + /* + * Now *this and q are separate, so the only concern is that b might be + * aliased to one of them. If so, use a temporary copy of b. + */ + if (this == &b || &q == &b) { + BigUnsigned tmpB(b); + divideWithRemainder(tmpB, q); + return; + } /* * Note that the mathematical definition of mod (I'm trusting Knuth) is somewhat @@ -684,9 +723,7 @@ void BigUnsigned::divideWithRemainder(const BigUnsigned &b, BigUnsigned &q) { // Bitwise and void BigUnsigned::bitAnd(const BigUnsigned &a, const BigUnsigned &b) { - // Block unsafe calls - if (this == &a || this == &b) - throw "BigUnsigned::bitAnd: One of the arguments is the invoked object"; + DOTR_ALIASED(this == &a || this == &b, bitAnd(a, b)); len = (a.len >= b.len) ? b.len : a.len; allocate(len); Index i; @@ -697,9 +734,7 @@ void BigUnsigned::bitAnd(const BigUnsigned &a, const BigUnsigned &b) { // Bitwise or void BigUnsigned::bitOr(const BigUnsigned &a, const BigUnsigned &b) { - // Block unsafe calls - if (this == &a || this == &b) - throw "BigUnsigned::bitOr: One of the arguments is the invoked object"; + DOTR_ALIASED(this == &a || this == &b, bitOr(a, b)); Index i; const BigUnsigned *a2, *b2; if (a.len >= b.len) { @@ -719,9 +754,7 @@ void BigUnsigned::bitOr(const BigUnsigned &a, const BigUnsigned &b) { // Bitwise xor void BigUnsigned::bitXor(const BigUnsigned &a, const BigUnsigned &b) { - // Block unsafe calls - if (this == &a || this == &b) - throw "BigUnsigned::bitXor: One of the arguments is the invoked object"; + DOTR_ALIASED(this == &a || this == &b, bitXor(a, b)); Index i; const BigUnsigned *a2, *b2; if (a.len >= b.len) { diff --git a/BigUnsigned.hh b/BigUnsigned.hh index 3e7aa10..1eb056f 100644 --- a/BigUnsigned.hh +++ b/BigUnsigned.hh @@ -151,7 +151,8 @@ class BigUnsigned : protected NumberlikeArray { * c = a + b; // Now c == 50. * c.add(a, b); // Same effect but without the two bulk-copies. * c.divideWithRemainder(b, d); // 50 / 7; now d == 7 (quotient) and c == 1 (remainder). - * a.add(a, b); // Unsafe ``aliased'' call; causes a runtime error. + * a.add(a, b); // ``Aliased'' calls now do the right thing using a + * // temporary copy, but see note on divideWithRemainder. */ // PUT-HERE OPERATIONS @@ -166,17 +167,17 @@ class BigUnsigned : protected NumberlikeArray { * and these differ from the semantics of primitive-type * / and % under division by zero. * Look in `BigUnsigned.cc' for details. + * `a.divideWithRemainder(b, a)' causes an exception: it doesn't make + * sense to write quotient and remainder into the same variable. */ void divideWithRemainder(const BigUnsigned &b, BigUnsigned &q); void divide(const BigUnsigned &a, const BigUnsigned &b) { - // Division, deprecated and provided for backward compatibility BigUnsigned a2(a); a2.divideWithRemainder(b, *this); // quotient now in *this // don't care about remainder left in a2 } void modulo(const BigUnsigned &a, const BigUnsigned &b) { - // Modular reduction, deprecated and provided for backward compatibility *this = a; BigUnsigned q; divideWithRemainder(b, q); @@ -190,10 +191,9 @@ class BigUnsigned : protected NumberlikeArray { void bitOr(const BigUnsigned &a, const BigUnsigned &b); // Bitwise OR void bitXor(const BigUnsigned &a, const BigUnsigned &b); // Bitwise XOR - // These functions are declared but not defined. (Sorry.) - // Trying to call either will result in a link-time error. - void bitShiftLeft(const BigUnsigned &a, unsigned int b); // Bitwise left shift - void bitShiftRight(const BigUnsigned &a, unsigned int b); // Bitwise right shift + // These functions might exist someday. + //void bitShiftLeft(const BigUnsigned &a, unsigned int b); // Bitwise left shift + //void bitShiftRight(const BigUnsigned &a, unsigned int b); // Bitwise right shift // NORMAL OPERATORS // These perform the operation on this (to the left of the operator) @@ -278,21 +278,23 @@ inline BigUnsigned BigUnsigned::operator ^(const BigUnsigned &x) const { return ans; } -// ASSIGNMENT OPERATORS -// These create a copy of this, then invoke the appropriate -// put-here operation on this, passing the copy and x. -// Exception: those updated for divideWithRemainder. +/* + * ASSIGNMENT OPERATORS + * + * Now the responsibility for making a temporary copy if necessary + * belongs to the put-here operations. I made this change on 2007.02.13 after + * Boris Dessy pointed out that the old implementation handled calls like + * "a *= a" badly: it translated them to essentially "a.multiply(aCopy, a)", + * which threw an exception. + */ inline void BigUnsigned::operator +=(const BigUnsigned &x) { - BigUnsigned thisCopy(*this); - add(thisCopy, x); + add(*this, x); } inline void BigUnsigned::operator -=(const BigUnsigned &x) { - BigUnsigned thisCopy(*this); - subtract(thisCopy, x); + subtract(*this, x); } inline void BigUnsigned::operator *=(const BigUnsigned &x) { - BigUnsigned thisCopy(*this); - multiply(thisCopy, x); + multiply(*this, x); } inline void BigUnsigned::operator /=(const BigUnsigned &x) { // Updated for divideWithRemainder @@ -309,16 +311,13 @@ inline void BigUnsigned::operator %=(const BigUnsigned &x) { // don't care about quotient left in q } inline void BigUnsigned::operator &=(const BigUnsigned &x) { - BigUnsigned thisCopy(*this); - bitAnd(thisCopy, x); + bitAnd(*this, x); } inline void BigUnsigned::operator |=(const BigUnsigned &x) { - BigUnsigned thisCopy(*this); - bitOr(thisCopy, x); + bitOr(*this, x); } inline void BigUnsigned::operator ^=(const BigUnsigned &x) { - BigUnsigned thisCopy(*this); - bitXor(thisCopy, x); + bitXor(*this, x); } #endif diff --git a/ChangeLog b/ChangeLog index 45e36b0..b31813c 100644 --- a/ChangeLog +++ b/ChangeLog @@ -5,6 +5,10 @@ Change Log ========== These entries tell you what was added, fixed, or improved in each version as compared to the previous one. In case you haven't noticed, a version number roughly corresponds to the release date of that version in `YYYY.MM.DD[.N]' format, where `.N' goes `.2', `.3', etc. if there are multiple versions on the same day. +2007.02.13 +---------- +Boris Dessy pointed out that the library threw an exception on "a *= a", so I changed all the put-here operations to handle aliased calls correctly using a temporary copy instead of throwing exceptions. + 2006.08.14 ---------- In BigUnsigned::bitXor, change allocate(b2->len) to allocate(a2->len): we should allocate enough space for the longer number, not the shorter one! Thanks to Sriram Sankararaman for pointing this out. -- 2.34.1