rev 12972 : 8140606: Update library code to use internal Unsafe
Reviewed-by: duke

   1 /*
   2  * Copyright (c) 2014, 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.zip;
  26 
  27 import java.nio.ByteBuffer;
  28 import java.nio.ByteOrder;
  29 
  30 import jdk.internal.HotSpotIntrinsicCandidate;
  31 import sun.misc.Unsafe;
  32 import sun.nio.ch.DirectBuffer;
  33 
  34 /**
  35  * A class that can be used to compute the CRC-32C of a data stream.
  36  *
  37  * <p>
  38  * CRC-32C is defined in <a href="http://www.ietf.org/rfc/rfc3720.txt">RFC
  39  * 3720</a>: Internet Small Computer Systems Interface (iSCSI).
  40  * </p>
  41  *
  42  * <p>
  43  * Passing a {@code null} argument to a method in this class will cause a
  44  * {@link NullPointerException} to be thrown.
  45  * </p>
  46  *
  47  * @since 1.9
  48  */
  49 public final class CRC32C implements Checksum {
  50 
  51     /*
  52      * This CRC-32C implementation uses the 'slicing-by-8' algorithm described
  53      * in the paper "A Systematic Approach to Building High Performance
  54      * Software-Based CRC Generators" by Michael E. Kounavis and Frank L. Berry,
  55      * Intel Research and Development
  56      */
  57 
  58     /**
  59      * CRC-32C Polynomial
  60      */
  61     private static final int CRC32C_POLY = 0x1EDC6F41;
  62     private static final int REVERSED_CRC32C_POLY = Integer.reverse(CRC32C_POLY);
  63 
  64     private static final Unsafe UNSAFE = Unsafe.getUnsafe();
  65 
  66     // Lookup tables
  67     // Lookup table for single byte calculations
  68     private static final int[] byteTable;
  69     // Lookup tables for bulk operations in 'slicing-by-8' algorithm
  70     private static final int[][] byteTables = new int[8][256];
  71     private static final int[] byteTable0 = byteTables[0];
  72     private static final int[] byteTable1 = byteTables[1];
  73     private static final int[] byteTable2 = byteTables[2];
  74     private static final int[] byteTable3 = byteTables[3];
  75     private static final int[] byteTable4 = byteTables[4];
  76     private static final int[] byteTable5 = byteTables[5];
  77     private static final int[] byteTable6 = byteTables[6];
  78     private static final int[] byteTable7 = byteTables[7];
  79 
  80     static {
  81         // Generate lookup tables
  82         // High-order polynomial term stored in LSB of r.
  83         for (int index = 0; index < byteTables[0].length; index++) {
  84            int r = index;
  85             for (int i = 0; i < Byte.SIZE; i++) {
  86                 if ((r & 1) != 0) {
  87                     r = (r >>> 1) ^ REVERSED_CRC32C_POLY;
  88                 } else {
  89                     r >>>= 1;
  90                 }
  91             }
  92             byteTables[0][index] = r;
  93         }
  94 
  95         for (int index = 0; index < byteTables[0].length; index++) {
  96             int r = byteTables[0][index];
  97 
  98             for (int k = 1; k < byteTables.length; k++) {
  99                 r = byteTables[0][r & 0xFF] ^ (r >>> 8);
 100                 byteTables[k][index] = r;
 101             }
 102         }
 103 
 104         if (ByteOrder.nativeOrder() == ByteOrder.LITTLE_ENDIAN) {
 105             byteTable = byteTables[0];
 106         } else { // ByteOrder.BIG_ENDIAN
 107             byteTable = new int[byteTable0.length];
 108             System.arraycopy(byteTable0, 0, byteTable, 0, byteTable0.length);
 109             for (int[] table : byteTables) {
 110                 for (int index = 0; index < table.length; index++) {
 111                     table[index] = Integer.reverseBytes(table[index]);
 112                 }
 113             }
 114         }
 115     }
 116 
 117     /**
 118      * Calculated CRC-32C value
 119      */
 120     private int crc = 0xFFFFFFFF;
 121 
 122     /**
 123      * Creates a new CRC32C object.
 124      */
 125     public CRC32C() {
 126     }
 127 
 128     /**
 129      * Updates the CRC-32C checksum with the specified byte (the low eight bits
 130      * of the argument b).
 131      */
 132     @Override
 133     public void update(int b) {
 134         crc = (crc >>> 8) ^ byteTable[(crc ^ (b & 0xFF)) & 0xFF];
 135     }
 136 
 137     /**
 138      * Updates the CRC-32C checksum with the specified array of bytes.
 139      *
 140      * @throws ArrayIndexOutOfBoundsException
 141      *         if {@code off} is negative, or {@code len} is negative, or
 142      *         {@code off+len} is negative or greater than the length of
 143      *         the array {@code b}.
 144      */
 145     @Override
 146     public void update(byte[] b, int off, int len) {
 147         if (b == null) {
 148             throw new NullPointerException();
 149         }
 150         if (off < 0 || len < 0 || off > b.length - len) {
 151             throw new ArrayIndexOutOfBoundsException();
 152         }
 153         crc = updateBytes(crc, b, off, (off + len));
 154     }
 155 
 156     /**
 157      * Updates the CRC-32C checksum with the bytes from the specified buffer.
 158      *
 159      * The checksum is updated with the remaining bytes in the buffer, starting
 160      * at the buffer's position. Upon return, the buffer's position will be
 161      * updated to its limit; its limit will not have been changed.
 162      */
 163     @Override
 164     public void update(ByteBuffer buffer) {
 165         int pos = buffer.position();
 166         int limit = buffer.limit();
 167         assert (pos <= limit);
 168         int rem = limit - pos;
 169         if (rem <= 0) {
 170             return;
 171         }
 172 
 173         if (buffer instanceof DirectBuffer) {
 174             crc = updateDirectByteBuffer(crc, ((DirectBuffer) buffer).address(),
 175                                          pos, limit);
 176         } else if (buffer.hasArray()) {
 177             crc = updateBytes(crc, buffer.array(), pos + buffer.arrayOffset(),
 178                               limit + buffer.arrayOffset());
 179         } else {
 180             byte[] b = new byte[Math.min(buffer.remaining(), 4096)];
 181             while (buffer.hasRemaining()) {
 182                 int length = Math.min(buffer.remaining(), b.length);
 183                 buffer.get(b, 0, length);
 184                 update(b, 0, length);
 185             }
 186         }
 187         buffer.position(limit);
 188     }
 189 
 190     /**
 191      * Resets CRC-32C to initial value.
 192      */
 193     @Override
 194     public void reset() {
 195         crc = 0xFFFFFFFF;
 196     }
 197 
 198     /**
 199      * Returns CRC-32C value.
 200      */
 201     @Override
 202     public long getValue() {
 203         return (~crc) & 0xFFFFFFFFL;
 204     }
 205 
 206     /**
 207      * Updates the CRC-32C checksum with the specified array of bytes.
 208      */
 209     @HotSpotIntrinsicCandidate
 210     private static int updateBytes(int crc, byte[] b, int off, int end) {
 211 
 212         // Do only byte reads for arrays so short they can't be aligned
 213         // or if bytes are stored with a larger witdh than one byte.,%
 214         if (end - off >= 8 && Unsafe.ARRAY_BYTE_INDEX_SCALE == 1) {
 215 
 216             // align on 8 bytes
 217             int alignLength
 218                     = (8 - ((Unsafe.ARRAY_BYTE_BASE_OFFSET + off) & 0x7)) & 0x7;
 219             for (int alignEnd = off + alignLength; off < alignEnd; off++) {
 220                 crc = (crc >>> 8) ^ byteTable[(crc ^ b[off]) & 0xFF];
 221             }
 222 
 223             if (ByteOrder.nativeOrder() == ByteOrder.BIG_ENDIAN) {
 224                 crc = Integer.reverseBytes(crc);
 225             }
 226 
 227             // slicing-by-8
 228             for (; off < (end - Long.BYTES); off += Long.BYTES) {
 229                 int firstHalf;
 230                 int secondHalf;
 231                 if (Unsafe.ADDRESS_SIZE == 4) {
 232                     // On 32 bit platforms read two ints instead of a single 64bit long
 233                     firstHalf = UNSAFE.getInt(b, (long)Unsafe.ARRAY_BYTE_BASE_OFFSET + off);
 234                     secondHalf = UNSAFE.getInt(b, (long)Unsafe.ARRAY_BYTE_BASE_OFFSET + off
 235                                                + Integer.BYTES);
 236                 } else {
 237                     long value = UNSAFE.getLong(b, (long)Unsafe.ARRAY_BYTE_BASE_OFFSET + off);
 238                     if (ByteOrder.nativeOrder() == ByteOrder.LITTLE_ENDIAN) {
 239                         firstHalf = (int) value;
 240                         secondHalf = (int) (value >>> 32);
 241                     } else { // ByteOrder.BIG_ENDIAN
 242                         firstHalf = (int) (value >>> 32);
 243                         secondHalf = (int) value;
 244                     }
 245                 }
 246                 crc ^= firstHalf;
 247                 if (ByteOrder.nativeOrder() == ByteOrder.LITTLE_ENDIAN) {
 248                     crc = byteTable7[crc & 0xFF]
 249                             ^ byteTable6[(crc >>> 8) & 0xFF]
 250                             ^ byteTable5[(crc >>> 16) & 0xFF]
 251                             ^ byteTable4[crc >>> 24]
 252                             ^ byteTable3[secondHalf & 0xFF]
 253                             ^ byteTable2[(secondHalf >>> 8) & 0xFF]
 254                             ^ byteTable1[(secondHalf >>> 16) & 0xFF]
 255                             ^ byteTable0[secondHalf >>> 24];
 256                 } else { // ByteOrder.BIG_ENDIAN
 257                     crc = byteTable0[secondHalf & 0xFF]
 258                             ^ byteTable1[(secondHalf >>> 8) & 0xFF]
 259                             ^ byteTable2[(secondHalf >>> 16) & 0xFF]
 260                             ^ byteTable3[secondHalf >>> 24]
 261                             ^ byteTable4[crc & 0xFF]
 262                             ^ byteTable5[(crc >>> 8) & 0xFF]
 263                             ^ byteTable6[(crc >>> 16) & 0xFF]
 264                             ^ byteTable7[crc >>> 24];
 265                 }
 266             }
 267 
 268             if (ByteOrder.nativeOrder() == ByteOrder.BIG_ENDIAN) {
 269                 crc = Integer.reverseBytes(crc);
 270             }
 271         }
 272 
 273         // Tail
 274         for (; off < end; off++) {
 275             crc = (crc >>> 8) ^ byteTable[(crc ^ b[off]) & 0xFF];
 276         }
 277 
 278         return crc;
 279     }
 280 
 281     /**
 282      * Updates the CRC-32C checksum reading from the specified address.
 283      */
 284     @HotSpotIntrinsicCandidate
 285     private static int updateDirectByteBuffer(int crc, long address,
 286                                               int off, int end) {
 287 
 288         // Do only byte reads for arrays so short they can't be aligned
 289         if (end - off >= 8) {
 290 
 291             // align on 8 bytes
 292             int alignLength = (8 - (int) ((address + off) & 0x7)) & 0x7;
 293             for (int alignEnd = off + alignLength; off < alignEnd; off++) {
 294                 crc = (crc >>> 8)
 295                         ^ byteTable[(crc ^ UNSAFE.getByte(address + off)) & 0xFF];
 296             }
 297 
 298             if (ByteOrder.nativeOrder() == ByteOrder.BIG_ENDIAN) {
 299                 crc = Integer.reverseBytes(crc);
 300             }
 301 
 302             // slicing-by-8
 303             for (; off <= (end - Long.BYTES); off += Long.BYTES) {
 304                 // Always reading two ints as reading a long followed by
 305                 // shifting and casting was slower.
 306                 int firstHalf = UNSAFE.getInt(address + off);
 307                 int secondHalf = UNSAFE.getInt(address + off + Integer.BYTES);
 308                 crc ^= firstHalf;
 309                 if (ByteOrder.nativeOrder() == ByteOrder.LITTLE_ENDIAN) {
 310                     crc = byteTable7[crc & 0xFF]
 311                             ^ byteTable6[(crc >>> 8) & 0xFF]
 312                             ^ byteTable5[(crc >>> 16) & 0xFF]
 313                             ^ byteTable4[crc >>> 24]
 314                             ^ byteTable3[secondHalf & 0xFF]
 315                             ^ byteTable2[(secondHalf >>> 8) & 0xFF]
 316                             ^ byteTable1[(secondHalf >>> 16) & 0xFF]
 317                             ^ byteTable0[secondHalf >>> 24];
 318                 } else { // ByteOrder.BIG_ENDIAN
 319                     crc = byteTable0[secondHalf & 0xFF]
 320                             ^ byteTable1[(secondHalf >>> 8) & 0xFF]
 321                             ^ byteTable2[(secondHalf >>> 16) & 0xFF]
 322                             ^ byteTable3[secondHalf >>> 24]
 323                             ^ byteTable4[crc & 0xFF]
 324                             ^ byteTable5[(crc >>> 8) & 0xFF]
 325                             ^ byteTable6[(crc >>> 16) & 0xFF]
 326                             ^ byteTable7[crc >>> 24];
 327                 }
 328             }
 329 
 330             if (ByteOrder.nativeOrder() == ByteOrder.BIG_ENDIAN) {
 331                 crc = Integer.reverseBytes(crc);
 332             }
 333         }
 334 
 335         // Tail
 336         for (; off < end; off++) {
 337             crc = (crc >>> 8)
 338                     ^ byteTable[(crc ^ UNSAFE.getByte(address + off)) & 0xFF];
 339         }
 340 
 341         return crc;
 342     }
 343 }
--- EOF ---