jaroslav@640: /* Inflater.java - Decompress a data stream
jaroslav@640:    Copyright (C) 1999, 2000, 2001, 2003  Free Software Foundation, Inc.
jaroslav@640: 
jaroslav@640: This file is part of GNU Classpath.
jaroslav@640: 
jaroslav@640: GNU Classpath is free software; you can redistribute it and/or modify
jaroslav@640: it under the terms of the GNU General Public License as published by
jaroslav@640: the Free Software Foundation; either version 2, or (at your option)
jaroslav@640: any later version.
jaroslav@640:  
jaroslav@640: GNU Classpath is distributed in the hope that it will be useful, but
jaroslav@640: WITHOUT ANY WARRANTY; without even the implied warranty of
jaroslav@640: MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
jaroslav@640: General Public License for more details.
jaroslav@640: 
jaroslav@640: You should have received a copy of the GNU General Public License
jaroslav@640: along with GNU Classpath; see the file COPYING.  If not, write to the
jaroslav@640: Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
jaroslav@640: 02111-1307 USA.
jaroslav@640: 
jaroslav@640: Linking this library statically or dynamically with other modules is
jaroslav@640: making a combined work based on this library.  Thus, the terms and
jaroslav@640: conditions of the GNU General Public License cover the whole
jaroslav@640: combination.
jaroslav@640: 
jaroslav@640: As a special exception, the copyright holders of this library give you
jaroslav@640: permission to link this library with independent modules to produce an
jaroslav@640: executable, regardless of the license terms of these independent
jaroslav@640: modules, and to copy and distribute the resulting executable under
jaroslav@640: terms of your choice, provided that you also meet, for each linked
jaroslav@640: independent module, the terms and conditions of the license of that
jaroslav@640: module.  An independent module is a module which is not derived from
jaroslav@640: or based on this library.  If you modify this library, you may extend
jaroslav@640: this exception to your version of the library, but you are not
jaroslav@640: obligated to do so.  If you do not wish to do so, delete this
jaroslav@640: exception statement from your version. */
jaroslav@609: 
jaroslav@609: package java.util.zip;
jaroslav@609: 
jaroslav@640: import org.apidesign.bck2brwsr.emul.lang.System;
jaroslav@611: 
jaroslav@609: /**
jaroslav@609:  * This class provides support for general purpose decompression using the
jaroslav@609:  * popular ZLIB compression library. The ZLIB compression library was
jaroslav@609:  * initially developed as part of the PNG graphics standard and is not
jaroslav@609:  * protected by patents. It is fully described in the specifications at
jaroslav@609:  * the <a href="package-summary.html#package_description">java.util.zip
jaroslav@609:  * package description</a>.
jaroslav@609:  *
jaroslav@609:  * <p>The following code fragment demonstrates a trivial compression
jaroslav@609:  * and decompression of a string using <tt>Deflater</tt> and
jaroslav@609:  * <tt>Inflater</tt>.
jaroslav@609:  *
jaroslav@609:  * <blockquote><pre>
jaroslav@609:  * try {
jaroslav@609:  *     // Encode a String into bytes
jaroslav@609:  *     String inputString = "blahblahblah\u20AC\u20AC";
jaroslav@609:  *     byte[] input = inputString.getBytes("UTF-8");
jaroslav@609:  *
jaroslav@609:  *     // Compress the bytes
jaroslav@609:  *     byte[] output = new byte[100];
jaroslav@609:  *     Deflater compresser = new Deflater();
jaroslav@609:  *     compresser.setInput(input);
jaroslav@609:  *     compresser.finish();
jaroslav@609:  *     int compressedDataLength = compresser.deflate(output);
jaroslav@609:  *
jaroslav@609:  *     // Decompress the bytes
jaroslav@609:  *     Inflater decompresser = new Inflater();
jaroslav@609:  *     decompresser.setInput(output, 0, compressedDataLength);
jaroslav@609:  *     byte[] result = new byte[100];
jaroslav@609:  *     int resultLength = decompresser.inflate(result);
jaroslav@609:  *     decompresser.end();
jaroslav@609:  *
jaroslav@609:  *     // Decode the bytes into a String
jaroslav@609:  *     String outputString = new String(result, 0, resultLength, "UTF-8");
jaroslav@609:  * } catch(java.io.UnsupportedEncodingException ex) {
jaroslav@609:  *     // handle
jaroslav@609:  * } catch (java.util.zip.DataFormatException ex) {
jaroslav@609:  *     // handle
jaroslav@609:  * }
jaroslav@609:  * </pre></blockquote>
jaroslav@609:  *
jaroslav@609:  * @see         Deflater
jaroslav@609:  * @author      David Connelly
jaroslav@609:  *
jaroslav@609:  */
jaroslav@609: 
jaroslav@640: /* Written using on-line Java Platform 1.2 API Specification
jaroslav@640:  * and JCL book.
jaroslav@640:  * Believed complete and correct.
jaroslav@640:  */
jaroslav@609: 
jaroslav@640: /**
jaroslav@640:  * Inflater is used to decompress data that has been compressed according 
jaroslav@640:  * to the "deflate" standard described in rfc1950.
jaroslav@640:  *
jaroslav@640:  * The usage is as following.  First you have to set some input with
jaroslav@640:  * <code>setInput()</code>, then inflate() it.  If inflate doesn't
jaroslav@640:  * inflate any bytes there may be three reasons:
jaroslav@640:  * <ul>
jaroslav@640:  * <li>needsInput() returns true because the input buffer is empty.
jaroslav@640:  * You have to provide more input with <code>setInput()</code>.  
jaroslav@640:  * NOTE: needsInput() also returns true when, the stream is finished.
jaroslav@640:  * </li>
jaroslav@640:  * <li>needsDictionary() returns true, you have to provide a preset 
jaroslav@640:  *     dictionary with <code>setDictionary()</code>.</li>
jaroslav@640:  * <li>finished() returns true, the inflater has finished.</li>
jaroslav@640:  * </ul>
jaroslav@640:  * Once the first output byte is produced, a dictionary will not be
jaroslav@640:  * needed at a later stage.
jaroslav@640:  *
jaroslav@640:  * @author John Leuner, Jochen Hoenicke
jaroslav@640:  * @author Tom Tromey
jaroslav@640:  * @date May 17, 1999
jaroslav@640:  * @since JDK 1.1
jaroslav@640:  */
jaroslav@640: public class Inflater
jaroslav@640: {
jaroslav@640:   /* Copy lengths for literal codes 257..285 */
jaroslav@640:   private static final int CPLENS[] = 
jaroslav@640:   { 
jaroslav@640:     3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31,
jaroslav@640:     35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258
jaroslav@640:   };
jaroslav@640:   
jaroslav@640:   /* Extra bits for literal codes 257..285 */  
jaroslav@640:   private static final int CPLEXT[] = 
jaroslav@640:   { 
jaroslav@640:     0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2,
jaroslav@640:     3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0
jaroslav@640:   };
jaroslav@640: 
jaroslav@640:   /* Copy offsets for distance codes 0..29 */
jaroslav@640:   private static final int CPDIST[] = {
jaroslav@640:     1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193,
jaroslav@640:     257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145,
jaroslav@640:     8193, 12289, 16385, 24577
jaroslav@640:   };
jaroslav@640:   
jaroslav@640:   /* Extra bits for distance codes */
jaroslav@640:   private static final int CPDEXT[] = {
jaroslav@640:     0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6,
jaroslav@640:     7, 7, 8, 8, 9, 9, 10, 10, 11, 11, 
jaroslav@640:     12, 12, 13, 13
jaroslav@640:   };
jaroslav@640: 
jaroslav@640:   /* This are the state in which the inflater can be.  */
jaroslav@640:   private static final int DECODE_HEADER           = 0;
jaroslav@640:   private static final int DECODE_DICT             = 1;
jaroslav@640:   private static final int DECODE_BLOCKS           = 2;
jaroslav@640:   private static final int DECODE_STORED_LEN1      = 3;
jaroslav@640:   private static final int DECODE_STORED_LEN2      = 4;
jaroslav@640:   private static final int DECODE_STORED           = 5;
jaroslav@640:   private static final int DECODE_DYN_HEADER       = 6;
jaroslav@640:   private static final int DECODE_HUFFMAN          = 7;
jaroslav@640:   private static final int DECODE_HUFFMAN_LENBITS  = 8;
jaroslav@640:   private static final int DECODE_HUFFMAN_DIST     = 9;
jaroslav@640:   private static final int DECODE_HUFFMAN_DISTBITS = 10;
jaroslav@640:   private static final int DECODE_CHKSUM           = 11;
jaroslav@640:   private static final int FINISHED                = 12;
jaroslav@640: 
jaroslav@640:   /** This variable contains the current state. */
jaroslav@640:   private int mode;
jaroslav@640: 
jaroslav@640:   /**
jaroslav@640:    * The adler checksum of the dictionary or of the decompressed
jaroslav@640:    * stream, as it is written in the header resp. footer of the
jaroslav@640:    * compressed stream.  <br>
jaroslav@640:    *
jaroslav@640:    * Only valid if mode is DECODE_DICT or DECODE_CHKSUM.
jaroslav@640:    */
jaroslav@640:   private int readAdler;
jaroslav@640:   /** 
jaroslav@640:    * The number of bits needed to complete the current state.  This
jaroslav@640:    * is valid, if mode is DECODE_DICT, DECODE_CHKSUM,
jaroslav@640:    * DECODE_HUFFMAN_LENBITS or DECODE_HUFFMAN_DISTBITS.  
jaroslav@640:    */
jaroslav@640:   private int neededBits;
jaroslav@640:   private int repLength, repDist;
jaroslav@640:   private int uncomprLen;
jaroslav@640:   /**
jaroslav@640:    * True, if the last block flag was set in the last block of the
jaroslav@640:    * inflated stream.  This means that the stream ends after the
jaroslav@640:    * current block.  
jaroslav@640:    */
jaroslav@640:   private boolean isLastBlock;
jaroslav@640: 
jaroslav@640:   /**
jaroslav@640:    * The total number of inflated bytes.
jaroslav@640:    */
jaroslav@640:   private long totalOut;
jaroslav@640:   /**
jaroslav@640:    * The total number of bytes set with setInput().  This is not the
jaroslav@640:    * value returned by getTotalIn(), since this also includes the 
jaroslav@640:    * unprocessed input.
jaroslav@640:    */
jaroslav@640:   private long totalIn;
jaroslav@640:   /**
jaroslav@640:    * This variable stores the nowrap flag that was given to the constructor.
jaroslav@640:    * True means, that the inflated stream doesn't contain a header nor the
jaroslav@640:    * checksum in the footer.
jaroslav@640:    */
jaroslav@640:   private boolean nowrap;
jaroslav@640: 
jaroslav@640:   private StreamManipulator input;
jaroslav@640:   private OutputWindow outputWindow;
jaroslav@640:   private InflaterDynHeader dynHeader;
jaroslav@640:   private InflaterHuffmanTree litlenTree, distTree;
jaroslav@640:   private Adler32 adler;
jaroslav@640: 
jaroslav@640:   /**
jaroslav@640:    * Creates a new inflater.
jaroslav@640:    */
jaroslav@640:   public Inflater ()
jaroslav@640:   {
jaroslav@640:     this (false);
jaroslav@640:   }
jaroslav@640: 
jaroslav@640:   /**
jaroslav@640:    * Creates a new inflater.
jaroslav@640:    * @param nowrap true if no header and checksum field appears in the
jaroslav@640:    * stream.  This is used for GZIPed input.  For compatibility with
jaroslav@640:    * Sun JDK you should provide one byte of input more than needed in
jaroslav@640:    * this case.
jaroslav@640:    */
jaroslav@640:   public Inflater (boolean nowrap)
jaroslav@640:   {
jaroslav@640:     this.nowrap = nowrap;
jaroslav@640:     this.adler = new Adler32();
jaroslav@640:     input = new StreamManipulator();
jaroslav@640:     outputWindow = new OutputWindow();
jaroslav@640:     mode = nowrap ? DECODE_BLOCKS : DECODE_HEADER;
jaroslav@640:   }
jaroslav@640: 
jaroslav@640:   /**
jaroslav@640:    * Finalizes this object.
jaroslav@640:    */
jaroslav@640:   protected void finalize ()
jaroslav@640:   {
jaroslav@640:     /* Exists only for compatibility */
jaroslav@640:   }
jaroslav@640: 
jaroslav@640:   /**
jaroslav@640:    * Frees all objects allocated by the inflater.  There's no reason
jaroslav@640:    * to call this, since you can just rely on garbage collection (even
jaroslav@640:    * for the Sun implementation).  Exists only for compatibility
jaroslav@640:    * with Sun's JDK, where the compressor allocates native memory.
jaroslav@640:    * If you call any method (even reset) afterwards the behaviour is
jaroslav@640:    * <i>undefined</i>.  
jaroslav@640:    * @deprecated Just clear all references to inflater instead.
jaroslav@640:    */
jaroslav@640:   public void end ()
jaroslav@640:   {
jaroslav@640:     outputWindow = null;
jaroslav@640:     input = null;
jaroslav@640:     dynHeader = null;
jaroslav@640:     litlenTree = null;
jaroslav@640:     distTree = null;
jaroslav@640:     adler = null;
jaroslav@640:   }
jaroslav@640: 
jaroslav@640:   /**
jaroslav@640:    * Returns true, if the inflater has finished.  This means, that no
jaroslav@640:    * input is needed and no output can be produced.
jaroslav@640:    */
jaroslav@640:   public boolean finished() 
jaroslav@640:   {
jaroslav@640:     return mode == FINISHED && outputWindow.getAvailable() == 0;
jaroslav@640:   }
jaroslav@640: 
jaroslav@640:   /**
jaroslav@640:    * Gets the adler checksum.  This is either the checksum of all
jaroslav@640:    * uncompressed bytes returned by inflate(), or if needsDictionary()
jaroslav@640:    * returns true (and thus no output was yet produced) this is the
jaroslav@640:    * adler checksum of the expected dictionary.
jaroslav@640:    * @returns the adler checksum.
jaroslav@640:    */
jaroslav@640:   public int getAdler()
jaroslav@640:   {
jaroslav@640:     return needsDictionary() ? readAdler : (int) adler.getValue();
jaroslav@640:   }
jaroslav@640:   
jaroslav@640:   /**
jaroslav@640:    * Gets the number of unprocessed input.  Useful, if the end of the
jaroslav@640:    * stream is reached and you want to further process the bytes after
jaroslav@640:    * the deflate stream.  
jaroslav@640:    * @return the number of bytes of the input which were not processed.
jaroslav@640:    */
jaroslav@640:   public int getRemaining()
jaroslav@640:   {
jaroslav@640:     return input.getAvailableBytes();
jaroslav@640:   }
jaroslav@640:   
jaroslav@640:   /**
jaroslav@640:    * Gets the total number of processed compressed input bytes.
jaroslav@640:    * @return the total number of bytes of processed input bytes.
jaroslav@640:    */
jaroslav@640:   public int getTotalIn()
jaroslav@640:   {
jaroslav@640:     return (int)getBytesRead();
jaroslav@640:   }
jaroslav@640:   
jaroslav@640:   /**
jaroslav@640:    * Gets the total number of output bytes returned by inflate().
jaroslav@640:    * @return the total number of output bytes.
jaroslav@640:    */
jaroslav@640:   public int getTotalOut()
jaroslav@640:   {
jaroslav@640:     return (int)totalOut;
jaroslav@640:   }
jaroslav@640:   
jaroslav@640:   public long getBytesWritten() {
jaroslav@640:      return totalOut;
jaroslav@640:   }
jaroslav@640: 
jaroslav@640:   public long getBytesRead() {
jaroslav@640:     return totalIn - getRemaining();
jaroslav@640:   }
jaroslav@640:   
jaroslav@640: 
jaroslav@640:   /**
jaroslav@640:    * Inflates the compressed stream to the output buffer.  If this
jaroslav@640:    * returns 0, you should check, whether needsDictionary(),
jaroslav@640:    * needsInput() or finished() returns true, to determine why no 
jaroslav@640:    * further output is produced.
jaroslav@640:    * @param buffer the output buffer.
jaroslav@640:    * @return the number of bytes written to the buffer, 0 if no further
jaroslav@640:    * output can be produced.  
jaroslav@640:    * @exception DataFormatException if deflated stream is invalid.
jaroslav@640:    * @exception IllegalArgumentException if buf has length 0.
jaroslav@640:    */
jaroslav@640:   public int inflate (byte[] buf) throws DataFormatException
jaroslav@640:   {
jaroslav@640:     return inflate (buf, 0, buf.length);
jaroslav@640:   }
jaroslav@640: 
jaroslav@640:   /**
jaroslav@640:    * Inflates the compressed stream to the output buffer.  If this
jaroslav@640:    * returns 0, you should check, whether needsDictionary(),
jaroslav@640:    * needsInput() or finished() returns true, to determine why no 
jaroslav@640:    * further output is produced.
jaroslav@640:    * @param buffer the output buffer.
jaroslav@640:    * @param off the offset into buffer where the output should start.
jaroslav@640:    * @param len the maximum length of the output.
jaroslav@640:    * @return the number of bytes written to the buffer, 0 if no further
jaroslav@640:    * output can be produced.  
jaroslav@640:    * @exception DataFormatException if deflated stream is invalid.
jaroslav@640:    * @exception IndexOutOfBoundsException if the off and/or len are wrong.
jaroslav@640:    */
jaroslav@640:   public int inflate (byte[] buf, int off, int len) throws DataFormatException
jaroslav@640:   {
jaroslav@640:     /* Special case: len may be zero */
jaroslav@640:     if (len == 0)
jaroslav@640:       return 0;
jaroslav@640:     /* Check for correct buff, off, len triple */
jaroslav@640:     if (0 > off || off > off + len || off + len > buf.length)
jaroslav@640:       throw new ArrayIndexOutOfBoundsException();
jaroslav@640:     int count = 0;
jaroslav@640:     int more;
jaroslav@640:     do
jaroslav@640:       {
jaroslav@640: 	if (mode != DECODE_CHKSUM)
jaroslav@640: 	  {
jaroslav@640: 	    /* Don't give away any output, if we are waiting for the
jaroslav@640: 	     * checksum in the input stream.
jaroslav@640: 	     *
jaroslav@640: 	     * With this trick we have always:
jaroslav@640: 	     *   needsInput() and not finished() 
jaroslav@640: 	     *   implies more output can be produced.  
jaroslav@640: 	     */
jaroslav@640: 	    more = outputWindow.copyOutput(buf, off, len);
jaroslav@640: 	    adler.update(buf, off, more);
jaroslav@640: 	    off += more;
jaroslav@640: 	    count += more;
jaroslav@640: 	    totalOut += more;
jaroslav@640: 	    len -= more;
jaroslav@640: 	    if (len == 0)
jaroslav@640: 	      return count;
jaroslav@640: 	  }
jaroslav@640:       }
jaroslav@640:     while (decode() || (outputWindow.getAvailable() > 0
jaroslav@640: 			&& mode != DECODE_CHKSUM));
jaroslav@640:     return count;
jaroslav@640:   }
jaroslav@640: 
jaroslav@640:   /**
jaroslav@640:    * Returns true, if a preset dictionary is needed to inflate the input.
jaroslav@640:    */
jaroslav@640:   public boolean needsDictionary ()
jaroslav@640:   {
jaroslav@640:     return mode == DECODE_DICT && neededBits == 0;
jaroslav@640:   }
jaroslav@640: 
jaroslav@640:   /**
jaroslav@640:    * Returns true, if the input buffer is empty.
jaroslav@640:    * You should then call setInput(). <br>
jaroslav@640:    *
jaroslav@640:    * <em>NOTE</em>: This method also returns true when the stream is finished.
jaroslav@640:    */
jaroslav@640:   public boolean needsInput () 
jaroslav@640:   {
jaroslav@640:     return input.needsInput ();
jaroslav@640:   }
jaroslav@640: 
jaroslav@640:   /**
jaroslav@640:    * Resets the inflater so that a new stream can be decompressed.  All
jaroslav@640:    * pending input and output will be discarded.
jaroslav@640:    */
jaroslav@640:   public void reset ()
jaroslav@640:   {
jaroslav@640:     mode = nowrap ? DECODE_BLOCKS : DECODE_HEADER;
jaroslav@640:     totalIn = totalOut = 0;
jaroslav@640:     input.reset();
jaroslav@640:     outputWindow.reset();
jaroslav@640:     dynHeader = null;
jaroslav@640:     litlenTree = null;
jaroslav@640:     distTree = null;
jaroslav@640:     isLastBlock = false;
jaroslav@640:     adler.reset();
jaroslav@640:   }
jaroslav@640: 
jaroslav@640:   /**
jaroslav@640:    * Sets the preset dictionary.  This should only be called, if
jaroslav@640:    * needsDictionary() returns true and it should set the same
jaroslav@640:    * dictionary, that was used for deflating.  The getAdler()
jaroslav@640:    * function returns the checksum of the dictionary needed.
jaroslav@640:    * @param buffer the dictionary.
jaroslav@640:    * @exception IllegalStateException if no dictionary is needed.
jaroslav@640:    * @exception IllegalArgumentException if the dictionary checksum is
jaroslav@640:    * wrong.  
jaroslav@640:    */
jaroslav@640:   public void setDictionary (byte[] buffer)
jaroslav@640:   {
jaroslav@640:     setDictionary(buffer, 0, buffer.length);
jaroslav@640:   }
jaroslav@640: 
jaroslav@640:   /**
jaroslav@640:    * Sets the preset dictionary.  This should only be called, if
jaroslav@640:    * needsDictionary() returns true and it should set the same
jaroslav@640:    * dictionary, that was used for deflating.  The getAdler()
jaroslav@640:    * function returns the checksum of the dictionary needed.
jaroslav@640:    * @param buffer the dictionary.
jaroslav@640:    * @param off the offset into buffer where the dictionary starts.
jaroslav@640:    * @param len the length of the dictionary.
jaroslav@640:    * @exception IllegalStateException if no dictionary is needed.
jaroslav@640:    * @exception IllegalArgumentException if the dictionary checksum is
jaroslav@640:    * wrong.  
jaroslav@640:    * @exception IndexOutOfBoundsException if the off and/or len are wrong.
jaroslav@640:    */
jaroslav@640:   public void setDictionary (byte[] buffer, int off, int len)
jaroslav@640:   {
jaroslav@640:     if (!needsDictionary())
jaroslav@640:       throw new IllegalStateException();
jaroslav@640: 
jaroslav@640:     adler.update(buffer, off, len);
jaroslav@640:     if ((int) adler.getValue() != readAdler)
jaroslav@640:       throw new IllegalArgumentException("Wrong adler checksum");
jaroslav@640:     adler.reset();
jaroslav@640:     outputWindow.copyDict(buffer, off, len);
jaroslav@640:     mode = DECODE_BLOCKS;
jaroslav@640:   }
jaroslav@640: 
jaroslav@640:   /**
jaroslav@640:    * Sets the input.  This should only be called, if needsInput()
jaroslav@640:    * returns true.
jaroslav@640:    * @param buffer the input.
jaroslav@640:    * @exception IllegalStateException if no input is needed.
jaroslav@640:    */
jaroslav@640:   public void setInput (byte[] buf) 
jaroslav@640:   {
jaroslav@640:     setInput (buf, 0, buf.length);
jaroslav@640:   }
jaroslav@640: 
jaroslav@640:   /**
jaroslav@640:    * Sets the input.  This should only be called, if needsInput()
jaroslav@640:    * returns true.
jaroslav@640:    * @param buffer the input.
jaroslav@640:    * @param off the offset into buffer where the input starts.
jaroslav@640:    * @param len the length of the input.  
jaroslav@640:    * @exception IllegalStateException if no input is needed.
jaroslav@640:    * @exception IndexOutOfBoundsException if the off and/or len are wrong.
jaroslav@640:    */
jaroslav@640:   public void setInput (byte[] buf, int off, int len) 
jaroslav@640:   {
jaroslav@640:     input.setInput (buf, off, len);
jaroslav@640:     totalIn += len;
jaroslav@640:   }
jaroslav@640:   private static final int DEFLATED = 8;
jaroslav@640:   /**
jaroslav@640:    * Decodes the deflate header.
jaroslav@640:    * @return false if more input is needed. 
jaroslav@640:    * @exception DataFormatException if header is invalid.
jaroslav@640:    */
jaroslav@640:   private boolean decodeHeader () throws DataFormatException
jaroslav@640:   {
jaroslav@640:     int header = input.peekBits(16);
jaroslav@640:     if (header < 0)
jaroslav@640:       return false;
jaroslav@640:     input.dropBits(16);
jaroslav@640:     
jaroslav@640:     /* The header is written in "wrong" byte order */
jaroslav@640:     header = ((header << 8) | (header >> 8)) & 0xffff;
jaroslav@640:     if (header % 31 != 0)
jaroslav@640:       throw new DataFormatException("Header checksum illegal");
jaroslav@640:     
jaroslav@640:     if ((header & 0x0f00) != (DEFLATED << 8))
jaroslav@640:       throw new DataFormatException("Compression Method unknown");
jaroslav@640: 
jaroslav@640:     /* Maximum size of the backwards window in bits. 
jaroslav@640:      * We currently ignore this, but we could use it to make the
jaroslav@640:      * inflater window more space efficient. On the other hand the
jaroslav@640:      * full window (15 bits) is needed most times, anyway.
jaroslav@640:      int max_wbits = ((header & 0x7000) >> 12) + 8;
jaroslav@640:      */
jaroslav@640:     
jaroslav@640:     if ((header & 0x0020) == 0) // Dictionary flag?
jaroslav@640:       {
jaroslav@640: 	mode = DECODE_BLOCKS;
jaroslav@640:       }
jaroslav@640:     else
jaroslav@640:       {
jaroslav@640: 	mode = DECODE_DICT;
jaroslav@640: 	neededBits = 32;      
jaroslav@640:       }
jaroslav@640:     return true;
jaroslav@640:   }
jaroslav@640:    
jaroslav@640:   /**
jaroslav@640:    * Decodes the dictionary checksum after the deflate header.
jaroslav@640:    * @return false if more input is needed. 
jaroslav@640:    */
jaroslav@640:   private boolean decodeDict ()
jaroslav@640:   {
jaroslav@640:     while (neededBits > 0)
jaroslav@640:       {
jaroslav@640: 	int dictByte = input.peekBits(8);
jaroslav@640: 	if (dictByte < 0)
jaroslav@640: 	  return false;
jaroslav@640: 	input.dropBits(8);
jaroslav@640: 	readAdler = (readAdler << 8) | dictByte;
jaroslav@640: 	neededBits -= 8;
jaroslav@640:       }
jaroslav@640:     return false;
jaroslav@640:   }
jaroslav@640: 
jaroslav@640:   /**
jaroslav@640:    * Decodes the huffman encoded symbols in the input stream.
jaroslav@640:    * @return false if more input is needed, true if output window is
jaroslav@640:    * full or the current block ends.
jaroslav@640:    * @exception DataFormatException if deflated stream is invalid.  
jaroslav@640:    */
jaroslav@640:   private boolean decodeHuffman () throws DataFormatException
jaroslav@640:   {
jaroslav@640:     int free = outputWindow.getFreeSpace();
jaroslav@640:     while (free >= 258)
jaroslav@640:       {
jaroslav@640: 	int symbol;
jaroslav@640: 	switch (mode)
jaroslav@640: 	  {
jaroslav@640: 	  case DECODE_HUFFMAN:
jaroslav@640: 	    /* This is the inner loop so it is optimized a bit */
jaroslav@640: 	    while (((symbol = litlenTree.getSymbol(input)) & ~0xff) == 0)
jaroslav@640: 	      {
jaroslav@640: 		outputWindow.write(symbol);
jaroslav@640: 		if (--free < 258)
jaroslav@640: 		  return true;
jaroslav@640: 	      } 
jaroslav@640: 	    if (symbol < 257)
jaroslav@640: 	      {
jaroslav@640: 		if (symbol < 0)
jaroslav@640: 		  return false;
jaroslav@640: 		else
jaroslav@640: 		  {
jaroslav@640: 		    /* symbol == 256: end of block */
jaroslav@640: 		    distTree = null;
jaroslav@640: 		    litlenTree = null;
jaroslav@640: 		    mode = DECODE_BLOCKS;
jaroslav@640: 		    return true;
jaroslav@640: 		  }
jaroslav@640: 	      }
jaroslav@640: 		
jaroslav@640: 	    try
jaroslav@640: 	      {
jaroslav@640: 		repLength = CPLENS[symbol - 257];
jaroslav@640: 		neededBits = CPLEXT[symbol - 257];
jaroslav@640: 	      }
jaroslav@640: 	    catch (ArrayIndexOutOfBoundsException ex)
jaroslav@640: 	      {
jaroslav@640: 		throw new DataFormatException("Illegal rep length code");
jaroslav@640: 	      }
jaroslav@640: 	    /* fall through */
jaroslav@640: 	  case DECODE_HUFFMAN_LENBITS:
jaroslav@640: 	    if (neededBits > 0)
jaroslav@640: 	      {
jaroslav@640: 		mode = DECODE_HUFFMAN_LENBITS;
jaroslav@640: 		int i = input.peekBits(neededBits);
jaroslav@640: 		if (i < 0)
jaroslav@640: 		  return false;
jaroslav@640: 		input.dropBits(neededBits);
jaroslav@640: 		repLength += i;
jaroslav@640: 	      }
jaroslav@640: 	    mode = DECODE_HUFFMAN_DIST;
jaroslav@640: 	    /* fall through */
jaroslav@640: 	  case DECODE_HUFFMAN_DIST:
jaroslav@640: 	    symbol = distTree.getSymbol(input);
jaroslav@640: 	    if (symbol < 0)
jaroslav@640: 	      return false;
jaroslav@640: 	    try 
jaroslav@640: 	      {
jaroslav@640: 		repDist = CPDIST[symbol];
jaroslav@640: 		neededBits = CPDEXT[symbol];
jaroslav@640: 	      }
jaroslav@640: 	    catch (ArrayIndexOutOfBoundsException ex)
jaroslav@640: 	      {
jaroslav@640: 		throw new DataFormatException("Illegal rep dist code");
jaroslav@640: 	      }
jaroslav@640: 	    /* fall through */
jaroslav@640: 	  case DECODE_HUFFMAN_DISTBITS:
jaroslav@640: 	    if (neededBits > 0)
jaroslav@640: 	      {
jaroslav@640: 		mode = DECODE_HUFFMAN_DISTBITS;
jaroslav@640: 		int i = input.peekBits(neededBits);
jaroslav@640: 		if (i < 0)
jaroslav@640: 		  return false;
jaroslav@640: 		input.dropBits(neededBits);
jaroslav@640: 		repDist += i;
jaroslav@640: 	      }
jaroslav@640: 	    outputWindow.repeat(repLength, repDist);
jaroslav@640: 	    free -= repLength;
jaroslav@640: 	    mode = DECODE_HUFFMAN;
jaroslav@640: 	    break;
jaroslav@640: 	  default:
jaroslav@640: 	    throw new IllegalStateException();
jaroslav@640: 	  }
jaroslav@640:       }
jaroslav@640:     return true;
jaroslav@640:   }
jaroslav@640: 
jaroslav@640:   /**
jaroslav@640:    * Decodes the adler checksum after the deflate stream.
jaroslav@640:    * @return false if more input is needed. 
jaroslav@640:    * @exception DataFormatException if checksum doesn't match.
jaroslav@640:    */
jaroslav@640:   private boolean decodeChksum () throws DataFormatException
jaroslav@640:   {
jaroslav@640:     while (neededBits > 0)
jaroslav@640:       {
jaroslav@640: 	int chkByte = input.peekBits(8);
jaroslav@640: 	if (chkByte < 0)
jaroslav@640: 	  return false;
jaroslav@640: 	input.dropBits(8);
jaroslav@640: 	readAdler = (readAdler << 8) | chkByte;
jaroslav@640: 	neededBits -= 8;
jaroslav@640:       }
jaroslav@640:     if ((int) adler.getValue() != readAdler)
jaroslav@640:       throw new DataFormatException("Adler chksum doesn't match: "
jaroslav@640: 				    +Integer.toHexString((int)adler.getValue())
jaroslav@640: 				    +" vs. "+Integer.toHexString(readAdler));
jaroslav@640:     mode = FINISHED;
jaroslav@640:     return false;
jaroslav@640:   }
jaroslav@640: 
jaroslav@640:   /**
jaroslav@640:    * Decodes the deflated stream.
jaroslav@640:    * @return false if more input is needed, or if finished. 
jaroslav@640:    * @exception DataFormatException if deflated stream is invalid.
jaroslav@640:    */
jaroslav@640:   private boolean decode () throws DataFormatException
jaroslav@640:   {
jaroslav@640:     switch (mode) 
jaroslav@640:       {
jaroslav@640:       case DECODE_HEADER:
jaroslav@640: 	return decodeHeader();
jaroslav@640:       case DECODE_DICT:
jaroslav@640: 	return decodeDict();
jaroslav@640:       case DECODE_CHKSUM:
jaroslav@640: 	return decodeChksum();
jaroslav@640: 
jaroslav@640:       case DECODE_BLOCKS:
jaroslav@640: 	if (isLastBlock)
jaroslav@640: 	  {
jaroslav@640: 	    if (nowrap)
jaroslav@640: 	      {
jaroslav@640: 		mode = FINISHED;
jaroslav@640: 		return false;
jaroslav@640: 	      }
jaroslav@640: 	    else
jaroslav@640: 	      {
jaroslav@640: 		input.skipToByteBoundary();
jaroslav@640: 		neededBits = 32;
jaroslav@640: 		mode = DECODE_CHKSUM;
jaroslav@640: 		return true;
jaroslav@640: 	      }
jaroslav@640: 	  }
jaroslav@640: 
jaroslav@640: 	int type = input.peekBits(3);
jaroslav@640: 	if (type < 0)
jaroslav@640: 	  return false;
jaroslav@640: 	input.dropBits(3);
jaroslav@640: 
jaroslav@640: 	if ((type & 1) != 0)
jaroslav@640: 	  isLastBlock = true;
jaroslav@640: 	switch (type >> 1)
jaroslav@640: 	  {
jaroslav@640: 	  case DeflaterConstants.STORED_BLOCK:
jaroslav@640: 	    input.skipToByteBoundary();
jaroslav@640: 	    mode = DECODE_STORED_LEN1;
jaroslav@640: 	    break;
jaroslav@640: 	  case DeflaterConstants.STATIC_TREES:
jaroslav@640: 	    litlenTree = InflaterHuffmanTree.defLitLenTree;
jaroslav@640: 	    distTree = InflaterHuffmanTree.defDistTree;
jaroslav@640: 	    mode = DECODE_HUFFMAN;
jaroslav@640: 	    break;
jaroslav@640: 	  case DeflaterConstants.DYN_TREES:
jaroslav@640: 	    dynHeader = new InflaterDynHeader();
jaroslav@640: 	    mode = DECODE_DYN_HEADER;
jaroslav@640: 	    break;
jaroslav@640: 	  default:
jaroslav@640: 	    throw new DataFormatException("Unknown block type "+type);
jaroslav@640: 	  }
jaroslav@640: 	return true;
jaroslav@640: 
jaroslav@640:       case DECODE_STORED_LEN1:
jaroslav@640: 	{
jaroslav@640: 	  if ((uncomprLen = input.peekBits(16)) < 0)
jaroslav@640: 	    return false;
jaroslav@640: 	  input.dropBits(16);
jaroslav@640: 	  mode = DECODE_STORED_LEN2;
jaroslav@640: 	}
jaroslav@640: 	/* fall through */
jaroslav@640:       case DECODE_STORED_LEN2:
jaroslav@640: 	{
jaroslav@640: 	  int nlen = input.peekBits(16);
jaroslav@640: 	  if (nlen < 0)
jaroslav@640: 	    return false;
jaroslav@640: 	  input.dropBits(16);
jaroslav@640: 	  if (nlen != (uncomprLen ^ 0xffff))
jaroslav@640: 	    throw new DataFormatException("broken uncompressed block");
jaroslav@640: 	  mode = DECODE_STORED;
jaroslav@640: 	}
jaroslav@640: 	/* fall through */
jaroslav@640:       case DECODE_STORED:
jaroslav@640: 	{
jaroslav@640: 	  int more = outputWindow.copyStored(input, uncomprLen);
jaroslav@640: 	  uncomprLen -= more;
jaroslav@640: 	  if (uncomprLen == 0)
jaroslav@640: 	    {
jaroslav@640: 	      mode = DECODE_BLOCKS;
jaroslav@640: 	      return true;
jaroslav@640: 	    }
jaroslav@640: 	  return !input.needsInput();
jaroslav@640: 	}
jaroslav@640: 
jaroslav@640:       case DECODE_DYN_HEADER:
jaroslav@640: 	if (!dynHeader.decode(input))
jaroslav@640: 	  return false;
jaroslav@640: 	litlenTree = dynHeader.buildLitLenTree();
jaroslav@640: 	distTree = dynHeader.buildDistTree();
jaroslav@640: 	mode = DECODE_HUFFMAN;
jaroslav@640: 	/* fall through */
jaroslav@640:       case DECODE_HUFFMAN:
jaroslav@640:       case DECODE_HUFFMAN_LENBITS:
jaroslav@640:       case DECODE_HUFFMAN_DIST:
jaroslav@640:       case DECODE_HUFFMAN_DISTBITS:
jaroslav@640: 	return decodeHuffman();
jaroslav@640:       case FINISHED:
jaroslav@640: 	return false;
jaroslav@640:       default:
jaroslav@640: 	throw new IllegalStateException();
jaroslav@640:       }	
jaroslav@640:   }
jaroslav@640: 
jaroslav@640: 
jaroslav@640:     interface DeflaterConstants {
jaroslav@640:       final static boolean DEBUGGING = false;
jaroslav@640: 
jaroslav@640:       final static int STORED_BLOCK = 0;
jaroslav@640:       final static int STATIC_TREES = 1;
jaroslav@640:       final static int DYN_TREES    = 2;
jaroslav@640:       final static int PRESET_DICT  = 0x20;
jaroslav@640: 
jaroslav@640:       final static int DEFAULT_MEM_LEVEL = 8;
jaroslav@640: 
jaroslav@640:       final static int MAX_MATCH = 258;
jaroslav@640:       final static int MIN_MATCH = 3;
jaroslav@640: 
jaroslav@640:       final static int MAX_WBITS = 15;
jaroslav@640:       final static int WSIZE = 1 << MAX_WBITS;
jaroslav@640:       final static int WMASK = WSIZE - 1;
jaroslav@640: 
jaroslav@640:       final static int HASH_BITS = DEFAULT_MEM_LEVEL + 7;
jaroslav@640:       final static int HASH_SIZE = 1 << HASH_BITS;
jaroslav@640:       final static int HASH_MASK = HASH_SIZE - 1;
jaroslav@640:       final static int HASH_SHIFT = (HASH_BITS + MIN_MATCH - 1) / MIN_MATCH;
jaroslav@640: 
jaroslav@640:       final static int MIN_LOOKAHEAD = MAX_MATCH + MIN_MATCH + 1;
jaroslav@640:       final static int MAX_DIST = WSIZE - MIN_LOOKAHEAD;
jaroslav@640: 
jaroslav@640:       final static int PENDING_BUF_SIZE = 1 << (DEFAULT_MEM_LEVEL + 8);
jaroslav@640:       final static int MAX_BLOCK_SIZE = Math.min(65535, PENDING_BUF_SIZE-5);
jaroslav@640: 
jaroslav@640:       final static int DEFLATE_STORED = 0;
jaroslav@640:       final static int DEFLATE_FAST   = 1;
jaroslav@640:       final static int DEFLATE_SLOW   = 2;
jaroslav@640: 
jaroslav@640:       final static int GOOD_LENGTH[] = { 0,4, 4, 4, 4, 8,  8,  8,  32,  32 };
jaroslav@640:       final static int MAX_LAZY[]    = { 0,4, 5, 6, 4,16, 16, 32, 128, 258 };
jaroslav@640:       final static int NICE_LENGTH[] = { 0,8,16,32,16,32,128,128, 258, 258 };
jaroslav@640:       final static int MAX_CHAIN[]   = { 0,4, 8,32,16,32,128,256,1024,4096 };
jaroslav@640:       final static int COMPR_FUNC[]  = { 0,1, 1, 1, 1, 2,  2,  2,   2,   2 };
jaroslav@640:     }
jaroslav@640:     private static class InflaterHuffmanTree {
jaroslav@640:       private final static int MAX_BITLEN = 15;
jaroslav@640:       private short[] tree;
jaroslav@640: 
jaroslav@640:       public static InflaterHuffmanTree defLitLenTree, defDistTree;
jaroslav@640: 
jaroslav@640:       static
jaroslav@640:       {
jaroslav@640:         try 
jaroslav@640:           {
jaroslav@640:         byte[] codeLengths = new byte[288];
jaroslav@640:         int i = 0;
jaroslav@640:         while (i < 144)
jaroslav@640:           codeLengths[i++] = 8;
jaroslav@640:         while (i < 256)
jaroslav@640:           codeLengths[i++] = 9;
jaroslav@640:         while (i < 280)
jaroslav@640:           codeLengths[i++] = 7;
jaroslav@640:         while (i < 288)
jaroslav@640:           codeLengths[i++] = 8;
jaroslav@640:         defLitLenTree = new InflaterHuffmanTree(codeLengths);
jaroslav@640: 
jaroslav@640:         codeLengths = new byte[32];
jaroslav@640:         i = 0;
jaroslav@640:         while (i < 32)
jaroslav@640:           codeLengths[i++] = 5;
jaroslav@640:         defDistTree = new InflaterHuffmanTree(codeLengths);
jaroslav@640:           } 
jaroslav@640:         catch (DataFormatException ex)
jaroslav@640:           {
jaroslav@640:         throw new IllegalStateException
jaroslav@640:           ("InflaterHuffmanTree: static tree length illegal");
jaroslav@640:           }
jaroslav@640:       }
jaroslav@640: 
jaroslav@640:       /**
jaroslav@640:        * Constructs a Huffman tree from the array of code lengths.
jaroslav@640:        *
jaroslav@640:        * @param codeLengths the array of code lengths
jaroslav@640:        */
jaroslav@640:       public InflaterHuffmanTree(byte[] codeLengths) throws DataFormatException
jaroslav@640:       {
jaroslav@640:         buildTree(codeLengths);
jaroslav@640:       }
jaroslav@640: 
jaroslav@640:       private void buildTree(byte[] codeLengths) throws DataFormatException
jaroslav@640:       {
jaroslav@640:         int[] blCount = new int[MAX_BITLEN+1];
jaroslav@640:         int[] nextCode = new int[MAX_BITLEN+1];
jaroslav@640:         for (int i = 0; i < codeLengths.length; i++)
jaroslav@640:           {
jaroslav@640:         int bits = codeLengths[i];
jaroslav@640:         if (bits > 0)
jaroslav@640:           blCount[bits]++;
jaroslav@640:           }
jaroslav@640: 
jaroslav@640:         int code = 0;
jaroslav@640:         int treeSize = 512;
jaroslav@640:         for (int bits = 1; bits <= MAX_BITLEN; bits++)
jaroslav@640:           {
jaroslav@640:         nextCode[bits] = code;
jaroslav@640:         code += blCount[bits] << (16 - bits);
jaroslav@640:         if (bits >= 10)
jaroslav@640:           {
jaroslav@640:             /* We need an extra table for bit lengths >= 10. */
jaroslav@640:             int start = nextCode[bits] & 0x1ff80;
jaroslav@640:             int end   = code & 0x1ff80;
jaroslav@640:             treeSize += (end - start) >> (16 - bits);
jaroslav@640:           }
jaroslav@640:           }
jaroslav@640:         if (code != 65536)
jaroslav@640:           throw new DataFormatException("Code lengths don't add up properly.");
jaroslav@640: 
jaroslav@687:         fillTable1(treeSize, code, blCount);
jaroslav@640: 
jaroslav@640:         for (int i = 0; i < codeLengths.length; i++)
jaroslav@640:           {
jaroslav@640:         int bits = codeLengths[i];
jaroslav@640:         if (bits == 0)
jaroslav@640:           continue;
jaroslav@640:         code = nextCode[bits];
jaroslav@640:         int revcode = bitReverse(code);
jaroslav@640:         if (bits <= 9)
jaroslav@640:           {
jaroslav@640:             do
jaroslav@640:               {
jaroslav@640:             tree[revcode] = (short) ((i << 4) | bits);
jaroslav@640:             revcode += 1 << bits;
jaroslav@640:               }
jaroslav@640:             while (revcode < 512);
jaroslav@640:           }
jaroslav@640:         else
jaroslav@640:           {
jaroslav@640:             int subTree = tree[revcode & 511];
jaroslav@640:             int treeLen = 1 << (subTree & 15);
jaroslav@640:             subTree = -(subTree >> 4);
jaroslav@640:             do
jaroslav@640:               { 
jaroslav@640:             tree[subTree | (revcode >> 9)] = (short) ((i << 4) | bits);
jaroslav@640:             revcode += 1 << bits;
jaroslav@640:               }
jaroslav@640:             while (revcode < treeLen);
jaroslav@640:           }
jaroslav@640:         nextCode[bits] = code + (1 << (16 - bits));
jaroslav@640:           }
jaroslav@640:       }
jaroslav@640:       private final static String bit4Reverse =
jaroslav@640:         "\000\010\004\014\002\012\006\016\001\011\005\015\003\013\007\017";
jaroslav@640:       static short bitReverse(int value) {
jaroslav@640:             return (short) (bit4Reverse.charAt(value & 0xf) << 12
jaroslav@687:                     | bit4Reverse.charAt((value >> 4) & 0xf) << 8
jaroslav@687:                     | bit4Reverse.charAt((value >> 8) & 0xf) << 4
jaroslav@687:                     | bit4Reverse.charAt(value >> 12));
jaroslav@640:       }
jaroslav@687:       
jaroslav@640:       /**
jaroslav@640:        * Reads the next symbol from input.  The symbol is encoded using the
jaroslav@640:        * huffman tree.
jaroslav@640:        * @param input the input source.
jaroslav@640:        * @return the next symbol, or -1 if not enough input is available.
jaroslav@640:        */
jaroslav@640:       public int getSymbol(StreamManipulator input) throws DataFormatException
jaroslav@640:       {
jaroslav@640:         int lookahead, symbol;
jaroslav@640:         if ((lookahead = input.peekBits(9)) >= 0)
jaroslav@640:           {
jaroslav@640:         if ((symbol = tree[lookahead]) >= 0)
jaroslav@640:           {
jaroslav@640:             input.dropBits(symbol & 15);
jaroslav@640:             return symbol >> 4;
jaroslav@640:           }
jaroslav@640:         int subtree = -(symbol >> 4);
jaroslav@640:         int bitlen = symbol & 15;
jaroslav@640:         if ((lookahead = input.peekBits(bitlen)) >= 0)
jaroslav@640:           {
jaroslav@640:             symbol = tree[subtree | (lookahead >> 9)];
jaroslav@640:             input.dropBits(symbol & 15);
jaroslav@640:             return symbol >> 4;
jaroslav@640:           }
jaroslav@640:         else
jaroslav@640:           {
jaroslav@640:             int bits = input.getAvailableBits();
jaroslav@640:             lookahead = input.peekBits(bits);
jaroslav@640:             symbol = tree[subtree | (lookahead >> 9)];
jaroslav@640:             if ((symbol & 15) <= bits)
jaroslav@640:               {
jaroslav@640:             input.dropBits(symbol & 15);
jaroslav@640:             return symbol >> 4;
jaroslav@640:               }
jaroslav@640:             else
jaroslav@640:               return -1;
jaroslav@640:           }
jaroslav@640:           }
jaroslav@640:         else
jaroslav@640:           {
jaroslav@640:         int bits = input.getAvailableBits();
jaroslav@640:         lookahead = input.peekBits(bits);
jaroslav@640:         symbol = tree[lookahead];
jaroslav@640:         if (symbol >= 0 && (symbol & 15) <= bits)
jaroslav@640:           {
jaroslav@640:             input.dropBits(symbol & 15);
jaroslav@640:             return symbol >> 4;
jaroslav@640:           }
jaroslav@640:         else
jaroslav@640:           return -1;
jaroslav@640:           }
jaroslav@640:       }
jaroslav@687: 
jaroslav@687:         private void fillTable1(int treeSize, int code, int[] blCount) {
jaroslav@687:             /* Now create and fill the extra tables from longest to shortest
jaroslav@687:              * bit len.  This way the sub trees will be aligned.
jaroslav@687:              */
jaroslav@687:             tree = new short[treeSize];
jaroslav@687:             int treePtr = 512;
jaroslav@687:             for (int bits = MAX_BITLEN; bits >= 10; bits--) {
jaroslav@687:                 int end = code & 0x1ff80;
jaroslav@687:                 code -= blCount[bits] << (16 - bits);
jaroslav@687:                 int start = code & 0x1ff80;
jaroslav@687:                 final int inc = 1 << 7;
jaroslav@687:                 fillTable2(start, end, inc, treePtr, bits);
jaroslav@687:             }
jaroslav@687:         }
jaroslav@687: 
jaroslav@687:         private void fillTable2(int start, int end, final int inc, int treePtr, int bits) {
jaroslav@687:             for (int i = start; i < end; i += inc) {
jaroslav@687:                 final short br = bitReverse(i);
jaroslav@687:                 tree[br] = (short) ((-treePtr << 4) | bits);
jaroslav@687:                 treePtr += 1 << (bits - 9);
jaroslav@687:             }
jaroslav@687:         }
jaroslav@640:     }
jaroslav@640:     private static class InflaterDynHeader
jaroslav@640:     {
jaroslav@640:       private static final int LNUM   = 0;
jaroslav@640:       private static final int DNUM   = 1;
jaroslav@640:       private static final int BLNUM  = 2;
jaroslav@640:       private static final int BLLENS = 3;
jaroslav@640:       private static final int LENS   = 4;
jaroslav@640:       private static final int REPS   = 5;
jaroslav@640: 
jaroslav@640:       private static final int repMin[]  = { 3, 3, 11 };
jaroslav@640:       private static final int repBits[] = { 2, 3,  7 };
jaroslav@640: 
jaroslav@640: 
jaroslav@640:       private byte[] blLens;
jaroslav@640:       private byte[] litdistLens;
jaroslav@640: 
jaroslav@640:       private InflaterHuffmanTree blTree;
jaroslav@640: 
jaroslav@640:       private int mode;
jaroslav@640:       private int lnum, dnum, blnum, num;
jaroslav@640:       private int repSymbol;
jaroslav@640:       private byte lastLen;
jaroslav@640:       private int ptr;
jaroslav@640: 
jaroslav@640:       private static final int[] BL_ORDER =
jaroslav@640:       { 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15 };
jaroslav@640: 
jaroslav@640:       public InflaterDynHeader()
jaroslav@640:       {
jaroslav@640:       }
jaroslav@640: 
jaroslav@640:       public boolean decode(StreamManipulator input) throws DataFormatException
jaroslav@640:       {
jaroslav@640:       decode_loop:
jaroslav@640:         for (;;)
jaroslav@640:           {
jaroslav@640:         switch (mode)
jaroslav@640:           {
jaroslav@640:           case LNUM:
jaroslav@640:             lnum = input.peekBits(5);
jaroslav@640:             if (lnum < 0)
jaroslav@640:               return false;
jaroslav@640:             lnum += 257;
jaroslav@640:             input.dropBits(5);
jaroslav@640:     //  	    System.err.println("LNUM: "+lnum);
jaroslav@640:             mode = DNUM;
jaroslav@640:             /* fall through */
jaroslav@640:           case DNUM:
jaroslav@640:             dnum = input.peekBits(5);
jaroslav@640:             if (dnum < 0)
jaroslav@640:               return false;
jaroslav@640:             dnum++;
jaroslav@640:             input.dropBits(5);
jaroslav@640:     //  	    System.err.println("DNUM: "+dnum);
jaroslav@640:             num = lnum+dnum;
jaroslav@640:             litdistLens = new byte[num];
jaroslav@640:             mode = BLNUM;
jaroslav@640:             /* fall through */
jaroslav@640:           case BLNUM:
jaroslav@640:             blnum = input.peekBits(4);
jaroslav@640:             if (blnum < 0)
jaroslav@640:               return false;
jaroslav@640:             blnum += 4;
jaroslav@640:             input.dropBits(4);
jaroslav@640:             blLens = new byte[19];
jaroslav@640:             ptr = 0;
jaroslav@640:     //  	    System.err.println("BLNUM: "+blnum);
jaroslav@640:             mode = BLLENS;
jaroslav@640:             /* fall through */
jaroslav@640:           case BLLENS:
jaroslav@640:             while (ptr < blnum)
jaroslav@640:               {
jaroslav@640:             int len = input.peekBits(3);
jaroslav@640:             if (len < 0)
jaroslav@640:               return false;
jaroslav@640:             input.dropBits(3);
jaroslav@640:     //  		System.err.println("blLens["+BL_ORDER[ptr]+"]: "+len);
jaroslav@640:             blLens[BL_ORDER[ptr]] = (byte) len;
jaroslav@640:             ptr++;
jaroslav@640:               }
jaroslav@640:             blTree = new InflaterHuffmanTree(blLens);
jaroslav@640:             blLens = null;
jaroslav@640:             ptr = 0;
jaroslav@640:             mode = LENS;
jaroslav@640:             /* fall through */
jaroslav@640:           case LENS:
jaroslav@640:             {
jaroslav@640:               int symbol;
jaroslav@640:               while (((symbol = blTree.getSymbol(input)) & ~15) == 0)
jaroslav@640:             {
jaroslav@640:               /* Normal case: symbol in [0..15] */
jaroslav@640: 
jaroslav@640:     //  		  System.err.println("litdistLens["+ptr+"]: "+symbol);
jaroslav@640:               litdistLens[ptr++] = lastLen = (byte) symbol;
jaroslav@640: 
jaroslav@640:               if (ptr == num)
jaroslav@640:                 {
jaroslav@640:                   /* Finished */
jaroslav@640:                   return true;
jaroslav@640:                 }
jaroslav@640:             }
jaroslav@640: 
jaroslav@640:               /* need more input ? */
jaroslav@640:               if (symbol < 0)
jaroslav@640:             return false;
jaroslav@640: 
jaroslav@640:               /* otherwise repeat code */
jaroslav@640:               if (symbol >= 17)
jaroslav@640:             {
jaroslav@640:               /* repeat zero */
jaroslav@640:     //  		  System.err.println("repeating zero");
jaroslav@640:               lastLen = 0;
jaroslav@640:             }
jaroslav@640:               else
jaroslav@640:             {
jaroslav@640:               if (ptr == 0)
jaroslav@640:                 throw new DataFormatException();
jaroslav@640:             }
jaroslav@640:               repSymbol = symbol-16;
jaroslav@640:               mode = REPS;
jaroslav@640:             }
jaroslav@640:             /* fall through */
jaroslav@640: 
jaroslav@640:           case REPS:
jaroslav@640:             {
jaroslav@640:               int bits = repBits[repSymbol];
jaroslav@640:               int count = input.peekBits(bits);
jaroslav@640:               if (count < 0)
jaroslav@640:             return false;
jaroslav@640:               input.dropBits(bits);
jaroslav@640:               count += repMin[repSymbol];
jaroslav@640:     //  	      System.err.println("litdistLens repeated: "+count);
jaroslav@640: 
jaroslav@640:               if (ptr + count > num)
jaroslav@640:             throw new DataFormatException();
jaroslav@640:               while (count-- > 0)
jaroslav@640:             litdistLens[ptr++] = lastLen;
jaroslav@640: 
jaroslav@640:               if (ptr == num)
jaroslav@640:             {
jaroslav@640:               /* Finished */
jaroslav@640:               return true;
jaroslav@640:             }
jaroslav@640:             }
jaroslav@640:             mode = LENS;
jaroslav@640:             continue decode_loop;
jaroslav@640:           }
jaroslav@640:           }
jaroslav@640:       }
jaroslav@640: 
jaroslav@640:       public InflaterHuffmanTree buildLitLenTree() throws DataFormatException
jaroslav@640:       {
jaroslav@640:         byte[] litlenLens = new byte[lnum];
jaroslav@640:         System.arraycopy(litdistLens, 0, litlenLens, 0, lnum);
jaroslav@640:         return new InflaterHuffmanTree(litlenLens);
jaroslav@640:       }
jaroslav@640: 
jaroslav@640:       public InflaterHuffmanTree buildDistTree() throws DataFormatException
jaroslav@640:       {
jaroslav@640:         byte[] distLens = new byte[dnum];
jaroslav@640:         System.arraycopy(litdistLens, lnum, distLens, 0, dnum);
jaroslav@640:         return new InflaterHuffmanTree(distLens);
jaroslav@640:       }
jaroslav@640:     }
jaroslav@609:     /**
jaroslav@640:      * This class allows us to retrieve a specified amount of bits from
jaroslav@640:      * the input buffer, as well as copy big byte blocks.
jaroslav@609:      *
jaroslav@640:      * It uses an int buffer to store up to 31 bits for direct
jaroslav@640:      * manipulation.  This guarantees that we can get at least 16 bits,
jaroslav@640:      * but we only need at most 15, so this is all safe.
jaroslav@640:      *
jaroslav@640:      * There are some optimizations in this class, for example, you must
jaroslav@640:      * never peek more then 8 bits more than needed, and you must first 
jaroslav@640:      * peek bits before you may drop them.  This is not a general purpose
jaroslav@640:      * class but optimized for the behaviour of the Inflater.
jaroslav@640:      *
jaroslav@640:      * @author John Leuner, Jochen Hoenicke
jaroslav@609:      */
jaroslav@640: 
jaroslav@640:     private static class StreamManipulator
jaroslav@640:     {
jaroslav@640:       private byte[] window;
jaroslav@640:       private int window_start = 0;
jaroslav@640:       private int window_end = 0;
jaroslav@640: 
jaroslav@640:       private int buffer = 0;
jaroslav@640:       private int bits_in_buffer = 0;
jaroslav@640: 
jaroslav@640:       /**
jaroslav@640:        * Get the next n bits but don't increase input pointer.  n must be
jaroslav@640:        * less or equal 16 and if you if this call succeeds, you must drop
jaroslav@640:        * at least n-8 bits in the next call.
jaroslav@640:        * 
jaroslav@640:        * @return the value of the bits, or -1 if not enough bits available.  */
jaroslav@640:       public final int peekBits(int n)
jaroslav@640:       {
jaroslav@640:         if (bits_in_buffer < n)
jaroslav@640:           {
jaroslav@640:         if (window_start == window_end)
jaroslav@640:           return -1;
jaroslav@640:         buffer |= (window[window_start++] & 0xff
jaroslav@640:                | (window[window_start++] & 0xff) << 8) << bits_in_buffer;
jaroslav@640:         bits_in_buffer += 16;
jaroslav@640:           }
jaroslav@640:         return buffer & ((1 << n) - 1);
jaroslav@640:       }
jaroslav@640: 
jaroslav@640:       /* Drops the next n bits from the input.  You should have called peekBits
jaroslav@640:        * with a bigger or equal n before, to make sure that enough bits are in
jaroslav@640:        * the bit buffer.
jaroslav@640:        */
jaroslav@640:       public final void dropBits(int n)
jaroslav@640:       {
jaroslav@640:         buffer >>>= n;
jaroslav@640:         bits_in_buffer -= n;
jaroslav@640:       }
jaroslav@640: 
jaroslav@640:       /**
jaroslav@640:        * Gets the next n bits and increases input pointer.  This is equivalent
jaroslav@640:        * to peekBits followed by dropBits, except for correct error handling.
jaroslav@640:        * @return the value of the bits, or -1 if not enough bits available. 
jaroslav@640:        */
jaroslav@640:       public final int getBits(int n)
jaroslav@640:       {
jaroslav@640:         int bits = peekBits(n);
jaroslav@640:         if (bits >= 0)
jaroslav@640:           dropBits(n);
jaroslav@640:         return bits;
jaroslav@640:       }
jaroslav@640:       /**
jaroslav@640:        * Gets the number of bits available in the bit buffer.  This must be
jaroslav@640:        * only called when a previous peekBits() returned -1.
jaroslav@640:        * @return the number of bits available.
jaroslav@640:        */
jaroslav@640:       public final int getAvailableBits()
jaroslav@640:       {
jaroslav@640:         return bits_in_buffer;
jaroslav@640:       }
jaroslav@640: 
jaroslav@640:       /**
jaroslav@640:        * Gets the number of bytes available.  
jaroslav@640:        * @return the number of bytes available.
jaroslav@640:        */
jaroslav@640:       public final int getAvailableBytes()
jaroslav@640:       {
jaroslav@640:         return window_end - window_start + (bits_in_buffer >> 3);
jaroslav@640:       }
jaroslav@640: 
jaroslav@640:       /**
jaroslav@640:        * Skips to the next byte boundary.
jaroslav@640:        */
jaroslav@640:       public void skipToByteBoundary()
jaroslav@640:       {
jaroslav@640:         buffer >>= (bits_in_buffer & 7);
jaroslav@640:         bits_in_buffer &= ~7;
jaroslav@640:       }
jaroslav@640: 
jaroslav@640:       public final boolean needsInput() {
jaroslav@640:         return window_start == window_end;
jaroslav@640:       }
jaroslav@640: 
jaroslav@640: 
jaroslav@640:       /* Copies length bytes from input buffer to output buffer starting
jaroslav@640:        * at output[offset].  You have to make sure, that the buffer is
jaroslav@640:        * byte aligned.  If not enough bytes are available, copies fewer
jaroslav@640:        * bytes.
jaroslav@640:        * @param length the length to copy, 0 is allowed.
jaroslav@640:        * @return the number of bytes copied, 0 if no byte is available.  
jaroslav@640:        */
jaroslav@640:       public int copyBytes(byte[] output, int offset, int length)
jaroslav@640:       {
jaroslav@640:         if (length < 0)
jaroslav@640:           throw new IllegalArgumentException("length negative");
jaroslav@640:         if ((bits_in_buffer & 7) != 0)  
jaroslav@640:           /* bits_in_buffer may only be 0 or 8 */
jaroslav@640:           throw new IllegalStateException("Bit buffer is not aligned!");
jaroslav@640: 
jaroslav@640:         int count = 0;
jaroslav@640:         while (bits_in_buffer > 0 && length > 0)
jaroslav@640:           {
jaroslav@640:         output[offset++] = (byte) buffer;
jaroslav@640:         buffer >>>= 8;
jaroslav@640:         bits_in_buffer -= 8;
jaroslav@640:         length--;
jaroslav@640:         count++;
jaroslav@640:           }
jaroslav@640:         if (length == 0)
jaroslav@640:           return count;
jaroslav@640: 
jaroslav@640:         int avail = window_end - window_start;
jaroslav@640:         if (length > avail)
jaroslav@640:           length = avail;
jaroslav@640:         System.arraycopy(window, window_start, output, offset, length);
jaroslav@640:         window_start += length;
jaroslav@640: 
jaroslav@640:         if (((window_start - window_end) & 1) != 0)
jaroslav@640:           {
jaroslav@640:         /* We always want an even number of bytes in input, see peekBits */
jaroslav@640:         buffer = (window[window_start++] & 0xff);
jaroslav@640:         bits_in_buffer = 8;
jaroslav@640:           }
jaroslav@640:         return count + length;
jaroslav@640:       }
jaroslav@640: 
jaroslav@640:       public StreamManipulator()
jaroslav@640:       {
jaroslav@640:       }
jaroslav@640: 
jaroslav@640:       public void reset()
jaroslav@640:       {
jaroslav@640:         window_start = window_end = buffer = bits_in_buffer = 0;
jaroslav@640:       }
jaroslav@640: 
jaroslav@640:       public void setInput(byte[] buf, int off, int len)
jaroslav@640:       {
jaroslav@640:         if (window_start < window_end)
jaroslav@640:           throw new IllegalStateException
jaroslav@640:         ("Old input was not completely processed");
jaroslav@640: 
jaroslav@640:         int end = off + len;
jaroslav@640: 
jaroslav@640:         /* We want to throw an ArrayIndexOutOfBoundsException early.  The
jaroslav@640:          * check is very tricky: it also handles integer wrap around.  
jaroslav@640:          */
jaroslav@640:         if (0 > off || off > end || end > buf.length)
jaroslav@640:           throw new ArrayIndexOutOfBoundsException();
jaroslav@640: 
jaroslav@640:         if ((len & 1) != 0)
jaroslav@640:           {
jaroslav@640:         /* We always want an even number of bytes in input, see peekBits */
jaroslav@640:         buffer |= (buf[off++] & 0xff) << bits_in_buffer;
jaroslav@640:         bits_in_buffer += 8;
jaroslav@640:           }
jaroslav@640: 
jaroslav@640:         window = buf;
jaroslav@640:         window_start = off;
jaroslav@640:         window_end = end;
jaroslav@640:       }
jaroslav@609:     }
jaroslav@640:     /*
jaroslav@640:      * Contains the output from the Inflation process.
jaroslav@640:      *
jaroslav@640:      * We need to have a window so that we can refer backwards into the output stream
jaroslav@640:      * to repeat stuff.
jaroslav@640:      *
jaroslav@640:      * @author John Leuner
jaroslav@640:      * @since JDK 1.1
jaroslav@640:      */
jaroslav@609: 
jaroslav@640:     private static class OutputWindow
jaroslav@640:     {
jaroslav@640:       private final int WINDOW_SIZE = 1 << 15;
jaroslav@640:       private final int WINDOW_MASK = WINDOW_SIZE - 1;
jaroslav@640: 
jaroslav@640:       private byte[] window = new byte[WINDOW_SIZE]; //The window is 2^15 bytes
jaroslav@640:       private int window_end  = 0;
jaroslav@640:       private int window_filled = 0;
jaroslav@640: 
jaroslav@640:       public void write(int abyte)
jaroslav@640:       {
jaroslav@640:         if (window_filled++ == WINDOW_SIZE)
jaroslav@640:           throw new IllegalStateException("Window full");
jaroslav@640:         window[window_end++] = (byte) abyte;
jaroslav@640:         window_end &= WINDOW_MASK;
jaroslav@640:       }
jaroslav@640: 
jaroslav@640: 
jaroslav@640:       private final void slowRepeat(int rep_start, int len, int dist)
jaroslav@640:       {
jaroslav@640:         while (len-- > 0)
jaroslav@640:           {
jaroslav@640:         window[window_end++] = window[rep_start++];
jaroslav@640:         window_end &= WINDOW_MASK;
jaroslav@640:         rep_start &= WINDOW_MASK;
jaroslav@640:           }
jaroslav@640:       }
jaroslav@640: 
jaroslav@640:       public void repeat(int len, int dist)
jaroslav@640:       {
jaroslav@640:         if ((window_filled += len) > WINDOW_SIZE)
jaroslav@640:           throw new IllegalStateException("Window full");
jaroslav@640: 
jaroslav@640:         int rep_start = (window_end - dist) & WINDOW_MASK;
jaroslav@640:         int border = WINDOW_SIZE - len;
jaroslav@640:         if (rep_start <= border && window_end < border)
jaroslav@640:           {
jaroslav@640:         if (len <= dist)
jaroslav@640:           {
jaroslav@640:             System.arraycopy(window, rep_start, window, window_end, len);
jaroslav@640:             window_end += len;
jaroslav@640:           }
jaroslav@640:         else
jaroslav@640:           {
jaroslav@640:             /* We have to copy manually, since the repeat pattern overlaps.
jaroslav@640:              */
jaroslav@640:             while (len-- > 0)
jaroslav@640:               window[window_end++] = window[rep_start++];
jaroslav@640:           }
jaroslav@640:           }
jaroslav@640:         else
jaroslav@640:           slowRepeat(rep_start, len, dist);
jaroslav@640:       }
jaroslav@640: 
jaroslav@640:       public int copyStored(StreamManipulator input, int len)
jaroslav@640:       {
jaroslav@640:         len = Math.min(Math.min(len, WINDOW_SIZE - window_filled), 
jaroslav@640:                input.getAvailableBytes());
jaroslav@640:         int copied;
jaroslav@640: 
jaroslav@640:         int tailLen = WINDOW_SIZE - window_end;
jaroslav@640:         if (len > tailLen)
jaroslav@640:           {
jaroslav@640:         copied = input.copyBytes(window, window_end, tailLen);
jaroslav@640:         if (copied == tailLen)
jaroslav@640:           copied += input.copyBytes(window, 0, len - tailLen);
jaroslav@640:           }
jaroslav@640:         else
jaroslav@640:           copied = input.copyBytes(window, window_end, len);
jaroslav@640: 
jaroslav@640:         window_end = (window_end + copied) & WINDOW_MASK;
jaroslav@640:         window_filled += copied;
jaroslav@640:         return copied;
jaroslav@640:       }
jaroslav@640: 
jaroslav@640:       public void copyDict(byte[] dict, int offset, int len)
jaroslav@640:       {
jaroslav@640:         if (window_filled > 0)
jaroslav@640:           throw new IllegalStateException();
jaroslav@640: 
jaroslav@640:         if (len > WINDOW_SIZE)
jaroslav@640:           {
jaroslav@640:         offset += len - WINDOW_SIZE;
jaroslav@640:         len = WINDOW_SIZE;
jaroslav@640:           }
jaroslav@640:         System.arraycopy(dict, offset, window, 0, len);
jaroslav@640:         window_end = len & WINDOW_MASK;
jaroslav@640:       }
jaroslav@640: 
jaroslav@640:       public int getFreeSpace()
jaroslav@640:       {
jaroslav@640:         return WINDOW_SIZE - window_filled;
jaroslav@640:       }
jaroslav@640: 
jaroslav@640:       public int getAvailable()
jaroslav@640:       {
jaroslav@640:         return window_filled;
jaroslav@640:       }
jaroslav@640: 
jaroslav@640:       public int copyOutput(byte[] output, int offset, int len)
jaroslav@640:       {
jaroslav@640:         int copy_end = window_end;
jaroslav@640:         if (len > window_filled)
jaroslav@640:           len = window_filled;
jaroslav@640:         else
jaroslav@640:           copy_end = (window_end - window_filled + len) & WINDOW_MASK;
jaroslav@640: 
jaroslav@640:         int copied = len;
jaroslav@640:         int tailLen = len - copy_end;
jaroslav@640: 
jaroslav@640:         if (tailLen > 0)
jaroslav@640:           {
jaroslav@640:         System.arraycopy(window, WINDOW_SIZE - tailLen,
jaroslav@640:                  output, offset, tailLen);
jaroslav@640:         offset += tailLen;
jaroslav@640:         len = copy_end;
jaroslav@640:           }
jaroslav@640:         System.arraycopy(window, copy_end - len, output, offset, len);
jaroslav@640:         window_filled -= copied;
jaroslav@640:         if (window_filled < 0)
jaroslav@640:           throw new IllegalStateException();
jaroslav@640:         return copied;
jaroslav@640:       }
jaroslav@640: 
jaroslav@640:       public void reset() {
jaroslav@640:         window_filled = window_end = 0;
jaroslav@640:       }
jaroslav@609:     }
jaroslav@640:   
jaroslav@609: }