Fix build broken at ac8fda05418b on windows
[pdfium.git] / third_party / bigint / BigInteger.hh
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.
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;
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
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. */
150 inline BigInteger BigInteger::operator +(const BigInteger &x) const {
151         BigInteger ans;
152         ans.add(*this, x);
153         return ans;
154 }
155 inline BigInteger BigInteger::operator -(const BigInteger &x) const {
156         BigInteger ans;
157         ans.subtract(*this, x);
158         return ans;
159 }
160 inline BigInteger BigInteger::operator *(const BigInteger &x) const {
161         BigInteger ans;
162         ans.multiply(*this, x);
163         return ans;
164 }
165 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 }
173 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 }
181 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  */
194 inline void BigInteger::operator +=(const BigInteger &x) {
195         add(*this, x);
196 }
197 inline void BigInteger::operator -=(const BigInteger &x) {
198         subtract(*this, x);
199 }
200 inline void BigInteger::operator *=(const BigInteger &x) {
201         multiply(*this, x);
202 }
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 }
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
221 inline void BigInteger::flipSign() {
222         sign = Sign(-sign);
223 }
224
225 #endif