1 /* InflaterHuffmanTree.java -- 2 Copyright (C) 2001, 2004 Free Software Foundation, Inc. 3 4 This file is part of GNU Classpath. 5 6 GNU Classpath is free software; you can redistribute it and/or modify 7 it under the terms of the GNU General Public License as published by 8 the Free Software Foundation; either version 2, or (at your option) 9 any later version. 10 11 GNU Classpath is distributed in the hope that it will be useful, but 12 WITHOUT ANY WARRANTY; without even the implied warranty of 13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 14 General Public License for more details. 15 16 You should have received a copy of the GNU General Public License 17 along with GNU Classpath; see the file COPYING. If not, write to the 18 Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 19 02110-1301 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 package java.util.zip; 39 40 class InflaterHuffmanTree 41 { 42 private static final int MAX_BITLEN = 15; 43 44 private short[] tree; 45 46 static InflaterHuffmanTree defLitLenTree, defDistTree; 47 48 static 49 { 50 try 51 { 52 byte[] codeLengths = new byte[288]; 53 int i = 0; 54 while (i < 144) 55 codeLengths[i++] = 8; 56 while (i < 256) 57 codeLengths[i++] = 9; 58 while (i < 280) 59 codeLengths[i++] = 7; 60 while (i < 288) 61 codeLengths[i++] = 8; 62 defLitLenTree = new InflaterHuffmanTree(codeLengths); 63 64 codeLengths = new byte[32]; 65 i = 0; 66 while (i < 32) 67 codeLengths[i++] = 5; 68 defDistTree = new InflaterHuffmanTree(codeLengths); 69 } 70 catch (DataFormatException ex) 71 { 72 throw new InternalError 73 ("InflaterHuffmanTree: static tree length illegal"); 74 } 75 } 76 77 /** 78 * Constructs a Huffman tree from the array of code lengths. 79 * 80 * @param codeLengths the array of code lengths 81 */ InflaterHuffmanTree(byte[] codeLengths)82 InflaterHuffmanTree(byte[] codeLengths) throws DataFormatException 83 { 84 buildTree(codeLengths); 85 } 86 buildTree(byte[] codeLengths)87 private void buildTree(byte[] codeLengths) throws DataFormatException 88 { 89 int[] blCount = new int[MAX_BITLEN+1]; 90 int[] nextCode = new int[MAX_BITLEN+1]; 91 for (int i = 0; i < codeLengths.length; i++) 92 { 93 int bits = codeLengths[i]; 94 if (bits > 0) 95 blCount[bits]++; 96 } 97 98 int max = 0; 99 int code = 0; 100 int treeSize = 512; 101 for (int bits = 1; bits <= MAX_BITLEN; bits++) 102 { 103 nextCode[bits] = code; 104 if (blCount[bits] > 0) 105 max = bits; 106 code += blCount[bits] << (16 - bits); 107 if (bits >= 10) 108 { 109 /* We need an extra table for bit lengths >= 10. */ 110 int start = nextCode[bits] & 0x1ff80; 111 int end = code & 0x1ff80; 112 treeSize += (end - start) >> (16 - bits); 113 } 114 } 115 if (code != 65536 && max > 1) 116 throw new DataFormatException("incomplete dynamic bit lengths tree"); 117 118 /* Now create and fill the extra tables from longest to shortest 119 * bit len. This way the sub trees will be aligned. 120 */ 121 tree = new short[treeSize]; 122 int treePtr = 512; 123 for (int bits = MAX_BITLEN; bits >= 10; bits--) 124 { 125 int end = code & 0x1ff80; 126 code -= blCount[bits] << (16 - bits); 127 int start = code & 0x1ff80; 128 for (int i = start; i < end; i += 1 << 7) 129 { 130 tree[DeflaterHuffman.bitReverse(i)] 131 = (short) ((-treePtr << 4) | bits); 132 treePtr += 1 << (bits-9); 133 } 134 } 135 136 for (int i = 0; i < codeLengths.length; i++) 137 { 138 int bits = codeLengths[i]; 139 if (bits == 0) 140 continue; 141 code = nextCode[bits]; 142 int revcode = DeflaterHuffman.bitReverse(code); 143 if (bits <= 9) 144 { 145 do 146 { 147 tree[revcode] = (short) ((i << 4) | bits); 148 revcode += 1 << bits; 149 } 150 while (revcode < 512); 151 } 152 else 153 { 154 int subTree = tree[revcode & 511]; 155 int treeLen = 1 << (subTree & 15); 156 subTree = -(subTree >> 4); 157 do 158 { 159 tree[subTree | (revcode >> 9)] = (short) ((i << 4) | bits); 160 revcode += 1 << bits; 161 } 162 while (revcode < treeLen); 163 } 164 nextCode[bits] = code + (1 << (16 - bits)); 165 } 166 } 167 168 /** 169 * Reads the next symbol from input. The symbol is encoded using the 170 * huffman tree. 171 * @param input the input source. 172 * @return the next symbol, or -1 if not enough input is available. 173 */ getSymbol(StreamManipulator input)174 int getSymbol(StreamManipulator input) throws DataFormatException 175 { 176 int lookahead, symbol; 177 if ((lookahead = input.peekBits(9)) >= 0) 178 { 179 if ((symbol = tree[lookahead]) >= 0) 180 { 181 input.dropBits(symbol & 15); 182 return symbol >> 4; 183 } 184 int subtree = -(symbol >> 4); 185 int bitlen = symbol & 15; 186 if ((lookahead = input.peekBits(bitlen)) >= 0) 187 { 188 symbol = tree[subtree | (lookahead >> 9)]; 189 input.dropBits(symbol & 15); 190 return symbol >> 4; 191 } 192 else 193 { 194 int bits = input.getAvailableBits(); 195 lookahead = input.peekBits(bits); 196 symbol = tree[subtree | (lookahead >> 9)]; 197 if ((symbol & 15) <= bits) 198 { 199 input.dropBits(symbol & 15); 200 return symbol >> 4; 201 } 202 else 203 return -1; 204 } 205 } 206 else 207 { 208 int bits = input.getAvailableBits(); 209 lookahead = input.peekBits(bits); 210 symbol = tree[lookahead]; 211 if (symbol >= 0 && (symbol & 15) <= bits) 212 { 213 input.dropBits(symbol & 15); 214 return symbol >> 4; 215 } 216 else 217 return -1; 218 } 219 } 220 } 221