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 sun.misc.Unsafe;
  28 
  29 class ArraysSupport {
  30     static final Unsafe U = Unsafe.getUnsafe();
  31 
  32     private static final boolean BIG_ENDIAN = U.isBigEndian();
  33 
  34     private static final int LOG2_ARRAY_BOOLEAN_INDEX_SCALE = exactLog2(Unsafe.ARRAY_BOOLEAN_INDEX_SCALE);
  35     private static final int LOG2_ARRAY_BYTE_INDEX_SCALE = exactLog2(Unsafe.ARRAY_BYTE_INDEX_SCALE);
  36     private static final int LOG2_ARRAY_CHAR_INDEX_SCALE = exactLog2(Unsafe.ARRAY_CHAR_INDEX_SCALE);
  37     private static final int LOG2_ARRAY_SHORT_INDEX_SCALE = exactLog2(Unsafe.ARRAY_SHORT_INDEX_SCALE);
  38     private static final int LOG2_ARRAY_INT_INDEX_SCALE = exactLog2(Unsafe.ARRAY_INT_INDEX_SCALE);
  39     private static final int LOG2_ARRAY_LONG_INDEX_SCALE = exactLog2(Unsafe.ARRAY_LONG_INDEX_SCALE);
  40     private static final int LOG2_ARRAY_FLOAT_INDEX_SCALE = exactLog2(Unsafe.ARRAY_FLOAT_INDEX_SCALE);
  41     private static final int LOG2_ARRAY_DOUBLE_INDEX_SCALE = exactLog2(Unsafe.ARRAY_DOUBLE_INDEX_SCALE);
  42 
  43     private static int exactLog2(int scale) {
  44         if ((scale & (scale - 1)) != 0)
  45             throw new Error("data type scale not a power of two");
  46         return Integer.numberOfTrailingZeros(scale);
  47     }
  48 
  49     private ArraysSupport() {}
  50 
  51     /**
  52      * Find the relative index of the first mismatching pair of elements in two
  53      * arrays of the same component type.  For reference component types the
  54      * reference values (as opposed to what they reference) will be matched.
  55      * Pairs of elements will be tested in order relative to given offsets into
  56      * both arrays.
  57      *
  58      * <p>This method does not perform bounds checks.  It is the responsibility
  59      * of the caller to perform such bounds checks before calling this method.
  60      *
  61      * @param a the first array to be tested for mismatch
  62      * @param aOffset the offset, in bytes, from the base address of the
  63      * first array to test from
  64      * @param b the second array to be tested for mismatch
  65      * @param bOffset the offset, in bytes, from the base address of the
  66      * second array to test from
  67      * @param length the number of array elements to test
  68      * @param log2ArrayIndexScale log<sub>2</sub> of the array index scale
  69      * @return if a mismatch is found a relative index of the first
  70      * mismatching pair of elements in the two arrays.
  71      * If a mismatch is not found the negation of one plus the number of
  72      * remaining pairs of elements to be checked in the tail of the two arrays.
  73      */
  74     static int vectorizedMismatch(Object a, long aOffset,
  75                                   Object b, long bOffset,
  76                                   int length,
  77                                   int log2ArrayIndexScale) {
  78         // assert a.getClass().isArray();
  79         // assert b.getClass().isArray();
  80         // assert 0 <= length <= sizeOf(a)
  81         // assert 0 <= length <= sizeOf(b)
  82         // assert 0 <= log2ArrayIndexScale <= 3
  83 
  84         int valuesPerWidth = LOG2_ARRAY_LONG_INDEX_SCALE - log2ArrayIndexScale;
  85         int wi = 0;
  86         for (; wi < length >> valuesPerWidth; wi++) {
  87             long bi = ((long) wi) << LOG2_ARRAY_LONG_INDEX_SCALE;
  88             long av = U.getLongUnaligned(a, aOffset + bi);
  89             long bv = U.getLongUnaligned(b, bOffset + bi);
  90             if (av != bv) {
  91                 long x = av ^ bv;
  92                 int o = BIG_ENDIAN
  93                         ? Long.numberOfLeadingZeros(x) >> (3 + log2ArrayIndexScale)
  94                         : Long.numberOfTrailingZeros(x) >> (3 + log2ArrayIndexScale);
  95                 return (wi << valuesPerWidth) + o;
  96             }
  97         }
  98 
  99         // Calculate the tail of remaining elements to check
 100         int tail = length - (wi << valuesPerWidth);
 101 
 102         if (log2ArrayIndexScale < 2) {
 103             int wordTail = 1 << (LOG2_ARRAY_INT_INDEX_SCALE - log2ArrayIndexScale);
 104             // Handle 4 bytes or 2 chars in the tail using int width
 105             if (tail >= wordTail) {
 106                 long bi = ((long) wi) << LOG2_ARRAY_LONG_INDEX_SCALE;
 107                 int av = U.getIntUnaligned(a, aOffset + bi);
 108                 int bv = U.getIntUnaligned(b, bOffset + bi);
 109                 if (av != bv) {
 110                     int x = av ^ bv;
 111                     int o = BIG_ENDIAN
 112                             ? Integer.numberOfLeadingZeros(x) >> (3 + log2ArrayIndexScale)
 113                             : Integer.numberOfTrailingZeros(x) >> (3 + log2ArrayIndexScale);
 114                     return (wi << valuesPerWidth) + o;
 115                 }
 116                 tail -= wordTail;
 117             }
 118             return -1 - tail;
 119         }
 120         else {
 121             return -1 - tail;
 122         }
 123     }
 124 
 125     // Booleans
 126     // Each boolean element takes up one byte
 127 
 128     static int mismatchBoolean(boolean[] a,
 129                                boolean[] b,
 130                                int length) {
 131         int i = 0;
 132         if (length > 3) {
 133             i = vectorizedMismatch(
 134                     a, Unsafe.ARRAY_BOOLEAN_BASE_OFFSET,
 135                     b, Unsafe.ARRAY_BOOLEAN_BASE_OFFSET,
 136                     length, LOG2_ARRAY_BOOLEAN_INDEX_SCALE);
 137             if (i >= 0)
 138                 return i;
 139             i = length + 1 + i;
 140         }
 141         for (; i < length; i++) {
 142             if (a[i] != b[i])
 143                 return i;
 144         }
 145         return -1;
 146     }
 147 
 148     static int mismatchBooleanRange(boolean[] a, int aFromIndex,
 149                                     boolean[] b, int bFromIndex,
 150                                     int length) {
 151         int i = 0;
 152         if (length > 3) {
 153             int aOffset = Unsafe.ARRAY_BOOLEAN_BASE_OFFSET + aFromIndex;
 154             int bOffset = Unsafe.ARRAY_BOOLEAN_BASE_OFFSET + bFromIndex;
 155             i = vectorizedMismatch(
 156                     a, aOffset,
 157                     b, bOffset,
 158                     length, LOG2_ARRAY_BOOLEAN_INDEX_SCALE);
 159             if (i >= 0)
 160                 return i;
 161             i = length + 1 + i;
 162         }
 163         for (; i < length; i++) {
 164             if (a[aFromIndex + i] != b[bFromIndex + i])
 165                 return i;
 166         }
 167         return -1;
 168     }
 169 
 170 
 171     // Bytes
 172 
 173     /**
 174      * Find the index of a mismatch between two arrays.
 175      *
 176      * <p>This method does not perform bounds checks. It is the responsibility
 177      * of the caller to perform such bounds checks before calling this method.
 178      *
 179      * @param a the first array to be tested for a mismatch
 180      * @param b the second array to be tested for a mismatch
 181      * @param length the number of bytes from each array to check
 182      * @return the index of a mismatch between the two arrays, otherwise
 183      * -1 if no mismatch.  THe index will be within the range of
 184      * (inclusive) 0 to (exclusive) the smaller of the two array
 185      * lengths.
 186      */
 187     static int mismatchByte(byte[] a,
 188                             byte[] b,
 189                             int length) {
 190         // @@@ defer to index receiving methods if performance is good
 191         // assert length <= a.length
 192         // assert length <= b.length
 193 
 194         int i = 0;
 195         if (length > 3) {
 196             i = vectorizedMismatch(
 197                     a, Unsafe.ARRAY_BYTE_BASE_OFFSET,
 198                     b, Unsafe.ARRAY_BYTE_BASE_OFFSET,
 199                     length, LOG2_ARRAY_BYTE_INDEX_SCALE);
 200             if (i >= 0)
 201                 return i;
 202             // Align to tail
 203             i = length + 1 + i;
 204 //            assert i >= 0 && i <= 7;
 205         }
 206         // Tail < 8 bytes
 207         for (; i < length; i++) {
 208             if (a[i] != b[i])
 209                 return i;
 210         }
 211         return -1;
 212     }
 213 
 214     /**
 215      * Find the relative index of a mismatch between two arrays starting from
 216      * given indexes.
 217      *
 218      * <p>This method does not perform bounds checks. It is the responsibility
 219      * of the caller to perform such bounds checks before calling this method.
 220      *
 221      * @param a the first array to be tested for a mismatch
 222      * @param aFromIndex the index of the first element (inclusive) in the
 223      * first array to be compared
 224      * @param b the second array to be tested for a mismatch
 225      * @param bFromIndex the index of the first element (inclusive) in the
 226      * second array to be compared
 227      * @param length the number of bytes from each array to check
 228      * @return the relative index of a mismatch between the two arrays,
 229      * otherwise -1 if no mismatch.  The index will be within the range
 230      * of (inclusive) 0 to (exclusive) the smaller of the two array
 231      * bounds.
 232      */
 233     static int mismatchByteRange(byte[] a, int aFromIndex,
 234                                  byte[] b, int bFromIndex,
 235                                  int length) {
 236         // assert 0 <= aFromIndex < a.length
 237         // assert 0 <= aFromIndex + length <= a.length
 238         // assert 0 <= bFromIndex < b.length
 239         // assert 0 <= bFromIndex + length <= b.length
 240         // assert length >= 0
 241 
 242         int i = 0;
 243         if (length > 3) {
 244             int aOffset = Unsafe.ARRAY_BYTE_BASE_OFFSET + aFromIndex;
 245             int bOffset = Unsafe.ARRAY_BYTE_BASE_OFFSET + bFromIndex;
 246             i = vectorizedMismatch(
 247                     a, aOffset,
 248                     b, bOffset,
 249                     length, LOG2_ARRAY_BYTE_INDEX_SCALE);
 250             if (i >= 0)
 251                 return i;
 252             i = length + 1 + i;
 253         }
 254         for (; i < length; i++) {
 255             if (a[aFromIndex + i] != b[bFromIndex + i])
 256                 return i;
 257         }
 258         return -1;
 259     }
 260 
 261 
 262     // Chars
 263 
 264     static int mismatchChar(char[] a,
 265                             char[] b,
 266                             int length) {
 267         int i = 0;
 268         if (length > 1) {
 269             i = vectorizedMismatch(
 270                     a, Unsafe.ARRAY_CHAR_BASE_OFFSET,
 271                     b, Unsafe.ARRAY_CHAR_BASE_OFFSET,
 272                     length, LOG2_ARRAY_CHAR_INDEX_SCALE);
 273             if (i >= 0)
 274                 return i;
 275             i = length + 1 + i;
 276         }
 277         for (; i < length; i++) {
 278             if (a[i] != b[i])
 279                 return i;
 280         }
 281         return -1;
 282     }
 283 
 284     static int mismatchCharRange(char[] a, int aFromIndex,
 285                                  char[] b, int bFromIndex,
 286                                  int length) {
 287         int i = 0;
 288         if (length > 1) {
 289             int aOffset = Unsafe.ARRAY_CHAR_BASE_OFFSET + (aFromIndex << 1);
 290             int bOffset = Unsafe.ARRAY_CHAR_BASE_OFFSET + (bFromIndex << 1);
 291             i = vectorizedMismatch(
 292                     a, aOffset,
 293                     b, bOffset,
 294                     length, LOG2_ARRAY_CHAR_INDEX_SCALE);
 295             if (i >= 0)
 296                 return i;
 297             i = length + 1 + i;
 298         }
 299         for (; i < length; i++) {
 300             if (a[aFromIndex + i] != b[bFromIndex + i])
 301                 return i;
 302         }
 303         return -1;
 304     }
 305 
 306 
 307     // Shorts
 308 
 309     static int mismatchShort(short[] a,
 310                              short[] b,
 311                              int length) {
 312         int i = 0;
 313         if (length > 1) {
 314             i = vectorizedMismatch(
 315                     a, Unsafe.ARRAY_SHORT_BASE_OFFSET,
 316                     b, Unsafe.ARRAY_SHORT_BASE_OFFSET,
 317                     length, LOG2_ARRAY_SHORT_INDEX_SCALE);
 318             if (i >= 0)
 319                 return i;
 320             i = length + 1 + i;
 321         }
 322         for (; i < length; i++) {
 323             if (a[i] != b[i])
 324                 return i;
 325         }
 326         return -1;
 327     }
 328 
 329     static int mismatchShortRange(short[] a, int aFromIndex,
 330                                   short[] b, int bFromIndex,
 331                                   int length) {
 332         int i = 0;
 333         if (length > 1) {
 334             int aOffset = Unsafe.ARRAY_SHORT_BASE_OFFSET + (aFromIndex << 1);
 335             int bOffset = Unsafe.ARRAY_SHORT_BASE_OFFSET + (bFromIndex << 1);
 336             i = vectorizedMismatch(
 337                     a, aOffset,
 338                     b, bOffset,
 339                     length, LOG2_ARRAY_SHORT_INDEX_SCALE);
 340             if (i >= 0)
 341                 return i;
 342             i = length + 1 + i;
 343         }
 344         for (; i < length; i++) {
 345             if (a[aFromIndex + i] != b[bFromIndex + i])
 346                 return i;
 347         }
 348         return -1;
 349     }
 350 
 351 
 352     // Ints
 353 
 354     static int mismatchInt(int[] a,
 355                            int[] b,
 356                            int length) {
 357         int i = 0;
 358         if (length > 1) {
 359             i = vectorizedMismatch(
 360                     a, Unsafe.ARRAY_INT_BASE_OFFSET,
 361                     b, Unsafe.ARRAY_INT_BASE_OFFSET,
 362                     length, LOG2_ARRAY_INT_INDEX_SCALE);
 363             if (i >= 0)
 364                 return i;
 365             i = length + 1 + i;
 366         }
 367         for (; i < length; i++) {
 368             if (a[i] != b[i])
 369                 return i;
 370         }
 371         return -1;
 372     }
 373 
 374     static int mismatchIntRange(int[] a, int aFromIndex,
 375                                 int[] b, int bFromIndex,
 376                                 int length) {
 377         int i = 0;
 378         if (length > 1) {
 379             int aOffset = Unsafe.ARRAY_INT_BASE_OFFSET + (aFromIndex << 2);
 380             int bOffset = Unsafe.ARRAY_INT_BASE_OFFSET + (bFromIndex << 2);
 381             i = vectorizedMismatch(
 382                     a, aOffset,
 383                     b, bOffset,
 384                     length, LOG2_ARRAY_INT_INDEX_SCALE);
 385             if (i >= 0)
 386                 return i;
 387             i = length + 1 + i;
 388         }
 389         for (; i < length; i++) {
 390             if (a[aFromIndex + i] != b[bFromIndex + i])
 391                 return i;
 392         }
 393         return -1;
 394     }
 395 
 396 
 397     // Floats
 398 
 399     static int mismatchFloat(float[] a,
 400                              float[] b,
 401                              int length) {
 402         return mismatchFloatRange(a, 0, b, 0, length);
 403     }
 404 
 405     static int mismatchFloatRange(float[] a, int aFromIndex,
 406                                   float[] b, int bFromIndex,
 407                                   int length) {
 408         int i = 0;
 409         if (length > 1) {
 410             int aOffset = Unsafe.ARRAY_FLOAT_BASE_OFFSET + (aFromIndex << 2);
 411             int bOffset = Unsafe.ARRAY_FLOAT_BASE_OFFSET + (bFromIndex << 2);
 412             i = vectorizedMismatch(
 413                     a, aOffset,
 414                     b, bOffset,
 415                     length, LOG2_ARRAY_FLOAT_INDEX_SCALE);
 416             // Mismatched
 417             if (i >= 0) {
 418                 // Check if mismatch is not associated with two NaN values
 419                 if (!Float.isNaN(a[aFromIndex + i]) || !Float.isNaN(b[aFromIndex + i]))
 420                     return i;
 421 
 422                 // Mismatch on two different NaN values that are normalized to match
 423                 // Fall back to slow mechanism
 424                 // @@@ Consider looping over vectorizedMismatch adjusting ranges
 425                 // However, requires that returned value be relative to input ranges
 426                 i++;
 427             }
 428             // Matched
 429             else {
 430                 i = length + 1 + i;
 431             }
 432         }
 433         for (; i < length; i++) {
 434             if (Float.floatToIntBits(a[aFromIndex + i]) != Float.floatToIntBits(b[bFromIndex + i]))
 435                 return i;
 436         }
 437         return -1;
 438     }
 439 
 440     // 64 bit sizes
 441     // @@@ Can these leverage the same mismatch method without being impacted?
 442 
 443     // Long
 444 
 445     static int mismatchLong(long[] a,
 446                             long[] b,
 447                             int length) {
 448         int i = vectorizedMismatch(
 449                 a, Unsafe.ARRAY_LONG_BASE_OFFSET,
 450                 b, Unsafe.ARRAY_LONG_BASE_OFFSET,
 451                 length, LOG2_ARRAY_LONG_INDEX_SCALE);
 452         return i >= 0 ? i : -1;
 453     }
 454 
 455     static int mismatchLongRange(long[] a, int aFromIndex,
 456                                  long[] b, int bFromIndex,
 457                                  int length) {
 458         int aOffset = Unsafe.ARRAY_LONG_BASE_OFFSET + (aFromIndex << 3);
 459         int bOffset = Unsafe.ARRAY_LONG_BASE_OFFSET + (bFromIndex << 3);
 460         int i = vectorizedMismatch(
 461                 a, aOffset,
 462                 b, bOffset,
 463                 length, LOG2_ARRAY_LONG_INDEX_SCALE);
 464         return i >= 0 ? i : -1;
 465     }
 466 
 467 
 468     // Double
 469 
 470     static int mismatchDouble(double[] a,
 471                               double[] b,
 472                               int length) {
 473         return mismatchDoubleRange(a, 0, b, 0, length);
 474     }
 475 
 476     static int mismatchDoubleRange(double[] a, int aFromIndex,
 477                                    double[] b, int bFromIndex,
 478                                    int length) {
 479         int aOffset = Unsafe.ARRAY_DOUBLE_BASE_OFFSET + (aFromIndex << 3);
 480         int bOffset = Unsafe.ARRAY_DOUBLE_BASE_OFFSET + (bFromIndex << 3);
 481         int i = vectorizedMismatch(
 482                 a, aOffset,
 483                 b, bOffset,
 484                 length, LOG2_ARRAY_DOUBLE_INDEX_SCALE);
 485         if (i >= 0) {
 486             // Check if mismatch is not associated with two NaN values
 487             if (!Double.isNaN(a[aFromIndex + i]) || !Double.isNaN(b[aFromIndex + i]))
 488                 return i;
 489 
 490             // Mismatch on two different NaN values that are normalized to match
 491             // Fall back to slow mechanism
 492             // @@@ Consider looping over vectorizedMismatch adjusting ranges
 493             // However, requires that returned value be relative to input ranges
 494             i++;
 495             for (; i < length; i++) {
 496                 if (Double.doubleToLongBits(a[aFromIndex + i]) != Double.doubleToLongBits(b[bFromIndex + i]))
 497                     return i;
 498             }
 499         }
 500 
 501         return -1;
 502     }
 503 }