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 if (a[0] != b[0]) 170 return 0; 171 i = vectorizedMismatch( 172 a, Unsafe.ARRAY_BOOLEAN_BASE_OFFSET, 173 b, Unsafe.ARRAY_BOOLEAN_BASE_OFFSET, 174 length, LOG2_ARRAY_BOOLEAN_INDEX_SCALE); 175 if (i >= 0) 176 return i; 177 i = length - ~i; 178 } 179 for (; i < length; i++) { 180 if (a[i] != b[i]) 181 return i; 182 } 183 return -1; 184 } 185 186 public static int mismatch(boolean[] a, int aFromIndex, 187 boolean[] b, int bFromIndex, 188 int length) { 189 int i = 0; 190 if (length > 7) { 191 if (a[aFromIndex] != b[bFromIndex]) 192 return 0; 193 int aOffset = Unsafe.ARRAY_BOOLEAN_BASE_OFFSET + aFromIndex; 194 int bOffset = Unsafe.ARRAY_BOOLEAN_BASE_OFFSET + bFromIndex; 195 i = vectorizedMismatch( 196 a, aOffset, 197 b, bOffset, 198 length, LOG2_ARRAY_BOOLEAN_INDEX_SCALE); 199 if (i >= 0) 200 return i; 201 i = length - ~i; 202 } 203 for (; i < length; i++) { 204 if (a[aFromIndex + i] != b[bFromIndex + i]) 205 return i; 206 } 207 return -1; 208 } 209 210 211 // Bytes 212 213 /** 214 * Find the index of a mismatch between two arrays. 215 * 216 * <p>This method does not perform bounds checks. It is the responsibility 217 * of the caller to perform such bounds checks before calling this method. 218 * 219 * @param a the first array to be tested for a mismatch 220 * @param b the second array to be tested for a mismatch 221 * @param length the number of bytes from each array to check 222 * @return the index of a mismatch between the two arrays, otherwise -1 if 223 * no mismatch. The index will be within the range of (inclusive) 0 to 224 * (exclusive) the smaller of the two array lengths. 225 */ 226 public static int mismatch(byte[] a, 227 byte[] b, 228 int length) { 229 // ISSUE: defer to index receiving methods if performance is good 230 // assert length <= a.length 231 // assert length <= b.length 232 233 int i = 0; 234 if (length > 7) { 235 if (a[0] != b[0]) 236 return 0; 237 i = vectorizedMismatch( 238 a, Unsafe.ARRAY_BYTE_BASE_OFFSET, 239 b, Unsafe.ARRAY_BYTE_BASE_OFFSET, 240 length, LOG2_ARRAY_BYTE_INDEX_SCALE); 241 if (i >= 0) 242 return i; 243 // Align to tail 244 i = length - ~i; 245 // assert i >= 0 && i <= 7; 246 } 247 // Tail < 8 bytes 248 for (; i < length; i++) { 249 if (a[i] != b[i]) 250 return i; 251 } 252 return -1; 253 } 254 255 /** 256 * Find the relative index of a mismatch between two arrays starting from 257 * given indexes. 258 * 259 * <p>This method does not perform bounds checks. It is the responsibility 260 * of the caller to perform such bounds checks before calling this method. 261 * 262 * @param a the first array to be tested for a mismatch 263 * @param aFromIndex the index of the first element (inclusive) in the first 264 * array to be compared 265 * @param b the second array to be tested for a mismatch 266 * @param bFromIndex the index of the first element (inclusive) in the 267 * second array to be compared 268 * @param length the number of bytes from each array to check 269 * @return the relative index of a mismatch between the two arrays, 270 * otherwise -1 if no mismatch. The index will be within the range of 271 * (inclusive) 0 to (exclusive) the smaller of the two array bounds. 272 */ 273 public static int mismatch(byte[] a, int aFromIndex, 274 byte[] b, int bFromIndex, 275 int length) { 276 // assert 0 <= aFromIndex < a.length 277 // assert 0 <= aFromIndex + length <= a.length 278 // assert 0 <= bFromIndex < b.length 279 // assert 0 <= bFromIndex + length <= b.length 280 // assert length >= 0 281 282 int i = 0; 283 if (length > 7) { 284 if (a[aFromIndex] != b[bFromIndex]) 285 return 0; 286 int aOffset = Unsafe.ARRAY_BYTE_BASE_OFFSET + aFromIndex; 287 int bOffset = Unsafe.ARRAY_BYTE_BASE_OFFSET + bFromIndex; 288 i = vectorizedMismatch( 289 a, aOffset, 290 b, bOffset, 291 length, LOG2_ARRAY_BYTE_INDEX_SCALE); 292 if (i >= 0) 293 return i; 294 i = length - ~i; 295 } 296 for (; i < length; i++) { 297 if (a[aFromIndex + i] != b[bFromIndex + i]) 298 return i; 299 } 300 return -1; 301 } 302 303 304 // Chars 305 306 public static int mismatch(char[] a, 307 char[] b, 308 int length) { 309 int i = 0; 310 if (length > 3) { 311 if (a[0] != b[0]) 312 return 0; 313 i = vectorizedMismatch( 314 a, Unsafe.ARRAY_CHAR_BASE_OFFSET, 315 b, Unsafe.ARRAY_CHAR_BASE_OFFSET, 316 length, LOG2_ARRAY_CHAR_INDEX_SCALE); 317 if (i >= 0) 318 return i; 319 i = length - ~i; 320 } 321 for (; i < length; i++) { 322 if (a[i] != b[i]) 323 return i; 324 } 325 return -1; 326 } 327 328 public static int mismatch(char[] a, int aFromIndex, 329 char[] b, int bFromIndex, 330 int length) { 331 int i = 0; 332 if (length > 3) { 333 if (a[aFromIndex] != b[bFromIndex]) 334 return 0; 335 int aOffset = Unsafe.ARRAY_CHAR_BASE_OFFSET + (aFromIndex << LOG2_ARRAY_CHAR_INDEX_SCALE); 336 int bOffset = Unsafe.ARRAY_CHAR_BASE_OFFSET + (bFromIndex << LOG2_ARRAY_CHAR_INDEX_SCALE); 337 i = vectorizedMismatch( 338 a, aOffset, 339 b, bOffset, 340 length, LOG2_ARRAY_CHAR_INDEX_SCALE); 341 if (i >= 0) 342 return i; 343 i = length - ~i; 344 } 345 for (; i < length; i++) { 346 if (a[aFromIndex + i] != b[bFromIndex + i]) 347 return i; 348 } 349 return -1; 350 } 351 352 353 // Shorts 354 355 public static int mismatch(short[] a, 356 short[] b, 357 int length) { 358 int i = 0; 359 if (length > 3) { 360 if (a[0] != b[0]) 361 return 0; 362 i = vectorizedMismatch( 363 a, Unsafe.ARRAY_SHORT_BASE_OFFSET, 364 b, Unsafe.ARRAY_SHORT_BASE_OFFSET, 365 length, LOG2_ARRAY_SHORT_INDEX_SCALE); 366 if (i >= 0) 367 return i; 368 i = length - ~i; 369 } 370 for (; i < length; i++) { 371 if (a[i] != b[i]) 372 return i; 373 } 374 return -1; 375 } 376 377 public static int mismatch(short[] a, int aFromIndex, 378 short[] b, int bFromIndex, 379 int length) { 380 int i = 0; 381 if (length > 3) { 382 if (a[aFromIndex] != b[bFromIndex]) 383 return 0; 384 int aOffset = Unsafe.ARRAY_SHORT_BASE_OFFSET + (aFromIndex << LOG2_ARRAY_SHORT_INDEX_SCALE); 385 int bOffset = Unsafe.ARRAY_SHORT_BASE_OFFSET + (bFromIndex << LOG2_ARRAY_SHORT_INDEX_SCALE); 386 i = vectorizedMismatch( 387 a, aOffset, 388 b, bOffset, 389 length, LOG2_ARRAY_SHORT_INDEX_SCALE); 390 if (i >= 0) 391 return i; 392 i = length - ~i; 393 } 394 for (; i < length; i++) { 395 if (a[aFromIndex + i] != b[bFromIndex + i]) 396 return i; 397 } 398 return -1; 399 } 400 401 402 // Ints 403 404 public static int mismatch(int[] a, 405 int[] b, 406 int length) { 407 int i = 0; 408 if (length > 1) { 409 if (a[0] != b[0]) 410 return 0; 411 i = vectorizedMismatch( 412 a, Unsafe.ARRAY_INT_BASE_OFFSET, 413 b, Unsafe.ARRAY_INT_BASE_OFFSET, 414 length, LOG2_ARRAY_INT_INDEX_SCALE); 415 if (i >= 0) 416 return i; 417 i = length - ~i; 418 } 419 for (; i < length; i++) { 420 if (a[i] != b[i]) 421 return i; 422 } 423 return -1; 424 } 425 426 public static int mismatch(int[] a, int aFromIndex, 427 int[] b, int bFromIndex, 428 int length) { 429 int i = 0; 430 if (length > 1) { 431 if (a[aFromIndex] != b[bFromIndex]) 432 return 0; 433 int aOffset = Unsafe.ARRAY_INT_BASE_OFFSET + (aFromIndex << LOG2_ARRAY_INT_INDEX_SCALE); 434 int bOffset = Unsafe.ARRAY_INT_BASE_OFFSET + (bFromIndex << LOG2_ARRAY_INT_INDEX_SCALE); 435 i = vectorizedMismatch( 436 a, aOffset, 437 b, bOffset, 438 length, LOG2_ARRAY_INT_INDEX_SCALE); 439 if (i >= 0) 440 return i; 441 i = length - ~i; 442 } 443 for (; i < length; i++) { 444 if (a[aFromIndex + i] != b[bFromIndex + i]) 445 return i; 446 } 447 return -1; 448 } 449 450 451 // Floats 452 453 public static int mismatch(float[] a, 454 float[] b, 455 int length) { 456 return mismatch(a, 0, b, 0, length); 457 } 458 459 public static int mismatch(float[] a, int aFromIndex, 460 float[] b, int bFromIndex, 461 int length) { 462 int i = 0; 463 if (length > 1) { 464 if (Float.floatToRawIntBits(a[aFromIndex]) == Float.floatToRawIntBits(b[bFromIndex])) { 465 int aOffset = Unsafe.ARRAY_FLOAT_BASE_OFFSET + (aFromIndex << LOG2_ARRAY_FLOAT_INDEX_SCALE); 466 int bOffset = Unsafe.ARRAY_FLOAT_BASE_OFFSET + (bFromIndex << LOG2_ARRAY_FLOAT_INDEX_SCALE); 467 i = vectorizedMismatch( 468 a, aOffset, 469 b, bOffset, 470 length, LOG2_ARRAY_FLOAT_INDEX_SCALE); 471 } 472 // Mismatched 473 if (i >= 0) { 474 // Check if mismatch is not associated with two NaN values 475 if (!Float.isNaN(a[aFromIndex + i]) || !Float.isNaN(b[bFromIndex + i])) 476 return i; 477 478 // Mismatch on two different NaN values that are normalized to match 479 // Fall back to slow mechanism 480 // ISSUE: Consider looping over vectorizedMismatch adjusting ranges 481 // However, requires that returned value be relative to input ranges 482 i++; 483 } 484 // Matched 485 else { 486 i = length - ~i; 487 } 488 } 489 for (; i < length; i++) { 490 if (Float.floatToIntBits(a[aFromIndex + i]) != Float.floatToIntBits(b[bFromIndex + i])) 491 return i; 492 } 493 return -1; 494 } 495 496 // 64 bit sizes 497 498 // Long 499 500 public static int mismatch(long[] a, 501 long[] b, 502 int length) { 503 if (length == 0) { 504 return -1; 505 } 506 if (a[0] != b[0]) 507 return 0; 508 int i = vectorizedMismatch( 509 a, Unsafe.ARRAY_LONG_BASE_OFFSET, 510 b, Unsafe.ARRAY_LONG_BASE_OFFSET, 511 length, LOG2_ARRAY_LONG_INDEX_SCALE); 512 return i >= 0 ? i : -1; 513 } 514 515 public static int mismatch(long[] a, int aFromIndex, 516 long[] b, int bFromIndex, 517 int length) { 518 if (length == 0) { 519 return -1; 520 } 521 if (a[aFromIndex] != b[bFromIndex]) 522 return 0; 523 int aOffset = Unsafe.ARRAY_LONG_BASE_OFFSET + (aFromIndex << LOG2_ARRAY_LONG_INDEX_SCALE); 524 int bOffset = Unsafe.ARRAY_LONG_BASE_OFFSET + (bFromIndex << LOG2_ARRAY_LONG_INDEX_SCALE); 525 int i = vectorizedMismatch( 526 a, aOffset, 527 b, bOffset, 528 length, LOG2_ARRAY_LONG_INDEX_SCALE); 529 return i >= 0 ? i : -1; 530 } 531 532 533 // Double 534 535 public static int mismatch(double[] a, 536 double[] b, 537 int length) { 538 return mismatch(a, 0, b, 0, length); 539 } 540 541 public static int mismatch(double[] a, int aFromIndex, 542 double[] b, int bFromIndex, 543 int length) { 544 if (length == 0) { 545 return -1; 546 } 547 int i = 0; 548 if (Double.doubleToRawLongBits(a[aFromIndex]) == Double.doubleToRawLongBits(b[bFromIndex])) { 549 int aOffset = Unsafe.ARRAY_DOUBLE_BASE_OFFSET + (aFromIndex << LOG2_ARRAY_DOUBLE_INDEX_SCALE); 550 int bOffset = Unsafe.ARRAY_DOUBLE_BASE_OFFSET + (bFromIndex << LOG2_ARRAY_DOUBLE_INDEX_SCALE); 551 i = vectorizedMismatch( 552 a, aOffset, 553 b, bOffset, 554 length, LOG2_ARRAY_DOUBLE_INDEX_SCALE); 555 } 556 if (i >= 0) { 557 // Check if mismatch is not associated with two NaN values 558 if (!Double.isNaN(a[aFromIndex + i]) || !Double.isNaN(b[bFromIndex + i])) 559 return i; 560 561 // Mismatch on two different NaN values that are normalized to match 562 // Fall back to slow mechanism 563 // ISSUE: Consider looping over vectorizedMismatch adjusting ranges 564 // However, requires that returned value be relative to input ranges 565 i++; 566 for (; i < length; i++) { 567 if (Double.doubleToLongBits(a[aFromIndex + i]) != Double.doubleToLongBits(b[bFromIndex + i])) 568 return i; 569 } 570 } 571 572 return -1; 573 } 574 }