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 // BEGIN android-added 55 val.establishOldRepresentation("Conversion.bigInteger2String"); 56 // END android-added 57 int sign = val.sign; 58 int numberLength = val.numberLength; 59 int digits[] = val.digits; 60 61 if (sign == 0) { 62 return "0"; //$NON-NLS-1$ 63 } 64 if (numberLength == 1) { 65 int highDigit = digits[numberLength - 1]; 66 long v = highDigit & 0xFFFFFFFFL; 67 if (sign < 0) { 68 v = -v; 69 } 70 return Long.toString(v, radix); 71 } 72 if ((radix == 10) || (radix < Character.MIN_RADIX) 73 || (radix > Character.MAX_RADIX)) { 74 return val.toString(); 75 } 76 double bitsForRadixDigit; 77 bitsForRadixDigit = Math.log(radix) / Math.log(2); 78 int resLengthInChars = (int) (val.abs().bitLength() / bitsForRadixDigit + ((sign < 0) ? 1 79 : 0)) + 1; 80 81 char result[] = new char[resLengthInChars]; 82 int currentChar = resLengthInChars; 83 int resDigit; 84 if (radix != 16) { 85 int temp[] = new int[numberLength]; 86 System.arraycopy(digits, 0, temp, 0, numberLength); 87 int tempLen = numberLength; 88 int charsPerInt = digitFitInInt[radix]; 89 int i; 90 // get the maximal power of radix that fits in int 91 int bigRadix = bigRadices[radix - 2]; 92 while (true) { 93 // divide the array of digits by bigRadix and convert remainders 94 // to characters collecting them in the char array 95 resDigit = Division.divideArrayByInt(temp, temp, tempLen, 96 bigRadix); 97 int previous = currentChar; 98 do { 99 result[--currentChar] = Character.forDigit( 100 resDigit % radix, radix); 101 } while (((resDigit /= radix) != 0) && (currentChar != 0)); 102 int delta = charsPerInt - previous + currentChar; 103 for (i = 0; i < delta && currentChar > 0; i++) { 104 result[--currentChar] = '0'; 105 } 106 for (i = tempLen - 1; (i > 0) && (temp[i] == 0); i--) { 107 ; 108 } 109 tempLen = i + 1; 110 if ((tempLen == 1) && (temp[0] == 0)) { // the quotient is 0 111 break; 112 } 113 } 114 } else { 115 // radix == 16 116 for (int i = 0; i < numberLength; i++) { 117 for (int j = 0; (j < 8) && (currentChar > 0); j++) { 118 resDigit = digits[i] >> (j << 2) & 0xf; 119 result[--currentChar] = Character.forDigit(resDigit, 16); 120 } 121 } 122 } 123 while (result[currentChar] == '0') { 124 currentChar++; 125 } 126 if (sign == -1) { 127 result[--currentChar] = '-'; 128 } 129 return new String(result, currentChar, resLengthInChars - currentChar); 130 } 131 132 /** 133 * Builds the correspondent {@code String} representation of {@code val} 134 * being scaled by {@code scale}. 135 * 136 * @see BigInteger#toString() 137 * @see BigDecimal#toString() 138 */ 139 static String toDecimalScaledString(BigInteger val, int scale) { 140 // BEGIN android-added 141 val.establishOldRepresentation("Conversion.toDecimalScaledString"); 142 // END android-added 143 int sign = val.sign; 144 int numberLength = val.numberLength; 145 int digits[] = val.digits; 146 int resLengthInChars; 147 int currentChar; 148 char result[]; 149 150 if (sign == 0) { 151 switch (scale) { 152 case 0: 153 return "0"; //$NON-NLS-1$ 154 case 1: 155 return "0.0"; //$NON-NLS-1$ 156 case 2: 157 return "0.00"; //$NON-NLS-1$ 158 case 3: 159 return "0.000"; //$NON-NLS-1$ 160 case 4: 161 return "0.0000"; //$NON-NLS-1$ 162 case 5: 163 return "0.00000"; //$NON-NLS-1$ 164 case 6: 165 return "0.000000"; //$NON-NLS-1$ 166 default: 167 StringBuffer result1 = new StringBuffer(); 168 if (scale < 0) { 169 result1.append("0E+"); //$NON-NLS-1$ 170 } else { 171 result1.append("0E"); //$NON-NLS-1$ 172 } 173 result1.append(-scale); 174 return result1.toString(); 175 } 176 } 177 // one 32-bit unsigned value may contains 10 decimal digits 178 resLengthInChars = numberLength * 10 + 1 + 7; 179 // Explanation why +1+7: 180 // +1 - one char for sign if needed. 181 // +7 - For "special case 2" (see below) we have 7 free chars for 182 // inserting necessary scaled digits. 183 result = new char[resLengthInChars + 1]; 184 // allocated [resLengthInChars+1] characters. 185 // a free latest character may be used for "special case 1" (see 186 // below) 187 currentChar = resLengthInChars; 188 if (numberLength == 1) { 189 int highDigit = digits[0]; 190 if (highDigit < 0) { 191 long v = highDigit & 0xFFFFFFFFL; 192 do { 193 long prev = v; 194 v /= 10; 195 result[--currentChar] = (char) (0x0030 + ((int) (prev - v * 10))); 196 } while (v != 0); 197 } else { 198 int v = highDigit; 199 do { 200 int prev = v; 201 v /= 10; 202 result[--currentChar] = (char) (0x0030 + (prev - v * 10)); 203 } while (v != 0); 204 } 205 } else { 206 int temp[] = new int[numberLength]; 207 int tempLen = numberLength; 208 System.arraycopy(digits, 0, temp, 0, tempLen); 209 BIG_LOOP: while (true) { 210 // divide the array of digits by bigRadix and convert 211 // remainders 212 // to characters collecting them in the char array 213 long result11 = 0; 214 for (int i1 = tempLen - 1; i1 >= 0; i1--) { 215 long temp1 = (result11 << 32) 216 + (temp[i1] & 0xFFFFFFFFL); 217 long res = divideLongByBillion(temp1); 218 temp[i1] = (int) res; 219 result11 = (int) (res >> 32); 220 } 221 int resDigit = (int) result11; 222 int previous = currentChar; 223 do { 224 result[--currentChar] = (char) (0x0030 + (resDigit % 10)); 225 } while (((resDigit /= 10) != 0) && (currentChar != 0)); 226 int delta = 9 - previous + currentChar; 227 for (int i = 0; (i < delta) && (currentChar > 0); i++) { 228 result[--currentChar] = '0'; 229 } 230 int j = tempLen - 1; 231 for (; temp[j] == 0; j--) { 232 if (j == 0) { // means temp[0] == 0 233 break BIG_LOOP; 234 } 235 } 236 tempLen = j + 1; 237 } 238 while (result[currentChar] == '0') { 239 currentChar++; 240 } 241 } 242 boolean negNumber = (sign < 0); 243 int exponent = resLengthInChars - currentChar - scale - 1; 244 if (scale == 0) { 245 if (negNumber) { 246 result[--currentChar] = '-'; 247 } 248 return new String(result, currentChar, resLengthInChars 249 - currentChar); 250 } 251 if ((scale > 0) && (exponent >= -6)) { 252 if (exponent >= 0) { 253 // special case 1 254 int insertPoint = currentChar + exponent; 255 for (int j = resLengthInChars - 1; j >= insertPoint; j--) { 256 result[j + 1] = result[j]; 257 } 258 result[++insertPoint] = '.'; 259 if (negNumber) { 260 result[--currentChar] = '-'; 261 } 262 return new String(result, currentChar, resLengthInChars 263 - currentChar + 1); 264 } 265 // special case 2 266 for (int j = 2; j < -exponent + 1; j++) { 267 result[--currentChar] = '0'; 268 } 269 result[--currentChar] = '.'; 270 result[--currentChar] = '0'; 271 if (negNumber) { 272 result[--currentChar] = '-'; 273 } 274 return new String(result, currentChar, resLengthInChars 275 - currentChar); 276 } 277 int startPoint = currentChar + 1; 278 int endPoint = resLengthInChars; 279 StringBuffer result1 = new StringBuffer(16 + endPoint - startPoint); 280 if (negNumber) { 281 result1.append('-'); 282 } 283 if (endPoint - startPoint >= 1) { 284 result1.append(result[currentChar]); 285 result1.append('.'); 286 result1.append(result, currentChar + 1, resLengthInChars 287 - currentChar - 1); 288 } else { 289 result1.append(result, currentChar, resLengthInChars 290 - currentChar); 291 } 292 result1.append('E'); 293 if (exponent > 0) { 294 result1.append('+'); 295 } 296 result1.append(Integer.toString(exponent)); 297 return result1.toString(); 298 } 299 300 /* can process only 32-bit numbers */ 301 static String toDecimalScaledString(long value, int scale) { 302 int resLengthInChars; 303 int currentChar; 304 char result[]; 305 boolean negNumber = value < 0; 306 if(negNumber) { 307 value = -value; 308 } 309 if (value == 0) { 310 switch (scale) { 311 case 0: return "0"; //$NON-NLS-1$ 312 case 1: return "0.0"; //$NON-NLS-1$ 313 case 2: return "0.00"; //$NON-NLS-1$ 314 case 3: return "0.000"; //$NON-NLS-1$ 315 case 4: return "0.0000"; //$NON-NLS-1$ 316 case 5: return "0.00000"; //$NON-NLS-1$ 317 case 6: return "0.000000"; //$NON-NLS-1$ 318 default: 319 StringBuffer result1 = new StringBuffer(); 320 if (scale < 0) { 321 result1.append("0E+"); //$NON-NLS-1$ 322 } else { 323 result1.append("0E"); //$NON-NLS-1$ 324 } 325 result1.append( (scale == Integer.MIN_VALUE) ? "2147483648" : Integer.toString(-scale)); //$NON-NLS-1$ 326 return result1.toString(); 327 } 328 } 329 // one 32-bit unsigned value may contains 10 decimal digits 330 resLengthInChars = 18; 331 // Explanation why +1+7: 332 // +1 - one char for sign if needed. 333 // +7 - For "special case 2" (see below) we have 7 free chars for 334 // inserting necessary scaled digits. 335 result = new char[resLengthInChars+1]; 336 // Allocated [resLengthInChars+1] characters. 337 // a free latest character may be used for "special case 1" (see below) 338 currentChar = resLengthInChars; 339 long v = value; 340 do { 341 long prev = v; 342 v /= 10; 343 result[--currentChar] = (char) (0x0030 + (prev - v * 10)); 344 } while (v != 0); 345 346 long exponent = (long)resLengthInChars - (long)currentChar - scale - 1L; 347 if (scale == 0) { 348 if (negNumber) { 349 result[--currentChar] = '-'; 350 } 351 return new String(result, currentChar, resLengthInChars - currentChar); 352 } 353 if (scale > 0 && exponent >= -6) { 354 if (exponent >= 0) { 355 // special case 1 356 int insertPoint = currentChar + (int) exponent ; 357 for(int j=resLengthInChars-1; j>=insertPoint; j--) { 358 result[j+1] = result[j]; 359 } 360 result[++insertPoint]='.'; 361 if (negNumber) { 362 result[--currentChar] = '-'; 363 } 364 return new String(result, currentChar, resLengthInChars - currentChar + 1); 365 } 366 // special case 2 367 for (int j = 2; j < -exponent + 1; j++) { 368 result[--currentChar] = '0'; 369 } 370 result[--currentChar] = '.'; 371 result[--currentChar] = '0'; 372 if (negNumber) { 373 result[--currentChar] = '-'; 374 } 375 return new String(result, currentChar, resLengthInChars - currentChar); 376 } 377 int startPoint = currentChar + 1; 378 int endPoint = resLengthInChars; 379 StringBuffer result1 = new StringBuffer(16+endPoint-startPoint); 380 if (negNumber) { 381 result1.append('-'); 382 } 383 if (endPoint - startPoint >= 1) { 384 result1.append(result[currentChar]); 385 result1.append('.'); 386 result1.append(result,currentChar+1,resLengthInChars - currentChar-1); 387 } else { 388 result1.append(result,currentChar,resLengthInChars - currentChar); 389 } 390 result1.append('E'); 391 if (exponent > 0) { 392 result1.append('+'); 393 } 394 result1.append(Long.toString(exponent)); 395 return result1.toString(); 396 } 397 398 static long divideLongByBillion(long a) { 399 long quot; 400 long rem; 401 402 if (a >= 0) { 403 long bLong = 1000000000L; 404 quot = (a / bLong); 405 rem = (a % bLong); 406 } else { 407 /* 408 * Make the dividend positive shifting it right by 1 bit then get 409 * the quotient an remainder and correct them properly 410 */ 411 long aPos = a >>> 1; 412 long bPos = 1000000000L >>> 1; 413 quot = aPos / bPos; 414 rem = aPos % bPos; 415 // double the remainder and add 1 if 'a' is odd 416 rem = (rem << 1) + (a & 1); 417 } 418 return ((rem << 32) | (quot & 0xFFFFFFFFL)); 419 } 420 421 /** @see BigInteger#doubleValue() */ 422 static double bigInteger2Double(BigInteger val) { 423 // BEGIN android-added 424 val.establishOldRepresentation("Conversion.bigInteger2Double"); 425 // END android-added 426 // val.bitLength() < 64 427 if ((val.numberLength < 2) 428 || ((val.numberLength == 2) && (val.digits[1] > 0))) { 429 return val.longValue(); 430 } 431 // val.bitLength() >= 33 * 32 > 1024 432 if (val.numberLength > 32) { 433 return ((val.sign > 0) ? Double.POSITIVE_INFINITY 434 : Double.NEGATIVE_INFINITY); 435 } 436 int bitLen = val.abs().bitLength(); 437 long exponent = bitLen - 1; 438 int delta = bitLen - 54; 439 // We need 54 top bits from this, the 53th bit is always 1 in lVal. 440 long lVal = val.abs().shiftRight(delta).longValue(); 441 /* 442 * Take 53 bits from lVal to mantissa. The least significant bit is 443 * needed for rounding. 444 */ 445 long mantissa = lVal & 0x1FFFFFFFFFFFFFL; 446 if (exponent == 1023) { 447 if (mantissa == 0X1FFFFFFFFFFFFFL) { 448 return ((val.sign > 0) ? Double.POSITIVE_INFINITY 449 : Double.NEGATIVE_INFINITY); 450 } 451 if (mantissa == 0x1FFFFFFFFFFFFEL) { 452 return ((val.sign > 0) ? Double.MAX_VALUE : -Double.MAX_VALUE); 453 } 454 } 455 // Round the mantissa 456 if (((mantissa & 1) == 1) 457 && (((mantissa & 2) == 2) || BitLevel.nonZeroDroppedBits(delta, 458 val.digits))) { 459 mantissa += 2; 460 } 461 mantissa >>= 1; // drop the rounding bit 462 long resSign = (val.sign < 0) ? 0x8000000000000000L : 0; 463 exponent = ((1023 + exponent) << 52) & 0x7FF0000000000000L; 464 long result = resSign | exponent | mantissa; 465 return Double.longBitsToDouble(result); 466 } 467 } 468
