1 using System;
2 using ICSharpCode.SharpZipLib.Zip.Compression.Streams;
3 
4 namespace ICSharpCode.SharpZipLib.Zip.Compression
5 {
6 	/// <summary>
7 	/// Huffman tree used for inflation
8 	/// </summary>
9 	public class InflaterHuffmanTree
10 	{
11 		#region Constants
12 		const int MAX_BITLEN = 15;
13 		#endregion
14 
15 		#region Instance Fields
16 		short[] tree;
17 		#endregion
18 
19 		/// <summary>
20 		/// Literal length tree
21 		/// </summary>
22 		public static InflaterHuffmanTree defLitLenTree;
23 
24 		/// <summary>
25 		/// Distance tree
26 		/// </summary>
27 		public static InflaterHuffmanTree defDistTree;
28 
InflaterHuffmanTree()29 		static InflaterHuffmanTree()
30 		{
31 			try {
32 				byte[] codeLengths = new byte[288];
33 				int i = 0;
34 				while (i < 144) {
35 					codeLengths[i++] = 8;
36 				}
37 				while (i < 256) {
38 					codeLengths[i++] = 9;
39 				}
40 				while (i < 280) {
41 					codeLengths[i++] = 7;
42 				}
43 				while (i < 288) {
44 					codeLengths[i++] = 8;
45 				}
46 				defLitLenTree = new InflaterHuffmanTree(codeLengths);
47 
48 				codeLengths = new byte[32];
49 				i = 0;
50 				while (i < 32) {
51 					codeLengths[i++] = 5;
52 				}
53 				defDistTree = new InflaterHuffmanTree(codeLengths);
54 			} catch (Exception) {
55 				throw new SharpZipBaseException("InflaterHuffmanTree: static tree length illegal");
56 			}
57 		}
58 
59 		#region Constructors
60 		/// <summary>
61 		/// Constructs a Huffman tree from the array of code lengths.
62 		/// </summary>
63 		/// <param name = "codeLengths">
64 		/// the array of code lengths
65 		/// </param>
InflaterHuffmanTree(byte[] codeLengths)66 		public InflaterHuffmanTree(byte[] codeLengths)
67 		{
68 			BuildTree(codeLengths);
69 		}
70 		#endregion
71 
BuildTree(byte[] codeLengths)72 		void BuildTree(byte[] codeLengths)
73 		{
74 			int[] blCount = new int[MAX_BITLEN + 1];
75 			int[] nextCode = new int[MAX_BITLEN + 1];
76 
77 			for (int i = 0; i < codeLengths.Length; i++) {
78 				int bits = codeLengths[i];
79 				if (bits > 0) {
80 					blCount[bits]++;
81 				}
82 			}
83 
84 			int code = 0;
85 			int treeSize = 512;
86 			for (int bits = 1; bits <= MAX_BITLEN; bits++) {
87 				nextCode[bits] = code;
88 				code += blCount[bits] << (16 - bits);
89 				if (bits >= 10) {
90 					/* We need an extra table for bit lengths >= 10. */
91 					int start = nextCode[bits] & 0x1ff80;
92 					int end = code & 0x1ff80;
93 					treeSize += (end - start) >> (16 - bits);
94 				}
95 			}
96 
97 			/* -jr comment this out! doesnt work for dynamic trees and pkzip 2.04g
98 						if (code != 65536)
99 						{
100 							throw new SharpZipBaseException("Code lengths don't add up properly.");
101 						}
102 			*/
103 			/* Now create and fill the extra tables from longest to shortest
104 			* bit len.  This way the sub trees will be aligned.
105 			*/
106 			tree = new short[treeSize];
107 			int treePtr = 512;
108 			for (int bits = MAX_BITLEN; bits >= 10; bits--) {
109 				int end = code & 0x1ff80;
110 				code -= blCount[bits] << (16 - bits);
111 				int start = code & 0x1ff80;
112 				for (int i = start; i < end; i += 1 << 7) {
113 					tree[DeflaterHuffman.BitReverse(i)] = (short)((-treePtr << 4) | bits);
114 					treePtr += 1 << (bits - 9);
115 				}
116 			}
117 
118 			for (int i = 0; i < codeLengths.Length; i++) {
119 				int bits = codeLengths[i];
120 				if (bits == 0) {
121 					continue;
122 				}
123 				code = nextCode[bits];
124 				int revcode = DeflaterHuffman.BitReverse(code);
125 				if (bits <= 9) {
126 					do {
127 						tree[revcode] = (short)((i << 4) | bits);
128 						revcode += 1 << bits;
129 					} while (revcode < 512);
130 				} else {
131 					int subTree = tree[revcode & 511];
132 					int treeLen = 1 << (subTree & 15);
133 					subTree = -(subTree >> 4);
134 					do {
135 						tree[subTree | (revcode >> 9)] = (short)((i << 4) | bits);
136 						revcode += 1 << bits;
137 					} while (revcode < treeLen);
138 				}
139 				nextCode[bits] = code + (1 << (16 - bits));
140 			}
141 
142 		}
143 
144 		/// <summary>
145 		/// Reads the next symbol from input.  The symbol is encoded using the
146 		/// huffman tree.
147 		/// </summary>
148 		/// <param name="input">
149 		/// input the input source.
150 		/// </param>
151 		/// <returns>
152 		/// the next symbol, or -1 if not enough input is available.
153 		/// </returns>
GetSymbol(StreamManipulator input)154 		public int GetSymbol(StreamManipulator input)
155 		{
156 			int lookahead, symbol;
157 			if ((lookahead = input.PeekBits(9)) >= 0) {
158 				if ((symbol = tree[lookahead]) >= 0) {
159 					input.DropBits(symbol & 15);
160 					return symbol >> 4;
161 				}
162 				int subtree = -(symbol >> 4);
163 				int bitlen = symbol & 15;
164 				if ((lookahead = input.PeekBits(bitlen)) >= 0) {
165 					symbol = tree[subtree | (lookahead >> 9)];
166 					input.DropBits(symbol & 15);
167 					return symbol >> 4;
168 				} else {
169 					int bits = input.AvailableBits;
170 					lookahead = input.PeekBits(bits);
171 					symbol = tree[subtree | (lookahead >> 9)];
172 					if ((symbol & 15) <= bits) {
173 						input.DropBits(symbol & 15);
174 						return symbol >> 4;
175 					} else {
176 						return -1;
177 					}
178 				}
179 			} else {
180 				int bits = input.AvailableBits;
181 				lookahead = input.PeekBits(bits);
182 				symbol = tree[lookahead];
183 				if (symbol >= 0 && (symbol & 15) <= bits) {
184 					input.DropBits(symbol & 15);
185 					return symbol >> 4;
186 				} else {
187 					return -1;
188 				}
189 			}
190 		}
191 	}
192 }
193 
194