1 /*

     2  * Copyright (c) 2015, 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 java.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 class ArraysSupport {

    54     static final Unsafe U = Unsafe.getUnsafe();

    55 

    56     private static final boolean BIG_ENDIAN = U.isBigEndian();

    57 

    58     private static final int LOG2_ARRAY_BOOLEAN_INDEX_SCALE = exactLog2(Unsafe.ARRAY_BOOLEAN_INDEX_SCALE);

    59     private static final int LOG2_ARRAY_BYTE_INDEX_SCALE = exactLog2(Unsafe.ARRAY_BYTE_INDEX_SCALE);

    60     private static final int LOG2_ARRAY_CHAR_INDEX_SCALE = exactLog2(Unsafe.ARRAY_CHAR_INDEX_SCALE);

    61     private static final int LOG2_ARRAY_SHORT_INDEX_SCALE = exactLog2(Unsafe.ARRAY_SHORT_INDEX_SCALE);

    62     private static final int LOG2_ARRAY_INT_INDEX_SCALE = exactLog2(Unsafe.ARRAY_INT_INDEX_SCALE);

    63     private static final int LOG2_ARRAY_LONG_INDEX_SCALE = exactLog2(Unsafe.ARRAY_LONG_INDEX_SCALE);

    64     private static final int LOG2_ARRAY_FLOAT_INDEX_SCALE = exactLog2(Unsafe.ARRAY_FLOAT_INDEX_SCALE);

    65     private 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     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     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     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     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     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     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     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     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     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     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     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     static int mismatch(float[] a,

   434                         float[] b,

   435                         int length) {

   436         return mismatch(a, 0, b, 0, length);

   437     }

   438 

   439     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     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     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     static int mismatch(double[] a,

   510                         double[] b,

   511                         int length) {

   512         return mismatch(a, 0, b, 0, length);

   513     }

   514 

   515     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 }