001 /*
002 * Copyright (C) 2009 The Guava Authors
003 *
004 * Licensed under the Apache License, Version 2.0 (the "License");
005 * you may not use this file except in compliance with the License.
006 * You may obtain a copy of the License at
007 *
008 * http://www.apache.org/licenses/LICENSE-2.0
009 *
010 * Unless required by applicable law or agreed to in writing, software
011 * distributed under the License is distributed on an "AS IS" BASIS,
012 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
013 * See the License for the specific language governing permissions and
014 * limitations under the License.
015 */
016
017 package com.google.common.primitives;
018
019 import static com.google.common.base.Preconditions.checkArgument;
020 import static com.google.common.base.Preconditions.checkNotNull;
021
022 import com.google.common.annotations.VisibleForTesting;
023
024 import sun.misc.Unsafe;
025
026 import java.lang.reflect.Field;
027 import java.nio.ByteOrder;
028 import java.security.AccessController;
029 import java.security.PrivilegedAction;
030 import java.util.Comparator;
031
032 /**
033 * Static utility methods pertaining to {@code byte} primitives that interpret
034 * values as <i>unsigned</i> (that is, any negative value {@code b} is treated
035 * as the positive value {@code 256 + b}). The corresponding methods that treat
036 * the values as signed are found in {@link SignedBytes}, and the methods for
037 * which signedness is not an issue are in {@link Bytes}.
038 *
039 * @author Kevin Bourrillion
040 * @author Martin Buchholz
041 * @author Hiroshi Yamauchi
042 * @since 1.0
043 */
044 public final class UnsignedBytes {
045 private UnsignedBytes() {}
046
047 /**
048 * The largest power of two that can be represented as an unsigned {@code byte}.
049 *
050 * @since 10.0
051 */
052 public static final byte MAX_POWER_OF_TWO = (byte) (1 << 7);
053
054 /**
055 * Returns the value of the given byte as an integer, when treated as
056 * unsigned. That is, returns {@code value + 256} if {@code value} is
057 * negative; {@code value} itself otherwise.
058 *
059 * @since 6.0
060 */
061 public static int toInt(byte value) {
062 return value & 0xFF;
063 }
064
065 /**
066 * Returns the {@code byte} value that, when treated as unsigned, is equal to
067 * {@code value}, if possible.
068 *
069 * @param value a value between 0 and 255 inclusive
070 * @return the {@code byte} value that, when treated as unsigned, equals
071 * {@code value}
072 * @throws IllegalArgumentException if {@code value} is negative or greater
073 * than 255
074 */
075 public static byte checkedCast(long value) {
076 checkArgument(value >> 8 == 0, "out of range: %s", value);
077 return (byte) value;
078 }
079
080 /**
081 * Returns the {@code byte} value that, when treated as unsigned, is nearest
082 * in value to {@code value}.
083 *
084 * @param value any {@code long} value
085 * @return {@code (byte) 255} if {@code value >= 255}, {@code (byte) 0} if
086 * {@code value <= 0}, and {@code value} cast to {@code byte} otherwise
087 */
088 public static byte saturatedCast(long value) {
089 if (value > 255) {
090 return (byte) 255; // -1
091 }
092 if (value < 0) {
093 return (byte) 0;
094 }
095 return (byte) value;
096 }
097
098 /**
099 * Compares the two specified {@code byte} values, treating them as unsigned
100 * values between 0 and 255 inclusive. For example, {@code (byte) -127} is
101 * considered greater than {@code (byte) 127} because it is seen as having
102 * the value of positive {@code 129}.
103 *
104 * @param a the first {@code byte} to compare
105 * @param b the second {@code byte} to compare
106 * @return a negative value if {@code a} is less than {@code b}; a positive
107 * value if {@code a} is greater than {@code b}; or zero if they are equal
108 */
109 public static int compare(byte a, byte b) {
110 return toInt(a) - toInt(b);
111 }
112
113 /**
114 * Returns the least value present in {@code array}.
115 *
116 * @param array a <i>nonempty</i> array of {@code byte} values
117 * @return the value present in {@code array} that is less than or equal to
118 * every other value in the array
119 * @throws IllegalArgumentException if {@code array} is empty
120 */
121 public static byte min(byte... array) {
122 checkArgument(array.length > 0);
123 int min = toInt(array[0]);
124 for (int i = 1; i < array.length; i++) {
125 int next = toInt(array[i]);
126 if (next < min) {
127 min = next;
128 }
129 }
130 return (byte) min;
131 }
132
133 /**
134 * Returns the greatest value present in {@code array}.
135 *
136 * @param array a <i>nonempty</i> array of {@code byte} values
137 * @return the value present in {@code array} that is greater than or equal
138 * to every other value in the array
139 * @throws IllegalArgumentException if {@code array} is empty
140 */
141 public static byte max(byte... array) {
142 checkArgument(array.length > 0);
143 int max = toInt(array[0]);
144 for (int i = 1; i < array.length; i++) {
145 int next = toInt(array[i]);
146 if (next > max) {
147 max = next;
148 }
149 }
150 return (byte) max;
151 }
152
153 /**
154 * Returns a string containing the supplied {@code byte} values separated by
155 * {@code separator}. For example, {@code join(":", (byte) 1, (byte) 2,
156 * (byte) 255)} returns the string {@code "1:2:255"}.
157 *
158 * @param separator the text that should appear between consecutive values in
159 * the resulting string (but not at the start or end)
160 * @param array an array of {@code byte} values, possibly empty
161 */
162 public static String join(String separator, byte... array) {
163 checkNotNull(separator);
164 if (array.length == 0) {
165 return "";
166 }
167
168 // For pre-sizing a builder, just get the right order of magnitude
169 StringBuilder builder = new StringBuilder(array.length * 5);
170 builder.append(toInt(array[0]));
171 for (int i = 1; i < array.length; i++) {
172 builder.append(separator).append(toInt(array[i]));
173 }
174 return builder.toString();
175 }
176
177 /**
178 * Returns a comparator that compares two {@code byte} arrays
179 * lexicographically. That is, it compares, using {@link
180 * #compare(byte, byte)}), the first pair of values that follow any common
181 * prefix, or when one array is a prefix of the other, treats the shorter
182 * array as the lesser. For example, {@code [] < [0x01] < [0x01, 0x7F] <
183 * [0x01, 0x80] < [0x02]}. Values are treated as unsigned.
184 *
185 * <p>The returned comparator is inconsistent with {@link
186 * Object#equals(Object)} (since arrays support only identity equality), but
187 * it is consistent with {@link java.util.Arrays#equals(byte[], byte[])}.
188 *
189 * @see <a href="http://en.wikipedia.org/wiki/Lexicographical_order">
190 * Lexicographical order article at Wikipedia</a>
191 * @since 2.0
192 */
193 public static Comparator<byte[]> lexicographicalComparator() {
194 return LexicographicalComparatorHolder.BEST_COMPARATOR;
195 }
196
197 @VisibleForTesting
198 static Comparator<byte[]> lexicographicalComparatorJavaImpl() {
199 return LexicographicalComparatorHolder.PureJavaComparator.INSTANCE;
200 }
201
202 /**
203 * Provides a lexicographical comparator implementation; either a Java
204 * implementation or a faster implementation based on {@link Unsafe}.
205 *
206 * <p>Uses reflection to gracefully fall back to the Java implementation if
207 * {@code Unsafe} isn't available.
208 */
209 @VisibleForTesting
210 static class LexicographicalComparatorHolder {
211 static final String UNSAFE_COMPARATOR_NAME =
212 LexicographicalComparatorHolder.class.getName() + "$UnsafeComparator";
213
214 static final Comparator<byte[]> BEST_COMPARATOR = getBestComparator();
215
216 @VisibleForTesting
217 enum UnsafeComparator implements Comparator<byte[]> {
218 INSTANCE;
219
220 static final boolean littleEndian =
221 ByteOrder.nativeOrder().equals(ByteOrder.LITTLE_ENDIAN);
222
223 /*
224 * The following static final fields exist for performance reasons.
225 *
226 * In UnsignedBytesBenchmark, accessing the following objects via static
227 * final fields is the fastest (more than twice as fast as the Java
228 * implementation, vs ~1.5x with non-final static fields, on x86_32)
229 * under the Hotspot server compiler. The reason is obviously that the
230 * non-final fields need to be reloaded inside the loop.
231 *
232 * And, no, defining (final or not) local variables out of the loop still
233 * isn't as good because the null check on the theUnsafe object remains
234 * inside the loop and BYTE_ARRAY_BASE_OFFSET doesn't get
235 * constant-folded.
236 *
237 * The compiler can treat static final fields as compile-time constants
238 * and can constant-fold them while (final or not) local variables are
239 * run time values.
240 */
241
242 static final Unsafe theUnsafe;
243
244 /** The offset to the first element in a byte array. */
245 static final int BYTE_ARRAY_BASE_OFFSET;
246
247 static {
248 theUnsafe = (Unsafe) AccessController.doPrivileged(
249 new PrivilegedAction<Object>() {
250 @Override
251 public Object run() {
252 try {
253 Field f = Unsafe.class.getDeclaredField("theUnsafe");
254 f.setAccessible(true);
255 return f.get(null);
256 } catch (NoSuchFieldException e) {
257 // It doesn't matter what we throw;
258 // it's swallowed in getBestComparator().
259 throw new Error();
260 } catch (IllegalAccessException e) {
261 throw new Error();
262 }
263 }
264 });
265
266 BYTE_ARRAY_BASE_OFFSET = theUnsafe.arrayBaseOffset(byte[].class);
267
268 // sanity check - this should never fail
269 if (theUnsafe.arrayIndexScale(byte[].class) != 1) {
270 throw new AssertionError();
271 }
272 }
273
274 @Override public int compare(byte[] left, byte[] right) {
275 int minLength = Math.min(left.length, right.length);
276 int minWords = minLength / Longs.BYTES;
277
278 /*
279 * Compare 8 bytes at a time. Benchmarking shows comparing 8 bytes at a
280 * time is no slower than comparing 4 bytes at a time even on 32-bit.
281 * On the other hand, it is substantially faster on 64-bit.
282 */
283 for (int i = 0; i < minWords * Longs.BYTES; i += Longs.BYTES) {
284 long lw = theUnsafe.getLong(left, BYTE_ARRAY_BASE_OFFSET + (long) i);
285 long rw = theUnsafe.getLong(right, BYTE_ARRAY_BASE_OFFSET + (long) i);
286 long diff = lw ^ rw;
287
288 if (diff != 0) {
289 if (!littleEndian) {
290 return UnsignedLongs.compare(lw, rw);
291 }
292
293 // Use binary search
294 int n = 0;
295 int y;
296 int x = (int) diff;
297 if (x == 0) {
298 x = (int) (diff >>> 32);
299 n = 32;
300 }
301
302 y = x << 16;
303 if (y == 0) {
304 n += 16;
305 } else {
306 x = y;
307 }
308
309 y = x << 8;
310 if (y == 0) {
311 n += 8;
312 }
313 return (int) (((lw >>> n) & 0xFFL) - ((rw >>> n) & 0xFFL));
314 }
315 }
316
317 // The epilogue to cover the last (minLength % 8) elements.
318 for (int i = minWords * Longs.BYTES; i < minLength; i++) {
319 int result = UnsignedBytes.compare(left[i], right[i]);
320 if (result != 0) {
321 return result;
322 }
323 }
324 return left.length - right.length;
325 }
326 }
327
328 enum PureJavaComparator implements Comparator<byte[]> {
329 INSTANCE;
330
331 @Override public int compare(byte[] left, byte[] right) {
332 int minLength = Math.min(left.length, right.length);
333 for (int i = 0; i < minLength; i++) {
334 int result = UnsignedBytes.compare(left[i], right[i]);
335 if (result != 0) {
336 return result;
337 }
338 }
339 return left.length - right.length;
340 }
341 }
342
343 /**
344 * Returns the Unsafe-using Comparator, or falls back to the pure-Java
345 * implementation if unable to do so.
346 */
347 static Comparator<byte[]> getBestComparator() {
348 try {
349 Class<?> theClass = Class.forName(UNSAFE_COMPARATOR_NAME);
350
351 // yes, UnsafeComparator does implement Comparator<byte[]>
352 @SuppressWarnings("unchecked")
353 Comparator<byte[]> comparator =
354 (Comparator<byte[]>) theClass.getEnumConstants()[0];
355 return comparator;
356 } catch (Throwable t) { // ensure we really catch *everything*
357 return lexicographicalComparatorJavaImpl();
358 }
359 }
360 }
361 }
362