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