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 |
|
---|
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 |
|
---|
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 |
|
---|
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 |
|
---|
62 | void putArraysToCache(ArrayCache arrayCache) {
|
---|
63 | arrayCache.putArray(hash4Table);
|
---|
64 | arrayCache.putArray(hash3Table);
|
---|
65 | arrayCache.putArray(hash2Table);
|
---|
66 | }
|
---|
67 |
|
---|
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 |
|
---|
79 | int getHash2Pos() {
|
---|
80 | return hash2Table[hash2Value];
|
---|
81 | }
|
---|
82 |
|
---|
83 | int getHash3Pos() {
|
---|
84 | return hash3Table[hash3Value];
|
---|
85 | }
|
---|
86 |
|
---|
87 | int getHash4Pos() {
|
---|
88 | return hash4Table[hash4Value];
|
---|
89 | }
|
---|
90 |
|
---|
91 | void updateTables(int pos) {
|
---|
92 | hash2Table[hash2Value] = pos;
|
---|
93 | hash3Table[hash3Value] = pos;
|
---|
94 | hash4Table[hash4Value] = pos;
|
---|
95 | }
|
---|
96 |
|
---|
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 | }
|
---|