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 // Android-changed: Android is little endian. 57 private static final boolean BIG_ENDIAN = false; 58 59 public static final int LOG2_ARRAY_BOOLEAN_INDEX_SCALE = exactLog2(Unsafe.ARRAY_BOOLEAN_INDEX_SCALE); 60 public static final int LOG2_ARRAY_BYTE_INDEX_SCALE = exactLog2(Unsafe.ARRAY_BYTE_INDEX_SCALE); 61 public static final int LOG2_ARRAY_CHAR_INDEX_SCALE = exactLog2(Unsafe.ARRAY_CHAR_INDEX_SCALE); 62 public static final int LOG2_ARRAY_SHORT_INDEX_SCALE = exactLog2(Unsafe.ARRAY_SHORT_INDEX_SCALE); 63 public static final int LOG2_ARRAY_INT_INDEX_SCALE = exactLog2(Unsafe.ARRAY_INT_INDEX_SCALE); 64 public static final int LOG2_ARRAY_LONG_INDEX_SCALE = exactLog2(Unsafe.ARRAY_LONG_INDEX_SCALE); 65 public static final int LOG2_ARRAY_FLOAT_INDEX_SCALE = exactLog2(Unsafe.ARRAY_FLOAT_INDEX_SCALE); 66 public static final int LOG2_ARRAY_DOUBLE_INDEX_SCALE = exactLog2(Unsafe.ARRAY_DOUBLE_INDEX_SCALE); 67 68 private static final int LOG2_BYTE_BIT_SIZE = exactLog2(Byte.SIZE); 69 exactLog2(int scale)70 private static int exactLog2(int scale) { 71 if ((scale & (scale - 1)) != 0) 72 throw new Error("data type scale not a power of two"); 73 return Integer.numberOfTrailingZeros(scale); 74 } 75 ArraysSupport()76 private ArraysSupport() {} 77 78 /** 79 * Find the relative index of the first mismatching pair of elements in two 80 * primitive arrays of the same component type. Pairs of elements will be 81 * tested in order relative to given offsets into both arrays. 82 * 83 * <p>This method does not perform type checks or bounds checks. It is the 84 * responsibility of the caller to perform such checks before calling this 85 * method. 86 * 87 * <p>The given offsets, in bytes, need not be aligned according to the 88 * given log<sub>2</sub> size the array elements. More specifically, an 89 * offset modulus the size need not be zero. 90 * 91 * @param a the first array to be tested for mismatch, or {@code null} for 92 * direct memory access 93 * @param aOffset the relative offset, in bytes, from the base address of 94 * the first array to test from, otherwise if the first array is 95 * {@code null}, an absolute address pointing to the first element to test. 96 * @param b the second array to be tested for mismatch, or {@code null} for 97 * direct memory access 98 * @param bOffset the relative offset, in bytes, from the base address of 99 * the second array to test from, otherwise if the second array is 100 * {@code null}, an absolute address pointing to the first element to test. 101 * @param length the number of array elements to test 102 * @param log2ArrayIndexScale log<sub>2</sub> of the array index scale, that 103 * corresponds to the size, in bytes, of an array element. 104 * @return if a mismatch is found a relative index, between 0 (inclusive) 105 * and {@code length} (exclusive), of the first mismatching pair of elements 106 * in the two arrays. Otherwise, if a mismatch is not found the bitwise 107 * compliment of the number of remaining pairs of elements to be checked in 108 * the tail of the two arrays. 109 */ 110 @HotSpotIntrinsicCandidate vectorizedMismatch(Object a, long aOffset, Object b, long bOffset, int length, int log2ArrayIndexScale)111 public static int vectorizedMismatch(Object a, long aOffset, 112 Object b, long bOffset, 113 int length, 114 int log2ArrayIndexScale) { 115 // assert a.getClass().isArray(); 116 // assert b.getClass().isArray(); 117 // assert 0 <= length <= sizeOf(a) 118 // assert 0 <= length <= sizeOf(b) 119 // assert 0 <= log2ArrayIndexScale <= 3 120 121 int log2ValuesPerWidth = LOG2_ARRAY_LONG_INDEX_SCALE - log2ArrayIndexScale; 122 int wi = 0; 123 for (; wi < length >> log2ValuesPerWidth; wi++) { 124 long bi = ((long) wi) << LOG2_ARRAY_LONG_INDEX_SCALE; 125 long av = U.getLongUnaligned(a, aOffset + bi); 126 long bv = U.getLongUnaligned(b, bOffset + bi); 127 if (av != bv) { 128 long x = av ^ bv; 129 int o = BIG_ENDIAN 130 ? Long.numberOfLeadingZeros(x) >> (LOG2_BYTE_BIT_SIZE + log2ArrayIndexScale) 131 : Long.numberOfTrailingZeros(x) >> (LOG2_BYTE_BIT_SIZE + log2ArrayIndexScale); 132 return (wi << log2ValuesPerWidth) + o; 133 } 134 } 135 136 // Calculate the tail of remaining elements to check 137 int tail = length - (wi << log2ValuesPerWidth); 138 139 if (log2ArrayIndexScale < LOG2_ARRAY_INT_INDEX_SCALE) { 140 int wordTail = 1 << (LOG2_ARRAY_INT_INDEX_SCALE - log2ArrayIndexScale); 141 // Handle 4 bytes or 2 chars in the tail using int width 142 if (tail >= wordTail) { 143 long bi = ((long) wi) << LOG2_ARRAY_LONG_INDEX_SCALE; 144 int av = U.getIntUnaligned(a, aOffset + bi); 145 int bv = U.getIntUnaligned(b, bOffset + bi); 146 if (av != bv) { 147 int x = av ^ bv; 148 int o = BIG_ENDIAN 149 ? Integer.numberOfLeadingZeros(x) >> (LOG2_BYTE_BIT_SIZE + log2ArrayIndexScale) 150 : Integer.numberOfTrailingZeros(x) >> (LOG2_BYTE_BIT_SIZE + log2ArrayIndexScale); 151 return (wi << log2ValuesPerWidth) + o; 152 } 153 tail -= wordTail; 154 } 155 return ~tail; 156 } 157 else { 158 return ~tail; 159 } 160 } 161 162 // Booleans 163 // Each boolean element takes up one byte 164 mismatch(boolean[] a, boolean[] b, int length)165 public static int mismatch(boolean[] a, 166 boolean[] b, 167 int length) { 168 int i = 0; 169 if (length > 7) { 170 if (a[0] != b[0]) 171 return 0; 172 i = vectorizedMismatch( 173 a, Unsafe.ARRAY_BOOLEAN_BASE_OFFSET, 174 b, Unsafe.ARRAY_BOOLEAN_BASE_OFFSET, 175 length, LOG2_ARRAY_BOOLEAN_INDEX_SCALE); 176 if (i >= 0) 177 return i; 178 i = length - ~i; 179 } 180 for (; i < length; i++) { 181 if (a[i] != b[i]) 182 return i; 183 } 184 return -1; 185 } 186 mismatch(boolean[] a, int aFromIndex, boolean[] b, int bFromIndex, int length)187 public static int mismatch(boolean[] a, int aFromIndex, 188 boolean[] b, int bFromIndex, 189 int length) { 190 int i = 0; 191 if (length > 7) { 192 if (a[aFromIndex] != b[bFromIndex]) 193 return 0; 194 int aOffset = Unsafe.ARRAY_BOOLEAN_BASE_OFFSET + aFromIndex; 195 int bOffset = Unsafe.ARRAY_BOOLEAN_BASE_OFFSET + bFromIndex; 196 i = vectorizedMismatch( 197 a, aOffset, 198 b, bOffset, 199 length, LOG2_ARRAY_BOOLEAN_INDEX_SCALE); 200 if (i >= 0) 201 return i; 202 i = length - ~i; 203 } 204 for (; i < length; i++) { 205 if (a[aFromIndex + i] != b[bFromIndex + i]) 206 return i; 207 } 208 return -1; 209 } 210 211 212 // Bytes 213 214 /** 215 * Find the index of a mismatch between two arrays. 216 * 217 * <p>This method does not perform bounds checks. It is the responsibility 218 * of the caller to perform such bounds checks before calling this method. 219 * 220 * @param a the first array to be tested for a mismatch 221 * @param b the second array to be tested for a mismatch 222 * @param length the number of bytes from each array to check 223 * @return the index of a mismatch between the two arrays, otherwise -1 if 224 * no mismatch. The index will be within the range of (inclusive) 0 to 225 * (exclusive) the smaller of the two array lengths. 226 */ mismatch(byte[] a, byte[] b, int length)227 public static int mismatch(byte[] a, 228 byte[] b, 229 int length) { 230 // ISSUE: defer to index receiving methods if performance is good 231 // assert length <= a.length 232 // assert length <= b.length 233 234 int i = 0; 235 if (length > 7) { 236 if (a[0] != b[0]) 237 return 0; 238 i = vectorizedMismatch( 239 a, Unsafe.ARRAY_BYTE_BASE_OFFSET, 240 b, Unsafe.ARRAY_BYTE_BASE_OFFSET, 241 length, LOG2_ARRAY_BYTE_INDEX_SCALE); 242 if (i >= 0) 243 return i; 244 // Align to tail 245 i = length - ~i; 246 // assert i >= 0 && i <= 7; 247 } 248 // Tail < 8 bytes 249 for (; i < length; i++) { 250 if (a[i] != b[i]) 251 return i; 252 } 253 return -1; 254 } 255 256 /** 257 * Find the relative index of a mismatch between two arrays starting from 258 * given indexes. 259 * 260 * <p>This method does not perform bounds checks. It is the responsibility 261 * of the caller to perform such bounds checks before calling this method. 262 * 263 * @param a the first array to be tested for a mismatch 264 * @param aFromIndex the index of the first element (inclusive) in the first 265 * array to be compared 266 * @param b the second array to be tested for a mismatch 267 * @param bFromIndex the index of the first element (inclusive) in the 268 * second array to be compared 269 * @param length the number of bytes from each array to check 270 * @return the relative index of a mismatch between the two arrays, 271 * otherwise -1 if no mismatch. The index will be within the range of 272 * (inclusive) 0 to (exclusive) the smaller of the two array bounds. 273 */ mismatch(byte[] a, int aFromIndex, byte[] b, int bFromIndex, int length)274 public static int mismatch(byte[] a, int aFromIndex, 275 byte[] b, int bFromIndex, 276 int length) { 277 // assert 0 <= aFromIndex < a.length 278 // assert 0 <= aFromIndex + length <= a.length 279 // assert 0 <= bFromIndex < b.length 280 // assert 0 <= bFromIndex + length <= b.length 281 // assert length >= 0 282 283 int i = 0; 284 if (length > 7) { 285 if (a[aFromIndex] != b[bFromIndex]) 286 return 0; 287 int aOffset = Unsafe.ARRAY_BYTE_BASE_OFFSET + aFromIndex; 288 int bOffset = Unsafe.ARRAY_BYTE_BASE_OFFSET + bFromIndex; 289 i = vectorizedMismatch( 290 a, aOffset, 291 b, bOffset, 292 length, LOG2_ARRAY_BYTE_INDEX_SCALE); 293 if (i >= 0) 294 return i; 295 i = length - ~i; 296 } 297 for (; i < length; i++) { 298 if (a[aFromIndex + i] != b[bFromIndex + i]) 299 return i; 300 } 301 return -1; 302 } 303 304 305 // Chars 306 mismatch(char[] a, char[] b, int length)307 public static int mismatch(char[] a, 308 char[] b, 309 int length) { 310 int i = 0; 311 if (length > 3) { 312 if (a[0] != b[0]) 313 return 0; 314 i = vectorizedMismatch( 315 a, Unsafe.ARRAY_CHAR_BASE_OFFSET, 316 b, Unsafe.ARRAY_CHAR_BASE_OFFSET, 317 length, LOG2_ARRAY_CHAR_INDEX_SCALE); 318 if (i >= 0) 319 return i; 320 i = length - ~i; 321 } 322 for (; i < length; i++) { 323 if (a[i] != b[i]) 324 return i; 325 } 326 return -1; 327 } 328 mismatch(char[] a, int aFromIndex, char[] b, int bFromIndex, int length)329 public static int mismatch(char[] a, int aFromIndex, 330 char[] b, int bFromIndex, 331 int length) { 332 int i = 0; 333 if (length > 3) { 334 if (a[aFromIndex] != b[bFromIndex]) 335 return 0; 336 int aOffset = Unsafe.ARRAY_CHAR_BASE_OFFSET + (aFromIndex << LOG2_ARRAY_CHAR_INDEX_SCALE); 337 int bOffset = Unsafe.ARRAY_CHAR_BASE_OFFSET + (bFromIndex << LOG2_ARRAY_CHAR_INDEX_SCALE); 338 i = vectorizedMismatch( 339 a, aOffset, 340 b, bOffset, 341 length, LOG2_ARRAY_CHAR_INDEX_SCALE); 342 if (i >= 0) 343 return i; 344 i = length - ~i; 345 } 346 for (; i < length; i++) { 347 if (a[aFromIndex + i] != b[bFromIndex + i]) 348 return i; 349 } 350 return -1; 351 } 352 353 354 // Shorts 355 mismatch(short[] a, short[] b, int length)356 public static int mismatch(short[] a, 357 short[] b, 358 int length) { 359 int i = 0; 360 if (length > 3) { 361 if (a[0] != b[0]) 362 return 0; 363 i = vectorizedMismatch( 364 a, Unsafe.ARRAY_SHORT_BASE_OFFSET, 365 b, Unsafe.ARRAY_SHORT_BASE_OFFSET, 366 length, LOG2_ARRAY_SHORT_INDEX_SCALE); 367 if (i >= 0) 368 return i; 369 i = length - ~i; 370 } 371 for (; i < length; i++) { 372 if (a[i] != b[i]) 373 return i; 374 } 375 return -1; 376 } 377 mismatch(short[] a, int aFromIndex, short[] b, int bFromIndex, int length)378 public static int mismatch(short[] a, int aFromIndex, 379 short[] b, int bFromIndex, 380 int length) { 381 int i = 0; 382 if (length > 3) { 383 if (a[aFromIndex] != b[bFromIndex]) 384 return 0; 385 int aOffset = Unsafe.ARRAY_SHORT_BASE_OFFSET + (aFromIndex << LOG2_ARRAY_SHORT_INDEX_SCALE); 386 int bOffset = Unsafe.ARRAY_SHORT_BASE_OFFSET + (bFromIndex << LOG2_ARRAY_SHORT_INDEX_SCALE); 387 i = vectorizedMismatch( 388 a, aOffset, 389 b, bOffset, 390 length, LOG2_ARRAY_SHORT_INDEX_SCALE); 391 if (i >= 0) 392 return i; 393 i = length - ~i; 394 } 395 for (; i < length; i++) { 396 if (a[aFromIndex + i] != b[bFromIndex + i]) 397 return i; 398 } 399 return -1; 400 } 401 402 403 // Ints 404 mismatch(int[] a, int[] b, int length)405 public static int mismatch(int[] a, 406 int[] b, 407 int length) { 408 int i = 0; 409 if (length > 1) { 410 if (a[0] != b[0]) 411 return 0; 412 i = vectorizedMismatch( 413 a, Unsafe.ARRAY_INT_BASE_OFFSET, 414 b, Unsafe.ARRAY_INT_BASE_OFFSET, 415 length, LOG2_ARRAY_INT_INDEX_SCALE); 416 if (i >= 0) 417 return i; 418 i = length - ~i; 419 } 420 for (; i < length; i++) { 421 if (a[i] != b[i]) 422 return i; 423 } 424 return -1; 425 } 426 mismatch(int[] a, int aFromIndex, int[] b, int bFromIndex, int length)427 public static int mismatch(int[] a, int aFromIndex, 428 int[] b, int bFromIndex, 429 int length) { 430 int i = 0; 431 if (length > 1) { 432 if (a[aFromIndex] != b[bFromIndex]) 433 return 0; 434 int aOffset = Unsafe.ARRAY_INT_BASE_OFFSET + (aFromIndex << LOG2_ARRAY_INT_INDEX_SCALE); 435 int bOffset = Unsafe.ARRAY_INT_BASE_OFFSET + (bFromIndex << LOG2_ARRAY_INT_INDEX_SCALE); 436 i = vectorizedMismatch( 437 a, aOffset, 438 b, bOffset, 439 length, LOG2_ARRAY_INT_INDEX_SCALE); 440 if (i >= 0) 441 return i; 442 i = length - ~i; 443 } 444 for (; i < length; i++) { 445 if (a[aFromIndex + i] != b[bFromIndex + i]) 446 return i; 447 } 448 return -1; 449 } 450 451 452 // Floats 453 mismatch(float[] a, float[] b, int length)454 public static int mismatch(float[] a, 455 float[] b, 456 int length) { 457 return mismatch(a, 0, b, 0, length); 458 } 459 mismatch(float[] a, int aFromIndex, float[] b, int bFromIndex, int length)460 public static int mismatch(float[] a, int aFromIndex, 461 float[] b, int bFromIndex, 462 int length) { 463 int i = 0; 464 if (length > 1) { 465 if (Float.floatToRawIntBits(a[aFromIndex]) == Float.floatToRawIntBits(b[bFromIndex])) { 466 int aOffset = Unsafe.ARRAY_FLOAT_BASE_OFFSET + (aFromIndex << LOG2_ARRAY_FLOAT_INDEX_SCALE); 467 int bOffset = Unsafe.ARRAY_FLOAT_BASE_OFFSET + (bFromIndex << LOG2_ARRAY_FLOAT_INDEX_SCALE); 468 i = vectorizedMismatch( 469 a, aOffset, 470 b, bOffset, 471 length, LOG2_ARRAY_FLOAT_INDEX_SCALE); 472 } 473 // Mismatched 474 if (i >= 0) { 475 // Check if mismatch is not associated with two NaN values 476 if (!Float.isNaN(a[aFromIndex + i]) || !Float.isNaN(b[bFromIndex + i])) 477 return i; 478 479 // Mismatch on two different NaN values that are normalized to match 480 // Fall back to slow mechanism 481 // ISSUE: Consider looping over vectorizedMismatch adjusting ranges 482 // However, requires that returned value be relative to input ranges 483 i++; 484 } 485 // Matched 486 else { 487 i = length - ~i; 488 } 489 } 490 for (; i < length; i++) { 491 if (Float.floatToIntBits(a[aFromIndex + i]) != Float.floatToIntBits(b[bFromIndex + i])) 492 return i; 493 } 494 return -1; 495 } 496 497 // 64 bit sizes 498 499 // Long 500 mismatch(long[] a, long[] b, int length)501 public static int mismatch(long[] a, 502 long[] b, 503 int length) { 504 if (length == 0) { 505 return -1; 506 } 507 if (a[0] != b[0]) 508 return 0; 509 int i = vectorizedMismatch( 510 a, Unsafe.ARRAY_LONG_BASE_OFFSET, 511 b, Unsafe.ARRAY_LONG_BASE_OFFSET, 512 length, LOG2_ARRAY_LONG_INDEX_SCALE); 513 return i >= 0 ? i : -1; 514 } 515 mismatch(long[] a, int aFromIndex, long[] b, int bFromIndex, int length)516 public static int mismatch(long[] a, int aFromIndex, 517 long[] b, int bFromIndex, 518 int length) { 519 if (length == 0) { 520 return -1; 521 } 522 if (a[aFromIndex] != b[bFromIndex]) 523 return 0; 524 int aOffset = Unsafe.ARRAY_LONG_BASE_OFFSET + (aFromIndex << LOG2_ARRAY_LONG_INDEX_SCALE); 525 int bOffset = Unsafe.ARRAY_LONG_BASE_OFFSET + (bFromIndex << LOG2_ARRAY_LONG_INDEX_SCALE); 526 int i = vectorizedMismatch( 527 a, aOffset, 528 b, bOffset, 529 length, LOG2_ARRAY_LONG_INDEX_SCALE); 530 return i >= 0 ? i : -1; 531 } 532 533 534 // Double 535 mismatch(double[] a, double[] b, int length)536 public static int mismatch(double[] a, 537 double[] b, 538 int length) { 539 return mismatch(a, 0, b, 0, length); 540 } 541 mismatch(double[] a, int aFromIndex, double[] b, int bFromIndex, int length)542 public static int mismatch(double[] a, int aFromIndex, 543 double[] b, int bFromIndex, 544 int length) { 545 if (length == 0) { 546 return -1; 547 } 548 int i = 0; 549 if (Double.doubleToRawLongBits(a[aFromIndex]) == Double.doubleToRawLongBits(b[bFromIndex])) { 550 int aOffset = Unsafe.ARRAY_DOUBLE_BASE_OFFSET + (aFromIndex << LOG2_ARRAY_DOUBLE_INDEX_SCALE); 551 int bOffset = Unsafe.ARRAY_DOUBLE_BASE_OFFSET + (bFromIndex << LOG2_ARRAY_DOUBLE_INDEX_SCALE); 552 i = vectorizedMismatch( 553 a, aOffset, 554 b, bOffset, 555 length, LOG2_ARRAY_DOUBLE_INDEX_SCALE); 556 } 557 if (i >= 0) { 558 // Check if mismatch is not associated with two NaN values 559 if (!Double.isNaN(a[aFromIndex + i]) || !Double.isNaN(b[bFromIndex + i])) 560 return i; 561 562 // Mismatch on two different NaN values that are normalized to match 563 // Fall back to slow mechanism 564 // ISSUE: Consider looping over vectorizedMismatch adjusting ranges 565 // However, requires that returned value be relative to input ranges 566 i++; 567 for (; i < length; i++) { 568 if (Double.doubleToLongBits(a[aFromIndex + i]) != Double.doubleToLongBits(b[bFromIndex + i])) 569 return i; 570 } 571 } 572 573 return -1; 574 } 575 } 576