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}