Commit | Line | Data |
---|---|---|
05780f4b MM |
1 | #include "BigUnsignedInABase.hh" |
2 | ||
8cad5ca9 MM |
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 | ||
05780f4b MM |
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 | } | |
a8b42b68 | 31 | |
05780f4b MM |
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"; | |
05780f4b | 36 | this->base = base; |
5ff40cf5 | 37 | |
05780f4b | 38 | // Get an upper bound on how much space we need |
4efbb076 | 39 | int maxBitLenOfX = x.getLength() * BigUnsigned::N; |
05780f4b MM |
40 | int minBitsPerDigit = bitLen(base) - 1; |
41 | int maxDigitLenOfX = ceilingDiv(maxBitLenOfX, minBitsPerDigit); | |
3e132790 | 42 | len = maxDigitLenOfX; // Another change to comply with `staying in bounds'. |
2f145f11 | 43 | allocate(len); // Get the space |
5ff40cf5 | 44 | |
05780f4b MM |
45 | BigUnsigned x2(x), buBase(base); |
46 | Index digitNum = 0; | |
5ff40cf5 | 47 | |
05780f4b MM |
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. | |
3e132790 | 53 | blk[digitNum] = lastDigit.toUnsignedShort(); |
05780f4b MM |
54 | // Move on. We can't run out of room: we figured it out above. |
55 | digitNum++; | |
56 | } | |
5ff40cf5 | 57 | |
2f145f11 | 58 | // Save the actual length. |
05780f4b MM |
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; | |
5ff40cf5 | 80 | |
a8b42b68 MM |
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()); | |
05780f4b | 84 | allocate(len); |
5ff40cf5 | 85 | |
05780f4b MM |
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."; | |
79881c05 MM |
98 | |
99 | if (blk[digitNum] >= base) | |
100 | throw "BigUnsignedInABase::BigUnsignedInABase(const Digit *, Index, Base): A digit is too large for the specified base"; | |
05780f4b MM |
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"); | |
8cad5ca9 | 110 | // Some compilers don't have push_back, so use a char * buffer instead. |
b3fe29df MM |
111 | char *s = new char[len + 1]; |
112 | s[len] = '\0'; | |
05780f4b MM |
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) | |
b3fe29df | 118 | s[symbolNumInString] = char('0' + theDigit); |
05780f4b | 119 | else |
b3fe29df | 120 | s[symbolNumInString] = char('A' + theDigit - 10); |
05780f4b | 121 | } |
2f145f11 | 122 | std::string s2(s); |
be1bdfe2 | 123 | delete [] s; |
2f145f11 | 124 | return s2; |
05780f4b | 125 | } |