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 17package 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 */ 37public 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 static final char[] UPPER_CASE_DIGITS = { 112 '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 113 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 114 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 115 'U', 'V', 'W', 'X', 'Y', 'Z' 116 }; 117 118 private IntegralToString() { 119 } 120 121 /** 122 * Equivalent to Integer.toString(i, radix). 123 */ 124 public static String intToString(int i, int radix) { 125 if (radix < Character.MIN_RADIX || radix > Character.MAX_RADIX) { 126 radix = 10; 127 } 128 if (radix == 10) { 129 return intToString(i); 130 } 131 132 /* 133 * If i is positive, negate it. This is the opposite of what one might 134 * expect. It is necessary because the range of the negative values is 135 * strictly larger than that of the positive values: there is no 136 * positive value corresponding to Integer.MIN_VALUE. 137 */ 138 boolean negative = false; 139 if (i < 0) { 140 negative = true; 141 } else { 142 i = -i; 143 } 144 145 int bufLen = radix < 8 ? 33 : 12; // Max chars in result (conservative) 146 char[] buf = new char[bufLen]; 147 int cursor = bufLen; 148 149 do { 150 int q = i / radix; 151 buf[--cursor] = DIGITS[radix * q - i]; 152 i = q; 153 } while (i != 0); 154 155 if (negative) { 156 buf[--cursor] = '-'; 157 } 158 159 return new String(cursor, bufLen - cursor, buf); 160 } 161 162 /** 163 * Equivalent to Integer.toString(i). 164 */ 165 public static String intToString(int i) { 166 return convertInt(null, i); 167 } 168 169 /** 170 * Equivalent to sb.append(Integer.toString(i)). 171 */ 172 public static void appendInt(AbstractStringBuilder sb, int i) { 173 convertInt(sb, i); 174 } 175 176 /** 177 * Returns the string representation of i and leaves sb alone if sb is null. 178 * Returns null and appends the string representation of i to sb if sb is non-null. 179 */ 180 private static String convertInt(AbstractStringBuilder sb, int i) { 181 boolean negative = false; 182 String quickResult = null; 183 if (i < 0) { 184 negative = true; 185 i = -i; 186 if (i < 100) { 187 if (i < 0) { 188 // If -n is still negative, n is Integer.MIN_VALUE 189 quickResult = "-2147483648"; 190 } else { 191 quickResult = SMALL_NEGATIVE_VALUES[i]; 192 if (quickResult == null) { 193 SMALL_NEGATIVE_VALUES[i] = quickResult = 194 i < 10 ? stringOf('-', ONES[i]) : stringOf('-', TENS[i], ONES[i]); 195 } 196 } 197 } 198 } else { 199 if (i < 100) { 200 quickResult = SMALL_NONNEGATIVE_VALUES[i]; 201 if (quickResult == null) { 202 SMALL_NONNEGATIVE_VALUES[i] = quickResult = 203 i < 10 ? stringOf(ONES[i]) : stringOf(TENS[i], ONES[i]); 204 } 205 } 206 } 207 if (quickResult != null) { 208 if (sb != null) { 209 sb.append0(quickResult); 210 return null; 211 } 212 return quickResult; 213 } 214 215 int bufLen = 11; // Max number of chars in result 216 char[] buf = (sb != null) ? BUFFER.get() : new char[bufLen]; 217 int cursor = bufLen; 218 219 // Calculate digits two-at-a-time till remaining digits fit in 16 bits 220 while (i >= (1 << 16)) { 221 // Compute q = n/100 and r = n % 100 as per "Hacker's Delight" 10-8 222 int q = (int) ((0x51EB851FL * i) >>> 37); 223 int r = i - 100*q; 224 buf[--cursor] = ONES[r]; 225 buf[--cursor] = TENS[r]; 226 i = q; 227 } 228 229 // Calculate remaining digits one-at-a-time for performance 230 while (i != 0) { 231 // Compute q = n/10 and r = n % 10 as per "Hacker's Delight" 10-8 232 int q = (0xCCCD * i) >>> 19; 233 int r = i - 10*q; 234 buf[--cursor] = DIGITS[r]; 235 i = q; 236 } 237 238 if (negative) { 239 buf[--cursor] = '-'; 240 } 241 242 if (sb != null) { 243 sb.append0(buf, cursor, bufLen - cursor); 244 return null; 245 } else { 246 return new String(cursor, bufLen - cursor, buf); 247 } 248 } 249 250 /** 251 * Equivalent to Long.toString(v, radix). 252 */ 253 public static String longToString(long v, int radix) { 254 int i = (int) v; 255 if (i == v) { 256 return intToString(i, radix); 257 } 258 259 if (radix < Character.MIN_RADIX || radix > Character.MAX_RADIX) { 260 radix = 10; 261 } 262 if (radix == 10) { 263 return longToString(v); 264 } 265 266 /* 267 * If v is positive, negate it. This is the opposite of what one might 268 * expect. It is necessary because the range of the negative values is 269 * strictly larger than that of the positive values: there is no 270 * positive value corresponding to Integer.MIN_VALUE. 271 */ 272 boolean negative = false; 273 if (v < 0) { 274 negative = true; 275 } else { 276 v = -v; 277 } 278 279 int bufLen = radix < 8 ? 65 : 23; // Max chars in result (conservative) 280 char[] buf = new char[bufLen]; 281 int cursor = bufLen; 282 283 do { 284 long q = v / radix; 285 buf[--cursor] = DIGITS[(int) (radix * q - v)]; 286 v = q; 287 } while (v != 0); 288 289 if (negative) { 290 buf[--cursor] = '-'; 291 } 292 293 return new String(cursor, bufLen - cursor, buf); 294 } 295 296 /** 297 * Equivalent to Long.toString(l). 298 */ 299 public static String longToString(long l) { 300 return convertLong(null, l); 301 } 302 303 /** 304 * Equivalent to sb.append(Long.toString(l)). 305 */ 306 public static void appendLong(AbstractStringBuilder sb, long l) { 307 convertLong(sb, l); 308 } 309 310 /** 311 * Returns the string representation of n and leaves sb alone if sb is null. 312 * Returns null and appends the string representation of n to sb if sb is non-null. 313 */ 314 private static String convertLong(AbstractStringBuilder sb, long n) { 315 int i = (int) n; 316 if (i == n) { 317 return convertInt(sb, i); 318 } 319 320 boolean negative = (n < 0); 321 if (negative) { 322 n = -n; 323 if (n < 0) { 324 // If -n is still negative, n is Long.MIN_VALUE 325 String quickResult = "-9223372036854775808"; 326 if (sb != null) { 327 sb.append0(quickResult); 328 return null; 329 } 330 return quickResult; 331 } 332 } 333 334 int bufLen = 20; // Maximum number of chars in result 335 char[] buf = (sb != null) ? BUFFER.get() : new char[bufLen]; 336 337 int low = (int) (n % 1000000000); // Extract low-order 9 digits 338 int cursor = intIntoCharArray(buf, bufLen, low); 339 340 // Zero-pad Low order part to 9 digits 341 while (cursor != (bufLen - 9)) { 342 buf[--cursor] = '0'; 343 } 344 345 /* 346 * The remaining digits are (n - low) / 1,000,000,000. This 347 * "exact division" is done as per the online addendum to Hank Warren's 348 * "Hacker's Delight" 10-20, http://www.hackersdelight.org/divcMore.pdf 349 */ 350 n = ((n - low) >>> 9) * 0x8E47CE423A2E9C6DL; 351 352 /* 353 * If the remaining digits fit in an int, emit them using a 354 * single call to intIntoCharArray. Otherwise, strip off the 355 * low-order digit, put it in buf, and then call intIntoCharArray 356 * on the remaining digits (which now fit in an int). 357 */ 358 if ((n & (-1L << 32)) == 0) { 359 cursor = intIntoCharArray(buf, cursor, (int) n); 360 } else { 361 /* 362 * Set midDigit to n % 10 363 */ 364 int lo32 = (int) n; 365 int hi32 = (int) (n >>> 32); 366 367 // midDigit = ((unsigned) low32) % 10, per "Hacker's Delight" 10-21 368 int midDigit = MOD_10_TABLE[(0x19999999 * lo32 + (lo32 >>> 1) + (lo32 >>> 3)) >>> 28]; 369 370 // Adjust midDigit for hi32. (assert hi32 == 1 || hi32 == 2) 371 midDigit -= hi32 << 2; // 1L << 32 == -4 MOD 10 372 if (midDigit < 0) { 373 midDigit += 10; 374 } 375 buf[--cursor] = DIGITS[midDigit]; 376 377 // Exact division as per Warren 10-20 378 int rest = ((int) ((n - midDigit) >>> 1)) * 0xCCCCCCCD; 379 cursor = intIntoCharArray(buf, cursor, rest); 380 } 381 382 if (negative) { 383 buf[--cursor] = '-'; 384 } 385 if (sb != null) { 386 sb.append0(buf, cursor, bufLen - cursor); 387 return null; 388 } else { 389 return new String(cursor, bufLen - cursor, buf); 390 } 391 } 392 393 /** 394 * Inserts the unsigned decimal integer represented by n into the specified 395 * character array starting at position cursor. Returns the index after 396 * the last character inserted (i.e., the value to pass in as cursor the 397 * next time this method is called). Note that n is interpreted as a large 398 * positive integer (not a negative integer) if its sign bit is set. 399 */ 400 private static int intIntoCharArray(char[] buf, int cursor, int n) { 401 // Calculate digits two-at-a-time till remaining digits fit in 16 bits 402 while ((n & 0xffff0000) != 0) { 403 /* 404 * Compute q = n/100 and r = n % 100 as per "Hacker's Delight" 10-8. 405 * This computation is slightly different from the corresponding 406 * computation in intToString: the shifts before and after 407 * multiply can't be combined, as that would yield the wrong result 408 * if n's sign bit were set. 409 */ 410 int q = (int) ((0x51EB851FL * (n >>> 2)) >>> 35); 411 int r = n - 100*q; 412 buf[--cursor] = ONES[r]; 413 buf[--cursor] = TENS[r]; 414 n = q; 415 } 416 417 // Calculate remaining digits one-at-a-time for performance 418 while (n != 0) { 419 // Compute q = n / 10 and r = n % 10 as per "Hacker's Delight" 10-8 420 int q = (0xCCCD * n) >>> 19; 421 int r = n - 10*q; 422 buf[--cursor] = DIGITS[r]; 423 n = q; 424 } 425 return cursor; 426 } 427 428 public static String intToBinaryString(int i) { 429 int bufLen = 32; // Max number of binary digits in an int 430 char[] buf = new char[bufLen]; 431 int cursor = bufLen; 432 433 do { 434 buf[--cursor] = DIGITS[i & 1]; 435 } while ((i >>>= 1) != 0); 436 437 return new String(cursor, bufLen - cursor, buf); 438 } 439 440 public static String longToBinaryString(long v) { 441 int i = (int) v; 442 if (v >= 0 && i == v) { 443 return intToBinaryString(i); 444 } 445 446 int bufLen = 64; // Max number of binary digits in a long 447 char[] buf = new char[bufLen]; 448 int cursor = bufLen; 449 450 do { 451 buf[--cursor] = DIGITS[((int) v) & 1]; 452 } while ((v >>>= 1) != 0); 453 454 return new String(cursor, bufLen - cursor, buf); 455 } 456 457 public static StringBuilder appendByteAsHex(StringBuilder sb, byte b, boolean upperCase) { 458 char[] digits = upperCase ? UPPER_CASE_DIGITS : DIGITS; 459 sb.append(digits[(b >> 4) & 0xf]); 460 sb.append(digits[b & 0xf]); 461 return sb; 462 } 463 464 public static String byteToHexString(byte b, boolean upperCase) { 465 char[] digits = upperCase ? UPPER_CASE_DIGITS : DIGITS; 466 char[] buf = new char[2]; // We always want two digits. 467 buf[0] = digits[(b >> 4) & 0xf]; 468 buf[1] = digits[b & 0xf]; 469 return new String(0, 2, buf); 470 } 471 472 public static String bytesToHexString(byte[] bytes, boolean upperCase) { 473 char[] digits = upperCase ? UPPER_CASE_DIGITS : DIGITS; 474 char[] buf = new char[bytes.length * 2]; 475 int c = 0; 476 for (byte b : bytes) { 477 buf[c++] = digits[(b >> 4) & 0xf]; 478 buf[c++] = digits[b & 0xf]; 479 } 480 return new String(buf); 481 } 482 483 public static String intToHexString(int i, boolean upperCase, int minWidth) { 484 int bufLen = 8; // Max number of hex digits in an int 485 char[] buf = new char[bufLen]; 486 int cursor = bufLen; 487 488 char[] digits = upperCase ? UPPER_CASE_DIGITS : DIGITS; 489 do { 490 buf[--cursor] = digits[i & 0xf]; 491 } while ((i >>>= 4) != 0 || (bufLen - cursor < minWidth)); 492 493 return new String(cursor, bufLen - cursor, buf); 494 } 495 496 public static String longToHexString(long v) { 497 int i = (int) v; 498 if (v >= 0 && i == v) { 499 return intToHexString(i, false, 0); 500 } 501 502 int bufLen = 16; // Max number of hex digits in a long 503 char[] buf = new char[bufLen]; 504 int cursor = bufLen; 505 506 do { 507 buf[--cursor] = DIGITS[((int) v) & 0xF]; 508 } while ((v >>>= 4) != 0); 509 510 return new String(cursor, bufLen - cursor, buf); 511 } 512 513 public static String intToOctalString(int i) { 514 int bufLen = 11; // Max number of octal digits in an int 515 char[] buf = new char[bufLen]; 516 int cursor = bufLen; 517 518 do { 519 buf[--cursor] = DIGITS[i & 7]; 520 } while ((i >>>= 3) != 0); 521 522 return new String(cursor, bufLen - cursor, buf); 523 } 524 525 public static String longToOctalString(long v) { 526 int i = (int) v; 527 if (v >= 0 && i == v) { 528 return intToOctalString(i); 529 } 530 int bufLen = 22; // Max number of octal digits in a long 531 char[] buf = new char[bufLen]; 532 int cursor = bufLen; 533 534 do { 535 buf[--cursor] = DIGITS[((int) v) & 7]; 536 } while ((v >>>= 3) != 0); 537 538 return new String(cursor, bufLen - cursor, buf); 539 } 540 541 /** 542 * Returns a string composed of the specified characters. Note that the 543 * autoboxing does *not* result in an extra copy of the char array: we are 544 * using a package-private string constructor that incorporates the 545 * "autoboxing array" into the new string. 546 */ 547 private static String stringOf(char... args) { 548 return new String(0, args.length, args); 549 } 550} 551