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