1 // Copyright 2014 PDFium Authors. All rights reserved. 2 // Use of this source code is governed by a BSD-style license that can be 3 // found in the LICENSE file. 4 5 // Original code by Matt McCutchen, see the LICENSE file. 6 7 #include "BigUnsignedInABase.hh" 8 9 BigUnsignedInABase::BigUnsignedInABase(const Digit *d, Index l, Base base) 10 : NumberlikeArray<Digit>(d, l), base(base) { 11 // Check the base 12 if (base < 2) 13 abort(); 14 15 // Validate the digits. 16 for (Index i = 0; i < l; i++) 17 if (blk[i] >= base) 18 abort(); 19 20 // Eliminate any leading zeros we may have been passed. 21 zapLeadingZeros(); 22 } 23 24 namespace { 25 unsigned int bitLen(unsigned int x) { 26 unsigned int len = 0; 27 while (x > 0) { 28 x >>= 1; 29 len++; 30 } 31 return len; 32 } 33 unsigned int ceilingDiv(unsigned int a, unsigned int b) { 34 return (a + b - 1) / b; 35 } 36 } 37 38 BigUnsignedInABase::BigUnsignedInABase(const BigUnsigned &x, Base base) { 39 // Check the base 40 if (base < 2) 41 abort(); 42 this->base = base; 43 44 // Get an upper bound on how much space we need 45 int maxBitLenOfX = x.getLength() * BigUnsigned::N; 46 int minBitsPerDigit = bitLen(base) - 1; 47 int maxDigitLenOfX = ceilingDiv(maxBitLenOfX, minBitsPerDigit); 48 len = maxDigitLenOfX; // Another change to comply with `staying in bounds'. 49 allocate(len); // Get the space 50 51 BigUnsigned x2(x), buBase(base); 52 Index digitNum = 0; 53 54 while (!x2.isZero()) { 55 // Get last digit. This is like `lastDigit = x2 % buBase, x2 /= buBase'. 56 BigUnsigned lastDigit(x2); 57 lastDigit.divideWithRemainder(buBase, x2); 58 // Save the digit. 59 blk[digitNum] = lastDigit.toUnsignedShort(); 60 // Move on. We can't run out of room: we figured it out above. 61 digitNum++; 62 } 63 64 // Save the actual length. 65 len = digitNum; 66 } 67 68 BigUnsignedInABase::operator BigUnsigned() const { 69 BigUnsigned ans(0), buBase(base), temp; 70 Index digitNum = len; 71 while (digitNum > 0) { 72 digitNum--; 73 temp.multiply(ans, buBase); 74 ans.add(temp, BigUnsigned(blk[digitNum])); 75 } 76 return ans; 77 } 78 79 BigUnsignedInABase::BigUnsignedInABase(const std::string &s, Base base) { 80 // Check the base. 81 if (base > 36) 82 abort(); 83 // Save the base. 84 // This pattern is seldom seen in C++, but the analogous ``this.'' is common in Java. 85 this->base = base; 86 87 // `s.length()' is a `size_t', while `len' is a `NumberlikeArray::Index', 88 // also known as an `unsigned int'. Some compilers warn without this cast. 89 len = Index(s.length()); 90 allocate(len); 91 92 Index digitNum, symbolNumInString; 93 for (digitNum = 0; digitNum < len; digitNum++) { 94 symbolNumInString = len - 1 - digitNum; 95 char theSymbol = s[symbolNumInString]; 96 if (theSymbol >= '0' && theSymbol <= '9') 97 blk[digitNum] = theSymbol - '0'; 98 else if (theSymbol >= 'A' && theSymbol <= 'Z') 99 blk[digitNum] = theSymbol - 'A' + 10; 100 else if (theSymbol >= 'a' && theSymbol <= 'z') 101 blk[digitNum] = theSymbol - 'a' + 10; 102 else 103 abort(); 104 105 if (blk[digitNum] >= base) 106 abort(); 107 } 108 zapLeadingZeros(); 109 } 110 111 BigUnsignedInABase::operator std::string() const { 112 if (base > 36) 113 abort(); 114 if (len == 0) 115 return std::string("0"); 116 // Some compilers don't have push_back, so use a char * buffer instead. 117 char *s = new char[len + 1]; 118 s[len] = '\0'; 119 Index digitNum, symbolNumInString; 120 for (symbolNumInString = 0; symbolNumInString < len; symbolNumInString++) { 121 digitNum = len - 1 - symbolNumInString; 122 Digit theDigit = blk[digitNum]; 123 if (theDigit < 10) 124 s[symbolNumInString] = char('0' + theDigit); 125 else 126 s[symbolNumInString] = char('A' + theDigit - 10); 127 } 128 std::string s2(s); 129 delete [] s; 130 return s2; 131 } 132
