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
11package org.tukaani.xz.lz;
12
13final 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