Rewrote all the toString and bit twiddling code in Integer and Long using
state-of-the-art recipes. The resulting code is much faster than what it
replaced, as well as being more concise. While I was in the neighborhood
I also cleaned up a few other things in the boxed primitives (TYPE fields,
small-value caches, etc.).
Addressed review comments.
diff --git a/libcore/luni/src/main/java/java/lang/Boolean.java b/libcore/luni/src/main/java/java/lang/Boolean.java
index 9c476a4..ae7fec1 100644
--- a/libcore/luni/src/main/java/java/lang/Boolean.java
+++ b/libcore/luni/src/main/java/java/lang/Boolean.java
@@ -38,9 +38,8 @@
* boolean}.
*/
@SuppressWarnings("unchecked")
- public static final Class<Boolean> TYPE = (Class<Boolean>) new boolean[0]
- .getClass().getComponentType();
-
+ public static final Class<Boolean> TYPE
+ = (Class<Boolean>) boolean[].class.getComponentType();
// Note: This can't be set to "boolean.class", since *that* is
// defined to be "java.lang.Boolean.TYPE";
@@ -122,15 +121,7 @@
* @since 1.5
*/
public int compareTo(Boolean that) {
- if (that == null) {
- throw new NullPointerException();
- }
-
- if (this.value == that.value) {
- return 0;
- }
-
- return this.value ? 1 : -1;
+ return value == that.value ? 0 : value ? 1 : -1;
}
/**
diff --git a/libcore/luni/src/main/java/java/lang/Byte.java b/libcore/luni/src/main/java/java/lang/Byte.java
index 7e20493..043a9f3 100644
--- a/libcore/luni/src/main/java/java/lang/Byte.java
+++ b/libcore/luni/src/main/java/java/lang/Byte.java
@@ -53,18 +53,12 @@
* The {@link Class} object that represents the primitive type {@code byte}.
*/
@SuppressWarnings("unchecked")
- public static final Class<Byte> TYPE = (Class<Byte>) new byte[0].getClass()
- .getComponentType();
-
+ public static final Class<Byte> TYPE
+ = (Class<Byte>) byte[].class.getComponentType();
// Note: This can't be set to "byte.class", since *that* is
// defined to be "java.lang.Byte.TYPE";
/**
- * A cache of instances used by {@link #valueOf(byte)} and auto-boxing.
- */
- private static final Byte[] CACHE = new Byte[256];
-
- /**
* Constructs a new {@code Byte} with the specified primitive byte value.
*
* @param value
@@ -295,10 +289,17 @@
* @since 1.5
*/
public static Byte valueOf(byte b) {
- synchronized (CACHE) {
- int idx = b - MIN_VALUE;
- Byte result = CACHE[idx];
- return (result == null ? CACHE[idx] = new Byte(b) : result);
+ return VALUES[b + 128];
+ }
+
+ /**
+ * A cache of instances used by {@link Byte#valueOf(byte)} and auto-boxing
+ */
+ private static final Byte[] VALUES = new Byte[256];
+
+ static {
+ for (int i = -128; i < 128; i++) {
+ VALUES[i + 128] = new Byte((byte) i);
}
}
}
diff --git a/libcore/luni/src/main/java/java/lang/Character.java b/libcore/luni/src/main/java/java/lang/Character.java
index f643183..56628e3 100644
--- a/libcore/luni/src/main/java/java/lang/Character.java
+++ b/libcore/luni/src/main/java/java/lang/Character.java
@@ -82,8 +82,8 @@
* The {@link Class} object that represents the primitive type {@code char}.
*/
@SuppressWarnings("unchecked")
- public static final Class<Character> TYPE = (Class<Character>) new char[0]
- .getClass().getComponentType();
+ public static final Class<Character> TYPE
+ = (Class<Character>) char[].class.getComponentType();
// Note: This can't be set to "char.class", since *that* is
// defined to be "java.lang.Character.TYPE";
@@ -1517,9 +1517,10 @@
/**
* Returns a {@code Character} instance for the {@code char} value passed.
- * For ASCII/Latin-1 characters (and generally all characters with a Unicode
- * value up to 512), this method should be used instead of the constructor,
- * as it maintains a cache of corresponding {@code Character} instances.
+ * <p>
+ * If it is not necessary to get a new {@code Character} instance, it is
+ * recommended to use this method instead of the constructor, since it
+ * maintains a cache of instances which may result in better performance.
*
* @param c
* the char value for which to get a {@code Character} instance.
@@ -1527,26 +1528,17 @@
* @since 1.5
*/
public static Character valueOf(char c) {
- if (c >= CACHE_LEN ) {
- return new Character(c);
- }
- return valueOfCache.CACHE[c];
+ return c < 128 ? SMALL_VALUES[c] : new Character(c);
}
- private static final int CACHE_LEN = 512;
+ /**
+ * A cache of instances used by {@link #valueOf(char)} and auto-boxing
+ */
+ private static final Character[] SMALL_VALUES = new Character[128];
- static class valueOfCache {
- /*
- * Provides a cache for the 'valueOf' method. A size of 512 should cache the
- * first couple pages of Unicode, which includes the ASCII/Latin-1
- * characters, which other parts of this class are optimized for.
- */
- private static final Character[] CACHE = new Character[CACHE_LEN ];
-
- static {
- for(int i=0; i<CACHE.length; i++){
- CACHE[i] = new Character((char)i);
- }
+ static {
+ for(int i = 0; i < 128; i++) {
+ SMALL_VALUES[i] = new Character((char) i);
}
}
/**
@@ -3267,5 +3259,4 @@
public static int toUpperCase(int codePoint) {
return UCharacter.toUpperCase(codePoint);
}
-
}
diff --git a/libcore/luni/src/main/java/java/lang/Double.java b/libcore/luni/src/main/java/java/lang/Double.java
index bc0c380..d6ad58e 100644
--- a/libcore/luni/src/main/java/java/lang/Double.java
+++ b/libcore/luni/src/main/java/java/lang/Double.java
@@ -67,8 +67,8 @@
* @since 1.1
*/
@SuppressWarnings("unchecked")
- public static final Class<Double> TYPE = (Class<Double>) new double[0]
- .getClass().getComponentType();
+ public static final Class<Double> TYPE
+ = (Class<Double>) double[].class.getComponentType();
// Note: This can't be set to "double.class", since *that* is
// defined to be "java.lang.Double.TYPE";
@@ -321,7 +321,7 @@
* @see #parseDouble(String)
*/
public static Double valueOf(String string) throws NumberFormatException {
- return new Double(parseDouble(string));
+ return parseDouble(string);
}
/**
diff --git a/libcore/luni/src/main/java/java/lang/Float.java b/libcore/luni/src/main/java/java/lang/Float.java
index 067149d..92b1731 100644
--- a/libcore/luni/src/main/java/java/lang/Float.java
+++ b/libcore/luni/src/main/java/java/lang/Float.java
@@ -64,8 +64,8 @@
* @since 1.1
*/
@SuppressWarnings("unchecked")
- public static final Class<Float> TYPE = (Class<Float>) new float[0]
- .getClass().getComponentType();
+ public static final Class<Float> TYPE
+ = (Class<Float>) float[].class.getComponentType();
// Note: This can't be set to "float.class", since *that* is
// defined to be "java.lang.Float.TYPE";
@@ -324,7 +324,7 @@
* @see #parseFloat(String)
*/
public static Float valueOf(String string) throws NumberFormatException {
- return valueOf(parseFloat(string));
+ return parseFloat(string);
}
/**
diff --git a/libcore/luni/src/main/java/java/lang/Integer.java b/libcore/luni/src/main/java/java/lang/Integer.java
index 5dcf217..34b9c16 100644
--- a/libcore/luni/src/main/java/java/lang/Integer.java
+++ b/libcore/luni/src/main/java/java/lang/Integer.java
@@ -15,25 +15,30 @@
* limitations under the License.
*/
+// BEGIN android-note
+// Reimiplemented toString, bit-twiddling, etc. Faster and cleaner.
+// BEGIN android-note
+
package java.lang;
/**
* The wrapper for the primitive type {@code int}.
* <p>
- * As with the specification, this implementation relies on code laid out in <a
- * href="http://www.hackersdelight.org/">Henry S. Warren, Jr.'s Hacker's
- * Delight, (Addison Wesley, 2002)</a> as well as <a
- * href="http://aggregate.org/MAGIC/">The Aggregate's Magic Algorithms</a>.
+ * Implementation note: The "bit twiddling" methods in this class use techniques
+ * described in <a href="http://www.hackersdelight.org/">Henry S. Warren,
+ * Jr.'s Hacker's Delight, (Addison Wesley, 2002)</a> and <a href=
+ * "http://graphics.stanford.edu/~seander/bithacks.html">Sean Anderson's
+ * Bit Twiddling Hacks.</a>
*
- * @see java.lang.Number
- * @since 1.1
+ * @see java.lang.Long
+ * @since 1.0
*/
public final class Integer extends Number implements Comparable<Integer> {
private static final long serialVersionUID = 1360826667806852920L;
/**
- * The value which the receiver represents.
+ * The int value represented by this Integer
*/
private final int value;
@@ -55,22 +60,75 @@
*/
public static final int SIZE = 32;
- /*
- * Progressively smaller decimal order of magnitude that can be represented
- * by an instance of Integer. Used to help compute the String
- * representation.
+ /**
+ * These tables are used to special-case toString computation for
+ * small values. This serves three purposes: it reduces memory usage;
+ * it increases performance for small values; and it decreases the
+ * number of comparisons required to do the length computation.
+ * Elements of this table are lazily initialized on first use.
+ * No locking is necessary, i.e., we use the non-volatile, racy
+ * single-check idiom.
*/
- private static final int[] decimalScale = new int[] { 1000000000, 100000000,
- 10000000, 1000000, 100000, 10000, 1000, 100, 10, 1 };
+ private static final String[] SMALL_NONNEGATIVE_VALUES = new String[100];
+ private static final String[] SMALL_NEGATIVE_VALUES = new String[100];
+
+ /** TENS[i] contains the tens digit of the number i, 0 <= i <= 99. */
+ static final char[] TENS = {
+ '0', '0', '0', '0', '0', '0', '0', '0', '0', '0',
+ '1', '1', '1', '1', '1', '1', '1', '1', '1', '1',
+ '2', '2', '2', '2', '2', '2', '2', '2', '2', '2',
+ '3', '3', '3', '3', '3', '3', '3', '3', '3', '3',
+ '4', '4', '4', '4', '4', '4', '4', '4', '4', '4',
+ '5', '5', '5', '5', '5', '5', '5', '5', '5', '5',
+ '6', '6', '6', '6', '6', '6', '6', '6', '6', '6',
+ '7', '7', '7', '7', '7', '7', '7', '7', '7', '7',
+ '8', '8', '8', '8', '8', '8', '8', '8', '8', '8',
+ '9', '9', '9', '9', '9', '9', '9', '9', '9', '9'
+ };
+
+ /** Ones [i] contains the tens digit of the number i, 0 <= i <= 99. */
+ static final char[] ONES = {
+ '0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
+ '0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
+ '0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
+ '0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
+ '0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
+ '0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
+ '0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
+ '0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
+ '0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
+ '0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
+ };
+
+ /**
+ * The digits for all supported radices.
+ */
+ static final char[] DIGITS = {
+ '0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
+ 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j',
+ 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't',
+ 'u', 'v', 'w', 'x', 'y', 'z'
+ };
+
+ /**
+ * Table for Seal's algorithm for Number of Trailing Zeros. Hacker's Delight
+ * online, Figure 5-18 (http://www.hackersdelight.org/revisions.pdf)
+ * The entries whose value is -1 are never referenced.
+ */
+ private static final byte NTZ_TABLE[] = {
+ 32, 0, 1, 12, 2, 6, -1, 13, 3, -1, 7, -1, -1, -1, -1, 14,
+ 10, 4, -1, -1, 8, -1, -1, 25, -1, -1, -1, -1, -1, 21, 27, 15,
+ 31, 11, 5, -1, -1, -1, -1, -1, 9, -1, -1, 24, -1, -1, 20, 26,
+ 30, -1, -1, -1, -1, 23, -1, 19, 29, -1, 22, 18, 28, 17, 16, -1
+ };
/**
* The {@link Class} object that represents the primitive type {@code int}.
*/
@SuppressWarnings("unchecked")
- public static final Class<Integer> TYPE = (Class<Integer>) new int[0]
- .getClass().getComponentType();
-
- // Note: This can't be set to "int.class", since *that* is
+ public static final Class<Integer> TYPE
+ = (Class<Integer>) int[].class.getComponentType();
+ // Note: Integer.TYPE can't be set to "int.class", since *that* is
// defined to be "java.lang.Integer.TYPE";
/**
@@ -116,7 +174,9 @@
* @since 1.2
*/
public int compareTo(Integer object) {
- return value > object.value ? 1 : (value < object.value ? -1 : 0);
+ int thisValue = value;
+ int thatValue = object.value;
+ return thisValue < thatValue ? -1 : (thisValue == thatValue ? 0 : 1);
}
/**
@@ -195,8 +255,7 @@
*/
@Override
public boolean equals(Object o) {
- return (o instanceof Integer)
- && (value == ((Integer) o).value);
+ return o instanceof Integer && ((Integer) o).value == value;
}
@Override
@@ -412,22 +471,15 @@
* @return the binary string representation of {@code i}.
*/
public static String toBinaryString(int i) {
- int count = 1, j = i;
+ int bufLen = 32; // Max number of binary digits in an int
+ char[] buf = new char[bufLen];
+ int cursor = bufLen;
- if (i < 0) {
- count = 32;
- } else {
- while ((j >>>= 1) != 0) {
- count++;
- }
- }
-
- char[] buffer = new char[count];
do {
- buffer[--count] = (char) ((i & 1) + '0');
- i >>>= 1;
- } while (count > 0);
- return new String(0, buffer.length, buffer);
+ buf[--cursor] = (char) ((i & 1) + '0');
+ } while ((i >>>= 1) != 0);
+
+ return new String(cursor, bufLen - cursor, buf);
}
/**
@@ -440,28 +492,15 @@
* @return the hexadecimal string representation of {@code i}.
*/
public static String toHexString(int i) {
- int count = 1, j = i;
+ int bufLen = 8; // Max number of hex digits in an int
+ char[] buf = new char[bufLen];
+ int cursor = bufLen;
- if (i < 0) {
- count = 8;
- } else {
- while ((j >>>= 4) != 0) {
- count++;
- }
- }
-
- char[] buffer = new char[count];
do {
- int t = i & 15;
- if (t > 9) {
- t = t - 10 + 'a';
- } else {
- t += '0';
- }
- buffer[--count] = (char) t;
- i >>>= 4;
- } while (count > 0);
- return new String(0, buffer.length, buffer);
+ buf[--cursor] = DIGITS[i & 0xF];
+ } while ((i >>>= 4) != 0);
+
+ return new String(cursor, bufLen - cursor, buf);
}
/**
@@ -473,22 +512,15 @@
* @return the octal string representation of {@code i}.
*/
public static String toOctalString(int i) {
- int count = 1, j = i;
+ int bufLen = 11; // Max number of octal digits in an int
+ char[] buf = new char[bufLen];
+ int cursor = bufLen;
- if (i < 0) {
- count = 11;
- } else {
- while ((j >>>= 3) != 0) {
- count++;
- }
- }
-
- char[] buffer = new char[count];
do {
- buffer[--count] = (char) ((i & 7) + '0');
- i >>>= 3;
- } while (count > 0);
- return new String(0, buffer.length, buffer);
+ buf[--cursor] = (char) ((i & 7) + '0');
+ } while ((i >>>= 3) != 0);
+
+ return new String(cursor, bufLen - cursor, buf);
}
@Override
@@ -501,101 +533,80 @@
* The returned string is a concatenation of a minus sign if the number is
* negative and characters from '0' to '9'.
*
- * @param value
+ * @param i
* the integer to convert.
- * @return the decimal string representation of {@code value}.
+ * @return the decimal string representation of {@code i}.
*/
- public static String toString(int value) {
- // BEGIN android-note
- // cache the strings in the range 0..99 to save allocations?
- // END android-note
- if (value == 0) {
- return "0"; //$NON-NLS-1$
- }
-
- // Faster algorithm for smaller Integers
- if (value < 1000 && value > -1000) {
- char[] buffer = new char[4];
- int positive_value = value < 0 ? -value : value;
- int first_digit = 0;
- if (value < 0) {
- buffer[0] = '-';
- first_digit++;
- }
- int last_digit = first_digit;
- int quot = positive_value;
- do {
- int res = quot / 10;
- int digit_value = quot - ((res << 3) + (res << 1));
- digit_value += '0';
- buffer[last_digit++] = (char) digit_value;
- quot = res;
- } while (quot != 0);
-
- int count = last_digit--;
- do {
- char tmp = buffer[last_digit];
- buffer[last_digit--] = buffer[first_digit];
- buffer[first_digit++] = tmp;
- } while (first_digit < last_digit);
- return new String(0, count, buffer);
- }
- if (value == MIN_VALUE) {
- return "-2147483648";//$NON-NLS-1$
- }
-
- char[] buffer = new char[11];
- int positive_value = value < 0 ? -value : value;
- byte first_digit = 0;
- if (value < 0) {
- buffer[0] = '-';
- first_digit++;
- }
- byte last_digit = first_digit;
- byte count;
- int number;
- boolean start = false;
- for (int i = 0; i < 9; i++) {
- count = 0;
- if (positive_value < (number = decimalScale[i])) {
- if (start) {
- buffer[last_digit++] = '0';
+ public static String toString(int i) {
+ boolean negative = false;
+ if (i < 0) {
+ negative = true;
+ i = -i;
+ if (i < 100) {
+ if (i < 0) // If -n is still negative, n is Integer.MIN_VALUE
+ return "-2147483648";
+ String result = SMALL_NEGATIVE_VALUES[i];
+ if (result == null) {
+ SMALL_NEGATIVE_VALUES[i] = result =
+ i < 10 ? stringOf('-', ONES[i])
+ : stringOf('-', TENS[i], ONES[i]);
}
- continue;
+ return result;
}
-
- if (i > 0) {
- number = (decimalScale[i] << 3);
- if (positive_value >= number) {
- positive_value -= number;
- count += 8;
+ } else {
+ if (i < 100) {
+ String result = SMALL_NONNEGATIVE_VALUES[i];
+ if (result == null) {
+ SMALL_NONNEGATIVE_VALUES[i] = result =
+ i < 10 ? stringOf(ONES[i]) : stringOf(TENS[i], ONES[i]);
}
- number = (decimalScale[i] << 2);
- if (positive_value >= number) {
- positive_value -= number;
- count += 4;
- }
- }
- number = (decimalScale[i] << 1);
- if (positive_value >= number) {
- positive_value -= number;
- count += 2;
- }
- if (positive_value >= decimalScale[i]) {
- positive_value -= decimalScale[i];
- count++;
- }
- if (count > 0 && !start) {
- start = true;
- }
- if (start) {
- buffer[last_digit++] = (char) (count + '0');
+ return result;
}
}
- buffer[last_digit++] = (char) (positive_value + '0');
- count = last_digit--;
- return new String(0, count, buffer);
+ int bufLen = 11; // Max number of chars in result
+ char[] buf = new char[bufLen];
+ int cursor = bufLen;
+
+ // Calculate digits two-at-a-time till remaining digits fit in 16 bits
+ while (i >= (1 << 16)) {
+ // Compute q = n/100 and r = n % 100 as per "Hacker's Delight" 10-8
+ int q = (int) ((0x51EB851FL * i) >>> 37);
+ // BEGIN android-changed
+ int r = i - ((q << 6) + (q << 5) + (q << 2)); // int r = n - 100*q;
+ // END android-changed
+
+ buf[--cursor] = ONES[r];
+ buf[--cursor] = TENS[r];
+ i = q;
+ }
+
+ // Calculate remaining digits one-at-a-time for performance
+ while (i != 0) {
+ // Compute q = n/10 and r = n % 10 as per "Hacker's Delight" 10-8
+ int q = (0xCCCD * i) >>> 19;
+ // BEGIN android-changed
+ int r = i - ((q << 3) + (q << 1)); // int r = n - 10 * q;
+ // END android-changed
+
+ buf[--cursor] = (char) (r + '0');
+ i = q;
+ }
+
+ if (negative)
+ buf[--cursor] = '-';
+
+ return new String(cursor, bufLen - cursor, buf);
+ }
+
+ /**
+ * Returns a string composed of the specified characters. Note that the
+ * autoboxing does *not* result in an extra copy of the char array: we are
+ * using a package-private string constructor that uses incorporates the
+ * "autoboxing array" into the new string.
+ */
+ private static String stringOf(char... args) {
+ return new String(0, args.length, args);
}
/**
@@ -613,41 +624,41 @@
* @return the string representation of {@code i}.
*/
public static String toString(int i, int radix) {
- // BEGIN android-note
- // if radix==10, call thru to faster Integer.toString(int) ?
- // only worthwhile if 10 is a popular parameter
- // END android-note
if (radix < Character.MIN_RADIX || radix > Character.MAX_RADIX) {
radix = 10;
}
- if (i == 0) {
- return "0"; //$NON-NLS-1$
+ if (radix == 10) {
+ return toString(i);
}
- int count = 2, j = i;
- boolean negative = i < 0;
- if (!negative) {
- count = 1;
- j = -i;
- }
- while ((i /= radix) != 0) {
- count++;
+ /*
+ * If i is positive, negate it. This is the opposite of what one might
+ * expect. It is necessary because the range of the negative values is
+ * strictly larger than that of the positive values: there is no
+ * positive value corresponding to Integer.MIN_VALUE.
+ */
+ boolean negative = false;
+ if (i < 0) {
+ negative = true;
+ } else {
+ i = -i;
}
- char[] buffer = new char[count];
+ int bufLen = radix < 8 ? 33 : 12; // Max chars in result (conservative)
+ char[] buf = new char[bufLen];
+ int cursor = bufLen;
+
do {
- int ch = 0 - (j % radix);
- if (ch > 9) {
- ch = ch - 10 + 'a';
- } else {
- ch += '0';
- }
- buffer[--count] = (char) ch;
- } while ((j /= radix) != 0);
+ int q = i / radix;
+ buf[--cursor] = DIGITS[radix * q - i];
+ i = q;
+ } while (i != 0);
+
if (negative) {
- buffer[0] = '-';
+ buf[--cursor] = '-';
}
- return new String(0, buffer.length, buffer);
+
+ return new String(cursor, bufLen - cursor, buf);
}
/**
@@ -700,12 +711,13 @@
* @since 1.5
*/
public static int highestOneBit(int i) {
+ // Hacker's Delight, Figure 3-1
i |= (i >> 1);
i |= (i >> 2);
i |= (i >> 4);
i |= (i >> 8);
i |= (i >> 16);
- return (i & ~(i >>> 1));
+ return i - (i >>> 1);
}
/**
@@ -720,7 +732,7 @@
* @since 1.5
*/
public static int lowestOneBit(int i) {
- return (i & (-i));
+ return i & -i;
}
/**
@@ -733,12 +745,28 @@
* @since 1.5
*/
public static int numberOfLeadingZeros(int i) {
- i |= i >> 1;
- i |= i >> 2;
- i |= i >> 4;
- i |= i >> 8;
- i |= i >> 16;
- return bitCount(~i);
+ // Hacker's Delight, Figure 5-6
+ if (i <= 0) {
+ return (~i >> 26) & 32;
+ }
+ int n = 1;
+ if (i >> 16 == 0) {
+ n += 16;
+ i <<= 16;
+ }
+ if (i >> 24 == 0) {
+ n += 8;
+ i <<= 8;
+ }
+ if (i >> 28 == 0) {
+ n += 4;
+ i <<= 4;
+ }
+ if (i >> 30 == 0) {
+ n += 2;
+ i <<= 2;
+ }
+ return n - (i >>> 31);
}
/**
@@ -751,7 +779,14 @@
* @since 1.5
*/
public static int numberOfTrailingZeros(int i) {
- return bitCount((i & -i) - 1);
+ // Seal's algorithm - Hacker's Delight 5-18
+ // BEGIN android-changed - Harmony version should be one-liner in comment below
+ i &= -i;
+ i = (i << 4) + i; // x *= 17
+ i = (i << 6) + i; // x *= 65
+ i = (i << 16) - i; // x *= 65535
+ return NTZ_TABLE[i >>> 26]; // NTZ_TABLE[((i & -i) * 0x0450FBAF) >>> 26]
+ // END android-changed
}
/**
@@ -764,12 +799,13 @@
* @since 1.5
*/
public static int bitCount(int i) {
- i -= ((i >> 1) & 0x55555555);
+ // Hacker's Delight, Figure 5-2
+ i -= (i >> 1) & 0x55555555;
i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
- i = (((i >> 4) + i) & 0x0F0F0F0F);
- i += (i >> 8);
- i += (i >> 16);
- return (i & 0x0000003F);
+ i = ((i >> 4) + i) & 0x0F0F0F0F;
+ i += i >> 8;
+ i += i >> 16;
+ return i & 0x0000003F;
}
/**
@@ -784,15 +820,8 @@
* @since 1.5
*/
public static int rotateLeft(int i, int distance) {
- if (distance == 0) {
- return i;
- }
- /*
- * According to JLS3, 15.19, the right operand of a shift is always
- * implicitly masked with 0x1F, which the negation of 'distance' is
- * taking advantage of.
- */
- return ((i << distance) | (i >>> (-distance)));
+ // Shift distances are mod 32 (JLS3 15.19), so we needn't mask -distance
+ return (i << distance) | (i >>> -distance);
}
/**
@@ -807,15 +836,8 @@
* @since 1.5
*/
public static int rotateRight(int i, int distance) {
- if (distance == 0) {
- return i;
- }
- /*
- * According to JLS3, 15.19, the right operand of a shift is always
- * implicitly masked with 0x1F, which the negation of 'distance' is
- * taking advantage of.
- */
- return ((i >>> distance) | (i << (-distance)));
+ // Shift distances are mod 32 (JLS3 15.19), so we needn't mask -distance
+ return (i >>> distance) | (i << -distance);
}
/**
@@ -827,11 +849,10 @@
* @since 1.5
*/
public static int reverseBytes(int i) {
- int b3 = i >>> 24;
- int b2 = (i >>> 8) & 0xFF00;
- int b1 = (i & 0xFF00) << 8;
- int b0 = i << 24;
- return (b0 | b1 | b2 | b3);
+ // Hacker's Delight 7-1, with minor tweak from Veldmeijer
+ // http://graphics.stanford.edu/~seander/bithacks.html
+ i = ((i >>> 8) & 0x00FF00FF) | ((i & 0x00FF00FF) << 8);
+ return ( i >>> 16 ) | ( i << 16);
}
/**
@@ -843,11 +864,13 @@
* @since 1.5
*/
public static int reverse(int i) {
- // From Hacker's Delight, 7-1, Figure 7-1
- i = (i & 0x55555555) << 1 | (i >> 1) & 0x55555555;
- i = (i & 0x33333333) << 2 | (i >> 2) & 0x33333333;
- i = (i & 0x0F0F0F0F) << 4 | (i >> 4) & 0x0F0F0F0F;
- return reverseBytes(i);
+ // Hacker's Delight 7-1, with minor tweak from Veldmeijer
+ // http://graphics.stanford.edu/~seander/bithacks.html
+ i = ((i >>> 1) & 0x55555555) | ((i & 0x55555555) << 1);
+ i = ((i >>> 2) & 0x33333333) | ((i & 0x33333333) << 2);
+ i = ((i >>> 4) & 0x0F0F0F0F) | ((i & 0x0F0F0F0F) << 4);
+ i = ((i >>> 8) & 0x00FF00FF) | ((i & 0x00FF00FF) << 8);
+ return ((i >>> 16) ) | ((i ) << 16);
}
/**
@@ -861,7 +884,7 @@
* @since 1.5
*/
public static int signum(int i) {
- return (i == 0 ? 0 : (i < 0 ? -1 : 1));
+ return (i >> 31) | (-i >>> 31); // Hacker's delight 2-7
}
/**
@@ -877,24 +900,17 @@
* @since 1.5
*/
public static Integer valueOf(int i) {
- if (i < -128 || i > 127) {
- return new Integer(i);
- }
- return valueOfCache.CACHE [i+128];
-
+ return i >= 128 || i < -128 ? new Integer(i) : SMALL_VALUES[i + 128];
}
- static class valueOfCache {
- /**
- * <p>
- * A cache of instances used by {@link Integer#valueOf(int)} and auto-boxing.
- */
- static final Integer[] CACHE = new Integer[256];
+ /**
+ * A cache of instances used by {@link Integer#valueOf(int)} and auto-boxing
+ */
+ private static final Integer[] SMALL_VALUES = new Integer[256];
- static {
- for(int i=-128; i<=127; i++) {
- CACHE[i+128] = new Integer(i);
- }
+ static {
+ for(int i = -128; i < 128; i++) {
+ SMALL_VALUES[i + 128] = new Integer(i);
}
}
}
diff --git a/libcore/luni/src/main/java/java/lang/Long.java b/libcore/luni/src/main/java/java/lang/Long.java
index 2746424..8a2a8da 100644
--- a/libcore/luni/src/main/java/java/lang/Long.java
+++ b/libcore/luni/src/main/java/java/lang/Long.java
@@ -15,17 +15,22 @@
* limitations under the License.
*/
+// BEGIN android-note
+// Reimiplemented toString, bit-twiddling, etc. Faster and cleaner.
+// BEGIN android-note
+
package java.lang;
/**
* The wrapper for the primitive type {@code long}.
* <p>
- * As with the specification, this implementation relies on code laid out in <a
- * href="http://www.hackersdelight.org/">Henry S. Warren, Jr.'s Hacker's
- * Delight, (Addison Wesley, 2002)</a> as well as <a
- * href="http://aggregate.org/MAGIC/">The Aggregate's Magic Algorithms</a>.
+ * Implementation note: The "bit twiddling" methods in this class use techniques
+ * described in <a href="http://www.hackersdelight.org/">Henry S. Warren,
+ * Jr.'s Hacker's Delight, (Addison Wesley, 2002)</a> and <a href=
+ * "http://graphics.stanford.edu/~seander/bithacks.html">Sean Anderson's
+ * Bit Twiddling Hacks.</a>
*
- * @see java.lang.Number
+ * @see java.lang.Integer
* @since 1.0
*/
public final class Long extends Number implements Comparable<Long> {
@@ -51,10 +56,9 @@
* The {@link Class} object that represents the primitive type {@code long}.
*/
@SuppressWarnings("unchecked")
- public static final Class<Long> TYPE = (Class<Long>) new long[0].getClass()
- .getComponentType();
-
- // Note: This can't be set to "long.class", since *that* is
+ public static final Class<Long> TYPE
+ = (Class<Long>) long[].class.getComponentType();
+ // Note: Long.TYPE can't be set to "long.class", since *that* is
// defined to be "java.lang.Long.TYPE";
/**
@@ -65,10 +69,18 @@
*/
public static final int SIZE = 64;
+ /**
+ * Table for MOD / DIV 10 computation described in Section 10-21
+ * of Hank Warren's "Hacker's Delight" online addendum.
+ * http://www.hackersdelight.org/divcMore.pdf
+ */
+ private static final char[] MOD_10_TABLE = {
+ 0, 1, 2, 2, 3, 3, 4, 5, 5, 6, 7, 7, 8, 8, 9, 0
+ };
/**
* Constructs a new {@code Long} with the specified primitive long value.
- *
+ *
* @param value
* the primitive long value to store in the new instance.
*/
@@ -78,7 +90,7 @@
/**
* Constructs a new {@code Long} from the specified string.
- *
+ *
* @param string
* the string representation of a long value.
* @throws NumberFormatException
@@ -97,7 +109,7 @@
/**
* Compares this object to the specified long object to determine their
* relative order.
- *
+ *
* @param object
* the long object to compare this object to.
* @return a negative value if the value of this long is less than the value
@@ -108,7 +120,9 @@
* @since 1.2
*/
public int compareTo(Long object) {
- return value > object.value ? 1 : (value < object.value ? -1 : 0);
+ long thisValue = this.value;
+ long thatValue = object.value;
+ return thisValue < thatValue ? -1 : (thisValue == thatValue ? 0 : 1);
}
/**
@@ -116,7 +130,7 @@
* string can be decoded into a long value. The string may be an optional
* minus sign "-" followed by a hexadecimal ("0x..." or "#..."), octal
* ("0..."), or decimal ("...") representation of a long.
- *
+ *
* @param string
* a string representation of a long value.
* @return a {@code Long} containing the value represented by {@code string}.
@@ -172,7 +186,7 @@
* Compares this instance with the specified object and indicates if they
* are equal. In order to be equal, {@code o} must be an instance of
* {@code Long} and have the same long value as this object.
- *
+ *
* @param o
* the object to compare this long with.
* @return {@code true} if the specified object is equal to this
@@ -180,8 +194,7 @@
*/
@Override
public boolean equals(Object o) {
- return (o instanceof Long)
- && (value == ((Long) o).value);
+ return o instanceof Long && ((Long) o).value == value;
}
@Override
@@ -194,7 +207,7 @@
* {@code string}. Returns {@code null} if {@code string} is {@code null}
* or empty, if the property can not be found or if its value can not be
* parsed as a long.
- *
+ *
* @param string
* the name of the requested system property.
* @return the requested property's value as a {@code Long} or {@code null}.
@@ -219,7 +232,7 @@
* {@code string}. Returns the specified default value if {@code string} is
* {@code null} or empty, if the property can not be found or if its value
* can not be parsed as a long.
- *
+ *
* @param string
* the name of the requested system property.
* @param defaultValue
@@ -248,7 +261,7 @@
* {@code string}. Returns the specified default value if {@code string} is
* {@code null} or empty, if the property can not be found or if its value
* can not be parsed as a long.
- *
+ *
* @param string
* the name of the requested system property.
* @param defaultValue
@@ -284,7 +297,7 @@
/**
* Gets the primitive value of this long.
- *
+ *
* @return this object's primitive value.
*/
@Override
@@ -295,7 +308,7 @@
/**
* Parses the specified string as a signed decimal long value. The ASCII
* character \u002d ('-') is recognized as the minus sign.
- *
+ *
* @param string
* the string representation of a long value.
* @return the primitive long value represented by {@code string}.
@@ -310,7 +323,7 @@
/**
* Parses the specified string as a signed long value using the specified
* radix. The ASCII character \u002d ('-') is recognized as the minus sign.
- *
+ *
* @param string
* the string representation of a long value.
* @param radix
@@ -376,92 +389,76 @@
/**
* Converts the specified long value into its binary string representation.
* The returned string is a concatenation of '0' and '1' characters.
- *
- * @param l
+ *
+ * @param v
* the long value to convert.
* @return the binary string representation of {@code l}.
*/
- public static String toBinaryString(long l) {
- int count = 1;
- long j = l;
-
- if (l < 0) {
- count = 64;
- } else {
- while ((j >>= 1) != 0) {
- count++;
- }
+ public static String toBinaryString(long v) {
+ int i = (int) v;
+ if (i == v) {
+ return Integer.toBinaryString(i);
}
- char[] buffer = new char[count];
+ int bufLen = 64; // Max number of binary digits in a long
+ char[] buf = new char[bufLen];
+ int cursor = bufLen;
+
do {
- buffer[--count] = (char) ((l & 1) + '0');
- l >>= 1;
- } while (count > 0);
- return new String(0, buffer.length, buffer);
- }
+ buf[--cursor] = (char) ((v & 1) + '0');
+ } while ((v >>>= 1) != 0);
+
+ return new String(cursor, bufLen - cursor, buf);
+ }
/**
* Converts the specified long value into its hexadecimal string
* representation. The returned string is a concatenation of characters from
* '0' to '9' and 'a' to 'f'.
- *
- * @param l
+ *
+ * @param v
* the long value to convert.
* @return the hexadecimal string representation of {@code l}.
*/
- public static String toHexString(long l) {
- int count = 1;
- long j = l;
-
- if (l < 0) {
- count = 16;
- } else {
- while ((j >>= 4) != 0) {
- count++;
- }
+ public static String toHexString(long v) {
+ int i = (int) v;
+ if (i == v) {
+ return Integer.toHexString(i);
}
- char[] buffer = new char[count];
+ int bufLen = 16; // Max number of hex digits in a long
+ char[] buf = new char[bufLen];
+ int cursor = bufLen;
+
do {
- int t = (int) (l & 15);
- if (t > 9) {
- t = t - 10 + 'a';
- } else {
- t += '0';
- }
- buffer[--count] = (char) t;
- l >>= 4;
- } while (count > 0);
- return new String(0, buffer.length, buffer);
+ buf[--cursor] = Integer.DIGITS[((int) v) & 0xF];
+ } while ((v >>>= 4) != 0);
+
+ return new String(cursor, bufLen - cursor, buf);
}
/**
* Converts the specified long value into its octal string representation.
* The returned string is a concatenation of characters from '0' to '7'.
- *
- * @param l
+ *
+ * @param v
* the long value to convert.
* @return the octal string representation of {@code l}.
*/
- public static String toOctalString(long l) {
- int count = 1;
- long j = l;
-
- if (l < 0) {
- count = 22;
- } else {
- while ((j >>>= 3) != 0) {
- count++;
- }
+ public static String toOctalString(long v) {
+ int i = (int) v;
+ if (i == v) {
+ return Integer.toOctalString(i);
}
+ int bufLen = 22; // Max number of octal digits in a long
+ char[] buf = new char[bufLen];
+ int cursor = bufLen;
- char[] buffer = new char[count];
do {
- buffer[--count] = (char) ((l & 7) + '0');
- l >>>= 3;
- } while (count > 0);
- return new String(0, buffer.length, buffer);
+ buf[--cursor] = (char) (((int)v & 7) + '0');
+ } while ((v >>>= 3) != 0);
+
+ return new String(cursor, bufLen - cursor, buf);
}
@Override
@@ -473,13 +470,116 @@
* Converts the specified long value into its decimal string representation.
* The returned string is a concatenation of a minus sign if the number is
* negative and characters from '0' to '9'.
- *
- * @param l
+ *
+ * @param n
* the long to convert.
* @return the decimal string representation of {@code l}.
*/
- public static String toString(long l) {
- return toString(l, 10);
+ public static String toString(long n) {
+ int i = (int) n;
+ if (i == n)
+ return Integer.toString(i);
+
+ boolean negative = (n < 0);
+ if (negative) {
+ n = -n;
+ if (n < 0) // If -n is still negative, n is Long.MIN_VALUE
+ return "-9223372036854775808";
+ }
+
+ int bufLen = 20; // Maximum number of chars in result
+ char[] buf = new char[bufLen];
+
+ int low = (int) (n % 1000000000); // Extract low-order 9 digits
+ int cursor = intIntoCharArray(buf, bufLen, low);
+
+ // Zero-pad Low order part to 9 digits
+ while (cursor != (bufLen - 9))
+ buf[--cursor] = '0';
+
+ /*
+ * The remaining digits are (n - low) / 1,000,000,000. This
+ * "exact division" is done as per the online addendum to Hank Warren's
+ * "Hacker's Delight" 10-20, http://www.hackersdelight.org/divcMore.pdf
+ */
+ n = ((n - low) >>> 9) * 0x8E47CE423A2E9C6DL;
+
+ /*
+ * If the remaining digits fit in an int, emit them using a
+ * single call to intIntoCharArray. Otherwise, strip off the
+ * low-order digit, put it in buf, and then call intIntoCharArray
+ * on the remaining digits (which now fit in an int).
+ */
+ if ((n & (-1L << 32)) == 0) {
+ cursor = intIntoCharArray(buf, cursor, (int) n);
+ } else {
+ /*
+ * Set midDigit to n % 10
+ */
+ int lo32 = (int) n;
+ int hi32 = (int) (n >>> 32);
+
+ // midDigit = ((unsigned) low32) % 10, per "Hacker's Delight" 10-21
+ int midDigit = MOD_10_TABLE[
+ (0x19999999 * lo32 + (lo32 >>> 1) + (lo32 >>> 3)) >>> 28];
+
+ // Adjust midDigit for hi32. (assert hi32 == 1 || hi32 == 2)
+ midDigit -= hi32 << 2; // 1L << 32 == -4 MOD 10
+ if (midDigit < 0)
+ midDigit += 10;
+
+ buf[--cursor] = (char) (midDigit + '0');
+
+ // Exact division as per Warren 10-20
+ int rest = ((int) ((n - midDigit) >> 1)) * 0xCCCCCCCD;
+ cursor = intIntoCharArray(buf, cursor, rest);
+ }
+
+ if (negative)
+ buf[--cursor] = '-';
+
+ return new String(cursor, bufLen - cursor, buf);
+ }
+
+ /**
+ * Inserts the unsigned decimal integer represented by n into the specified
+ * character array starting at position cursor. Returns the index after
+ * the last character inserted (i.e., the value to pass in as cursor the
+ * next time this method is called). Note that n is interpreted as a large
+ * positive integer (not a negative integer) if its sign bit is set.
+ */
+ static int intIntoCharArray(char[] buf, int cursor, int n) {
+ // Calculate digits two-at-a-time till remaining digits fit in 16 bits
+ while ((n & 0xffff0000) != 0) {
+ /*
+ * Compute q = n/100 and r = n % 100 as per "Hacker's Delight" 10-8.
+ * This computation is sligthly different from the corresponding
+ * computation in Integer.toString: the shifts before and after
+ * multiply can't be combined, as that would yield the wrong result
+ * if n's sign bit were set.
+ */
+ int q = (int) ((0x51EB851FL * (n >>> 2)) >>> 35);
+ // BEGIN android-changed
+ int r = n - ((q << 6) + (q << 5) + (q << 2)); // int r = n - 100*q;
+ // END android-changed
+
+ buf[--cursor] = Integer.ONES[r];
+ buf[--cursor] = Integer.TENS[r];
+ n = q;
+ }
+
+ // Calculate remaining digits one-at-a-time for performance
+ while (n != 0) {
+ // Compute q = n / 10 and r = n % 10 as per "Hacker's Delight" 10-8
+ int q = (0xCCCD * n) >>> 19;
+ // BEGIN android-changed
+ int r = n - ((q << 3) + (q << 1)); // int r = n - 10 * q;
+ // END android-changed
+
+ buf[--cursor] = (char) (r + '0');
+ n = q;
+ }
+ return cursor;
}
/**
@@ -489,51 +589,59 @@
* 'z', depending on the radix. If {@code radix} is not in the interval
* defined by {@code Character.MIN_RADIX} and {@code Character.MAX_RADIX}
* then 10 is used as the base for the conversion.
- *
- * @param l
+ *
+ * @param v
* the long to convert.
* @param radix
* the base to use for the conversion.
- * @return the string representation of {@code l}.
+ * @return the string representation of {@code v}.
*/
- public static String toString(long l, int radix) {
+ public static String toString(long v, int radix) {
+ int i = (int) v;
+ if (i == v) {
+ return Integer.toString(i, radix);
+ }
+
if (radix < Character.MIN_RADIX || radix > Character.MAX_RADIX) {
radix = 10;
}
- if (l == 0) {
- return "0"; //$NON-NLS-1$
+ if (radix == 10) {
+ return toString(v);
}
- int count = 2;
- long j = l;
- boolean negative = l < 0;
- if (!negative) {
- count = 1;
- j = -l;
- }
- while ((l /= radix) != 0) {
- count++;
+ /*
+ * If v is positive, negate it. This is the opposite of what one might
+ * expect. It is necessary because the range of the negative values is
+ * strictly larger than that of the positive values: there is no
+ * positive value corresponding to Integer.MIN_VALUE.
+ */
+ boolean negative = false;
+ if (v < 0) {
+ negative = true;
+ } else {
+ v = -v;
}
- char[] buffer = new char[count];
+ int bufLen = radix < 8 ? 65 : 23; // Max chars in result (conservative)
+ char[] buf = new char[bufLen];
+ int cursor = bufLen;
+
do {
- int ch = 0 - (int) (j % radix);
- if (ch > 9) {
- ch = ch - 10 + 'a';
- } else {
- ch += '0';
- }
- buffer[--count] = (char) ch;
- } while ((j /= radix) != 0);
+ long q = v / radix;
+ buf[--cursor] = Integer.DIGITS[(int) (radix * q - v)];
+ v = q;
+ } while (v != 0);
+
if (negative) {
- buffer[0] = '-';
+ buf[--cursor] = '-';
}
- return new String(0, buffer.length, buffer);
+
+ return new String(cursor, bufLen - cursor, buf);
}
/**
* Parses the specified string as a signed decimal long value.
- *
+ *
* @param string
* the string representation of a long value.
* @return a {@code Long} instance containing the long value represented by
@@ -550,7 +658,7 @@
/**
* Parses the specified string as a signed long value using the specified
* radix.
- *
+ *
* @param string
* the string representation of a long value.
* @param radix
@@ -574,20 +682,21 @@
* 1 and returns the bit mask value for that bit. This is also referred to
* as the Most Significant 1 Bit. Returns zero if the specified long is
* zero.
- *
- * @param lng
+ *
+ * @param v
* the long to examine.
- * @return the bit mask indicating the highest 1 bit in {@code lng}.
+ * @return the bit mask indicating the highest 1 bit in {@code v}.
* @since 1.5
*/
- public static long highestOneBit(long lng) {
- lng |= (lng >> 1);
- lng |= (lng >> 2);
- lng |= (lng >> 4);
- lng |= (lng >> 8);
- lng |= (lng >> 16);
- lng |= (lng >> 32);
- return (lng & ~(lng >>> 1));
+ public static long highestOneBit(long v) {
+ // Hacker's Delight, Figure 3-1
+ v |= (v >> 1);
+ v |= (v >> 2);
+ v |= (v >> 4);
+ v |= (v >> 8);
+ v |= (v >> 16);
+ v |= (v >> 32);
+ return v - (v >>> 1);
}
/**
@@ -595,166 +704,196 @@
* 1 and returns the bit mask value for that bit. This is also referred to
* as the Least Significant 1 Bit. Returns zero if the specified long is
* zero.
- *
- * @param lng
+ *
+ * @param v
* the long to examine.
- * @return the bit mask indicating the lowest 1 bit in {@code lng}.
+ * @return the bit mask indicating the lowest 1 bit in {@code v}.
* @since 1.5
*/
- public static long lowestOneBit(long lng) {
- return (lng & (-lng));
+ public static long lowestOneBit(long v) {
+ return v & -v;
}
/**
* Determines the number of leading zeros in the specified long value prior
* to the {@link #highestOneBit(long) highest one bit}.
*
- * @param lng
+ * @param v
* the long to examine.
- * @return the number of leading zeros in {@code lng}.
+ * @return the number of leading zeros in {@code v}.
* @since 1.5
*/
- public static int numberOfLeadingZeros(long lng) {
- lng |= lng >> 1;
- lng |= lng >> 2;
- lng |= lng >> 4;
- lng |= lng >> 8;
- lng |= lng >> 16;
- lng |= lng >> 32;
- return bitCount(~lng);
+ public static int numberOfLeadingZeros(long v) {
+ // After Hacker's Delight, Figure 5-6
+ if (v < 0) {
+ return 0;
+ }
+ if (v == 0) {
+ return 64;
+ }
+ // On a 64-bit VM, the two previous tests should probably be replaced by
+ // if (v <= 0) return ((int) (~v >> 57)) & 64;
+
+ int n = 1;
+ int i = (int) (v >>> 32);
+ if (i == 0) {
+ n += 32;
+ i = (int) v;
+ }
+ if (i >> 16 == 0) {
+ n += 16;
+ i <<= 16;
+ }
+ if (i >> 24 == 0) {
+ n += 8;
+ i <<= 8;
+ }
+ if (i >> 28 == 0) {
+ n += 4;
+ i <<= 4;
+ }
+ if (i >> 30 == 0) {
+ n += 2;
+ i <<= 2;
+ }
+ return n - (i >>> 31);
}
/**
* Determines the number of trailing zeros in the specified long value after
* the {@link #lowestOneBit(long) lowest one bit}.
*
- * @param lng
+ * @param v
* the long to examine.
- * @return the number of trailing zeros in {@code lng}.
+ * @return the number of trailing zeros in {@code v}.
* @since 1.5
*/
- public static int numberOfTrailingZeros(long lng) {
- return bitCount((lng & -lng) - 1);
+ public static int numberOfTrailingZeros(long v) {
+ int low = (int) v;
+ return low !=0 ? Integer.numberOfTrailingZeros(low)
+ : 32 + Integer.numberOfTrailingZeros((int) (v >>> 32));
}
/**
* Counts the number of 1 bits in the specified long value; this is also
* referred to as population count.
*
- * @param lng
+ * @param v
* the long to examine.
- * @return the number of 1 bits in {@code lng}.
+ * @return the number of 1 bits in {@code v}.
* @since 1.5
*/
- public static int bitCount(long lng) {
- lng = (lng & 0x5555555555555555L) + ((lng >> 1) & 0x5555555555555555L);
- lng = (lng & 0x3333333333333333L) + ((lng >> 2) & 0x3333333333333333L);
- // adjust for 64-bit integer
- int i = (int) ((lng >>> 32) + lng);
+ public static int bitCount(long v) {
+ // Combines techniques from several sources
+ v -= (v >>> 1) & 0x5555555555555555L;
+ v = (v & 0x3333333333333333L) + ((v >> 2) & 0x3333333333333333L);
+ int i = ((int)(v >>> 32)) + (int) v;
i = (i & 0x0F0F0F0F) + ((i >> 4) & 0x0F0F0F0F);
- i = (i & 0x00FF00FF) + ((i >> 8) & 0x00FF00FF);
- i = (i & 0x0000FFFF) + ((i >> 16) & 0x0000FFFF);
- return i;
+ i += i >>> 8;
+ i += i >>> 16;
+ return i & 0x0000007F;
}
+ /*
+ * On a modern 64-bit processor with a fast hardware multiply, this is
+ * much faster (assuming you're running a 64-bit VM):
+ *
+ * // http://chessprogramming.wikispaces.com/Population+Count
+ * int bitCount (long x) {
+ * x -= (x >>> 1) & 0x5555555555555555L;
+ * x = (x & 0x3333333333333333L) + ((x >>> 2) & 0x3333333333333333L);
+ * x = (x + (x >>> 4)) & 0x0f0f0f0f0f0f0f0fL;
+ * x = (x * 0x0101010101010101L) >>> 56;
+ * return (int) x;
+ * }
+ *
+ * Really modern processors (e.g., Nehalem, K-10) have hardware popcount
+ * instructions.
+ */
+
/**
* Rotates the bits of the specified long value to the left by the specified
* number of bits.
*
- * @param lng
+ * @param v
* the long value to rotate left.
* @param distance
* the number of bits to rotate.
* @return the rotated value.
* @since 1.5
*/
- public static long rotateLeft(long lng, int distance) {
- if (distance == 0) {
- return lng;
- }
- /*
- * According to JLS3, 15.19, the right operand of a shift is always
- * implicitly masked with 0x3F, which the negation of 'distance' is
- * taking advantage of.
- */
- return ((lng << distance) | (lng >>> (-distance)));
+ public static long rotateLeft(long v, int distance) {
+ // Shift distances are mod 64 (JLS3 15.19), so we needn't mask -distance
+ return (v << distance) | (v >>> -distance);
}
/**
- * <p>
* Rotates the bits of the specified long value to the right by the
* specified number of bits.
*
- * @param lng
+ * @param v
* the long value to rotate right.
* @param distance
* the number of bits to rotate.
* @return the rotated value.
* @since 1.5
*/
- public static long rotateRight(long lng, int distance) {
- if (distance == 0) {
- return lng;
- }
- /*
- * According to JLS3, 15.19, the right operand of a shift is always
- * implicitly masked with 0x3F, which the negation of 'distance' is
- * taking advantage of.
- */
- return ((lng >>> distance) | (lng << (-distance)));
+ public static long rotateRight(long v, int distance) {
+ // Shift distances are mod 64 (JLS3 15.19), so we needn't mask -distance
+ return (v >>> distance) | (v << -distance);
}
/**
* Reverses the order of the bytes of the specified long value.
- *
- * @param lng
+ *
+ * @param v
* the long value for which to reverse the byte order.
* @return the reversed value.
* @since 1.5
*/
- public static long reverseBytes(long lng) {
- long b7 = lng >>> 56;
- long b6 = (lng >>> 40) & 0xFF00L;
- long b5 = (lng >>> 24) & 0xFF0000L;
- long b4 = (lng >>> 8) & 0xFF000000L;
- long b3 = (lng & 0xFF000000L) << 8;
- long b2 = (lng & 0xFF0000L) << 24;
- long b1 = (lng & 0xFF00L) << 40;
- long b0 = lng << 56;
- return (b0 | b1 | b2 | b3 | b4 | b5 | b6 | b7);
+ public static long reverseBytes(long v) {
+ // Hacker's Delight 7-1, with minor tweak from Veldmeijer
+ // http://graphics.stanford.edu/~seander/bithacks.html
+ v = ((v >> 8) & 0x00FF00FF00FF00FFL) | ((v & 0x00FF00FF00FF00FFL) << 8);
+ v = ((v >>16) & 0x0000FFFF0000FFFFL) | ((v & 0x0000FFFF0000FFFFL) <<16);
+ return ((v >>32) ) | ((v ) <<32);
}
/**
* Reverses the order of the bits of the specified long value.
- *
- * @param lng
+ *
+ * @param v
* the long value for which to reverse the bit order.
* @return the reversed value.
* @since 1.5
*/
- public static long reverse(long lng) {
- // From Hacker's Delight, 7-1, Figure 7-1
- lng = (lng & 0x5555555555555555L) << 1 | (lng >> 1)
- & 0x5555555555555555L;
- lng = (lng & 0x3333333333333333L) << 2 | (lng >> 2)
- & 0x3333333333333333L;
- lng = (lng & 0x0F0F0F0F0F0F0F0FL) << 4 | (lng >> 4)
- & 0x0F0F0F0F0F0F0F0FL;
- return reverseBytes(lng);
+ public static long reverse(long v) {
+ // Hacker's Delight 7-1, with minor tweak from Veldmeijer
+ // http://graphics.stanford.edu/~seander/bithacks.html
+ v = ((v >> 1) & 0x5555555555555555L) | ((v & 0x5555555555555555L) << 1);
+ v = ((v >> 2) & 0x3333333333333333L) | ((v & 0x3333333333333333L) << 2);
+ v = ((v >> 4) & 0x0F0F0F0F0F0F0F0FL) | ((v & 0x0F0F0F0F0F0F0F0FL) << 4);
+ v = ((v >> 8) & 0x00FF00FF00FF00FFL) | ((v & 0x00FF00FF00FF00FFL) << 8);
+ v = ((v >>16) & 0x0000FFFF0000FFFFL) | ((v & 0x0000FFFF0000FFFFL) <<16);
+ return ((v >>32) ) | ((v ) <<32);
}
/**
* Returns the value of the {@code signum} function for the specified long
* value.
- *
- * @param lng
+ *
+ * @param v
* the long value to check.
- * @return -1 if {@code lng} is negative, 1 if {@code lng} is positive, 0 if
- * {@code lng} is zero.
+ * @return -1 if {@code v} is negative, 1 if {@code v} is positive, 0 if
+ * {@code v} is zero.
* @since 1.5
*/
- public static int signum(long lng) {
- return (lng == 0 ? 0 : (lng < 0 ? -1 : 1));
+ public static int signum(long v) {
+ // BEGIN android-changed
+ return v < 0 ? -1 : (v == 0 ? 0 : 1);
+ // END android-changed
+// The following branch-free version is faster on modern desktops/servers
+// return ((int)(v >> 63)) | (int) (-v >>> 63); // Hacker's delight 2-7
}
/**
@@ -764,29 +903,24 @@
* recommended to use this method instead of the constructor, since it
* maintains a cache of instances which may result in better performance.
*
- * @param lng
+ * @param v
* the long value to store in the instance.
- * @return a {@code Long} instance containing {@code lng}.
+ * @return a {@code Long} instance containing {@code v}.
* @since 1.5
*/
- public static Long valueOf(long lng) {
- if (lng < -128 || lng > 127) {
- return new Long(lng);
- }
- return valueOfCache.CACHE[128+(int)lng];
+ public static Long valueOf(long v) {
+ return v >= 128 || v < -128 ? new Long(v)
+ : SMALL_VALUES[((int) v) + 128];
}
- static class valueOfCache {
- /**
- * <p>
- * A cache of instances used by {@link Long#valueOf(long)} and auto-boxing.
- */
- static final Long[] CACHE = new Long[256];
+ /**
+ * A cache of instances used by {@link Long#valueOf(long)} and auto-boxing.
+ */
+ private static final Long[] SMALL_VALUES = new Long[256];
- static {
- for(int i=-128; i<=127; i++) {
- CACHE[i+128] = new Long(i);
- }
+ static {
+ for(int i = -128; i < 128; i++) {
+ SMALL_VALUES[i + 128] = new Long(i);
}
}
}
diff --git a/libcore/luni/src/main/java/java/lang/Short.java b/libcore/luni/src/main/java/java/lang/Short.java
index 9baf3a8..e2e7d61 100644
--- a/libcore/luni/src/main/java/java/lang/Short.java
+++ b/libcore/luni/src/main/java/java/lang/Short.java
@@ -19,7 +19,7 @@
/**
* The wrapper for the primitive type {@code short}.
- *
+ *
* @see java.lang.Number
* @since 1.1
*/
@@ -55,13 +55,11 @@
* short}.
*/
@SuppressWarnings("unchecked")
- public static final Class<Short> TYPE = (Class<Short>) new short[0]
- .getClass().getComponentType();
+ public static final Class<Short> TYPE
+ = (Class<Short>) short[].class.getComponentType();
+ // Note: Short.TYPE can't be set to "short.class", since *that* is
+ // defined to be "java.lang.Short.TYPE";
- // Note: This can't be set to "short.class", since *that* is
- // defined to be "java.lang.Short.TYPE";
-
-
/**
* Constructs a new {@code Short} from the specified string.
*
@@ -93,7 +91,7 @@
/**
* Compares this object to the specified short object to determine their
* relative order.
- *
+ *
* @param object
* the short object to compare this object to.
* @return a negative value if the value of this short is less than the
@@ -277,19 +275,17 @@
throws NumberFormatException {
return valueOf(parseShort(string, radix));
}
-
+
/**
* Reverses the bytes of the specified short.
- *
+ *
* @param s
* the short value for which to reverse bytes.
* @return the reversed value.
* @since 1.5
*/
public static short reverseBytes(short s) {
- int high = (s >> 8) & 0xFF;
- int low = (s & 0xFF) << 8;
- return (short) (low | high);
+ return (short) ((s << 8) | ((s >>> 8) & 0xFF));
}
/**
@@ -305,22 +301,17 @@
* @since 1.5
*/
public static Short valueOf(short s) {
- if (s < -128 || s > 127) {
- return new Short(s);
- }
- return valueOfCache.CACHE[s+128];
+ return s < -128 || s >= 128 ? new Short(s) : SMALL_VALUES[s + 128];
}
- static class valueOfCache {
- /**
- * A cache of instances used by {@link Short#valueOf(short)} and auto-boxing.
- */
- private static final Short[] CACHE = new Short[256];
+ /**
+ * A cache of instances used by {@link Short#valueOf(short)} and auto-boxing.
+ */
+ private static final Short[] SMALL_VALUES = new Short[256];
- static {
- for(int i=-128; i<=127; i++) {
- CACHE[i+128] = new Short((short)i);
- }
+ static {
+ for(int i = -128; i < 128; i++) {
+ SMALL_VALUES[i + 128] = new Short((short) i);
}
}
}
diff --git a/libcore/luni/src/test/java/org/apache/harmony/luni/tests/java/lang/CharacterImplTest.java b/libcore/luni/src/test/java/org/apache/harmony/luni/tests/java/lang/CharacterImplTest.java
index 93e3abb..9a10cc4 100644
--- a/libcore/luni/src/test/java/org/apache/harmony/luni/tests/java/lang/CharacterImplTest.java
+++ b/libcore/luni/src/test/java/org/apache/harmony/luni/tests/java/lang/CharacterImplTest.java
@@ -4,9 +4,9 @@
* The ASF licenses this file to You under the Apache License, Version 2.0
* (the "License"); you may not use this file except in compliance with
* the License. You may obtain a copy of the License at
- *
+ *
* http://www.apache.org/licenses/LICENSE-2.0
- *
+ *
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
@@ -24,7 +24,7 @@
import junit.framework.TestCase;
-@TestTargetClass(Character.class)
+@TestTargetClass(Character.class)
public class CharacterImplTest extends TestCase {
@TestTargetNew(
@@ -33,10 +33,15 @@
method = "valueOf",
args = {char.class}
)
- @AndroidOnly("valueOf doesn't return the same values on RI.")
public void test_valueOfC() {
// test the cache range
- for (char c = '\u0000'; c < 512; c++) {
+// BEGIN android-changed
+// The JLS requires caching for chars between "\u0000 to \u007f"
+// http://java.sun.com/docs/books/jls/third_edition/html/conversions.html#5.1.7
+// The Harmony code cached 0-512 and tested for this behavior. The test and the
+// code have been modified to match the JLS
+ for (char c = '\u0000'; c < 128; c++) {
+// END android-changed
Character e = new Character(c);
Character a = Character.valueOf(c);
assertEquals(e, a);
