Unsigned Short

UnsignedShorts.java

import static com.google.common.base.Preconditions.checkArgument;
import static com.google.common.base.Preconditions.checkNotNull;

import java.lang.reflect.Field;
import java.nio.ByteOrder;
import java.security.AccessController;
import java.security.PrivilegedAction;
import java.util.Comparator;

import sun.misc.Unsafe;

import com.google.common.annotations.VisibleForTesting;
import com.google.common.primitives.Longs;
import com.google.common.primitives.Shorts;

/**
 * Static utility methods pertaining to {@code short} primitives that interpret
 * values as <i>unsigned</i> (that is, any negative value {@code b} is treated
 * as the positive value {@code 256 + b}). The corresponding methods that treat
 * the values as signed are found in {@link SignedShorts}, and the methods for
 * which signedness is not an issue are in {@link Shorts}.
 * 
 */
public final class UnsignedShorts {
    private UnsignedShorts() {}

    /**
     * Returns the value of the given short as an integer, when treated as
     * unsigned. That is, returns {@code value + 256} if {@code value} is
     * negative; {@code value} itself otherwise.
     * 
     * @since 6
     */
    public static int toInt(short value) {
        return value & 0xFFFF;
    }

    /**
     * Returns the {@code short} value that, when treated as unsigned, is equal
     * to {@code value}, if possible.
     * 
     * @param value
     *            a value between 0 and 65535 inclusive
     * @return the {@code short} value that, when treated as unsigned, equals
     *         {@code value}
     * @throws IllegalArgumentException
     *             if {@code value} is negative or greater than 65535
     */
    public static short checkedCast(long value) {
        checkArgument(value >> 16 == 0, "out of range: %s", value);
        return (short) value;
    }

    /**
     * Returns the {@code short} value that, when treated as unsigned, is
     * nearest in value to {@code value}.
     * 
     * @param value
     *            any {@code long} value
     * @return {@code (short) 65535} if {@code value >= 65535},
     *         {@code (short) 0} if {@code value <= 0}, and {@code value} cast
     *         to {@code short} otherwise
     */
    public static short saturatedCast(long value) {
        if (value > 65535) {
            return (short) 65535; // -1
        }
        if (value < 0) {
            return (short) 0;
        }
        return (short) value;
    }

    /**
     * Compares the two specified {@code short} values, treating them as
     * unsigned values between 0 and 65535 inclusive. For example,
     * {@code (short) -32767} is considered greater than {@code (short) 32767}
     * because it is seen as having the value of positive {@code 32769}.
     * 
     * @param a
     *            the first {@code short} to compare
     * @param b
     *            the second {@code short} to compare
     * @return a negative value if {@code a} is less than {@code b}; a positive
     *         value if {@code a} is greater than {@code b}; or zero if they are
     *         equal
     */
    public static int compare(short a, short b) {
        return toInt(a) - toInt(b);
    }

    /**
     * Returns the least value present in {@code array}.
     * 
     * @param array
     *            a <i>nonempty</i> array of {@code short} values
     * @return the value present in {@code array} that is less than or equal to
     *         every other value in the array
     * @throws IllegalArgumentException
     *             if {@code array} is empty
     */
    public static short min(short... array) {
        checkArgument(array.length > 0);
        int min = toInt(array[0]);
        for (int i = 1; i < array.length; i++) {
            int next = toInt(array[i]);
            if (next < min) {
                min = next;
            }
        }
        return (short) min;
    }

    /**
     * Returns the greatest value present in {@code array}.
     * 
     * @param array
     *            a <i>nonempty</i> array of {@code short} values
     * @return the value present in {@code array} that is greater than or equal
     *         to every other value in the array
     * @throws IllegalArgumentException
     *             if {@code array} is empty
     */
    public static short max(short... array) {
        checkArgument(array.length > 0);
        int max = toInt(array[0]);
        for (int i = 1; i < array.length; i++) {
            int next = toInt(array[i]);
            if (next > max) {
                max = next;
            }
        }
        return (short) max;
    }

    /**
     * Returns a string containing the supplied {@code short} values separated
     * by {@code separator}. For example, {@code join(":", (short) 1, (short) 2,
     * (short) 255)} returns the string {@code "1:2:255"}.
     * 
     * @param separator
     *            the text that should appear between consecutive values in the
     *            resulting string (but not at the start or end)
     * @param array
     *            an array of {@code short} values, possibly empty
     */
    public static String join(String separator, short... array) {
        checkNotNull(separator);
        if (array.length == 0) {
            return "";
        }

        // For pre-sizing a builder, just get the right order of magnitude
        StringBuilder builder = new StringBuilder(array.length * 5);
        builder.append(toInt(array[0]));
        for (int i = 1; i < array.length; i++) {
            builder.append(separator).append(toInt(array[i]));
        }
        return builder.toString();
    }

    /**
     * Returns a comparator that compares two {@code short} arrays
     * lexicographically. That is, it compares, using
     * {@link #compare(short, short)}), the first pair of values that follow any
     * common prefix, or when one array is a prefix of the other, treats the
     * shorter array as the lesser. For example,
     * {@code [] < [0x01] < [0x01, 0x7F] <
     * [0x01, 0x80] < [0x02]}. Values are treated as unsigned.
     * 
     * <p>
     * The returned comparator is inconsistent with
     * {@link Object#equals(Object)} (since arrays support only identity
     * equality), but it is consistent with
     * {@link java.util.Arrays#equals(short[], short[])}.
     * 
     * @see <a href="http://en.wikipedia.org/wiki/Lexicographical_order">
     *      Lexicographical order article at Wikipedia</a>
     * @since 2
     */
    public static Comparator<short[]> lexicographicalComparator() {
        return LexicographicalComparatorHolder.BEST_COMPARATOR;
    }

    @VisibleForTesting
    static Comparator<short[]> lexicographicalComparatorJavaImpl() {
        return LexicographicalComparatorHolder.PureJavaComparator.INSTANCE;
    }

    /**
     * Provides a lexicographical comparator implementation; either a Java
     * implementation or a faster implementation based on {@link Unsafe}.
     * 
     * <p>
     * Uses reflection to gracefully fall back to the Java implementation if
     * {@code Unsafe} isn't available.
     */
    @VisibleForTesting
    static class LexicographicalComparatorHolder {
        static final String UNSAFE_COMPARATOR_NAME = LexicographicalComparatorHolder.class.getName()
                                                     + "$UnsafeComparator";

        static final Comparator<short[]> BEST_COMPARATOR = getBestComparator();

        // only access this class via reflection!
        enum UnsafeComparator implements Comparator<short[]> {
            INSTANCE;

            static final boolean littleEndian = ByteOrder.nativeOrder()
                                                         .equals(ByteOrder.LITTLE_ENDIAN);

            /*
             * The following static final fields exist for performance reasons.
             * 
             * In UnsignedShortsBenchmark, accessing the following objects via
             * static final fields is the fastest (more than twice as fast as
             * the Java implementation, vs ~1.5x with non-final static fields,
             * on x86_32) under the Hotspot server compiler. The reason is
             * obviously that the non-final fields need to be reloaded inside
             * the loop.
             * 
             * And, no, defining (final or not) local variables out of the loop
             * still isn't as good because the null check on the theUnsafe
             * object remains inside the loop and SHORT_ARRAY_BASE_OFFSET
             * doesn't get constant-folded.
             * 
             * The compiler can treat static final fields as compile-time
             * constants and can constant-fold them while (final or not) local
             * variables are run time values.
             */

            static final Unsafe theUnsafe;

            /** The offset to the first element in a short array. */
            static final int SHORT_ARRAY_BASE_OFFSET;

            static {
                theUnsafe = (Unsafe) AccessController.doPrivileged(new PrivilegedAction<Object>() {
                    @Override
                    public Object run() {
                        try {
                            Field f = Unsafe.class.getDeclaredField("theUnsafe");
                            f.setAccessible(true);
                            return f.get(null);
                        }
                        catch (NoSuchFieldException e) {
                            // It doesn't matter what we throw;
                            // it's swallowed in getBestComparator().
                            throw new Error();
                        }
                        catch (IllegalAccessException e) {
                            throw new Error();
                        }
                    }
                });

                SHORT_ARRAY_BASE_OFFSET = theUnsafe.arrayBaseOffset(short[].class);

                // sanity check - this should never fail
                if (theUnsafe.arrayIndexScale(short[].class) != 1) {
                    throw new AssertionError();
                }
            }

            /**
             * Returns true if x1 is less than x2, when both values are treated
             * as unsigned.
             */
            // TODO(kevinb): Should be a common method in
            // primitives.UnsignedLongs.
            static boolean lessThanUnsigned(long x1, long x2) {
                return (x1 + Long.MIN_VALUE) < (x2 + Long.MIN_VALUE);
            }

            @Override
            public int compare(short[] left, short[] right) {
                int minLength = Math.min(left.length, right.length);
                int minWords = minLength / Longs.BYTES;

                /*
                 * Compare 8 bytes at a time. Benchmarking shows comparing 8
                 * bytes at a time is no slower than comparing 4 bytes at a time
                 * even on 32-bit. On the other hand, it is substantially faster
                 * on 64-bit.
                 */
                for (int i = 0; i < minWords * Longs.BYTES; i += Longs.BYTES) {
                    long lw = theUnsafe.getLong(left, SHORT_ARRAY_BASE_OFFSET + (long) i);
                    long rw = theUnsafe.getLong(right, SHORT_ARRAY_BASE_OFFSET + (long) i);
                    long diff = lw ^ rw;

                    if (diff != 0) {
                        if (!littleEndian) {
                            return lessThanUnsigned(lw, rw) ? -1 : 1;
                        }

                        // Use binary search
                        int n = 0;
                        int y;
                        int x = (int) diff;
                        if (x == 0) {
                            x = (int) (diff >>> 32);
                            n = 32;
                        }

                        y = x << 16;
                        if (y == 0) {
                            n += 16;
                        } else {
                            x = y;
                        }

                        y = x << 8;
                        if (y == 0) {
                            n += 8;
                        }
                        return (int) (((lw >>> n) & 0xFFL) - ((rw >>> n) & 0xFFL));
                    }
                }

                // The epilogue to cover the last (minLength % 8) elements.
                for (int i = minWords * Longs.BYTES; i < minLength; i++) {
                    int result = UnsignedShorts.compare(left[i], right[i]);
                    if (result != 0) {
                        return result;
                    }
                }
                return left.length - right.length;
            }
        }

        enum PureJavaComparator implements Comparator<short[]> {
            INSTANCE;

            @Override
            public int compare(short[] left, short[] right) {
                int minLength = Math.min(left.length, right.length);
                for (int i = 0; i < minLength; i++) {
                    int result = UnsignedShorts.compare(left[i], right[i]);
                    if (result != 0) {
                        return result;
                    }
                }
                return left.length - right.length;
            }
        }

        /**
         * Returns the Unsafe-using Comparator, or falls back to the pure-Java
         * implementation if unable to do so.
         */
        static Comparator<short[]> getBestComparator() {
            try {
                Class<?> theClass = Class.forName(UNSAFE_COMPARATOR_NAME);

                // yes, UnsafeComparator does implement Comparator<short[]>
                @SuppressWarnings("unchecked")
                Comparator<short[]> comparator = (Comparator<short[]>) theClass.getEnumConstants()[0];
                return comparator;
            }
            catch (Throwable t) { // ensure we really catch *everything*
                return lexicographicalComparatorJavaImpl();
            }
        }
    }
}