XXHash32.java
/*
* Licensed to the Apache Software Foundation (ASF) under one or more
* contributor license agreements. See the NOTICE file distributed with
* this work for additional information regarding copyright ownership.
* The ASF licenses this file to You under the Apache License, Version 2.0
* (the "License"); you may not use this file except in compliance with
* the License. You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
package org.apache.commons.codec.digest;
import static java.lang.Integer.rotateLeft;
import java.util.zip.Checksum;
/**
* Implementation of the xxHash32 hash algorithm.
*
* <p>
* Copied from Commons Compress 1.14 <a href=
* "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>
* </p>
* <p>
* NotThreadSafe
* </p>
*
* @see <a href="https://cyan4973.github.io/xxHash/">xxHash</a>
* @since 1.11
*/
public class XXHash32 implements Checksum {
private static final int BUF_SIZE = 16;
private static final int ROTATE_BITS = 13;
private static final int PRIME1 = (int) 2654435761L;
private static final int PRIME2 = (int) 2246822519L;
private static final int PRIME3 = (int) 3266489917L;
private static final int PRIME4 = 668265263;
private static final int PRIME5 = 374761393;
/**
* Gets the little-endian int from 4 bytes starting at the specified index.
*
* @param buffer The data
* @param idx The index
* @return The little-endian int
*/
private static int getInt(final byte[] buffer, final int idx) {
return buffer[idx ] & 0xff |
(buffer[idx + 1] & 0xff) << 8 |
(buffer[idx + 2] & 0xff) << 16 |
(buffer[idx + 3] & 0xff) << 24;
}
private final byte[] oneByte = new byte[1];
private final int[] state = new int[4];
// Note: the code used to use ByteBuffer but the manual method is 50% faster
// See: https://gitbox.apache.org/repos/asf/commons-compress/diff/2f56fb5c
private final byte[] buffer = new byte[BUF_SIZE];
private final int seed;
private int totalLen;
private int pos;
/** Sets to true when the state array has been updated since the last reset. */
private boolean stateUpdated;
/**
* Creates an XXHash32 instance with a seed of 0.
*/
public XXHash32() {
this(0);
}
/**
* Creates an XXHash32 instance.
* @param seed the seed to use
*/
public XXHash32(final int seed) {
this.seed = seed;
initializeState();
}
@Override
public long getValue() {
int hash;
if (stateUpdated) {
// Hash with the state
hash =
rotateLeft(state[0], 1) +
rotateLeft(state[1], 7) +
rotateLeft(state[2], 12) +
rotateLeft(state[3], 18);
} else {
// Hash using the original seed from position 2
hash = state[2] + PRIME5;
}
hash += totalLen;
int idx = 0;
final int limit = pos - 4;
for (; idx <= limit; idx += 4) {
hash = rotateLeft(hash + getInt(buffer, idx) * PRIME3, 17) * PRIME4;
}
while (idx < pos) {
hash = rotateLeft(hash + (buffer[idx++] & 0xff) * PRIME5, 11) * PRIME1;
}
hash ^= hash >>> 15;
hash *= PRIME2;
hash ^= hash >>> 13;
hash *= PRIME3;
hash ^= hash >>> 16;
return hash & 0xffffffffL;
}
private void initializeState() {
state[0] = seed + PRIME1 + PRIME2;
state[1] = seed + PRIME2;
state[2] = seed;
state[3] = seed - PRIME1;
}
private void process(final byte[] b, final int offset) {
// local shadows for performance
int s0 = state[0];
int s1 = state[1];
int s2 = state[2];
int s3 = state[3];
s0 = rotateLeft(s0 + getInt(b, offset) * PRIME2, ROTATE_BITS) * PRIME1;
s1 = rotateLeft(s1 + getInt(b, offset + 4) * PRIME2, ROTATE_BITS) * PRIME1;
s2 = rotateLeft(s2 + getInt(b, offset + 8) * PRIME2, ROTATE_BITS) * PRIME1;
s3 = rotateLeft(s3 + getInt(b, offset + 12) * PRIME2, ROTATE_BITS) * PRIME1;
state[0] = s0;
state[1] = s1;
state[2] = s2;
state[3] = s3;
stateUpdated = true;
}
@Override
public void reset() {
initializeState();
totalLen = 0;
pos = 0;
stateUpdated = false;
}
@Override
public void update(final byte[] b, int off, final int len) {
if (len <= 0) {
return;
}
totalLen += len;
final int end = off + len;
// Check if the unprocessed bytes and new bytes can fill a block of 16.
// Make this overflow safe in the event that len is Integer.MAX_VALUE.
// Equivalent to: (pos + len < BUF_SIZE)
if (pos + len - BUF_SIZE < 0) {
System.arraycopy(b, off, buffer, pos, len);
pos += len;
return;
}
// Process left-over bytes with new bytes
if (pos > 0) {
final int size = BUF_SIZE - pos;
System.arraycopy(b, off, buffer, pos, size);
process(buffer, 0);
off += size;
}
final int limit = end - BUF_SIZE;
while (off <= limit) {
process(b, off);
off += BUF_SIZE;
}
// Handle left-over bytes
if (off < end) {
pos = end - off;
System.arraycopy(b, off, buffer, 0, pos);
} else {
pos = 0;
}
}
@Override
public void update(final int b) {
oneByte[0] = (byte) (b & 0xff);
update(oneByte, 0, 1);
}
}