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 
18 package 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  */
24 class Conversion {
25 
26     /** Just to denote that this class can't be instantiated */
Conversion()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) */
bigInteger2String(BigInteger val, int radix)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      */
toDecimalScaledString(BigInteger val, int scale)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 */
toDecimalScaledString(long value, int scale)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 
divideLongByBillion(long a)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() */
bigInteger2Double(BigInteger val)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