// Copyright 2014 The PDFium Authors // 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) { … } BigUnsigned::BigUnsigned(unsigned int x) { … } BigUnsigned::BigUnsigned(unsigned short x) { … } BigUnsigned::BigUnsigned( long x) { … } BigUnsigned::BigUnsigned( int x) { … } BigUnsigned::BigUnsigned( short x) { … } unsigned long BigUnsigned::toUnsignedLong () const { … } unsigned int BigUnsigned::toUnsignedInt () const { … } unsigned short BigUnsigned::toUnsignedShort() const { … } long BigUnsigned::toLong () const { … } int BigUnsigned::toInt () const { … } short BigUnsigned::toShort () const { … } // BIT/BLOCK ACCESSORS void BigUnsigned::setBlock(Index i, Blk 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 { … } void BigUnsigned::setBit(Index bi, bool newBit) { … } // COMPARISON BigUnsigned::CmpRes BigUnsigned::compareTo(const BigUnsigned &x) const { … } // 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) … void BigUnsigned::add(const BigUnsigned &a, const BigUnsigned &b) { … } void BigUnsigned::subtract(const BigUnsigned &a, const BigUnsigned &b) { … } /* * 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) { … } void BigUnsigned::multiply(const BigUnsigned &a, const BigUnsigned &b) { … } /* * 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) { … } /* 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) { … } void BigUnsigned::bitOr(const BigUnsigned &a, const BigUnsigned &b) { … } void BigUnsigned::bitXor(const BigUnsigned &a, const BigUnsigned &b) { … } void BigUnsigned::bitShiftLeft(const BigUnsigned &a, int b) { … } void BigUnsigned::bitShiftRight(const BigUnsigned &a, int b) { … } // INCREMENT/DECREMENT OPERATORS // Prefix increment BigUnsigned& BigUnsigned::operator ++() { … } // Postfix increment BigUnsigned BigUnsigned::operator ++(int) { … } // Prefix decrement BigUnsigned& BigUnsigned::operator --() { … } // Postfix decrement BigUnsigned BigUnsigned::operator --(int) { … }
Codebase Browser
chromium