View Javadoc
1   /*
2    * Copyright (C) 2015 The Guava Authors
3    *
4    * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except
5    * in compliance with the License. You may obtain a copy of the License at
6    *
7    * http://www.apache.org/licenses/LICENSE-2.0
8    *
9    * Unless required by applicable law or agreed to in writing, software distributed under the License
10   * is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express
11   * or implied. See the License for the specific language governing permissions and limitations under
12   * the License.
13   */
14  
15  package com.google.common.hash;
16  
17  import com.google.common.primitives.Longs;
18  import java.nio.ByteOrder;
19  import sun.misc.Unsafe;
20  
21  /**
22   * Utility functions for loading and storing values from a byte array.
23   *
24   * @author Kevin Damm
25   * @author Kyle Maddison
26   */
27  final class LittleEndianByteArray {
28  
29    /** The instance that actually does the work; delegates to Unsafe or a pure-Java fallback. */
30    private static final LittleEndianBytes byteArray;
31  
32    /**
33     * Load 8 bytes into long in a little endian manner, from the substring between position and
34     * position + 8. The array must have at least 8 bytes from offset (inclusive).
35     *
36     * @param input the input bytes
37     * @param offset the offset into the array at which to start
38     * @return a long of a concatenated 8 bytes
39     */
40    static long load64(byte[] input, int offset) {
41      // We don't want this in production code as this is the most critical part of the loop.
42      assert input.length >= offset + 8;
43      // Delegates to the fast (unsafe) version or the fallback.
44      return byteArray.getLongLittleEndian(input, offset);
45    }
46  
47    /**
48     * Similar to load64, but allows offset + 8 > input.length, padding the result with zeroes. This
49     * has to explicitly reverse the order of the bytes as it packs them into the result which makes
50     * it slower than the native version.
51     *
52     * @param input the input bytes
53     * @param offset the offset into the array at which to start reading
54     * @param length the number of bytes from the input to read
55     * @return a long of a concatenated 8 bytes
56     */
57    static long load64Safely(byte[] input, int offset, int length) {
58      long result = 0;
59      // Due to the way we shift, we can stop iterating once we've run out of data, the rest
60      // of the result already being filled with zeros.
61  
62      // This loop is critical to performance, so please check HashBenchmark if altering it.
63      int limit = Math.min(length, 8);
64      for (int i = 0; i < limit; i++) {
65        // Shift value left while iterating logically through the array.
66        result |= (input[offset + i] & 0xFFL) << (i * 8);
67      }
68      return result;
69    }
70  
71    /**
72     * Store 8 bytes into the provided array at the indicated offset, using the value provided.
73     *
74     * @param sink the output byte array
75     * @param offset the offset into the array at which to start writing
76     * @param value the value to write
77     */
78    static void store64(byte[] sink, int offset, long value) {
79      // We don't want to assert in production code.
80      assert offset >= 0 && offset + 8 <= sink.length;
81      // Delegates to the fast (unsafe)version or the fallback.
82      byteArray.putLongLittleEndian(sink, offset, value);
83    }
84  
85    /**
86     * Load 4 bytes from the provided array at the indicated offset.
87     *
88     * @param source the input bytes
89     * @param offset the offset into the array at which to start
90     * @return the value found in the array in the form of a long
91     */
92    static int load32(byte[] source, int offset) {
93      // TODO(user): Measure the benefit of delegating this to LittleEndianBytes also.
94      return (source[offset] & 0xFF)
95          | ((source[offset + 1] & 0xFF) << 8)
96          | ((source[offset + 2] & 0xFF) << 16)
97          | ((source[offset + 3] & 0xFF) << 24);
98    }
99  
100   /**
101    * Indicates that the loading of Unsafe was successful and the load and store operations will be
102    * very efficient. May be useful for calling code to fall back on an alternative implementation
103    * that is slower than Unsafe.get/store but faster than the pure-Java mask-and-shift.
104    */
105   static boolean usingUnsafe() {
106     return (byteArray instanceof UnsafeByteArray);
107   }
108 
109   /**
110    * Common interface for retrieving a 64-bit long from a little-endian byte array.
111    *
112    * This abstraction allows us to use single-instruction load and put when available, or fall back
113    * on the slower approach of using Longs.fromBytes(byte...).
114    */
115   private interface LittleEndianBytes {
116     long getLongLittleEndian(byte[] array, int offset);
117 
118     void putLongLittleEndian(byte[] array, int offset, long value);
119   }
120 
121   /**
122    * The only reference to Unsafe is in this nested class. We set things up so that if
123    * Unsafe.theUnsafe is inaccessible, the attempt to load the nested class fails, and the outer
124    * class's static initializer can fall back on a non-Unsafe version.
125    */
126   private enum UnsafeByteArray implements LittleEndianBytes {
127     // Do *not* change the order of these constants!
128     UNSAFE_LITTLE_ENDIAN {
129       @Override
130       public long getLongLittleEndian(byte[] array, int offset) {
131         return theUnsafe.getLong(array, (long) offset + BYTE_ARRAY_BASE_OFFSET);
132       }
133 
134       @Override
135       public void putLongLittleEndian(byte[] array, int offset, long value) {
136         theUnsafe.putLong(array, (long) offset + BYTE_ARRAY_BASE_OFFSET, value);
137       }
138     },
139     UNSAFE_BIG_ENDIAN {
140       @Override
141       public long getLongLittleEndian(byte[] array, int offset) {
142         long bigEndian = theUnsafe.getLong(array, (long) offset + BYTE_ARRAY_BASE_OFFSET);
143         // The hardware is big-endian, so we need to reverse the order of the bytes.
144         return Long.reverseBytes(bigEndian);
145       }
146 
147       @Override
148       public void putLongLittleEndian(byte[] array, int offset, long value) {
149         // Reverse the order of the bytes before storing, since we're on big-endian hardware.
150         long littleEndianValue = Long.reverseBytes(value);
151         theUnsafe.putLong(array, (long) offset + BYTE_ARRAY_BASE_OFFSET, littleEndianValue);
152       }
153     };
154 
155     // Provides load and store operations that use native instructions to get better performance.
156     private static final Unsafe theUnsafe;
157 
158     // The offset to the first element in a byte array.
159     private static final int BYTE_ARRAY_BASE_OFFSET;
160 
161     /**
162      * Returns a sun.misc.Unsafe. Suitable for use in a 3rd party package. Replace with a simple
163      * call to Unsafe.getUnsafe when integrating into a jdk.
164      *
165      * @return a sun.misc.Unsafe instance if successful
166      */
167     private static sun.misc.Unsafe getUnsafe() {
168       try {
169         return sun.misc.Unsafe.getUnsafe();
170       } catch (SecurityException tryReflectionInstead) {
171         // We'll try reflection instead.
172       }
173       try {
174         return java.security.AccessController.doPrivileged(
175             new java.security.PrivilegedExceptionAction<sun.misc.Unsafe>() {
176               @Override
177               public sun.misc.Unsafe run() throws Exception {
178                 Class<sun.misc.Unsafe> k = sun.misc.Unsafe.class;
179                 for (java.lang.reflect.Field f : k.getDeclaredFields()) {
180                   f.setAccessible(true);
181                   Object x = f.get(null);
182                   if (k.isInstance(x)) {
183                     return k.cast(x);
184                   }
185                 }
186                 throw new NoSuchFieldError("the Unsafe");
187               }
188             });
189       } catch (java.security.PrivilegedActionException e) {
190         throw new RuntimeException("Could not initialize intrinsics", e.getCause());
191       }
192     }
193 
194     static {
195       theUnsafe = getUnsafe();
196       BYTE_ARRAY_BASE_OFFSET = theUnsafe.arrayBaseOffset(byte[].class);
197 
198       // sanity check - this should never fail
199       if (theUnsafe.arrayIndexScale(byte[].class) != 1) {
200         throw new AssertionError();
201       }
202     }
203   }
204 
205   /**
206    * Fallback implementation for when Unsafe is not available in our current environment.
207    */
208   private enum JavaLittleEndianBytes implements LittleEndianBytes {
209     INSTANCE {
210       @Override
211       public long getLongLittleEndian(byte[] source, int offset) {
212         return Longs.fromBytes(
213             source[offset + 7],
214             source[offset + 6],
215             source[offset + 5],
216             source[offset + 4],
217             source[offset + 3],
218             source[offset + 2],
219             source[offset + 1],
220             source[offset]);
221       }
222 
223       @Override
224       public void putLongLittleEndian(byte[] sink, int offset, long value) {
225         long mask = 0xFFL;
226         for (int i = 0; i < 8; mask <<= 8, i++) {
227           sink[offset + i] = (byte) ((value & mask) >> (i * 8));
228         }
229       }
230     };
231   }
232 
233   static {
234     LittleEndianBytes theGetter = JavaLittleEndianBytes.INSTANCE;
235     try {
236       /*
237         UnsafeByteArray uses Unsafe.getLong() in an unsupported way, which is known to cause crashes
238         on 32-bit Android (ARMv7 with ART). Ideally, we shouldn't use Unsafe.getLong() at all, but
239         the performance benefit on x86_64 is too great to ignore, so as a compromise, we enable the
240         optimization only on platforms that we specifically know to work.
241 
242         In the future, the use of Unsafe.getLong() should be replaced by ByteBuffer.getLong(), which
243         will have an efficient native implementation in JDK 9.
244 
245       */
246       final String arch = System.getProperty("os.arch");
247       if ("amd64".equals(arch) || "aarch64".equals(arch)) {
248         theGetter =
249             ByteOrder.nativeOrder().equals(ByteOrder.LITTLE_ENDIAN)
250                 ? UnsafeByteArray.UNSAFE_LITTLE_ENDIAN
251                 : UnsafeByteArray.UNSAFE_BIG_ENDIAN;
252       }
253     } catch (Throwable t) {
254       // ensure we really catch *everything*
255     }
256     byteArray = theGetter;
257   }
258 
259   /** Deter instantiation of this class. */
260   private LittleEndianByteArray() {}
261 }