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.) */
19 class BigInteger {
20
21 public:
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
32 protected:
33 Sign sign;
34 BigUnsigned mag;
35
36 public:
37 // Constructs zero.
BigInteger()38 BigInteger() : sign(zero), mag() {}
39
40 // Copy constructor
BigInteger(const BigInteger & x)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.
BigInteger(const Blk * b,Index blen)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
BigInteger(const BigUnsigned & x)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;
79 protected:
80 // Helper
81 template <class X> X convertToUnsignedPrimitive() const;
82 template <class X, class UX> X convertToSignedPrimitive() const;
83 public:
84
85 // ACCESSORS
getSign() const86 Sign getSign() const { return sign; }
87 /* The client can't do any harm by holding a read-only reference to the
88 * magnitude. */
getMagnitude() const89 const BigUnsigned &getMagnitude() const { return mag; }
90
91 // Some accessors that go through to the magnitude
getLength() const92 Index getLength() const { return mag.getLength(); }
getCapacity() const93 Index getCapacity() const { return mag.getCapacity(); }
getBlock(Index i) const94 Blk getBlock(Index i) const { return mag.getBlock(i); }
isZero() const95 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
operator ==(const BigInteger & x) const103 bool operator ==(const BigInteger &x) const {
104 return sign == x.sign && mag == x.mag;
105 }
operator !=(const BigInteger & x) const106 bool operator !=(const BigInteger &x) const { return !operator ==(x); };
operator <(const BigInteger & x) const107 bool operator < (const BigInteger &x) const { return compareTo(x) == less ; }
operator <=(const BigInteger & x) const108 bool operator <=(const BigInteger &x) const { return compareTo(x) != greater; }
operator >=(const BigInteger & x) const109 bool operator >=(const BigInteger &x) const { return compareTo(x) != less ; }
operator >(const BigInteger & x) const110 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. */
operator +(const BigInteger & x) const150 inline BigInteger BigInteger::operator +(const BigInteger &x) const {
151 BigInteger ans;
152 ans.add(*this, x);
153 return ans;
154 }
operator -(const BigInteger & x) const155 inline BigInteger BigInteger::operator -(const BigInteger &x) const {
156 BigInteger ans;
157 ans.subtract(*this, x);
158 return ans;
159 }
operator *(const BigInteger & x) const160 inline BigInteger BigInteger::operator *(const BigInteger &x) const {
161 BigInteger ans;
162 ans.multiply(*this, x);
163 return ans;
164 }
operator /(const BigInteger & x) const165 inline 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 }
operator %(const BigInteger & x) const173 inline 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 }
operator -() const181 inline 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 */
operator +=(const BigInteger & x)194 inline void BigInteger::operator +=(const BigInteger &x) {
195 add(*this, x);
196 }
operator -=(const BigInteger & x)197 inline void BigInteger::operator -=(const BigInteger &x) {
198 subtract(*this, x);
199 }
operator *=(const BigInteger & x)200 inline void BigInteger::operator *=(const BigInteger &x) {
201 multiply(*this, x);
202 }
operator /=(const BigInteger & x)203 inline 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 }
operator %=(const BigInteger & x)213 inline 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
flipSign()221 inline void BigInteger::flipSign() {
222 sign = Sign(-sign);
223 }
224
225 #endif
226