Re: [xz-devel] java crc64 implementation

[Brett Okken]

Here is a slice by 4 implementation. It goes byte by byte to easily be
compatible with older jdks. Performance wise, it is pretty comparable
to the java port of Adler's stackoverflow implementation:

Benchmark                     Mode  Cnt      Score     Error  Units
Hash64Benchmark.adler         avgt    5   6850.172 ± 251.528  ns/op
Hash64Benchmark.crc64         avgt    5  16347.986 ±  53.702  ns/op
Hash64Benchmark.slice4        avgt    5   6842.010 ± 393.149  ns/op

package org.tukaani.xz.check;

public class CRC64 extends Check {
    private static final long[][] TABLE = new long[4][256];

    static {
        final long poly64 = 0xC96C5795D7870F42L;
        for (int s = 0; s < 4; ++s) {
            for (int b = 0; b < 256; ++b) {
                long r = s == 0 ? b : TABLE[s-1][b];
                for (int i=0; i< 8; ++i) {
                    if ((r & 1) == 1) {
                        r = (r >>> 1) ^ poly64;
                    } else {
                        r >>>= 1;
                    }
                }
                TABLE[s][b] = r;
            }
        }
    }

    private long crc = -1;

    public CRC64() {
        size = 8;
        name = "CRC64";
    }

    @Override
    public void update(byte[] buf, int off, int len) {
        final int end = off + len;
        int i=off;
        for (int j = end-3; i<j; i += 4) {
            crc = TABLE[3][(int) ((crc & 0xFF) ^ (buf[i] & 0xFF))] ^
                  TABLE[2][(int) (((crc >>> 8) & 0xFF) ^ (buf[i + 1] & 0XFF))] ^
                  (crc >>> 32) ^
                  TABLE[1][(int) (((crc >>> 16) & 0xFF) ^ (buf[i + 2]
& 0XFF))] ^
                  TABLE[0][(int) (((crc >>> 24) & 0xFF) ^ (buf[i + 3] & 0XFF))];
        }
        for (; i<end; ++i) {
            crc = TABLE[0][(buf[i] ^ (int) crc) & 0xFF] ^ (crc >>> 8);
        }
    }

    @Override
    public byte[] finish() {
        long value = ~crc;
        crc = -1;

        byte[] buf = new byte[8];
        for (int i = 0; i < buf.length; ++i)
            buf[i] = (byte)(value >> (i * 8));

        return buf;
    }
}