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
9BigUnsignedInABase::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
24namespace {
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
38BigUnsignedInABase::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
68BigUnsignedInABase::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
79BigUnsignedInABase::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
111BigUnsignedInABase::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