/*
 * Copyright (c) 2014, 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.nio.ByteBuffer;
import java.nio.ByteOrder;
import sun.misc.Unsafe;
import sun.nio.ch.DirectBuffer;

/**
 * <P>
 * A class that can be used to compute the CRC-32C of a data stream.</P>
 *
 * <P>
 * CRC-32C is defined in <a href="http://tools.ietf.org/html/rfc3720">IETF 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>
 *
 * @see Checksum
 * @since 1.9
 */
public class CRC32C implements Checksum {

    /**
     * Calculated CRC-32C value
     */
    private int crc = 0xFFFFFFFF;

    // CRC-32C Polynom
    private final static int CRC32C_POLY = 0x1EDC6F41;

    /**
     * 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
     */
    private transient final static Unsafe UNSAFE = Unsafe.getUnsafe();
    private transient final static ByteOrder ENDIAN = ByteOrder.nativeOrder().equals(ByteOrder.BIG_ENDIAN)
            ? ByteOrder.BIG_ENDIAN : ByteOrder.LITTLE_ENDIAN;

    // Lookup tables
    private transient final static int[][] byteTables = new int[8][256];
    private transient final static int[] byteTable;
    private transient final static int[] byteTable0 = byteTables[0];
    private transient final static int[] byteTable1 = byteTables[1];
    private transient final static int[] byteTable2 = byteTables[2];
    private transient final static int[] byteTable3 = byteTables[3];
    private transient final static int[] byteTable4 = byteTables[4];
    private transient final static int[] byteTable5 = byteTables[5];
    private transient final static int[] byteTable6 = byteTables[6];
    private transient final static int[] byteTable7 = byteTables[7];

    static {
        // Generate lookup tables
        for (int index = 0; index < byteTables[0].length; index++) {
            int r = reflect(index);
            for (int i = 0; i < Byte.SIZE; i++) {
                if ((r & 0x080000000) != 0) {
                    r = (r << 1) ^ CRC32C_POLY;
                } else {
                    r <<= 1;
                }
            }
            byteTables[0][index] = reflect(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 (ENDIAN == 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] = swap32(table[index]);
                }
            }
        }
    }

    /**
     * Creates a new CRC32C object.
     */
    public CRC32C() {
    }

    /**
     * Updates the CRC-32C checksum with the specified byte (the low eight bits
     * of the argument b).
     *
     * @param b the byte to update the checksum with
     */
    @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 greater than the length of
     * the array {@code b}
     *
     * @param b the byte array to update the checksum with
     * @param off the start offset of the data
     * @param len the number of bytes to use for the update
     */
    @Override
    public void update(byte[] b, int off, int len) {
        if (b == null) {
            throw new NullPointerException();
        }
        if (off < 0 || len < 0 || (off + len) > b.length) {
            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 using
     * buffer.{@link java.nio.Buffer#remaining() remaining()} bytes starting at
     * buffer.{@link java.nio.Buffer#position() position()} Upon return, the
     * buffer's position will be updated to its limit; its limit will not have
     * been changed.
     *
     * @param buffer the ByteBuffer to update the checksum with
     */
    @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 instanceof DirectBuffer) {
            crc = updateDirectByteBuffer(crc, ((DirectBuffer) buffer).address(), pos, limit);
        } else if (buffer.hasArray()) {
            crc = updateBytes(crc, buffer.array(), pos + buffer.arrayOffset(), limit + buffer.arrayOffset());
        } else {
            byte[] b = new byte[rem];
            buffer.get(b);
            crc = updateBytes(crc, b, 0, b.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.
     */
    private static int updateBytes(int crc, byte[] b, int off, int end) {

        if (end - off >= 8) {

            // 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 (ENDIAN == ByteOrder.BIG_ENDIAN) {
                crc = swap32(crc);
            }

            // slicing-by-8
            for (; off < (end - Unsafe.ARRAY_LONG_INDEX_SCALE); off += Unsafe.ARRAY_LONG_INDEX_SCALE) {
                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, Unsafe.ARRAY_BYTE_BASE_OFFSET + off);
                    secondHalf = UNSAFE.getInt(b, Unsafe.ARRAY_BYTE_BASE_OFFSET + off + Unsafe.ARRAY_INT_INDEX_SCALE);
                } else {
                    long value = UNSAFE.getLong(b, Unsafe.ARRAY_BYTE_BASE_OFFSET + off);
                    if (ENDIAN == ByteOrder.LITTLE_ENDIAN) {
                        firstHalf = (int) (value & 0xFFFFFFFF);
                        secondHalf = (int) (value >>> 32);
                    } else { // ByteOrder.BIG_ENDIAN
                        firstHalf = (int) (value >>> 32);
                        secondHalf = (int) (value & 0xFFFFFFFF);
                    }
                }
                crc ^= firstHalf;
                if (ENDIAN == 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 (ENDIAN == ByteOrder.BIG_ENDIAN) {
                crc = swap32(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.
     */
    private static int updateDirectByteBuffer(int crc, long address, int off, int end) {

        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 (ENDIAN == ByteOrder.BIG_ENDIAN) {
                crc = swap32(crc);
            }

            // slicing-by-8
            for (; off < (end - Unsafe.ARRAY_LONG_INDEX_SCALE); off += Unsafe.ARRAY_LONG_INDEX_SCALE) {
                int firstHalf = UNSAFE.getInt(address + off);
                int secondHalf = UNSAFE.getInt(address + off + Unsafe.ARRAY_INT_INDEX_SCALE);
                crc ^= firstHalf;
                if (ENDIAN == 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 (ENDIAN == ByteOrder.BIG_ENDIAN) {
                crc = swap32(crc);
            }
        }
        
        // Tail
        for (; off < end; off++) {
            crc = (crc >>> 8) ^ byteTable[(crc ^ UNSAFE.getByte(address + off)) & 0xFF];
        }

        return crc;
    }

    /**
     * Swap the bytes in a 32 bit quantity.
     */
    private static int swap32(int value) {
        return ((value >>> 24) + ((value >>> 8) & 0xFF00) + ((value & 0xFF00) << 8) + (value << 24));
    }

    /**
     * Reflect a 32 bit quantity.
     */
    private static int reflect(int b) {
        return (((b >>> 31) & 0x000000001)
                | ((b >>> 29) & 0x000000002)
                | ((b >>> 27) & 0x000000004)
                | ((b >>> 25) & 0x000000008)
                | ((b >>> 23) & 0x000000010)
                | ((b >>> 21) & 0x000000020)
                | ((b >>> 19) & 0x000000040)
                | ((b >>> 17) & 0x000000080)
                | ((b >>> 15) & 0x000000100)
                | ((b >>> 13) & 0x000000200)
                | ((b >>> 11) & 0x000000400)
                | ((b >>> 9) & 0x000000800)
                | ((b >>> 7) & 0x000001000)
                | ((b >>> 5) & 0x000002000)
                | ((b >>> 3) & 0x000004000)
                | ((b >>> 1) & 0x000008000)
                | ((b << 1) & 0x000010000)
                | ((b << 3) & 0x000020000)
                | ((b << 5) & 0x000040000)
                | ((b << 7) & 0x000080000)
                | ((b << 9) & 0x000100000)
                | ((b << 11) & 0x000200000)
                | ((b << 13) & 0x000400000)
                | ((b << 15) & 0x000800000)
                | ((b << 17) & 0x001000000)
                | ((b << 19) & 0x002000000)
                | ((b << 21) & 0x004000000)
                | ((b << 23) & 0x008000000)
                | ((b << 25) & 0x010000000)
                | ((b << 27) & 0x020000000)
                | ((b << 29) & 0x040000000)
                | ((b << 31) & 0x080000000));
    }
}