// 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);
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);
// 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;
* -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;
// 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
// 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
* 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);
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
* 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);
// 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);
// 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;
* 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
// 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;
// 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) {
// 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) {
* 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
* 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);
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)
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
// 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
==========
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.
Matt McCutchen's Web Site / bigint / bigint.git / commitdiff