1 // InflaterHuffmanTree.cs 2 // Copyright (C) 2001 Mike Krueger 3 // 4 // This file was translated from java, it was part of the GNU Classpath 5 // Copyright (C) 2001 Free Software Foundation, Inc. 6 // 7 // This program is free software; you can redistribute it and/or 8 // modify it under the terms of the GNU General Public License 9 // as published by the Free Software Foundation; either version 2 10 // of the License, or (at your option) any later version. 11 // 12 // This program is distributed in the hope that it will be useful, 13 // but WITHOUT ANY WARRANTY; without even the implied warranty of 14 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 15 // GNU General Public License for more details. 16 // 17 // You should have received a copy of the GNU General Public License 18 // along with this program; if not, write to the Free Software 19 // Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. 20 // 21 // Linking this library statically or dynamically with other modules is 22 // making a combined work based on this library. Thus, the terms and 23 // conditions of the GNU General Public License cover the whole 24 // combination. 25 // 26 // As a special exception, the copyright holders of this library give you 27 // permission to link this library with independent modules to produce an 28 // executable, regardless of the license terms of these independent 29 // modules, and to copy and distribute the resulting executable under 30 // terms of your choice, provided that you also meet, for each linked 31 // independent module, the terms and conditions of the license of that 32 // module. An independent module is a module which is not derived from 33 // or based on this library. If you modify this library, you may extend 34 // this exception to your version of the library, but you are not 35 // obligated to do so. If you do not wish to do so, delete this 36 // exception statement from your version. 37 38 using System; 39 40 using agsXMPP.IO.Compression.Streams; 41 42 namespace agsXMPP.IO.Compression 43 { 44 45 /// <summary> 46 /// Huffman tree used for inflation 47 /// </summary> 48 public class InflaterHuffmanTree 49 { 50 static int MAX_BITLEN = 15; 51 short[] tree; 52 53 /// <summary> 54 /// Literal length tree 55 /// </summary> 56 public static InflaterHuffmanTree defLitLenTree; 57 58 /// <summary> 59 /// Distance tree 60 /// </summary> 61 public static InflaterHuffmanTree defDistTree; 62 InflaterHuffmanTree()63 static InflaterHuffmanTree() 64 { 65 try { 66 byte[] codeLengths = new byte[288]; 67 int i = 0; 68 while (i < 144) { 69 codeLengths[i++] = 8; 70 } 71 while (i < 256) { 72 codeLengths[i++] = 9; 73 } 74 while (i < 280) { 75 codeLengths[i++] = 7; 76 } 77 while (i < 288) { 78 codeLengths[i++] = 8; 79 } 80 defLitLenTree = new InflaterHuffmanTree(codeLengths); 81 82 codeLengths = new byte[32]; 83 i = 0; 84 while (i < 32) { 85 codeLengths[i++] = 5; 86 } 87 defDistTree = new InflaterHuffmanTree(codeLengths); 88 } catch (Exception) { 89 throw new SharpZipBaseException("InflaterHuffmanTree: static tree length illegal"); 90 } 91 } 92 93 /// <summary> 94 /// Constructs a Huffman tree from the array of code lengths. 95 /// </summary> 96 /// <param name = "codeLengths"> 97 /// the array of code lengths 98 /// </param> InflaterHuffmanTree(byte[] codeLengths)99 public InflaterHuffmanTree(byte[] codeLengths) 100 { 101 BuildTree(codeLengths); 102 } 103 BuildTree(byte[] codeLengths)104 void BuildTree(byte[] codeLengths) 105 { 106 int[] blCount = new int[MAX_BITLEN + 1]; 107 int[] nextCode = new int[MAX_BITLEN + 1]; 108 109 for (int i = 0; i < codeLengths.Length; i++) { 110 int bits = codeLengths[i]; 111 if (bits > 0) { 112 blCount[bits]++; 113 } 114 } 115 116 int code = 0; 117 int treeSize = 512; 118 for (int bits = 1; bits <= MAX_BITLEN; bits++) { 119 nextCode[bits] = code; 120 code += blCount[bits] << (16 - bits); 121 if (bits >= 10) { 122 /* We need an extra table for bit lengths >= 10. */ 123 int start = nextCode[bits] & 0x1ff80; 124 int end = code & 0x1ff80; 125 treeSize += (end - start) >> (16 - bits); 126 } 127 } 128 129 /* -jr comment this out! doesnt work for dynamic trees and pkzip 2.04g 130 if (code != 65536) 131 { 132 throw new SharpZipBaseException("Code lengths don't add up properly."); 133 } 134 */ 135 /* Now create and fill the extra tables from longest to shortest 136 * bit len. This way the sub trees will be aligned. 137 */ 138 tree = new short[treeSize]; 139 int treePtr = 512; 140 for (int bits = MAX_BITLEN; bits >= 10; bits--) { 141 int end = code & 0x1ff80; 142 code -= blCount[bits] << (16 - bits); 143 int start = code & 0x1ff80; 144 for (int i = start; i < end; i += 1 << 7) { 145 tree[DeflaterHuffman.BitReverse(i)] = (short) ((-treePtr << 4) | bits); 146 treePtr += 1 << (bits-9); 147 } 148 } 149 150 for (int i = 0; i < codeLengths.Length; i++) { 151 int bits = codeLengths[i]; 152 if (bits == 0) { 153 continue; 154 } 155 code = nextCode[bits]; 156 int revcode = DeflaterHuffman.BitReverse(code); 157 if (bits <= 9) { 158 do { 159 tree[revcode] = (short) ((i << 4) | bits); 160 revcode += 1 << bits; 161 } while (revcode < 512); 162 } else { 163 int subTree = tree[revcode & 511]; 164 int treeLen = 1 << (subTree & 15); 165 subTree = -(subTree >> 4); 166 do { 167 tree[subTree | (revcode >> 9)] = (short) ((i << 4) | bits); 168 revcode += 1 << bits; 169 } while (revcode < treeLen); 170 } 171 nextCode[bits] = code + (1 << (16 - bits)); 172 } 173 174 } 175 176 /// <summary> 177 /// Reads the next symbol from input. The symbol is encoded using the 178 /// huffman tree. 179 /// </summary> 180 /// <param name="input"> 181 /// input the input source. 182 /// </param> 183 /// <returns> 184 /// the next symbol, or -1 if not enough input is available. 185 /// </returns> GetSymbol(StreamManipulator input)186 public int GetSymbol(StreamManipulator input) 187 { 188 int lookahead, symbol; 189 if ((lookahead = input.PeekBits(9)) >= 0) { 190 if ((symbol = tree[lookahead]) >= 0) { 191 input.DropBits(symbol & 15); 192 return symbol >> 4; 193 } 194 int subtree = -(symbol >> 4); 195 int bitlen = symbol & 15; 196 if ((lookahead = input.PeekBits(bitlen)) >= 0) { 197 symbol = tree[subtree | (lookahead >> 9)]; 198 input.DropBits(symbol & 15); 199 return symbol >> 4; 200 } else { 201 int bits = input.AvailableBits; 202 lookahead = input.PeekBits(bits); 203 symbol = tree[subtree | (lookahead >> 9)]; 204 if ((symbol & 15) <= bits) { 205 input.DropBits(symbol & 15); 206 return symbol >> 4; 207 } else { 208 return -1; 209 } 210 } 211 } else { 212 int bits = input.AvailableBits; 213 lookahead = input.PeekBits(bits); 214 symbol = tree[lookahead]; 215 if (symbol >= 0 && (symbol & 15) <= bits) { 216 input.DropBits(symbol & 15); 217 return symbol >> 4; 218 } else { 219 return -1; 220 } 221 } 222 } 223 } 224 } 225 226