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 BIGUNSIGNED_H 8 #define BIGUNSIGNED_H 9 10 #include "NumberlikeArray.hh" 11 12 /* A BigUnsigned object represents a nonnegative 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 * The number is stored as a NumberlikeArray of unsigned longs as if it were 17 * written in base 256^sizeof(unsigned long). The least significant block is 18 * first, and the length is such that the most significant block is nonzero. */ 19 class BigUnsigned : protected NumberlikeArray<unsigned long> { 20 21 public: 22 // Enumeration for the result of a comparison. 23 enum CmpRes { less = -1, equal = 0, greater = 1 }; 24 25 // BigUnsigneds are built with a Blk type of unsigned long. 26 typedef unsigned long Blk; 27 28 typedef NumberlikeArray<Blk>::Index Index; 29 using NumberlikeArray<Blk>::N; 30 31 protected: 32 // Creates a BigUnsigned with a capacity; for internal use. 33 BigUnsigned(int, Index c) : NumberlikeArray<Blk>(0, c) {} 34 35 // Decreases len to eliminate any leading zero blocks. 36 void zapLeadingZeros() { 37 while (len > 0 && blk[len - 1] == 0) 38 len--; 39 } 40 41 public: 42 // Constructs zero. 43 BigUnsigned() : NumberlikeArray<Blk>() {} 44 45 // Copy constructor 46 BigUnsigned(const BigUnsigned &x) : NumberlikeArray<Blk>(x) {} 47 48 // Assignment operator 49 void operator=(const BigUnsigned &x) { 50 NumberlikeArray<Blk>::operator =(x); 51 } 52 53 // Constructor that copies from a given array of blocks. 54 BigUnsigned(const Blk *b, Index blen) : NumberlikeArray<Blk>(b, blen) { 55 // Eliminate any leading zeros we may have been passed. 56 zapLeadingZeros(); 57 } 58 59 // Destructor. NumberlikeArray does the delete for us. 60 ~BigUnsigned() {} 61 62 // Constructors from primitive integer types 63 BigUnsigned(unsigned long x); 64 BigUnsigned( long x); 65 BigUnsigned(unsigned int x); 66 BigUnsigned( int x); 67 BigUnsigned(unsigned short x); 68 BigUnsigned( short x); 69 protected: 70 // Helpers 71 template <class X> void initFromPrimitive (X x); 72 template <class X> void initFromSignedPrimitive(X x); 73 public: 74 75 /* Converters to primitive integer types 76 * The implicit conversion operators caused trouble, so these are now 77 * named. */ 78 unsigned long toUnsignedLong () const; 79 long toLong () const; 80 unsigned int toUnsignedInt () const; 81 int toInt () const; 82 unsigned short toUnsignedShort() const; 83 short toShort () const; 84 protected: 85 // Helpers 86 template <class X> X convertToSignedPrimitive() const; 87 template <class X> X convertToPrimitive () const; 88 public: 89 90 // BIT/BLOCK ACCESSORS 91 92 // Expose these from NumberlikeArray directly. 93 using NumberlikeArray<Blk>::getCapacity; 94 using NumberlikeArray<Blk>::getLength; 95 96 /* Returns the requested block, or 0 if it is beyond the length (as if 97 * the number had 0s infinitely to the left). */ 98 Blk getBlock(Index i) const { return i >= len ? 0 : blk[i]; } 99 /* Sets the requested block. The number grows or shrinks as necessary. */ 100 void setBlock(Index i, Blk newBlock); 101 102 // The number is zero if and only if the canonical length is zero. 103 bool isZero() const { return NumberlikeArray<Blk>::isEmpty(); } 104 105 /* Returns the length of the number in bits, i.e., zero if the number 106 * is zero and otherwise one more than the largest value of bi for 107 * which getBit(bi) returns true. */ 108 Index bitLength() const; 109 /* Get the state of bit bi, which has value 2^bi. Bits beyond the 110 * number's length are considered to be 0. */ 111 bool getBit(Index bi) const { 112 return (getBlock(bi / N) & (Blk(1) << (bi % N))) != 0; 113 } 114 /* Sets the state of bit bi to newBit. The number grows or shrinks as 115 * necessary. */ 116 void setBit(Index bi, bool newBit); 117 118 // COMPARISONS 119 120 // Compares this to x like Perl's <=> 121 CmpRes compareTo(const BigUnsigned &x) const; 122 123 // Ordinary comparison operators 124 bool operator ==(const BigUnsigned &x) const { 125 return NumberlikeArray<Blk>::operator ==(x); 126 } 127 bool operator !=(const BigUnsigned &x) const { 128 return NumberlikeArray<Blk>::operator !=(x); 129 } 130 bool operator < (const BigUnsigned &x) const { return compareTo(x) == less ; } 131 bool operator <=(const BigUnsigned &x) const { return compareTo(x) != greater; } 132 bool operator >=(const BigUnsigned &x) const { return compareTo(x) != less ; } 133 bool operator > (const BigUnsigned &x) const { return compareTo(x) == greater; } 134 135 /* 136 * BigUnsigned and BigInteger both provide three kinds of operators. 137 * Here ``big-integer'' refers to BigInteger or BigUnsigned. 138 * 139 * (1) Overloaded ``return-by-value'' operators: 140 * +, -, *, /, %, unary -, &, |, ^, <<, >>. 141 * Big-integer code using these operators looks identical to code using 142 * the primitive integer types. These operators take one or two 143 * big-integer inputs and return a big-integer result, which can then 144 * be assigned to a BigInteger variable or used in an expression. 145 * Example: 146 * BigInteger a(1), b = 1; 147 * BigInteger c = a + b; 148 * 149 * (2) Overloaded assignment operators: 150 * +=, -=, *=, /=, %=, flipSign, &=, |=, ^=, <<=, >>=, ++, --. 151 * Again, these are used on big integers just like on ints. They take 152 * one writable big integer that both provides an operand and receives a 153 * result. Most also take a second read-only operand. 154 * Example: 155 * BigInteger a(1), b(1); 156 * a += b; 157 * 158 * (3) Copy-less operations: `add', `subtract', etc. 159 * These named methods take operands as arguments and store the result 160 * in the receiver (*this), avoiding unnecessary copies and allocations. 161 * `divideWithRemainder' is special: it both takes the dividend from and 162 * stores the remainder into the receiver, and it takes a separate 163 * object in which to store the quotient. NOTE: If you are wondering 164 * why these don't return a value, you probably mean to use the 165 * overloaded return-by-value operators instead. 166 * 167 * Examples: 168 * BigInteger a(43), b(7), c, d; 169 * 170 * c = a + b; // Now c == 50. 171 * c.add(a, b); // Same effect but without the two copies. 172 * 173 * c.divideWithRemainder(b, d); 174 * // 50 / 7; now d == 7 (quotient) and c == 1 (remainder). 175 * 176 * // ``Aliased'' calls now do the right thing using a temporary 177 * // copy, but see note on `divideWithRemainder'. 178 * a.add(a, b); 179 */ 180 181 // COPY-LESS OPERATIONS 182 183 // These 8: Arguments are read-only operands, result is saved in *this. 184 void add(const BigUnsigned &a, const BigUnsigned &b); 185 void subtract(const BigUnsigned &a, const BigUnsigned &b); 186 void multiply(const BigUnsigned &a, const BigUnsigned &b); 187 void bitAnd(const BigUnsigned &a, const BigUnsigned &b); 188 void bitOr(const BigUnsigned &a, const BigUnsigned &b); 189 void bitXor(const BigUnsigned &a, const BigUnsigned &b); 190 /* Negative shift amounts translate to opposite-direction shifts, 191 * except for -2^(8*sizeof(int)-1) which is unimplemented. */ 192 void bitShiftLeft(const BigUnsigned &a, int b); 193 void bitShiftRight(const BigUnsigned &a, int b); 194 195 /* `a.divideWithRemainder(b, q)' is like `q = a / b, a %= b'. 196 * / and % use semantics similar to Knuth's, which differ from the 197 * primitive integer semantics under division by zero. See the 198 * implementation in BigUnsigned.cc for details. 199 * `a.divideWithRemainder(b, a)' throws an exception: it doesn't make 200 * sense to write quotient and remainder into the same variable. */ 201 void divideWithRemainder(const BigUnsigned &b, BigUnsigned &q); 202 203 /* `divide' and `modulo' are no longer offered. Use 204 * `divideWithRemainder' instead. */ 205 206 // OVERLOADED RETURN-BY-VALUE OPERATORS 207 BigUnsigned operator +(const BigUnsigned &x) const; 208 BigUnsigned operator -(const BigUnsigned &x) const; 209 BigUnsigned operator *(const BigUnsigned &x) const; 210 BigUnsigned operator /(const BigUnsigned &x) const; 211 BigUnsigned operator %(const BigUnsigned &x) const; 212 /* OK, maybe unary minus could succeed in one case, but it really 213 * shouldn't be used, so it isn't provided. */ 214 BigUnsigned operator &(const BigUnsigned &x) const; 215 BigUnsigned operator |(const BigUnsigned &x) const; 216 BigUnsigned operator ^(const BigUnsigned &x) const; 217 BigUnsigned operator <<(int b) const; 218 BigUnsigned operator >>(int b) const; 219 220 // OVERLOADED ASSIGNMENT OPERATORS 221 void operator +=(const BigUnsigned &x); 222 void operator -=(const BigUnsigned &x); 223 void operator *=(const BigUnsigned &x); 224 void operator /=(const BigUnsigned &x); 225 void operator %=(const BigUnsigned &x); 226 void operator &=(const BigUnsigned &x); 227 void operator |=(const BigUnsigned &x); 228 void operator ^=(const BigUnsigned &x); 229 void operator <<=(int b); 230 void operator >>=(int b); 231 232 /* INCREMENT/DECREMENT OPERATORS 233 * To discourage messy coding, these do not return *this, so prefix 234 * and postfix behave the same. */ 235 void operator ++( ); 236 void operator ++(int); 237 void operator --( ); 238 void operator --(int); 239 240 // Helper function that needs access to BigUnsigned internals 241 friend Blk getShiftedBlock(const BigUnsigned &num, Index x, 242 unsigned int y); 243 244 // See BigInteger.cc. 245 template <class X> 246 friend X convertBigUnsignedToPrimitiveAccess(const BigUnsigned &a); 247 }; 248 249 /* Implementing the return-by-value and assignment operators in terms of the 250 * copy-less operations. The copy-less operations are responsible for making 251 * any necessary temporary copies to work around aliasing. */ 252 253 inline BigUnsigned BigUnsigned::operator +(const BigUnsigned &x) const { 254 BigUnsigned ans; 255 ans.add(*this, x); 256 return ans; 257 } 258 inline BigUnsigned BigUnsigned::operator -(const BigUnsigned &x) const { 259 BigUnsigned ans; 260 ans.subtract(*this, x); 261 return ans; 262 } 263 inline BigUnsigned BigUnsigned::operator *(const BigUnsigned &x) const { 264 BigUnsigned ans; 265 ans.multiply(*this, x); 266 return ans; 267 } 268 inline BigUnsigned BigUnsigned::operator /(const BigUnsigned &x) const { 269 if (x.isZero()) 270 abort(); 271 BigUnsigned q, r; 272 r = *this; 273 r.divideWithRemainder(x, q); 274 return q; 275 } 276 inline BigUnsigned BigUnsigned::operator %(const BigUnsigned &x) const { 277 if (x.isZero()) 278 abort(); 279 BigUnsigned q, r; 280 r = *this; 281 r.divideWithRemainder(x, q); 282 return r; 283 } 284 inline BigUnsigned BigUnsigned::operator &(const BigUnsigned &x) const { 285 BigUnsigned ans; 286 ans.bitAnd(*this, x); 287 return ans; 288 } 289 inline BigUnsigned BigUnsigned::operator |(const BigUnsigned &x) const { 290 BigUnsigned ans; 291 ans.bitOr(*this, x); 292 return ans; 293 } 294 inline BigUnsigned BigUnsigned::operator ^(const BigUnsigned &x) const { 295 BigUnsigned ans; 296 ans.bitXor(*this, x); 297 return ans; 298 } 299 inline BigUnsigned BigUnsigned::operator <<(int b) const { 300 BigUnsigned ans; 301 ans.bitShiftLeft(*this, b); 302 return ans; 303 } 304 inline BigUnsigned BigUnsigned::operator >>(int b) const { 305 BigUnsigned ans; 306 ans.bitShiftRight(*this, b); 307 return ans; 308 } 309 310 inline void BigUnsigned::operator +=(const BigUnsigned &x) { 311 add(*this, x); 312 } 313 inline void BigUnsigned::operator -=(const BigUnsigned &x) { 314 subtract(*this, x); 315 } 316 inline void BigUnsigned::operator *=(const BigUnsigned &x) { 317 multiply(*this, x); 318 } 319 inline void BigUnsigned::operator /=(const BigUnsigned &x) { 320 if (x.isZero()) 321 abort(); 322 /* The following technique is slightly faster than copying *this first 323 * when x is large. */ 324 BigUnsigned q; 325 divideWithRemainder(x, q); 326 // *this contains the remainder, but we overwrite it with the quotient. 327 *this = q; 328 } 329 inline void BigUnsigned::operator %=(const BigUnsigned &x) { 330 if (x.isZero()) 331 abort(); 332 BigUnsigned q; 333 // Mods *this by x. Don't care about quotient left in q. 334 divideWithRemainder(x, q); 335 } 336 inline void BigUnsigned::operator &=(const BigUnsigned &x) { 337 bitAnd(*this, x); 338 } 339 inline void BigUnsigned::operator |=(const BigUnsigned &x) { 340 bitOr(*this, x); 341 } 342 inline void BigUnsigned::operator ^=(const BigUnsigned &x) { 343 bitXor(*this, x); 344 } 345 inline void BigUnsigned::operator <<=(int b) { 346 bitShiftLeft(*this, b); 347 } 348 inline void BigUnsigned::operator >>=(int b) { 349 bitShiftRight(*this, b); 350 } 351 352 /* Templates for conversions of BigUnsigned to and from primitive integers. 353 * BigInteger.cc needs to instantiate convertToPrimitive, and the uses in 354 * BigUnsigned.cc didn't do the trick; I think g++ inlined convertToPrimitive 355 * instead of generating linkable instantiations. So for consistency, I put 356 * all the templates here. */ 357 358 // CONSTRUCTION FROM PRIMITIVE INTEGERS 359 360 /* Initialize this BigUnsigned from the given primitive integer. The same 361 * pattern works for all primitive integer types, so I put it into a template to 362 * reduce code duplication. (Don't worry: this is protected and we instantiate 363 * it only with primitive integer types.) Type X could be signed, but x is 364 * known to be nonnegative. */ 365 template <class X> 366 void BigUnsigned::initFromPrimitive(X x) { 367 if (x == 0) 368 ; // NumberlikeArray already initialized us to zero. 369 else { 370 // Create a single block. blk is NULL; no need to delete it. 371 cap = 1; 372 blk = new Blk[1]; 373 len = 1; 374 blk[0] = Blk(x); 375 } 376 } 377 378 /* Ditto, but first check that x is nonnegative. I could have put the check in 379 * initFromPrimitive and let the compiler optimize it out for unsigned-type 380 * instantiations, but I wanted to avoid the warning stupidly issued by g++ for 381 * a condition that is constant in *any* instantiation, even if not in all. */ 382 template <class X> 383 void BigUnsigned::initFromSignedPrimitive(X x) { 384 if (x < 0) 385 abort(); 386 else 387 initFromPrimitive(x); 388 } 389 390 // CONVERSION TO PRIMITIVE INTEGERS 391 392 /* Template with the same idea as initFromPrimitive. This might be slightly 393 * slower than the previous version with the masks, but it's much shorter and 394 * clearer, which is the library's stated goal. */ 395 template <class X> 396 X BigUnsigned::convertToPrimitive() const { 397 if (len == 0) 398 // The number is zero; return zero. 399 return 0; 400 else if (len == 1) { 401 // The single block might fit in an X. Try the conversion. 402 X x = X(blk[0]); 403 // Make sure the result accurately represents the block. 404 if (Blk(x) == blk[0]) 405 // Successful conversion. 406 return x; 407 // Otherwise fall through. 408 } 409 abort(); 410 } 411 412 /* Wrap the above in an x >= 0 test to make sure we got a nonnegative result, 413 * not a negative one that happened to convert back into the correct nonnegative 414 * one. (E.g., catch incorrect conversion of 2^31 to the long -2^31.) Again, 415 * separated to avoid a g++ warning. */ 416 template <class X> 417 X BigUnsigned::convertToSignedPrimitive() const { 418 X x = convertToPrimitive<X>(); 419 if (x >= 0) 420 return x; 421 else 422 abort(); 423 } 424 425 #endif 426