Bo Xu | 8ad0040 | 2014-12-02 13:06:22 -0800 | [diff] [blame] | 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()) |
Bo Xu | 8ad0040 | 2014-12-02 13:06:22 -0800 | [diff] [blame] | 270 | abort(); |
Bo Xu | 8ad0040 | 2014-12-02 13:06:22 -0800 | [diff] [blame] | 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()) |
Bo Xu | 8ad0040 | 2014-12-02 13:06:22 -0800 | [diff] [blame] | 278 | abort(); |
Bo Xu | 8ad0040 | 2014-12-02 13:06:22 -0800 | [diff] [blame] | 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()) |
Bo Xu | 8ad0040 | 2014-12-02 13:06:22 -0800 | [diff] [blame] | 321 | abort(); |
Bo Xu | 8ad0040 | 2014-12-02 13:06:22 -0800 | [diff] [blame] | 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()) |
Bo Xu | 8ad0040 | 2014-12-02 13:06:22 -0800 | [diff] [blame] | 331 | abort(); |
Bo Xu | 8ad0040 | 2014-12-02 13:06:22 -0800 | [diff] [blame] | 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) |
Bo Xu | 8ad0040 | 2014-12-02 13:06:22 -0800 | [diff] [blame] | 385 | abort(); |
Bo Xu | 8ad0040 | 2014-12-02 13:06:22 -0800 | [diff] [blame] | 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 | } |
Bo Xu | 8ad0040 | 2014-12-02 13:06:22 -0800 | [diff] [blame] | 409 | abort(); |
Bo Xu | 8ad0040 | 2014-12-02 13:06:22 -0800 | [diff] [blame] | 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 |
Bo Xu | 8ad0040 | 2014-12-02 13:06:22 -0800 | [diff] [blame] | 422 | abort(); |
Bo Xu | 8ad0040 | 2014-12-02 13:06:22 -0800 | [diff] [blame] | 423 | } |
| 424 | |
| 425 | #endif |