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