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 (a[i] != b[i])
 169             return i;
 170         if (length > 7) {
 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 (a[i] != b[i])
 191             return i;
 192         if (length > 7) {
 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 (a[i] != b[i])
 235             return i;
 236         if (length > 7) {
 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 (a[i] != b[i])
 284             return i;
 285         if (length > 7) {
 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 (a[i] != b[i])
 311             return i;
 312         if (length > 3) {
 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 (a[i] != b[i])
 333             return i;
 334         if (length > 3) {
 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 (a[i] != b[i])
 360             return i;
 361         if (length > 3) {
 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 (a[i] != b[i])
 382             return i;
 383         if (length > 3) {
 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 (a[i] != b[i])
 409             return i;
 410         if (length > 1) {
 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 (a[i] != b[i])
 431             return i;
 432         if (length > 1) {
 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 (a[i] != b[i])
 464             return i;
 465         if (length > 1) {
 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             // 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         int i = vectorizedMismatch(
 507                 a, Unsafe.ARRAY_LONG_BASE_OFFSET,
 508                 b, Unsafe.ARRAY_LONG_BASE_OFFSET,
 509                 length, LOG2_ARRAY_LONG_INDEX_SCALE);
 510         return i >= 0 ? i : -1;
 511     }
 512 
 513     public static int mismatch(long[] a, int aFromIndex,
 514                                long[] b, int bFromIndex,
 515                                int length) {
 516         if (length == 0) {
 517             return -1;
 518         }
 519         int aOffset = Unsafe.ARRAY_LONG_BASE_OFFSET + (aFromIndex << LOG2_ARRAY_LONG_INDEX_SCALE);
 520         int bOffset = Unsafe.ARRAY_LONG_BASE_OFFSET + (bFromIndex << LOG2_ARRAY_LONG_INDEX_SCALE);
 521         int i = vectorizedMismatch(
 522                 a, aOffset,
 523                 b, bOffset,
 524                 length, LOG2_ARRAY_LONG_INDEX_SCALE);
 525         return i >= 0 ? i : -1;
 526     }
 527 
 528 
 529     // Double
 530 
 531     public static int mismatch(double[] a,
 532                                double[] b,
 533                                int length) {
 534         return mismatch(a, 0, b, 0, length);
 535     }
 536 
 537     public static int mismatch(double[] a, int aFromIndex,
 538                                double[] b, int bFromIndex,
 539                                int length) {
 540         if (length == 0) {
 541             return -1;
 542         }
 543         int aOffset = Unsafe.ARRAY_DOUBLE_BASE_OFFSET + (aFromIndex << LOG2_ARRAY_DOUBLE_INDEX_SCALE);
 544         int bOffset = Unsafe.ARRAY_DOUBLE_BASE_OFFSET + (bFromIndex << LOG2_ARRAY_DOUBLE_INDEX_SCALE);
 545         int i = vectorizedMismatch(
 546                 a, aOffset,
 547                 b, bOffset,
 548                 length, LOG2_ARRAY_DOUBLE_INDEX_SCALE);
 549         if (i >= 0) {
 550             // Check if mismatch is not associated with two NaN values
 551             if (!Double.isNaN(a[aFromIndex + i]) || !Double.isNaN(b[bFromIndex + i]))
 552                 return i;
 553 
 554             // Mismatch on two different NaN values that are normalized to match
 555             // Fall back to slow mechanism
 556             // ISSUE: Consider looping over vectorizedMismatch adjusting ranges
 557             // However, requires that returned value be relative to input ranges
 558             i++;
 559             for (; i < length; i++) {
 560                 if (Double.doubleToLongBits(a[aFromIndex + i]) != Double.doubleToLongBits(b[bFromIndex + i]))
 561                     return i;
 562             }
 563         }
 564 
 565         return -1;
 566     }
 567 }