android/guava/src/com/google/common/hash/LittleEndianByteArray.java - platform/external/guava - Git at Google

 /*
  * 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() {}
 }
	/*
	* 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() {}
	}