Workaround of some problems with bytecode conversion demonstrated by ZipCompatibilityTest. Splitting the code into two new methods.
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 fillTable1(treeSize, code, blCount);
887 for (int i = 0; i < codeLengths.length; i++)
889 int bits = codeLengths[i];
892 code = nextCode[bits];
893 int revcode = bitReverse(code);
898 tree[revcode] = (short) ((i << 4) | bits);
899 revcode += 1 << bits;
901 while (revcode < 512);
905 int subTree = tree[revcode & 511];
906 int treeLen = 1 << (subTree & 15);
907 subTree = -(subTree >> 4);
910 tree[subTree | (revcode >> 9)] = (short) ((i << 4) | bits);
911 revcode += 1 << bits;
913 while (revcode < treeLen);
915 nextCode[bits] = code + (1 << (16 - bits));
918 private final static String bit4Reverse =
919 "\000\010\004\014\002\012\006\016\001\011\005\015\003\013\007\017";
920 static short bitReverse(int value) {
921 return (short) (bit4Reverse.charAt(value & 0xf) << 12
922 | bit4Reverse.charAt((value >> 4) & 0xf) << 8
923 | bit4Reverse.charAt((value >> 8) & 0xf) << 4
924 | bit4Reverse.charAt(value >> 12));
928 * Reads the next symbol from input. The symbol is encoded using the
930 * @param input the input source.
931 * @return the next symbol, or -1 if not enough input is available.
933 public int getSymbol(StreamManipulator input) throws DataFormatException
935 int lookahead, symbol;
936 if ((lookahead = input.peekBits(9)) >= 0)
938 if ((symbol = tree[lookahead]) >= 0)
940 input.dropBits(symbol & 15);
943 int subtree = -(symbol >> 4);
944 int bitlen = symbol & 15;
945 if ((lookahead = input.peekBits(bitlen)) >= 0)
947 symbol = tree[subtree | (lookahead >> 9)];
948 input.dropBits(symbol & 15);
953 int bits = input.getAvailableBits();
954 lookahead = input.peekBits(bits);
955 symbol = tree[subtree | (lookahead >> 9)];
956 if ((symbol & 15) <= bits)
958 input.dropBits(symbol & 15);
967 int bits = input.getAvailableBits();
968 lookahead = input.peekBits(bits);
969 symbol = tree[lookahead];
970 if (symbol >= 0 && (symbol & 15) <= bits)
972 input.dropBits(symbol & 15);
980 private void fillTable1(int treeSize, int code, int[] blCount) {
981 /* Now create and fill the extra tables from longest to shortest
982 * bit len. This way the sub trees will be aligned.
984 tree = new short[treeSize];
986 for (int bits = MAX_BITLEN; bits >= 10; bits--) {
987 int end = code & 0x1ff80;
988 code -= blCount[bits] << (16 - bits);
989 int start = code & 0x1ff80;
990 final int inc = 1 << 7;
991 fillTable2(start, end, inc, treePtr, bits);
995 private void fillTable2(int start, int end, final int inc, int treePtr, int bits) {
996 for (int i = start; i < end; i += inc) {
997 final short br = bitReverse(i);
998 tree[br] = (short) ((-treePtr << 4) | bits);
999 treePtr += 1 << (bits - 9);
1003 private static class InflaterDynHeader
1005 private static final int LNUM = 0;
1006 private static final int DNUM = 1;
1007 private static final int BLNUM = 2;
1008 private static final int BLLENS = 3;
1009 private static final int LENS = 4;
1010 private static final int REPS = 5;
1012 private static final int repMin[] = { 3, 3, 11 };
1013 private static final int repBits[] = { 2, 3, 7 };
1016 private byte[] blLens;
1017 private byte[] litdistLens;
1019 private InflaterHuffmanTree blTree;
1022 private int lnum, dnum, blnum, num;
1023 private int repSymbol;
1024 private byte lastLen;
1027 private static final int[] BL_ORDER =
1028 { 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15 };
1030 public InflaterDynHeader()
1034 public boolean decode(StreamManipulator input) throws DataFormatException
1042 lnum = input.peekBits(5);
1047 // System.err.println("LNUM: "+lnum);
1051 dnum = input.peekBits(5);
1056 // System.err.println("DNUM: "+dnum);
1058 litdistLens = new byte[num];
1062 blnum = input.peekBits(4);
1067 blLens = new byte[19];
1069 // System.err.println("BLNUM: "+blnum);
1075 int len = input.peekBits(3);
1079 // System.err.println("blLens["+BL_ORDER[ptr]+"]: "+len);
1080 blLens[BL_ORDER[ptr]] = (byte) len;
1083 blTree = new InflaterHuffmanTree(blLens);
1091 while (((symbol = blTree.getSymbol(input)) & ~15) == 0)
1093 /* Normal case: symbol in [0..15] */
1095 // System.err.println("litdistLens["+ptr+"]: "+symbol);
1096 litdistLens[ptr++] = lastLen = (byte) symbol;
1105 /* need more input ? */
1109 /* otherwise repeat code */
1113 // System.err.println("repeating zero");
1119 throw new DataFormatException();
1121 repSymbol = symbol-16;
1128 int bits = repBits[repSymbol];
1129 int count = input.peekBits(bits);
1132 input.dropBits(bits);
1133 count += repMin[repSymbol];
1134 // System.err.println("litdistLens repeated: "+count);
1136 if (ptr + count > num)
1137 throw new DataFormatException();
1139 litdistLens[ptr++] = lastLen;
1148 continue decode_loop;
1153 public InflaterHuffmanTree buildLitLenTree() throws DataFormatException
1155 byte[] litlenLens = new byte[lnum];
1156 System.arraycopy(litdistLens, 0, litlenLens, 0, lnum);
1157 return new InflaterHuffmanTree(litlenLens);
1160 public InflaterHuffmanTree buildDistTree() throws DataFormatException
1162 byte[] distLens = new byte[dnum];
1163 System.arraycopy(litdistLens, lnum, distLens, 0, dnum);
1164 return new InflaterHuffmanTree(distLens);
1168 * This class allows us to retrieve a specified amount of bits from
1169 * the input buffer, as well as copy big byte blocks.
1171 * It uses an int buffer to store up to 31 bits for direct
1172 * manipulation. This guarantees that we can get at least 16 bits,
1173 * but we only need at most 15, so this is all safe.
1175 * There are some optimizations in this class, for example, you must
1176 * never peek more then 8 bits more than needed, and you must first
1177 * peek bits before you may drop them. This is not a general purpose
1178 * class but optimized for the behaviour of the Inflater.
1180 * @author John Leuner, Jochen Hoenicke
1183 private static class StreamManipulator
1185 private byte[] window;
1186 private int window_start = 0;
1187 private int window_end = 0;
1189 private int buffer = 0;
1190 private int bits_in_buffer = 0;
1193 * Get the next n bits but don't increase input pointer. n must be
1194 * less or equal 16 and if you if this call succeeds, you must drop
1195 * at least n-8 bits in the next call.
1197 * @return the value of the bits, or -1 if not enough bits available. */
1198 public final int peekBits(int n)
1200 if (bits_in_buffer < n)
1202 if (window_start == window_end)
1204 buffer |= (window[window_start++] & 0xff
1205 | (window[window_start++] & 0xff) << 8) << bits_in_buffer;
1206 bits_in_buffer += 16;
1208 return buffer & ((1 << n) - 1);
1211 /* Drops the next n bits from the input. You should have called peekBits
1212 * with a bigger or equal n before, to make sure that enough bits are in
1215 public final void dropBits(int n)
1218 bits_in_buffer -= n;
1222 * Gets the next n bits and increases input pointer. This is equivalent
1223 * to peekBits followed by dropBits, except for correct error handling.
1224 * @return the value of the bits, or -1 if not enough bits available.
1226 public final int getBits(int n)
1228 int bits = peekBits(n);
1234 * Gets the number of bits available in the bit buffer. This must be
1235 * only called when a previous peekBits() returned -1.
1236 * @return the number of bits available.
1238 public final int getAvailableBits()
1240 return bits_in_buffer;
1244 * Gets the number of bytes available.
1245 * @return the number of bytes available.
1247 public final int getAvailableBytes()
1249 return window_end - window_start + (bits_in_buffer >> 3);
1253 * Skips to the next byte boundary.
1255 public void skipToByteBoundary()
1257 buffer >>= (bits_in_buffer & 7);
1258 bits_in_buffer &= ~7;
1261 public final boolean needsInput() {
1262 return window_start == window_end;
1266 /* Copies length bytes from input buffer to output buffer starting
1267 * at output[offset]. You have to make sure, that the buffer is
1268 * byte aligned. If not enough bytes are available, copies fewer
1270 * @param length the length to copy, 0 is allowed.
1271 * @return the number of bytes copied, 0 if no byte is available.
1273 public int copyBytes(byte[] output, int offset, int length)
1276 throw new IllegalArgumentException("length negative");
1277 if ((bits_in_buffer & 7) != 0)
1278 /* bits_in_buffer may only be 0 or 8 */
1279 throw new IllegalStateException("Bit buffer is not aligned!");
1282 while (bits_in_buffer > 0 && length > 0)
1284 output[offset++] = (byte) buffer;
1286 bits_in_buffer -= 8;
1293 int avail = window_end - window_start;
1296 System.arraycopy(window, window_start, output, offset, length);
1297 window_start += length;
1299 if (((window_start - window_end) & 1) != 0)
1301 /* We always want an even number of bytes in input, see peekBits */
1302 buffer = (window[window_start++] & 0xff);
1305 return count + length;
1308 public StreamManipulator()
1314 window_start = window_end = buffer = bits_in_buffer = 0;
1317 public void setInput(byte[] buf, int off, int len)
1319 if (window_start < window_end)
1320 throw new IllegalStateException
1321 ("Old input was not completely processed");
1323 int end = off + len;
1325 /* We want to throw an ArrayIndexOutOfBoundsException early. The
1326 * check is very tricky: it also handles integer wrap around.
1328 if (0 > off || off > end || end > buf.length)
1329 throw new ArrayIndexOutOfBoundsException();
1333 /* We always want an even number of bytes in input, see peekBits */
1334 buffer |= (buf[off++] & 0xff) << bits_in_buffer;
1335 bits_in_buffer += 8;
1344 * Contains the output from the Inflation process.
1346 * We need to have a window so that we can refer backwards into the output stream
1349 * @author John Leuner
1353 private static class OutputWindow
1355 private final int WINDOW_SIZE = 1 << 15;
1356 private final int WINDOW_MASK = WINDOW_SIZE - 1;
1358 private byte[] window = new byte[WINDOW_SIZE]; //The window is 2^15 bytes
1359 private int window_end = 0;
1360 private int window_filled = 0;
1362 public void write(int abyte)
1364 if (window_filled++ == WINDOW_SIZE)
1365 throw new IllegalStateException("Window full");
1366 window[window_end++] = (byte) abyte;
1367 window_end &= WINDOW_MASK;
1371 private final void slowRepeat(int rep_start, int len, int dist)
1375 window[window_end++] = window[rep_start++];
1376 window_end &= WINDOW_MASK;
1377 rep_start &= WINDOW_MASK;
1381 public void repeat(int len, int dist)
1383 if ((window_filled += len) > WINDOW_SIZE)
1384 throw new IllegalStateException("Window full");
1386 int rep_start = (window_end - dist) & WINDOW_MASK;
1387 int border = WINDOW_SIZE - len;
1388 if (rep_start <= border && window_end < border)
1392 System.arraycopy(window, rep_start, window, window_end, len);
1397 /* We have to copy manually, since the repeat pattern overlaps.
1400 window[window_end++] = window[rep_start++];
1404 slowRepeat(rep_start, len, dist);
1407 public int copyStored(StreamManipulator input, int len)
1409 len = Math.min(Math.min(len, WINDOW_SIZE - window_filled),
1410 input.getAvailableBytes());
1413 int tailLen = WINDOW_SIZE - window_end;
1416 copied = input.copyBytes(window, window_end, tailLen);
1417 if (copied == tailLen)
1418 copied += input.copyBytes(window, 0, len - tailLen);
1421 copied = input.copyBytes(window, window_end, len);
1423 window_end = (window_end + copied) & WINDOW_MASK;
1424 window_filled += copied;
1428 public void copyDict(byte[] dict, int offset, int len)
1430 if (window_filled > 0)
1431 throw new IllegalStateException();
1433 if (len > WINDOW_SIZE)
1435 offset += len - WINDOW_SIZE;
1438 System.arraycopy(dict, offset, window, 0, len);
1439 window_end = len & WINDOW_MASK;
1442 public int getFreeSpace()
1444 return WINDOW_SIZE - window_filled;
1447 public int getAvailable()
1449 return window_filled;
1452 public int copyOutput(byte[] output, int offset, int len)
1454 int copy_end = window_end;
1455 if (len > window_filled)
1456 len = window_filled;
1458 copy_end = (window_end - window_filled + len) & WINDOW_MASK;
1461 int tailLen = len - copy_end;
1465 System.arraycopy(window, WINDOW_SIZE - tailLen,
1466 output, offset, tailLen);
1470 System.arraycopy(window, copy_end - len, output, offset, len);
1471 window_filled -= copied;
1472 if (window_filled < 0)
1473 throw new IllegalStateException();
1477 public void reset() {
1478 window_filled = window_end = 0;