| /* |
| * Copyright (C) 2015 The Guava Authors |
| * |
| * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except |
| * in compliance with the License. You may obtain a copy of the License at |
| * |
| * http://www.apache.org/licenses/LICENSE-2.0 |
| * |
| * Unless required by applicable law or agreed to in writing, software distributed under the License |
| * is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express |
| * or implied. See the License for the specific language governing permissions and limitations under |
| * the License. |
| */ |
| |
| package com.google.common.hash; |
| |
| import com.google.common.primitives.Longs; |
| import java.nio.ByteOrder; |
| import sun.misc.Unsafe; |
| |
| /** |
| * Utility functions for loading and storing values from a byte array. |
| * |
| * @author Kevin Damm |
| * @author Kyle Maddison |
| */ |
| final class LittleEndianByteArray { |
| |
| /** The instance that actually does the work; delegates to Unsafe or a pure-Java fallback. */ |
| private static final LittleEndianBytes byteArray; |
| |
| /** |
| * Load 8 bytes into long in a little endian manner, from the substring between position and |
| * position + 8. The array must have at least 8 bytes from offset (inclusive). |
| * |
| * @param input the input bytes |
| * @param offset the offset into the array at which to start |
| * @return a long of a concatenated 8 bytes |
| */ |
| static long load64(byte[] input, int offset) { |
| // We don't want this in production code as this is the most critical part of the loop. |
| assert input.length >= offset + 8; |
| // Delegates to the fast (unsafe) version or the fallback. |
| return byteArray.getLongLittleEndian(input, offset); |
| } |
| |
| /** |
| * Similar to load64, but allows offset + 8 > input.length, padding the result with zeroes. This |
| * has to explicitly reverse the order of the bytes as it packs them into the result which makes |
| * it slower than the native version. |
| * |
| * @param input the input bytes |
| * @param offset the offset into the array at which to start reading |
| * @param length the number of bytes from the input to read |
| * @return a long of a concatenated 8 bytes |
| */ |
| static long load64Safely(byte[] input, int offset, int length) { |
| long result = 0; |
| // Due to the way we shift, we can stop iterating once we've run out of data, the rest |
| // of the result already being filled with zeros. |
| |
| // This loop is critical to performance, so please check HashBenchmark if altering it. |
| int limit = Math.min(length, 8); |
| for (int i = 0; i < limit; i++) { |
| // Shift value left while iterating logically through the array. |
| result |= (input[offset + i] & 0xFFL) << (i * 8); |
| } |
| return result; |
| } |
| |
| /** |
| * Store 8 bytes into the provided array at the indicated offset, using the value provided. |
| * |
| * @param sink the output byte array |
| * @param offset the offset into the array at which to start writing |
| * @param value the value to write |
| */ |
| static void store64(byte[] sink, int offset, long value) { |
| // We don't want to assert in production code. |
| assert offset >= 0 && offset + 8 <= sink.length; |
| // Delegates to the fast (unsafe)version or the fallback. |
| byteArray.putLongLittleEndian(sink, offset, value); |
| } |
| |
| /** |
| * Load 4 bytes from the provided array at the indicated offset. |
| * |
| * @param source the input bytes |
| * @param offset the offset into the array at which to start |
| * @return the value found in the array in the form of a long |
| */ |
| static int load32(byte[] source, int offset) { |
| // TODO(user): Measure the benefit of delegating this to LittleEndianBytes also. |
| return (source[offset] & 0xFF) |
| | ((source[offset + 1] & 0xFF) << 8) |
| | ((source[offset + 2] & 0xFF) << 16) |
| | ((source[offset + 3] & 0xFF) << 24); |
| } |
| |
| /** |
| * Indicates that the loading of Unsafe was successful and the load and store operations will be |
| * very efficient. May be useful for calling code to fall back on an alternative implementation |
| * that is slower than Unsafe.get/store but faster than the pure-Java mask-and-shift. |
| */ |
| static boolean usingUnsafe() { |
| return (byteArray instanceof UnsafeByteArray); |
| } |
| |
| /** |
| * Common interface for retrieving a 64-bit long from a little-endian byte array. |
| * |
| * <p>This abstraction allows us to use single-instruction load and put when available, or fall |
| * back on the slower approach of using Longs.fromBytes(byte...). |
| */ |
| private interface LittleEndianBytes { |
| long getLongLittleEndian(byte[] array, int offset); |
| |
| void putLongLittleEndian(byte[] array, int offset, long value); |
| } |
| |
| /** |
| * The only reference to Unsafe is in this nested class. We set things up so that if |
| * Unsafe.theUnsafe is inaccessible, the attempt to load the nested class fails, and the outer |
| * class's static initializer can fall back on a non-Unsafe version. |
| */ |
| private enum UnsafeByteArray implements LittleEndianBytes { |
| // Do *not* change the order of these constants! |
| UNSAFE_LITTLE_ENDIAN { |
| @Override |
| public long getLongLittleEndian(byte[] array, int offset) { |
| return theUnsafe.getLong(array, (long) offset + BYTE_ARRAY_BASE_OFFSET); |
| } |
| |
| @Override |
| public void putLongLittleEndian(byte[] array, int offset, long value) { |
| theUnsafe.putLong(array, (long) offset + BYTE_ARRAY_BASE_OFFSET, value); |
| } |
| }, |
| UNSAFE_BIG_ENDIAN { |
| @Override |
| public long getLongLittleEndian(byte[] array, int offset) { |
| long bigEndian = theUnsafe.getLong(array, (long) offset + BYTE_ARRAY_BASE_OFFSET); |
| // The hardware is big-endian, so we need to reverse the order of the bytes. |
| return Long.reverseBytes(bigEndian); |
| } |
| |
| @Override |
| public void putLongLittleEndian(byte[] array, int offset, long value) { |
| // Reverse the order of the bytes before storing, since we're on big-endian hardware. |
| long littleEndianValue = Long.reverseBytes(value); |
| theUnsafe.putLong(array, (long) offset + BYTE_ARRAY_BASE_OFFSET, littleEndianValue); |
| } |
| }; |
| |
| // Provides load and store operations that use native instructions to get better performance. |
| private static final Unsafe theUnsafe; |
| |
| // The offset to the first element in a byte array. |
| private static final int BYTE_ARRAY_BASE_OFFSET; |
| |
| /** |
| * Returns a sun.misc.Unsafe. Suitable for use in a 3rd party package. Replace with a simple |
| * call to Unsafe.getUnsafe when integrating into a jdk. |
| * |
| * @return a sun.misc.Unsafe instance if successful |
| */ |
| private static sun.misc.Unsafe getUnsafe() { |
| try { |
| return sun.misc.Unsafe.getUnsafe(); |
| } catch (SecurityException tryReflectionInstead) { |
| // We'll try reflection instead. |
| } |
| try { |
| return java.security.AccessController.doPrivileged( |
| new java.security.PrivilegedExceptionAction<sun.misc.Unsafe>() { |
| @Override |
| public sun.misc.Unsafe run() throws Exception { |
| Class<sun.misc.Unsafe> k = sun.misc.Unsafe.class; |
| for (java.lang.reflect.Field f : k.getDeclaredFields()) { |
| f.setAccessible(true); |
| Object x = f.get(null); |
| if (k.isInstance(x)) { |
| return k.cast(x); |
| } |
| } |
| throw new NoSuchFieldError("the Unsafe"); |
| } |
| }); |
| } catch (java.security.PrivilegedActionException e) { |
| throw new RuntimeException("Could not initialize intrinsics", e.getCause()); |
| } |
| } |
| |
| static { |
| theUnsafe = getUnsafe(); |
| BYTE_ARRAY_BASE_OFFSET = theUnsafe.arrayBaseOffset(byte[].class); |
| |
| // sanity check - this should never fail |
| if (theUnsafe.arrayIndexScale(byte[].class) != 1) { |
| throw new AssertionError(); |
| } |
| } |
| } |
| |
| /** Fallback implementation for when Unsafe is not available in our current environment. */ |
| private enum JavaLittleEndianBytes implements LittleEndianBytes { |
| INSTANCE { |
| @Override |
| public long getLongLittleEndian(byte[] source, int offset) { |
| return Longs.fromBytes( |
| source[offset + 7], |
| source[offset + 6], |
| source[offset + 5], |
| source[offset + 4], |
| source[offset + 3], |
| source[offset + 2], |
| source[offset + 1], |
| source[offset]); |
| } |
| |
| @Override |
| public void putLongLittleEndian(byte[] sink, int offset, long value) { |
| long mask = 0xFFL; |
| for (int i = 0; i < 8; mask <<= 8, i++) { |
| sink[offset + i] = (byte) ((value & mask) >> (i * 8)); |
| } |
| } |
| }; |
| } |
| |
| static { |
| LittleEndianBytes theGetter = JavaLittleEndianBytes.INSTANCE; |
| try { |
| /* |
| UnsafeByteArray uses Unsafe.getLong() in an unsupported way, which is known to cause crashes |
| on Android when running in 32-bit mode. For maximum safety, we shouldn't use |
| Unsafe.getLong() at all, but the performance benefit on x86_64 is too great to ignore, so as |
| a compromise, we enable the optimization only on platforms that we specifically know to |
| work. |
| |
| In the future, the use of Unsafe.getLong() should be replaced by ByteBuffer.getLong(), which |
| will have an efficient native implementation in JDK 9. |
| |
| */ |
| final String arch = System.getProperty("os.arch"); |
| if ("amd64".equals(arch)) { |
| theGetter = |
| ByteOrder.nativeOrder().equals(ByteOrder.LITTLE_ENDIAN) |
| ? UnsafeByteArray.UNSAFE_LITTLE_ENDIAN |
| : UnsafeByteArray.UNSAFE_BIG_ENDIAN; |
| } |
| } catch (Throwable t) { |
| // ensure we really catch *everything* |
| } |
| byteArray = theGetter; |
| } |
| |
| /** Deter instantiation of this class. */ |
| private LittleEndianByteArray() {} |
| } |