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 import org.tukaani.xz.ArrayCache; 14 15 final class Hash234 extends CRC32Hash { 16 private static final int HASH_2_SIZE = 1 << 10; 17 private static final int HASH_2_MASK = HASH_2_SIZE - 1; 18 19 private static final int HASH_3_SIZE = 1 << 16; 20 private static final int HASH_3_MASK = HASH_3_SIZE - 1; 21 22 private final int hash4Mask; 23 24 private final int[] hash2Table; 25 private final int[] hash3Table; 26 private final int[] hash4Table; 27 private final int hash4Size; 28 29 private int hash2Value = 0; 30 private int hash3Value = 0; 31 private int hash4Value = 0; 32 getHash4Size(int dictSize)33 static int getHash4Size(int dictSize) { 34 int h = dictSize - 1; 35 h |= h >>> 1; 36 h |= h >>> 2; 37 h |= h >>> 4; 38 h |= h >>> 8; 39 h >>>= 1; 40 h |= 0xFFFF; 41 if (h > (1 << 24)) 42 h >>>= 1; 43 44 return h + 1; 45 } 46 getMemoryUsage(int dictSize)47 static int getMemoryUsage(int dictSize) { 48 // Sizes of the hash arrays + a little extra 49 return (HASH_2_SIZE + HASH_3_SIZE + getHash4Size(dictSize)) 50 / (1024 / 4) + 4; 51 } 52 Hash234(int dictSize, ArrayCache arrayCache)53 Hash234(int dictSize, ArrayCache arrayCache) { 54 hash2Table = arrayCache.getIntArray(HASH_2_SIZE, true); 55 hash3Table = arrayCache.getIntArray(HASH_3_SIZE, true); 56 57 hash4Size = getHash4Size(dictSize); 58 hash4Table = arrayCache.getIntArray(hash4Size, true); 59 hash4Mask = hash4Size - 1; 60 } 61 putArraysToCache(ArrayCache arrayCache)62 void putArraysToCache(ArrayCache arrayCache) { 63 arrayCache.putArray(hash4Table); 64 arrayCache.putArray(hash3Table); 65 arrayCache.putArray(hash2Table); 66 } 67 calcHashes(byte[] buf, int off)68 void calcHashes(byte[] buf, int off) { 69 int temp = crcTable[buf[off] & 0xFF] ^ (buf[off + 1] & 0xFF); 70 hash2Value = temp & HASH_2_MASK; 71 72 temp ^= (buf[off + 2] & 0xFF) << 8; 73 hash3Value = temp & HASH_3_MASK; 74 75 temp ^= crcTable[buf[off + 3] & 0xFF] << 5; 76 hash4Value = temp & hash4Mask; 77 } 78 getHash2Pos()79 int getHash2Pos() { 80 return hash2Table[hash2Value]; 81 } 82 getHash3Pos()83 int getHash3Pos() { 84 return hash3Table[hash3Value]; 85 } 86 getHash4Pos()87 int getHash4Pos() { 88 return hash4Table[hash4Value]; 89 } 90 updateTables(int pos)91 void updateTables(int pos) { 92 hash2Table[hash2Value] = pos; 93 hash3Table[hash3Value] = pos; 94 hash4Table[hash4Value] = pos; 95 } 96 normalize(int normalizeOffset)97 void normalize(int normalizeOffset) { 98 LZEncoder.normalize(hash2Table, HASH_2_SIZE, normalizeOffset); 99 LZEncoder.normalize(hash3Table, HASH_3_SIZE, normalizeOffset); 100 LZEncoder.normalize(hash4Table, hash4Size, normalizeOffset); 101 } 102 } 103