pdfium / pdfium / 40d12fbacc27d41dd631f0920f50806ce9bad638 / . / third_party / bigint / BigUnsigned.cc

// Copyright 2014 PDFium Authors. All rights reserved. | |

// Use of this source code is governed by a BSD-style license that can be | |

// found in the LICENSE file. | |

// Original code by Matt McCutchen, see the LICENSE file. | |

#include "BigUnsigned.hh" | |

// Memory management definitions have moved to the bottom of NumberlikeArray.hh. | |

// The templates used by these constructors and converters are at the bottom of | |

// BigUnsigned.hh. | |

BigUnsigned::BigUnsigned(unsigned long x) { initFromPrimitive (x); } | |

BigUnsigned::BigUnsigned(unsigned int x) { initFromPrimitive (x); } | |

BigUnsigned::BigUnsigned(unsigned short x) { initFromPrimitive (x); } | |

BigUnsigned::BigUnsigned( long x) { initFromSignedPrimitive(x); } | |

BigUnsigned::BigUnsigned( int x) { initFromSignedPrimitive(x); } | |

BigUnsigned::BigUnsigned( short x) { initFromSignedPrimitive(x); } | |

unsigned long BigUnsigned::toUnsignedLong () const { return convertToPrimitive <unsigned long >(); } | |

unsigned int BigUnsigned::toUnsignedInt () const { return convertToPrimitive <unsigned int >(); } | |

unsigned short BigUnsigned::toUnsignedShort() const { return convertToPrimitive <unsigned short>(); } | |

long BigUnsigned::toLong () const { return convertToSignedPrimitive< long >(); } | |

int BigUnsigned::toInt () const { return convertToSignedPrimitive< int >(); } | |

short BigUnsigned::toShort () const { return convertToSignedPrimitive< short>(); } | |

// BIT/BLOCK ACCESSORS | |

void BigUnsigned::setBlock(Index i, Blk newBlock) { | |

if (newBlock == 0) { | |

if (i < len) { | |

blk[i] = 0; | |

zapLeadingZeros(); | |

} | |

// If i >= len, no effect. | |

} else { | |

if (i >= len) { | |

// The nonzero block extends the number. | |

allocateAndCopy(i+1); | |

// Zero any added blocks that we aren't setting. | |

for (Index j = len; j < i; j++) | |

blk[j] = 0; | |

len = i+1; | |

} | |

blk[i] = newBlock; | |

} | |

} | |

/* Evidently the compiler wants BigUnsigned:: on the return type because, at | |

* that point, it hasn't yet parsed the BigUnsigned:: on the name to get the | |

* proper scope. */ | |

BigUnsigned::Index BigUnsigned::bitLength() const { | |

if (isZero()) | |

return 0; | |

else { | |

Blk leftmostBlock = getBlock(len - 1); | |

Index leftmostBlockLen = 0; | |

while (leftmostBlock != 0) { | |

leftmostBlock >>= 1; | |

leftmostBlockLen++; | |

} | |

return leftmostBlockLen + (len - 1) * N; | |

} | |

} | |

void BigUnsigned::setBit(Index bi, bool newBit) { | |

Index blockI = bi / N; | |

Blk block = getBlock(blockI), mask = Blk(1) << (bi % N); | |

block = newBit ? (block | mask) : (block & ~mask); | |

setBlock(blockI, block); | |

} | |

// COMPARISON | |

BigUnsigned::CmpRes BigUnsigned::compareTo(const BigUnsigned &x) const { | |

// A bigger length implies a bigger number. | |

if (len < x.len) | |

return less; | |

else if (len > x.len) | |

return greater; | |

else { | |

// Compare blocks one by one from left to right. | |

Index i = len; | |

while (i > 0) { | |

i--; | |

if (blk[i] == x.blk[i]) | |

continue; | |

else if (blk[i] > x.blk[i]) | |

return greater; | |

else | |

return less; | |

} | |

// If no blocks differed, the numbers are equal. | |

return equal; | |

} | |

} | |

// COPY-LESS OPERATIONS | |

/* | |

* On most calls to copy-less operations, it's safe to read the inputs little by | |

* little and write the outputs little by little. However, if one of the | |

* inputs is coming from the same variable into which the output is to be | |

* stored (an "aliased" call), we risk overwriting the input before we read it. | |

* In this case, we first compute the result into a temporary BigUnsigned | |

* variable and then copy it into the requested output variable *this. | |

* Each put-here operation uses the DTRT_ALIASED macro (Do The Right Thing on | |

* aliased calls) to generate code for this check. | |

* | |

* I adopted this approach on 2007.02.13 (see Assignment Operators in | |

* BigUnsigned.hh). Before then, put-here operations rejected aliased calls | |

* with an exception. I think doing the right thing is better. | |

* | |

* Some of the put-here operations can probably handle aliased calls safely | |

* without the extra copy because (for example) they process blocks strictly | |

* right-to-left. At some point I might determine which ones don't need the | |

* copy, but my reasoning would need to be verified very carefully. For now | |

* I'll leave in the copy. | |

*/ | |

#define DTRT_ALIASED(cond, op) \ | |

if (cond) { \ | |

BigUnsigned tmpThis; \ | |

tmpThis.op; \ | |

*this = tmpThis; \ | |

return; \ | |

} | |

void BigUnsigned::add(const BigUnsigned &a, const BigUnsigned &b) { | |

DTRT_ALIASED(this == &a || this == &b, add(a, b)); | |

// If one argument is zero, copy the other. | |

if (a.len == 0) { | |

operator =(b); | |

return; | |

} else if (b.len == 0) { | |

operator =(a); | |

return; | |

} | |

// Some variables... | |

// Carries in and out of an addition stage | |

bool carryIn, carryOut; | |

Blk temp; | |

Index i; | |

// a2 points to the longer input, b2 points to the shorter | |

const BigUnsigned *a2, *b2; | |

if (a.len >= b.len) { | |

a2 = &a; | |

b2 = &b; | |

} else { | |

a2 = &b; | |

b2 = &a; | |

} | |

// Set prelimiary length and make room in this BigUnsigned | |

len = a2->len + 1; | |

allocate(len); | |

// For each block index that is present in both inputs... | |

for (i = 0, carryIn = false; i < b2->len; i++) { | |

// Add input blocks | |

temp = a2->blk[i] + b2->blk[i]; | |

// If a rollover occurred, the result is less than either input. | |

// This test is used many times in the BigUnsigned code. | |

carryOut = (temp < a2->blk[i]); | |

// If a carry was input, handle it | |

if (carryIn) { | |

temp++; | |

carryOut |= (temp == 0); | |

} | |

blk[i] = temp; // Save the addition result | |

carryIn = carryOut; // Pass the carry along | |

} | |

// If there is a carry left over, increase blocks until | |

// one does not roll over. | |

for (; i < a2->len && carryIn; i++) { | |

temp = a2->blk[i] + 1; | |

carryIn = (temp == 0); | |

blk[i] = temp; | |

} | |

// If the carry was resolved but the larger number | |

// still has blocks, copy them over. | |

for (; i < a2->len; i++) | |

blk[i] = a2->blk[i]; | |

// Set the extra block if there's still a carry, decrease length otherwise | |

if (carryIn) | |

blk[i] = 1; | |

else | |

len--; | |

} | |

void BigUnsigned::subtract(const BigUnsigned &a, const BigUnsigned &b) { | |

DTRT_ALIASED(this == &a || this == &b, subtract(a, b)); | |

if (b.len == 0) { | |

// If b is zero, copy a. | |

operator =(a); | |

return; | |

} else if (a.len < b.len) | |

// If a is shorter than b, the result is negative. | |

abort(); | |

// Some variables... | |

bool borrowIn, borrowOut; | |

Blk temp; | |

Index i; | |

// Set preliminary length and make room | |

len = a.len; | |

allocate(len); | |

// For each block index that is present in both inputs... | |

for (i = 0, borrowIn = false; i < b.len; i++) { | |

temp = a.blk[i] - b.blk[i]; | |

// If a reverse rollover occurred, | |

// the result is greater than the block from a. | |

borrowOut = (temp > a.blk[i]); | |

// Handle an incoming borrow | |

if (borrowIn) { | |

borrowOut |= (temp == 0); | |

temp--; | |

} | |

blk[i] = temp; // Save the subtraction result | |

borrowIn = borrowOut; // Pass the borrow along | |

} | |

// If there is a borrow left over, decrease blocks until | |

// one does not reverse rollover. | |

for (; i < a.len && borrowIn; i++) { | |

borrowIn = (a.blk[i] == 0); | |

blk[i] = a.blk[i] - 1; | |

} | |

/* If there's still a borrow, the result is negative. | |

* Throw an exception, but zero out this object so as to leave it in a | |

* predictable state. */ | |

if (borrowIn) { | |

len = 0; | |

abort(); | |

} else | |

// Copy over the rest of the blocks | |

for (; i < a.len; i++) | |

blk[i] = a.blk[i]; | |

// Zap leading zeros | |

zapLeadingZeros(); | |

} | |

/* | |

* About the multiplication and division algorithms: | |

* | |

* I searched unsucessfully for fast C++ built-in operations like the `b_0' | |

* and `c_0' Knuth describes in Section 4.3.1 of ``The Art of Computer | |

* Programming'' (replace `place' by `Blk'): | |

* | |

* ``b_0[:] multiplication of a one-place integer by another one-place | |

* integer, giving a two-place answer; | |

* | |

* ``c_0[:] division of a two-place integer by a one-place integer, | |

* provided that the quotient is a one-place integer, and yielding | |

* also a one-place remainder.'' | |

* | |

* I also missed his note that ``[b]y adjusting the word size, if | |

* necessary, nearly all computers will have these three operations | |

* available'', so I gave up on trying to use algorithms similar to his. | |

* A future version of the library might include such algorithms; I | |

* would welcome contributions from others for this. | |

* | |

* I eventually decided to use bit-shifting algorithms. To multiply `a' | |

* and `b', we zero out the result. Then, for each `1' bit in `a', we | |

* shift `b' left the appropriate amount and add it to the result. | |

* Similarly, to divide `a' by `b', we shift `b' left varying amounts, | |

* repeatedly trying to subtract it from `a'. When we succeed, we note | |

* the fact by setting a bit in the quotient. While these algorithms | |

* have the same O(n^2) time complexity as Knuth's, the ``constant factor'' | |

* is likely to be larger. | |

* | |

* Because I used these algorithms, which require single-block addition | |

* and subtraction rather than single-block multiplication and division, | |

* the innermost loops of all four routines are very similar. Study one | |

* of them and all will become clear. | |

*/ | |

/* | |

* This is a little inline function used by both the multiplication | |

* routine and the division routine. | |

* | |

* `getShiftedBlock' returns the `x'th block of `num << y'. | |

* `y' may be anything from 0 to N - 1, and `x' may be anything from | |

* 0 to `num.len'. | |

* | |

* Two things contribute to this block: | |

* | |

* (1) The `N - y' low bits of `num.blk[x]', shifted `y' bits left. | |

* | |

* (2) The `y' high bits of `num.blk[x-1]', shifted `N - y' bits right. | |

* | |

* But we must be careful if `x == 0' or `x == num.len', in | |

* which case we should use 0 instead of (2) or (1), respectively. | |

* | |

* If `y == 0', then (2) contributes 0, as it should. However, | |

* in some computer environments, for a reason I cannot understand, | |

* `a >> b' means `a >> (b % N)'. This means `num.blk[x-1] >> (N - y)' | |

* will return `num.blk[x-1]' instead of the desired 0 when `y == 0'; | |

* the test `y == 0' handles this case specially. | |

*/ | |

inline BigUnsigned::Blk getShiftedBlock(const BigUnsigned &num, | |

BigUnsigned::Index x, unsigned int y) { | |

BigUnsigned::Blk part1 = (x == 0 || y == 0) ? 0 : (num.blk[x - 1] >> (BigUnsigned::N - y)); | |

BigUnsigned::Blk part2 = (x == num.len) ? 0 : (num.blk[x] << y); | |

return part1 | part2; | |

} | |

void BigUnsigned::multiply(const BigUnsigned &a, const BigUnsigned &b) { | |

DTRT_ALIASED(this == &a || this == &b, multiply(a, b)); | |

// If either a or b is zero, set to zero. | |

if (a.len == 0 || b.len == 0) { | |

len = 0; | |

return; | |

} | |

/* | |

* Overall method: | |

* | |

* Set this = 0. | |

* For each 1-bit of `a' (say the `i2'th bit of block `i'): | |

* Add `b << (i blocks and i2 bits)' to *this. | |

*/ | |

// Variables for the calculation | |

Index i, j, k; | |

unsigned int i2; | |

Blk temp; | |

bool carryIn, carryOut; | |

// Set preliminary length and make room | |

len = a.len + b.len; | |

allocate(len); | |

// Zero out this object | |

for (i = 0; i < len; i++) | |

blk[i] = 0; | |

// For each block of the first number... | |

for (i = 0; i < a.len; i++) { | |

// For each 1-bit of that block... | |

for (i2 = 0; i2 < N; i2++) { | |

if ((a.blk[i] & (Blk(1) << i2)) == 0) | |

continue; | |

/* | |

* Add b to this, shifted left i blocks and i2 bits. | |

* j is the index in b, and k = i + j is the index in this. | |

* | |

* `getShiftedBlock', a short inline function defined above, | |

* is now used for the bit handling. It replaces the more | |

* complex `bHigh' code, in which each run of the loop dealt | |

* immediately with the low bits and saved the high bits to | |

* be picked up next time. The last run of the loop used to | |

* leave leftover high bits, which were handled separately. | |

* Instead, this loop runs an additional time with j == b.len. | |

* These changes were made on 2005.01.11. | |

*/ | |

for (j = 0, k = i, carryIn = false; j <= b.len; j++, k++) { | |

/* | |

* The body of this loop is very similar to the body of the first loop | |

* in `add', except that this loop does a `+=' instead of a `+'. | |

*/ | |

temp = blk[k] + getShiftedBlock(b, j, i2); | |

carryOut = (temp < blk[k]); | |

if (carryIn) { | |

temp++; | |

carryOut |= (temp == 0); | |

} | |

blk[k] = temp; | |

carryIn = carryOut; | |

} | |

// No more extra iteration to deal with `bHigh'. | |

// Roll-over a carry as necessary. | |

for (; carryIn; k++) { | |

blk[k]++; | |

carryIn = (blk[k] == 0); | |

} | |

} | |

} | |

// Zap possible leading zero | |

if (blk[len - 1] == 0) | |

len--; | |

} | |

/* | |

* DIVISION WITH REMAINDER | |

* This monstrous function mods *this by the given divisor b while storing the | |

* quotient in the given object q; at the end, *this contains the remainder. | |

* The seemingly bizarre pattern of inputs and outputs was chosen so that the | |

* function copies as little as possible (since it is implemented by repeated | |

* subtraction of multiples of b from *this). | |

* | |

* "modWithQuotient" might be a better name for this function, but I would | |

* rather not change the name now. | |

*/ | |

void BigUnsigned::divideWithRemainder(const BigUnsigned &b, BigUnsigned &q) { | |

/* Defending against aliased calls is more complex than usual because we | |

* are writing to both *this and q. | |

* | |

* It would be silly to try to write quotient and remainder to the | |

* same variable. Rule that out right away. */ | |

if (this == &q) | |

abort(); | |

/* Now *this and q are separate, so the only concern is that b might be | |

* aliased to one of them. If so, use a temporary copy of b. */ | |

if (this == &b || &q == &b) { | |

BigUnsigned tmpB(b); | |

divideWithRemainder(tmpB, q); | |

return; | |

} | |

/* | |

* Knuth's definition of mod (which this function uses) is somewhat | |

* different from the C++ definition of % in case of division by 0. | |

* | |

* We let a / 0 == 0 (it doesn't matter much) and a % 0 == a, no | |

* exceptions thrown. This allows us to preserve both Knuth's demand | |

* that a mod 0 == a and the useful property that | |

* (a / b) * b + (a % b) == a. | |

*/ | |

if (b.len == 0) { | |

q.len = 0; | |

return; | |

} | |

/* | |

* If *this.len < b.len, then *this < b, and we can be sure that b doesn't go into | |

* *this at all. The quotient is 0 and *this is already the remainder (so leave it alone). | |

*/ | |

if (len < b.len) { | |

q.len = 0; | |

return; | |

} | |

// At this point we know (*this).len >= b.len > 0. (Whew!) | |

/* | |

* Overall method: | |

* | |

* For each appropriate i and i2, decreasing: | |

* Subtract (b << (i blocks and i2 bits)) from *this, storing the | |

* result in subtractBuf. | |

* If the subtraction succeeds with a nonnegative result: | |

* Turn on bit i2 of block i of the quotient q. | |

* Copy subtractBuf back into *this. | |

* Otherwise bit i2 of block i remains off, and *this is unchanged. | |

* | |

* Eventually q will contain the entire quotient, and *this will | |

* be left with the remainder. | |

* | |

* subtractBuf[x] corresponds to blk[x], not blk[x+i], since 2005.01.11. | |

* But on a single iteration, we don't touch the i lowest blocks of blk | |

* (and don't use those of subtractBuf) because these blocks are | |

* unaffected by the subtraction: we are subtracting | |

* (b << (i blocks and i2 bits)), which ends in at least `i' zero | |

* blocks. */ | |

// Variables for the calculation | |

Index i, j, k; | |

unsigned int i2; | |

Blk temp; | |

bool borrowIn, borrowOut; | |

/* | |

* Make sure we have an extra zero block just past the value. | |

* | |

* When we attempt a subtraction, we might shift `b' so | |

* its first block begins a few bits left of the dividend, | |

* and then we'll try to compare these extra bits with | |

* a nonexistent block to the left of the dividend. The | |

* extra zero block ensures sensible behavior; we need | |

* an extra block in `subtractBuf' for exactly the same reason. | |

*/ | |

Index origLen = len; // Save real length. | |

/* To avoid an out-of-bounds access in case of reallocation, allocate | |

* first and then increment the logical length. */ | |

allocateAndCopy(len + 1); | |

len++; | |

blk[origLen] = 0; // Zero the added block. | |

// subtractBuf holds part of the result of a subtraction; see above. | |

Blk *subtractBuf = new Blk[len]; | |

// Set preliminary length for quotient and make room | |

q.len = origLen - b.len + 1; | |

q.allocate(q.len); | |

// Zero out the quotient | |

for (i = 0; i < q.len; i++) | |

q.blk[i] = 0; | |

// For each possible left-shift of b in blocks... | |

i = q.len; | |

while (i > 0) { | |

i--; | |

// For each possible left-shift of b in bits... | |

// (Remember, N is the number of bits in a Blk.) | |

q.blk[i] = 0; | |

i2 = N; | |

while (i2 > 0) { | |

i2--; | |

/* | |

* Subtract b, shifted left i blocks and i2 bits, from *this, | |

* and store the answer in subtractBuf. In the for loop, `k == i + j'. | |

* | |

* Compare this to the middle section of `multiply'. They | |

* are in many ways analogous. See especially the discussion | |

* of `getShiftedBlock'. | |

*/ | |

for (j = 0, k = i, borrowIn = false; j <= b.len; j++, k++) { | |

temp = blk[k] - getShiftedBlock(b, j, i2); | |

borrowOut = (temp > blk[k]); | |

if (borrowIn) { | |

borrowOut |= (temp == 0); | |

temp--; | |

} | |

// Since 2005.01.11, indices of `subtractBuf' directly match those of `blk', so use `k'. | |

subtractBuf[k] = temp; | |

borrowIn = borrowOut; | |

} | |

// No more extra iteration to deal with `bHigh'. | |

// Roll-over a borrow as necessary. | |

for (; k < origLen && borrowIn; k++) { | |

borrowIn = (blk[k] == 0); | |

subtractBuf[k] = blk[k] - 1; | |

} | |

/* | |

* If the subtraction was performed successfully (!borrowIn), | |

* set bit i2 in block i of the quotient. | |

* | |

* Then, copy the portion of subtractBuf filled by the subtraction | |

* back to *this. This portion starts with block i and ends-- | |

* where? Not necessarily at block `i + b.len'! Well, we | |

* increased k every time we saved a block into subtractBuf, so | |

* the region of subtractBuf we copy is just [i, k). | |

*/ | |

if (!borrowIn) { | |

q.blk[i] |= (Blk(1) << i2); | |

while (k > i) { | |

k--; | |

blk[k] = subtractBuf[k]; | |

} | |

} | |

} | |

} | |

// Zap possible leading zero in quotient | |

if (q.blk[q.len - 1] == 0) | |

q.len--; | |

// Zap any/all leading zeros in remainder | |

zapLeadingZeros(); | |

// Deallocate subtractBuf. | |

// (Thanks to Brad Spencer for noticing my accidental omission of this!) | |

delete [] subtractBuf; | |

} | |

/* BITWISE OPERATORS | |

* These are straightforward blockwise operations except that they differ in | |

* the output length and the necessity of zapLeadingZeros. */ | |

void BigUnsigned::bitAnd(const BigUnsigned &a, const BigUnsigned &b) { | |

DTRT_ALIASED(this == &a || this == &b, bitAnd(a, b)); | |

// The bitwise & can't be longer than either operand. | |

len = (a.len >= b.len) ? b.len : a.len; | |

allocate(len); | |

Index i; | |

for (i = 0; i < len; i++) | |

blk[i] = a.blk[i] & b.blk[i]; | |

zapLeadingZeros(); | |

} | |

void BigUnsigned::bitOr(const BigUnsigned &a, const BigUnsigned &b) { | |

DTRT_ALIASED(this == &a || this == &b, bitOr(a, b)); | |

Index i; | |

const BigUnsigned *a2, *b2; | |

if (a.len >= b.len) { | |

a2 = &a; | |

b2 = &b; | |

} else { | |

a2 = &b; | |

b2 = &a; | |

} | |

allocate(a2->len); | |

for (i = 0; i < b2->len; i++) | |

blk[i] = a2->blk[i] | b2->blk[i]; | |

for (; i < a2->len; i++) | |

blk[i] = a2->blk[i]; | |

len = a2->len; | |

// Doesn't need zapLeadingZeros. | |

} | |

void BigUnsigned::bitXor(const BigUnsigned &a, const BigUnsigned &b) { | |

DTRT_ALIASED(this == &a || this == &b, bitXor(a, b)); | |

Index i; | |

const BigUnsigned *a2, *b2; | |

if (a.len >= b.len) { | |

a2 = &a; | |

b2 = &b; | |

} else { | |

a2 = &b; | |

b2 = &a; | |

} | |

allocate(a2->len); | |

for (i = 0; i < b2->len; i++) | |

blk[i] = a2->blk[i] ^ b2->blk[i]; | |

for (; i < a2->len; i++) | |

blk[i] = a2->blk[i]; | |

len = a2->len; | |

zapLeadingZeros(); | |

} | |

void BigUnsigned::bitShiftLeft(const BigUnsigned &a, int b) { | |

DTRT_ALIASED(this == &a, bitShiftLeft(a, b)); | |

if (b < 0) { | |

if (b << 1 == 0) | |

abort(); | |

else { | |

bitShiftRight(a, -b); | |

return; | |

} | |

} | |

Index shiftBlocks = b / N; | |

unsigned int shiftBits = b % N; | |

// + 1: room for high bits nudged left into another block | |

len = a.len + shiftBlocks + 1; | |

allocate(len); | |

Index i, j; | |

for (i = 0; i < shiftBlocks; i++) | |

blk[i] = 0; | |

for (j = 0, i = shiftBlocks; j <= a.len; j++, i++) | |

blk[i] = getShiftedBlock(a, j, shiftBits); | |

// Zap possible leading zero | |

if (blk[len - 1] == 0) | |

len--; | |

} | |

void BigUnsigned::bitShiftRight(const BigUnsigned &a, int b) { | |

DTRT_ALIASED(this == &a, bitShiftRight(a, b)); | |

if (b < 0) { | |

if (b << 1 == 0) | |

abort(); | |

else { | |

bitShiftLeft(a, -b); | |

return; | |

} | |

} | |

// This calculation is wacky, but expressing the shift as a left bit shift | |

// within each block lets us use getShiftedBlock. | |

Index rightShiftBlocks = (b + N - 1) / N; | |

unsigned int leftShiftBits = N * rightShiftBlocks - b; | |

// Now (N * rightShiftBlocks - leftShiftBits) == b | |

// and 0 <= leftShiftBits < N. | |

if (rightShiftBlocks >= a.len + 1) { | |

// All of a is guaranteed to be shifted off, even considering the left | |

// bit shift. | |

len = 0; | |

return; | |

} | |

// Now we're allocating a positive amount. | |

// + 1: room for high bits nudged left into another block | |

len = a.len + 1 - rightShiftBlocks; | |

allocate(len); | |

Index i, j; | |

for (j = rightShiftBlocks, i = 0; j <= a.len; j++, i++) | |

blk[i] = getShiftedBlock(a, j, leftShiftBits); | |

// Zap possible leading zero | |

if (blk[len - 1] == 0) | |

len--; | |

} | |

// INCREMENT/DECREMENT OPERATORS | |

// Prefix increment | |

BigUnsigned& BigUnsigned::operator ++() { | |

Index i; | |

bool carry = true; | |

for (i = 0; i < len && carry; i++) { | |

blk[i]++; | |

carry = (blk[i] == 0); | |

} | |

if (carry) { | |

// Allocate and then increase length, as in divideWithRemainder | |

allocateAndCopy(len + 1); | |

len++; | |

blk[i] = 1; | |

} | |

return *this; | |

} | |

// Postfix increment | |

BigUnsigned BigUnsigned::operator ++(int) { | |

BigUnsigned temp(*this); | |

operator ++(); | |

return temp; | |

} | |

// Prefix decrement | |

BigUnsigned& BigUnsigned::operator --() { | |

if (len == 0) | |

abort(); | |

Index i; | |

bool borrow = true; | |

for (i = 0; borrow; i++) { | |

borrow = (blk[i] == 0); | |

blk[i]--; | |

} | |

// Zap possible leading zero (there can only be one) | |

if (blk[len - 1] == 0) | |

len--; | |

return *this; | |

} | |

// Postfix decrement | |

BigUnsigned BigUnsigned::operator --(int) { | |

BigUnsigned temp(*this); | |

operator --(); | |

return temp; | |

} |