1/*
2 *  Licensed to the Apache Software Foundation (ASF) under one or more
3 *  contributor license agreements.  See the NOTICE file distributed with
4 *  this work for additional information regarding copyright ownership.
5 *  The ASF licenses this file to You under the Apache License, Version 2.0
6 *  (the "License"); you may not use this file except in compliance with
7 *  the License.  You may obtain a copy of the License at
8 *
9 *     http://www.apache.org/licenses/LICENSE-2.0
10 *
11 *  Unless required by applicable law or agreed to in writing, software
12 *  distributed under the License is distributed on an "AS IS" BASIS,
13 *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 *  See the License for the specific language governing permissions and
15 *  limitations under the License.
16 */
17
18package java.math;
19
20/**
21 * Static library that provides {@link BigInteger} base conversion from/to any
22 * integer represented in an {@link java.lang.String} Object.
23 */
24class Conversion {
25
26    /** Just to denote that this class can't be instantiated */
27    private Conversion() {}
28
29    /**
30     * Holds the maximal exponent for each radix, so that radix<sup>digitFitInInt[radix]</sup>
31     * fit in an {@code int} (32 bits).
32     */
33    static final int[] digitFitInInt = { -1, -1, 31, 19, 15, 13, 11,
34            11, 10, 9, 9, 8, 8, 8, 8, 7, 7, 7, 7, 7, 7, 7, 6, 6, 6, 6, 6, 6, 6,
35            6, 6, 6, 6, 6, 6, 6, 5 };
36
37    /**
38     * bigRadices values are precomputed maximal powers of radices (integer
39     * numbers from 2 to 36) that fit into unsigned int (32 bits). bigRadices[0] =
40     * 2 ^ 31, bigRadices[8] = 10 ^ 9, etc.
41     */
42
43    static final int[] bigRadices = { -2147483648, 1162261467,
44            1073741824, 1220703125, 362797056, 1977326743, 1073741824,
45            387420489, 1000000000, 214358881, 429981696, 815730721, 1475789056,
46            170859375, 268435456, 410338673, 612220032, 893871739, 1280000000,
47            1801088541, 113379904, 148035889, 191102976, 244140625, 308915776,
48            387420489, 481890304, 594823321, 729000000, 887503681, 1073741824,
49            1291467969, 1544804416, 1838265625, 60466176 };
50
51
52    /** @see BigInteger#toString(int) */
53    static String bigInteger2String(BigInteger val, int radix) {
54        val.prepareJavaRepresentation();
55        int sign = val.sign;
56        int numberLength = val.numberLength;
57        int[] digits = val.digits;
58
59        if (sign == 0) {
60            return "0";
61        }
62        if (numberLength == 1) {
63            int highDigit = digits[numberLength - 1];
64            long v = highDigit & 0xFFFFFFFFL;
65            if (sign < 0) {
66                v = -v;
67            }
68            return Long.toString(v, radix);
69        }
70        if ((radix == 10) || (radix < Character.MIN_RADIX)
71                || (radix > Character.MAX_RADIX)) {
72            return val.toString();
73        }
74        double bitsForRadixDigit;
75        bitsForRadixDigit = Math.log(radix) / Math.log(2);
76        int resLengthInChars = (int) (val.abs().bitLength() / bitsForRadixDigit + ((sign < 0) ? 1
77                : 0)) + 1;
78
79        char[] result = new char[resLengthInChars];
80        int currentChar = resLengthInChars;
81        int resDigit;
82        if (radix != 16) {
83            int[] temp = new int[numberLength];
84            System.arraycopy(digits, 0, temp, 0, numberLength);
85            int tempLen = numberLength;
86            int charsPerInt = digitFitInInt[radix];
87            int i;
88            // get the maximal power of radix that fits in int
89            int bigRadix = bigRadices[radix - 2];
90            while (true) {
91                // divide the array of digits by bigRadix and convert remainders
92                // to characters collecting them in the char array
93                resDigit = Division.divideArrayByInt(temp, temp, tempLen,
94                        bigRadix);
95                int previous = currentChar;
96                do {
97                    result[--currentChar] = Character.forDigit(
98                            resDigit % radix, radix);
99                } while (((resDigit /= radix) != 0) && (currentChar != 0));
100                int delta = charsPerInt - previous + currentChar;
101                for (i = 0; i < delta && currentChar > 0; i++) {
102                    result[--currentChar] = '0';
103                }
104                for (i = tempLen - 1; (i > 0) && (temp[i] == 0); i--) {
105                    ;
106                }
107                tempLen = i + 1;
108                if ((tempLen == 1) && (temp[0] == 0)) { // the quotient is 0
109                    break;
110                }
111            }
112        } else {
113            // radix == 16
114            for (int i = 0; i < numberLength; i++) {
115                for (int j = 0; (j < 8) && (currentChar > 0); j++) {
116                    resDigit = digits[i] >> (j << 2) & 0xf;
117                    result[--currentChar] = Character.forDigit(resDigit, 16);
118                }
119            }
120        }
121        while (result[currentChar] == '0') {
122            currentChar++;
123        }
124        if (sign == -1) {
125            result[--currentChar] = '-';
126        }
127        return new String(result, currentChar, resLengthInChars - currentChar);
128    }
129
130    /**
131     * Builds the correspondent {@code String} representation of {@code val}
132     * being scaled by {@code scale}.
133     *
134     * @see BigInteger#toString()
135     * @see BigDecimal#toString()
136     */
137    static String toDecimalScaledString(BigInteger val, int scale) {
138        val.prepareJavaRepresentation();
139        int sign = val.sign;
140        int numberLength = val.numberLength;
141        int[] digits = val.digits;
142        int resLengthInChars;
143        int currentChar;
144        char[] result;
145
146        if (sign == 0) {
147            switch (scale) {
148                case 0:
149                    return "0";
150                case 1:
151                    return "0.0";
152                case 2:
153                    return "0.00";
154                case 3:
155                    return "0.000";
156                case 4:
157                    return "0.0000";
158                case 5:
159                    return "0.00000";
160                case 6:
161                    return "0.000000";
162                default:
163                    StringBuilder result1 = new StringBuilder();
164                    if (scale < 0) {
165                        result1.append("0E+");
166                    } else {
167                        result1.append("0E");
168                    }
169                    result1.append(-scale);
170                    return result1.toString();
171            }
172        }
173        // one 32-bit unsigned value may contains 10 decimal digits
174        resLengthInChars = numberLength * 10 + 1 + 7;
175        // Explanation why +1+7:
176        // +1 - one char for sign if needed.
177        // +7 - For "special case 2" (see below) we have 7 free chars for
178        // inserting necessary scaled digits.
179        result = new char[resLengthInChars + 1];
180        // allocated [resLengthInChars+1] characters.
181        // a free latest character may be used for "special case 1" (see
182        // below)
183        currentChar = resLengthInChars;
184        if (numberLength == 1) {
185            int highDigit = digits[0];
186            if (highDigit < 0) {
187                long v = highDigit & 0xFFFFFFFFL;
188                do {
189                    long prev = v;
190                    v /= 10;
191                    result[--currentChar] = (char) (0x0030 + ((int) (prev - v * 10)));
192                } while (v != 0);
193            } else {
194                int v = highDigit;
195                do {
196                    int prev = v;
197                    v /= 10;
198                    result[--currentChar] = (char) (0x0030 + (prev - v * 10));
199                } while (v != 0);
200            }
201        } else {
202            int[] temp = new int[numberLength];
203            int tempLen = numberLength;
204            System.arraycopy(digits, 0, temp, 0, tempLen);
205            BIG_LOOP: while (true) {
206                // divide the array of digits by bigRadix and convert
207                // remainders
208                // to characters collecting them in the char array
209                long result11 = 0;
210                for (int i1 = tempLen - 1; i1 >= 0; i1--) {
211                    long temp1 = (result11 << 32)
212                            + (temp[i1] & 0xFFFFFFFFL);
213                    long res = divideLongByBillion(temp1);
214                    temp[i1] = (int) res;
215                    result11 = (int) (res >> 32);
216                }
217                int resDigit = (int) result11;
218                int previous = currentChar;
219                do {
220                    result[--currentChar] = (char) (0x0030 + (resDigit % 10));
221                } while (((resDigit /= 10) != 0) && (currentChar != 0));
222                int delta = 9 - previous + currentChar;
223                for (int i = 0; (i < delta) && (currentChar > 0); i++) {
224                    result[--currentChar] = '0';
225                }
226                int j = tempLen - 1;
227                for (; temp[j] == 0; j--) {
228                    if (j == 0) { // means temp[0] == 0
229                        break BIG_LOOP;
230                    }
231                }
232                tempLen = j + 1;
233            }
234            while (result[currentChar] == '0') {
235                currentChar++;
236            }
237        }
238        boolean negNumber = (sign < 0);
239        int exponent = resLengthInChars - currentChar - scale - 1;
240        if (scale == 0) {
241            if (negNumber) {
242                result[--currentChar] = '-';
243            }
244            return new String(result, currentChar, resLengthInChars
245                    - currentChar);
246        }
247        if ((scale > 0) && (exponent >= -6)) {
248            if (exponent >= 0) {
249                // special case 1
250                int insertPoint = currentChar + exponent;
251                for (int j = resLengthInChars - 1; j >= insertPoint; j--) {
252                    result[j + 1] = result[j];
253                }
254                result[++insertPoint] = '.';
255                if (negNumber) {
256                    result[--currentChar] = '-';
257                }
258                return new String(result, currentChar, resLengthInChars
259                        - currentChar + 1);
260            }
261            // special case 2
262            for (int j = 2; j < -exponent + 1; j++) {
263                result[--currentChar] = '0';
264            }
265            result[--currentChar] = '.';
266            result[--currentChar] = '0';
267            if (negNumber) {
268                result[--currentChar] = '-';
269            }
270            return new String(result, currentChar, resLengthInChars
271                    - currentChar);
272        }
273        int startPoint = currentChar + 1;
274        int endPoint = resLengthInChars;
275        StringBuilder result1 = new StringBuilder(16 + endPoint - startPoint);
276        if (negNumber) {
277            result1.append('-');
278        }
279        if (endPoint - startPoint >= 1) {
280            result1.append(result[currentChar]);
281            result1.append('.');
282            result1.append(result, currentChar + 1, resLengthInChars
283                    - currentChar - 1);
284        } else {
285            result1.append(result, currentChar, resLengthInChars
286                    - currentChar);
287        }
288        result1.append('E');
289        if (exponent > 0) {
290            result1.append('+');
291        }
292        result1.append(Integer.toString(exponent));
293        return result1.toString();
294    }
295
296    /* can process only 32-bit numbers */
297    static String toDecimalScaledString(long value, int scale) {
298        int resLengthInChars;
299        int currentChar;
300        char[] result;
301        boolean negNumber = value < 0;
302        if(negNumber) {
303            value = -value;
304        }
305        if (value == 0) {
306            switch (scale) {
307                case 0: return "0";
308                case 1: return "0.0";
309                case 2: return "0.00";
310                case 3: return "0.000";
311                case 4: return "0.0000";
312                case 5: return "0.00000";
313                case 6: return "0.000000";
314                default:
315                    StringBuilder result1 = new StringBuilder();
316                    if (scale  < 0) {
317                        result1.append("0E+");
318                    } else {
319                        result1.append("0E");
320                    }
321                    result1.append( (scale == Integer.MIN_VALUE) ? "2147483648" : Integer.toString(-scale));
322                    return result1.toString();
323            }
324        }
325        // one 32-bit unsigned value may contains 10 decimal digits
326        resLengthInChars = 18;
327        // Explanation why +1+7:
328        // +1 - one char for sign if needed.
329        // +7 - For "special case 2" (see below) we have 7 free chars for
330        //  inserting necessary scaled digits.
331        result = new char[resLengthInChars+1];
332        //  Allocated [resLengthInChars+1] characters.
333        // a free latest character may be used for "special case 1" (see below)
334        currentChar = resLengthInChars;
335        long v = value;
336        do {
337            long prev = v;
338            v /= 10;
339            result[--currentChar] = (char) (0x0030 + (prev - v * 10));
340        } while (v != 0);
341
342        long exponent = (long)resLengthInChars - (long)currentChar - scale - 1L;
343        if (scale == 0) {
344            if (negNumber) {
345                result[--currentChar] = '-';
346            }
347            return new String(result, currentChar, resLengthInChars - currentChar);
348        }
349        if (scale > 0 && exponent >= -6) {
350            if (exponent >= 0) {
351                // special case 1
352                int insertPoint = currentChar + (int) exponent ;
353                for (int j=resLengthInChars-1; j>=insertPoint; j--) {
354                    result[j+1] = result[j];
355                }
356                result[++insertPoint]='.';
357                if (negNumber) {
358                    result[--currentChar] = '-';
359                }
360                return new String(result, currentChar, resLengthInChars - currentChar + 1);
361            }
362            // special case 2
363            for (int j = 2; j < -exponent + 1; j++) {
364                result[--currentChar] = '0';
365            }
366            result[--currentChar] = '.';
367            result[--currentChar] = '0';
368            if (negNumber) {
369                result[--currentChar] = '-';
370            }
371            return new String(result, currentChar, resLengthInChars - currentChar);
372        }
373        int startPoint = currentChar + 1;
374        int endPoint = resLengthInChars;
375        StringBuilder result1 = new StringBuilder(16 + endPoint - startPoint);
376        if (negNumber) {
377            result1.append('-');
378        }
379        if (endPoint - startPoint >= 1) {
380            result1.append(result[currentChar]);
381            result1.append('.');
382            result1.append(result,currentChar+1,resLengthInChars - currentChar-1);
383        } else {
384            result1.append(result,currentChar,resLengthInChars - currentChar);
385        }
386        result1.append('E');
387        if (exponent > 0) {
388            result1.append('+');
389        }
390        result1.append(Long.toString(exponent));
391        return result1.toString();
392    }
393
394    static long divideLongByBillion(long a) {
395        long quot;
396        long rem;
397
398        if (a >= 0) {
399            long bLong = 1000000000L;
400            quot = (a / bLong);
401            rem = (a % bLong);
402        } else {
403            /*
404             * Make the dividend positive shifting it right by 1 bit then get
405             * the quotient an remainder and correct them properly
406             */
407            long aPos = a >>> 1;
408            long bPos = 1000000000L >>> 1;
409            quot = aPos / bPos;
410            rem = aPos % bPos;
411            // double the remainder and add 1 if 'a' is odd
412            rem = (rem << 1) + (a & 1);
413        }
414        return ((rem << 32) | (quot & 0xFFFFFFFFL));
415    }
416
417    /** @see BigInteger#doubleValue() */
418    static double bigInteger2Double(BigInteger val) {
419        val.prepareJavaRepresentation();
420        // val.bitLength() < 64
421        if ((val.numberLength < 2)
422                || ((val.numberLength == 2) && (val.digits[1] > 0))) {
423            return val.longValue();
424        }
425        // val.bitLength() >= 33 * 32 > 1024
426        if (val.numberLength > 32) {
427            return ((val.sign > 0) ? Double.POSITIVE_INFINITY
428                    : Double.NEGATIVE_INFINITY);
429        }
430        int bitLen = val.abs().bitLength();
431        long exponent = bitLen - 1;
432        int delta = bitLen - 54;
433        // We need 54 top bits from this, the 53th bit is always 1 in lVal.
434        long lVal = val.abs().shiftRight(delta).longValue();
435        /*
436         * Take 53 bits from lVal to mantissa. The least significant bit is
437         * needed for rounding.
438         */
439        long mantissa = lVal & 0x1FFFFFFFFFFFFFL;
440        if (exponent == 1023) {
441            if (mantissa == 0X1FFFFFFFFFFFFFL) {
442                return ((val.sign > 0) ? Double.POSITIVE_INFINITY
443                        : Double.NEGATIVE_INFINITY);
444            }
445            if (mantissa == 0x1FFFFFFFFFFFFEL) {
446                return ((val.sign > 0) ? Double.MAX_VALUE : -Double.MAX_VALUE);
447            }
448        }
449        // Round the mantissa
450        if (((mantissa & 1) == 1)
451                && (((mantissa & 2) == 2) || BitLevel.nonZeroDroppedBits(delta,
452                        val.digits))) {
453            mantissa += 2;
454        }
455        mantissa >>= 1; // drop the rounding bit
456        long resSign = (val.sign < 0) ? 0x8000000000000000L : 0;
457        exponent = ((1023 + exponent) << 52) & 0x7FF0000000000000L;
458        long result = resSign | exponent | mantissa;
459        return Double.longBitsToDouble(result);
460    }
461}
462