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://gitbox.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://gitbox.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://gitbox.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
059    /** Set to true when the state array has been updated since the last reset. */
060    private boolean stateUpdated;
061
062    /**
063     * Creates an XXHash32 instance with a seed of 0.
064     */
065    public XXHash32() {
066        this(0);
067    }
068
069    /**
070     * Creates an XXHash32 instance.
071     * @param seed the seed to use
072     */
073    public XXHash32(final int seed) {
074        this.seed = seed;
075        initializeState();
076    }
077
078    @Override
079    public void reset() {
080        initializeState();
081        totalLen = 0;
082        pos = 0;
083        stateUpdated = false;
084    }
085
086    @Override
087    public void update(final int b) {
088        oneByte[0] = (byte) (b & 0xff);
089        update(oneByte, 0, 1);
090    }
091
092    @Override
093    public void update(final byte[] b, int off, final int len) {
094        if (len <= 0) {
095            return;
096        }
097        totalLen += len;
098
099        final int end = off + len;
100
101        // Check if the unprocessed bytes and new bytes can fill a block of 16.
102        // Make this overflow safe in the event that len is Integer.MAX_VALUE.
103        // Equivalent to: (pos + len < BUF_SIZE)
104        if (pos + len - BUF_SIZE < 0) {
105            System.arraycopy(b, off, buffer, pos, len);
106            pos += len;
107            return;
108        }
109
110        // Process left-over bytes with new bytes
111        if (pos > 0) {
112            final int size = BUF_SIZE - pos;
113            System.arraycopy(b, off, buffer, pos, size);
114            process(buffer, 0);
115            off += size;
116        }
117
118        final int limit = end - BUF_SIZE;
119        while (off <= limit) {
120            process(b, off);
121            off += BUF_SIZE;
122        }
123
124        // Handle left-over bytes
125        if (off < end) {
126            pos = end - off;
127            System.arraycopy(b, off, buffer, 0, pos);
128        } else {
129            pos = 0;
130        }
131    }
132
133    @Override
134    public long getValue() {
135        int hash;
136        if (stateUpdated) {
137            // Hash with the state
138            hash =
139                rotateLeft(state[0],  1) +
140                rotateLeft(state[1],  7) +
141                rotateLeft(state[2], 12) +
142                rotateLeft(state[3], 18);
143        } else {
144            // Hash using the original seed from position 2
145            hash = state[2] + PRIME5;
146        }
147        hash += totalLen;
148
149        int idx = 0;
150        final int limit = pos - 4;
151        for (; idx <= limit; idx += 4) {
152            hash = rotateLeft(hash + getInt(buffer, idx) * PRIME3, 17) * PRIME4;
153        }
154        while (idx < pos) {
155            hash = rotateLeft(hash + (buffer[idx++] & 0xff) * PRIME5, 11) * PRIME1;
156        }
157
158        hash ^= hash >>> 15;
159        hash *= PRIME2;
160        hash ^= hash >>> 13;
161        hash *= PRIME3;
162        hash ^= hash >>> 16;
163        return hash & 0xffffffffL;
164    }
165
166    /**
167     * Gets the little-endian int from 4 bytes starting at the specified index.
168     *
169     * @param buffer The data
170     * @param idx The index
171     * @return The little-endian int
172     */
173    private static int getInt(final byte[] buffer, final int idx) {
174        return ((buffer[idx    ] & 0xff)      ) |
175               ((buffer[idx + 1] & 0xff) <<  8) |
176               ((buffer[idx + 2] & 0xff) << 16) |
177               ((buffer[idx + 3] & 0xff) << 24);
178    }
179
180    private void initializeState() {
181        state[0] = seed + PRIME1 + PRIME2;
182        state[1] = seed + PRIME2;
183        state[2] = seed;
184        state[3] = seed - PRIME1;
185    }
186
187    private void process(final byte[] b, final int offset) {
188        // local shadows for performance
189        int s0 = state[0];
190        int s1 = state[1];
191        int s2 = state[2];
192        int s3 = state[3];
193
194        s0 = rotateLeft(s0 + getInt(b, offset) * PRIME2, ROTATE_BITS) * PRIME1;
195        s1 = rotateLeft(s1 + getInt(b, offset + 4) * PRIME2, ROTATE_BITS) * PRIME1;
196        s2 = rotateLeft(s2 + getInt(b, offset + 8) * PRIME2, ROTATE_BITS) * PRIME1;
197        s3 = rotateLeft(s3 + getInt(b, offset + 12) * PRIME2, ROTATE_BITS) * PRIME1;
198
199        state[0] = s0;
200        state[1] = s1;
201        state[2] = s2;
202        state[3] = s3;
203
204        stateUpdated = true;
205    }
206}