1 // Copyright 2014 PDFium Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4
5 // Original code by Matt McCutchen, see the LICENSE file.
6
7 #include "BigUnsignedInABase.hh"
8
BigUnsignedInABase(const Digit * d,Index l,Base base)9 BigUnsignedInABase::BigUnsignedInABase(const Digit *d, Index l, Base base)
10 : NumberlikeArray<Digit>(d, l), base(base) {
11 // Check the base
12 if (base < 2)
13 abort();
14
15 // Validate the digits.
16 for (Index i = 0; i < l; i++)
17 if (blk[i] >= base)
18 abort();
19
20 // Eliminate any leading zeros we may have been passed.
21 zapLeadingZeros();
22 }
23
24 namespace {
bitLen(unsigned int x)25 unsigned int bitLen(unsigned int x) {
26 unsigned int len = 0;
27 while (x > 0) {
28 x >>= 1;
29 len++;
30 }
31 return len;
32 }
ceilingDiv(unsigned int a,unsigned int b)33 unsigned int ceilingDiv(unsigned int a, unsigned int b) {
34 return (a + b - 1) / b;
35 }
36 }
37
BigUnsignedInABase(const BigUnsigned & x,Base base)38 BigUnsignedInABase::BigUnsignedInABase(const BigUnsigned &x, Base base) {
39 // Check the base
40 if (base < 2)
41 abort();
42 this->base = base;
43
44 // Get an upper bound on how much space we need
45 int maxBitLenOfX = x.getLength() * BigUnsigned::N;
46 int minBitsPerDigit = bitLen(base) - 1;
47 int maxDigitLenOfX = ceilingDiv(maxBitLenOfX, minBitsPerDigit);
48 len = maxDigitLenOfX; // Another change to comply with `staying in bounds'.
49 allocate(len); // Get the space
50
51 BigUnsigned x2(x), buBase(base);
52 Index digitNum = 0;
53
54 while (!x2.isZero()) {
55 // Get last digit. This is like `lastDigit = x2 % buBase, x2 /= buBase'.
56 BigUnsigned lastDigit(x2);
57 lastDigit.divideWithRemainder(buBase, x2);
58 // Save the digit.
59 blk[digitNum] = lastDigit.toUnsignedShort();
60 // Move on. We can't run out of room: we figured it out above.
61 digitNum++;
62 }
63
64 // Save the actual length.
65 len = digitNum;
66 }
67
operator BigUnsigned() const68 BigUnsignedInABase::operator BigUnsigned() const {
69 BigUnsigned ans(0), buBase(base), temp;
70 Index digitNum = len;
71 while (digitNum > 0) {
72 digitNum--;
73 temp.multiply(ans, buBase);
74 ans.add(temp, BigUnsigned(blk[digitNum]));
75 }
76 return ans;
77 }
78
BigUnsignedInABase(const std::string & s,Base base)79 BigUnsignedInABase::BigUnsignedInABase(const std::string &s, Base base) {
80 // Check the base.
81 if (base > 36)
82 abort();
83 // Save the base.
84 // This pattern is seldom seen in C++, but the analogous ``this.'' is common in Java.
85 this->base = base;
86
87 // `s.length()' is a `size_t', while `len' is a `NumberlikeArray::Index',
88 // also known as an `unsigned int'. Some compilers warn without this cast.
89 len = Index(s.length());
90 allocate(len);
91
92 Index digitNum, symbolNumInString;
93 for (digitNum = 0; digitNum < len; digitNum++) {
94 symbolNumInString = len - 1 - digitNum;
95 char theSymbol = s[symbolNumInString];
96 if (theSymbol >= '0' && theSymbol <= '9')
97 blk[digitNum] = theSymbol - '0';
98 else if (theSymbol >= 'A' && theSymbol <= 'Z')
99 blk[digitNum] = theSymbol - 'A' + 10;
100 else if (theSymbol >= 'a' && theSymbol <= 'z')
101 blk[digitNum] = theSymbol - 'a' + 10;
102 else
103 abort();
104
105 if (blk[digitNum] >= base)
106 abort();
107 }
108 zapLeadingZeros();
109 }
110
operator std::string() const111 BigUnsignedInABase::operator std::string() const {
112 if (base > 36)
113 abort();
114 if (len == 0)
115 return std::string("0");
116 // Some compilers don't have push_back, so use a char * buffer instead.
117 char *s = new char[len + 1];
118 s[len] = '\0';
119 Index digitNum, symbolNumInString;
120 for (symbolNumInString = 0; symbolNumInString < len; symbolNumInString++) {
121 digitNum = len - 1 - symbolNumInString;
122 Digit theDigit = blk[digitNum];
123 if (theDigit < 10)
124 s[symbolNumInString] = char('0' + theDigit);
125 else
126 s[symbolNumInString] = char('A' + theDigit - 10);
127 }
128 std::string s2(s);
129 delete [] s;
130 return s2;
131 }
132