001: /*
002: * Licensed to the Apache Software Foundation (ASF) under one or more
003: * contributor license agreements. See the NOTICE file distributed with
004: * this work for additional information regarding copyright ownership.
005: * The ASF licenses this file to You under the Apache License, Version 2.0
006: * (the "License"); you may not use this file except in compliance with
007: * the License. You may obtain a copy of the License at
008: *
009: * http://www.apache.org/licenses/LICENSE-2.0
010: *
011: * Unless required by applicable law or agreed to in writing, software
012: * distributed under the License is distributed on an "AS IS" BASIS,
013: * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014: * See the License for the specific language governing permissions and
015: * limitations under the License.
016: */
017:
018: package java.math;
019:
020: /**
021: * Static library that provides {@link BigInteger} base conversion from/to any
022: * integer represented in an {@link java.lang.String} Object.
023: *
024: * @author Intel Middleware Product Division
025: * @author Instituto Tecnologico de Cordoba
026: */
027: class Conversion {
028:
029: /** Just to denote that this class can't be instantiated */
030: private Conversion() {
031: }
032:
033: /**
034: * Holds the maximal exponent for each radix, so that radix<sup>digitFitInInt[radix]</sup>
035: * fit in an {@code int} (32 bits).
036: */
037: static final int[] digitFitInInt = { -1, -1, 31, 19, 15, 13, 11,
038: 11, 10, 9, 9, 8, 8, 8, 8, 7, 7, 7, 7, 7, 7, 7, 6, 6, 6, 6,
039: 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 5 };
040:
041: /**
042: * bigRadices values are precomputed maximal powers of radices (integer
043: * numbers from 2 to 36) that fit into unsigned int (32 bits). bigRadices[0] =
044: * 2 ^ 31, bigRadices[8] = 10 ^ 9, etc.
045: */
046:
047: static final int bigRadices[] = { -2147483648, 1162261467,
048: 1073741824, 1220703125, 362797056, 1977326743, 1073741824,
049: 387420489, 1000000000, 214358881, 429981696, 815730721,
050: 1475789056, 170859375, 268435456, 410338673, 612220032,
051: 893871739, 1280000000, 1801088541, 113379904, 148035889,
052: 191102976, 244140625, 308915776, 387420489, 481890304,
053: 594823321, 729000000, 887503681, 1073741824, 1291467969,
054: 1544804416, 1838265625, 60466176 };
055:
056: /** @see BigInteger#toString(int) */
057: static String bigInteger2String(BigInteger val, int radix) {
058: int sign = val.sign;
059: int numberLength = val.numberLength;
060: int digits[] = val.digits;
061:
062: if (sign == 0) {
063: return "0"; //$NON-NLS-1$
064: }
065: if (numberLength == 1) {
066: int highDigit = digits[numberLength - 1];
067: long v = highDigit & 0xFFFFFFFFL;
068: if (sign < 0) {
069: v = -v;
070: }
071: return Long.toString(v, radix);
072: }
073: if ((radix == 10) || (radix < Character.MIN_RADIX)
074: || (radix > Character.MAX_RADIX)) {
075: return val.toString();
076: }
077: double bitsForRadixDigit;
078: bitsForRadixDigit = Math.log(radix) / Math.log(2);
079: int resLengthInChars = (int) (val.abs().bitLength()
080: / bitsForRadixDigit + ((sign < 0) ? 1 : 0)) + 1;
081:
082: char result[] = new char[resLengthInChars];
083: int currentChar = resLengthInChars;
084: int resDigit;
085: if (radix != 16) {
086: int temp[] = new int[numberLength];
087: System.arraycopy(digits, 0, temp, 0, numberLength);
088: int tempLen = numberLength;
089: int charsPerInt = digitFitInInt[radix];
090: int i;
091: // get the maximal power of radix that fits in int
092: int bigRadix = bigRadices[radix - 2];
093: while (true) {
094: // divide the array of digits by bigRadix and convert remainders
095: // to characters collecting them in the char array
096: resDigit = Division.divideArrayByInt(temp, temp,
097: tempLen, bigRadix);
098: int previous = currentChar;
099: do {
100: result[--currentChar] = Character.forDigit(resDigit
101: % radix, radix);
102: } while (((resDigit /= radix) != 0)
103: && (currentChar != 0));
104: int delta = charsPerInt - previous + currentChar;
105: for (i = 0; i < delta && currentChar > 0; i++) {
106: result[--currentChar] = '0';
107: }
108: for (i = tempLen - 1; (i > 0) && (temp[i] == 0); i--) {
109: ;
110: }
111: tempLen = i + 1;
112: if ((tempLen == 1) && (temp[0] == 0)) { // the quotient is 0
113: break;
114: }
115: }
116: } else {
117: // radix == 16
118: for (int i = 0; i < numberLength; i++) {
119: for (int j = 0; (j < 8) && (currentChar > 0); j++) {
120: resDigit = digits[i] >> (j << 2) & 0xf;
121: result[--currentChar] = Character.forDigit(
122: resDigit, 16);
123: }
124: }
125: }
126: while (result[currentChar] == '0') {
127: currentChar++;
128: }
129: if (sign == -1) {
130: result[--currentChar] = '-';
131: }
132: return new String(result, currentChar, resLengthInChars
133: - currentChar);
134: }
135:
136: /**
137: * Builds the correspondent {@code String} representation of {@code val}
138: * being scaled by {@code scale}.
139: *
140: * @see BigInteger#toString()
141: * @see BigDecimal#toString()
142: */
143: static String toDecimalScaledString(BigInteger val, int scale) {
144: int sign = val.sign;
145: int numberLength = val.numberLength;
146: int digits[] = val.digits;
147: int resLengthInChars;
148: int currentChar;
149: char result[];
150:
151: if (sign == 0) {
152: switch (scale) {
153: case 0:
154: return "0"; //$NON-NLS-1$
155: case 1:
156: return "0.0"; //$NON-NLS-1$
157: case 2:
158: return "0.00"; //$NON-NLS-1$
159: case 3:
160: return "0.000"; //$NON-NLS-1$
161: case 4:
162: return "0.0000"; //$NON-NLS-1$
163: case 5:
164: return "0.00000"; //$NON-NLS-1$
165: case 6:
166: return "0.000000"; //$NON-NLS-1$
167: default:
168: StringBuffer result1 = new StringBuffer();
169: if (scale < 0) {
170: result1.append("0E+"); //$NON-NLS-1$
171: } else {
172: result1.append("0E"); //$NON-NLS-1$
173: }
174: result1.append(-scale);
175: return result1.toString();
176: }
177: }
178: // one 32-bit unsigned value may contains 10 decimal digits
179: resLengthInChars = numberLength * 10 + 1 + 7;
180: // Explanation why +1+7:
181: // +1 - one char for sign if needed.
182: // +7 - For "special case 2" (see below) we have 7 free chars for
183: // inserting necessary scaled digits.
184: result = new char[resLengthInChars + 1];
185: // allocated [resLengthInChars+1] characters.
186: // a free latest character may be used for "special case 1" (see
187: // below)
188: currentChar = resLengthInChars;
189: if (numberLength == 1) {
190: int highDigit = digits[0];
191: if (highDigit < 0) {
192: long v = highDigit & 0xFFFFFFFFL;
193: do {
194: long prev = v;
195: v /= 10;
196: result[--currentChar] = (char) (0x0030 + ((int) (prev - v * 10)));
197: } while (v != 0);
198: } else {
199: int v = highDigit;
200: do {
201: int prev = v;
202: v /= 10;
203: result[--currentChar] = (char) (0x0030 + (prev - v * 10));
204: } while (v != 0);
205: }
206: } else {
207: int temp[] = new int[numberLength];
208: int tempLen = numberLength;
209: System.arraycopy(digits, 0, temp, 0, tempLen);
210: BIG_LOOP: while (true) {
211: // divide the array of digits by bigRadix and convert
212: // remainders
213: // to characters collecting them in the char array
214: long result11 = 0;
215: for (int i1 = tempLen - 1; i1 >= 0; i1--) {
216: long temp1 = (result11 << 32)
217: + (temp[i1] & 0xFFFFFFFFL);
218: long res = divideLongByBillion(temp1);
219: temp[i1] = (int) res;
220: result11 = (int) (res >> 32);
221: }
222: int resDigit = (int) result11;
223: int previous = currentChar;
224: do {
225: result[--currentChar] = (char) (0x0030 + (resDigit % 10));
226: } while (((resDigit /= 10) != 0) && (currentChar != 0));
227: int delta = 9 - previous + currentChar;
228: for (int i = 0; (i < delta) && (currentChar > 0); i++) {
229: result[--currentChar] = '0';
230: }
231: int j = tempLen - 1;
232: for (; temp[j] == 0; j--) {
233: if (j == 0) { // means temp[0] == 0
234: break BIG_LOOP;
235: }
236: }
237: tempLen = j + 1;
238: }
239: while (result[currentChar] == '0') {
240: currentChar++;
241: }
242: }
243: boolean negNumber = (sign < 0);
244: int exponent = resLengthInChars - currentChar - scale - 1;
245: if (scale == 0) {
246: if (negNumber) {
247: result[--currentChar] = '-';
248: }
249: return new String(result, currentChar, resLengthInChars
250: - currentChar);
251: }
252: if ((scale > 0) && (exponent >= -6)) {
253: if (exponent >= 0) {
254: // special case 1
255: int insertPoint = currentChar + exponent;
256: for (int j = resLengthInChars - 1; j >= insertPoint; j--) {
257: result[j + 1] = result[j];
258: }
259: result[++insertPoint] = '.';
260: if (negNumber) {
261: result[--currentChar] = '-';
262: }
263: return new String(result, currentChar, resLengthInChars
264: - currentChar + 1);
265: }
266: // special case 2
267: for (int j = 2; j < -exponent + 1; j++) {
268: result[--currentChar] = '0';
269: }
270: result[--currentChar] = '.';
271: result[--currentChar] = '0';
272: if (negNumber) {
273: result[--currentChar] = '-';
274: }
275: return new String(result, currentChar, resLengthInChars
276: - currentChar);
277: }
278: int startPoint = currentChar + 1;
279: int endPoint = resLengthInChars;
280: StringBuffer result1 = new StringBuffer(16 + endPoint
281: - startPoint);
282: if (negNumber) {
283: result1.append('-');
284: }
285: if (endPoint - startPoint >= 1) {
286: result1.append(result[currentChar]);
287: result1.append('.');
288: result1.append(result, currentChar + 1, resLengthInChars
289: - currentChar - 1);
290: } else {
291: result1.append(result, currentChar, resLengthInChars
292: - currentChar);
293: }
294: result1.append('E');
295: if (exponent > 0) {
296: result1.append('+');
297: }
298: result1.append(Integer.toString(exponent));
299: return result1.toString();
300: }
301:
302: /* can process only 32-bit numbers */
303: static String toDecimalScaledString(long value, int scale) {
304: int resLengthInChars;
305: int currentChar;
306: char result[];
307: boolean negNumber = value < 0;
308: if (negNumber) {
309: value = -value;
310: }
311: if (value == 0) {
312: switch (scale) {
313: case 0:
314: return "0"; //$NON-NLS-1$
315: case 1:
316: return "0.0"; //$NON-NLS-1$
317: case 2:
318: return "0.00"; //$NON-NLS-1$
319: case 3:
320: return "0.000"; //$NON-NLS-1$
321: case 4:
322: return "0.0000"; //$NON-NLS-1$
323: case 5:
324: return "0.00000"; //$NON-NLS-1$
325: case 6:
326: return "0.000000"; //$NON-NLS-1$
327: default:
328: StringBuffer result1 = new StringBuffer();
329: if (scale < 0) {
330: result1.append("0E+"); //$NON-NLS-1$
331: } else {
332: result1.append("0E"); //$NON-NLS-1$
333: }
334: result1
335: .append((scale == Integer.MIN_VALUE) ? "2147483648" : Integer.toString(-scale)); //$NON-NLS-1$
336: return result1.toString();
337: }
338: }
339: // one 32-bit unsigned value may contains 10 decimal digits
340: resLengthInChars = 18;
341: // Explanation why +1+7:
342: // +1 - one char for sign if needed.
343: // +7 - For "special case 2" (see below) we have 7 free chars for
344: // inserting necessary scaled digits.
345: result = new char[resLengthInChars + 1];
346: // Allocated [resLengthInChars+1] characters.
347: // a free latest character may be used for "special case 1" (see below)
348: currentChar = resLengthInChars;
349: long v = value;
350: do {
351: long prev = v;
352: v /= 10;
353: result[--currentChar] = (char) (0x0030 + (prev - v * 10));
354: } while (v != 0);
355:
356: long exponent = (long) resLengthInChars - (long) currentChar
357: - scale - 1L;
358: if (scale == 0) {
359: if (negNumber) {
360: result[--currentChar] = '-';
361: }
362: return new String(result, currentChar, resLengthInChars
363: - currentChar);
364: }
365: if (scale > 0 && exponent >= -6) {
366: if (exponent >= 0) {
367: // special case 1
368: int insertPoint = currentChar + (int) exponent;
369: for (int j = resLengthInChars - 1; j >= insertPoint; j--) {
370: result[j + 1] = result[j];
371: }
372: result[++insertPoint] = '.';
373: if (negNumber) {
374: result[--currentChar] = '-';
375: }
376: return new String(result, currentChar, resLengthInChars
377: - currentChar + 1);
378: }
379: // special case 2
380: for (int j = 2; j < -exponent + 1; j++) {
381: result[--currentChar] = '0';
382: }
383: result[--currentChar] = '.';
384: result[--currentChar] = '0';
385: if (negNumber) {
386: result[--currentChar] = '-';
387: }
388: return new String(result, currentChar, resLengthInChars
389: - currentChar);
390: }
391: int startPoint = currentChar + 1;
392: int endPoint = resLengthInChars;
393: StringBuffer result1 = new StringBuffer(16 + endPoint
394: - startPoint);
395: if (negNumber) {
396: result1.append('-');
397: }
398: if (endPoint - startPoint >= 1) {
399: result1.append(result[currentChar]);
400: result1.append('.');
401: result1.append(result, currentChar + 1, resLengthInChars
402: - currentChar - 1);
403: } else {
404: result1.append(result, currentChar, resLengthInChars
405: - currentChar);
406: }
407: result1.append('E');
408: if (exponent > 0) {
409: result1.append('+');
410: }
411: result1.append(Long.toString(exponent));
412: return result1.toString();
413: }
414:
415: static long divideLongByBillion(long a) {
416: long quot;
417: long rem;
418:
419: if (a >= 0) {
420: long bLong = 1000000000L;
421: quot = (a / bLong);
422: rem = (a % bLong);
423: } else {
424: /*
425: * Make the dividend positive shifting it right by 1 bit then get
426: * the quotient an remainder and correct them properly
427: */
428: long aPos = a >>> 1;
429: long bPos = 1000000000L >>> 1;
430: quot = aPos / bPos;
431: rem = aPos % bPos;
432: // double the remainder and add 1 if 'a' is odd
433: rem = (rem << 1) + (a & 1);
434: }
435: return ((rem << 32) | (quot & 0xFFFFFFFFL));
436: }
437:
438: /** @see BigInteger#doubleValue() */
439: static double bigInteger2Double(BigInteger val) {
440: // val.bitLength() < 64
441: if ((val.numberLength < 2)
442: || ((val.numberLength == 2) && (val.digits[1] > 0))) {
443: return val.longValue();
444: }
445: // val.bitLength() >= 33 * 32 > 1024
446: if (val.numberLength > 32) {
447: return ((val.sign > 0) ? Double.POSITIVE_INFINITY
448: : Double.NEGATIVE_INFINITY);
449: }
450: int bitLen = val.abs().bitLength();
451: long exponent = bitLen - 1;
452: int delta = bitLen - 54;
453: // We need 54 top bits from this, the 53th bit is always 1 in lVal.
454: long lVal = val.abs().shiftRight(delta).longValue();
455: /*
456: * Take 53 bits from lVal to mantissa. The least significant bit is
457: * needed for rounding.
458: */
459: long mantissa = lVal & 0x1FFFFFFFFFFFFFL;
460: if (exponent == 1023) {
461: if (mantissa == 0X1FFFFFFFFFFFFFL) {
462: return ((val.sign > 0) ? Double.POSITIVE_INFINITY
463: : Double.NEGATIVE_INFINITY);
464: }
465: if (mantissa == 0x1FFFFFFFFFFFFEL) {
466: return ((val.sign > 0) ? Double.MAX_VALUE
467: : -Double.MAX_VALUE);
468: }
469: }
470: // Round the mantissa
471: if (((mantissa & 1) == 1)
472: && (((mantissa & 2) == 2) || BitLevel
473: .nonZeroDroppedBits(delta, val.digits))) {
474: mantissa += 2;
475: }
476: mantissa >>= 1; // drop the rounding bit
477: long resSign = (val.sign < 0) ? 0x8000000000000000L : 0;
478: exponent = ((1023 + exponent) << 52) & 0x7FF0000000000000L;
479: long result = resSign | exponent | mantissa;
480: return Double.longBitsToDouble(result);
481: }
482: }
|