11d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert/* 21d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Copyright (C) 2009 The Guava Authors 31d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 41d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Licensed under the Apache License, Version 2.0 (the "License"); 51d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * you may not use this file except in compliance with the License. 61d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * You may obtain a copy of the License at 71d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 81d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * http://www.apache.org/licenses/LICENSE-2.0 91d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 101d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Unless required by applicable law or agreed to in writing, software 111d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * distributed under the License is distributed on an "AS IS" BASIS, 121d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 131d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * See the License for the specific language governing permissions and 141d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * limitations under the License. 151d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 161d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 171d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertpackage com.google.common.primitives; 181d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 191d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport static com.google.common.base.Preconditions.checkArgument; 201d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport static com.google.common.base.Preconditions.checkNotNull; 211d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 221d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport com.google.common.annotations.VisibleForTesting; 231d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 241d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert// BEGIN android-changed 251d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert//import sun.misc.Unsafe; 261d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert// END android-changed 271d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 281d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport java.lang.reflect.Field; 291d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport java.nio.ByteOrder; 301d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport java.security.AccessController; 311d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport java.security.PrivilegedAction; 321d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport java.util.Comparator; 331d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 341d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert/** 351d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Static utility methods pertaining to {@code byte} primitives that interpret 361d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * values as <i>unsigned</i> (that is, any negative value {@code b} is treated 371d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * as the positive value {@code 256 + b}). The corresponding methods that treat 381d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * the values as signed are found in {@link SignedBytes}, and the methods for 391d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * which signedness is not an issue are in {@link Bytes}. 401d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 411d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @author Kevin Bourrillion 421d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @author Martin Buchholz 431d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @author Hiroshi Yamauchi 441d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @since 1.0 451d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 461d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertpublic final class UnsignedBytes { 471d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert private UnsignedBytes() {} 481d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 491d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 501d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * The largest power of two that can be represented as an unsigned {@code byte}. 511d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 521d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @since 10.0 531d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 541d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public static final byte MAX_POWER_OF_TWO = (byte) (1 << 7); 551d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 561d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 571d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Returns the value of the given byte as an integer, when treated as 581d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * unsigned. That is, returns {@code value + 256} if {@code value} is 591d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * negative; {@code value} itself otherwise. 601d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 611d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @since 6.0 621d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 631d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public static int toInt(byte value) { 641d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return value & 0xFF; 651d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 661d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 671d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 681d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Returns the {@code byte} value that, when treated as unsigned, is equal to 691d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * {@code value}, if possible. 701d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 711d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @param value a value between 0 and 255 inclusive 721d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @return the {@code byte} value that, when treated as unsigned, equals 731d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * {@code value} 741d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @throws IllegalArgumentException if {@code value} is negative or greater 751d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * than 255 761d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 771d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public static byte checkedCast(long value) { 781d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert checkArgument(value >> 8 == 0, "out of range: %s", value); 791d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return (byte) value; 801d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 811d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 821d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 831d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Returns the {@code byte} value that, when treated as unsigned, is nearest 841d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * in value to {@code value}. 851d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 861d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @param value any {@code long} value 871d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @return {@code (byte) 255} if {@code value >= 255}, {@code (byte) 0} if 881d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * {@code value <= 0}, and {@code value} cast to {@code byte} otherwise 891d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 901d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public static byte saturatedCast(long value) { 911d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (value > 255) { 921d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return (byte) 255; // -1 931d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 941d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (value < 0) { 951d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return (byte) 0; 961d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 971d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return (byte) value; 981d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 991d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1001d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 1011d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Compares the two specified {@code byte} values, treating them as unsigned 1021d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * values between 0 and 255 inclusive. For example, {@code (byte) -127} is 1031d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * considered greater than {@code (byte) 127} because it is seen as having 1041d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * the value of positive {@code 129}. 1051d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 1061d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @param a the first {@code byte} to compare 1071d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @param b the second {@code byte} to compare 1081d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @return a negative value if {@code a} is less than {@code b}; a positive 1091d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * value if {@code a} is greater than {@code b}; or zero if they are equal 1101d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 1111d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public static int compare(byte a, byte b) { 1121d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return toInt(a) - toInt(b); 1131d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1141d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1151d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 1161d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Returns the least value present in {@code array}. 1171d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 1181d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @param array a <i>nonempty</i> array of {@code byte} values 1191d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @return the value present in {@code array} that is less than or equal to 1201d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * every other value in the array 1211d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @throws IllegalArgumentException if {@code array} is empty 1221d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 1231d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public static byte min(byte... array) { 1241d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert checkArgument(array.length > 0); 1251d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert int min = toInt(array[0]); 1261d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert for (int i = 1; i < array.length; i++) { 1271d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert int next = toInt(array[i]); 1281d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (next < min) { 1291d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert min = next; 1301d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1311d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1321d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return (byte) min; 1331d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1341d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1351d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 1361d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Returns the greatest value present in {@code array}. 1371d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 1381d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @param array a <i>nonempty</i> array of {@code byte} values 1391d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @return the value present in {@code array} that is greater than or equal 1401d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * to every other value in the array 1411d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @throws IllegalArgumentException if {@code array} is empty 1421d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 1431d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public static byte max(byte... array) { 1441d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert checkArgument(array.length > 0); 1451d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert int max = toInt(array[0]); 1461d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert for (int i = 1; i < array.length; i++) { 1471d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert int next = toInt(array[i]); 1481d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (next > max) { 1491d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert max = next; 1501d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1511d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1521d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return (byte) max; 1531d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1541d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1551d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 1561d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Returns a string containing the supplied {@code byte} values separated by 1571d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * {@code separator}. For example, {@code join(":", (byte) 1, (byte) 2, 1581d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * (byte) 255)} returns the string {@code "1:2:255"}. 1591d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 1601d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @param separator the text that should appear between consecutive values in 1611d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * the resulting string (but not at the start or end) 1621d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @param array an array of {@code byte} values, possibly empty 1631d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 1641d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public static String join(String separator, byte... array) { 1651d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert checkNotNull(separator); 1661d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (array.length == 0) { 1671d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return ""; 1681d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1691d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1701d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // For pre-sizing a builder, just get the right order of magnitude 1711d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert StringBuilder builder = new StringBuilder(array.length * 5); 1721d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert builder.append(toInt(array[0])); 1731d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert for (int i = 1; i < array.length; i++) { 1741d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert builder.append(separator).append(toInt(array[i])); 1751d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1761d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return builder.toString(); 1771d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1781d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1791d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 1801d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Returns a comparator that compares two {@code byte} arrays 1811d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * lexicographically. That is, it compares, using {@link 1821d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * #compare(byte, byte)}), the first pair of values that follow any common 1831d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * prefix, or when one array is a prefix of the other, treats the shorter 1841d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * array as the lesser. For example, {@code [] < [0x01] < [0x01, 0x7F] < 1851d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * [0x01, 0x80] < [0x02]}. Values are treated as unsigned. 1861d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 1871d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <p>The returned comparator is inconsistent with {@link 1881d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Object#equals(Object)} (since arrays support only identity equality), but 1891d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * it is consistent with {@link java.util.Arrays#equals(byte[], byte[])}. 1901d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 1911d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @see <a href="http://en.wikipedia.org/wiki/Lexicographical_order"> 1921d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Lexicographical order article at Wikipedia</a> 1931d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @since 2.0 1941d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 1951d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public static Comparator<byte[]> lexicographicalComparator() { 1961d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return LexicographicalComparatorHolder.BEST_COMPARATOR; 1971d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1981d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1991d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @VisibleForTesting 2001d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert static Comparator<byte[]> lexicographicalComparatorJavaImpl() { 2011d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return LexicographicalComparatorHolder.PureJavaComparator.INSTANCE; 2021d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2031d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 2041d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 2051d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Provides a lexicographical comparator implementation; either a Java 2061d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * implementation or a faster implementation based on {@link Unsafe}. 2071d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 2081d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <p>Uses reflection to gracefully fall back to the Java implementation if 2091d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * {@code Unsafe} isn't available. 2101d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 2111d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @VisibleForTesting 2121d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert static class LexicographicalComparatorHolder { 2131d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert static final String UNSAFE_COMPARATOR_NAME = 2141d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert LexicographicalComparatorHolder.class.getName() + "$UnsafeComparator"; 2151d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 2161d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // BEGIN android-changed 2171d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 2181d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert static final Comparator<byte[]> BEST_COMPARATOR = lexicographicalComparatorJavaImpl(); 2191d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 2201d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // @VisibleForTesting 2211d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // enum UnsafeComparator implements Comparator<byte[]> { 2221d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // INSTANCE; 2231d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 2241d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // static final boolean littleEndian = 2251d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // ByteOrder.nativeOrder().equals(ByteOrder.LITTLE_ENDIAN); 2261d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 2271d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // /* 2281d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // * The following static final fields exist for performance reasons. 2291d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // * 2301d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // * In UnsignedBytesBenchmark, accessing the following objects via static 2311d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // * final fields is the fastest (more than twice as fast as the Java 2321d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // * implementation, vs ~1.5x with non-final static fields, on x86_32) 2331d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // * under the Hotspot server compiler. The reason is obviously that the 2341d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // * non-final fields need to be reloaded inside the loop. 2351d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // * 2361d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // * And, no, defining (final or not) local variables out of the loop still 2371d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // * isn't as good because the null check on the theUnsafe object remains 2381d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // * inside the loop and BYTE_ARRAY_BASE_OFFSET doesn't get 2391d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // * constant-folded. 2401d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // * 2411d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // * The compiler can treat static final fields as compile-time constants 2421d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // * and can constant-fold them while (final or not) local variables are 2431d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // * run time values. 2441d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // */ 2451d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 2461d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // static final Unsafe theUnsafe; 2471d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 2481d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // /** The offset to the first element in a byte array. */ 2491d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // static final int BYTE_ARRAY_BASE_OFFSET; 2501d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 2511d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // static { 2521d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // theUnsafe = (Unsafe) AccessController.doPrivileged( 2531d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // new PrivilegedAction<Object>() { 2541d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // @Override 2551d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // public Object run() { 2561d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // try { 2571d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // Field f = Unsafe.class.getDeclaredField("theUnsafe"); 2581d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // f.setAccessible(true); 2591d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // return f.get(null); 2601d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // } catch (NoSuchFieldException e) { 2611d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // // It doesn't matter what we throw; 2621d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // // it's swallowed in getBestComparator(). 2631d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // throw new Error(); 2641d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // } catch (IllegalAccessException e) { 2651d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // throw new Error(); 2661d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // } 2671d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // } 2681d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // }); 2691d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 2701d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // BYTE_ARRAY_BASE_OFFSET = theUnsafe.arrayBaseOffset(byte[].class); 2711d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 2721d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // // sanity check - this should never fail 2731d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // if (theUnsafe.arrayIndexScale(byte[].class) != 1) { 2741d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // throw new AssertionError(); 2751d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // } 2761d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // } 2771d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 2781d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // @Override public int compare(byte[] left, byte[] right) { 2791d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // int minLength = Math.min(left.length, right.length); 2801d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // int minWords = minLength / Longs.BYTES; 2811d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 2821d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // /* 2831d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // * Compare 8 bytes at a time. Benchmarking shows comparing 8 bytes at a 2841d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // * time is no slower than comparing 4 bytes at a time even on 32-bit. 2851d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // * On the other hand, it is substantially faster on 64-bit. 2861d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // */ 2871d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // for (int i = 0; i < minWords * Longs.BYTES; i += Longs.BYTES) { 2881d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // long lw = theUnsafe.getLong(left, BYTE_ARRAY_BASE_OFFSET + (long) i); 2891d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // long rw = theUnsafe.getLong(right, BYTE_ARRAY_BASE_OFFSET + (long) i); 2901d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // long diff = lw ^ rw; 2911d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 2921d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // if (diff != 0) { 2931d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // if (!littleEndian) { 2941d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // return UnsignedLongs.compare(lw, rw); 2951d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // } 2961d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 2971d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // // Use binary search 2981d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // int n = 0; 2991d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // int y; 3001d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // int x = (int) diff; 3011d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // if (x == 0) { 3021d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // x = (int) (diff >>> 32); 3031d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // n = 32; 3041d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // } 3051d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 3061d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // y = x << 16; 3071d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // if (y == 0) { 3081d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // n += 16; 3091d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // } else { 3101d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // x = y; 3111d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // } 3121d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 3131d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // y = x << 8; 3141d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // if (y == 0) { 3151d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // n += 8; 3161d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // } 3171d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // return (int) (((lw >>> n) & 0xFFL) - ((rw >>> n) & 0xFFL)); 3181d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // } 3191d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // } 3201d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 3211d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // // The epilogue to cover the last (minLength % 8) elements. 3221d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // for (int i = minWords * Longs.BYTES; i < minLength; i++) { 3231d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // int result = UnsignedBytes.compare(left[i], right[i]); 3241d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // if (result != 0) { 3251d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // return result; 3261d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // } 3271d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // } 3281d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // return left.length - right.length; 3291d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // } 3301d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // } 3311d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 3321d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // END android-changed 3331d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 3341d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert enum PureJavaComparator implements Comparator<byte[]> { 3351d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert INSTANCE; 3361d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 3371d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override public int compare(byte[] left, byte[] right) { 3381d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert int minLength = Math.min(left.length, right.length); 3391d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert for (int i = 0; i < minLength; i++) { 3401d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert int result = UnsignedBytes.compare(left[i], right[i]); 3411d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (result != 0) { 3421d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return result; 3431d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 3441d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 3451d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return left.length - right.length; 3461d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 3471d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 3481d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 3491d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // BEGIN android-changed 3501d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 3511d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // /** 3521d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // * Returns the Unsafe-using Comparator, or falls back to the pure-Java 3531d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // * implementation if unable to do so. 3541d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // */ 3551d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // static Comparator<byte[]> getBestComparator() { 3561d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // try { 3571d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // Class<?> theClass = Class.forName(UNSAFE_COMPARATOR_NAME); 3581d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 3591d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // // yes, UnsafeComparator does implement Comparator<byte[]> 3601d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // @SuppressWarnings("unchecked") 3611d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // Comparator<byte[]> comparator = 3621d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // (Comparator<byte[]>) theClass.getEnumConstants()[0]; 3631d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // return comparator; 3641d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // } catch (Throwable t) { // ensure we really catch *everything* 3651d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // return lexicographicalComparatorJavaImpl(); 3661d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // } 3671d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // } 3681d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 3691d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // END android-changed 3701d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 3711d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 3721d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert} 3731d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 374