Initial check in of big integer library, v2010.04.30

R=tsepez@chromium.org

Review URL: https://codereview.chromium.org/773443004

1 files changed, 215 insertions, 0 deletions

diff --git a/third_party/bigint/BigInteger.hh b/third_party/bigint/BigInteger.hh
new file mode 100644
index 0000000000..cf6e91056f
--- /dev/null
+++ b/third_party/bigint/BigInteger.hh
@@ -0,0 +1,215 @@
+#ifndef BIGINTEGER_H
+#define BIGINTEGER_H
+
+#include "BigUnsigned.hh"
+
+/* A BigInteger object represents a signed integer of size limited only by
+ * available memory.  BigUnsigneds support most mathematical operators and can
+ * be converted to and from most primitive integer types.
+ *
+ * A BigInteger is just an aggregate of a BigUnsigned and a sign.  (It is no
+ * longer derived from BigUnsigned because that led to harmful implicit
+ * conversions.) */
+class BigInteger {
+
+public:
+	typedef BigUnsigned::Blk Blk;
+	typedef BigUnsigned::Index Index;
+	typedef BigUnsigned::CmpRes CmpRes;
+	static const CmpRes
+		less    = BigUnsigned::less   ,
+		equal   = BigUnsigned::equal  ,
+		greater = BigUnsigned::greater;
+	// Enumeration for the sign of a BigInteger.
+	enum Sign { negative = -1, zero = 0, positive = 1 };
+
+protected:
+	Sign sign;
+	BigUnsigned mag;
+
+public:
+	// Constructs zero.
+	BigInteger() : sign(zero), mag() {}
+
+	// Copy constructor
+	BigInteger(const BigInteger &x) : sign(x.sign), mag(x.mag) {};
+
+	// Assignment operator
+	void operator=(const BigInteger &x);
+
+	// Constructor that copies from a given array of blocks with a sign.
+	BigInteger(const Blk *b, Index blen, Sign s);
+
+	// Nonnegative constructor that copies from a given array of blocks.
+	BigInteger(const Blk *b, Index blen) : mag(b, blen) {
+		sign = mag.isZero() ? zero : positive;
+	}
+
+	// Constructor from a BigUnsigned and a sign
+	BigInteger(const BigUnsigned &x, Sign s);
+
+	// Nonnegative constructor from a BigUnsigned
+	BigInteger(const BigUnsigned &x) : mag(x) {
+		sign = mag.isZero() ? zero : positive;
+	}
+
+	// Constructors from primitive integer types
+	BigInteger(unsigned long  x);
+	BigInteger(         long  x);
+	BigInteger(unsigned int   x);
+	BigInteger(         int   x);
+	BigInteger(unsigned short x);
+	BigInteger(         short x);
+
+	/* Converters to primitive integer types
+	 * The implicit conversion operators caused trouble, so these are now
+	 * named. */
+	unsigned long  toUnsignedLong () const;
+	long           toLong         () const;
+	unsigned int   toUnsignedInt  () const;
+	int            toInt          () const;
+	unsigned short toUnsignedShort() const;
+	short          toShort        () const;
+protected:
+	// Helper
+	template <class X> X convertToUnsignedPrimitive() const;
+	template <class X, class UX> X convertToSignedPrimitive() const;
+public:
+
+	// ACCESSORS
+	Sign getSign() const { return sign; }
+	/* The client can't do any harm by holding a read-only reference to the
+	 * magnitude. */
+	const BigUnsigned &getMagnitude() const { return mag; }
+
+	// Some accessors that go through to the magnitude
+	Index getLength() const { return mag.getLength(); }
+	Index getCapacity() const { return mag.getCapacity(); }
+	Blk getBlock(Index i) const { return mag.getBlock(i); }
+	bool isZero() const { return sign == zero; } // A bit special
+
+	// COMPARISONS
+
+	// Compares this to x like Perl's <=>
+	CmpRes compareTo(const BigInteger &x) const;
+
+	// Ordinary comparison operators
+	bool operator ==(const BigInteger &x) const {
+		return sign == x.sign && mag == x.mag;
+	}
+	bool operator !=(const BigInteger &x) const { return !operator ==(x); };
+	bool operator < (const BigInteger &x) const { return compareTo(x) == less   ; }
+	bool operator <=(const BigInteger &x) const { return compareTo(x) != greater; }
+	bool operator >=(const BigInteger &x) const { return compareTo(x) != less   ; }
+	bool operator > (const BigInteger &x) const { return compareTo(x) == greater; }
+
+	// OPERATORS -- See the discussion in BigUnsigned.hh.
+	void add     (const BigInteger &a, const BigInteger &b);
+	void subtract(const BigInteger &a, const BigInteger &b);
+	void multiply(const BigInteger &a, const BigInteger &b);
+	/* See the comment on BigUnsigned::divideWithRemainder.  Semantics
+	 * differ from those of primitive integers when negatives and/or zeros
+	 * are involved. */
+	void divideWithRemainder(const BigInteger &b, BigInteger &q);
+	void negate(const BigInteger &a);
+	
+	/* Bitwise operators are not provided for BigIntegers.  Use
+	 * getMagnitude to get the magnitude and operate on that instead. */
+
+	BigInteger operator +(const BigInteger &x) const;
+	BigInteger operator -(const BigInteger &x) const;
+	BigInteger operator *(const BigInteger &x) const;
+	BigInteger operator /(const BigInteger &x) const;
+	BigInteger operator %(const BigInteger &x) const;
+	BigInteger operator -() const;
+
+	void operator +=(const BigInteger &x);
+	void operator -=(const BigInteger &x);
+	void operator *=(const BigInteger &x);
+	void operator /=(const BigInteger &x);
+	void operator %=(const BigInteger &x);
+	void flipSign();
+
+	// INCREMENT/DECREMENT OPERATORS
+	void operator ++(   );
+	void operator ++(int);
+	void operator --(   );
+	void operator --(int);
+};
+
+// NORMAL OPERATORS
+/* These create an object to hold the result and invoke
+ * the appropriate put-here operation on it, passing
+ * this and x.  The new object is then returned. */
+inline BigInteger BigInteger::operator +(const BigInteger &x) const {
+	BigInteger ans;
+	ans.add(*this, x);
+	return ans;
+}
+inline BigInteger BigInteger::operator -(const BigInteger &x) const {
+	BigInteger ans;
+	ans.subtract(*this, x);
+	return ans;
+}
+inline BigInteger BigInteger::operator *(const BigInteger &x) const {
+	BigInteger ans;
+	ans.multiply(*this, x);
+	return ans;
+}
+inline BigInteger BigInteger::operator /(const BigInteger &x) const {
+	if (x.isZero()) throw "BigInteger::operator /: division by zero";
+	BigInteger q, r;
+	r = *this;
+	r.divideWithRemainder(x, q);
+	return q;
+}
+inline BigInteger BigInteger::operator %(const BigInteger &x) const {
+	if (x.isZero()) throw "BigInteger::operator %: division by zero";
+	BigInteger q, r;
+	r = *this;
+	r.divideWithRemainder(x, q);
+	return r;
+}
+inline BigInteger BigInteger::operator -() const {
+	BigInteger ans;
+	ans.negate(*this);
+	return ans;
+}
+
+/*
+ * 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) {
+	add(*this, x);
+}
+inline void BigInteger::operator -=(const BigInteger &x) {
+	subtract(*this, x);
+}
+inline void BigInteger::operator *=(const BigInteger &x) {
+	multiply(*this, x);
+}
+inline void BigInteger::operator /=(const BigInteger &x) {
+	if (x.isZero()) throw "BigInteger::operator /=: division by zero";
+	/* The following technique is slightly faster than copying *this first
+	 * when x is large. */
+	BigInteger q;
+	divideWithRemainder(x, q);
+	// *this contains the remainder, but we overwrite it with the quotient.
+	*this = q;
+}
+inline void BigInteger::operator %=(const BigInteger &x) {
+	if (x.isZero()) throw "BigInteger::operator %=: division by zero";
+	BigInteger q;
+	// Mods *this by x.  Don't care about quotient left in q.
+	divideWithRemainder(x, q);
+}
+// This one is trivial
+inline void BigInteger::flipSign() {
+	sign = Sign(-sign);
+}
+
+#endif