Commit | Line | Data |
---|---|---|
05780f4b MM |
1 | /* |
2 | * Matt McCutchen's Big Integer Library | |
3 | * http://mysite.verizon.net/mccutchen/bigint/ | |
4 | */ | |
5 | ||
6 | #include "BigUnsignedInABase.hh" | |
7 | ||
8 | namespace { | |
9 | unsigned int bitLen(unsigned int x) { | |
10 | unsigned int len = 0; | |
11 | while (x > 0) { | |
12 | x >>= 1; | |
13 | len++; | |
14 | } | |
15 | return len; | |
16 | } | |
17 | unsigned int ceilingDiv(unsigned int a, unsigned int b) { | |
18 | return (a + b - 1) / b; | |
19 | } | |
20 | } | |
21 | ||
22 | BigUnsignedInABase::BigUnsignedInABase(const BigUnsigned &x, Base base) { | |
23 | // Check the base | |
24 | if (base < 2) | |
25 | throw "BigUnsignedInABase(BigUnsigned, Base): The base must be at least 2"; | |
26 | // Save the base. | |
27 | // This pattern is seldom seen in C++, but the analogous ``this.'' is common in Java. | |
28 | this->base = base; | |
29 | ||
30 | // Get an upper bound on how much space we need | |
31 | int maxBitLenOfX = x.getLength() * 8 * sizeof(BigUnsigned::Blk); | |
32 | int minBitsPerDigit = bitLen(base) - 1; | |
33 | int maxDigitLenOfX = ceilingDiv(maxBitLenOfX, minBitsPerDigit); | |
34 | allocate(maxDigitLenOfX); // Get the space | |
35 | ||
36 | BigUnsigned x2(x), buBase(base); | |
37 | Index digitNum = 0; | |
38 | ||
39 | while (!x2.isZero()) { | |
40 | // Get last digit. This is like `lastDigit = x2 % buBase, x2 /= buBase'. | |
41 | BigUnsigned lastDigit(x2); | |
42 | lastDigit.divideWithRemainder(buBase, x2); | |
43 | // Save the digit. | |
44 | blk[digitNum] = Digit(lastDigit); // invokes `BigUnsigned ==> unsigned short' converter | |
45 | // Move on. We can't run out of room: we figured it out above. | |
46 | digitNum++; | |
47 | } | |
48 | ||
49 | // Save the eventual length. | |
50 | len = digitNum; | |
51 | } | |
52 | ||
53 | BigUnsignedInABase::operator BigUnsigned() const { | |
54 | BigUnsigned ans(0), buBase(base), temp; | |
55 | Index digitNum = len; | |
56 | while (digitNum > 0) { | |
57 | digitNum--; | |
58 | temp.multiply(ans, buBase); | |
59 | ans.add(temp, BigUnsigned(blk[digitNum])); | |
60 | } | |
61 | return ans; | |
62 | } | |
63 | ||
64 | BigUnsignedInABase::BigUnsignedInABase(const std::string &s, Base base) { | |
65 | // Check the base. | |
66 | if (base > 36) | |
67 | 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."; | |
68 | // Save the base. | |
69 | // This pattern is seldom seen in C++, but the analogous ``this.'' is common in Java. | |
70 | this->base = base; | |
71 | ||
72 | len = s.length(); | |
73 | allocate(len); | |
74 | ||
75 | Index digitNum, symbolNumInString; | |
76 | for (digitNum = 0; digitNum < len; digitNum++) { | |
77 | symbolNumInString = len - 1 - digitNum; | |
78 | char theSymbol = s[symbolNumInString]; | |
79 | if (theSymbol >= '0' && theSymbol <= '9') | |
80 | blk[digitNum] = theSymbol - '0'; | |
81 | else if (theSymbol >= 'A' && theSymbol <= 'Z') | |
82 | blk[digitNum] = theSymbol - 'A' + 10; | |
83 | else if (theSymbol >= 'a' && theSymbol <= 'z') | |
84 | blk[digitNum] = theSymbol - 'a' + 10; | |
85 | else | |
86 | throw "BigUnsignedInABase(std::string, Base): Bad symbol in input. Only 0-9, A-Z, a-z are accepted."; | |
87 | } | |
88 | zapLeadingZeros(); | |
89 | } | |
90 | ||
91 | BigUnsignedInABase::operator std::string() const { | |
92 | if (base > 36) | |
93 | 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."; | |
94 | if (len == 0) | |
95 | return std::string("0"); | |
96 | std::string s; | |
97 | s.reserve(len); | |
98 | Index digitNum, symbolNumInString; | |
99 | for (symbolNumInString = 0; symbolNumInString < len; symbolNumInString++) { | |
100 | digitNum = len - 1 - symbolNumInString; | |
101 | Digit theDigit = blk[digitNum]; | |
102 | if (theDigit < 10) | |
103 | s.push_back(char('0' + theDigit)); | |
104 | else | |
105 | s.push_back(char('A' + theDigit - 10)); | |
106 | } | |
107 | return s; | |
108 | } |