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 9void 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 19BigInteger::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 38BigInteger::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. 62BigInteger::BigInteger(unsigned long x) : mag(x) { sign = mag.isZero() ? zero : positive; } 63BigInteger::BigInteger(unsigned int x) : mag(x) { sign = mag.isZero() ? zero : positive; } 64BigInteger::BigInteger(unsigned short x) : mag(x) { sign = mag.isZero() ? zero : positive; } 65 66// For signed input, determine the desired magnitude and sign separately. 67 68namespace { 69 template <class X, class UX> 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> 76 BigInteger::Sign signOf(X x) { 77 return (x == 0) ? BigInteger::zero 78 : (x > 0) ? BigInteger::positive 79 : BigInteger::negative; 80 } 81} 82 83BigInteger::BigInteger(long x) : sign(signOf(x)), mag(magOf<long , unsigned long >(x)) {} 84BigInteger::BigInteger(int x) : sign(signOf(x)), mag(magOf<int , unsigned int >(x)) {} 85BigInteger::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. */ 93template <class X> 94inline X convertBigUnsignedToPrimitiveAccess(const BigUnsigned &a) { 95 return a.convertToPrimitive<X>(); 96} 97 98template <class X> 99X 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. */ 108template <class X, class UX> 109X 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 131unsigned long BigInteger::toUnsignedLong () const { return convertToUnsignedPrimitive<unsigned long > (); } 132unsigned int BigInteger::toUnsignedInt () const { return convertToUnsignedPrimitive<unsigned int > (); } 133unsigned short BigInteger::toUnsignedShort() const { return convertToUnsignedPrimitive<unsigned short> (); } 134long BigInteger::toLong () const { return convertToSignedPrimitive <long , unsigned long> (); } 135int BigInteger::toInt () const { return convertToSignedPrimitive <int , unsigned int> (); } 136short BigInteger::toShort () const { return convertToSignedPrimitive <short, unsigned short>(); } 137 138// COMPARISON 139BigInteger::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 173void 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 207void 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 247void 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 */ 284void 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 366void 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 377void 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 389void BigInteger::operator ++(int) { 390 operator ++(); 391} 392 393// Prefix decrement 394void 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 406void BigInteger::operator --(int) { 407 operator --(); 408} 409 410