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}