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 #include "BigInteger.hh"
8 
operator =(const BigInteger & x)9 void BigInteger::operator =(const BigInteger &x) {
10 	// Calls like a = a have no effect
11 	if (this == &x)
12 		return;
13 	// Copy sign
14 	sign = x.sign;
15 	// Copy the rest
16 	mag = x.mag;
17 }
18 
BigInteger(const Blk * b,Index blen,Sign s)19 BigInteger::BigInteger(const Blk *b, Index blen, Sign s) : mag(b, blen) {
20 	switch (s) {
21 	case zero:
22 		if (!mag.isZero())
23             abort();
24 		sign = zero;
25 		break;
26 	case positive:
27 	case negative:
28 		// If the magnitude is zero, force the sign to zero.
29 		sign = mag.isZero() ? zero : s;
30 		break;
31 	default:
32 		/* g++ seems to be optimizing out this case on the assumption
33 		 * that the sign is a valid member of the enumeration.  Oh well. */
34         abort();
35 	}
36 }
37 
BigInteger(const BigUnsigned & x,Sign s)38 BigInteger::BigInteger(const BigUnsigned &x, Sign s) : mag(x) {
39 	switch (s) {
40 	case zero:
41 		if (!mag.isZero())
42             abort();
43 		sign = zero;
44 		break;
45 	case positive:
46 	case negative:
47 		// If the magnitude is zero, force the sign to zero.
48 		sign = mag.isZero() ? zero : s;
49 		break;
50 	default:
51 		/* g++ seems to be optimizing out this case on the assumption
52 		 * that the sign is a valid member of the enumeration.  Oh well. */
53         abort();
54 	}
55 }
56 
57 /* CONSTRUCTION FROM PRIMITIVE INTEGERS
58  * Same idea as in BigUnsigned.cc, except that negative input results in a
59  * negative BigInteger instead of an exception. */
60 
61 // Done longhand to let us use initialization.
BigInteger(unsigned long x)62 BigInteger::BigInteger(unsigned long  x) : mag(x) { sign = mag.isZero() ? zero : positive; }
BigInteger(unsigned int x)63 BigInteger::BigInteger(unsigned int   x) : mag(x) { sign = mag.isZero() ? zero : positive; }
BigInteger(unsigned short x)64 BigInteger::BigInteger(unsigned short x) : mag(x) { sign = mag.isZero() ? zero : positive; }
65 
66 // For signed input, determine the desired magnitude and sign separately.
67 
68 namespace {
69 	template <class X, class UX>
magOf(X x)70 	BigInteger::Blk magOf(X x) {
71 		/* UX(...) cast needed to stop short(-2^15), which negates to
72 		 * itself, from sign-extending in the conversion to Blk. */
73 		return BigInteger::Blk(x < 0 ? UX(-x) : x);
74 	}
75 	template <class X>
signOf(X x)76 	BigInteger::Sign signOf(X x) {
77 		return (x == 0) ? BigInteger::zero
78 			: (x > 0) ? BigInteger::positive
79 			: BigInteger::negative;
80 	}
81 }
82 
BigInteger(long x)83 BigInteger::BigInteger(long  x) : sign(signOf(x)), mag(magOf<long , unsigned long >(x)) {}
BigInteger(int x)84 BigInteger::BigInteger(int   x) : sign(signOf(x)), mag(magOf<int  , unsigned int  >(x)) {}
BigInteger(short x)85 BigInteger::BigInteger(short x) : sign(signOf(x)), mag(magOf<short, unsigned short>(x)) {}
86 
87 // CONVERSION TO PRIMITIVE INTEGERS
88 
89 /* Reuse BigUnsigned's conversion to an unsigned primitive integer.
90  * The friend is a separate function rather than
91  * BigInteger::convertToUnsignedPrimitive to avoid requiring BigUnsigned to
92  * declare BigInteger. */
93 template <class X>
convertBigUnsignedToPrimitiveAccess(const BigUnsigned & a)94 inline X convertBigUnsignedToPrimitiveAccess(const BigUnsigned &a) {
95 	return a.convertToPrimitive<X>();
96 }
97 
98 template <class X>
convertToUnsignedPrimitive() const99 X BigInteger::convertToUnsignedPrimitive() const {
100 	if (sign == negative)
101         abort();
102 	else
103 		return convertBigUnsignedToPrimitiveAccess<X>(mag);
104 }
105 
106 /* Similar to BigUnsigned::convertToPrimitive, but split into two cases for
107  * nonnegative and negative numbers. */
108 template <class X, class UX>
convertToSignedPrimitive() const109 X BigInteger::convertToSignedPrimitive() const {
110 	if (sign == zero)
111 		return 0;
112 	else if (mag.getLength() == 1) {
113 		// The single block might fit in an X.  Try the conversion.
114 		Blk b = mag.getBlock(0);
115 		if (sign == positive) {
116 			X x = X(b);
117 			if (x >= 0 && Blk(x) == b)
118 				return x;
119 		} else {
120 			X x = -X(b);
121 			/* UX(...) needed to avoid rejecting conversion of
122 			 * -2^15 to a short. */
123 			if (x < 0 && Blk(UX(-x)) == b)
124 				return x;
125 		}
126 		// Otherwise fall through.
127 	}
128     abort();
129 }
130 
toUnsignedLong() const131 unsigned long  BigInteger::toUnsignedLong () const { return convertToUnsignedPrimitive<unsigned long >       (); }
toUnsignedInt() const132 unsigned int   BigInteger::toUnsignedInt  () const { return convertToUnsignedPrimitive<unsigned int  >       (); }
toUnsignedShort() const133 unsigned short BigInteger::toUnsignedShort() const { return convertToUnsignedPrimitive<unsigned short>       (); }
toLong() const134 long           BigInteger::toLong         () const { return convertToSignedPrimitive  <long , unsigned long> (); }
toInt() const135 int            BigInteger::toInt          () const { return convertToSignedPrimitive  <int  , unsigned int>  (); }
toShort() const136 short          BigInteger::toShort        () const { return convertToSignedPrimitive  <short, unsigned short>(); }
137 
138 // COMPARISON
compareTo(const BigInteger & x) const139 BigInteger::CmpRes BigInteger::compareTo(const BigInteger &x) const {
140 	// A greater sign implies a greater number
141 	if (sign < x.sign)
142 		return less;
143 	else if (sign > x.sign)
144 		return greater;
145 	else switch (sign) {
146 		// If the signs are the same...
147 	case zero:
148 		return equal; // Two zeros are equal
149 	case positive:
150 		// Compare the magnitudes
151 		return mag.compareTo(x.mag);
152 	case negative:
153 		// Compare the magnitudes, but return the opposite result
154 		return CmpRes(-mag.compareTo(x.mag));
155 	default:
156         abort();
157 	}
158 }
159 
160 /* COPY-LESS OPERATIONS
161  * These do some messing around to determine the sign of the result,
162  * then call one of BigUnsigned's copy-less operations. */
163 
164 // See remarks about aliased calls in BigUnsigned.cc .
165 #define DTRT_ALIASED(cond, op) \
166 	if (cond) { \
167 		BigInteger tmpThis; \
168 		tmpThis.op; \
169 		*this = tmpThis; \
170 		return; \
171 	}
172 
add(const BigInteger & a,const BigInteger & b)173 void BigInteger::add(const BigInteger &a, const BigInteger &b) {
174 	DTRT_ALIASED(this == &a || this == &b, add(a, b));
175 	// If one argument is zero, copy the other.
176 	if (a.sign == zero)
177 		operator =(b);
178 	else if (b.sign == zero)
179 		operator =(a);
180 	// If the arguments have the same sign, take the
181 	// common sign and add their magnitudes.
182 	else if (a.sign == b.sign) {
183 		sign = a.sign;
184 		mag.add(a.mag, b.mag);
185 	} else {
186 		// Otherwise, their magnitudes must be compared.
187 		switch (a.mag.compareTo(b.mag)) {
188 		case equal:
189 			// If their magnitudes are the same, copy zero.
190 			mag = 0;
191 			sign = zero;
192 			break;
193 			// Otherwise, take the sign of the greater, and subtract
194 			// the lesser magnitude from the greater magnitude.
195 		case greater:
196 			sign = a.sign;
197 			mag.subtract(a.mag, b.mag);
198 			break;
199 		case less:
200 			sign = b.sign;
201 			mag.subtract(b.mag, a.mag);
202 			break;
203 		}
204 	}
205 }
206 
subtract(const BigInteger & a,const BigInteger & b)207 void BigInteger::subtract(const BigInteger &a, const BigInteger &b) {
208 	// Notice that this routine is identical to BigInteger::add,
209 	// if one replaces b.sign by its opposite.
210 	DTRT_ALIASED(this == &a || this == &b, subtract(a, b));
211 	// If a is zero, copy b and flip its sign.  If b is zero, copy a.
212 	if (a.sign == zero) {
213 		mag = b.mag;
214 		// Take the negative of _b_'s, sign, not ours.
215 		// Bug pointed out by Sam Larkin on 2005.03.30.
216 		sign = Sign(-b.sign);
217 	} else if (b.sign == zero)
218 		operator =(a);
219 	// If their signs differ, take a.sign and add the magnitudes.
220 	else if (a.sign != b.sign) {
221 		sign = a.sign;
222 		mag.add(a.mag, b.mag);
223 	} else {
224 		// Otherwise, their magnitudes must be compared.
225 		switch (a.mag.compareTo(b.mag)) {
226 			// If their magnitudes are the same, copy zero.
227 		case equal:
228 			mag = 0;
229 			sign = zero;
230 			break;
231 			// If a's magnitude is greater, take a.sign and
232 			// subtract a from b.
233 		case greater:
234 			sign = a.sign;
235 			mag.subtract(a.mag, b.mag);
236 			break;
237 			// If b's magnitude is greater, take the opposite
238 			// of b.sign and subtract b from a.
239 		case less:
240 			sign = Sign(-b.sign);
241 			mag.subtract(b.mag, a.mag);
242 			break;
243 		}
244 	}
245 }
246 
multiply(const BigInteger & a,const BigInteger & b)247 void BigInteger::multiply(const BigInteger &a, const BigInteger &b) {
248 	DTRT_ALIASED(this == &a || this == &b, multiply(a, b));
249 	// If one object is zero, copy zero and return.
250 	if (a.sign == zero || b.sign == zero) {
251 		sign = zero;
252 		mag = 0;
253 		return;
254 	}
255 	// If the signs of the arguments are the same, the result
256 	// is positive, otherwise it is negative.
257 	sign = (a.sign == b.sign) ? positive : negative;
258 	// Multiply the magnitudes.
259 	mag.multiply(a.mag, b.mag);
260 }
261 
262 /*
263  * DIVISION WITH REMAINDER
264  * Please read the comments before the definition of
265  * `BigUnsigned::divideWithRemainder' in `BigUnsigned.cc' for lots of
266  * information you should know before reading this function.
267  *
268  * Following Knuth, I decree that x / y is to be
269  * 0 if y==0 and floor(real-number x / y) if y!=0.
270  * Then x % y shall be x - y*(integer x / y).
271  *
272  * Note that x = y * (x / y) + (x % y) always holds.
273  * In addition, (x % y) is from 0 to y - 1 if y > 0,
274  * and from -(|y| - 1) to 0 if y < 0.  (x % y) = x if y = 0.
275  *
276  * Examples: (q = a / b, r = a % b)
277  *	a	b	q	r
278  *	===	===	===	===
279  *	4	3	1	1
280  *	-4	3	-2	2
281  *	4	-3	-2	-2
282  *	-4	-3	1	-1
283  */
divideWithRemainder(const BigInteger & b,BigInteger & q)284 void BigInteger::divideWithRemainder(const BigInteger &b, BigInteger &q) {
285 	// Defend against aliased calls;
286 	// same idea as in BigUnsigned::divideWithRemainder .
287 	if (this == &q)
288         abort();
289 	if (this == &b || &q == &b) {
290 		BigInteger tmpB(b);
291 		divideWithRemainder(tmpB, q);
292 		return;
293 	}
294 
295 	// Division by zero gives quotient 0 and remainder *this
296 	if (b.sign == zero) {
297 		q.mag = 0;
298 		q.sign = zero;
299 		return;
300 	}
301 	// 0 / b gives quotient 0 and remainder 0
302 	if (sign == zero) {
303 		q.mag = 0;
304 		q.sign = zero;
305 		return;
306 	}
307 
308 	// Here *this != 0, b != 0.
309 
310 	// Do the operands have the same sign?
311 	if (sign == b.sign) {
312 		// Yes: easy case.  Quotient is zero or positive.
313 		q.sign = positive;
314 	} else {
315 		// No: harder case.  Quotient is negative.
316 		q.sign = negative;
317 		// Decrease the magnitude of the dividend by one.
318 		mag--;
319 		/*
320 		 * We tinker with the dividend before and with the
321 		 * quotient and remainder after so that the result
322 		 * comes out right.  To see why it works, consider the following
323 		 * list of examples, where A is the magnitude-decreased
324 		 * a, Q and R are the results of BigUnsigned division
325 		 * with remainder on A and |b|, and q and r are the
326 		 * final results we want:
327 		 *
328 		 *	a	A	b	Q	R	q	r
329 		 *	-3	-2	3	0	2	-1	0
330 		 *	-4	-3	3	1	0	-2	2
331 		 *	-5	-4	3	1	1	-2	1
332 		 *	-6	-5	3	1	2	-2	0
333 		 *
334 		 * It appears that we need a total of 3 corrections:
335 		 * Decrease the magnitude of a to get A.  Increase the
336 		 * magnitude of Q to get q (and make it negative).
337 		 * Find r = (b - 1) - R and give it the desired sign.
338 		 */
339 	}
340 
341 	// Divide the magnitudes.
342 	mag.divideWithRemainder(b.mag, q.mag);
343 
344 	if (sign != b.sign) {
345 		// More for the harder case (as described):
346 		// Increase the magnitude of the quotient by one.
347 		q.mag++;
348 		// Modify the remainder.
349 		mag.subtract(b.mag, mag);
350 		mag--;
351 	}
352 
353 	// Sign of the remainder is always the sign of the divisor b.
354 	sign = b.sign;
355 
356 	// Set signs to zero as necessary.  (Thanks David Allen!)
357 	if (mag.isZero())
358 		sign = zero;
359 	if (q.mag.isZero())
360 		q.sign = zero;
361 
362 	// WHEW!!!
363 }
364 
365 // Negation
negate(const BigInteger & a)366 void BigInteger::negate(const BigInteger &a) {
367 	DTRT_ALIASED(this == &a, negate(a));
368 	// Copy a's magnitude
369 	mag = a.mag;
370 	// Copy the opposite of a.sign
371 	sign = Sign(-a.sign);
372 }
373 
374 // INCREMENT/DECREMENT OPERATORS
375 
376 // Prefix increment
operator ++()377 void BigInteger::operator ++() {
378 	if (sign == negative) {
379 		mag--;
380 		if (mag == 0)
381 			sign = zero;
382 	} else {
383 		mag++;
384 		sign = positive; // if not already
385 	}
386 }
387 
388 // Postfix increment: same as prefix
operator ++(int)389 void BigInteger::operator ++(int) {
390 	operator ++();
391 }
392 
393 // Prefix decrement
operator --()394 void BigInteger::operator --() {
395 	if (sign == positive) {
396 		mag--;
397 		if (mag == 0)
398 			sign = zero;
399 	} else {
400 		mag++;
401 		sign = negative;
402 	}
403 }
404 
405 // Postfix decrement: same as prefix
operator --(int)406 void BigInteger::operator --(int) {
407 	operator --();
408 }
409 
410