| /* |
| * Copyright (c) 2014, 2020, Oracle and/or its affiliates. All rights reserved. |
| * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. |
| * |
| * This code is free software; you can redistribute it and/or modify it |
| * under the terms of the GNU General Public License version 2 only, as |
| * published by the Free Software Foundation. Oracle designates this |
| * particular file as subject to the "Classpath" exception as provided |
| * by Oracle in the LICENSE file that accompanied this code. |
| * |
| * This code is distributed in the hope that it will be useful, but WITHOUT |
| * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or |
| * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License |
| * version 2 for more details (a copy is included in the LICENSE file that |
| * accompanied this code). |
| * |
| * You should have received a copy of the GNU General Public License version |
| * 2 along with this work; if not, write to the Free Software Foundation, |
| * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. |
| * |
| * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA |
| * or visit www.oracle.com if you need additional information or have any |
| * questions. |
| */ |
| package java.util.zip; |
| |
| import java.lang.ref.Reference; |
| import java.nio.ByteBuffer; |
| import java.nio.ByteOrder; |
| |
| import jdk.internal.misc.Unsafe; |
| import jdk.internal.vm.annotation.IntrinsicCandidate; |
| import sun.nio.ch.DirectBuffer; |
| |
| /** |
| * A class that can be used to compute the CRC-32C of a data stream. |
| * |
| * <p> |
| * CRC-32C is defined in <a href="http://www.ietf.org/rfc/rfc3720.txt">RFC |
| * 3720</a>: Internet Small Computer Systems Interface (iSCSI). |
| * </p> |
| * |
| * <p> |
| * Passing a {@code null} argument to a method in this class will cause a |
| * {@link NullPointerException} to be thrown. |
| * </p> |
| * |
| * @since 9 |
| */ |
| public final class CRC32C implements Checksum { |
| |
| /* |
| * This CRC-32C implementation uses the 'slicing-by-8' algorithm described |
| * in the paper "A Systematic Approach to Building High Performance |
| * Software-Based CRC Generators" by Michael E. Kounavis and Frank L. Berry, |
| * Intel Research and Development |
| */ |
| |
| /** |
| * CRC-32C Polynomial |
| */ |
| private static final int CRC32C_POLY = 0x1EDC6F41; |
| private static final int REVERSED_CRC32C_POLY = Integer.reverse(CRC32C_POLY); |
| |
| private static final Unsafe UNSAFE = Unsafe.getUnsafe(); |
| |
| // Lookup tables |
| // Lookup table for single byte calculations |
| private static final int[] byteTable; |
| // Lookup tables for bulk operations in 'slicing-by-8' algorithm |
| private static final int[][] byteTables = new int[8][256]; |
| private static final int[] byteTable0 = byteTables[0]; |
| private static final int[] byteTable1 = byteTables[1]; |
| private static final int[] byteTable2 = byteTables[2]; |
| private static final int[] byteTable3 = byteTables[3]; |
| private static final int[] byteTable4 = byteTables[4]; |
| private static final int[] byteTable5 = byteTables[5]; |
| private static final int[] byteTable6 = byteTables[6]; |
| private static final int[] byteTable7 = byteTables[7]; |
| |
| static { |
| // Generate lookup tables |
| // High-order polynomial term stored in LSB of r. |
| for (int index = 0; index < byteTables[0].length; index++) { |
| int r = index; |
| for (int i = 0; i < Byte.SIZE; i++) { |
| if ((r & 1) != 0) { |
| r = (r >>> 1) ^ REVERSED_CRC32C_POLY; |
| } else { |
| r >>>= 1; |
| } |
| } |
| byteTables[0][index] = r; |
| } |
| |
| for (int index = 0; index < byteTables[0].length; index++) { |
| int r = byteTables[0][index]; |
| |
| for (int k = 1; k < byteTables.length; k++) { |
| r = byteTables[0][r & 0xFF] ^ (r >>> 8); |
| byteTables[k][index] = r; |
| } |
| } |
| |
| if (ByteOrder.nativeOrder() == ByteOrder.LITTLE_ENDIAN) { |
| byteTable = byteTables[0]; |
| } else { // ByteOrder.BIG_ENDIAN |
| byteTable = new int[byteTable0.length]; |
| System.arraycopy(byteTable0, 0, byteTable, 0, byteTable0.length); |
| for (int[] table : byteTables) { |
| for (int index = 0; index < table.length; index++) { |
| table[index] = Integer.reverseBytes(table[index]); |
| } |
| } |
| } |
| } |
| |
| /** |
| * Calculated CRC-32C value |
| */ |
| private int crc = 0xFFFFFFFF; |
| |
| /** |
| * Creates a new CRC32C object. |
| */ |
| public CRC32C() { |
| } |
| |
| /** |
| * Updates the CRC-32C checksum with the specified byte (the low eight bits |
| * of the argument b). |
| */ |
| @Override |
| public void update(int b) { |
| crc = (crc >>> 8) ^ byteTable[(crc ^ (b & 0xFF)) & 0xFF]; |
| } |
| |
| /** |
| * Updates the CRC-32C checksum with the specified array of bytes. |
| * |
| * @throws ArrayIndexOutOfBoundsException |
| * if {@code off} is negative, or {@code len} is negative, or |
| * {@code off+len} is negative or greater than the length of |
| * the array {@code b}. |
| */ |
| @Override |
| public void update(byte[] b, int off, int len) { |
| if (b == null) { |
| throw new NullPointerException(); |
| } |
| if (off < 0 || len < 0 || off > b.length - len) { |
| throw new ArrayIndexOutOfBoundsException(); |
| } |
| crc = updateBytes(crc, b, off, (off + len)); |
| } |
| |
| /** |
| * Updates the CRC-32C checksum with the bytes from the specified buffer. |
| * |
| * The checksum is updated with the remaining bytes in the buffer, starting |
| * at the buffer's position. Upon return, the buffer's position will be |
| * updated to its limit; its limit will not have been changed. |
| */ |
| @Override |
| public void update(ByteBuffer buffer) { |
| int pos = buffer.position(); |
| int limit = buffer.limit(); |
| assert (pos <= limit); |
| int rem = limit - pos; |
| if (rem <= 0) { |
| return; |
| } |
| |
| if (buffer.isDirect()) { |
| try { |
| crc = updateDirectByteBuffer(crc, ((DirectBuffer) buffer).address(), |
| pos, limit); |
| } finally { |
| Reference.reachabilityFence(buffer); |
| } |
| } else if (buffer.hasArray()) { |
| crc = updateBytes(crc, buffer.array(), pos + buffer.arrayOffset(), |
| limit + buffer.arrayOffset()); |
| } else { |
| byte[] b = new byte[Math.min(buffer.remaining(), 4096)]; |
| while (buffer.hasRemaining()) { |
| int length = Math.min(buffer.remaining(), b.length); |
| buffer.get(b, 0, length); |
| update(b, 0, length); |
| } |
| } |
| buffer.position(limit); |
| } |
| |
| /** |
| * Resets CRC-32C to initial value. |
| */ |
| @Override |
| public void reset() { |
| crc = 0xFFFFFFFF; |
| } |
| |
| /** |
| * Returns CRC-32C value. |
| */ |
| @Override |
| public long getValue() { |
| return (~crc) & 0xFFFFFFFFL; |
| } |
| |
| /** |
| * Updates the CRC-32C checksum with the specified array of bytes. |
| */ |
| @IntrinsicCandidate |
| private static int updateBytes(int crc, byte[] b, int off, int end) { |
| |
| // Do only byte reads for arrays so short they can't be aligned |
| // or if bytes are stored with a larger witdh than one byte.,% |
| if (end - off >= 8 && Unsafe.ARRAY_BYTE_INDEX_SCALE == 1) { |
| |
| // align on 8 bytes |
| int alignLength |
| = (8 - ((Unsafe.ARRAY_BYTE_BASE_OFFSET + off) & 0x7)) & 0x7; |
| for (int alignEnd = off + alignLength; off < alignEnd; off++) { |
| crc = (crc >>> 8) ^ byteTable[(crc ^ b[off]) & 0xFF]; |
| } |
| |
| if (ByteOrder.nativeOrder() == ByteOrder.BIG_ENDIAN) { |
| crc = Integer.reverseBytes(crc); |
| } |
| |
| // slicing-by-8 |
| for (; off < (end - Long.BYTES); off += Long.BYTES) { |
| int firstHalf; |
| int secondHalf; |
| if (Unsafe.ADDRESS_SIZE == 4) { |
| // On 32 bit platforms read two ints instead of a single 64bit long |
| firstHalf = UNSAFE.getInt(b, (long)Unsafe.ARRAY_BYTE_BASE_OFFSET + off); |
| secondHalf = UNSAFE.getInt(b, (long)Unsafe.ARRAY_BYTE_BASE_OFFSET + off |
| + Integer.BYTES); |
| } else { |
| long value = UNSAFE.getLong(b, (long)Unsafe.ARRAY_BYTE_BASE_OFFSET + off); |
| if (ByteOrder.nativeOrder() == ByteOrder.LITTLE_ENDIAN) { |
| firstHalf = (int) value; |
| secondHalf = (int) (value >>> 32); |
| } else { // ByteOrder.BIG_ENDIAN |
| firstHalf = (int) (value >>> 32); |
| secondHalf = (int) value; |
| } |
| } |
| crc ^= firstHalf; |
| if (ByteOrder.nativeOrder() == ByteOrder.LITTLE_ENDIAN) { |
| crc = byteTable7[crc & 0xFF] |
| ^ byteTable6[(crc >>> 8) & 0xFF] |
| ^ byteTable5[(crc >>> 16) & 0xFF] |
| ^ byteTable4[crc >>> 24] |
| ^ byteTable3[secondHalf & 0xFF] |
| ^ byteTable2[(secondHalf >>> 8) & 0xFF] |
| ^ byteTable1[(secondHalf >>> 16) & 0xFF] |
| ^ byteTable0[secondHalf >>> 24]; |
| } else { // ByteOrder.BIG_ENDIAN |
| crc = byteTable0[secondHalf & 0xFF] |
| ^ byteTable1[(secondHalf >>> 8) & 0xFF] |
| ^ byteTable2[(secondHalf >>> 16) & 0xFF] |
| ^ byteTable3[secondHalf >>> 24] |
| ^ byteTable4[crc & 0xFF] |
| ^ byteTable5[(crc >>> 8) & 0xFF] |
| ^ byteTable6[(crc >>> 16) & 0xFF] |
| ^ byteTable7[crc >>> 24]; |
| } |
| } |
| |
| if (ByteOrder.nativeOrder() == ByteOrder.BIG_ENDIAN) { |
| crc = Integer.reverseBytes(crc); |
| } |
| } |
| |
| // Tail |
| for (; off < end; off++) { |
| crc = (crc >>> 8) ^ byteTable[(crc ^ b[off]) & 0xFF]; |
| } |
| |
| return crc; |
| } |
| |
| /** |
| * Updates the CRC-32C checksum reading from the specified address. |
| */ |
| @IntrinsicCandidate |
| private static int updateDirectByteBuffer(int crc, long address, |
| int off, int end) { |
| |
| // Do only byte reads for arrays so short they can't be aligned |
| if (end - off >= 8) { |
| |
| // align on 8 bytes |
| int alignLength = (8 - (int) ((address + off) & 0x7)) & 0x7; |
| for (int alignEnd = off + alignLength; off < alignEnd; off++) { |
| crc = (crc >>> 8) |
| ^ byteTable[(crc ^ UNSAFE.getByte(address + off)) & 0xFF]; |
| } |
| |
| if (ByteOrder.nativeOrder() == ByteOrder.BIG_ENDIAN) { |
| crc = Integer.reverseBytes(crc); |
| } |
| |
| // slicing-by-8 |
| for (; off <= (end - Long.BYTES); off += Long.BYTES) { |
| // Always reading two ints as reading a long followed by |
| // shifting and casting was slower. |
| int firstHalf = UNSAFE.getInt(address + off); |
| int secondHalf = UNSAFE.getInt(address + off + Integer.BYTES); |
| crc ^= firstHalf; |
| if (ByteOrder.nativeOrder() == ByteOrder.LITTLE_ENDIAN) { |
| crc = byteTable7[crc & 0xFF] |
| ^ byteTable6[(crc >>> 8) & 0xFF] |
| ^ byteTable5[(crc >>> 16) & 0xFF] |
| ^ byteTable4[crc >>> 24] |
| ^ byteTable3[secondHalf & 0xFF] |
| ^ byteTable2[(secondHalf >>> 8) & 0xFF] |
| ^ byteTable1[(secondHalf >>> 16) & 0xFF] |
| ^ byteTable0[secondHalf >>> 24]; |
| } else { // ByteOrder.BIG_ENDIAN |
| crc = byteTable0[secondHalf & 0xFF] |
| ^ byteTable1[(secondHalf >>> 8) & 0xFF] |
| ^ byteTable2[(secondHalf >>> 16) & 0xFF] |
| ^ byteTable3[secondHalf >>> 24] |
| ^ byteTable4[crc & 0xFF] |
| ^ byteTable5[(crc >>> 8) & 0xFF] |
| ^ byteTable6[(crc >>> 16) & 0xFF] |
| ^ byteTable7[crc >>> 24]; |
| } |
| } |
| |
| if (ByteOrder.nativeOrder() == ByteOrder.BIG_ENDIAN) { |
| crc = Integer.reverseBytes(crc); |
| } |
| } |
| |
| // Tail |
| for (; off < end; off++) { |
| crc = (crc >>> 8) |
| ^ byteTable[(crc ^ UNSAFE.getByte(address + off)) & 0xFF]; |
| } |
| |
| return crc; |
| } |
| } |
