summaryrefslogtreecommitdiff
path: root/third_party/bigint/BigUnsignedInABase.cc
diff options
context:
space:
mode:
authorBo Xu <bo_xu@foxitsoftware.com>2014-12-02 13:06:22 -0800
committerBo Xu <bo_xu@foxitsoftware.com>2014-12-02 16:57:19 -0800
commit8ad0040bbb42d7738965eea99e029145cce0b24e (patch)
tree2ebd20da7529d0f0c58618fbd2883fdb1ae71142 /third_party/bigint/BigUnsignedInABase.cc
parent610b751e894371a2933d7ba17efeee325381465d (diff)
downloadpdfium-8ad0040bbb42d7738965eea99e029145cce0b24e.tar.xz
Merge "Add big integer library""
This patch merges the 3 commits in master branch into one
Diffstat (limited to 'third_party/bigint/BigUnsignedInABase.cc')
-rw-r--r--third_party/bigint/BigUnsignedInABase.cc159
1 files changed, 159 insertions, 0 deletions
diff --git a/third_party/bigint/BigUnsignedInABase.cc b/third_party/bigint/BigUnsignedInABase.cc
new file mode 100644
index 0000000000..a24042d538
--- /dev/null
+++ b/third_party/bigint/BigUnsignedInABase.cc
@@ -0,0 +1,159 @@
+// 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 "BigUnsignedInABase.hh"
+
+BigUnsignedInABase::BigUnsignedInABase(const Digit *d, Index l, Base base)
+ : NumberlikeArray<Digit>(d, l), base(base) {
+ // Check the base
+ if (base < 2)
+#ifdef FOXIT_CHROME_BUILD
+ abort();
+#else
+ throw "BigUnsignedInABase::BigUnsignedInABase(const Digit *, Index, Base): The base must be at least 2";
+#endif
+
+ // Validate the digits.
+ for (Index i = 0; i < l; i++)
+ if (blk[i] >= base)
+#ifdef FOXIT_CHROME_BUILD
+ abort();
+#else
+ throw "BigUnsignedInABase::BigUnsignedInABase(const Digit *, Index, Base): A digit is too large for the specified base";
+#endif
+
+ // Eliminate any leading zeros we may have been passed.
+ zapLeadingZeros();
+}
+
+namespace {
+ unsigned int bitLen(unsigned int x) {
+ unsigned int len = 0;
+ while (x > 0) {
+ x >>= 1;
+ len++;
+ }
+ return len;
+ }
+ unsigned int ceilingDiv(unsigned int a, unsigned int b) {
+ return (a + b - 1) / b;
+ }
+}
+
+BigUnsignedInABase::BigUnsignedInABase(const BigUnsigned &x, Base base) {
+ // Check the base
+ if (base < 2)
+#ifdef FOXIT_CHROME_BUILD
+ abort();
+#else
+ throw "BigUnsignedInABase(BigUnsigned, Base): The base must be at least 2";
+#endif
+ this->base = base;
+
+ // Get an upper bound on how much space we need
+ int maxBitLenOfX = x.getLength() * BigUnsigned::N;
+ int minBitsPerDigit = bitLen(base) - 1;
+ int maxDigitLenOfX = ceilingDiv(maxBitLenOfX, minBitsPerDigit);
+ len = maxDigitLenOfX; // Another change to comply with `staying in bounds'.
+ allocate(len); // Get the space
+
+ BigUnsigned x2(x), buBase(base);
+ Index digitNum = 0;
+
+ while (!x2.isZero()) {
+ // Get last digit. This is like `lastDigit = x2 % buBase, x2 /= buBase'.
+ BigUnsigned lastDigit(x2);
+ lastDigit.divideWithRemainder(buBase, x2);
+ // Save the digit.
+ blk[digitNum] = lastDigit.toUnsignedShort();
+ // Move on. We can't run out of room: we figured it out above.
+ digitNum++;
+ }
+
+ // Save the actual length.
+ len = digitNum;
+}
+
+BigUnsignedInABase::operator BigUnsigned() const {
+ BigUnsigned ans(0), buBase(base), temp;
+ Index digitNum = len;
+ while (digitNum > 0) {
+ digitNum--;
+ temp.multiply(ans, buBase);
+ ans.add(temp, BigUnsigned(blk[digitNum]));
+ }
+ return ans;
+}
+
+BigUnsignedInABase::BigUnsignedInABase(const std::string &s, Base base) {
+ // Check the base.
+ if (base > 36)
+#ifdef FOXIT_CHROME_BUILD
+ abort();
+#else
+ throw "BigUnsignedInABase(std::string, Base): The default string conversion routines use the symbol set 0-9, A-Z and therefore support only up to base 36. You tried a conversion with a base over 36; write your own string conversion routine.";
+#endif
+ // Save the base.
+ // This pattern is seldom seen in C++, but the analogous ``this.'' is common in Java.
+ this->base = base;
+
+ // `s.length()' is a `size_t', while `len' is a `NumberlikeArray::Index',
+ // also known as an `unsigned int'. Some compilers warn without this cast.
+ len = Index(s.length());
+ allocate(len);
+
+ Index digitNum, symbolNumInString;
+ for (digitNum = 0; digitNum < len; digitNum++) {
+ symbolNumInString = len - 1 - digitNum;
+ char theSymbol = s[symbolNumInString];
+ if (theSymbol >= '0' && theSymbol <= '9')
+ blk[digitNum] = theSymbol - '0';
+ else if (theSymbol >= 'A' && theSymbol <= 'Z')
+ blk[digitNum] = theSymbol - 'A' + 10;
+ else if (theSymbol >= 'a' && theSymbol <= 'z')
+ blk[digitNum] = theSymbol - 'a' + 10;
+ else
+#ifdef FOXIT_CHROME_BUILD
+ abort();
+#else
+ throw "BigUnsignedInABase(std::string, Base): Bad symbol in input. Only 0-9, A-Z, a-z are accepted.";
+#endif
+
+ if (blk[digitNum] >= base)
+#ifdef FOXIT_CHROME_BUILD
+ abort();
+#else
+ throw "BigUnsignedInABase::BigUnsignedInABase(const Digit *, Index, Base): A digit is too large for the specified base";
+#endif
+ }
+ zapLeadingZeros();
+}
+
+BigUnsignedInABase::operator std::string() const {
+ if (base > 36)
+#ifdef FOXIT_CHROME_BUILD
+ abort();
+#else
+ throw "BigUnsignedInABase ==> std::string: The default string conversion routines use the symbol set 0-9, A-Z and therefore support only up to base 36. You tried a conversion with a base over 36; write your own string conversion routine.";
+#endif
+ if (len == 0)
+ return std::string("0");
+ // Some compilers don't have push_back, so use a char * buffer instead.
+ char *s = new char[len + 1];
+ s[len] = '\0';
+ Index digitNum, symbolNumInString;
+ for (symbolNumInString = 0; symbolNumInString < len; symbolNumInString++) {
+ digitNum = len - 1 - symbolNumInString;
+ Digit theDigit = blk[digitNum];
+ if (theDigit < 10)
+ s[symbolNumInString] = char('0' + theDigit);
+ else
+ s[symbolNumInString] = char('A' + theDigit - 10);
+ }
+ std::string s2(s);
+ delete [] s;
+ return s2;
+}