001/* 002 * Copyright (C) 2009 The Guava Authors 003 * 004 * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except 005 * in compliance with the License. You may obtain a copy of the License at 006 * 007 * http://www.apache.org/licenses/LICENSE-2.0 008 * 009 * Unless required by applicable law or agreed to in writing, software distributed under the License 010 * is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express 011 * or implied. See the License for the specific language governing permissions and limitations under 012 * the License. 013 */ 014 015package com.google.common.primitives; 016 017import static com.google.common.base.Preconditions.checkArgument; 018import static com.google.common.base.Preconditions.checkNotNull; 019import static com.google.common.base.Preconditions.checkPositionIndexes; 020import static java.util.Objects.requireNonNull; 021 022import com.google.common.annotations.Beta; 023import com.google.common.annotations.GwtIncompatible; 024import com.google.common.annotations.VisibleForTesting; 025import com.google.errorprone.annotations.CanIgnoreReturnValue; 026import java.nio.ByteOrder; 027import java.util.Arrays; 028import java.util.Comparator; 029import sun.misc.Unsafe; 030 031/** 032 * Static utility methods pertaining to {@code byte} primitives that interpret values as 033 * <i>unsigned</i> (that is, any negative value {@code b} is treated as the positive value {@code 034 * 256 + b}). The corresponding methods that treat the values as signed are found in {@link 035 * SignedBytes}, and the methods for which signedness is not an issue are in {@link Bytes}. 036 * 037 * <p>See the Guava User Guide article on <a 038 * href="https://github.com/google/guava/wiki/PrimitivesExplained">primitive utilities</a>. 039 * 040 * @author Kevin Bourrillion 041 * @author Martin Buchholz 042 * @author Hiroshi Yamauchi 043 * @author Louis Wasserman 044 * @since 1.0 045 */ 046@GwtIncompatible 047@ElementTypesAreNonnullByDefault 048public final class UnsignedBytes { 049 private UnsignedBytes() {} 050 051 /** 052 * The largest power of two that can be represented as an unsigned {@code byte}. 053 * 054 * @since 10.0 055 */ 056 public static final byte MAX_POWER_OF_TWO = (byte) 0x80; 057 058 /** 059 * The largest value that fits into an unsigned byte. 060 * 061 * @since 13.0 062 */ 063 public static final byte MAX_VALUE = (byte) 0xFF; 064 065 private static final int UNSIGNED_MASK = 0xFF; 066 067 /** 068 * Returns the value of the given byte as an integer, when treated as unsigned. That is, returns 069 * {@code value + 256} if {@code value} is negative; {@code value} itself otherwise. 070 * 071 * <p><b>Java 8 users:</b> use {@link Byte#toUnsignedInt(byte)} instead. 072 * 073 * @since 6.0 074 */ 075 public static int toInt(byte value) { 076 return value & UNSIGNED_MASK; 077 } 078 079 /** 080 * Returns the {@code byte} value that, when treated as unsigned, is equal to {@code value}, if 081 * possible. 082 * 083 * @param value a value between 0 and 255 inclusive 084 * @return the {@code byte} value that, when treated as unsigned, equals {@code value} 085 * @throws IllegalArgumentException if {@code value} is negative or greater than 255 086 */ 087 @CanIgnoreReturnValue 088 public static byte checkedCast(long value) { 089 checkArgument(value >> Byte.SIZE == 0, "out of range: %s", value); 090 return (byte) value; 091 } 092 093 /** 094 * Returns the {@code byte} value that, when treated as unsigned, is nearest in value to {@code 095 * value}. 096 * 097 * @param value any {@code long} value 098 * @return {@code (byte) 255} if {@code value >= 255}, {@code (byte) 0} if {@code value <= 0}, and 099 * {@code value} cast to {@code byte} otherwise 100 */ 101 public static byte saturatedCast(long value) { 102 if (value > toInt(MAX_VALUE)) { 103 return MAX_VALUE; // -1 104 } 105 if (value < 0) { 106 return (byte) 0; 107 } 108 return (byte) value; 109 } 110 111 /** 112 * Compares the two specified {@code byte} values, treating them as unsigned values between 0 and 113 * 255 inclusive. For example, {@code (byte) -127} is considered greater than {@code (byte) 127} 114 * because it is seen as having the value of positive {@code 129}. 115 * 116 * @param a the first {@code byte} to compare 117 * @param b the second {@code byte} to compare 118 * @return a negative value if {@code a} is less than {@code b}; a positive value if {@code a} is 119 * greater than {@code b}; or zero if they are equal 120 */ 121 public static int compare(byte a, byte b) { 122 return toInt(a) - toInt(b); 123 } 124 125 /** 126 * Returns the least value present in {@code array}, treating values as unsigned. 127 * 128 * @param array a <i>nonempty</i> array of {@code byte} values 129 * @return the value present in {@code array} that is less than or equal to every other value in 130 * the array according to {@link #compare} 131 * @throws IllegalArgumentException if {@code array} is empty 132 */ 133 public static byte min(byte... array) { 134 checkArgument(array.length > 0); 135 int min = toInt(array[0]); 136 for (int i = 1; i < array.length; i++) { 137 int next = toInt(array[i]); 138 if (next < min) { 139 min = next; 140 } 141 } 142 return (byte) min; 143 } 144 145 /** 146 * Returns the greatest value present in {@code array}, treating values as unsigned. 147 * 148 * @param array a <i>nonempty</i> array of {@code byte} values 149 * @return the value present in {@code array} that is greater than or equal to every other value 150 * in the array according to {@link #compare} 151 * @throws IllegalArgumentException if {@code array} is empty 152 */ 153 public static byte max(byte... array) { 154 checkArgument(array.length > 0); 155 int max = toInt(array[0]); 156 for (int i = 1; i < array.length; i++) { 157 int next = toInt(array[i]); 158 if (next > max) { 159 max = next; 160 } 161 } 162 return (byte) max; 163 } 164 165 /** 166 * Returns a string representation of x, where x is treated as unsigned. 167 * 168 * @since 13.0 169 */ 170 @Beta 171 public static String toString(byte x) { 172 return toString(x, 10); 173 } 174 175 /** 176 * Returns a string representation of {@code x} for the given radix, where {@code x} is treated as 177 * unsigned. 178 * 179 * @param x the value to convert to a string. 180 * @param radix the radix to use while working with {@code x} 181 * @throws IllegalArgumentException if {@code radix} is not between {@link Character#MIN_RADIX} 182 * and {@link Character#MAX_RADIX}. 183 * @since 13.0 184 */ 185 @Beta 186 public static String toString(byte x, int radix) { 187 checkArgument( 188 radix >= Character.MIN_RADIX && radix <= Character.MAX_RADIX, 189 "radix (%s) must be between Character.MIN_RADIX and Character.MAX_RADIX", 190 radix); 191 // Benchmarks indicate this is probably not worth optimizing. 192 return Integer.toString(toInt(x), radix); 193 } 194 195 /** 196 * Returns the unsigned {@code byte} value represented by the given decimal string. 197 * 198 * @throws NumberFormatException if the string does not contain a valid unsigned {@code byte} 199 * value 200 * @throws NullPointerException if {@code string} is null (in contrast to {@link 201 * Byte#parseByte(String)}) 202 * @since 13.0 203 */ 204 @Beta 205 @CanIgnoreReturnValue 206 public static byte parseUnsignedByte(String string) { 207 return parseUnsignedByte(string, 10); 208 } 209 210 /** 211 * Returns the unsigned {@code byte} value represented by a string with the given radix. 212 * 213 * @param string the string containing the unsigned {@code byte} representation to be parsed. 214 * @param radix the radix to use while parsing {@code string} 215 * @throws NumberFormatException if the string does not contain a valid unsigned {@code byte} with 216 * the given radix, or if {@code radix} is not between {@link Character#MIN_RADIX} and {@link 217 * Character#MAX_RADIX}. 218 * @throws NullPointerException if {@code string} is null (in contrast to {@link 219 * Byte#parseByte(String)}) 220 * @since 13.0 221 */ 222 @Beta 223 @CanIgnoreReturnValue 224 public static byte parseUnsignedByte(String string, int radix) { 225 int parse = Integer.parseInt(checkNotNull(string), radix); 226 // We need to throw a NumberFormatException, so we have to duplicate checkedCast. =( 227 if (parse >> Byte.SIZE == 0) { 228 return (byte) parse; 229 } else { 230 throw new NumberFormatException("out of range: " + parse); 231 } 232 } 233 234 /** 235 * Returns a string containing the supplied {@code byte} values separated by {@code separator}. 236 * For example, {@code join(":", (byte) 1, (byte) 2, (byte) 255)} returns the string {@code 237 * "1:2:255"}. 238 * 239 * @param separator the text that should appear between consecutive values in the resulting string 240 * (but not at the start or end) 241 * @param array an array of {@code byte} values, possibly empty 242 */ 243 public static String join(String separator, byte... array) { 244 checkNotNull(separator); 245 if (array.length == 0) { 246 return ""; 247 } 248 249 // For pre-sizing a builder, just get the right order of magnitude 250 StringBuilder builder = new StringBuilder(array.length * (3 + separator.length())); 251 builder.append(toInt(array[0])); 252 for (int i = 1; i < array.length; i++) { 253 builder.append(separator).append(toString(array[i])); 254 } 255 return builder.toString(); 256 } 257 258 /** 259 * Returns a comparator that compares two {@code byte} arrays <a 260 * href="http://en.wikipedia.org/wiki/Lexicographical_order">lexicographically</a>. That is, it 261 * compares, using {@link #compare(byte, byte)}), the first pair of values that follow any common 262 * prefix, or when one array is a prefix of the other, treats the shorter array as the lesser. For 263 * example, {@code [] < [0x01] < [0x01, 0x7F] < [0x01, 0x80] < [0x02]}. Values are treated as 264 * unsigned. 265 * 266 * <p>The returned comparator is inconsistent with {@link Object#equals(Object)} (since arrays 267 * support only identity equality), but it is consistent with {@link 268 * java.util.Arrays#equals(byte[], byte[])}. 269 * 270 * @since 2.0 271 */ 272 public static Comparator<byte[]> lexicographicalComparator() { 273 return LexicographicalComparatorHolder.BEST_COMPARATOR; 274 } 275 276 @VisibleForTesting 277 static Comparator<byte[]> lexicographicalComparatorJavaImpl() { 278 return LexicographicalComparatorHolder.PureJavaComparator.INSTANCE; 279 } 280 281 /** 282 * Provides a lexicographical comparator implementation; either a Java implementation or a faster 283 * implementation based on {@link Unsafe}. 284 * 285 * <p>Uses reflection to gracefully fall back to the Java implementation if {@code Unsafe} isn't 286 * available. 287 */ 288 @VisibleForTesting 289 static class LexicographicalComparatorHolder { 290 static final String UNSAFE_COMPARATOR_NAME = 291 LexicographicalComparatorHolder.class.getName() + "$UnsafeComparator"; 292 293 static final Comparator<byte[]> BEST_COMPARATOR = getBestComparator(); 294 295 @VisibleForTesting 296 enum UnsafeComparator implements Comparator<byte[]> { 297 INSTANCE; 298 299 static final boolean BIG_ENDIAN = ByteOrder.nativeOrder().equals(ByteOrder.BIG_ENDIAN); 300 301 /* 302 * The following static final fields exist for performance reasons. 303 * 304 * In UnsignedBytesBenchmark, accessing the following objects via static final fields is the 305 * fastest (more than twice as fast as the Java implementation, vs ~1.5x with non-final static 306 * fields, on x86_32) under the Hotspot server compiler. The reason is obviously that the 307 * non-final fields need to be reloaded inside the loop. 308 * 309 * And, no, defining (final or not) local variables out of the loop still isn't as good 310 * because the null check on the theUnsafe object remains inside the loop and 311 * BYTE_ARRAY_BASE_OFFSET doesn't get constant-folded. 312 * 313 * The compiler can treat static final fields as compile-time constants and can constant-fold 314 * them while (final or not) local variables are run time values. 315 */ 316 317 static final Unsafe theUnsafe = getUnsafe(); 318 319 /** The offset to the first element in a byte array. */ 320 static final int BYTE_ARRAY_BASE_OFFSET = theUnsafe.arrayBaseOffset(byte[].class); 321 322 static { 323 // fall back to the safer pure java implementation unless we're in 324 // a 64-bit JVM with an 8-byte aligned field offset. 325 if (!("64".equals(System.getProperty("sun.arch.data.model")) 326 && (BYTE_ARRAY_BASE_OFFSET % 8) == 0 327 // sanity check - this should never fail 328 && theUnsafe.arrayIndexScale(byte[].class) == 1)) { 329 throw new Error(); // force fallback to PureJavaComparator 330 } 331 } 332 333 /** 334 * Returns a sun.misc.Unsafe. Suitable for use in a 3rd party package. Replace with a simple 335 * call to Unsafe.getUnsafe when integrating into a jdk. 336 * 337 * @return a sun.misc.Unsafe 338 */ 339 private static sun.misc.Unsafe getUnsafe() { 340 try { 341 return sun.misc.Unsafe.getUnsafe(); 342 } catch (SecurityException e) { 343 // that's okay; try reflection instead 344 } 345 try { 346 return java.security.AccessController.doPrivileged( 347 new java.security.PrivilegedExceptionAction<sun.misc.Unsafe>() { 348 @Override 349 public sun.misc.Unsafe run() throws Exception { 350 Class<sun.misc.Unsafe> k = sun.misc.Unsafe.class; 351 for (java.lang.reflect.Field f : k.getDeclaredFields()) { 352 f.setAccessible(true); 353 Object x = f.get(null); 354 if (k.isInstance(x)) { 355 return k.cast(x); 356 } 357 } 358 throw new NoSuchFieldError("the Unsafe"); 359 } 360 }); 361 } catch (java.security.PrivilegedActionException e) { 362 throw new RuntimeException("Could not initialize intrinsics", e.getCause()); 363 } 364 } 365 366 @Override 367 public int compare(byte[] left, byte[] right) { 368 final int stride = 8; 369 int minLength = Math.min(left.length, right.length); 370 int strideLimit = minLength & ~(stride - 1); 371 int i; 372 373 /* 374 * Compare 8 bytes at a time. Benchmarking on x86 shows a stride of 8 bytes is no slower 375 * than 4 bytes even on 32-bit. On the other hand, it is substantially faster on 64-bit. 376 */ 377 for (i = 0; i < strideLimit; i += stride) { 378 long lw = theUnsafe.getLong(left, BYTE_ARRAY_BASE_OFFSET + (long) i); 379 long rw = theUnsafe.getLong(right, BYTE_ARRAY_BASE_OFFSET + (long) i); 380 if (lw != rw) { 381 if (BIG_ENDIAN) { 382 return UnsignedLongs.compare(lw, rw); 383 } 384 385 /* 386 * We want to compare only the first index where left[index] != right[index]. This 387 * corresponds to the least significant nonzero byte in lw ^ rw, since lw and rw are 388 * little-endian. Long.numberOfTrailingZeros(diff) tells us the least significant 389 * nonzero bit, and zeroing out the first three bits of L.nTZ gives us the shift to get 390 * that least significant nonzero byte. 391 */ 392 int n = Long.numberOfTrailingZeros(lw ^ rw) & ~0x7; 393 return ((int) ((lw >>> n) & UNSIGNED_MASK)) - ((int) ((rw >>> n) & UNSIGNED_MASK)); 394 } 395 } 396 397 // The epilogue to cover the last (minLength % stride) elements. 398 for (; i < minLength; i++) { 399 int result = UnsignedBytes.compare(left[i], right[i]); 400 if (result != 0) { 401 return result; 402 } 403 } 404 return left.length - right.length; 405 } 406 407 @Override 408 public String toString() { 409 return "UnsignedBytes.lexicographicalComparator() (sun.misc.Unsafe version)"; 410 } 411 } 412 413 enum PureJavaComparator implements Comparator<byte[]> { 414 INSTANCE; 415 416 @Override 417 public int compare(byte[] left, byte[] right) { 418 int minLength = Math.min(left.length, right.length); 419 for (int i = 0; i < minLength; i++) { 420 int result = UnsignedBytes.compare(left[i], right[i]); 421 if (result != 0) { 422 return result; 423 } 424 } 425 return left.length - right.length; 426 } 427 428 @Override 429 public String toString() { 430 return "UnsignedBytes.lexicographicalComparator() (pure Java version)"; 431 } 432 } 433 434 /** 435 * Returns the Unsafe-using Comparator, or falls back to the pure-Java implementation if unable 436 * to do so. 437 */ 438 static Comparator<byte[]> getBestComparator() { 439 try { 440 Class<?> theClass = Class.forName(UNSAFE_COMPARATOR_NAME); 441 442 // requireNonNull is safe because the class is an enum. 443 Object[] constants = requireNonNull(theClass.getEnumConstants()); 444 445 // yes, UnsafeComparator does implement Comparator<byte[]> 446 @SuppressWarnings("unchecked") 447 Comparator<byte[]> comparator = (Comparator<byte[]>) constants[0]; 448 return comparator; 449 } catch (Throwable t) { // ensure we really catch *everything* 450 return lexicographicalComparatorJavaImpl(); 451 } 452 } 453 } 454 455 private static byte flip(byte b) { 456 return (byte) (b ^ 0x80); 457 } 458 459 /** 460 * Sorts the array, treating its elements as unsigned bytes. 461 * 462 * @since 23.1 463 */ 464 public static void sort(byte[] array) { 465 checkNotNull(array); 466 sort(array, 0, array.length); 467 } 468 469 /** 470 * Sorts the array between {@code fromIndex} inclusive and {@code toIndex} exclusive, treating its 471 * elements as unsigned bytes. 472 * 473 * @since 23.1 474 */ 475 public static void sort(byte[] array, int fromIndex, int toIndex) { 476 checkNotNull(array); 477 checkPositionIndexes(fromIndex, toIndex, array.length); 478 for (int i = fromIndex; i < toIndex; i++) { 479 array[i] = flip(array[i]); 480 } 481 Arrays.sort(array, fromIndex, toIndex); 482 for (int i = fromIndex; i < toIndex; i++) { 483 array[i] = flip(array[i]); 484 } 485 } 486 487 /** 488 * Sorts the elements of {@code array} in descending order, interpreting them as unsigned 8-bit 489 * integers. 490 * 491 * @since 23.1 492 */ 493 public static void sortDescending(byte[] array) { 494 checkNotNull(array); 495 sortDescending(array, 0, array.length); 496 } 497 498 /** 499 * Sorts the elements of {@code array} between {@code fromIndex} inclusive and {@code toIndex} 500 * exclusive in descending order, interpreting them as unsigned 8-bit integers. 501 * 502 * @since 23.1 503 */ 504 public static void sortDescending(byte[] array, int fromIndex, int toIndex) { 505 checkNotNull(array); 506 checkPositionIndexes(fromIndex, toIndex, array.length); 507 for (int i = fromIndex; i < toIndex; i++) { 508 array[i] ^= Byte.MAX_VALUE; 509 } 510 Arrays.sort(array, fromIndex, toIndex); 511 for (int i = fromIndex; i < toIndex; i++) { 512 array[i] ^= Byte.MAX_VALUE; 513 } 514 } 515}