Home | History | Annotate | Download | only in lz 
      1 /*
      2  * 2-, 3-, and 4-byte hashing
      3  *
      4  * Authors: Lasse Collin <lasse.collin (at) 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 
     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 
     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 
     50     Hash234(int dictSize) {
     51         hash4Table = new int[getHash4Size(dictSize)];
     52         hash4Mask = hash4Table.length - 1;
     53     }
     54 
     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 
     66     int getHash2Pos() {
     67         return hash2Table[hash2Value];
     68     }
     69 
     70     int getHash3Pos() {
     71         return hash3Table[hash3Value];
     72     }
     73 
     74     int getHash4Pos() {
     75         return hash4Table[hash4Value];
     76     }
     77 
     78     void updateTables(int pos) {
     79         hash2Table[hash2Value] = pos;
     80         hash3Table[hash3Value] = pos;
     81         hash4Table[hash4Value] = pos;
     82     }
     83 
     84     void normalize(int normalizeOffset) {
     85         LZEncoder.normalize(hash2Table, normalizeOffset);
     86         LZEncoder.normalize(hash3Table, normalizeOffset);
     87         LZEncoder.normalize(hash4Table, normalizeOffset);
     88     }
     89 }
     90