BigUnsigned.cpp

   1 /*
   2 * Matt McCutchen's Big Integer Library
   3 * http://mysite.verizon.net/mccutchen/bigint/
   4 */
   5
   6 #include "BigUnsigned.h"
   7
   8 // MANAGEMENT
   9
  10 // This routine is called to ensure the number array is at least a
  11 // certain size before the result of an operation is written over it.
  12 void BigUnsigned::allocate(BlkNum c) {
  13         // If the requested capacity is more than the current capacity...
  14         if (c > cap) {
  15                 // Delete the old number array
  16                 delete [] blk;
  17                 // Allocate the new array
  18                 cap = c;
  19                 blk = new Blk[cap];
  20         }
  21 }
  22
  23 // This routine is called to ensure the number array is at least a
  24 // certain size without losing its contents.
  25 void BigUnsigned::allocateAndCopy(BlkNum c) {
  26         // If the requested capacity is more than the current capacity...
  27         if (c > cap) {
  28                 Blk *oldBlk = blk;
  29                 // Allocate the new number array
  30                 cap = c;
  31                 blk = new Blk[cap];
  32                 // Copy number blocks
  33                 BlkNum i;
  34                 Blk *blkI;
  35                 const Blk *oldBlkI;
  36                 for (i = 0, blkI = blk, oldBlkI = oldBlk; i < len; i++, blkI++, oldBlkI++)
  37                         *blkI = *oldBlkI;
  38                 // Delete the old array
  39                 delete [] oldBlk;
  40         }
  41 }
  42
  43 // Copy constructor
  44 BigUnsigned::BigUnsigned(const BigUnsigned &x) : len(x.len) {
  45         // Create number array
  46         cap = len;
  47         blk = new Blk[cap];
  48         // Copy number blocks
  49         BlkNum i;
  50         Blk *blkI;
  51         const Blk *xBlkI;
  52         for (i = 0, blkI = blk, xBlkI = x.blk; i < len; i++, blkI++, xBlkI++)
  53                 *blkI = *xBlkI;
  54 }
  55
  56 // Assignment operator
  57 void BigUnsigned::operator=(const BigUnsigned &x) {
  58         // Calls like a = a have no effect
  59         if (this == &x)
  60                 return;
  61         // Copy length
  62         len = x.len;
  63         // Expand number array if necessary
  64         allocate(len);
  65         // Copy number blocks
  66         BlkNum i;
  67         Blk *blkI;
  68         const Blk *xBlkI;
  69         for (i = 0, blkI = blk, xBlkI = x.blk; i < len; i++, blkI++, xBlkI++)
  70                 *blkI = *xBlkI;
  71 }
  72
  73 // Constructor from an array of blocks
  74 BigUnsigned::BigUnsigned(const Blk *b, BlkNum l) : cap(l), len(l) {
  75         // Create number array
  76         blk = new Blk[cap];
  77         // Copy number blocks
  78         BlkNum i;
  79         Blk *blkI;
  80         const Blk *bI;
  81         for (i = 0, blkI = blk, bI = b; i < len; i++, blkI++, bI++)
  82                 *blkI = *bI;
  83         zapLeadingZeros();
  84 }
  85
  86 /*
  87 * The steps for construction of a BigUnsigned
  88 * from an integral value x are as follows:
  89 * 1. If x is zero, create an empty BigUnsigned and stop.
  90 * 2. If x is negative, throw an exception.
  91 * 3. Allocate a one-block number array.
  92 * 4. If x is of a signed type, convert x to the unsigned
  93 *    type of the same length.
  94 * 5. Expand x to a Blk, and store it in the number array.
  95 */
  96
  97 BigUnsigned::BigUnsigned(unsigned long x) {
  98         if (x == 0) {
  99                 cap = 0;
 100                 blk = new Blk[0];
 101                 len = 0;
 102         } else {
 103                 cap = 1;
 104                 blk = new Blk[1];
 105                 len = 1;
 106                 *blk = Blk(x);
 107         }
 108 }
 109
 110 BigUnsigned::BigUnsigned(long x) {
 111         if (x == 0) {
 112                 cap = 0;
 113                 blk = new Blk[0];
 114                 len = 0;
 115         } else if (x > 0) {
 116                 cap = 1;
 117                 blk = new Blk[1];
 118                 len = 1;
 119                 *blk = Blk(x);
 120         } else
 121     throw "BigUnsigned::BigUnsigned(long): Cannot construct a BigUnsigned from a negative number";
 122 }
 123
 124 BigUnsigned::BigUnsigned(unsigned int x) {
 125         if (x == 0) {
 126                 cap = 0;
 127                 blk = new Blk[0];
 128                 len = 0;
 129         } else {
 130                 cap = 1;
 131                 blk = new Blk[1];
 132                 len = 1;
 133                 *blk = Blk(x);
 134         }
 135 }
 136
 137 BigUnsigned::BigUnsigned(int x) {
 138         if (x == 0) {
 139                 cap = 0;
 140                 blk = new Blk[0];
 141                 len = 0;
 142         } else if (x > 0) {
 143                 cap = 1;
 144                 blk = new Blk[1];
 145                 len = 1;
 146                 *blk = Blk(x);
 147         } else
 148     throw "BigUnsigned::BigUnsigned(int): Cannot construct a BigUnsigned from a negative number";
 149 }
 150
 151 BigUnsigned::BigUnsigned(unsigned short x) {
 152         if (x == 0) {
 153                 cap = 0;
 154                 blk = new Blk[0];
 155                 len = 0;
 156         } else {
 157                 cap = 1;
 158                 blk = new Blk[1];
 159                 len = 1;
 160                 *blk = Blk(x);
 161         }
 162 }
 163
 164 BigUnsigned::BigUnsigned(short x) {
 165         if (x == 0) {
 166                 cap = 0;
 167                 blk = new Blk[0];
 168                 len = 0;
 169         } else if (x > 0) {
 170                 cap = 1;
 171                 blk = new Blk[1];
 172                 len = 1;
 173                 *blk = Blk(x);
 174         } else
 175     throw "BigUnsigned::BigUnsigned(short): Cannot construct a BigUnsigned from a negative number";
 176 }
 177
 178 // CONVERTERS
 179 /*
 180 * The steps for conversion of a BigUnsigned to an
 181 * integral type are as follows:
 182 * 1. If the BigUnsigned is zero, return zero.
 183 * 2. If it is more than one block long or its lowest
 184 *    block has bits set out of the range of the target
 185 *    type, throw an exception.
 186 * 3. Otherwise, convert the lowest block to the
 187 *    target type and return it.
 188 */
 189
 190 namespace {
 191         // These masks are used to test whether a Blk has bits
 192         // set out of the range of a smaller integral type.  Note
 193         // that this range is not considered to include the sign bit.
 194         const BigUnsigned::Blk  lMask = ~0 >> 1;
 195         const BigUnsigned::Blk uiMask = (unsigned int)(~0);
 196         const BigUnsigned::Blk  iMask = uiMask >> 1;
 197         const BigUnsigned::Blk usMask = (unsigned short)(~0);
 198         const BigUnsigned::Blk  sMask = usMask >> 1;
 199 }
 200
 201 BigUnsigned::operator unsigned long() const {
 202         if (len == 0)
 203                 return 0;
 204         else if (len == 1)
 205                 return (unsigned long) *blk;
 206         else
 207                 throw "BigUnsigned::operator unsigned long: Value is too big for an unsigned long";
 208 }
 209
 210 BigUnsigned::operator long() const {
 211         if (len == 0)
 212                 return 0;
 213         else if (len == 1 && (*blk & lMask) == *blk)
 214                 return (long) *blk;
 215         else
 216                 throw "BigUnsigned::operator long: Value is too big for a long";
 217 }
 218
 219 BigUnsigned::operator unsigned int() const {
 220         if (len == 0)
 221                 return 0;
 222         else if (len == 1 && (*blk & uiMask) == *blk)
 223                 return (unsigned int) *blk;
 224         else
 225                 throw "BigUnsigned::operator unsigned int: Value is too big for an unsigned int";
 226 }
 227
 228 BigUnsigned::operator int() const {
 229         if (len == 0)
 230                 return 0;
 231         else if (len == 1 && (*blk & iMask) == *blk)
 232                 return (int) *blk;
 233         else
 234                 throw "BigUnsigned::operator int: Value is too big for an int";
 235 }
 236
 237 BigUnsigned::operator unsigned short() const {
 238         if (len == 0)
 239                 return 0;
 240         else if (len == 1 && (*blk & usMask) == *blk)
 241                 return (unsigned short) *blk;
 242         else
 243                 throw "BigUnsigned::operator unsigned short: Value is too big for an unsigned short";
 244 }
 245
 246 BigUnsigned::operator short() const {
 247         if (len == 0)
 248                 return 0;
 249         else if (len == 1 && (*blk & sMask) == *blk)
 250                 return (short) *blk;
 251         else
 252                 throw "BigUnsigned::operator short: Value is too big for a short";
 253 }
 254
 255 // COMPARISON
 256 BigUnsigned::CmpRes BigUnsigned::compareTo(const BigUnsigned &x) const {
 257         // A bigger length implies a bigger number.
 258         if (len < x.len)
 259                 return less;
 260         else if (len > x.len)
 261                 return greater;
 262         else {
 263                 // Compare blocks one by one from left to right.
 264                 BlkNum i = len;
 265                 const Blk *blkI = blk + len;
 266                 const Blk *xBlkI = x.blk + len;
 267                 while (i > 0) {
 268                         i--;
 269                         blkI--;
 270                         xBlkI--;
 271                         if (*blkI == *xBlkI)
 272                                 continue;
 273                         else if (*blkI > *xBlkI)
 274                                 return greater;
 275                         else
 276                                 return less;
 277                 }
 278                 // If no blocks differed, the numbers are equal.
 279                 return equal;
 280         }
 281 }
 282
 283 // PUT-HERE OPERATIONS
 284
 285 // Addition
 286 void BigUnsigned::add(const BigUnsigned &a, const BigUnsigned &b) {
 287         // Block unsafe calls
 288         if (this == &a || this == &b)
 289                 throw "BigUnsigned::add: One of the arguments is the invoked object";
 290         // If one argument is zero, copy the other.
 291         if (a.len == 0) {
 292                 operator =(b);
 293                 return;
 294         } else if (b.len == 0) {
 295                 operator =(a);
 296                 return;
 297         }
 298         // Carries in and out of an addition stage
 299         bool carryIn, carryOut;
 300         Blk temp;
 301         BlkNum i;
 302         // a2 points to the longer input, b2 points to the shorter
 303         const BigUnsigned *a2, *b2;
 304         if (a.len >= b.len) {
 305                 a2 = &a;
 306                 b2 = &b;
 307         } else {
 308                 a2 = &b;
 309                 b2 = &a;
 310         }
 311         // These point directly to the position of interest in the
 312         // corresponding block arrays, for faster access.
 313         Blk *blkI;
 314         const Blk *a2BlkI, *b2BlkI;
 315         // Set prelimiary length and make room in this BigUnsigned
 316         len = a2->len + 1;
 317         allocate(len);
 318         // For each block index that is present in both inputs...
 319         for (i = 0, blkI = blk, a2BlkI = a2->blk, b2BlkI = b2->blk,
 320         carryIn = false; i < b2->len; i++, blkI++, a2BlkI++, b2BlkI++) {
 321                 // Add input blocks
 322                 temp = *a2BlkI + *b2BlkI;
 323                 // If a rollover occurred, the result is less than either input.
 324                 // This test is used many times in the BigUnsigned code.
 325                 carryOut = (temp < *a2BlkI);
 326                 // If a carry was input, handle it
 327                 if (carryIn) {
 328                         temp++;
 329                         carryOut |= (temp == 0);
 330                 }
 331                 *blkI = temp; // Save the addition result
 332                 carryIn = carryOut; // Pass the carry along
 333         }
 334         // If there is a carry left over, increase blocks until
 335         // one does not roll over.
 336         for (; i < a2->len && carryIn; i++, blkI++, a2BlkI++) {
 337                 temp = *a2BlkI + 1;
 338                 carryIn = (temp == 0);
 339                 *blkI = temp;
 340         }
 341         // If the carry was resolved but the larger number
 342         // still has blocks, copy them over.
 343         for (; i < a2->len; i++, blkI++, a2BlkI++)
 344                 *blkI = *a2BlkI;
 345         // Set the extra block if there's still a carry, decrease length otherwise
 346         if (carryIn)
 347                 *blkI = 1;
 348         else
 349                 len--;
 350 }
 351
 352 // Subtraction
 353 void BigUnsigned::subtract(const BigUnsigned &a, const BigUnsigned &b) {
 354         // Block unsafe calls
 355         if (this == &a || this == &b)
 356                 throw "BigUnsigned::subtract: One of the arguments is the invoked object";
 357         // If b is zero, copy a.  If a is shorter than b, the result is negative.
 358         if (b.len == 0) {
 359                 operator =(a);
 360                 return;
 361         } else if (a.len < b.len)
 362     throw "BigUnsigned::subtract: Negative result in unsigned calculation";
 363         bool borrowIn, borrowOut;
 364         Blk temp;
 365         BlkNum i;
 366         // These point directly to the position of interest in the
 367         // corresponding block arrays, for faster access.
 368         Blk *blkI;
 369         const Blk *aBlkI, *bBlkI;
 370         // Set preliminary length and make room
 371         len = a.len;
 372         allocate(len);
 373         // For each block index that is present in both inputs...
 374         for (i = 0, blkI = blk, aBlkI = a.blk, bBlkI = b.blk,
 375         borrowIn = false; i < b.len; i++, blkI++, aBlkI++, bBlkI++) {
 376                 temp = *aBlkI - *bBlkI;
 377                 // If a reverse rollover occurred, the result is greater than the block from a.
 378                 borrowOut = (temp > *aBlkI);
 379                 // Handle an incoming borrow
 380                 if (borrowIn) {
 381                         borrowOut |= (temp == 0);
 382                         temp--;
 383                 }
 384                 *blkI = temp; // Save the subtraction result
 385                 borrowIn = borrowOut; // Pass the borrow along
 386         }
 387         // If there is a borrow left over, decrease blocks until
 388         // one does not reverse rollover.
 389         for (; i < a.len && borrowIn; i++, blkI++, aBlkI++) {
 390                 borrowIn = (*aBlkI == 0);
 391                 *blkI = *aBlkI - 1;
 392         }
 393         // If there's still a borrow, the result is negative.
 394         // Throw an exception, but zero out this object first.
 395         if (borrowIn) {
 396                 len = 0;
 397                 throw "BigUnsigned::subtract: Negative result in unsigned calculation";
 398         } else // Copy over the rest of the blocks
 399     for (; i < a.len; i++, blkI++, aBlkI++)
 400                 *blkI = *aBlkI;
 401         // Zap leading zeros
 402         zapLeadingZeros();
 403 }
 404
 405 // Multiplication
 406 void BigUnsigned::multiply(const BigUnsigned &a, const BigUnsigned &b) {
 407         // Block unsafe calls
 408         if (this == &a || this == &b)
 409                 throw "BigUnsigned::multiply: One of the arguments is the invoked object";
 410         // If either a or b is zero, set to zero.
 411         if (a.len == 0 || b.len == 0) {
 412                 len = 0;
 413                 return;
 414         }
 415         // Overall method: this = 0, then for each 1-bit of a, add b
 416         // to this shifted the appropriate amount.
 417         // Variables for the calculation
 418         BlkNum i, j;
 419         unsigned int i2;
 420         Blk aBlk, bHigh, temp;
 421         bool carryIn, carryOut;
 422         // These point directly to the positions of interest in the
 423         // corresponding block arrays, for faster access.
 424         Blk *blkI, *blkK;
 425         const Blk *aBlkI, *bBlkJ;
 426         // Set preliminary length and make room
 427         len = a.len + b.len;
 428         allocate(len);
 429         // Zero out this object
 430         for (i = 0, blkI = blk; i < len; i++, blkI++)
 431                 *blkI = 0;
 432         // For each block of the first number...
 433         for (i = 0, blkI = blk, aBlkI = a.blk; i < a.len; i++, blkI++, aBlkI++)
 434                 // For each 1-bit of that block...
 435     for (i2 = 0, aBlk = *aBlkI; aBlk != 0; i2++, aBlk >>= 1) {
 436                 if ((aBlk & 1) == 0)
 437                         continue;
 438                 /* Add b to this, shifted left i blocks and i2 bits.
 439                 * j is the index in b, and k = i + j is the index in this.
 440                 * The low bits of b.blk[j] are shifted and added to blk[k].
 441                 * bHigh is used to carry the high bits to the next addition. */
 442                 carryIn = false;
 443                 bHigh = 0;
 444                 for (j = 0, bBlkJ = b.blk, blkK = blkI; j < b.len; j++, bBlkJ++, blkK++) {
 445                         temp = *blkK + ((*bBlkJ << i2) | bHigh);
 446                         carryOut = (temp < *blkK);
 447                         if (carryIn) {
 448                                 temp++;
 449                                 carryOut |= (temp == 0);
 450                         }
 451                         *blkK = temp;
 452                         carryIn = carryOut;
 453                         bHigh = (i2 == 0) ? 0 : *bBlkJ >> (8 * sizeof(Blk) - i2);
 454                 }
 455                 temp = *blkK + bHigh;
 456                 carryOut = (temp < *blkK);
 457                 if (carryIn) {
 458                         temp++;
 459                         carryOut |= (temp == 0);
 460                 }
 461                 *blkK = temp;
 462                 carryIn = carryOut;
 463                 for (; carryIn; blkK++) {
 464                         (*blkK)++;
 465                         carryIn = (*blkK == 0);
 466                 }
 467     }
 468         // Zap leading zero
 469         if (blk[len - 1] == 0)
 470                 len--;
 471 }
 472
 473 // Division
 474 void BigUnsigned::divide(const BigUnsigned &a, const BigUnsigned &b) {
 475         // Note: This is integer division.  Any fractional part
 476         // of the result is truncated.
 477         // Block unsafe calls
 478         if (this == &a || this == &b)
 479                 throw "BigUnsigned::divide: One of the arguments is the invoked object";
 480         // If b is zero, throw an exception.  If a is zero, set to zero.
 481         else if (b.len == 0)
 482                 throw "BigUnsigned::divide: Division by zero";
 483         else if (a.len < b.len) {
 484                 len = 0;
 485                 return;
 486         }
 487         /* Overall method: Subtract b, shifted varying amounts to
 488         * the left, from a, setting the bit in the quotient
 489         * whenever the subtraction succeeds. */
 490         // Variables for the calculation
 491         BlkNum i, j, k;
 492         unsigned int i2;
 493         Blk bHigh, temp;
 494         bool borrowIn, borrowOut;
 495         // work1 is a copy of a that can be modified
 496         // after each successful subtraction.
 497         Blk *work1 = new Blk[a.len + 1];
 498         Blk *work1I = work1;
 499         const Blk *aBlkI = a.blk;
 500         for (i = 0; i < a.len; i++, work1I++, aBlkI++)
 501                 *work1I = *aBlkI;
 502         *work1I = 0;
 503         // work2 holds part of the result of a subtraction
 504         Blk *work2 = new Blk[a.len + 1];
 505         // These point directly to the positions of interest in the
 506         // corresponding block arrays, for faster access.
 507         Blk *blkI, *work1K, *work2J;
 508         const Blk *bBlkJ;
 509         // Set preliminary length and make room
 510         len = a.len - b.len + 1;
 511         allocate(len);
 512         // For each possible left-shift of b in blocks...
 513         i = len;
 514         blkI = blk + len;
 515         work1I = work1 + len;
 516         while (i > 0) {
 517                 i--;
 518                 blkI--;
 519                 work1I--;
 520                 // For each possible left-shift of b in bits...
 521                 *blkI = 0;
 522                 i2 = 8 * sizeof(Blk);
 523                 while (i2 > 0) {
 524                         i2--;
 525                         // Subtract b, shifted left i blocks and i2 bits, from work1
 526                         // and store the answer in work2.  See note in BigUnsigned::multiply.
 527                         bHigh = 0;
 528                         for (j = 0, bBlkJ = b.blk, work2J = work2, k = i, work1K = work1I,
 529                         borrowIn = false; j < b.len; j++, bBlkJ++, work2J++, k++, work1K++) {
 530                                 temp = *work1K - ((*bBlkJ << i2) | bHigh);
 531                                 borrowOut = (temp > *work1K);
 532                                 if (borrowIn) {
 533                                         borrowOut |= (temp == 0);
 534                                         temp--;
 535                                 }
 536                                 *work2J = temp;
 537                                 borrowIn = borrowOut;
 538                                 bHigh = (i2 == 0) ? 0 : *bBlkJ >> (8 * sizeof(Blk) - i2);
 539                         }
 540                         temp = *work1K - bHigh;
 541                         borrowOut = (temp > *work1K);
 542                         if (borrowIn) {
 543                                 borrowOut |= (temp == 0);
 544                                 temp--;
 545                         }
 546                         *work2J = temp;
 547                         borrowIn = borrowOut;
 548                         j++;
 549                         work2J++;
 550                         k++;
 551                         work1K++;
 552                         for (; k < a.len + 1 && borrowIn; j++, work2J++, k++, work1K++) {
 553                                 borrowIn = (*work1K == 0);
 554                                 *work2J = *work1K - 1;
 555                         }
 556                         /* If the subtraction was performed successfully, set bit i2
 557                         * in block i of the quotient, and copy the changed portion of
 558                         * work2 back to work1. Otherwise, reset that bit and move on. */
 559                         if (!borrowIn) {
 560                                 *blkI |= (1 << i2);
 561                                 while (j > 0) {
 562                                         j--;
 563                                         work2J--;
 564                                         k--;
 565                                         work1K--;
 566                                         *work1K = *work2J;
 567                                 }
 568                         }
 569                 }
 570         }
 571         // Zap leading zero
 572         if (blk[len - 1] == 0)
 573                 len--;
 574         // Deallocate temporary arrays.
 575         // (Thanks to Brad Spencer for noticing my accidental omission of this!)
 576         delete [] work1;
 577         delete [] work2;
 578 }
 579
 580 // Modulo
 581 void BigUnsigned::modulo(const BigUnsigned &a, const BigUnsigned &b) {
 582         /* Note that the mathematical definition of mod is somewhat
 583         * different from the way the normal C++ % operator behaves.
 584         * This function does it the mathematical way. */
 585         // Block unsafe calls
 586         if (this == &a || this == &b)
 587                 throw "BigUnsigned::modulo: One of the arguments is the invoked object";
 588         // If b is zero, copy a and return.  By the mathematical definition,
 589         // x mod 0 = x, though the normal C++ % would throw an exception.
 590         else if (b.len == 0) {
 591                 len = 0;
 592                 return;
 593                 // If a is zero, set to zero and return.
 594         } else if (a.len < b.len) {
 595                 operator =(a);
 596                 return;
 597         }
 598         /* Overall method: Copy a into this.  Then subtract b,
 599         * shifted varying amounts to the left, from this.
 600         * When no more subtraction is possible, stop; this
 601         * will contain the remainder.
 602         * This is very similar to the division routine, except
 603         * that whether or not a subtraction succeeds is ignored,
 604         * and "this" serves the purpose of work1. */
 605         // Variables for the calculation
 606         BlkNum i, j, k;
 607         unsigned int i2;
 608         Blk bHigh, temp;
 609         bool borrowIn, borrowOut;
 610         allocate(a.len + 1);
 611         operator =(a);
 612         blk[len] = 0;
 613         // work2 holds part of the result of a subtraction
 614         Blk *work2 = new Blk[a.len + 1];
 615         // These point directly to the positions of interest in the
 616         // corresponding block arrays, for faster access.
 617         Blk *blkI, *blkK, *work2J;
 618         const Blk *bBlkJ;
 619         // For each possible left-shift of b in blocks...
 620         i = len;
 621         blkI = blk + len;
 622         while (i > 0) {
 623                 i--;
 624                 blkI--;
 625                 // For each possible left-shift of b in bits...
 626                 i2 = 8 * sizeof(Blk);
 627                 while (i2 > 0) {
 628                         i2--;
 629                         // Subtract b, shifted left i blocks and i2 bits, from work1
 630                         // and store the answer in work2.  See note in BigUnsigned::multiply.
 631                         bHigh = 0;
 632                         for (j = 0, bBlkJ = b.blk, work2J = work2, k = i, blkK = blkI,
 633                         borrowIn = false; j < b.len; j++, bBlkJ++, work2J++, k++, blkK++) {
 634                                 temp = *blkK - ((*bBlkJ << i2) | bHigh);
 635                                 borrowOut = (temp > *blkK);
 636                                 if (borrowIn) {
 637                                         borrowOut |= (temp == 0);
 638                                         temp--;
 639                                 }
 640                                 *work2J = temp;
 641                                 borrowIn = borrowOut;
 642                                 bHigh = (i2 == 0) ? 0 : *bBlkJ >> (8 * sizeof(Blk) - i2);
 643                         }
 644                         temp = *blkK - bHigh;
 645                         borrowOut = (temp > *blkK);
 646                         if (borrowIn) {
 647                                 borrowOut |= (temp == 0);
 648                                 temp--;
 649                         }
 650                         *work2J = temp;
 651                         borrowIn = borrowOut;
 652                         j++;
 653                         work2J++;
 654                         k++;
 655                         blkK++;
 656                         for (; k < a.len + 1 && borrowIn; j++, work2J++, k++, blkK++) {
 657                                 borrowIn = (*blkK == 0);
 658                                 *work2J = *blkK - 1;
 659                         }
 660                         // If the subtraction was performed successfully, set bit i2
 661                         // in block i of the quotient, and copy the changed portion of
 662                         // work2 back to this.
 663                         if (!borrowIn)
 664                         while (j > 0) {
 665                                 j--;
 666                                 work2J--;
 667                                 k--;
 668                                 blkK--;
 669                                 *blkK = *work2J;
 670                         }
 671                 }
 672         }
 673         // Blocks higher than the last block of the modulus are zero.
 674         len = b.len;
 675         // Zap leading zeros
 676         zapLeadingZeros();
 677 }
 678
 679 // Bitwise and
 680 void BigUnsigned::bitAnd(const BigUnsigned &a, const BigUnsigned &b) {
 681         // Block unsafe calls
 682         if (this == &a || this == &b)
 683                 throw "BigUnsigned::bitAnd: One of the arguments is the invoked object";
 684         len = (a.len >= b.len) ? b.len : a.len;
 685         allocate(len);
 686         BlkNum i;
 687         Blk *blkI;
 688         const Blk *aBlkI, *bBlkI;
 689         for (i = 0, blkI = blk, aBlkI = a.blk, bBlkI = b.blk;
 690         i < len; i++, blkI++, aBlkI++, bBlkI++)
 691     *blkI = *aBlkI & *bBlkI;
 692         zapLeadingZeros();
 693 }
 694
 695 // Bitwise or
 696 void BigUnsigned::bitOr(const BigUnsigned &a, const BigUnsigned &b) {
 697         // Block unsafe calls
 698         if (this == &a || this == &b)
 699                 throw "BigUnsigned::bitOr: One of the arguments is the invoked object";
 700         BlkNum i;
 701         Blk *blkI;
 702         const BigUnsigned *a2, *b2;
 703         if (a.len >= b.len) {
 704                 a2 = &a;
 705                 b2 = &b;
 706         } else {
 707                 a2 = &b;
 708                 b2 = &a;
 709         }
 710         allocate(a2->len);
 711         const Blk *a2BlkI, *b2BlkI;
 712         for (i = 0, blkI = blk, a2BlkI = a2->blk, b2BlkI = b2->blk;
 713         i < b2->len; i++, blkI++, a2BlkI++, b2BlkI++)
 714     *blkI = *a2BlkI | *b2BlkI;
 715         for (; i < a2->len; i++, blkI++, a2BlkI++)
 716                 *blkI = *a2BlkI;
 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         BlkNum i;
 726         Blk *blkI;
 727         const BigUnsigned *a2, *b2;
 728         if (a.len >= b.len) {
 729                 a2 = &a;
 730                 b2 = &b;
 731         } else {
 732                 a2 = &b;
 733                 b2 = &a;
 734         }
 735         allocate(b2->len);
 736         const Blk *a2BlkI, *b2BlkI;
 737         for (i = 0, blkI = blk, a2BlkI = a2->blk, b2BlkI = b2->blk;
 738         i < b2->len; i++, blkI++, a2BlkI++, b2BlkI++)
 739     *blkI = *a2BlkI ^ *b2BlkI;
 740         for (; i < a2->len; i++, blkI++, a2BlkI++)
 741                 *blkI = *a2BlkI;
 742         len = a2->len;
 743         zapLeadingZeros();
 744 }
 745
 746 // INCREMENT/DECREMENT OPERATORS
 747
 748 // Prefix increment
 749 void BigUnsigned::operator ++() {
 750         BlkNum i;
 751         Blk *blkI;
 752         bool carry = true;
 753         for (i = 0, blkI = blk; i < len && carry; i++) {
 754                 (*blkI)++;
 755                 carry = (*blkI == 0);
 756         }
 757         if (carry) {
 758                 allocateAndCopy(len + 1);
 759                 *blkI = 1;
 760         }
 761 }
 762
 763 // Postfix increment: same as prefix
 764 void BigUnsigned::operator ++(int) {
 765         operator ++();
 766 }
 767
 768 // Prefix decrement
 769 void BigUnsigned::operator --() {
 770         if (len == 0)
 771                 throw "BigUnsigned::operator --(): Cannot decrement an unsigned zero";
 772         BlkNum i;
 773         Blk *blkI;
 774         bool borrow = true;
 775         for (i = 0, blkI = blk; borrow; i++) {
 776                 borrow = (*blkI == 0);
 777                 (*blkI)--;
 778         }
 779         if (blk[len - 1] == 0)
 780                 len--;
 781 }
 782
 783 // Postfix decrement: same as prefix
 784 void BigUnsigned::operator --(int) {
 785         operator --();
 786 }
 787