BigUnsignedInABase.cc

   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 }