1
2
3
4 package joeq.ClassLib.Common.java.util.zip;
5
6 /***
7 * InflaterHuffmanTree
8 *
9 * @author John Whaley <jwhaley@alum.mit.edu>
10 * @version $Id: InflaterHuffmanTree.java 1451 2004-03-09 06:27:08Z jwhaley $
11 */
12 class InflaterHuffmanTree {
13
14 private static final int MAX_BITLEN = 15;
15 private short[] tree;
16
17 public static InflaterHuffmanTree defLitLenTree, defDistTree;
18
19 static
20 {
21 try
22 {
23 byte[] codeLengths = new byte[288];
24 int i = 0;
25 while (i < 144)
26 codeLengths[i++] = 8;
27 while (i < 256)
28 codeLengths[i++] = 9;
29 while (i < 280)
30 codeLengths[i++] = 7;
31 while (i < 288)
32 codeLengths[i++] = 8;
33 defLitLenTree = new InflaterHuffmanTree(codeLengths);
34
35 codeLengths = new byte[32];
36 i = 0;
37 while (i < 32)
38 codeLengths[i++] = 5;
39 defDistTree = new InflaterHuffmanTree(codeLengths);
40 }
41 catch (java.util.zip.DataFormatException ex)
42 {
43 throw new InternalError
44 ("InflaterHuffmanTree: static tree length illegal");
45 }
46 }
47
48 /***
49 * Constructs a Huffman tree from the array of code lengths.
50 *
51 * @param codeLengths the array of code lengths
52 */
53 public InflaterHuffmanTree(byte[] codeLengths) throws java.util.zip.DataFormatException
54 {
55 buildTree(codeLengths);
56 }
57
58 private void buildTree(byte[] codeLengths) throws java.util.zip.DataFormatException
59 {
60 int[] blCount = new int[MAX_BITLEN+1];
61 int[] nextCode = new int[MAX_BITLEN+1];
62 for (int i = 0; i < codeLengths.length; i++)
63 {
64 int bits = codeLengths[i];
65 if (bits > 0)
66 blCount[bits]++;
67 }
68
69 int code = 0;
70 int treeSize = 512;
71 for (int bits = 1; bits <= MAX_BITLEN; bits++)
72 {
73 nextCode[bits] = code;
74 code += blCount[bits] << (16 - bits);
75 if (bits >= 10)
76 {
77
78 int start = nextCode[bits] & 0x1ff80;
79 int end = code & 0x1ff80;
80 treeSize += (end - start) >> (16 - bits);
81 }
82 }
83 if (code != 65536)
84 throw new java.util.zip.DataFormatException("Code lengths don't add up properly.");
85
86
87
88
89 tree = new short[treeSize];
90 int treePtr = 512;
91 for (int bits = MAX_BITLEN; bits >= 10; bits--)
92 {
93 int end = code & 0x1ff80;
94 code -= blCount[bits] << (16 - bits);
95 int start = code & 0x1ff80;
96 for (int i = start; i < end; i += 1 << 7)
97 {
98 tree[DeflaterHuffman.bitReverse(i)]
99 = (short) ((-treePtr << 4) | bits);
100 treePtr += 1 << (bits-9);
101 }
102 }
103
104 for (int i = 0; i < codeLengths.length; i++)
105 {
106 int bits = codeLengths[i];
107 if (bits == 0)
108 continue;
109 code = nextCode[bits];
110 int revcode = DeflaterHuffman.bitReverse(code);
111 if (bits <= 9)
112 {
113 do
114 {
115 tree[revcode] = (short) ((i << 4) | bits);
116 revcode += 1 << bits;
117 }
118 while (revcode < 512);
119 }
120 else
121 {
122 int subTree = tree[revcode & 511];
123 int treeLen = 1 << (subTree & 15);
124 subTree = -(subTree >> 4);
125 do
126 {
127 tree[subTree | (revcode >> 9)] = (short) ((i << 4) | bits);
128 revcode += 1 << bits;
129 }
130 while (revcode < treeLen);
131 }
132 nextCode[bits] = code + (1 << (16 - bits));
133 }
134 }
135
136 /***
137 * Reads the next symbol from input. The symbol is encoded using the
138 * huffman tree.
139 * @param input the input source.
140 * @return the next symbol, or -1 if not enough input is available.
141 */
142 public int getSymbol(StreamManipulator input) throws java.util.zip.DataFormatException
143 {
144 int lookahead, symbol;
145 if ((lookahead = input.peekBits(9)) >= 0)
146 {
147 if ((symbol = tree[lookahead]) >= 0)
148 {
149 input.dropBits(symbol & 15);
150 return symbol >> 4;
151 }
152 int subtree = -(symbol >> 4);
153 int bitlen = symbol & 15;
154 if ((lookahead = input.peekBits(bitlen)) >= 0)
155 {
156 symbol = tree[subtree | (lookahead >> 9)];
157 input.dropBits(symbol & 15);
158 return symbol >> 4;
159 }
160 else
161 {
162 int bits = input.getAvailableBits();
163 lookahead = input.peekBits(bits);
164 symbol = tree[subtree | (lookahead >> 9)];
165 if ((symbol & 15) <= bits)
166 {
167 input.dropBits(symbol & 15);
168 return symbol >> 4;
169 }
170 else
171 return -1;
172 }
173 }
174 else
175 {
176 int bits = input.getAvailableBits();
177 lookahead = input.peekBits(bits);
178 symbol = tree[lookahead];
179 if (symbol >= 0 && (symbol & 15) <= bits)
180 {
181 input.dropBits(symbol & 15);
182 return symbol >> 4;
183 }
184 else
185 return -1;
186 }
187 }
188 }