Using GNU ClassPath implementation of ZipInputStream. Taken from http://sourceforge.net/projects/jazzlib/ rev. jazzlib-0.07.zip
1 /* Inflater.java - Decompress a data stream
2 Copyright (C) 1999, 2000, 2001, 2003 Free Software Foundation, Inc.
4 This file is part of GNU Classpath.
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)
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.
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., 59 Temple Place, Suite 330, Boston, MA
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
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. */
38 package java.util.zip;
40 import org.apidesign.bck2brwsr.emul.lang.System;
43 * This class provides support for general purpose decompression using the
44 * popular ZLIB compression library. The ZLIB compression library was
45 * initially developed as part of the PNG graphics standard and is not
46 * protected by patents. It is fully described in the specifications at
47 * the <a href="package-summary.html#package_description">java.util.zip
48 * package description</a>.
50 * <p>The following code fragment demonstrates a trivial compression
51 * and decompression of a string using <tt>Deflater</tt> and
56 * // Encode a String into bytes
57 * String inputString = "blahblahblah\u20AC\u20AC";
58 * byte[] input = inputString.getBytes("UTF-8");
60 * // Compress the bytes
61 * byte[] output = new byte[100];
62 * Deflater compresser = new Deflater();
63 * compresser.setInput(input);
64 * compresser.finish();
65 * int compressedDataLength = compresser.deflate(output);
67 * // Decompress the bytes
68 * Inflater decompresser = new Inflater();
69 * decompresser.setInput(output, 0, compressedDataLength);
70 * byte[] result = new byte[100];
71 * int resultLength = decompresser.inflate(result);
74 * // Decode the bytes into a String
75 * String outputString = new String(result, 0, resultLength, "UTF-8");
76 * } catch(java.io.UnsupportedEncodingException ex) {
78 * } catch (java.util.zip.DataFormatException ex) {
84 * @author David Connelly
88 /* Written using on-line Java Platform 1.2 API Specification
90 * Believed complete and correct.
94 * Inflater is used to decompress data that has been compressed according
95 * to the "deflate" standard described in rfc1950.
97 * The usage is as following. First you have to set some input with
98 * <code>setInput()</code>, then inflate() it. If inflate doesn't
99 * inflate any bytes there may be three reasons:
101 * <li>needsInput() returns true because the input buffer is empty.
102 * You have to provide more input with <code>setInput()</code>.
103 * NOTE: needsInput() also returns true when, the stream is finished.
105 * <li>needsDictionary() returns true, you have to provide a preset
106 * dictionary with <code>setDictionary()</code>.</li>
107 * <li>finished() returns true, the inflater has finished.</li>
109 * Once the first output byte is produced, a dictionary will not be
110 * needed at a later stage.
112 * @author John Leuner, Jochen Hoenicke
117 public class Inflater
119 /* Copy lengths for literal codes 257..285 */
120 private static final int CPLENS[] =
122 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31,
123 35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258
126 /* Extra bits for literal codes 257..285 */
127 private static final int CPLEXT[] =
129 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2,
130 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0
133 /* Copy offsets for distance codes 0..29 */
134 private static final int CPDIST[] = {
135 1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193,
136 257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145,
137 8193, 12289, 16385, 24577
140 /* Extra bits for distance codes */
141 private static final int CPDEXT[] = {
142 0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6,
143 7, 7, 8, 8, 9, 9, 10, 10, 11, 11,
147 /* This are the state in which the inflater can be. */
148 private static final int DECODE_HEADER = 0;
149 private static final int DECODE_DICT = 1;
150 private static final int DECODE_BLOCKS = 2;
151 private static final int DECODE_STORED_LEN1 = 3;
152 private static final int DECODE_STORED_LEN2 = 4;
153 private static final int DECODE_STORED = 5;
154 private static final int DECODE_DYN_HEADER = 6;
155 private static final int DECODE_HUFFMAN = 7;
156 private static final int DECODE_HUFFMAN_LENBITS = 8;
157 private static final int DECODE_HUFFMAN_DIST = 9;
158 private static final int DECODE_HUFFMAN_DISTBITS = 10;
159 private static final int DECODE_CHKSUM = 11;
160 private static final int FINISHED = 12;
162 /** This variable contains the current state. */
166 * The adler checksum of the dictionary or of the decompressed
167 * stream, as it is written in the header resp. footer of the
168 * compressed stream. <br>
170 * Only valid if mode is DECODE_DICT or DECODE_CHKSUM.
172 private int readAdler;
174 * The number of bits needed to complete the current state. This
175 * is valid, if mode is DECODE_DICT, DECODE_CHKSUM,
176 * DECODE_HUFFMAN_LENBITS or DECODE_HUFFMAN_DISTBITS.
178 private int neededBits;
179 private int repLength, repDist;
180 private int uncomprLen;
182 * True, if the last block flag was set in the last block of the
183 * inflated stream. This means that the stream ends after the
186 private boolean isLastBlock;
189 * The total number of inflated bytes.
191 private long totalOut;
193 * The total number of bytes set with setInput(). This is not the
194 * value returned by getTotalIn(), since this also includes the
197 private long totalIn;
199 * This variable stores the nowrap flag that was given to the constructor.
200 * True means, that the inflated stream doesn't contain a header nor the
201 * checksum in the footer.
203 private boolean nowrap;
205 private StreamManipulator input;
206 private OutputWindow outputWindow;
207 private InflaterDynHeader dynHeader;
208 private InflaterHuffmanTree litlenTree, distTree;
209 private Adler32 adler;
212 * Creates a new inflater.
220 * Creates a new inflater.
221 * @param nowrap true if no header and checksum field appears in the
222 * stream. This is used for GZIPed input. For compatibility with
223 * Sun JDK you should provide one byte of input more than needed in
226 public Inflater (boolean nowrap)
228 this.nowrap = nowrap;
229 this.adler = new Adler32();
230 input = new StreamManipulator();
231 outputWindow = new OutputWindow();
232 mode = nowrap ? DECODE_BLOCKS : DECODE_HEADER;
236 * Finalizes this object.
238 protected void finalize ()
240 /* Exists only for compatibility */
244 * Frees all objects allocated by the inflater. There's no reason
245 * to call this, since you can just rely on garbage collection (even
246 * for the Sun implementation). Exists only for compatibility
247 * with Sun's JDK, where the compressor allocates native memory.
248 * If you call any method (even reset) afterwards the behaviour is
250 * @deprecated Just clear all references to inflater instead.
263 * Returns true, if the inflater has finished. This means, that no
264 * input is needed and no output can be produced.
266 public boolean finished()
268 return mode == FINISHED && outputWindow.getAvailable() == 0;
272 * Gets the adler checksum. This is either the checksum of all
273 * uncompressed bytes returned by inflate(), or if needsDictionary()
274 * returns true (and thus no output was yet produced) this is the
275 * adler checksum of the expected dictionary.
276 * @returns the adler checksum.
278 public int getAdler()
280 return needsDictionary() ? readAdler : (int) adler.getValue();
284 * Gets the number of unprocessed input. Useful, if the end of the
285 * stream is reached and you want to further process the bytes after
286 * the deflate stream.
287 * @return the number of bytes of the input which were not processed.
289 public int getRemaining()
291 return input.getAvailableBytes();
295 * Gets the total number of processed compressed input bytes.
296 * @return the total number of bytes of processed input bytes.
298 public int getTotalIn()
300 return (int)getBytesRead();
304 * Gets the total number of output bytes returned by inflate().
305 * @return the total number of output bytes.
307 public int getTotalOut()
309 return (int)totalOut;
312 public long getBytesWritten() {
316 public long getBytesRead() {
317 return totalIn - getRemaining();
322 * Inflates the compressed stream to the output buffer. If this
323 * returns 0, you should check, whether needsDictionary(),
324 * needsInput() or finished() returns true, to determine why no
325 * further output is produced.
326 * @param buffer the output buffer.
327 * @return the number of bytes written to the buffer, 0 if no further
328 * output can be produced.
329 * @exception DataFormatException if deflated stream is invalid.
330 * @exception IllegalArgumentException if buf has length 0.
332 public int inflate (byte[] buf) throws DataFormatException
334 return inflate (buf, 0, buf.length);
338 * Inflates the compressed stream to the output buffer. If this
339 * returns 0, you should check, whether needsDictionary(),
340 * needsInput() or finished() returns true, to determine why no
341 * further output is produced.
342 * @param buffer the output buffer.
343 * @param off the offset into buffer where the output should start.
344 * @param len the maximum length of the output.
345 * @return the number of bytes written to the buffer, 0 if no further
346 * output can be produced.
347 * @exception DataFormatException if deflated stream is invalid.
348 * @exception IndexOutOfBoundsException if the off and/or len are wrong.
350 public int inflate (byte[] buf, int off, int len) throws DataFormatException
352 /* Special case: len may be zero */
355 /* Check for correct buff, off, len triple */
356 if (0 > off || off > off + len || off + len > buf.length)
357 throw new ArrayIndexOutOfBoundsException();
362 if (mode != DECODE_CHKSUM)
364 /* Don't give away any output, if we are waiting for the
365 * checksum in the input stream.
367 * With this trick we have always:
368 * needsInput() and not finished()
369 * implies more output can be produced.
371 more = outputWindow.copyOutput(buf, off, len);
372 adler.update(buf, off, more);
381 while (decode() || (outputWindow.getAvailable() > 0
382 && mode != DECODE_CHKSUM));
387 * Returns true, if a preset dictionary is needed to inflate the input.
389 public boolean needsDictionary ()
391 return mode == DECODE_DICT && neededBits == 0;
395 * Returns true, if the input buffer is empty.
396 * You should then call setInput(). <br>
398 * <em>NOTE</em>: This method also returns true when the stream is finished.
400 public boolean needsInput ()
402 return input.needsInput ();
406 * Resets the inflater so that a new stream can be decompressed. All
407 * pending input and output will be discarded.
411 mode = nowrap ? DECODE_BLOCKS : DECODE_HEADER;
412 totalIn = totalOut = 0;
414 outputWindow.reset();
423 * Sets the preset dictionary. This should only be called, if
424 * needsDictionary() returns true and it should set the same
425 * dictionary, that was used for deflating. The getAdler()
426 * function returns the checksum of the dictionary needed.
427 * @param buffer the dictionary.
428 * @exception IllegalStateException if no dictionary is needed.
429 * @exception IllegalArgumentException if the dictionary checksum is
432 public void setDictionary (byte[] buffer)
434 setDictionary(buffer, 0, buffer.length);
438 * Sets the preset dictionary. This should only be called, if
439 * needsDictionary() returns true and it should set the same
440 * dictionary, that was used for deflating. The getAdler()
441 * function returns the checksum of the dictionary needed.
442 * @param buffer the dictionary.
443 * @param off the offset into buffer where the dictionary starts.
444 * @param len the length of the dictionary.
445 * @exception IllegalStateException if no dictionary is needed.
446 * @exception IllegalArgumentException if the dictionary checksum is
448 * @exception IndexOutOfBoundsException if the off and/or len are wrong.
450 public void setDictionary (byte[] buffer, int off, int len)
452 if (!needsDictionary())
453 throw new IllegalStateException();
455 adler.update(buffer, off, len);
456 if ((int) adler.getValue() != readAdler)
457 throw new IllegalArgumentException("Wrong adler checksum");
459 outputWindow.copyDict(buffer, off, len);
460 mode = DECODE_BLOCKS;
464 * Sets the input. This should only be called, if needsInput()
466 * @param buffer the input.
467 * @exception IllegalStateException if no input is needed.
469 public void setInput (byte[] buf)
471 setInput (buf, 0, buf.length);
475 * Sets the input. This should only be called, if needsInput()
477 * @param buffer the input.
478 * @param off the offset into buffer where the input starts.
479 * @param len the length of the input.
480 * @exception IllegalStateException if no input is needed.
481 * @exception IndexOutOfBoundsException if the off and/or len are wrong.
483 public void setInput (byte[] buf, int off, int len)
485 input.setInput (buf, off, len);
488 private static final int DEFLATED = 8;
490 * Decodes the deflate header.
491 * @return false if more input is needed.
492 * @exception DataFormatException if header is invalid.
494 private boolean decodeHeader () throws DataFormatException
496 int header = input.peekBits(16);
501 /* The header is written in "wrong" byte order */
502 header = ((header << 8) | (header >> 8)) & 0xffff;
503 if (header % 31 != 0)
504 throw new DataFormatException("Header checksum illegal");
506 if ((header & 0x0f00) != (DEFLATED << 8))
507 throw new DataFormatException("Compression Method unknown");
509 /* Maximum size of the backwards window in bits.
510 * We currently ignore this, but we could use it to make the
511 * inflater window more space efficient. On the other hand the
512 * full window (15 bits) is needed most times, anyway.
513 int max_wbits = ((header & 0x7000) >> 12) + 8;
516 if ((header & 0x0020) == 0) // Dictionary flag?
518 mode = DECODE_BLOCKS;
529 * Decodes the dictionary checksum after the deflate header.
530 * @return false if more input is needed.
532 private boolean decodeDict ()
534 while (neededBits > 0)
536 int dictByte = input.peekBits(8);
540 readAdler = (readAdler << 8) | dictByte;
547 * Decodes the huffman encoded symbols in the input stream.
548 * @return false if more input is needed, true if output window is
549 * full or the current block ends.
550 * @exception DataFormatException if deflated stream is invalid.
552 private boolean decodeHuffman () throws DataFormatException
554 int free = outputWindow.getFreeSpace();
561 /* This is the inner loop so it is optimized a bit */
562 while (((symbol = litlenTree.getSymbol(input)) & ~0xff) == 0)
564 outputWindow.write(symbol);
574 /* symbol == 256: end of block */
577 mode = DECODE_BLOCKS;
584 repLength = CPLENS[symbol - 257];
585 neededBits = CPLEXT[symbol - 257];
587 catch (ArrayIndexOutOfBoundsException ex)
589 throw new DataFormatException("Illegal rep length code");
592 case DECODE_HUFFMAN_LENBITS:
595 mode = DECODE_HUFFMAN_LENBITS;
596 int i = input.peekBits(neededBits);
599 input.dropBits(neededBits);
602 mode = DECODE_HUFFMAN_DIST;
604 case DECODE_HUFFMAN_DIST:
605 symbol = distTree.getSymbol(input);
610 repDist = CPDIST[symbol];
611 neededBits = CPDEXT[symbol];
613 catch (ArrayIndexOutOfBoundsException ex)
615 throw new DataFormatException("Illegal rep dist code");
618 case DECODE_HUFFMAN_DISTBITS:
621 mode = DECODE_HUFFMAN_DISTBITS;
622 int i = input.peekBits(neededBits);
625 input.dropBits(neededBits);
628 outputWindow.repeat(repLength, repDist);
630 mode = DECODE_HUFFMAN;
633 throw new IllegalStateException();
640 * Decodes the adler checksum after the deflate stream.
641 * @return false if more input is needed.
642 * @exception DataFormatException if checksum doesn't match.
644 private boolean decodeChksum () throws DataFormatException
646 while (neededBits > 0)
648 int chkByte = input.peekBits(8);
652 readAdler = (readAdler << 8) | chkByte;
655 if ((int) adler.getValue() != readAdler)
656 throw new DataFormatException("Adler chksum doesn't match: "
657 +Integer.toHexString((int)adler.getValue())
658 +" vs. "+Integer.toHexString(readAdler));
664 * Decodes the deflated stream.
665 * @return false if more input is needed, or if finished.
666 * @exception DataFormatException if deflated stream is invalid.
668 private boolean decode () throws DataFormatException
673 return decodeHeader();
677 return decodeChksum();
689 input.skipToByteBoundary();
691 mode = DECODE_CHKSUM;
696 int type = input.peekBits(3);
705 case DeflaterConstants.STORED_BLOCK:
706 input.skipToByteBoundary();
707 mode = DECODE_STORED_LEN1;
709 case DeflaterConstants.STATIC_TREES:
710 litlenTree = InflaterHuffmanTree.defLitLenTree;
711 distTree = InflaterHuffmanTree.defDistTree;
712 mode = DECODE_HUFFMAN;
714 case DeflaterConstants.DYN_TREES:
715 dynHeader = new InflaterDynHeader();
716 mode = DECODE_DYN_HEADER;
719 throw new DataFormatException("Unknown block type "+type);
723 case DECODE_STORED_LEN1:
725 if ((uncomprLen = input.peekBits(16)) < 0)
728 mode = DECODE_STORED_LEN2;
731 case DECODE_STORED_LEN2:
733 int nlen = input.peekBits(16);
737 if (nlen != (uncomprLen ^ 0xffff))
738 throw new DataFormatException("broken uncompressed block");
739 mode = DECODE_STORED;
744 int more = outputWindow.copyStored(input, uncomprLen);
748 mode = DECODE_BLOCKS;
751 return !input.needsInput();
754 case DECODE_DYN_HEADER:
755 if (!dynHeader.decode(input))
757 litlenTree = dynHeader.buildLitLenTree();
758 distTree = dynHeader.buildDistTree();
759 mode = DECODE_HUFFMAN;
762 case DECODE_HUFFMAN_LENBITS:
763 case DECODE_HUFFMAN_DIST:
764 case DECODE_HUFFMAN_DISTBITS:
765 return decodeHuffman();
769 throw new IllegalStateException();
774 interface DeflaterConstants {
775 final static boolean DEBUGGING = false;
777 final static int STORED_BLOCK = 0;
778 final static int STATIC_TREES = 1;
779 final static int DYN_TREES = 2;
780 final static int PRESET_DICT = 0x20;
782 final static int DEFAULT_MEM_LEVEL = 8;
784 final static int MAX_MATCH = 258;
785 final static int MIN_MATCH = 3;
787 final static int MAX_WBITS = 15;
788 final static int WSIZE = 1 << MAX_WBITS;
789 final static int WMASK = WSIZE - 1;
791 final static int HASH_BITS = DEFAULT_MEM_LEVEL + 7;
792 final static int HASH_SIZE = 1 << HASH_BITS;
793 final static int HASH_MASK = HASH_SIZE - 1;
794 final static int HASH_SHIFT = (HASH_BITS + MIN_MATCH - 1) / MIN_MATCH;
796 final static int MIN_LOOKAHEAD = MAX_MATCH + MIN_MATCH + 1;
797 final static int MAX_DIST = WSIZE - MIN_LOOKAHEAD;
799 final static int PENDING_BUF_SIZE = 1 << (DEFAULT_MEM_LEVEL + 8);
800 final static int MAX_BLOCK_SIZE = Math.min(65535, PENDING_BUF_SIZE-5);
802 final static int DEFLATE_STORED = 0;
803 final static int DEFLATE_FAST = 1;
804 final static int DEFLATE_SLOW = 2;
806 final static int GOOD_LENGTH[] = { 0,4, 4, 4, 4, 8, 8, 8, 32, 32 };
807 final static int MAX_LAZY[] = { 0,4, 5, 6, 4,16, 16, 32, 128, 258 };
808 final static int NICE_LENGTH[] = { 0,8,16,32,16,32,128,128, 258, 258 };
809 final static int MAX_CHAIN[] = { 0,4, 8,32,16,32,128,256,1024,4096 };
810 final static int COMPR_FUNC[] = { 0,1, 1, 1, 1, 2, 2, 2, 2, 2 };
812 private static class InflaterHuffmanTree {
813 private final static int MAX_BITLEN = 15;
814 private short[] tree;
816 public static InflaterHuffmanTree defLitLenTree, defDistTree;
822 byte[] codeLengths = new byte[288];
825 codeLengths[i++] = 8;
827 codeLengths[i++] = 9;
829 codeLengths[i++] = 7;
831 codeLengths[i++] = 8;
832 defLitLenTree = new InflaterHuffmanTree(codeLengths);
834 codeLengths = new byte[32];
837 codeLengths[i++] = 5;
838 defDistTree = new InflaterHuffmanTree(codeLengths);
840 catch (DataFormatException ex)
842 throw new IllegalStateException
843 ("InflaterHuffmanTree: static tree length illegal");
848 * Constructs a Huffman tree from the array of code lengths.
850 * @param codeLengths the array of code lengths
852 public InflaterHuffmanTree(byte[] codeLengths) throws DataFormatException
854 buildTree(codeLengths);
857 private void buildTree(byte[] codeLengths) throws DataFormatException
859 int[] blCount = new int[MAX_BITLEN+1];
860 int[] nextCode = new int[MAX_BITLEN+1];
861 for (int i = 0; i < codeLengths.length; i++)
863 int bits = codeLengths[i];
870 for (int bits = 1; bits <= MAX_BITLEN; bits++)
872 nextCode[bits] = code;
873 code += blCount[bits] << (16 - bits);
876 /* We need an extra table for bit lengths >= 10. */
877 int start = nextCode[bits] & 0x1ff80;
878 int end = code & 0x1ff80;
879 treeSize += (end - start) >> (16 - bits);
883 throw new DataFormatException("Code lengths don't add up properly.");
885 /* Now create and fill the extra tables from longest to shortest
886 * bit len. This way the sub trees will be aligned.
888 tree = new short[treeSize];
890 for (int bits = MAX_BITLEN; bits >= 10; bits--)
892 int end = code & 0x1ff80;
893 code -= blCount[bits] << (16 - bits);
894 int start = code & 0x1ff80;
895 for (int i = start; i < end; i += 1 << 7)
898 = (short) ((-treePtr << 4) | bits);
899 treePtr += 1 << (bits-9);
903 for (int i = 0; i < codeLengths.length; i++)
905 int bits = codeLengths[i];
908 code = nextCode[bits];
909 int revcode = bitReverse(code);
914 tree[revcode] = (short) ((i << 4) | bits);
915 revcode += 1 << bits;
917 while (revcode < 512);
921 int subTree = tree[revcode & 511];
922 int treeLen = 1 << (subTree & 15);
923 subTree = -(subTree >> 4);
926 tree[subTree | (revcode >> 9)] = (short) ((i << 4) | bits);
927 revcode += 1 << bits;
929 while (revcode < treeLen);
931 nextCode[bits] = code + (1 << (16 - bits));
934 private final static String bit4Reverse =
935 "\000\010\004\014\002\012\006\016\001\011\005\015\003\013\007\017";
936 static short bitReverse(int value) {
937 return (short) (bit4Reverse.charAt(value & 0xf) << 12
938 | bit4Reverse.charAt((value >> 4) & 0xf) << 8
939 | bit4Reverse.charAt((value >> 8) & 0xf) << 4
940 | bit4Reverse.charAt(value >> 12));
944 * Reads the next symbol from input. The symbol is encoded using the
946 * @param input the input source.
947 * @return the next symbol, or -1 if not enough input is available.
949 public int getSymbol(StreamManipulator input) throws DataFormatException
951 int lookahead, symbol;
952 if ((lookahead = input.peekBits(9)) >= 0)
954 if ((symbol = tree[lookahead]) >= 0)
956 input.dropBits(symbol & 15);
959 int subtree = -(symbol >> 4);
960 int bitlen = symbol & 15;
961 if ((lookahead = input.peekBits(bitlen)) >= 0)
963 symbol = tree[subtree | (lookahead >> 9)];
964 input.dropBits(symbol & 15);
969 int bits = input.getAvailableBits();
970 lookahead = input.peekBits(bits);
971 symbol = tree[subtree | (lookahead >> 9)];
972 if ((symbol & 15) <= bits)
974 input.dropBits(symbol & 15);
983 int bits = input.getAvailableBits();
984 lookahead = input.peekBits(bits);
985 symbol = tree[lookahead];
986 if (symbol >= 0 && (symbol & 15) <= bits)
988 input.dropBits(symbol & 15);
996 private static class InflaterDynHeader
998 private static final int LNUM = 0;
999 private static final int DNUM = 1;
1000 private static final int BLNUM = 2;
1001 private static final int BLLENS = 3;
1002 private static final int LENS = 4;
1003 private static final int REPS = 5;
1005 private static final int repMin[] = { 3, 3, 11 };
1006 private static final int repBits[] = { 2, 3, 7 };
1009 private byte[] blLens;
1010 private byte[] litdistLens;
1012 private InflaterHuffmanTree blTree;
1015 private int lnum, dnum, blnum, num;
1016 private int repSymbol;
1017 private byte lastLen;
1020 private static final int[] BL_ORDER =
1021 { 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15 };
1023 public InflaterDynHeader()
1027 public boolean decode(StreamManipulator input) throws DataFormatException
1035 lnum = input.peekBits(5);
1040 // System.err.println("LNUM: "+lnum);
1044 dnum = input.peekBits(5);
1049 // System.err.println("DNUM: "+dnum);
1051 litdistLens = new byte[num];
1055 blnum = input.peekBits(4);
1060 blLens = new byte[19];
1062 // System.err.println("BLNUM: "+blnum);
1068 int len = input.peekBits(3);
1072 // System.err.println("blLens["+BL_ORDER[ptr]+"]: "+len);
1073 blLens[BL_ORDER[ptr]] = (byte) len;
1076 blTree = new InflaterHuffmanTree(blLens);
1084 while (((symbol = blTree.getSymbol(input)) & ~15) == 0)
1086 /* Normal case: symbol in [0..15] */
1088 // System.err.println("litdistLens["+ptr+"]: "+symbol);
1089 litdistLens[ptr++] = lastLen = (byte) symbol;
1098 /* need more input ? */
1102 /* otherwise repeat code */
1106 // System.err.println("repeating zero");
1112 throw new DataFormatException();
1114 repSymbol = symbol-16;
1121 int bits = repBits[repSymbol];
1122 int count = input.peekBits(bits);
1125 input.dropBits(bits);
1126 count += repMin[repSymbol];
1127 // System.err.println("litdistLens repeated: "+count);
1129 if (ptr + count > num)
1130 throw new DataFormatException();
1132 litdistLens[ptr++] = lastLen;
1141 continue decode_loop;
1146 public InflaterHuffmanTree buildLitLenTree() throws DataFormatException
1148 byte[] litlenLens = new byte[lnum];
1149 System.arraycopy(litdistLens, 0, litlenLens, 0, lnum);
1150 return new InflaterHuffmanTree(litlenLens);
1153 public InflaterHuffmanTree buildDistTree() throws DataFormatException
1155 byte[] distLens = new byte[dnum];
1156 System.arraycopy(litdistLens, lnum, distLens, 0, dnum);
1157 return new InflaterHuffmanTree(distLens);
1161 * This class allows us to retrieve a specified amount of bits from
1162 * the input buffer, as well as copy big byte blocks.
1164 * It uses an int buffer to store up to 31 bits for direct
1165 * manipulation. This guarantees that we can get at least 16 bits,
1166 * but we only need at most 15, so this is all safe.
1168 * There are some optimizations in this class, for example, you must
1169 * never peek more then 8 bits more than needed, and you must first
1170 * peek bits before you may drop them. This is not a general purpose
1171 * class but optimized for the behaviour of the Inflater.
1173 * @author John Leuner, Jochen Hoenicke
1176 private static class StreamManipulator
1178 private byte[] window;
1179 private int window_start = 0;
1180 private int window_end = 0;
1182 private int buffer = 0;
1183 private int bits_in_buffer = 0;
1186 * Get the next n bits but don't increase input pointer. n must be
1187 * less or equal 16 and if you if this call succeeds, you must drop
1188 * at least n-8 bits in the next call.
1190 * @return the value of the bits, or -1 if not enough bits available. */
1191 public final int peekBits(int n)
1193 if (bits_in_buffer < n)
1195 if (window_start == window_end)
1197 buffer |= (window[window_start++] & 0xff
1198 | (window[window_start++] & 0xff) << 8) << bits_in_buffer;
1199 bits_in_buffer += 16;
1201 return buffer & ((1 << n) - 1);
1204 /* Drops the next n bits from the input. You should have called peekBits
1205 * with a bigger or equal n before, to make sure that enough bits are in
1208 public final void dropBits(int n)
1211 bits_in_buffer -= n;
1215 * Gets the next n bits and increases input pointer. This is equivalent
1216 * to peekBits followed by dropBits, except for correct error handling.
1217 * @return the value of the bits, or -1 if not enough bits available.
1219 public final int getBits(int n)
1221 int bits = peekBits(n);
1227 * Gets the number of bits available in the bit buffer. This must be
1228 * only called when a previous peekBits() returned -1.
1229 * @return the number of bits available.
1231 public final int getAvailableBits()
1233 return bits_in_buffer;
1237 * Gets the number of bytes available.
1238 * @return the number of bytes available.
1240 public final int getAvailableBytes()
1242 return window_end - window_start + (bits_in_buffer >> 3);
1246 * Skips to the next byte boundary.
1248 public void skipToByteBoundary()
1250 buffer >>= (bits_in_buffer & 7);
1251 bits_in_buffer &= ~7;
1254 public final boolean needsInput() {
1255 return window_start == window_end;
1259 /* Copies length bytes from input buffer to output buffer starting
1260 * at output[offset]. You have to make sure, that the buffer is
1261 * byte aligned. If not enough bytes are available, copies fewer
1263 * @param length the length to copy, 0 is allowed.
1264 * @return the number of bytes copied, 0 if no byte is available.
1266 public int copyBytes(byte[] output, int offset, int length)
1269 throw new IllegalArgumentException("length negative");
1270 if ((bits_in_buffer & 7) != 0)
1271 /* bits_in_buffer may only be 0 or 8 */
1272 throw new IllegalStateException("Bit buffer is not aligned!");
1275 while (bits_in_buffer > 0 && length > 0)
1277 output[offset++] = (byte) buffer;
1279 bits_in_buffer -= 8;
1286 int avail = window_end - window_start;
1289 System.arraycopy(window, window_start, output, offset, length);
1290 window_start += length;
1292 if (((window_start - window_end) & 1) != 0)
1294 /* We always want an even number of bytes in input, see peekBits */
1295 buffer = (window[window_start++] & 0xff);
1298 return count + length;
1301 public StreamManipulator()
1307 window_start = window_end = buffer = bits_in_buffer = 0;
1310 public void setInput(byte[] buf, int off, int len)
1312 if (window_start < window_end)
1313 throw new IllegalStateException
1314 ("Old input was not completely processed");
1316 int end = off + len;
1318 /* We want to throw an ArrayIndexOutOfBoundsException early. The
1319 * check is very tricky: it also handles integer wrap around.
1321 if (0 > off || off > end || end > buf.length)
1322 throw new ArrayIndexOutOfBoundsException();
1326 /* We always want an even number of bytes in input, see peekBits */
1327 buffer |= (buf[off++] & 0xff) << bits_in_buffer;
1328 bits_in_buffer += 8;
1337 * Contains the output from the Inflation process.
1339 * We need to have a window so that we can refer backwards into the output stream
1342 * @author John Leuner
1346 private static class OutputWindow
1348 private final int WINDOW_SIZE = 1 << 15;
1349 private final int WINDOW_MASK = WINDOW_SIZE - 1;
1351 private byte[] window = new byte[WINDOW_SIZE]; //The window is 2^15 bytes
1352 private int window_end = 0;
1353 private int window_filled = 0;
1355 public void write(int abyte)
1357 if (window_filled++ == WINDOW_SIZE)
1358 throw new IllegalStateException("Window full");
1359 window[window_end++] = (byte) abyte;
1360 window_end &= WINDOW_MASK;
1364 private final void slowRepeat(int rep_start, int len, int dist)
1368 window[window_end++] = window[rep_start++];
1369 window_end &= WINDOW_MASK;
1370 rep_start &= WINDOW_MASK;
1374 public void repeat(int len, int dist)
1376 if ((window_filled += len) > WINDOW_SIZE)
1377 throw new IllegalStateException("Window full");
1379 int rep_start = (window_end - dist) & WINDOW_MASK;
1380 int border = WINDOW_SIZE - len;
1381 if (rep_start <= border && window_end < border)
1385 System.arraycopy(window, rep_start, window, window_end, len);
1390 /* We have to copy manually, since the repeat pattern overlaps.
1393 window[window_end++] = window[rep_start++];
1397 slowRepeat(rep_start, len, dist);
1400 public int copyStored(StreamManipulator input, int len)
1402 len = Math.min(Math.min(len, WINDOW_SIZE - window_filled),
1403 input.getAvailableBytes());
1406 int tailLen = WINDOW_SIZE - window_end;
1409 copied = input.copyBytes(window, window_end, tailLen);
1410 if (copied == tailLen)
1411 copied += input.copyBytes(window, 0, len - tailLen);
1414 copied = input.copyBytes(window, window_end, len);
1416 window_end = (window_end + copied) & WINDOW_MASK;
1417 window_filled += copied;
1421 public void copyDict(byte[] dict, int offset, int len)
1423 if (window_filled > 0)
1424 throw new IllegalStateException();
1426 if (len > WINDOW_SIZE)
1428 offset += len - WINDOW_SIZE;
1431 System.arraycopy(dict, offset, window, 0, len);
1432 window_end = len & WINDOW_MASK;
1435 public int getFreeSpace()
1437 return WINDOW_SIZE - window_filled;
1440 public int getAvailable()
1442 return window_filled;
1445 public int copyOutput(byte[] output, int offset, int len)
1447 int copy_end = window_end;
1448 if (len > window_filled)
1449 len = window_filled;
1451 copy_end = (window_end - window_filled + len) & WINDOW_MASK;
1454 int tailLen = len - copy_end;
1458 System.arraycopy(window, WINDOW_SIZE - tailLen,
1459 output, offset, tailLen);
1463 System.arraycopy(window, copy_end - len, output, offset, len);
1464 window_filled -= copied;
1465 if (window_filled < 0)
1466 throw new IllegalStateException();
1470 public void reset() {
1471 window_filled = window_end = 0;