| 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 | } |