1 /* 2 * 2-, 3-, and 4-byte hashing 3 * 4 * Authors: Lasse Collin <lasse.collin@tukaani.org> 5 * Igor Pavlov <http://7-zip.org/> 6 * 7 * This file has been put into the public domain. 8 * You can do whatever you want with this file. 9 */ 10 11 package org.tukaani.xz.lz; 12 13 final class Hash234 extends CRC32Hash { 14 private static final int HASH_2_SIZE = 1 << 10; 15 private static final int HASH_2_MASK = HASH_2_SIZE - 1; 16 17 private static final int HASH_3_SIZE = 1 << 16; 18 private static final int HASH_3_MASK = HASH_3_SIZE - 1; 19 20 private final int hash4Mask; 21 22 private final int[] hash2Table = new int[HASH_2_SIZE]; 23 private final int[] hash3Table = new int[HASH_3_SIZE]; 24 private final int[] hash4Table; 25 26 private int hash2Value = 0; 27 private int hash3Value = 0; 28 private int hash4Value = 0; 29 getHash4Size(int dictSize)30 static int getHash4Size(int dictSize) { 31 int h = dictSize - 1; 32 h |= h >>> 1; 33 h |= h >>> 2; 34 h |= h >>> 4; 35 h |= h >>> 8; 36 h >>>= 1; 37 h |= 0xFFFF; 38 if (h > (1 << 24)) 39 h >>>= 1; 40 41 return h + 1; 42 } 43 getMemoryUsage(int dictSize)44 static int getMemoryUsage(int dictSize) { 45 // Sizes of the hash arrays + a little extra 46 return (HASH_2_SIZE + HASH_3_SIZE + getHash4Size(dictSize)) 47 / (1024 / 4) + 4; 48 } 49 Hash234(int dictSize)50 Hash234(int dictSize) { 51 hash4Table = new int[getHash4Size(dictSize)]; 52 hash4Mask = hash4Table.length - 1; 53 } 54 calcHashes(byte[] buf, int off)55 void calcHashes(byte[] buf, int off) { 56 int temp = crcTable[buf[off] & 0xFF] ^ (buf[off + 1] & 0xFF); 57 hash2Value = temp & HASH_2_MASK; 58 59 temp ^= (buf[off + 2] & 0xFF) << 8; 60 hash3Value = temp & HASH_3_MASK; 61 62 temp ^= crcTable[buf[off + 3] & 0xFF] << 5; 63 hash4Value = temp & hash4Mask; 64 } 65 getHash2Pos()66 int getHash2Pos() { 67 return hash2Table[hash2Value]; 68 } 69 getHash3Pos()70 int getHash3Pos() { 71 return hash3Table[hash3Value]; 72 } 73 getHash4Pos()74 int getHash4Pos() { 75 return hash4Table[hash4Value]; 76 } 77 updateTables(int pos)78 void updateTables(int pos) { 79 hash2Table[hash2Value] = pos; 80 hash3Table[hash3Value] = pos; 81 hash4Table[hash4Value] = pos; 82 } 83 normalize(int normalizeOffset)84 void normalize(int normalizeOffset) { 85 LZEncoder.normalize(hash2Table, normalizeOffset); 86 LZEncoder.normalize(hash3Table, normalizeOffset); 87 LZEncoder.normalize(hash4Table, normalizeOffset); 88 } 89 } 90