1 /* 2 * Copyright (C) 2010 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 package java.lang; 18 19 /** 20 * Converts integral types to strings. This class is public but hidden so that it can also be 21 * used by java.util.Formatter to speed up %d. This class is in java.lang so that it can take 22 * advantage of the package-private String constructor. 23 * 24 * The most important methods are appendInt/appendLong and intToString(int)/longToString(int). 25 * The former are used in the implementation of StringBuilder, StringBuffer, and Formatter, while 26 * the latter are used by Integer.toString and Long.toString. 27 * 28 * The append methods take AbstractStringBuilder rather than Appendable because the latter requires 29 * CharSequences, while we only have raw char[]s. Since much of the savings come from not creating 30 * any garbage, we can't afford temporary CharSequence instances. 31 * 32 * One day the performance advantage of the binary/hex/octal specializations will be small enough 33 * that we can lose the duplication, but until then this class offers the full set. 34 * 35 * @hide 36 */ 37 public final class IntegralToString { 38 /** 39 * When appending to an AbstractStringBuilder, this thread-local char[] lets us avoid 40 * allocation of a temporary array. (We can't write straight into the AbstractStringBuilder 41 * because it's almost as expensive to work out the exact length of the result as it is to 42 * do the formatting. We could try being conservative and "delete"-ing the unused space 43 * afterwards, but then we'd need to duplicate convertInt and convertLong rather than share 44 * the code.) 45 */ 46 private static final ThreadLocal<char[]> BUFFER = new ThreadLocal<char[]>() { 47 @Override protected char[] initialValue() { 48 return new char[20]; // Maximum length of a base-10 long. 49 } 50 }; 51 52 /** 53 * These tables are used to special-case toString computation for 54 * small values. This serves three purposes: it reduces memory usage; 55 * it increases performance for small values; and it decreases the 56 * number of comparisons required to do the length computation. 57 * Elements of this table are lazily initialized on first use. 58 * No locking is necessary, i.e., we use the non-volatile, racy 59 * single-check idiom. 60 */ 61 private static final String[] SMALL_NONNEGATIVE_VALUES = new String[100]; 62 private static final String[] SMALL_NEGATIVE_VALUES = new String[100]; 63 64 /** TENS[i] contains the tens digit of the number i, 0 <= i <= 99. */ 65 private static final char[] TENS = { 66 '0', '0', '0', '0', '0', '0', '0', '0', '0', '0', 67 '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', 68 '2', '2', '2', '2', '2', '2', '2', '2', '2', '2', 69 '3', '3', '3', '3', '3', '3', '3', '3', '3', '3', 70 '4', '4', '4', '4', '4', '4', '4', '4', '4', '4', 71 '5', '5', '5', '5', '5', '5', '5', '5', '5', '5', 72 '6', '6', '6', '6', '6', '6', '6', '6', '6', '6', 73 '7', '7', '7', '7', '7', '7', '7', '7', '7', '7', 74 '8', '8', '8', '8', '8', '8', '8', '8', '8', '8', 75 '9', '9', '9', '9', '9', '9', '9', '9', '9', '9' 76 }; 77 78 /** Ones [i] contains the tens digit of the number i, 0 <= i <= 99. */ 79 private static final char[] ONES = { 80 '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 81 '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 82 '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 83 '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 84 '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 85 '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 86 '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 87 '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 88 '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 89 '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 90 }; 91 92 /** 93 * Table for MOD / DIV 10 computation described in Section 10-21 94 * of Hank Warren's "Hacker's Delight" online addendum. 95 * http://www.hackersdelight.org/divcMore.pdf 96 */ 97 private static final char[] MOD_10_TABLE = { 98 0, 1, 2, 2, 3, 3, 4, 5, 5, 6, 7, 7, 8, 8, 9, 0 99 }; 100 101 /** 102 * The digits for every supported radix. 103 */ 104 private static final char[] DIGITS = { 105 '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 106 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 107 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 108 'u', 'v', 'w', 'x', 'y', 'z' 109 }; 110 111 private IntegralToString() { 112 } 113 114 /** 115 * Equivalent to Integer.toString(i, radix). 116 */ 117 public static String intToString(int i, int radix) { 118 if (radix < Character.MIN_RADIX || radix > Character.MAX_RADIX) { 119 radix = 10; 120 } 121 if (radix == 10) { 122 return intToString(i); 123 } 124 125 /* 126 * If i is positive, negate it. This is the opposite of what one might 127 * expect. It is necessary because the range of the negative values is 128 * strictly larger than that of the positive values: there is no 129 * positive value corresponding to Integer.MIN_VALUE. 130 */ 131 boolean negative = false; 132 if (i < 0) { 133 negative = true; 134 } else { 135 i = -i; 136 } 137 138 int bufLen = radix < 8 ? 33 : 12; // Max chars in result (conservative) 139 char[] buf = new char[bufLen]; 140 int cursor = bufLen; 141 142 do { 143 int q = i / radix; 144 buf[--cursor] = DIGITS[radix * q - i]; 145 i = q; 146 } while (i != 0); 147 148 if (negative) { 149 buf[--cursor] = '-'; 150 } 151 152 return new String(cursor, bufLen - cursor, buf); 153 } 154 155 /** 156 * Equivalent to Integer.toString(i). 157 */ 158 public static String intToString(int i) { 159 return convertInt(null, i); 160 } 161 162 /** 163 * Equivalent to sb.append(Integer.toString(i)). 164 */ 165 public static void appendInt(AbstractStringBuilder sb, int i) { 166 convertInt(sb, i); 167 } 168 169 /** 170 * Returns the string representation of i and leaves sb alone if sb is null. 171 * Returns null and appends the string representation of i to sb if sb is non-null. 172 */ 173 private static String convertInt(AbstractStringBuilder sb, int i) { 174 boolean negative = false; 175 String quickResult = null; 176 if (i < 0) { 177 negative = true; 178 i = -i; 179 if (i < 100) { 180 if (i < 0) { 181 // If -n is still negative, n is Integer.MIN_VALUE 182 quickResult = "-2147483648"; 183 } else { 184 String result = SMALL_NEGATIVE_VALUES[i]; 185 if (result == null) { 186 SMALL_NEGATIVE_VALUES[i] = result = 187 i < 10 ? stringOf('-', ONES[i]) : stringOf('-', TENS[i], ONES[i]); 188 } 189 } 190 } 191 } else { 192 if (i < 100) { 193 quickResult = SMALL_NONNEGATIVE_VALUES[i]; 194 if (quickResult == null) { 195 SMALL_NONNEGATIVE_VALUES[i] = quickResult = 196 i < 10 ? stringOf(ONES[i]) : stringOf(TENS[i], ONES[i]); 197 } 198 } 199 } 200 if (quickResult != null) { 201 if (sb != null) { 202 sb.append0(quickResult); 203 return null; 204 } 205 return quickResult; 206 } 207 208 int bufLen = 11; // Max number of chars in result 209 char[] buf = (sb != null) ? BUFFER.get() : new char[bufLen]; 210 int cursor = bufLen; 211 212 // Calculate digits two-at-a-time till remaining digits fit in 16 bits 213 while (i >= (1 << 16)) { 214 // Compute q = n/100 and r = n % 100 as per "Hacker's Delight" 10-8 215 int q = (int) ((0x51EB851FL * i) >>> 37); 216 int r = i - 100*q; 217 buf[--cursor] = ONES[r]; 218 buf[--cursor] = TENS[r]; 219 i = q; 220 } 221 222 // Calculate remaining digits one-at-a-time for performance 223 while (i != 0) { 224 // Compute q = n/10 and r = n % 10 as per "Hacker's Delight" 10-8 225 int q = (0xCCCD * i) >>> 19; 226 int r = i - 10*q; 227 buf[--cursor] = DIGITS[r]; 228 i = q; 229 } 230 231 if (negative) { 232 buf[--cursor] = '-'; 233 } 234 235 if (sb != null) { 236 sb.append0(buf, cursor, bufLen - cursor); 237 return null; 238 } else { 239 return new String(cursor, bufLen - cursor, buf); 240 } 241 } 242 243 /** 244 * Equivalent to Long.toString(v, radix). 245 */ 246 public static String longToString(long v, int radix) { 247 int i = (int) v; 248 if (i == v) { 249 return intToString(i, radix); 250 } 251 252 if (radix < Character.MIN_RADIX || radix > Character.MAX_RADIX) { 253 radix = 10; 254 } 255 if (radix == 10) { 256 return longToString(v); 257 } 258 259 /* 260 * If v is positive, negate it. This is the opposite of what one might 261 * expect. It is necessary because the range of the negative values is 262 * strictly larger than that of the positive values: there is no 263 * positive value corresponding to Integer.MIN_VALUE. 264 */ 265 boolean negative = false; 266 if (v < 0) { 267 negative = true; 268 } else { 269 v = -v; 270 } 271 272 int bufLen = radix < 8 ? 65 : 23; // Max chars in result (conservative) 273 char[] buf = new char[bufLen]; 274 int cursor = bufLen; 275 276 do { 277 long q = v / radix; 278 buf[--cursor] = DIGITS[(int) (radix * q - v)]; 279 v = q; 280 } while (v != 0); 281 282 if (negative) { 283 buf[--cursor] = '-'; 284 } 285 286 return new String(cursor, bufLen - cursor, buf); 287 } 288 289 /** 290 * Equivalent to Long.toString(l). 291 */ 292 public static String longToString(long l) { 293 return convertLong(null, l); 294 } 295 296 /** 297 * Equivalent to sb.append(Long.toString(l)). 298 */ 299 public static void appendLong(AbstractStringBuilder sb, long l) { 300 convertLong(sb, l); 301 } 302 303 /** 304 * Returns the string representation of n and leaves sb alone if sb is null. 305 * Returns null and appends the string representation of n to sb if sb is non-null. 306 */ 307 private static String convertLong(AbstractStringBuilder sb, long n) { 308 int i = (int) n; 309 if (i == n) { 310 return convertInt(sb, i); 311 } 312 313 boolean negative = (n < 0); 314 if (negative) { 315 n = -n; 316 if (n < 0) { 317 // If -n is still negative, n is Long.MIN_VALUE 318 String quickResult = "-9223372036854775808"; 319 if (sb != null) { 320 sb.append0(quickResult); 321 return null; 322 } 323 return quickResult; 324 } 325 } 326 327 int bufLen = 20; // Maximum number of chars in result 328 char[] buf = (sb != null) ? BUFFER.get() : new char[bufLen]; 329 330 int low = (int) (n % 1000000000); // Extract low-order 9 digits 331 int cursor = intIntoCharArray(buf, bufLen, low); 332 333 // Zero-pad Low order part to 9 digits 334 while (cursor != (bufLen - 9)) { 335 buf[--cursor] = '0'; 336 } 337 338 /* 339 * The remaining digits are (n - low) / 1,000,000,000. This 340 * "exact division" is done as per the online addendum to Hank Warren's 341 * "Hacker's Delight" 10-20, http://www.hackersdelight.org/divcMore.pdf 342 */ 343 n = ((n - low) >>> 9) * 0x8E47CE423A2E9C6DL; 344 345 /* 346 * If the remaining digits fit in an int, emit them using a 347 * single call to intIntoCharArray. Otherwise, strip off the 348 * low-order digit, put it in buf, and then call intIntoCharArray 349 * on the remaining digits (which now fit in an int). 350 */ 351 if ((n & (-1L << 32)) == 0) { 352 cursor = intIntoCharArray(buf, cursor, (int) n); 353 } else { 354 /* 355 * Set midDigit to n % 10 356 */ 357 int lo32 = (int) n; 358 int hi32 = (int) (n >>> 32); 359 360 // midDigit = ((unsigned) low32) % 10, per "Hacker's Delight" 10-21 361 int midDigit = MOD_10_TABLE[(0x19999999 * lo32 + (lo32 >>> 1) + (lo32 >>> 3)) >>> 28]; 362 363 // Adjust midDigit for hi32. (assert hi32 == 1 || hi32 == 2) 364 midDigit -= hi32 << 2; // 1L << 32 == -4 MOD 10 365 if (midDigit < 0) { 366 midDigit += 10; 367 } 368 buf[--cursor] = DIGITS[midDigit]; 369 370 // Exact division as per Warren 10-20 371 int rest = ((int) ((n - midDigit) >>> 1)) * 0xCCCCCCCD; 372 cursor = intIntoCharArray(buf, cursor, rest); 373 } 374 375 if (negative) { 376 buf[--cursor] = '-'; 377 } 378 if (sb != null) { 379 sb.append0(buf, cursor, bufLen - cursor); 380 return null; 381 } else { 382 return new String(cursor, bufLen - cursor, buf); 383 } 384 } 385 386 /** 387 * Inserts the unsigned decimal integer represented by n into the specified 388 * character array starting at position cursor. Returns the index after 389 * the last character inserted (i.e., the value to pass in as cursor the 390 * next time this method is called). Note that n is interpreted as a large 391 * positive integer (not a negative integer) if its sign bit is set. 392 */ 393 private static int intIntoCharArray(char[] buf, int cursor, int n) { 394 // Calculate digits two-at-a-time till remaining digits fit in 16 bits 395 while ((n & 0xffff0000) != 0) { 396 /* 397 * Compute q = n/100 and r = n % 100 as per "Hacker's Delight" 10-8. 398 * This computation is slightly different from the corresponding 399 * computation in intToString: the shifts before and after 400 * multiply can't be combined, as that would yield the wrong result 401 * if n's sign bit were set. 402 */ 403 int q = (int) ((0x51EB851FL * (n >>> 2)) >>> 35); 404 int r = n - 100*q; 405 buf[--cursor] = ONES[r]; 406 buf[--cursor] = TENS[r]; 407 n = q; 408 } 409 410 // Calculate remaining digits one-at-a-time for performance 411 while (n != 0) { 412 // Compute q = n / 10 and r = n % 10 as per "Hacker's Delight" 10-8 413 int q = (0xCCCD * n) >>> 19; 414 int r = n - 10*q; 415 buf[--cursor] = DIGITS[r]; 416 n = q; 417 } 418 return cursor; 419 } 420 421 public static String intToBinaryString(int i) { 422 int bufLen = 32; // Max number of binary digits in an int 423 char[] buf = new char[bufLen]; 424 int cursor = bufLen; 425 426 do { 427 buf[--cursor] = DIGITS[i & 1]; 428 } while ((i >>>= 1) != 0); 429 430 return new String(cursor, bufLen - cursor, buf); 431 } 432 433 public static String longToBinaryString(long v) { 434 int i = (int) v; 435 if (v >= 0 && i == v) { 436 return intToBinaryString(i); 437 } 438 439 int bufLen = 64; // Max number of binary digits in a long 440 char[] buf = new char[bufLen]; 441 int cursor = bufLen; 442 443 do { 444 buf[--cursor] = DIGITS[((int) v) & 1]; 445 } while ((v >>>= 1) != 0); 446 447 return new String(cursor, bufLen - cursor, buf); 448 } 449 450 public static String intToHexString(int i) { 451 int bufLen = 8; // Max number of hex digits in an int 452 char[] buf = new char[bufLen]; 453 int cursor = bufLen; 454 455 do { 456 buf[--cursor] = DIGITS[i & 0xf]; 457 } while ((i >>>= 4) != 0); 458 459 return new String(cursor, bufLen - cursor, buf); 460 } 461 462 public static String longToHexString(long v) { 463 int i = (int) v; 464 if (v >= 0 && i == v) { 465 return intToHexString(i); 466 } 467 468 int bufLen = 16; // Max number of hex digits in a long 469 char[] buf = new char[bufLen]; 470 int cursor = bufLen; 471 472 do { 473 buf[--cursor] = DIGITS[((int) v) & 0xF]; 474 } while ((v >>>= 4) != 0); 475 476 return new String(cursor, bufLen - cursor, buf); 477 } 478 479 public static String intToOctalString(int i) { 480 int bufLen = 11; // Max number of octal digits in an int 481 char[] buf = new char[bufLen]; 482 int cursor = bufLen; 483 484 do { 485 buf[--cursor] = DIGITS[i & 7]; 486 } while ((i >>>= 3) != 0); 487 488 return new String(cursor, bufLen - cursor, buf); 489 } 490 491 public static String longToOctalString(long v) { 492 int i = (int) v; 493 if (v >= 0 && i == v) { 494 return intToOctalString(i); 495 } 496 int bufLen = 22; // Max number of octal digits in a long 497 char[] buf = new char[bufLen]; 498 int cursor = bufLen; 499 500 do { 501 buf[--cursor] = DIGITS[((int) v) & 7]; 502 } while ((v >>>= 3) != 0); 503 504 return new String(cursor, bufLen - cursor, buf); 505 } 506 507 /** 508 * Returns a string composed of the specified characters. Note that the 509 * autoboxing does *not* result in an extra copy of the char array: we are 510 * using a package-private string constructor that incorporates the 511 * "autoboxing array" into the new string. 512 */ 513 private static String stringOf(char... args) { 514 return new String(0, args.length, args); 515 } 516 } 517
