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