BigUnsigned.cc

   1 /*
   2 * Matt McCutchen's Big Integer Library
   3 * http://mysite.verizon.net/mccutchen/bigint/
   4 */
   5
   6 #include "BigUnsigned.hh"
   7
   8 // The "management" routines that used to be here are now in NumberlikeArray.hh.
   9
  10 /*
  11 * The steps for construction of a BigUnsigned
  12 * from an integral value x are as follows:
  13 * 1. If x is zero, create an empty BigUnsigned and stop.
  14 * 2. If x is negative, throw an exception.
  15 * 3. Allocate a one-block number array.
  16 * 4. If x is of a signed type, convert x to the unsigned
  17 *    type of the same length.
  18 * 5. Expand x to a Blk, and store it in the number array.
  19 *
  20 * Since 2005.01.06, NumberlikeArray uses `NULL' rather
  21 * than a real array if one of zero length is needed.
  22 * These constructors implicitly call NumberlikeArray's
  23 * default constructor, which sets `blk = NULL, cap = len = 0'.
  24 * So if the input number is zero, they can just return.
  25 * See remarks in `NumberlikeArray.hh'.
  26 */
  27
  28 BigUnsigned::BigUnsigned(unsigned long x) {
  29         if (x == 0)
  30                 ; // NumberlikeArray already did all the work
  31         else {
  32                 cap = 1;
  33                 blk = new Blk[1];
  34                 len = 1;
  35                 blk[0] = Blk(x);
  36         }
  37 }
  38
  39 BigUnsigned::BigUnsigned(long x) {
  40         if (x == 0)
  41                 ;
  42         else if (x > 0) {
  43                 cap = 1;
  44                 blk = new Blk[1];
  45                 len = 1;
  46                 blk[0] = Blk(x);
  47         } else
  48         throw "BigUnsigned::BigUnsigned(long): Cannot construct a BigUnsigned from a negative number";
  49 }
  50
  51 BigUnsigned::BigUnsigned(unsigned int x) {
  52         if (x == 0)
  53                 ;
  54         else {
  55                 cap = 1;
  56                 blk = new Blk[1];
  57                 len = 1;
  58                 blk[0] = Blk(x);
  59         }
  60 }
  61
  62 BigUnsigned::BigUnsigned(int x) {
  63         if (x == 0)
  64                 ;
  65         else if (x > 0) {
  66                 cap = 1;
  67                 blk = new Blk[1];
  68                 len = 1;
  69                 blk[0] = Blk(x);
  70         } else
  71         throw "BigUnsigned::BigUnsigned(int): Cannot construct a BigUnsigned from a negative number";
  72 }
  73
  74 BigUnsigned::BigUnsigned(unsigned short x) {
  75         if (x == 0)
  76                 ;
  77         else {
  78                 cap = 1;
  79                 blk = new Blk[1];
  80                 len = 1;
  81                 blk[0] = Blk(x);
  82         }
  83 }
  84
  85 BigUnsigned::BigUnsigned(short x) {
  86         if (x == 0)
  87                 ;
  88         else if (x > 0) {
  89                 cap = 1;
  90                 blk = new Blk[1];
  91                 len = 1;
  92                 blk[0] = Blk(x);
  93         } else
  94         throw "BigUnsigned::BigUnsigned(short): Cannot construct a BigUnsigned from a negative number";
  95 }
  96
  97 // CONVERTERS
  98 /*
  99 * The steps for conversion of a BigUnsigned to an
 100 * integral type are as follows:
 101 * 1. If the BigUnsigned is zero, return zero.
 102 * 2. If it is more than one block long or its lowest
 103 *    block has bits set out of the range of the target
 104 *    type, throw an exception.
 105 * 3. Otherwise, convert the lowest block to the
 106 *    target type and return it.
 107 */
 108
 109 namespace {
 110         // These masks are used to test whether a Blk has bits
 111         // set out of the range of a smaller integral type.  Note
 112         // that this range is not considered to include the sign bit.
 113         const BigUnsigned::Blk  lMask = ~0 >> 1;
 114         const BigUnsigned::Blk uiMask = (unsigned int)(~0);
 115         const BigUnsigned::Blk  iMask = uiMask >> 1;
 116         const BigUnsigned::Blk usMask = (unsigned short)(~0);
 117         const BigUnsigned::Blk  sMask = usMask >> 1;
 118 }
 119
 120 BigUnsigned::operator unsigned long() const {
 121         if (len == 0)
 122                 return 0;
 123         else if (len == 1)
 124                 return (unsigned long) blk[0];
 125         else
 126                 throw "BigUnsigned::operator unsigned long: Value is too big for an unsigned long";
 127 }
 128
 129 BigUnsigned::operator long() const {
 130         if (len == 0)
 131                 return 0;
 132         else if (len == 1 && (blk[0] & lMask) == blk[0])
 133                 return (long) blk[0];
 134         else
 135                 throw "BigUnsigned::operator long: Value is too big for a long";
 136 }
 137
 138 BigUnsigned::operator unsigned int() const {
 139         if (len == 0)
 140                 return 0;
 141         else if (len == 1 && (blk[0] & uiMask) == blk[0])
 142                 return (unsigned int) blk[0];
 143         else
 144                 throw "BigUnsigned::operator unsigned int: Value is too big for an unsigned int";
 145 }
 146
 147 BigUnsigned::operator int() const {
 148         if (len == 0)
 149                 return 0;
 150         else if (len == 1 && (blk[0] & iMask) == blk[0])
 151                 return (int) blk[0];
 152         else
 153                 throw "BigUnsigned::operator int: Value is too big for an int";
 154 }
 155
 156 BigUnsigned::operator unsigned short() const {
 157         if (len == 0)
 158                 return 0;
 159         else if (len == 1 && (blk[0] & usMask) == blk[0])
 160                 return (unsigned short) blk[0];
 161         else
 162                 throw "BigUnsigned::operator unsigned short: Value is too big for an unsigned short";
 163 }
 164
 165 BigUnsigned::operator short() const {
 166         if (len == 0)
 167                 return 0;
 168         else if (len == 1 && (blk[0] & sMask) == blk[0])
 169                 return (short) blk[0];
 170         else
 171                 throw "BigUnsigned::operator short: Value is too big for a short";
 172 }
 173
 174 // COMPARISON
 175 BigUnsigned::CmpRes BigUnsigned::compareTo(const BigUnsigned &x) const {
 176         // A bigger length implies a bigger number.
 177         if (len < x.len)
 178                 return less;
 179         else if (len > x.len)
 180                 return greater;
 181         else {
 182                 // Compare blocks one by one from left to right.
 183                 Index i = len;
 184                 while (i > 0) {
 185                         i--;
 186                         if (blk[i] == x.blk[i])
 187                                 continue;
 188                         else if (blk[i] > x.blk[i])
 189                                 return greater;
 190                         else
 191                                 return less;
 192                 }
 193                 // If no blocks differed, the numbers are equal.
 194                 return equal;
 195         }
 196 }
 197
 198 // PUT-HERE OPERATIONS
 199
 200 /*
 201 * Below are implementations of the four basic arithmetic operations
 202 * for `BigUnsigned's.  Their purpose is to use a mechanism that can
 203 * calculate the sum, difference, product, and quotient/remainder of
 204 * two individual blocks in order to calculate the sum, difference,
 205 * product, and quotient/remainder of two multi-block BigUnsigned
 206 * numbers.
 207 *
 208 * As alluded to in the comment before class `BigUnsigned',
 209 * these algorithms bear a remarkable similarity (in purpose, if
 210 * not in implementation) to the way humans operate on big numbers.
 211 * The built-in `+', `-', `*', `/' and `%' operators are analogous
 212 * to elementary-school ``math facts'' and ``times tables''; the
 213 * four routines below are analogous to ``long division'' and its
 214 * relatives.  (Only a computer can ``memorize'' a times table with
 215 * 18446744073709551616 entries!  (For 32-bit blocks.))
 216 *
 217 * The discovery of these four algorithms, called the ``classical
 218 * algorithms'', marked the beginning of the study of computer science.
 219 * See Section 4.3.1 of Knuth's ``The Art of Computer Programming''.
 220 */
 221
 222 // Addition
 223 void BigUnsigned::add(const BigUnsigned &a, const BigUnsigned &b) {
 224         // Block unsafe calls
 225         if (this == &a || this == &b)
 226                 throw "BigUnsigned::add: One of the arguments is the invoked object";
 227         // If one argument is zero, copy the other.
 228         if (a.len == 0) {
 229                 operator =(b);
 230                 return;
 231         } else if (b.len == 0) {
 232                 operator =(a);
 233                 return;
 234         }
 235         // Some variables...
 236         // Carries in and out of an addition stage
 237         bool carryIn, carryOut;
 238         Blk temp;
 239         Index i;
 240         // a2 points to the longer input, b2 points to the shorter
 241         const BigUnsigned *a2, *b2;
 242         if (a.len >= b.len) {
 243                 a2 = &a;
 244                 b2 = &b;
 245         } else {
 246                 a2 = &b;
 247                 b2 = &a;
 248         }
 249         // Set prelimiary length and make room in this BigUnsigned
 250         len = a2->len + 1;
 251         allocate(len);
 252         // For each block index that is present in both inputs...
 253         for (i = 0, carryIn = false; i < b2->len; i++) {
 254                 // Add input blocks
 255                 temp = a2->blk[i] + b2->blk[i];
 256                 // If a rollover occurred, the result is less than either input.
 257                 // This test is used many times in the BigUnsigned code.
 258                 carryOut = (temp < a2->blk[i]);
 259                 // If a carry was input, handle it
 260                 if (carryIn) {
 261                         temp++;
 262                         carryOut |= (temp == 0);
 263                 }
 264                 blk[i] = temp; // Save the addition result
 265                 carryIn = carryOut; // Pass the carry along
 266         }
 267         // If there is a carry left over, increase blocks until
 268         // one does not roll over.
 269         for (; i < a2->len && carryIn; i++) {
 270                 temp = a2->blk[i] + 1;
 271                 carryIn = (temp == 0);
 272                 blk[i] = temp;
 273         }
 274         // If the carry was resolved but the larger number
 275         // still has blocks, copy them over.
 276         for (; i < a2->len; i++)
 277                 blk[i] = a2->blk[i];
 278         // Set the extra block if there's still a carry, decrease length otherwise
 279         if (carryIn)
 280                 blk[i] = 1;
 281         else
 282                 len--;
 283 }
 284
 285 // Subtraction
 286 void BigUnsigned::subtract(const BigUnsigned &a, const BigUnsigned &b) {
 287         // Block unsafe calls
 288         if (this == &a || this == &b)
 289                 throw "BigUnsigned::subtract: One of the arguments is the invoked object";
 290         // If b is zero, copy a.  If a is shorter than b, the result is negative.
 291         if (b.len == 0) {
 292                 operator =(a);
 293                 return;
 294         } else if (a.len < b.len)
 295         throw "BigUnsigned::subtract: Negative result in unsigned calculation";
 296         // Some variables...
 297         bool borrowIn, borrowOut;
 298         Blk temp;
 299         Index i;
 300         // Set preliminary length and make room
 301         len = a.len;
 302         allocate(len);
 303         // For each block index that is present in both inputs...
 304         for (i = 0, borrowIn = false; i < b.len; i++) {
 305                 temp = a.blk[i] - b.blk[i];
 306                 // If a reverse rollover occurred, the result is greater than the block from a.
 307                 borrowOut = (temp > a.blk[i]);
 308                 // Handle an incoming borrow
 309                 if (borrowIn) {
 310                         borrowOut |= (temp == 0);
 311                         temp--;
 312                 }
 313                 blk[i] = temp; // Save the subtraction result
 314                 borrowIn = borrowOut; // Pass the borrow along
 315         }
 316         // If there is a borrow left over, decrease blocks until
 317         // one does not reverse rollover.
 318         for (; i < a.len && borrowIn; i++) {
 319                 borrowIn = (a.blk[i] == 0);
 320                 blk[i] = a.blk[i] - 1;
 321         }
 322         // If there's still a borrow, the result is negative.
 323         // Throw an exception, but zero out this object first just in case.
 324         if (borrowIn) {
 325                 len = 0;
 326                 throw "BigUnsigned::subtract: Negative result in unsigned calculation";
 327         } else // Copy over the rest of the blocks
 328         for (; i < a.len; i++)
 329                 blk[i] = a.blk[i];
 330         // Zap leading zeros
 331         zapLeadingZeros();
 332 }
 333
 334 /*
 335 * About the multiplication and division algorithms:
 336 *
 337 * I searched unsucessfully for fast built-in operations like the `b_0'
 338 * and `c_0' Knuth describes in Section 4.3.1 of ``The Art of Computer
 339 * Programming'' (replace `place' by `Blk'):
 340 *
 341 *    ``b_0[:] multiplication of a one-place integer by another one-place
 342 *      integer, giving a two-place answer;
 343 *
 344 *    ``c_0[:] division of a two-place integer by a one-place integer,
 345 *      provided that the quotient is a one-place integer, and yielding
 346 *      also a one-place remainder.''
 347 *
 348 * I also missed his note that ``[b]y adjusting the word size, if
 349 * necessary, nearly all computers will have these three operations
 350 * available'', so I gave up on trying to use algorithms similar to his.
 351 * A future version of the library might include such algorithms; I
 352 * would welcome contributions from others for this.
 353 *
 354 * I eventually decided to use bit-shifting algorithms.  To multiply `a'
 355 * and `b', we zero out the result.  Then, for each `1' bit in `a', we
 356 * shift `b' left the appropriate amount and add it to the result.
 357 * Similarly, to divide `a' by `b', we shift `b' left varying amounts,
 358 * repeatedly trying to subtract it from `a'.  When we succeed, we note
 359 * the fact by setting a bit in the quotient.  While these algorithms
 360 * have the same O(n^2) time complexity as Knuth's, the ``constant factor''
 361 * is likely to be larger.
 362 *
 363 * Because I used these algorithms, which require single-block addition
 364 * and subtraction rather than single-block multiplication and division,
 365 * the innermost loops of all four routines are very similar.  Study one
 366 * of them and all will become clear.
 367 */
 368
 369 /*
 370 * This is a little inline function used by both the multiplication
 371 * routine and the division routine.
 372 *
 373 * `getShiftedBlock' returns the `x'th block of `num << y'.
 374 * `y' may be anything from 0 to N - 1, and `x' may be anything from
 375 * 0 to `num.len'.
 376 *
 377 * Two things contribute to this block:
 378 *
 379 * (1) The `N - y' low bits of `num.blk[x]', shifted `y' bits left.
 380 *
 381 * (2) The `y' high bits of `num.blk[x-1]', shifted `N - y' bits right.
 382 *
 383 * But we must be careful if `x == 0' or `x == num.len', in
 384 * which case we should use 0 instead of (2) or (1), respectively.
 385 *
 386 * If `y == 0', then (2) contributes 0, as it should.  However,
 387 * in some computer environments, for a reason I cannot understand,
 388 * `a >> b' means `a >> (b % N)'.  This means `num.blk[x-1] >> (N - y)'
 389 * will return `num.blk[x-1]' instead of the desired 0 when `y == 0';
 390 * the test `y == 0' handles this case specially.
 391 */
 392 inline BigUnsigned::Blk getShiftedBlock(const BigUnsigned &num,
 393         BigUnsigned::Index x, unsigned int y) {
 394         BigUnsigned::Blk part1 = (x == 0 || y == 0) ? 0 : (num.blk[x - 1] >> (BigUnsigned::N - y));
 395         BigUnsigned::Blk part2 = (x == num.len) ? 0 : (num.blk[x] << y);
 396         return part1 | part2;
 397 }
 398
 399 // Multiplication
 400 void BigUnsigned::multiply(const BigUnsigned &a, const BigUnsigned &b) {
 401         // Block unsafe calls
 402         if (this == &a || this == &b)
 403                 throw "BigUnsigned::multiply: One of the arguments is the invoked object";
 404         // If either a or b is zero, set to zero.
 405         if (a.len == 0 || b.len == 0) {
 406                 len = 0;
 407                 return;
 408         }
 409         /*
 410         * Overall method:
 411         *
 412         * Set this = 0.
 413         * For each 1-bit of `a' (say the `i2'th bit of block `i'):
 414         *    Add `b << (i blocks and i2 bits)' to *this.
 415         */
 416         // Variables for the calculation
 417         Index i, j, k;
 418         unsigned int i2;
 419         Blk temp;
 420         bool carryIn, carryOut;
 421         // Set preliminary length and make room
 422         len = a.len + b.len;
 423         allocate(len);
 424         // Zero out this object
 425         for (i = 0; i < len; i++)
 426                 blk[i] = 0;
 427         // For each block of the first number...
 428         for (i = 0; i < a.len; i++) {
 429                 // For each 1-bit of that block...
 430                 for (i2 = 0; i2 < N; i2++) {
 431                         if ((a.blk[i] & (1 << i2)) == 0)
 432                                 continue;
 433                         /*
 434                         * Add b to this, shifted left i blocks and i2 bits.
 435                         * j is the index in b, and k = i + j is the index in this.
 436                         *
 437                         * `getShiftedBlock', a short inline function defined above,
 438                         * is now used for the bit handling.  It replaces the more
 439                         * complex `bHigh' code, in which each run of the loop dealt
 440                         * immediately with the low bits and saved the high bits to
 441                         * be picked up next time.  The last run of the loop used to
 442                         * leave leftover high bits, which were handled separately.
 443                         * Instead, this loop runs an additional time with j == b.len.
 444                         * These changes were made on 2005.01.11.
 445                         */
 446                         for (j = 0, k = i, carryIn = false; j <= b.len; j++, k++) {
 447                                 /*
 448                                 * The body of this loop is very similar to the body of the first loop
 449                                 * in `add', except that this loop does a `+=' instead of a `+'.
 450                                 */
 451                                 temp = blk[k] + getShiftedBlock(b, j, i2);
 452                                 carryOut = (temp < blk[k]);
 453                                 if (carryIn) {
 454                                         temp++;
 455                                         carryOut |= (temp == 0);
 456                                 }
 457                                 blk[k] = temp;
 458                                 carryIn = carryOut;
 459                         }
 460                         // No more extra iteration to deal with `bHigh'.
 461                         // Roll-over a carry as necessary.
 462                         for (; carryIn; k++) {
 463                                 blk[k]++;
 464                                 carryIn = (blk[k] == 0);
 465                         }
 466                 }
 467         }
 468         // Zap possible leading zero
 469         if (blk[len - 1] == 0)
 470                 len--;
 471 }
 472
 473 /*
 474 * DIVISION WITH REMAINDER
 475 * The functionality of divide, modulo, and %= is included in this one monstrous call,
 476 * which deserves some explanation.
 477 *
 478 * The division *this / b is performed.
 479 * Afterwards, q has the quotient, and *this has the remainder.
 480 * Thus, a call is like q = *this / b, *this %= b.
 481 *
 482 * This seemingly bizarre pattern of inputs and outputs has a justification.  The
 483 * ``put-here operations'' are supposed to be fast.  Therefore, they accept inputs
 484 * and provide outputs in the most convenient places so that no value ever needs
 485 * to be copied in its entirety.  That way, the client can perform exactly the
 486 * copying it needs depending on where the inputs are and where it wants the output.
 487 */
 488 void BigUnsigned::divideWithRemainder(const BigUnsigned &b, BigUnsigned &q) {
 489         // Block unsafe calls
 490         if (this == &b || &q == &b || this == &q)
 491                 throw "BigUnsigned::divideWithRemainder: Some two objects involved are the same";
 492
 493         /*
 494         * Note that the mathematical definition of mod (I'm trusting Knuth) is somewhat
 495         * different from the way the normal C++ % operator behaves in the case of division by 0.
 496         * This function does it Knuth's way.
 497         *
 498         * We let a / 0 == 0 (it doesn't matter) and a % 0 == a, no exceptions thrown.
 499         * This allows us to preserve both Knuth's demand that a mod 0 == a
 500         * and the useful property that (a / b) * b + (a % b) == a.
 501         */
 502         if (b.len == 0) {
 503                 q.len = 0;
 504                 return;
 505         }
 506
 507         /*
 508         * If *this.len < b.len, then *this < b, and we can be sure that b doesn't go into
 509         * *this at all.  The quotient is 0 and *this is already the remainder (so leave it alone).
 510         */
 511         if (len < b.len) {
 512                 q.len = 0;
 513                 return;
 514         }
 515
 516         /*
 517         * At this point we know *this > b > 0.  (Whew!)
 518         */
 519
 520         /*
 521         * Overall method:
 522         *
 523         * For each appropriate i and i2, decreasing:
 524         *    Try to subtract (b << (i blocks and i2 bits)) from *this.
 525         *        (`work2' holds the result of this subtraction.)
 526         *    If the result is nonnegative:
 527         *        Turn on bit i2 of block i of the quotient q.
 528         *        Save the result of the subtraction back into *this.
 529         *    Otherwise:
 530         *        Bit i2 of block i remains off, and *this is unchanged.
 531         *
 532         * Eventually q will contain the entire quotient, and *this will
 533         * be left with the remainder.
 534         *
 535         * We use work2 to temporarily store the result of a subtraction.
 536         * work2[x] corresponds to blk[x], not blk[x+i], since 2005.01.11.
 537         * If the subtraction is successful, we copy work2 back to blk.
 538         * (There's no `work1'.  In a previous version, when division was
 539         * coded for a read-only dividend, `work1' played the role of
 540         * the here-modifiable `*this' and got the remainder.)
 541         *
 542         * We never touch the i lowest blocks of either blk or work2 because
 543         * they are unaffected by the subtraction: we are subtracting
 544         * (b << (i blocks and i2 bits)), which ends in at least `i' zero blocks.
 545         */
 546         // Variables for the calculation
 547         Index i, j, k;
 548         unsigned int i2;
 549         Blk temp;
 550         bool borrowIn, borrowOut;
 551
 552         /*
 553         * Make sure we have an extra zero block just past the value.
 554         *
 555         * When we attempt a subtraction, we might shift `b' so
 556         * its first block begins a few bits left of the dividend,
 557         * and then we'll try to compare these extra bits with
 558         * a nonexistent block to the left of the dividend.  The
 559         * extra zero block ensures sensible behavior; we need
 560         * an extra block in `work2' for exactly the same reason.
 561         *
 562         * See below `divideWithRemainder' for the interesting and
 563         * amusing story of this section of code.
 564         */
 565         Index origLen = len; // Save real length.
 566         len++; // Increase the length.
 567         allocateAndCopy(len); // Get the space.
 568         blk[origLen] = 0; // Zero the extra block.
 569
 570         // work2 holds part of the result of a subtraction; see above.
 571         Blk *work2 = new Blk[len];
 572
 573         // Set preliminary length for quotient and make room
 574         q.len = origLen - b.len + 1;
 575         q.allocate(q.len);
 576         // Zero out the quotient
 577         for (i = 0; i < q.len; i++)
 578                 q.blk[i] = 0;
 579
 580         // For each possible left-shift of b in blocks...
 581         i = q.len;
 582         while (i > 0) {
 583                 i--;
 584                 // For each possible left-shift of b in bits...
 585                 // (Remember, N is the number of bits in a Blk.)
 586                 q.blk[i] = 0;
 587                 i2 = N;
 588                 while (i2 > 0) {
 589                         i2--;
 590                         /*
 591                         * Subtract b, shifted left i blocks and i2 bits, from *this,
 592                         * and store the answer in work2.  In the for loop, `k == i + j'.
 593                         *
 594                         * Compare this to the middle section of `multiply'.  They
 595                         * are in many ways analogous.  See especially the discussion
 596                         * of `getShiftedBlock'.
 597                         */
 598                         for (j = 0, k = i, borrowIn = false; j <= b.len; j++, k++) {
 599                                 temp = blk[k] - getShiftedBlock(b, j, i2);
 600                                 borrowOut = (temp > blk[k]);
 601                                 if (borrowIn) {
 602                                         borrowOut |= (temp == 0);
 603                                         temp--;
 604                                 }
 605                                 // Since 2005.01.11, indices of `work2' directly match those of `blk', so use `k'.
 606                                 work2[k] = temp;
 607                                 borrowIn = borrowOut;
 608                         }
 609                         // No more extra iteration to deal with `bHigh'.
 610                         // Roll-over a borrow as necessary.
 611                         for (; k < origLen && borrowIn; k++) {
 612                                 borrowIn = (blk[k] == 0);
 613                                 work2[k] = blk[k] - 1;
 614                         }
 615                         /*
 616                         * If the subtraction was performed successfully (!borrowIn),
 617                         * set bit i2 in block i of the quotient.
 618                         *
 619                         * Then, copy the portion of work2 filled by the subtraction
 620                         * back to *this.  This portion starts with block i and ends--
 621                         * where?  Not necessarily at block `i + b.len'!  Well, we
 622                         * increased k every time we saved a block into work2, so
 623                         * the region of work2 we copy is just [i, k).
 624                         */
 625                         if (!borrowIn) {
 626                                 q.blk[i] |= (1 << i2);
 627                                 while (k > i) {
 628                                         k--;
 629                                         blk[k] = work2[k];
 630                                 }
 631                         }
 632                 }
 633         }
 634         // Zap possible leading zero in quotient
 635         if (q.blk[q.len - 1] == 0)
 636                 q.len--;
 637         // Zap any/all leading zeros in remainder
 638         zapLeadingZeros();
 639         // Deallocate temporary array.
 640         // (Thanks to Brad Spencer for noticing my accidental omission of this!)
 641         delete [] work2;
 642
 643 }
 644 /*
 645 * The out-of-bounds accesses story:
 646 *
 647 * On 2005.01.06 or 2005.01.07 (depending on your time zone),
 648 * Milan Tomic reported out-of-bounds memory accesses in
 649 * the Big Integer Library.  To investigate the problem, I
 650 * added code to bounds-check every access to the `blk' array
 651 * of a `NumberlikeArray'.
 652 *
 653 * This gave me warnings that fell into two categories of false
 654 * positives.  The bounds checker was based on length, not
 655 * capacity, and in two places I had accessed memory that I knew
 656 * was inside the capacity but that wasn't inside the length:
 657 *
 658 * (1) The extra zero block at the left of `*this'.  Earlier
 659 * versions said `allocateAndCopy(len + 1); blk[len] = 0;'
 660 * but did not increment `len'.
 661 *
 662 * (2) The entire digit array in the conversion constructor
 663 * ``BigUnsignedInABase(BigUnsigned)''.  It was allocated with
 664 * a conservatively high capacity, but the length wasn't set
 665 * until the end of the constructor.
 666 *
 667 * To simplify matters, I changed both sections of code so that
 668 * all accesses occurred within the length.  The messages went
 669 * away, and I told Milan that I couldn't reproduce the problem,
 670 * sending a development snapshot of the bounds-checked code.
 671 *
 672 * Then, on 2005.01.09-10, he told me his debugger still found
 673 * problems, specifically at the line `delete [] work2'.
 674 * It was `work2', not `blk', that was causing the problems;
 675 * this possibility had not occurred to me at all.  In fact,
 676 * the problem was that `work2' needed an extra block just
 677 * like `*this'.  Go ahead and laugh at me for finding (1)
 678 * without seeing what was actually causing the trouble.  :-)
 679 *
 680 * The 2005.01.11 version fixes this problem.  I hope this is
 681 * the last of my memory-related bloopers.  So this is what
 682 * starts happening to your C++ code if you use Java too much!
 683 */
 684
 685 // Bitwise and
 686 void BigUnsigned::bitAnd(const BigUnsigned &a, const BigUnsigned &b) {
 687         // Block unsafe calls
 688         if (this == &a || this == &b)
 689                 throw "BigUnsigned::bitAnd: One of the arguments is the invoked object";
 690         len = (a.len >= b.len) ? b.len : a.len;
 691         allocate(len);
 692         Index i;
 693         for (i = 0; i < len; i++)
 694                 blk[i] = a.blk[i] & b.blk[i];
 695         zapLeadingZeros();
 696 }
 697
 698 // Bitwise or
 699 void BigUnsigned::bitOr(const BigUnsigned &a, const BigUnsigned &b) {
 700         // Block unsafe calls
 701         if (this == &a || this == &b)
 702                 throw "BigUnsigned::bitOr: One of the arguments is the invoked object";
 703         Index i;
 704         const BigUnsigned *a2, *b2;
 705         if (a.len >= b.len) {
 706                 a2 = &a;
 707                 b2 = &b;
 708         } else {
 709                 a2 = &b;
 710                 b2 = &a;
 711         }
 712         allocate(a2->len);
 713         for (i = 0; i < b2->len; i++)
 714                 blk[i] = a2->blk[i] | b2->blk[i];
 715         for (; i < a2->len; i++)
 716                 blk[i] = a2->blk[i];
 717         len = a2->len;
 718 }
 719
 720 // Bitwise xor
 721 void BigUnsigned::bitXor(const BigUnsigned &a, const BigUnsigned &b) {
 722         // Block unsafe calls
 723         if (this == &a || this == &b)
 724                 throw "BigUnsigned::bitXor: One of the arguments is the invoked object";
 725         Index i;
 726         const BigUnsigned *a2, *b2;
 727         if (a.len >= b.len) {
 728                 a2 = &a;
 729                 b2 = &b;
 730         } else {
 731                 a2 = &b;
 732                 b2 = &a;
 733         }
 734         allocate(b2->len);
 735         for (i = 0; i < b2->len; i++)
 736                 blk[i] = a2->blk[i] ^ b2->blk[i];
 737         for (; i < a2->len; i++)
 738                 blk[i] = a2->blk[i];
 739         len = a2->len;
 740         zapLeadingZeros();
 741 }
 742
 743 // INCREMENT/DECREMENT OPERATORS
 744
 745 // Prefix increment
 746 void BigUnsigned::operator ++() {
 747         Index i;
 748         bool carry = true;
 749         for (i = 0; i < len && carry; i++) {
 750                 blk[i]++;
 751                 carry = (blk[i] == 0);
 752         }
 753         if (carry) {
 754                 // Matt fixed a bug 2004.12.24: next 2 lines used to say allocateAndCopy(len + 1)
 755                 len++;
 756                 allocateAndCopy(len);
 757                 blk[i] = 1;
 758         }
 759 }
 760
 761 // Postfix increment: same as prefix
 762 void BigUnsigned::operator ++(int) {
 763         operator ++();
 764 }
 765
 766 // Prefix decrement
 767 void BigUnsigned::operator --() {
 768         if (len == 0)
 769                 throw "BigUnsigned::operator --(): Cannot decrement an unsigned zero";
 770         Index i;
 771         bool borrow = true;
 772         for (i = 0; borrow; i++) {
 773                 borrow = (blk[i] == 0);
 774                 blk[i]--;
 775         }
 776         // Zap possible leading zero (there can only be one)
 777         if (blk[len - 1] == 0)
 778                 len--;
 779 }
 780
 781 // Postfix decrement: same as prefix
 782 void BigUnsigned::operator --(int) {
 783         operator --();
 784 }