    001/*
    002 * Licensed to the Apache Software Foundation (ASF) under one
    003 * or more contributor license agreements.  See the NOTICE file
    004 * distributed with this work for additional information
    005 * regarding copyright ownership.  The ASF licenses this file
    006 * to you under the Apache License, Version 2.0 (the
    007 * "License"); you may not use this file except in compliance
    008 * with the License.  You may obtain a copy of the License at
    009 *
    010 * http://www.apache.org/licenses/LICENSE-2.0
    011 *
    012 * Unless required by applicable law or agreed to in writing,
    013 * software distributed under the License is distributed on an
    014 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
    015 * KIND, either express or implied.  See the License for the
    016 * specific language governing permissions and limitations
    017 * under the License.
    018 */
    019package org.apache.commons.compress.compressors.lz4;
    020
    021import static java.lang.Integer.rotateLeft;
    022import static org.apache.commons.compress.utils.ByteUtils.fromLittleEndian;
    023
    024import java.util.zip.Checksum;
    025
    026/**
    027 * Implementation of the xxhash32 hash algorithm.
    028 *
    029 * @see <a href="http://cyan4973.github.io/xxHash/">xxHash</a>
    030 * @NotThreadSafe
    031 * @since 1.14
    032 */
    033public class XXHash32 implements Checksum {
    034
    035    private static final int BUF_SIZE = 16;
    036    private static final int ROTATE_BITS = 13;
    037
    038    private static final int PRIME1 = (int) 2654435761L;
    039    private static final int PRIME2 = (int) 2246822519L;
    040    private static final int PRIME3 = (int) 3266489917L;
    041    private static final int PRIME4 =  668265263;
    042    private static final int PRIME5 =  374761393;
    043
    044    private static int getInt(final byte[] buffer, final int idx) {
    045        return (int) (fromLittleEndian(buffer, idx, 4) & 0xffffffffL);
    046    }
    047    private final byte[] oneByte = new byte[1];
    048    private final int[] state = new int[4];
    049    // Note: the code used to use ByteBuffer but the manual method is 50% faster
    050    // See: https://gitbox.apache.org/repos/asf/commons-compress/diff/2f56fb5c
    051    private final byte[] buffer = new byte[BUF_SIZE];
    052
    053    private final int seed;
    054    private int totalLen;
    055
    056    private int pos;
    057
    058    /**
    059     * Creates an XXHash32 instance with a seed of 0.
    060     */
    061    public XXHash32() {
    062        this(0);
    063    }
    064
    065    /**
    066     * Creates an XXHash32 instance.
    067     * @param seed the seed to use
    068     */
    069    public XXHash32(final int seed) {
    070        this.seed = seed;
    071        initializeState();
    072    }
    073
    074    @Override
    075    public long getValue() {
    076        int hash;
    077        if (totalLen > BUF_SIZE) {
    078            hash =
    079                rotateLeft(state[0],  1) +
    080                rotateLeft(state[1],  7) +
    081                rotateLeft(state[2], 12) +
    082                rotateLeft(state[3], 18);
    083        } else {
    084            hash = state[2] + PRIME5;
    085        }
    086        hash += totalLen;
    087
    088        int idx = 0;
    089        final int limit = pos - 4;
    090        for (; idx <= limit; idx += 4) {
    091            hash = rotateLeft(hash + getInt(buffer, idx) * PRIME3, 17) * PRIME4;
    092        }
    093        while (idx < pos) {
    094            hash = rotateLeft(hash + (buffer[idx++] & 0xff) * PRIME5, 11) * PRIME1;
    095        }
    096
    097        hash ^= hash >>> 15;
    098        hash *= PRIME2;
    099        hash ^= hash >>> 13;
    100        hash *= PRIME3;
    101        hash ^= hash >>> 16;
    102        return hash & 0xffffffffL;
    103    }
    104
    105    private void initializeState() {
    106        state[0] = seed + PRIME1 + PRIME2;
    107        state[1] = seed + PRIME2;
    108        state[2] = seed;
    109        state[3] = seed - PRIME1;
    110    }
    111
    112    private void process(final byte[] b, final int offset) {
    113        // local shadows for performance
    114        int s0 = state[0];
    115        int s1 = state[1];
    116        int s2 = state[2];
    117        int s3 = state[3];
    118
    119        s0 = rotateLeft(s0 + getInt(b, offset) * PRIME2, ROTATE_BITS) * PRIME1;
    120        s1 = rotateLeft(s1 + getInt(b, offset + 4) * PRIME2, ROTATE_BITS) * PRIME1;
    121        s2 = rotateLeft(s2 + getInt(b, offset + 8) * PRIME2, ROTATE_BITS) * PRIME1;
    122        s3 = rotateLeft(s3 + getInt(b, offset + 12) * PRIME2, ROTATE_BITS) * PRIME1;
    123
    124        state[0] = s0;
    125        state[1] = s1;
    126        state[2] = s2;
    127        state[3] = s3;
    128
    129        pos = 0;
    130    }
    131
    132    @Override
    133    public void reset() {
    134        initializeState();
    135        totalLen = 0;
    136        pos = 0;
    137    }
    138
    139    @Override
    140    public void update(final byte[] b, int off, final int len) {
    141        if (len <= 0) {
    142            return;
    143        }
    144        totalLen += len;
    145
    146        final int end = off + len;
    147
    148        if (pos + len < BUF_SIZE) {
    149            System.arraycopy(b, off, buffer, pos, len);
    150            pos += len;
    151            return;
    152        }
    153
    154        if (pos > 0) {
    155            final int size = BUF_SIZE - pos;
    156            System.arraycopy(b, off, buffer, pos, size);
    157            process(buffer, 0);
    158            off += size;
    159        }
    160
    161        final int limit = end - BUF_SIZE;
    162        while (off <= limit) {
    163            process(b, off);
    164            off += BUF_SIZE;
    165        }
    166
    167        if (off < end) {
    168            pos = end - off;
    169            System.arraycopy(b, off, buffer, 0, pos);
    170        }
    171    }
    172
    173    @Override
    174    public void update(final int b) {
    175        oneByte[0] = (byte) (b & 0xff);
    176        update(oneByte, 0, 1);
    177    }
    178}