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         zapLeadingZeros();
 100 }
 101
 102 BigUnsignedInABase::operator std::string() const {
 103         if (base > 36)
 104                 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.";
 105         if (len == 0)
 106                 return std::string("0");
 107         // Some compilers don't have push_back, so use a char * buffer instead.
 108         char *s = new char[len + 1];
 109         s[len] = '\0';
 110         Index digitNum, symbolNumInString;
 111         for (symbolNumInString = 0; symbolNumInString < len; symbolNumInString++) {
 112                 digitNum = len - 1 - symbolNumInString;
 113                 Digit theDigit = blk[digitNum];
 114                 if (theDigit < 10)
 115                         s[symbolNumInString] = char('0' + theDigit);
 116                 else
 117                         s[symbolNumInString] = char('A' + theDigit - 10);
 118         }
 119         std::string s2(s);
 120         delete [] s;
 121         return s2;
 122 }