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