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