The Android Open Source Project | 0eec464 | 2012-04-01 00:00:00 -0700 | [diff] [blame] | 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 | } |