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}