BigUnsignedInABase.cc

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