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