1// Copyright 2014 PDFium Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4
5// Original code by Matt McCutchen, see the LICENSE file.
6
7#ifndef BIGINTEGER_H
8#define BIGINTEGER_H
9
10#include "BigUnsigned.hh"
11
12/* A BigInteger object represents a signed integer of size limited only by
13 * available memory.  BigUnsigneds support most mathematical operators and can
14 * be converted to and from most primitive integer types.
15 *
16 * A BigInteger is just an aggregate of a BigUnsigned and a sign.  (It is no
17 * longer derived from BigUnsigned because that led to harmful implicit
18 * conversions.) */
19class BigInteger {
20
21public:
22	typedef BigUnsigned::Blk Blk;
23	typedef BigUnsigned::Index Index;
24	typedef BigUnsigned::CmpRes CmpRes;
25	static const CmpRes
26		less    = BigUnsigned::less   ,
27		equal   = BigUnsigned::equal  ,
28		greater = BigUnsigned::greater;
29	// Enumeration for the sign of a BigInteger.
30	enum Sign { negative = -1, zero = 0, positive = 1 };
31
32protected:
33	Sign sign;
34	BigUnsigned mag;
35
36public:
37	// Constructs zero.
38	BigInteger() : sign(zero), mag() {}
39
40	// Copy constructor
41	BigInteger(const BigInteger &x) : sign(x.sign), mag(x.mag) {};
42
43	// Assignment operator
44	void operator=(const BigInteger &x);
45
46	// Constructor that copies from a given array of blocks with a sign.
47	BigInteger(const Blk *b, Index blen, Sign s);
48
49	// Nonnegative constructor that copies from a given array of blocks.
50	BigInteger(const Blk *b, Index blen) : mag(b, blen) {
51		sign = mag.isZero() ? zero : positive;
52	}
53
54	// Constructor from a BigUnsigned and a sign
55	BigInteger(const BigUnsigned &x, Sign s);
56
57	// Nonnegative constructor from a BigUnsigned
58	BigInteger(const BigUnsigned &x) : mag(x) {
59		sign = mag.isZero() ? zero : positive;
60	}
61
62	// Constructors from primitive integer types
63	BigInteger(unsigned long  x);
64	BigInteger(         long  x);
65	BigInteger(unsigned int   x);
66	BigInteger(         int   x);
67	BigInteger(unsigned short x);
68	BigInteger(         short x);
69
70	/* Converters to primitive integer types
71	 * The implicit conversion operators caused trouble, so these are now
72	 * named. */
73	unsigned long  toUnsignedLong () const;
74	long           toLong         () const;
75	unsigned int   toUnsignedInt  () const;
76	int            toInt          () const;
77	unsigned short toUnsignedShort() const;
78	short          toShort        () const;
79protected:
80	// Helper
81	template <class X> X convertToUnsignedPrimitive() const;
82	template <class X, class UX> X convertToSignedPrimitive() const;
83public:
84
85	// ACCESSORS
86	Sign getSign() const { return sign; }
87	/* The client can't do any harm by holding a read-only reference to the
88	 * magnitude. */
89	const BigUnsigned &getMagnitude() const { return mag; }
90
91	// Some accessors that go through to the magnitude
92	Index getLength() const { return mag.getLength(); }
93	Index getCapacity() const { return mag.getCapacity(); }
94	Blk getBlock(Index i) const { return mag.getBlock(i); }
95	bool isZero() const { return sign == zero; } // A bit special
96
97	// COMPARISONS
98
99	// Compares this to x like Perl's <=>
100	CmpRes compareTo(const BigInteger &x) const;
101
102	// Ordinary comparison operators
103	bool operator ==(const BigInteger &x) const {
104		return sign == x.sign && mag == x.mag;
105	}
106	bool operator !=(const BigInteger &x) const { return !operator ==(x); };
107	bool operator < (const BigInteger &x) const { return compareTo(x) == less   ; }
108	bool operator <=(const BigInteger &x) const { return compareTo(x) != greater; }
109	bool operator >=(const BigInteger &x) const { return compareTo(x) != less   ; }
110	bool operator > (const BigInteger &x) const { return compareTo(x) == greater; }
111
112	// OPERATORS -- See the discussion in BigUnsigned.hh.
113	void add     (const BigInteger &a, const BigInteger &b);
114	void subtract(const BigInteger &a, const BigInteger &b);
115	void multiply(const BigInteger &a, const BigInteger &b);
116	/* See the comment on BigUnsigned::divideWithRemainder.  Semantics
117	 * differ from those of primitive integers when negatives and/or zeros
118	 * are involved. */
119	void divideWithRemainder(const BigInteger &b, BigInteger &q);
120	void negate(const BigInteger &a);
121
122	/* Bitwise operators are not provided for BigIntegers.  Use
123	 * getMagnitude to get the magnitude and operate on that instead. */
124
125	BigInteger operator +(const BigInteger &x) const;
126	BigInteger operator -(const BigInteger &x) const;
127	BigInteger operator *(const BigInteger &x) const;
128	BigInteger operator /(const BigInteger &x) const;
129	BigInteger operator %(const BigInteger &x) const;
130	BigInteger operator -() const;
131
132	void operator +=(const BigInteger &x);
133	void operator -=(const BigInteger &x);
134	void operator *=(const BigInteger &x);
135	void operator /=(const BigInteger &x);
136	void operator %=(const BigInteger &x);
137	void flipSign();
138
139	// INCREMENT/DECREMENT OPERATORS
140	void operator ++(   );
141	void operator ++(int);
142	void operator --(   );
143	void operator --(int);
144};
145
146// NORMAL OPERATORS
147/* These create an object to hold the result and invoke
148 * the appropriate put-here operation on it, passing
149 * this and x.  The new object is then returned. */
150inline BigInteger BigInteger::operator +(const BigInteger &x) const {
151	BigInteger ans;
152	ans.add(*this, x);
153	return ans;
154}
155inline BigInteger BigInteger::operator -(const BigInteger &x) const {
156	BigInteger ans;
157	ans.subtract(*this, x);
158	return ans;
159}
160inline BigInteger BigInteger::operator *(const BigInteger &x) const {
161	BigInteger ans;
162	ans.multiply(*this, x);
163	return ans;
164}
165inline BigInteger BigInteger::operator /(const BigInteger &x) const {
166	if (x.isZero())
167        abort();
168	BigInteger q, r;
169	r = *this;
170	r.divideWithRemainder(x, q);
171	return q;
172}
173inline BigInteger BigInteger::operator %(const BigInteger &x) const {
174	if (x.isZero())
175        abort();
176	BigInteger q, r;
177	r = *this;
178	r.divideWithRemainder(x, q);
179	return r;
180}
181inline BigInteger BigInteger::operator -() const {
182	BigInteger ans;
183	ans.negate(*this);
184	return ans;
185}
186
187/*
188 * ASSIGNMENT OPERATORS
189 *
190 * Now the responsibility for making a temporary copy if necessary
191 * belongs to the put-here operations.  See Assignment Operators in
192 * BigUnsigned.hh.
193 */
194inline void BigInteger::operator +=(const BigInteger &x) {
195	add(*this, x);
196}
197inline void BigInteger::operator -=(const BigInteger &x) {
198	subtract(*this, x);
199}
200inline void BigInteger::operator *=(const BigInteger &x) {
201	multiply(*this, x);
202}
203inline void BigInteger::operator /=(const BigInteger &x) {
204	if (x.isZero())
205        abort();
206	/* The following technique is slightly faster than copying *this first
207	 * when x is large. */
208	BigInteger q;
209	divideWithRemainder(x, q);
210	// *this contains the remainder, but we overwrite it with the quotient.
211	*this = q;
212}
213inline void BigInteger::operator %=(const BigInteger &x) {
214	if (x.isZero())
215        abort();
216	BigInteger q;
217	// Mods *this by x.  Don't care about quotient left in q.
218	divideWithRemainder(x, q);
219}
220// This one is trivial
221inline void BigInteger::flipSign() {
222	sign = Sign(-sign);
223}
224
225#endif
226