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 */ 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
