1 /*
2 * Copyright (c) 2015, 2017 Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation. Oracle designates this
8 * particular file as subject to the "Classpath" exception as provided
9 * by Oracle in the LICENSE file that accompanied this code.
10 *
11 * This code is distributed in the hope that it will be useful, but WITHOUT
12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 * version 2 for more details (a copy is included in the LICENSE file that
15 * accompanied this code).
16 *
17 * You should have received a copy of the GNU General Public License version
18 * 2 along with this work; if not, write to the Free Software Foundation,
19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20 *
21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
22 * or visit www.oracle.com if you need additional information or have any
23 * questions.
24 */
25 package jdk.internal.util;
26
27 import jdk.internal.HotSpotIntrinsicCandidate;
28 import jdk.internal.misc.Unsafe;
29
30 /**
31 * Utility methods to find a mismatch between two primitive arrays.
32 *
33 * <p>Array equality and lexicographical comparison can be built on top of
34 * array mismatch functionality.
35 *
36 * <p>The mismatch method implementation, {@link #vectorizedMismatch}, leverages
37 * vector-based techniques to access and compare the contents of two arrays.
38 * The Java implementation uses {@code Unsafe.getLongUnaligned} to access the
39 * content of an array, thus access is supported on platforms that do not
40 * support unaligned access. For a byte[] array, 8 bytes (64 bits) can be
41 * accessed and compared as a unit rather than individually, which increases
42 * the performance when the method is compiled by the HotSpot VM. On supported
43 * platforms the mismatch implementation is intrinsified to leverage SIMD
44 * instructions. So for a byte[] array, 16 bytes (128 bits), 32 bytes
45 * (256 bits), and perhaps in the future even 64 bytes (512 bits), platform
46 * permitting, can be accessed and compared as a unit, which further increases
47 * the performance over the Java implementation.
48 *
49 * <p>None of the mismatch methods perform array bounds checks. It is the
50 * responsibility of the caller (direct or otherwise) to perform such checks
51 * before calling this method.
52 */
53 public class ArraysSupport {
54 static final Unsafe U = Unsafe.getUnsafe();
55
56 private static final boolean BIG_ENDIAN = U.isBigEndian();
57
58 public static final int LOG2_ARRAY_BOOLEAN_INDEX_SCALE = exactLog2(Unsafe.ARRAY_BOOLEAN_INDEX_SCALE);
59 public static final int LOG2_ARRAY_BYTE_INDEX_SCALE = exactLog2(Unsafe.ARRAY_BYTE_INDEX_SCALE);
60 public static final int LOG2_ARRAY_CHAR_INDEX_SCALE = exactLog2(Unsafe.ARRAY_CHAR_INDEX_SCALE);
61 public static final int LOG2_ARRAY_SHORT_INDEX_SCALE = exactLog2(Unsafe.ARRAY_SHORT_INDEX_SCALE);
62 public static final int LOG2_ARRAY_INT_INDEX_SCALE = exactLog2(Unsafe.ARRAY_INT_INDEX_SCALE);
63 public static final int LOG2_ARRAY_LONG_INDEX_SCALE = exactLog2(Unsafe.ARRAY_LONG_INDEX_SCALE);
64 public static final int LOG2_ARRAY_FLOAT_INDEX_SCALE = exactLog2(Unsafe.ARRAY_FLOAT_INDEX_SCALE);
65 public static final int LOG2_ARRAY_DOUBLE_INDEX_SCALE = exactLog2(Unsafe.ARRAY_DOUBLE_INDEX_SCALE);
66
67 private static final int LOG2_BYTE_BIT_SIZE = exactLog2(Byte.SIZE);
68
69 private static int exactLog2(int scale) {
70 if ((scale & (scale - 1)) != 0)
71 throw new Error("data type scale not a power of two");
72 return Integer.numberOfTrailingZeros(scale);
73 }
74
75 private ArraysSupport() {}
76
77 /**
78 * Find the relative index of the first mismatching pair of elements in two
79 * primitive arrays of the same component type. Pairs of elements will be
80 * tested in order relative to given offsets into both arrays.
81 *
82 * <p>This method does not perform type checks or bounds checks. It is the
83 * responsibility of the caller to perform such checks before calling this
84 * method.
85 *
86 * <p>The given offsets, in bytes, need not be aligned according to the
87 * given log<sub>2</sub> size the array elements. More specifically, an
88 * offset modulus the size need not be zero.
89 *
90 * @param a the first array to be tested for mismatch, or {@code null} for
91 * direct memory access
92 * @param aOffset the relative offset, in bytes, from the base address of
93 * the first array to test from, otherwise if the first array is
94 * {@code null}, an absolute address pointing to the first element to test.
95 * @param b the second array to be tested for mismatch, or {@code null} for
96 * direct memory access
97 * @param bOffset the relative offset, in bytes, from the base address of
98 * the second array to test from, otherwise if the second array is
99 * {@code null}, an absolute address pointing to the first element to test.
100 * @param length the number of array elements to test
101 * @param log2ArrayIndexScale log<sub>2</sub> of the array index scale, that
102 * corresponds to the size, in bytes, of an array element.
103 * @return if a mismatch is found a relative index, between 0 (inclusive)
104 * and {@code length} (exclusive), of the first mismatching pair of elements
105 * in the two arrays. Otherwise, if a mismatch is not found the bitwise
106 * compliment of the number of remaining pairs of elements to be checked in
107 * the tail of the two arrays.
108 */
109 @HotSpotIntrinsicCandidate
110 public static int vectorizedMismatch(Object a, long aOffset,
111 Object b, long bOffset,
112 int length,
113 int log2ArrayIndexScale) {
114 // assert a.getClass().isArray();
115 // assert b.getClass().isArray();
116 // assert 0 <= length <= sizeOf(a)
117 // assert 0 <= length <= sizeOf(b)
118 // assert 0 <= log2ArrayIndexScale <= 3
119
120 int log2ValuesPerWidth = LOG2_ARRAY_LONG_INDEX_SCALE - log2ArrayIndexScale;
121 int wi = 0;
122 for (; wi < length >> log2ValuesPerWidth; wi++) {
123 long bi = ((long) wi) << LOG2_ARRAY_LONG_INDEX_SCALE;
124 long av = U.getLongUnaligned(a, aOffset + bi);
125 long bv = U.getLongUnaligned(b, bOffset + bi);
126 if (av != bv) {
127 long x = av ^ bv;
128 int o = BIG_ENDIAN
129 ? Long.numberOfLeadingZeros(x) >> (LOG2_BYTE_BIT_SIZE + log2ArrayIndexScale)
130 : Long.numberOfTrailingZeros(x) >> (LOG2_BYTE_BIT_SIZE + log2ArrayIndexScale);
131 return (wi << log2ValuesPerWidth) + o;
132 }
133 }
134
135 // Calculate the tail of remaining elements to check
136 int tail = length - (wi << log2ValuesPerWidth);
137
138 if (log2ArrayIndexScale < LOG2_ARRAY_INT_INDEX_SCALE) {
139 int wordTail = 1 << (LOG2_ARRAY_INT_INDEX_SCALE - log2ArrayIndexScale);
140 // Handle 4 bytes or 2 chars in the tail using int width
141 if (tail >= wordTail) {
142 long bi = ((long) wi) << LOG2_ARRAY_LONG_INDEX_SCALE;
143 int av = U.getIntUnaligned(a, aOffset + bi);
144 int bv = U.getIntUnaligned(b, bOffset + bi);
145 if (av != bv) {
146 int x = av ^ bv;
147 int o = BIG_ENDIAN
148 ? Integer.numberOfLeadingZeros(x) >> (LOG2_BYTE_BIT_SIZE + log2ArrayIndexScale)
149 : Integer.numberOfTrailingZeros(x) >> (LOG2_BYTE_BIT_SIZE + log2ArrayIndexScale);
150 return (wi << log2ValuesPerWidth) + o;
151 }
152 tail -= wordTail;
153 }
154 return ~tail;
155 }
156 else {
157 return ~tail;
158 }
159 }
160
161 // Booleans
162 // Each boolean element takes up one byte
163
164 public static int mismatch(boolean[] a,
165 boolean[] b,
166 int length) {
167 int i = 0;
168 if (length > 7) {
169 i = vectorizedMismatch(
170 a, Unsafe.ARRAY_BOOLEAN_BASE_OFFSET,
171 b, Unsafe.ARRAY_BOOLEAN_BASE_OFFSET,
172 length, LOG2_ARRAY_BOOLEAN_INDEX_SCALE);
173 if (i >= 0)
174 return i;
175 i = length - ~i;
176 }
177 for (; i < length; i++) {
178 if (a[i] != b[i])
179 return i;
180 }
181 return -1;
182 }
183
184 public static int mismatch(boolean[] a, int aFromIndex,
185 boolean[] b, int bFromIndex,
186 int length) {
187 int i = 0;
188 if (length > 7) {
189 int aOffset = Unsafe.ARRAY_BOOLEAN_BASE_OFFSET + aFromIndex;
190 int bOffset = Unsafe.ARRAY_BOOLEAN_BASE_OFFSET + bFromIndex;
191 i = vectorizedMismatch(
192 a, aOffset,
193 b, bOffset,
194 length, LOG2_ARRAY_BOOLEAN_INDEX_SCALE);
195 if (i >= 0)
196 return i;
197 i = length - ~i;
198 }
199 for (; i < length; i++) {
200 if (a[aFromIndex + i] != b[bFromIndex + i])
201 return i;
202 }
203 return -1;
204 }
205
206
207 // Bytes
208
209 /**
210 * Find the index of a mismatch between two arrays.
211 *
212 * <p>This method does not perform bounds checks. It is the responsibility
213 * of the caller to perform such bounds checks before calling this method.
214 *
215 * @param a the first array to be tested for a mismatch
216 * @param b the second array to be tested for a mismatch
217 * @param length the number of bytes from each array to check
218 * @return the index of a mismatch between the two arrays, otherwise -1 if
219 * no mismatch. The index will be within the range of (inclusive) 0 to
220 * (exclusive) the smaller of the two array lengths.
221 */
222 public static int mismatch(byte[] a,
223 byte[] b,
224 int length) {
225 // ISSUE: defer to index receiving methods if performance is good
226 // assert length <= a.length
227 // assert length <= b.length
228
229 int i = 0;
230 if (length > 7) {
231 i = vectorizedMismatch(
232 a, Unsafe.ARRAY_BYTE_BASE_OFFSET,
233 b, Unsafe.ARRAY_BYTE_BASE_OFFSET,
234 length, LOG2_ARRAY_BYTE_INDEX_SCALE);
235 if (i >= 0)
236 return i;
237 // Align to tail
238 i = length - ~i;
239 // assert i >= 0 && i <= 7;
240 }
241 // Tail < 8 bytes
242 for (; i < length; i++) {
243 if (a[i] != b[i])
244 return i;
245 }
246 return -1;
247 }
248
249 /**
250 * Find the relative index of a mismatch between two arrays starting from
251 * given indexes.
252 *
253 * <p>This method does not perform bounds checks. It is the responsibility
254 * of the caller to perform such bounds checks before calling this method.
255 *
256 * @param a the first array to be tested for a mismatch
257 * @param aFromIndex the index of the first element (inclusive) in the first
258 * array to be compared
259 * @param b the second array to be tested for a mismatch
260 * @param bFromIndex the index of the first element (inclusive) in the
261 * second array to be compared
262 * @param length the number of bytes from each array to check
263 * @return the relative index of a mismatch between the two arrays,
264 * otherwise -1 if no mismatch. The index will be within the range of
265 * (inclusive) 0 to (exclusive) the smaller of the two array bounds.
266 */
267 public static int mismatch(byte[] a, int aFromIndex,
268 byte[] b, int bFromIndex,
269 int length) {
270 // assert 0 <= aFromIndex < a.length
271 // assert 0 <= aFromIndex + length <= a.length
272 // assert 0 <= bFromIndex < b.length
273 // assert 0 <= bFromIndex + length <= b.length
274 // assert length >= 0
275
276 int i = 0;
277 if (length > 7) {
278 int aOffset = Unsafe.ARRAY_BYTE_BASE_OFFSET + aFromIndex;
279 int bOffset = Unsafe.ARRAY_BYTE_BASE_OFFSET + bFromIndex;
280 i = vectorizedMismatch(
281 a, aOffset,
282 b, bOffset,
283 length, LOG2_ARRAY_BYTE_INDEX_SCALE);
284 if (i >= 0)
285 return i;
286 i = length - ~i;
287 }
288 for (; i < length; i++) {
289 if (a[aFromIndex + i] != b[bFromIndex + i])
290 return i;
291 }
292 return -1;
293 }
294
295
296 // Chars
297
298 public static int mismatch(char[] a,
299 char[] b,
300 int length) {
301 int i = 0;
302 if (length > 3) {
303 i = vectorizedMismatch(
304 a, Unsafe.ARRAY_CHAR_BASE_OFFSET,
305 b, Unsafe.ARRAY_CHAR_BASE_OFFSET,
306 length, LOG2_ARRAY_CHAR_INDEX_SCALE);
307 if (i >= 0)
308 return i;
309 i = length - ~i;
310 }
311 for (; i < length; i++) {
312 if (a[i] != b[i])
313 return i;
314 }
315 return -1;
316 }
317
318 public static int mismatch(char[] a, int aFromIndex,
319 char[] b, int bFromIndex,
320 int length) {
321 int i = 0;
322 if (length > 3) {
323 int aOffset = Unsafe.ARRAY_CHAR_BASE_OFFSET + (aFromIndex << LOG2_ARRAY_CHAR_INDEX_SCALE);
324 int bOffset = Unsafe.ARRAY_CHAR_BASE_OFFSET + (bFromIndex << LOG2_ARRAY_CHAR_INDEX_SCALE);
325 i = vectorizedMismatch(
326 a, aOffset,
327 b, bOffset,
328 length, LOG2_ARRAY_CHAR_INDEX_SCALE);
329 if (i >= 0)
330 return i;
331 i = length - ~i;
332 }
333 for (; i < length; i++) {
334 if (a[aFromIndex + i] != b[bFromIndex + i])
335 return i;
336 }
337 return -1;
338 }
339
340
341 // Shorts
342
343 public static int mismatch(short[] a,
344 short[] b,
345 int length) {
346 int i = 0;
347 if (length > 3) {
348 i = vectorizedMismatch(
349 a, Unsafe.ARRAY_SHORT_BASE_OFFSET,
350 b, Unsafe.ARRAY_SHORT_BASE_OFFSET,
351 length, LOG2_ARRAY_SHORT_INDEX_SCALE);
352 if (i >= 0)
353 return i;
354 i = length - ~i;
355 }
356 for (; i < length; i++) {
357 if (a[i] != b[i])
358 return i;
359 }
360 return -1;
361 }
362
363 public static int mismatch(short[] a, int aFromIndex,
364 short[] b, int bFromIndex,
365 int length) {
366 int i = 0;
367 if (length > 3) {
368 int aOffset = Unsafe.ARRAY_SHORT_BASE_OFFSET + (aFromIndex << LOG2_ARRAY_SHORT_INDEX_SCALE);
369 int bOffset = Unsafe.ARRAY_SHORT_BASE_OFFSET + (bFromIndex << LOG2_ARRAY_SHORT_INDEX_SCALE);
370 i = vectorizedMismatch(
371 a, aOffset,
372 b, bOffset,
373 length, LOG2_ARRAY_SHORT_INDEX_SCALE);
374 if (i >= 0)
375 return i;
376 i = length - ~i;
377 }
378 for (; i < length; i++) {
379 if (a[aFromIndex + i] != b[bFromIndex + i])
380 return i;
381 }
382 return -1;
383 }
384
385
386 // Ints
387
388 public static int mismatch(int[] a,
389 int[] b,
390 int length) {
391 int i = 0;
392 if (length > 1) {
393 i = vectorizedMismatch(
394 a, Unsafe.ARRAY_INT_BASE_OFFSET,
395 b, Unsafe.ARRAY_INT_BASE_OFFSET,
396 length, LOG2_ARRAY_INT_INDEX_SCALE);
397 if (i >= 0)
398 return i;
399 i = length - ~i;
400 }
401 for (; i < length; i++) {
402 if (a[i] != b[i])
403 return i;
404 }
405 return -1;
406 }
407
408 public static int mismatch(int[] a, int aFromIndex,
409 int[] b, int bFromIndex,
410 int length) {
411 int i = 0;
412 if (length > 1) {
413 int aOffset = Unsafe.ARRAY_INT_BASE_OFFSET + (aFromIndex << LOG2_ARRAY_INT_INDEX_SCALE);
414 int bOffset = Unsafe.ARRAY_INT_BASE_OFFSET + (bFromIndex << LOG2_ARRAY_INT_INDEX_SCALE);
415 i = vectorizedMismatch(
416 a, aOffset,
417 b, bOffset,
418 length, LOG2_ARRAY_INT_INDEX_SCALE);
419 if (i >= 0)
420 return i;
421 i = length - ~i;
422 }
423 for (; i < length; i++) {
424 if (a[aFromIndex + i] != b[bFromIndex + i])
425 return i;
426 }
427 return -1;
428 }
429
430
431 // Floats
432
433 public static int mismatch(float[] a,
434 float[] b,
435 int length) {
436 return mismatch(a, 0, b, 0, length);
437 }
438
439 public static int mismatch(float[] a, int aFromIndex,
440 float[] b, int bFromIndex,
441 int length) {
442 int i = 0;
443 if (length > 1) {
444 int aOffset = Unsafe.ARRAY_FLOAT_BASE_OFFSET + (aFromIndex << LOG2_ARRAY_FLOAT_INDEX_SCALE);
445 int bOffset = Unsafe.ARRAY_FLOAT_BASE_OFFSET + (bFromIndex << LOG2_ARRAY_FLOAT_INDEX_SCALE);
446 i = vectorizedMismatch(
447 a, aOffset,
448 b, bOffset,
449 length, LOG2_ARRAY_FLOAT_INDEX_SCALE);
450 // Mismatched
451 if (i >= 0) {
452 // Check if mismatch is not associated with two NaN values
453 if (!Float.isNaN(a[aFromIndex + i]) || !Float.isNaN(b[bFromIndex + i]))
454 return i;
455
456 // Mismatch on two different NaN values that are normalized to match
457 // Fall back to slow mechanism
458 // ISSUE: Consider looping over vectorizedMismatch adjusting ranges
459 // However, requires that returned value be relative to input ranges
460 i++;
461 }
462 // Matched
463 else {
464 i = length - ~i;
465 }
466 }
467 for (; i < length; i++) {
468 if (Float.floatToIntBits(a[aFromIndex + i]) != Float.floatToIntBits(b[bFromIndex + i]))
469 return i;
470 }
471 return -1;
472 }
473
474 // 64 bit sizes
475
476 // Long
477
478 public static int mismatch(long[] a,
479 long[] b,
480 int length) {
481 if (length == 0) {
482 return -1;
483 }
484 int i = vectorizedMismatch(
485 a, Unsafe.ARRAY_LONG_BASE_OFFSET,
486 b, Unsafe.ARRAY_LONG_BASE_OFFSET,
487 length, LOG2_ARRAY_LONG_INDEX_SCALE);
488 return i >= 0 ? i : -1;
489 }
490
491 public static int mismatch(long[] a, int aFromIndex,
492 long[] b, int bFromIndex,
493 int length) {
494 if (length == 0) {
495 return -1;
496 }
497 int aOffset = Unsafe.ARRAY_LONG_BASE_OFFSET + (aFromIndex << LOG2_ARRAY_LONG_INDEX_SCALE);
498 int bOffset = Unsafe.ARRAY_LONG_BASE_OFFSET + (bFromIndex << LOG2_ARRAY_LONG_INDEX_SCALE);
499 int i = vectorizedMismatch(
500 a, aOffset,
501 b, bOffset,
502 length, LOG2_ARRAY_LONG_INDEX_SCALE);
503 return i >= 0 ? i : -1;
504 }
505
506
507 // Double
508
509 public static int mismatch(double[] a,
510 double[] b,
511 int length) {
512 return mismatch(a, 0, b, 0, length);
513 }
514
515 public static int mismatch(double[] a, int aFromIndex,
516 double[] b, int bFromIndex,
517 int length) {
518 if (length == 0) {
519 return -1;
520 }
521 int aOffset = Unsafe.ARRAY_DOUBLE_BASE_OFFSET + (aFromIndex << LOG2_ARRAY_DOUBLE_INDEX_SCALE);
522 int bOffset = Unsafe.ARRAY_DOUBLE_BASE_OFFSET + (bFromIndex << LOG2_ARRAY_DOUBLE_INDEX_SCALE);
523 int i = vectorizedMismatch(
524 a, aOffset,
525 b, bOffset,
526 length, LOG2_ARRAY_DOUBLE_INDEX_SCALE);
527 if (i >= 0) {
528 // Check if mismatch is not associated with two NaN values
529 if (!Double.isNaN(a[aFromIndex + i]) || !Double.isNaN(b[bFromIndex + i]))
530 return i;
531
532 // Mismatch on two different NaN values that are normalized to match
533 // Fall back to slow mechanism
534 // ISSUE: Consider looping over vectorizedMismatch adjusting ranges
535 // However, requires that returned value be relative to input ranges
536 i++;
537 for (; i < length; i++) {
538 if (Double.doubleToLongBits(a[aFromIndex + i]) != Double.doubleToLongBits(b[bFromIndex + i]))
539 return i;
540 }
541 }
542
543 return -1;
544 }
545 }