Fix NET_2_0 build

[mono-project.git] / mono / benchmark / zipmark.cs

// zipmark.cs
// (This file is the NZipLib sources with a crude benchmark class attached -
//  2002-15-05 Dan Lewis <dihlewis@yahoo.co.uk>)
// -------------------------------------------------------------------------
//
// NZipLib source:
// Copyright (C) 2001 Mike Krueger
//
// This file was translated from java, it was part of the GNU Classpath
// Copyright (C) 2001 Free Software Foundation, Inc.
//
// This program is free software; you can redistribute it and/or
// modify it under the terms of the GNU General Public License
// as published by the Free Software Foundation; either version 2
// of the License, or (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this program; if not, write to the Free Software
// Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
//
// As a special exception, if you link this library with other files to
// produce an executable, this library does not by itself cause the
// resulting executable to be covered by the GNU General Public License.
// This exception does not however invalidate any other reasons why the
// executable file might be covered by the GNU General Public License.

using System;
using System.IO;
using NZlib.Streams;
using NZlib.Checksums;
using NZlib.Compression;

class ZipMark {
        static int Iterations = 1000;
        static int BlockSize = 1024;

        public static void Main (string [] args)
        {
                if (args.Length == 0 || args.Length > 3) {
                        Console.WriteLine ("Usage: zipmark FILE [ITERATIONS] [BLOCKSIZE]");
                        return;
                }
        
                string filename = args [0];
                FileInfo file = new FileInfo (filename);
                if (!file.Exists) {
                        Console.WriteLine ("Couldn't find file {0}", filename);
                        return;
                }

                FileStream fs = file.OpenRead ();

                byte [] raw = new byte [file.Length];
                int count = fs.Read (raw, 0, (int)file.Length);
                fs.Close ();

                if (count != file.Length) {
                        Console.WriteLine ("Couldn't read file {0}", filename);
                        return;
                }

                Deflater def = new Deflater (Deflater.BEST_COMPRESSION, false);
                Inflater inf = new Inflater (false);

                // 1. Count deflated size

                int cooked_size = Deflate (def, raw, null);
                byte [] cooked = new byte [cooked_size];

                // 2. Deflate & Inflate

                if (args.Length > 1)
                        Iterations = Int32.Parse (args [1]);
                if (args.Length > 2)
                        BlockSize = Int32.Parse (args [2]);

                for (int i = 0; i < Iterations; ++ i) {
                        Deflate (def, raw, cooked);
                        Inflate (inf, cooked, raw);
                }

                return;
        }

        static int Deflate (Deflater def, byte [] src, byte [] dest)
        {
                bool count;
                int offset, length, remain;
                
                if (dest == null) {
                        dest = new byte [BlockSize];
                        count = true;
                } else
                        count = false;
                
                def.Reset ();
                def.SetInput (src);

                offset = 0;
                while (!def.IsFinished) {
                        if (def.IsNeedingInput)
                                def.Finish ();

                        remain = Math.Min (dest.Length - offset, BlockSize);
                        if (remain == 0)
                                break;

                        length = def.Deflate (dest, offset, remain);
                        if (!count)
                                offset += length;
                }

                return def.TotalOut;
        }

        static int Inflate (Inflater inf, byte [] src, byte [] dest)
        {
                int offset, length, remain;
        
                inf.Reset ();
                inf.SetInput (src);

                offset = 0;
                while (!inf.IsNeedingInput) {
                        remain = Math.Min (dest.Length - offset, BlockSize);
                        if (remain == 0)
                                break;

                        length = inf.Inflate (dest, offset, remain);
                        offset += length;
                }

                return inf.TotalOut;
        }
}

// ----------------------  NZipLib sources from here on --------------------------

namespace NZlib.Compression {
        
        /// <summary>
        /// This is the Deflater class.  The deflater class compresses input
        /// with the deflate algorithm described in RFC 1951.  It has several
        /// compression levels and three different strategies described below.
        ///
        /// This class is <i>not</i> thread safe.  This is inherent in the API, due
        /// to the split of deflate and setInput.
        /// 
        /// author of the original java version : Jochen Hoenicke
        /// </summary>
        public class Deflater
        {
                /// <summary>
                /// The best and slowest compression level.  This tries to find very
                /// long and distant string repetitions.
                /// </summary>
                public static  int BEST_COMPRESSION = 9;
                
                /// <summary>
                /// The worst but fastest compression level.
                /// </summary>
                public static  int BEST_SPEED = 1;
                
                /// <summary>
                /// The default compression level.
                /// </summary>
                public static  int DEFAULT_COMPRESSION = -1;
                
                /// <summary>
                /// This level won't compress at all but output uncompressed blocks.
                /// </summary>
                public static  int NO_COMPRESSION = 0;
                
                /// <summary>
                /// The default strategy.
                /// </summary>
                public static  int DEFAULT_STRATEGY = 0;
                
                
                /// <summary>
                /// This strategy will only allow longer string repetitions.  It is
                /// useful for random data with a small character set.
                /// </summary>
                public static  int FILTERED = 1;
                
                /// <summary>
                /// This strategy will not look for string repetitions at all.  It
                /// only encodes with Huffman trees (which means, that more common
                /// characters get a smaller encoding.
                /// </summary>
                public static  int HUFFMAN_ONLY = 2;
                
                /// <summary>
                /// The compression method.  This is the only method supported so far.
                /// There is no need to use this constant at all.
                /// </summary>
                public static  int DEFLATED = 8;
                
                /*
                * The Deflater can do the following state transitions:
                        *
                        * (1) -> INIT_STATE   ----> INIT_FINISHING_STATE ---.
                        *        /  | (2)      (5)                         |
                        *       /   v          (5)                         |
                        *   (3)| SETDICT_STATE ---> SETDICT_FINISHING_STATE |(3)
                        *       \   | (3)                 |        ,-------'
                        *        |  |                     | (3)   /
                        *        v  v          (5)        v      v
                        * (1) -> BUSY_STATE   ----> FINISHING_STATE
                        *                                | (6)
                        *                                v
                        *                           FINISHED_STATE
                        *    \_____________________________________/
                        *          | (7)
                        *          v
                        *        CLOSED_STATE
                        *
                        * (1) If we should produce a header we start in INIT_STATE, otherwise
                        *     we start in BUSY_STATE.
                        * (2) A dictionary may be set only when we are in INIT_STATE, then
                        *     we change the state as indicated.
                        * (3) Whether a dictionary is set or not, on the first call of deflate
                        *     we change to BUSY_STATE.
                        * (4) -- intentionally left blank -- :)
                        * (5) FINISHING_STATE is entered, when flush() is called to indicate that
                        *     there is no more INPUT.  There are also states indicating, that
                        *     the header wasn't written yet.
                        * (6) FINISHED_STATE is entered, when everything has been flushed to the
                        *     internal pending output buffer.
                        * (7) At any time (7)
                        *
                        */
                        
                private static  int IS_SETDICT              = 0x01;
                private static  int IS_FLUSHING             = 0x04;
                private static  int IS_FINISHING            = 0x08;
                
                private static  int INIT_STATE              = 0x00;
                private static  int SETDICT_STATE           = 0x01;
//              private static  int INIT_FINISHING_STATE    = 0x08;
//              private static  int SETDICT_FINISHING_STATE = 0x09;
                private static  int BUSY_STATE              = 0x10;
                private static  int FLUSHING_STATE          = 0x14;
                private static  int FINISHING_STATE         = 0x1c;
                private static  int FINISHED_STATE          = 0x1e;
                private static  int CLOSED_STATE            = 0x7f;
                
                /// <summary>
                /// Compression level.
                /// </summary>
                private int level;
                
                /// <summary>
                /// should we include a header.
                /// </summary>
                private bool noHeader;
                
//              /// <summary>
//              /// Compression strategy.
//              /// </summary>
//              private int strategy;
                
                /// <summary>
                /// The current state.
                /// </summary>
                private int state;
                
                /// <summary>
                /// The total bytes of output written.
                /// </summary>
                private int totalOut;
                
                /// <summary>
                /// The pending output.
                /// </summary>
                private DeflaterPending pending;
                
                /// <summary>
                /// The deflater engine.
                /// </summary>
                private DeflaterEngine engine;
                
                /// <summary>
                /// Creates a new deflater with default compression level.
                /// </summary>
                public Deflater() : this(DEFAULT_COMPRESSION, false)
                {
                        
                }
                
                /// <summary>
                /// Creates a new deflater with given compression level.
                /// </summary>
                /// <param name="lvl">
                /// the compression level, a value between NO_COMPRESSION
                /// and BEST_COMPRESSION, or DEFAULT_COMPRESSION.
                /// </param>
                /// <exception cref="System.ArgumentOutOfRangeException">if lvl is out of range.</exception>
                public Deflater(int lvl) : this(lvl, false)
                {
                        
                }
                
                /// <summary>
                /// Creates a new deflater with given compression level.
                /// </summary>
                /// <param name="lvl">
                /// the compression level, a value between NO_COMPRESSION
                /// and BEST_COMPRESSION.
                /// </param>
                /// <param name="nowrap">
                /// true, if we should suppress the deflate header at the
                /// beginning and the adler checksum at the end of the output.  This is
                /// useful for the GZIP format.
                /// </param>
                /// <exception cref="System.ArgumentOutOfRangeException">if lvl is out of range.</exception>
                public Deflater(int lvl, bool nowrap)
                {
                        if (lvl == DEFAULT_COMPRESSION) {
                                lvl = 6;
                        } else if (lvl < NO_COMPRESSION || lvl > BEST_COMPRESSION) {
                                throw new ArgumentOutOfRangeException("lvl");
                        }
                        
                        pending = new DeflaterPending();
                        engine = new DeflaterEngine(pending);
                        this.noHeader = nowrap;
                        SetStrategy(DEFAULT_STRATEGY);
                        SetLevel(lvl);
                        Reset();
                }
                
                
                /// <summary>
                /// Resets the deflater.  The deflater acts afterwards as if it was
                /// just created with the same compression level and strategy as it
                /// had before.
                /// </summary>
                public void Reset()
                {
                        state = (noHeader ? BUSY_STATE : INIT_STATE);
                        totalOut = 0;
                        pending.Reset();
                        engine.Reset();
                }
                
                /// <summary>
                /// Gets the current adler checksum of the data that was processed so far.
                /// </summary>
                public int Adler {
                        get {
                                return engine.Adler;
                        }
                }
                
                /// <summary>
                /// Gets the number of input bytes processed so far.
                /// </summary>
                public int TotalIn {
                        get {
                                return engine.TotalIn;
                        }
                }
                
                /// <summary>
                /// Gets the number of output bytes so far.
                /// </summary>
                public int TotalOut {
                        get {
                                return totalOut;
                        }
                }
                
                /// <summary>
                /// Flushes the current input block.  Further calls to deflate() will
                /// produce enough output to inflate everything in the current input
                /// block.  This is not part of Sun's JDK so I have made it package
                /// private.  It is used by DeflaterOutputStream to implement
                /// flush().
                /// </summary>
                public void Flush() 
                {
                        state |= IS_FLUSHING;
                }
                
                /// <summary>
                /// Finishes the deflater with the current input block.  It is an error
                /// to give more input after this method was called.  This method must
                /// be called to force all bytes to be flushed.
                /// </summary>
                public void Finish() 
                {
                        state |= IS_FLUSHING | IS_FINISHING;
                }
                
                /// <summary>
                /// Returns true if the stream was finished and no more output bytes
                /// are available.
                /// </summary>
                public bool IsFinished {
                        get {
                                return state == FINISHED_STATE && pending.IsFlushed;
                        }
                }
                
                /// <summary>
                /// Returns true, if the input buffer is empty.
                /// You should then call setInput(). 
                /// NOTE: This method can also return true when the stream
                /// was finished.
                /// </summary>
                public bool IsNeedingInput {
                        get {
                                return engine.NeedsInput();
                        }
                }
                
                /// <summary>
                /// Sets the data which should be compressed next.  This should be only
                /// called when needsInput indicates that more input is needed.
                /// If you call setInput when needsInput() returns false, the
                /// previous input that is still pending will be thrown away.
                /// The given byte array should not be changed, before needsInput() returns
                /// true again.
                /// This call is equivalent to <code>setInput(input, 0, input.length)</code>.
                /// </summary>
                /// <param name="input">
                /// the buffer containing the input data.
                /// </param>
                /// <exception cref="System.InvalidOperationException">
                /// if the buffer was finished() or ended().
                /// </exception>
                public void SetInput(byte[] input)
                {
                        SetInput(input, 0, input.Length);
                }
                
                /// <summary>
                /// Sets the data which should be compressed next.  This should be
                /// only called when needsInput indicates that more input is needed.
                /// The given byte array should not be changed, before needsInput() returns
                /// true again.
                /// </summary>
                /// <param name="input">
                /// the buffer containing the input data.
                /// </param>
                /// <param name="off">
                /// the start of the data.
                /// </param>
                /// <param name="len">
                /// the length of the data.
                /// </param>
                /// <exception cref="System.InvalidOperationException">
                /// if the buffer was finished() or ended() or if previous input is still pending.
                /// </exception>
                public void SetInput(byte[] input, int off, int len)
                {
                        if ((state & IS_FINISHING) != 0) {
                                throw new InvalidOperationException("finish()/end() already called");
                        }
                        engine.SetInput(input, off, len);
                }
                
                /// <summary>
                /// Sets the compression level.  There is no guarantee of the exact
                /// position of the change, but if you call this when needsInput is
                /// true the change of compression level will occur somewhere near
                /// before the end of the so far given input.
                /// </summary>
                /// <param name="lvl">
                /// the new compression level.
                /// </param>
                public void SetLevel(int lvl)
                {
                        if (lvl == DEFAULT_COMPRESSION) {
                                lvl = 6;
                        } else if (lvl < NO_COMPRESSION || lvl > BEST_COMPRESSION) {
                                throw new ArgumentOutOfRangeException("lvl");
                        }
                        
                        
                        if (level != lvl) {
                                level = lvl;
                                engine.SetLevel(lvl);
                        }
                }
                
                /// <summary>
                /// Sets the compression strategy. Strategy is one of
                /// DEFAULT_STRATEGY, HUFFMAN_ONLY and FILTERED.  For the exact
                /// position where the strategy is changed, the same as for
                /// setLevel() applies.
                /// </summary>
                /// <param name="stgy">
                /// the new compression strategy.
                /// </param>
                public void SetStrategy(int stgy)
                {
                        if (stgy != DEFAULT_STRATEGY && stgy != FILTERED && stgy != HUFFMAN_ONLY) {
                            throw new Exception();
                        }
                        engine.Strategy = stgy;
                }
                
                /// <summary>
                /// Deflates the current input block to the given array.  It returns
                /// the number of bytes compressed, or 0 if either
                /// needsInput() or finished() returns true or length is zero.
                /// </summary>
                /// <param name="output">
                /// the buffer where to write the compressed data.
                /// </param>
                public int Deflate(byte[] output)
                {
                        return Deflate(output, 0, output.Length);
                }
                
                /// <summary>
                /// Deflates the current input block to the given array.  It returns
                /// the number of bytes compressed, or 0 if either
                /// needsInput() or finished() returns true or length is zero.
                /// </summary>
                /// <param name="output">
                /// the buffer where to write the compressed data.
                /// </param>
                /// <param name="offset">
                /// the offset into the output array.
                /// </param>
                /// <param name="length">
                /// the maximum number of bytes that may be written.
                /// </param>
                /// <exception cref="System.InvalidOperationException">
                /// if end() was called.
                /// </exception>
                /// <exception cref="System.ArgumentOutOfRangeException">
                /// if offset and/or length don't match the array length.
                /// </exception>
                public int Deflate(byte[] output, int offset, int length)
                {
                        int origLength = length;
                        
                        if (state == CLOSED_STATE) {
                                throw new InvalidOperationException("Deflater closed");
                        }
                        
                        if (state < BUSY_STATE) {
                                /* output header */
                                int header = (DEFLATED +
                                              ((DeflaterConstants.MAX_WBITS - 8) << 4)) << 8;
                                int level_flags = (level - 1) >> 1;
                                if (level_flags < 0 || level_flags > 3) {
                                        level_flags = 3;
                                }
                                header |= level_flags << 6;
                                if ((state & IS_SETDICT) != 0) {
                                        /* Dictionary was set */
                                        header |= DeflaterConstants.PRESET_DICT;
                                }
                                header += 31 - (header % 31);
                                
                                
                                pending.WriteShortMSB(header);
                                if ((state & IS_SETDICT) != 0) {
                                        int chksum = engine.Adler;
                                        engine.ResetAdler();
                                        pending.WriteShortMSB(chksum >> 16);
                                        pending.WriteShortMSB(chksum & 0xffff);
                                }
                                
                                state = BUSY_STATE | (state & (IS_FLUSHING | IS_FINISHING));
                        }
                        
                        for (;;) {
                                int count = pending.Flush(output, offset, length);
                                offset   += count;
                                totalOut += count;
                                length   -= count;
                                
                                if (length == 0 || state == FINISHED_STATE) {
                                        break;
                                }
                                
                                if (!engine.Deflate((state & IS_FLUSHING) != 0, (state & IS_FINISHING) != 0)) {
                                        if (state == BUSY_STATE) {
                                                /* We need more input now */
                                                return origLength - length;
                                        } else if (state == FLUSHING_STATE) {
                                                if (level != NO_COMPRESSION) {
                                                        /* We have to supply some lookahead.  8 bit lookahead
                                                         * are needed by the zlib inflater, and we must fill
                                                         * the next byte, so that all bits are flushed.
                                                         */
                                                        int neededbits = 8 + ((-pending.BitCount) & 7);
                                                        while (neededbits > 0) {
                                                                /* write a static tree block consisting solely of
                                                                 * an EOF:
                                                                 */
                                                                pending.WriteBits(2, 10);
                                                                neededbits -= 10;
                                                        }
                                                }
                                                state = BUSY_STATE;
                                        } else if (state == FINISHING_STATE) {
                                                pending.AlignToByte();
                                                /* We have completed the stream */
                                                if (!noHeader) {
                                                        int adler = engine.Adler;
                                                        pending.WriteShortMSB(adler >> 16);
                                                        pending.WriteShortMSB(adler & 0xffff);
                                                }
                                                state = FINISHED_STATE;
                                        }
                                }
                        }
                        return origLength - length;
                }
                
                /// <summary>
                /// Sets the dictionary which should be used in the deflate process.
                /// This call is equivalent to <code>setDictionary(dict, 0, dict.Length)</code>.
                /// </summary>
                /// <param name="dict">
                /// the dictionary.
                /// </param>
                /// <exception cref="System.InvalidOperationException">
                /// if setInput () or deflate () were already called or another dictionary was already set.
                /// </exception>
                public void SetDictionary(byte[] dict)
                {
                        SetDictionary(dict, 0, dict.Length);
                }
                
                /// <summary>
                /// Sets the dictionary which should be used in the deflate process.
                /// The dictionary should be a byte array containing strings that are
                /// likely to occur in the data which should be compressed.  The
                /// dictionary is not stored in the compressed output, only a
                /// checksum.  To decompress the output you need to supply the same
                /// dictionary again.
                /// </summary>
                /// <param name="dict">
                /// the dictionary.
                /// </param>
                /// <param name="offset">
                /// an offset into the dictionary.
                /// </param>
                /// <param name="length">
                /// the length of the dictionary.
                /// </param>
                /// <exception cref="System.InvalidOperationException">
                /// if setInput () or deflate () were already called or another dictionary was already set.
                /// </exception>
                public void SetDictionary(byte[] dict, int offset, int length)
                {
                        if (state != INIT_STATE) {
                                throw new InvalidOperationException();
                        }
                        
                        state = SETDICT_STATE;
                        engine.SetDictionary(dict, offset, length);
                }
        }
}

namespace NZlib.Compression {
        
        /// <summary>
        /// This class contains constants used for the deflater.
        /// </summary>
        public class DeflaterConstants 
        {
                public const bool DEBUGGING = false;
                
                public const int STORED_BLOCK = 0;
                public const int STATIC_TREES = 1;
                public const int DYN_TREES    = 2;
                public const int PRESET_DICT  = 0x20;
                
                public const int DEFAULT_MEM_LEVEL = 8;
                
                public const int MAX_MATCH = 258;
                public const int MIN_MATCH = 3;
                
                public const int MAX_WBITS = 15;
                public const int WSIZE = 1 << MAX_WBITS;
                public const int WMASK = WSIZE - 1;
                
                public const int HASH_BITS = DEFAULT_MEM_LEVEL + 7;
                public const int HASH_SIZE = 1 << HASH_BITS;
                public const int HASH_MASK = HASH_SIZE - 1;
                public const int HASH_SHIFT = (HASH_BITS + MIN_MATCH - 1) / MIN_MATCH;
                
                public const int MIN_LOOKAHEAD = MAX_MATCH + MIN_MATCH + 1;
                public const int MAX_DIST = WSIZE - MIN_LOOKAHEAD;
                
                public const int PENDING_BUF_SIZE = 1 << (DEFAULT_MEM_LEVEL + 8);
                public static int MAX_BLOCK_SIZE = Math.Min(65535, PENDING_BUF_SIZE-5);
                
                public const int DEFLATE_STORED = 0;
                public const int DEFLATE_FAST   = 1;
                public const int DEFLATE_SLOW   = 2;
                
                public static int[] GOOD_LENGTH = { 0, 4, 4, 4, 4, 8,  8,  8,  32,  32 };
                public static int[] MAX_LAZY    = { 0, 4, 5, 6, 4,16, 16, 32, 128, 258 };
                public static int[] NICE_LENGTH = { 0, 8,16,32,16,32,128,128, 258, 258 };
                public static int[] MAX_CHAIN   = { 0, 4, 8,32,16,32,128,256,1024,4096 };
                public static int[] COMPR_FUNC  = { 0, 1, 1, 1, 1, 2,  2,  2,   2,   2 };
        }
}

namespace NZlib.Compression {
        
        public class DeflaterEngine : DeflaterConstants 
        {
                private  static int TOO_FAR = 4096;
                
                private int ins_h;
//              private byte[] buffer;
                private short[] head;
                private short[] prev;
                
                private int matchStart, matchLen;
                private bool prevAvailable;
                private int blockStart;
                private int strstart, lookahead;
                private byte[] window;
                
                private int strategy, max_chain, max_lazy, niceLength, goodLength;
                
                /// <summary>
                /// The current compression function.
                /// </summary>
                private int comprFunc;
                
                /// <summary>
                /// The input data for compression.
                /// </summary>
                private byte[] inputBuf;
                
                /// <summary>
                /// The total bytes of input read.
                /// </summary>
                private int totalIn;
                
                /// <summary>
                /// The offset into inputBuf, where input data starts.
                /// </summary>
                private int inputOff;
                
                /// <summary>
                /// The end offset of the input data.
                /// </summary>
                private int inputEnd;
                
                private DeflaterPending pending;
                private DeflaterHuffman huffman;
                
                /// <summary>
                /// The adler checksum
                /// </summary>
                private Adler32 adler;
                
                public DeflaterEngine(DeflaterPending pending) 
                {
                        this.pending = pending;
                        huffman = new DeflaterHuffman(pending);
                        adler = new Adler32();
                        
                        window = new byte[2*WSIZE];
                        head   = new short[HASH_SIZE];
                        prev   = new short[WSIZE];
                        
                        /* We start at index 1, to avoid a implementation deficiency, that
                        * we cannot build a repeat pattern at index 0.
                        */
                        blockStart = strstart = 1;
                }
                
                public void Reset()
                {
                        huffman.Reset();
                        adler.Reset();
                        blockStart = strstart = 1;
                        lookahead = 0;
                        totalIn   = 0;
                        prevAvailable = false;
                        matchLen = MIN_MATCH - 1;
                        
                        for (int i = 0; i < HASH_SIZE; i++) {
                                head[i] = 0;
                        }
                        
                        for (int i = 0; i < WSIZE; i++) {
                                prev[i] = 0;
                        }
                }
                
                public void ResetAdler()
                {
                        adler.Reset();
                }
                
                public int Adler {
                        get {
                                return (int)adler.Value;
                        }
                }
                
                public int TotalIn {
                        get {
                                return totalIn;
                        }
                }
                
                public int Strategy {
                        get {
                                return strategy;
                        }
                        set {
                                strategy = value;
                        }
                }
                
                public void SetLevel(int lvl)
                {
                        goodLength = DeflaterConstants.GOOD_LENGTH[lvl];
                        max_lazy   = DeflaterConstants.MAX_LAZY[lvl];
                        niceLength = DeflaterConstants.NICE_LENGTH[lvl];
                        max_chain  = DeflaterConstants.MAX_CHAIN[lvl];
                        
                        if (DeflaterConstants.COMPR_FUNC[lvl] != comprFunc) {
//                              if (DeflaterConstants.DEBUGGING) {
//                                      Console.WriteLine("Change from "+comprFunc +" to "
//                                                        + DeflaterConstants.COMPR_FUNC[lvl]);
//                              }
                                switch (comprFunc) {
                                        case DEFLATE_STORED:
                                                if (strstart > blockStart) {
                                                        huffman.FlushStoredBlock(window, blockStart,
                                                                                 strstart - blockStart, false);
                                                        blockStart = strstart;
                                                }
                                                UpdateHash();
                                                break;
                                        case DEFLATE_FAST:
                                                if (strstart > blockStart) {
                                                        huffman.FlushBlock(window, blockStart, strstart - blockStart,
                                                                           false);
                                                        blockStart = strstart;
                                                }
                                                break;
                                        case DEFLATE_SLOW:
                                                if (prevAvailable) {
                                                        huffman.TallyLit(window[strstart-1] & 0xff);
                                                }
                                                if (strstart > blockStart) {
                                                        huffman.FlushBlock(window, blockStart, strstart - blockStart,
                                                                           false);
                                                        blockStart = strstart;
                                                }
                                                prevAvailable = false;
                                                matchLen = MIN_MATCH - 1;
                                                break;
                                }
                                comprFunc = COMPR_FUNC[lvl];
                        }
                }
                
                private void UpdateHash() 
                {
//                      if (DEBUGGING) {
//                              Console.WriteLine("updateHash: "+strstart);
//                      }
                        ins_h = (window[strstart] << HASH_SHIFT) ^ window[strstart + 1];
                }
                
                private int InsertString() 
                {
                        short match;
                        int hash = ((ins_h << HASH_SHIFT) ^ window[strstart + (MIN_MATCH -1)]) & HASH_MASK;
                        
//                      if (DEBUGGING) {
//                              if (hash != (((window[strstart] << (2*HASH_SHIFT)) ^ 
//                                            (window[strstart + 1] << HASH_SHIFT) ^ 
//                                            (window[strstart + 2])) & HASH_MASK)) {
//                                              throw new Exception("hash inconsistent: "+hash+"/"
//                                                                  +window[strstart]+","
//                                                                  +window[strstart+1]+","
//                                                                  +window[strstart+2]+","+HASH_SHIFT);
//                                      }
//                      }
                        
                        prev[strstart & WMASK] = match = head[hash];
                        head[hash] = (short)strstart;
                        ins_h = hash;
                        return match & 0xffff;
                }
                
                public void FillWindow()
                {
                        while (lookahead < DeflaterConstants.MIN_LOOKAHEAD && inputOff < inputEnd) {
                                int more = 2*WSIZE - lookahead - strstart;
                                
                                /* If the window is almost full and there is insufficient lookahead,
                                * move the upper half to the lower one to make room in the upper half.
                                */
                                if (strstart >= WSIZE + MAX_DIST) {
                                        System.Array.Copy(window, WSIZE, window, 0, WSIZE);
                                        matchStart -= WSIZE;
                                        strstart -= WSIZE;
                                        blockStart -= WSIZE;
                                        
                                        /* Slide the hash table (could be avoided with 32 bit values
                                         * at the expense of memory usage).
                                         */
                                         for (int i = 0; i < HASH_SIZE; i++) {
                                                int m = head[i];
                                                head[i] = m >= WSIZE ? (short) (m - WSIZE) : (short)0;
                                         }
                                         more += WSIZE;
                                }
                                
                                if (more > inputEnd - inputOff) {
                                        more = inputEnd - inputOff;
                                }
                                
                                System.Array.Copy(inputBuf, inputOff, window, strstart + lookahead, more);
                                adler.Update(inputBuf, inputOff, more);
                                inputOff  += more;
                                totalIn   += more;
                                lookahead += more;
                                
                                if (lookahead >= MIN_MATCH) {
                                        UpdateHash();
                                }
                        }
                }
                
                private bool FindLongestMatch(int curMatch) 
                {
                        int chainLength = this.max_chain;
                        int niceLength  = this.niceLength;
                        short[] prev    = this.prev;
                        int scan        = this.strstart;
                        int match;
                        int best_end = this.strstart + matchLen;
                        int best_len = Math.Max(matchLen, MIN_MATCH - 1);
                        
                        int limit = Math.Max(strstart - MAX_DIST, 0);
                        
                        int strend = strstart + MAX_MATCH - 1;
                        byte scan_end1 = window[best_end - 1];
                        byte scan_end  = window[best_end];
                        
                        /* Do not waste too much time if we already have a good match: */
                        if (best_len >= this.goodLength) {
                                chainLength >>= 2;
                        }
                        
                        /* Do not look for matches beyond the end of the input. This is necessary
                        * to make deflate deterministic.
                        */
                        if (niceLength > lookahead) {
                                niceLength = lookahead;
                        }
                        
                        if (DeflaterConstants.DEBUGGING && strstart > 2*WSIZE - MIN_LOOKAHEAD) {
                            throw new InvalidOperationException("need lookahead");
                        }
                        
                        do {
                                if (DeflaterConstants.DEBUGGING && curMatch >= strstart) {
                                        throw new InvalidOperationException("future match");
                                }
                                if (window[curMatch + best_len] != scan_end      || 
                                    window[curMatch + best_len - 1] != scan_end1 || 
                                    window[curMatch] != window[scan]             || 
                                    window[curMatch+1] != window[scan + 1]) {
                                    continue;
                                }
                                
                                match = curMatch + 2;
                                scan += 2;
                                
                                /* We check for insufficient lookahead only every 8th comparison;
                                * the 256th check will be made at strstart+258.
                                */
                                while (window[++scan] == window[++match] && 
                                       window[++scan] == window[++match] && 
                                       window[++scan] == window[++match] && 
                                       window[++scan] == window[++match] && 
                                       window[++scan] == window[++match] && 
                                       window[++scan] == window[++match] && 
                                       window[++scan] == window[++match] && 
                                       window[++scan] == window[++match] && scan < strend) ;
                                
                                if (scan > best_end) {
                                        //      if (DeflaterConstants.DEBUGGING && ins_h == 0)
                                        //        System.err.println("Found match: "+curMatch+"-"+(scan-strstart));
                                        matchStart = curMatch;
                                        best_end = scan;
                                        best_len = scan - strstart;
                                        if (best_len >= niceLength) {
                                                break;
                                        }
                                        
                                        scan_end1  = window[best_end-1];
                                        scan_end   = window[best_end];
                                }
                                scan = strstart;
                        } while ((curMatch = (prev[curMatch & WMASK] & 0xffff)) > limit && --chainLength != 0);
                        
                        matchLen = Math.Min(best_len, lookahead);
                        return matchLen >= MIN_MATCH;
                }
                
                public void SetDictionary(byte[] buffer, int offset, int length) 
                {
                        if (DeflaterConstants.DEBUGGING && strstart != 1) {
                                throw new InvalidOperationException("strstart not 1");
                        }
                        adler.Update(buffer, offset, length);
                        if (length < MIN_MATCH) {
                                return;
                        }
                        if (length > MAX_DIST) {
                                offset += length - MAX_DIST;
                                length = MAX_DIST;
                        }
                        
                        System.Array.Copy(buffer, offset, window, strstart, length);
                        
                        UpdateHash();
                        --length;
                        while (--length > 0) {
                                InsertString();
                                strstart++;
                        }
                        strstart += 2;
                        blockStart = strstart;
                }
                
                private bool DeflateStored(bool flush, bool finish)
                {
                        if (!flush && lookahead == 0) {
                                return false;
                        }
                        
                        strstart += lookahead;
                        lookahead = 0;
                        
                        int storedLen = strstart - blockStart;
                        
                        if ((storedLen >= DeflaterConstants.MAX_BLOCK_SIZE) || /* Block is full */
                                (blockStart < WSIZE && storedLen >= MAX_DIST) ||   /* Block may move out of window */
                                flush) {
                                bool lastBlock = finish;
                                if (storedLen > DeflaterConstants.MAX_BLOCK_SIZE) {
                                        storedLen = DeflaterConstants.MAX_BLOCK_SIZE;
                                        lastBlock = false;
                                }
                                
//                              if (DeflaterConstants.DEBUGGING) {
//                                      Console.WriteLine("storedBlock["+storedLen+","+lastBlock+"]");
//                              }
                                        
                                huffman.FlushStoredBlock(window, blockStart, storedLen, lastBlock);
                                blockStart += storedLen;
                                return !lastBlock;
                        }
                        return true;
                }
                
                private bool DeflateFast(bool flush, bool finish)
                {
                        if (lookahead < MIN_LOOKAHEAD && !flush) {
                                return false;
                        }
                        
                        while (lookahead >= MIN_LOOKAHEAD || flush) {
                                if (lookahead == 0) {
                                        /* We are flushing everything */
                                        huffman.FlushBlock(window, blockStart, strstart - blockStart, finish);
                                        blockStart = strstart;
                                        return false;
                                }
                                
                                int hashHead;
                                if (lookahead >= MIN_MATCH && 
                                    (hashHead = InsertString()) != 0 && 
                                    strategy != Deflater.HUFFMAN_ONLY && 
                                    strstart - hashHead <= MAX_DIST && 
                                    FindLongestMatch(hashHead)) {
                                        /* longestMatch sets matchStart and matchLen */
//                                      if (DeflaterConstants.DEBUGGING) {
//                                              for (int i = 0 ; i < matchLen; i++) {
//                                                      if (window[strstart+i] != window[matchStart + i]) {
//                                                              throw new Exception();
//                                                      }
//                                              }
//                                      }
                                        
                                        huffman.TallyDist(strstart - matchStart, matchLen);
                                        
                                        lookahead -= matchLen;
                                        if (matchLen <= max_lazy && lookahead >= MIN_MATCH) {
                                                while (--matchLen > 0) {
                                                        ++strstart;
                                                        InsertString();
                                                }
                                                ++strstart;
                                        } else {
                                                strstart += matchLen;
                                                if (lookahead >= MIN_MATCH - 1) {
                                                        UpdateHash();
                                                }
                                        }
                                        matchLen = MIN_MATCH - 1;
                                        continue;
                                } else {
                                        /* No match found */
                                        huffman.TallyLit(window[strstart] & 0xff);
                                        ++strstart;
                                        --lookahead;
                                }
                                
                                if (huffman.IsFull()) {
                                        bool lastBlock = finish && lookahead == 0;
                                        huffman.FlushBlock(window, blockStart, strstart - blockStart,
                                                           lastBlock);
                                        blockStart = strstart;
                                        return !lastBlock;
                                }
                        }
                        return true;
                }
                
                private bool DeflateSlow(bool flush, bool finish)
                {
                        if (lookahead < MIN_LOOKAHEAD && !flush) {
                                return false;
                        }
                        
                        while (lookahead >= MIN_LOOKAHEAD || flush) {
                                if (lookahead == 0) {
                                        if (prevAvailable) {
                                                huffman.TallyLit(window[strstart-1] & 0xff);
                                        }
                                        prevAvailable = false;
                                        
                                        /* We are flushing everything */
                                        if (DeflaterConstants.DEBUGGING && !flush) {
                                                throw new Exception("Not flushing, but no lookahead");
                                        }
                                        huffman.FlushBlock(window, blockStart, strstart - blockStart,
                                                           finish);
                                        blockStart = strstart;
                                        return false;
                                }
                                
                                int prevMatch = matchStart;
                                int prevLen = matchLen;
                                if (lookahead >= MIN_MATCH) {
                                        int hashHead = InsertString();
                                        if (strategy != Deflater.HUFFMAN_ONLY && hashHead != 0 && strstart - hashHead <= MAX_DIST && FindLongestMatch(hashHead))
                                                {
                                                        /* longestMatch sets matchStart and matchLen */
                                                        
                                                        /* Discard match if too small and too far away */
                                                        if (matchLen <= 5 && (strategy == Deflater.FILTERED || (matchLen == MIN_MATCH && strstart - matchStart > TOO_FAR))) {
                                                                matchLen = MIN_MATCH - 1;
                                                        }
                                                }
                                }
                                
                                /* previous match was better */
                                if (prevLen >= MIN_MATCH && matchLen <= prevLen) {
//                                      if (DeflaterConstants.DEBUGGING) {
//                                              for (int i = 0 ; i < matchLen; i++) {
//                                                      if (window[strstart-1+i] != window[prevMatch + i])
//                                                              throw new Exception();
//                                              }
//                                      }
                                        huffman.TallyDist(strstart - 1 - prevMatch, prevLen);
                                        prevLen -= 2;
                                        do {
                                                strstart++;
                                                lookahead--;
                                                if (lookahead >= MIN_MATCH) {
                                                        InsertString();
                                                }
                                        } while (--prevLen > 0);
                                        strstart ++;
                                        lookahead--;
                                        prevAvailable = false;
                                        matchLen = MIN_MATCH - 1;
                                } else {
                                        if (prevAvailable) {
                                                huffman.TallyLit(window[strstart-1] & 0xff);
                                        }
                                        prevAvailable = true;
                                        strstart++;
                                        lookahead--;
                                }
                                
                                if (huffman.IsFull()) {
                                        int len = strstart - blockStart;
                                        if (prevAvailable) {
                                                len--;
                                        }
                                        bool lastBlock = (finish && lookahead == 0 && !prevAvailable);
                                        huffman.FlushBlock(window, blockStart, len, lastBlock);
                                        blockStart += len;
                                        return !lastBlock;
                                }
                        }
                        return true;
                }
                
                public bool Deflate(bool flush, bool finish)
                {
                        bool progress;
                        do {
                                FillWindow();
                                bool canFlush = flush && inputOff == inputEnd;
//                              if (DeflaterConstants.DEBUGGING) {
//                                      Console.WriteLine("window: ["+blockStart+","+strstart+","
//                                                        +lookahead+"], "+comprFunc+","+canFlush);
//                              }
                                switch (comprFunc) {
                                        case DEFLATE_STORED:
                                                progress = DeflateStored(canFlush, finish);
                                        break;
                                        case DEFLATE_FAST:
                                                progress = DeflateFast(canFlush, finish);
                                        break;
                                        case DEFLATE_SLOW:
                                                progress = DeflateSlow(canFlush, finish);
                                        break;
                                        default:
                                                throw new InvalidOperationException("unknown comprFunc");
                                }
                        } while (pending.IsFlushed && progress); /* repeat while we have no pending output and progress was made */
                        return progress;
                }
                
                public void SetInput(byte[] buf, int off, int len)
                {
                        if (inputOff < inputEnd) {
                                throw new InvalidOperationException("Old input was not completely processed");
                        }
                        
                        int end = off + len;
                        
                        /* We want to throw an ArrayIndexOutOfBoundsException early.  The
                        * check is very tricky: it also handles integer wrap around.
                        */
                        if (0 > off || off > end || end > buf.Length) {
                                throw new ArgumentOutOfRangeException();
                        }
                        
                        inputBuf = buf;
                        inputOff = off;
                        inputEnd = end;
                }
                
                public bool NeedsInput()
                {
                        return inputEnd == inputOff;
                }
        }
}

namespace NZlib.Compression {
        
        /// <summary>
        /// This is the DeflaterHuffman class.
        /// 
        /// This class is <i>not</i> thread safe.  This is inherent in the API, due
        /// to the split of deflate and setInput.
        /// 
        /// author of the original java version : Jochen Hoenicke
        /// </summary>
        public class DeflaterHuffman
        {
                private static  int BUFSIZE = 1 << (DeflaterConstants.DEFAULT_MEM_LEVEL + 6);
                private static  int LITERAL_NUM = 286;
                private static  int DIST_NUM = 30;
                private static  int BITLEN_NUM = 19;
                private static  int REP_3_6    = 16;
                private static  int REP_3_10   = 17;
                private static  int REP_11_138 = 18;
                private static  int EOF_SYMBOL = 256;
                private static  int[] BL_ORDER = { 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15 };
                
                private static byte[] bit4Reverse = {
                        0,
                        8,
                        4,
                        12,
                        2,
                        10,
                        6,
                        14,
                        1,
                        9,
                        5,
                        13,
                        3,
                        11,
                        7,
                        15
                };
                
                
                public class Tree 
                {
                        public short[] freqs;
                        public short[] codes;
                        public byte[]  length;
                        public int[]   bl_counts;
                        public int     minNumCodes, numCodes;
                        public int     maxLength;
                        DeflaterHuffman dh;
                        
                        public Tree(DeflaterHuffman dh, int elems, int minCodes, int maxLength) 
                        {
                                this.dh =  dh;
                                this.minNumCodes = minCodes;
                                this.maxLength  = maxLength;
                                freqs  = new short[elems];
                                bl_counts = new int[maxLength];
                        }
                        
                        public void Reset() 
                        {
                                for (int i = 0; i < freqs.Length; i++) {
                                        freqs[i] = 0;
                                }
                                codes = null;
                                length = null;
                        }
                        
                        public void WriteSymbol(int code)
                        {
//                              if (DeflaterConstants.DEBUGGING) {
//                                      freqs[code]--;
//                                      //        Console.Write("writeSymbol("+freqs.length+","+code+"): ");
//                              }
                                dh.pending.WriteBits(codes[code] & 0xffff, length[code]);
                        }
                        
                        public void CheckEmpty()
                        {
                                bool empty = true;
                                for (int i = 0; i < freqs.Length; i++) {
                                        if (freqs[i] != 0) {
                                                Console.WriteLine("freqs["+i+"] == "+freqs[i]);
                                                empty = false;
                                        }
                                }
                                if (!empty) {
                                        throw new Exception();
                                }
                                Console.WriteLine("checkEmpty suceeded!");
                        }
                        
                        public void SetStaticCodes(short[] stCodes, byte[] stLength)
                        {
                                codes = stCodes;
                                length = stLength;
                        }
                        
                        public void BuildCodes() 
                        {
                                int numSymbols = freqs.Length;
                                int[] nextCode = new int[maxLength];
                                int code = 0;
                                codes = new short[freqs.Length];
                                
//                              if (DeflaterConstants.DEBUGGING) {
//                                      Console.WriteLine("buildCodes: "+freqs.Length);
//                              }
                                
                                for (int bits = 0; bits < maxLength; bits++) {
                                        nextCode[bits] = code;
                                        code += bl_counts[bits] << (15 - bits);
//                                      if (DeflaterConstants.DEBUGGING) {
//                                              Console.WriteLine("bits: "+(bits+1)+" count: "+bl_counts[bits]
//                                                                +" nextCode: "+code); // HACK : Integer.toHexString(
//                                      }
                                }
                                if (DeflaterConstants.DEBUGGING && code != 65536) {
                                        throw new Exception("Inconsistent bl_counts!");
                                }
                                
                                for (int i=0; i < numCodes; i++) {
                                        int bits = length[i];
                                        if (bits > 0) {
//                                              if (DeflaterConstants.DEBUGGING) {
//                                                              Console.WriteLine("codes["+i+"] = rev(" + nextCode[bits-1]+")," // HACK : Integer.toHexString(
//                                                                                +bits);
//                                              }
                                                codes[i] = BitReverse(nextCode[bits-1]);
                                                nextCode[bits-1] += 1 << (16 - bits);
                                        }
                                }
                        }
                        
                        private void BuildLength(int[] childs)
                        {
                                this.length = new byte [freqs.Length];
                                int numNodes = childs.Length / 2;
                                int numLeafs = (numNodes + 1) / 2;
                                int overflow = 0;
                                
                                for (int i = 0; i < maxLength; i++) {
                                        bl_counts[i] = 0;
                                }
                                
                                /* First calculate optimal bit lengths */
                                int[] lengths = new int[numNodes];
                                lengths[numNodes-1] = 0;
                                
                                for (int i = numNodes - 1; i >= 0; i--) {
                                        if (childs[2*i+1] != -1) {
                                                int bitLength = lengths[i] + 1;
                                                if (bitLength > maxLength) {
                                                        bitLength = maxLength;
                                                        overflow++;
                                                }
                                                lengths[childs[2*i]] = lengths[childs[2*i+1]] = bitLength;
                                        } else {
                                                /* A leaf node */
                                                int bitLength = lengths[i];
                                                bl_counts[bitLength - 1]++;
                                                this.length[childs[2*i]] = (byte) lengths[i];
                                        }
                                }
                                
//                              if (DeflaterConstants.DEBUGGING) {
//                                      Console.WriteLine("Tree "+freqs.Length+" lengths:");
//                                      for (int i=0; i < numLeafs; i++) {
//                                              Console.WriteLine("Node "+childs[2*i]+" freq: "+freqs[childs[2*i]]
//                                                                + " len: "+length[childs[2*i]]);
//                                      }
//                              }
                                
                                if (overflow == 0) {
                                        return;
                                }
                                
                                int incrBitLen = maxLength - 1;
                                do {
                                        /* Find the first bit length which could increase: */
                                        while (bl_counts[--incrBitLen] == 0)
                                                ;
                                        
                                        /* Move this node one down and remove a corresponding
                                        * amount of overflow nodes.
                                        */
                                        do {
                                                bl_counts[incrBitLen]--;
                                                bl_counts[++incrBitLen]++;
                                                overflow -= 1 << (maxLength - 1 - incrBitLen);
                                        } while (overflow > 0 && incrBitLen < maxLength - 1);
                                } while (overflow > 0);
                                
                                /* We may have overshot above.  Move some nodes from maxLength to
                                * maxLength-1 in that case.
                                */
                                bl_counts[maxLength-1] += overflow;
                                bl_counts[maxLength-2] -= overflow;
                                
                                /* Now recompute all bit lengths, scanning in increasing
                                * frequency.  It is simpler to reconstruct all lengths instead of
                                * fixing only the wrong ones. This idea is taken from 'ar'
                                * written by Haruhiko Okumura.
                                *
                                * The nodes were inserted with decreasing frequency into the childs
                                * array.
                                */
                                int nodePtr = 2 * numLeafs;
                                for (int bits = maxLength; bits != 0; bits--) {
                                        int n = bl_counts[bits-1];
                                        while (n > 0) {
                                                int childPtr = 2*childs[nodePtr++];
                                                if (childs[childPtr + 1] == -1) {
                                                        /* We found another leaf */
                                                        length[childs[childPtr]] = (byte) bits;
                                                        n--;
                                                }
                                        }
                                }
//                              if (DeflaterConstants.DEBUGGING) {
//                                      Console.WriteLine("*** After overflow elimination. ***");
//                                      for (int i=0; i < numLeafs; i++) {
//                                              Console.WriteLine("Node "+childs[2*i]+" freq: "+freqs[childs[2*i]]
//                                                                + " len: "+length[childs[2*i]]);
//                                      }
//                              }
                        }
                        
                        public void BuildTree()
                        {
                                int numSymbols = freqs.Length;
                                
                                /* heap is a priority queue, sorted by frequency, least frequent
                                * nodes first.  The heap is a binary tree, with the property, that
                                * the parent node is smaller than both child nodes.  This assures
                                * that the smallest node is the first parent.
                                *
                                * The binary tree is encoded in an array:  0 is root node and
                                * the nodes 2*n+1, 2*n+2 are the child nodes of node n.
                                */
                                int[] heap = new int[numSymbols];
                                int heapLen = 0;
                                int maxCode = 0;
                                for (int n = 0; n < numSymbols; n++) {
                                        int freq = freqs[n];
                                        if (freq != 0) {
                                                /* Insert n into heap */
                                                int pos = heapLen++;
                                                int ppos;
                                                while (pos > 0 && freqs[heap[ppos = (pos - 1) / 2]] > freq) {
                                                        heap[pos] = heap[ppos];
                                                        pos = ppos;
                                                }
                                                heap[pos] = n;
                                                
                                                maxCode = n;
                                        }
                                }
                                
                                /* We could encode a single literal with 0 bits but then we
                                * don't see the literals.  Therefore we force at least two
                                * literals to avoid this case.  We don't care about order in
                                * this case, both literals get a 1 bit code.
                                */
                                while (heapLen < 2) {
                                        int node = maxCode < 2 ? ++maxCode : 0;
                                        heap[heapLen++] = node;
                                }
                                
                                numCodes = Math.Max(maxCode + 1, minNumCodes);
                                
                                int numLeafs = heapLen;
                                int[] childs = new int[4*heapLen - 2];
                                int[] values = new int[2*heapLen - 1];
                                int numNodes = numLeafs;
                                for (int i = 0; i < heapLen; i++) {
                                        int node = heap[i];
                                        childs[2*i]   = node;
                                        childs[2*i+1] = -1;
                                        values[i] = freqs[node] << 8;
                                        heap[i] = i;
                                }
                                
                                /* Construct the Huffman tree by repeatedly combining the least two
                                * frequent nodes.
                                */
                                do {
                                        int first = heap[0];
                                        int last  = heap[--heapLen];
                                        
                                        /* Propagate the hole to the leafs of the heap */
                                        int ppos = 0;
                                        int path = 1;
                                        while (path < heapLen) {
                                                if (path + 1 < heapLen && values[heap[path]] > values[heap[path+1]]) {
                                                        path++;
                                                }
                                                
                                                heap[ppos] = heap[path];
                                                ppos = path;
                                                path = path * 2 + 1;
                                        }
                                        
                                        /* Now propagate the last element down along path.  Normally
                                        * it shouldn't go too deep.
                                        */
                                        int lastVal = values[last];
                                        while ((path = ppos) > 0 && values[heap[ppos = (path - 1)/2]] > lastVal) {
                                                heap[path] = heap[ppos];
                                        }
                                        heap[path] = last;
                                        
                                        
                                        int second = heap[0];
                                        
                                        /* Create a new node father of first and second */
                                        last = numNodes++;
                                        childs[2*last] = first;
                                        childs[2*last+1] = second;
                                        int mindepth = Math.Min(values[first] & 0xff, values[second] & 0xff);
                                        values[last] = lastVal = values[first] + values[second] - mindepth + 1;
                                        
                                        /* Again, propagate the hole to the leafs */
                                        ppos = 0;
                                        path = 1;
                                        while (path < heapLen) {
                                                if (path + 1 < heapLen && values[heap[path]] > values[heap[path+1]]) {
                                                        path++;
                                                }
                                                
                                                heap[ppos] = heap[path];
                                                ppos = path;
                                                path = ppos * 2 + 1;
                                        }
                                        
                                        /* Now propagate the new element down along path */
                                        while ((path = ppos) > 0 && values[heap[ppos = (path - 1)/2]] > lastVal) {
                                                heap[path] = heap[ppos];
                                        }
                                        heap[path] = last;
                                } while (heapLen > 1);
                                
                                if (heap[0] != childs.Length / 2 - 1) {
                                        throw new Exception("Weird!");
                                }
                                BuildLength(childs);
                        }
                        
                        public int GetEncodedLength()
                        {
                                int len = 0;
                                for (int i = 0; i < freqs.Length; i++) {
                                        len += freqs[i] * length[i];
                                }
                                return len;
                        }
                        
                        public void CalcBLFreq(Tree blTree) 
                        {
                                int max_count;               /* max repeat count */
                                int min_count;               /* min repeat count */
                                int count;                   /* repeat count of the current code */
                                int curlen = -1;             /* length of current code */
                                
                                int i = 0;
                                while (i < numCodes) {
                                        count = 1;
                                        int nextlen = length[i];
                                        if (nextlen == 0) {
                                                max_count = 138;
                                                min_count = 3;
                                        } else {
                                                max_count = 6;
                                                min_count = 3;
                                                if (curlen != nextlen) {
                                                        blTree.freqs[nextlen]++;
                                                        count = 0;
                                                }
                                        }
                                        curlen = nextlen;
                                        i++;
                                        
                                        while (i < numCodes && curlen == length[i]) {
                                                i++;
                                                if (++count >= max_count) {
                                                        break;
                                                }
                                        }
                                        
                                        if (count < min_count) {
                                                blTree.freqs[curlen] += (short)count;
                                        } else if (curlen != 0) {
                                                blTree.freqs[REP_3_6]++;
                                        } else if (count <= 10) {
                                                blTree.freqs[REP_3_10]++;
                                        } else {
                                                blTree.freqs[REP_11_138]++;
                                        }
                                }
                        }
                        
                        public void WriteTree(Tree blTree)
                        {
                                int max_count;               /* max repeat count */
                                int min_count;               /* min repeat count */
                                int count;                   /* repeat count of the current code */
                                int curlen = -1;             /* length of current code */
                                
                                int i = 0;
                                while (i < numCodes) {
                                        count = 1;
                                        int nextlen = length[i];
                                        if (nextlen == 0) {
                                                max_count = 138;
                                                min_count = 3;
                                        } else {
                                                max_count = 6;
                                                min_count = 3;
                                                if (curlen != nextlen) {
                                                        blTree.WriteSymbol(nextlen);
                                                        count = 0;
                                                }
                                        }
                                        curlen = nextlen;
                                        i++;
                                        
                                        while (i < numCodes && curlen == length[i]) {
                                                i++;
                                                if (++count >= max_count) {
                                                        break;
                                                }
                                        }
                                        
                                        if (count < min_count) {
                                                while (count-- > 0) {
                                                        blTree.WriteSymbol(curlen);
                                                }
                                        }
                                        else if (curlen != 0) {
                                                blTree.WriteSymbol(REP_3_6);
                                                dh.pending.WriteBits(count - 3, 2);
                                        } else if (count <= 10) {
                                                blTree.WriteSymbol(REP_3_10);
                                                dh.pending.WriteBits(count - 3, 3);
                                        } else {
                                                blTree.WriteSymbol(REP_11_138);
                                                dh.pending.WriteBits(count - 11, 7);
                                        }
                                }
                        }
                }
                
                public DeflaterPending pending;
                private Tree literalTree, distTree, blTree;
                
                private short[] d_buf;
                private byte[] l_buf;
                private int last_lit;
                private int extra_bits;
                
                private static short[] staticLCodes;
                private static byte[]  staticLLength;
                private static short[] staticDCodes;
                private static byte[]  staticDLength;
                
                /// <summary>
                /// Reverse the bits of a 16 bit value.
                /// </summary>
                public static short BitReverse(int value) 
                {
                        return (short) (bit4Reverse[value & 0xF] << 12
                                        | bit4Reverse[(value >> 4) & 0xF] << 8
                                        | bit4Reverse[(value >> 8) & 0xF] << 4
                                        | bit4Reverse[value >> 12]);
                }
                
                
                static DeflaterHuffman() 
                {
                        /* See RFC 1951 3.2.6 */
                        /* Literal codes */
                        staticLCodes = new short[LITERAL_NUM];
                        staticLLength = new byte[LITERAL_NUM];
                        int i = 0;
                        while (i < 144) {
                                staticLCodes[i] = BitReverse((0x030 + i) << 8);
                                staticLLength[i++] = 8;
                        }
                        while (i < 256) {
                                staticLCodes[i] = BitReverse((0x190 - 144 + i) << 7);
                                staticLLength[i++] = 9;
                        }
                        while (i < 280) {
                                staticLCodes[i] = BitReverse((0x000 - 256 + i) << 9);
                                staticLLength[i++] = 7;
                        }
                        while (i < LITERAL_NUM) {
                                staticLCodes[i] = BitReverse((0x0c0 - 280 + i)  << 8);
                                staticLLength[i++] = 8;
                        }
                        
                        /* Distant codes */
                        staticDCodes = new short[DIST_NUM];
                        staticDLength = new byte[DIST_NUM];
                        for (i = 0; i < DIST_NUM; i++) {
                                staticDCodes[i] = BitReverse(i << 11);
                                staticDLength[i] = 5;
                        }
                }
                
                public DeflaterHuffman(DeflaterPending pending)
                {
                        this.pending = pending;
                        
                        literalTree = new Tree(this, LITERAL_NUM, 257, 15);
                        distTree    = new Tree(this, DIST_NUM, 1, 15);
                        blTree      = new Tree(this, BITLEN_NUM, 4, 7);
                        
                        d_buf = new short[BUFSIZE];
                        l_buf = new byte [BUFSIZE];
                }
                
                public void Reset() 
                {
                        last_lit = 0;
                        extra_bits = 0;
                        literalTree.Reset();
                        distTree.Reset();
                        blTree.Reset();
                }
                
                private int L_code(int len) 
                {
                        if (len == 255) {
                                return 285;
                        }
                        
                        int code = 257;
                        while (len >= 8) {
                                code += 4;
                                len >>= 1;
                        }
                        return code + len;
                }
                
                private int D_code(int distance) 
                {
                        int code = 0;
                        while (distance >= 4) {
                                code += 2;
                                distance >>= 1;
                        }
                        return code + distance;
                }
                
                public void SendAllTrees(int blTreeCodes)
                {
                        blTree.BuildCodes();
                        literalTree.BuildCodes();
                        distTree.BuildCodes();
                        pending.WriteBits(literalTree.numCodes - 257, 5);
                        pending.WriteBits(distTree.numCodes - 1, 5);
                        pending.WriteBits(blTreeCodes - 4, 4);
                        for (int rank = 0; rank < blTreeCodes; rank++) {
                                pending.WriteBits(blTree.length[BL_ORDER[rank]], 3);
                        }
                        literalTree.WriteTree(blTree);
                        distTree.WriteTree(blTree);
//                      if (DeflaterConstants.DEBUGGING) {
//                              blTree.CheckEmpty();
//                      }
                }
                
                public void CompressBlock()
                {
                        for (int i = 0; i < last_lit; i++) {
                                int litlen = l_buf[i] & 0xff;
                                int dist = d_buf[i];
                                if (dist-- != 0) {
//                                      if (DeflaterConstants.DEBUGGING) {
//                                              Console.Write("["+(dist+1)+","+(litlen+3)+"]: ");
//                                      }
                                        
                                        int lc = L_code(litlen);
                                        literalTree.WriteSymbol(lc);
                                        
                                        int bits = (lc - 261) / 4;
                                        if (bits > 0 && bits <= 5) {
                                                pending.WriteBits(litlen & ((1 << bits) - 1), bits);
                                        }
                                        
                                        int dc = D_code(dist);
                                        distTree.WriteSymbol(dc);
                                        
                                        bits = dc / 2 - 1;
                                        if (bits > 0) {
                                                pending.WriteBits(dist & ((1 << bits) - 1), bits);
                                        }
                                } else {
//                                      if (DeflaterConstants.DEBUGGING) {
//                                              if (litlen > 32 && litlen < 127) {
//                                                      Console.Write("("+(char)litlen+"): ");
//                                              } else {
//                                                      Console.Write("{"+litlen+"}: ");
//                                              }
//                                      }
                                        literalTree.WriteSymbol(litlen);
                                }
                        }
//                      if (DeflaterConstants.DEBUGGING) {
//                              Console.Write("EOF: ");
//                      }
                        literalTree.WriteSymbol(EOF_SYMBOL);
//                      if (DeflaterConstants.DEBUGGING) {
//                              literalTree.CheckEmpty();
//                              distTree.CheckEmpty();
//                      }
                }
                
                public void FlushStoredBlock(byte[] stored, int stored_offset, int stored_len, bool lastBlock)
                {
//                      if (DeflaterConstants.DEBUGGING) {
//                              Console.WriteLine("Flushing stored block "+ stored_len);
//                      }
                        pending.WriteBits((DeflaterConstants.STORED_BLOCK << 1)
                                          + (lastBlock ? 1 : 0), 3);
                        pending.AlignToByte();
                        pending.WriteShort(stored_len);
                        pending.WriteShort(~stored_len);
                        pending.WriteBlock(stored, stored_offset, stored_len);
                        Reset();
                }
                
                public void FlushBlock(byte[] stored, int stored_offset, int stored_len, bool lastBlock)
                {
                        literalTree.freqs[EOF_SYMBOL]++;
                        
                        /* Build trees */
                        literalTree.BuildTree();
                        distTree.BuildTree();
                        
                        /* Calculate bitlen frequency */
                        literalTree.CalcBLFreq(blTree);
                        distTree.CalcBLFreq(blTree);
                        
                        /* Build bitlen tree */
                        blTree.BuildTree();
                        
                        int blTreeCodes = 4;
                        for (int i = 18; i > blTreeCodes; i--) {
                                if (blTree.length[BL_ORDER[i]] > 0) {
                                        blTreeCodes = i+1;
                                }
                        }
                        int opt_len = 14 + blTreeCodes * 3 + blTree.GetEncodedLength() + 
                                      literalTree.GetEncodedLength() + distTree.GetEncodedLength() + 
                                      extra_bits;
                        
                        int static_len = extra_bits;
                        for (int i = 0; i < LITERAL_NUM; i++) {
                                static_len += literalTree.freqs[i] * staticLLength[i];
                        }
                        for (int i = 0; i < DIST_NUM; i++) {
                                static_len += distTree.freqs[i] * staticDLength[i];
                        }
                        if (opt_len >= static_len) {
                                /* Force static trees */
                                opt_len = static_len;
                        }
                        
                        if (stored_offset >= 0 && stored_len+4 < opt_len >> 3) {
                                /* Store Block */
//                              if (DeflaterConstants.DEBUGGING) {
//                                      Console.WriteLine("Storing, since " + stored_len + " < " + opt_len
//                                                        + " <= " + static_len);
//                              }
                                FlushStoredBlock(stored, stored_offset, stored_len, lastBlock);
                        } else if (opt_len == static_len) {
                                /* Encode with static tree */
                                pending.WriteBits((DeflaterConstants.STATIC_TREES << 1) + (lastBlock ? 1 : 0), 3);
                                literalTree.SetStaticCodes(staticLCodes, staticLLength);
                                distTree.SetStaticCodes(staticDCodes, staticDLength);
                                CompressBlock();
                                Reset();
                        } else {
                                /* Encode with dynamic tree */
                                pending.WriteBits((DeflaterConstants.DYN_TREES << 1) + (lastBlock ? 1 : 0), 3);
                                SendAllTrees(blTreeCodes);
                                CompressBlock();
                                Reset();
                        }
                }
                
                public bool IsFull()
                {
                        return last_lit + 16 >= BUFSIZE; // HACK: This was == 'last_lit == BUFSIZE', but errors occured with DeflateFast
                }
                
                public bool TallyLit(int lit)
                {
//                      if (DeflaterConstants.DEBUGGING) {
//                              if (lit > 32 && lit < 127) {
//                                      Console.WriteLine("("+(char)lit+")");
//                              } else {
//                                      Console.WriteLine("{"+lit+"}");
//                              }
//                      }
                        d_buf[last_lit] = 0;
                        l_buf[last_lit++] = (byte)lit;
                        literalTree.freqs[lit]++;
                        return IsFull();
                }
                
                public bool TallyDist(int dist, int len)
                {
//                      if (DeflaterConstants.DEBUGGING) {
//                              Console.WriteLine("["+dist+","+len+"]");
//                      }
                        
                        d_buf[last_lit]   = (short)dist;
                        l_buf[last_lit++] = (byte)(len - 3);
                        
                        int lc = L_code(len - 3);
                        literalTree.freqs[lc]++;
                        if (lc >= 265 && lc < 285) {
                                extra_bits += (lc - 261) / 4;
                        }
                        
                        int dc = D_code(dist - 1);
                        distTree.freqs[dc]++;
                        if (dc >= 4) {
                                extra_bits += dc / 2 - 1;
                        }
                        return IsFull();
                }
        }
}

namespace NZlib.Compression {
        
        /// <summary>
        /// This class stores the pending output of the Deflater.
        /// 
        /// author of the original java version : Jochen Hoenicke
        /// </summary>
        public class DeflaterPending : PendingBuffer
        {
                public DeflaterPending() : base(DeflaterConstants.PENDING_BUF_SIZE)
                {
                }
        }
}

namespace NZlib.Compression {
        
        /// <summary>
        /// Inflater is used to decompress data that has been compressed according
        /// to the "deflate" standard described in rfc1950.
        ///
        /// The usage is as following.  First you have to set some input with
        /// <code>setInput()</code>, then inflate() it.  If inflate doesn't
        /// inflate any bytes there may be three reasons:
        /// <ul>
        /// <li>needsInput() returns true because the input buffer is empty.
        /// You have to provide more input with <code>setInput()</code>.
        /// NOTE: needsInput() also returns true when, the stream is finished.
        /// </li>
        /// <li>needsDictionary() returns true, you have to provide a preset
        ///    dictionary with <code>setDictionary()</code>.</li>
        /// <li>finished() returns true, the inflater has finished.</li>
        /// </ul>
        /// Once the first output byte is produced, a dictionary will not be
        /// needed at a later stage.
        ///
        /// author of the original java version : John Leuner, Jochen Hoenicke
        /// </summary>
        public class Inflater
        {
                /// <summary>
                /// Copy lengths for literal codes 257..285
                /// </summary>
                private static int[] CPLENS = {
                        3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31,
                        35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258
                };
                
                /// <summary>
                /// Extra bits for literal codes 257..285
                /// </summary>
                private static int[] CPLEXT = {
                        0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2,
                        3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0
                };
                
                /// <summary>
                /// Copy offsets for distance codes 0..29
                /// </summary>
                private static int[] CPDIST = {
                        1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193,
                        257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145,
                        8193, 12289, 16385, 24577
                };
                
                /// <summary>
                /// Extra bits for distance codes
                /// </summary>
                private static int[] CPDEXT = {
                        0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6,
                        7, 7, 8, 8, 9, 9, 10, 10, 11, 11,
                        12, 12, 13, 13
                };
                
                /// <summary>
                /// This are the state in which the inflater can be.
                /// </summary>
                private const int DECODE_HEADER           = 0;
                private const int DECODE_DICT             = 1;
                private const int DECODE_BLOCKS           = 2;
                private const int DECODE_STORED_LEN1      = 3;
                private const int DECODE_STORED_LEN2      = 4;
                private const int DECODE_STORED           = 5;
                private const int DECODE_DYN_HEADER       = 6;
                private const int DECODE_HUFFMAN          = 7;
                private const int DECODE_HUFFMAN_LENBITS  = 8;
                private const int DECODE_HUFFMAN_DIST     = 9;
                private const int DECODE_HUFFMAN_DISTBITS = 10;
                private const int DECODE_CHKSUM           = 11;
                private const int FINISHED                = 12;
                
                /// <summary>
                /// This variable contains the current state.
                /// </summary>
                private int mode;
                
                /// <summary>
                /// The adler checksum of the dictionary or of the decompressed
                /// stream, as it is written in the header resp. footer of the
                /// compressed stream. 
                /// Only valid if mode is DECODE_DICT or DECODE_CHKSUM.
                /// </summary>
                private int readAdler;
                
                /// <summary>
                /// The number of bits needed to complete the current state.  This
                /// is valid, if mode is DECODE_DICT, DECODE_CHKSUM,
                /// DECODE_HUFFMAN_LENBITS or DECODE_HUFFMAN_DISTBITS.
                /// </summary>
                private int neededBits;
                private int repLength, repDist;
                private int uncomprLen;
                
                /// <summary>
                /// True, if the last block flag was set in the last block of the
                /// inflated stream.  This means that the stream ends after the
                /// current block.
                /// </summary>
                private bool isLastBlock;
                
                /// <summary>
                /// The total number of inflated bytes.
                /// </summary>
                private int totalOut;
                
                /// <summary>
                /// The total number of bytes set with setInput().  This is not the
                /// value returned by getTotalIn(), since this also includes the
                /// unprocessed input.
                /// </summary>
                private int totalIn;
                
                /// <summary>
                /// This variable stores the nowrap flag that was given to the constructor.
                /// True means, that the inflated stream doesn't contain a header nor the
                /// checksum in the footer.
                /// </summary>
                private bool nowrap;
                
                private StreamManipulator input;
                private OutputWindow outputWindow;
                private InflaterDynHeader dynHeader;
                private InflaterHuffmanTree litlenTree, distTree;
                private Adler32 adler;
                
                /// <summary>
                /// Creates a new inflater.
                /// </summary>
                public Inflater() : this(false)
                {
                }
                
                /// <summary>
                /// Creates a new inflater.
                /// </summary>
                /// <param name="nowrap">
                /// true if no header and checksum field appears in the
                /// stream.  This is used for GZIPed input.  For compatibility with
                /// Sun JDK you should provide one byte of input more than needed in
                /// this case.
                /// </param>
                public Inflater(bool nowrap)
                {
                        this.nowrap = nowrap;
                        this.adler = new Adler32();
                        input = new StreamManipulator();
                        outputWindow = new OutputWindow();
                        mode = nowrap ? DECODE_BLOCKS : DECODE_HEADER;
                }
                
                /// <summary>
                /// Resets the inflater so that a new stream can be decompressed.  All
                /// pending input and output will be discarded.
                /// </summary>
                public void Reset()
                {
                        mode = nowrap ? DECODE_BLOCKS : DECODE_HEADER;
                        totalIn = totalOut = 0;
                        input.Reset();
                        outputWindow.Reset();
                        dynHeader = null;
                        litlenTree = null;
                        distTree = null;
                        isLastBlock = false;
                        adler.Reset();
                }
                
                /// <summary>
                /// Decodes the deflate header.
                /// </summary>
                /// <returns>
                /// false if more input is needed.
                /// </returns>
                /// <exception cref="System.FormatException">
                /// if header is invalid.
                /// </exception>
                private bool DecodeHeader()
                {
                        int header = input.PeekBits(16);
                        if (header < 0) {
                                return false;
                        }
                        input.DropBits(16);
                        /* The header is written in "wrong" byte order */
                        header = ((header << 8) | (header >> 8)) & 0xffff;
                        if (header % 31 != 0) {
                                throw new FormatException("Header checksum illegal");
                        }
                        
                        if ((header & 0x0f00) != (Deflater.DEFLATED << 8)) {
                                throw new FormatException("Compression Method unknown");
                        }
                        
                        /* Maximum size of the backwards window in bits.
                        * We currently ignore this, but we could use it to make the
                        * inflater window more space efficient. On the other hand the
                        * full window (15 bits) is needed most times, anyway.
                        int max_wbits = ((header & 0x7000) >> 12) + 8;
                        */
                        
                        if ((header & 0x0020) == 0) { // Dictionary flag?
                                mode = DECODE_BLOCKS;
                        } else {
                                mode = DECODE_DICT;
                                neededBits = 32;
                        }
                        return true;
                }
                
                /// <summary>
                /// Decodes the dictionary checksum after the deflate header.
                /// </summary>
                /// <returns>
                /// false if more input is needed.
                /// </returns>
                private bool DecodeDict()
                {
                        while (neededBits > 0) {
                                int dictByte = input.PeekBits(8);
                                if (dictByte < 0) {
                                        return false;
                                }
                                input.DropBits(8);
                                readAdler = (readAdler << 8) | dictByte;
                                neededBits -= 8;
                        }
                        return false;
                }
                
                /// <summary>
                /// Decodes the huffman encoded symbols in the input stream.
                /// </summary>
                /// <returns>
                /// false if more input is needed, true if output window is
                /// full or the current block ends.
                /// </returns>
                /// <exception cref="System.FormatException">
                /// if deflated stream is invalid.
                /// </exception>
                private bool DecodeHuffman()
                {
                        int free = outputWindow.GetFreeSpace();
                        while (free >= 258) {
                                int symbol;
                                switch (mode) {
                                        case DECODE_HUFFMAN:
                                                /* This is the inner loop so it is optimized a bit */
                                                while (((symbol = litlenTree.GetSymbol(input)) & ~0xff) == 0) {
                                                        outputWindow.Write(symbol);
                                                        if (--free < 258) {
                                                                return true;
                                                        }
                                                }
                                                if (symbol < 257) {
                                                        if (symbol < 0) {
                                                                return false;
                                                        } else {
                                                                /* symbol == 256: end of block */
                                                                distTree = null;
                                                                litlenTree = null;
                                                                mode = DECODE_BLOCKS;
                                                                return true;
                                                        }
                                                }
                                                
                                                try {
                                                        repLength = CPLENS[symbol - 257];
                                                        neededBits = CPLEXT[symbol - 257];
                                                } catch (Exception) {
                                                        throw new FormatException("Illegal rep length code");
                                                }
                                                goto case DECODE_HUFFMAN_LENBITS;/* fall through */
                                        case DECODE_HUFFMAN_LENBITS:
                                                if (neededBits > 0) {
                                                        mode = DECODE_HUFFMAN_LENBITS;
                                                        int i = input.PeekBits(neededBits);
                                                        if (i < 0) {
                                                                return false;
                                                        }
                                                        input.DropBits(neededBits);
                                                        repLength += i;
                                                }
                                                mode = DECODE_HUFFMAN_DIST;
                                                goto case DECODE_HUFFMAN_DIST;/* fall through */
                                        case DECODE_HUFFMAN_DIST:
                                                symbol = distTree.GetSymbol(input);
                                                if (symbol < 0) {
                                                        return false;
                                                }
                                                try {
                                                        repDist = CPDIST[symbol];
                                                        neededBits = CPDEXT[symbol];
                                                } catch (Exception) {
                                                        throw new FormatException("Illegal rep dist code");
                                                }
                                                
                                                goto case DECODE_HUFFMAN_DISTBITS;/* fall through */
                                        case DECODE_HUFFMAN_DISTBITS:
                                                if (neededBits > 0) {
                                                        mode = DECODE_HUFFMAN_DISTBITS;
                                                        int i = input.PeekBits(neededBits);
                                                        if (i < 0) {
                                                                return false;
                                                        }
                                                        input.DropBits(neededBits);
                                                        repDist += i;
                                                }
                                                outputWindow.Repeat(repLength, repDist);
                                                free -= repLength;
                                                mode = DECODE_HUFFMAN;
                                                break;
                                        default:
                                                throw new FormatException();
                                }
                        }
                        return true;
                }
                
                /// <summary>
                /// Decodes the adler checksum after the deflate stream.
                /// </summary>
                /// <returns>
                /// false if more input is needed.
                /// </returns>
                /// <exception cref="System.FormatException">
                /// DataFormatException, if checksum doesn't match.
                /// </exception>
                private bool DecodeChksum()
                {
                        while (neededBits > 0) {
                                int chkByte = input.PeekBits(8);
                                if (chkByte < 0) {
                                        return false;
                                }
                                input.DropBits(8);
                                readAdler = (readAdler << 8) | chkByte;
                                neededBits -= 8;
                        }
                        if ((int) adler.Value != readAdler) {
                                throw new FormatException("Adler chksum doesn't match: "
                                                          + (int)adler.Value
                                                          + " vs. " + readAdler);
                        }
                        mode = FINISHED;
                        return false;
                }
                
                /// <summary>
                /// Decodes the deflated stream.
                /// </summary>
                /// <returns>
                /// false if more input is needed, or if finished.
                /// </returns>
                /// <exception cref="System.FormatException">
                /// DataFormatException, if deflated stream is invalid.
                /// </exception>
                private bool Decode()
                {
                        switch (mode) {
                                case DECODE_HEADER:
                                        return DecodeHeader();
                                case DECODE_DICT:
                                        return DecodeDict();
                                case DECODE_CHKSUM:
                                        return DecodeChksum();
                                
                                case DECODE_BLOCKS:
                                        if (isLastBlock) {
                                                if (nowrap) {
                                                        mode = FINISHED;
                                                        return false;
                                                } else {
                                                        input.SkipToByteBoundary();
                                                        neededBits = 32;
                                                        mode = DECODE_CHKSUM;
                                                        return true;
                                                }
                                        }
                                        
                                        int type = input.PeekBits(3);
                                        if (type < 0) {
                                                return false;
                                        }
                                        input.DropBits(3);
                                        
                                        if ((type & 1) != 0) {
                                                isLastBlock = true;
                                        }
                                        switch (type >> 1) {
                                                case DeflaterConstants.STORED_BLOCK:
                                                        input.SkipToByteBoundary();
                                                        mode = DECODE_STORED_LEN1;
                                                        break;
                                                case DeflaterConstants.STATIC_TREES:
                                                        litlenTree = InflaterHuffmanTree.defLitLenTree;
                                                        distTree = InflaterHuffmanTree.defDistTree;
                                                        mode = DECODE_HUFFMAN;
                                                        break;
                                                case DeflaterConstants.DYN_TREES:
                                                        dynHeader = new InflaterDynHeader();
                                                        mode = DECODE_DYN_HEADER;
                                                        break;
                                                default:
                                                        throw new FormatException("Unknown block type "+type);
                                        }
                                        return true;
                                
                                case DECODE_STORED_LEN1: {
                                        if ((uncomprLen = input.PeekBits(16)) < 0) {
                                                return false;
                                        }
                                        input.DropBits(16);
                                        mode = DECODE_STORED_LEN2;
                                }
                                goto case DECODE_STORED_LEN2; /* fall through */
                                case DECODE_STORED_LEN2: {
                                        int nlen = input.PeekBits(16);
                                        if (nlen < 0) {
                                                return false;
                                        }
                                        input.DropBits(16);
                                        if (nlen != (uncomprLen ^ 0xffff)) {
                                                throw new FormatException("broken uncompressed block");
                                        }
                                        mode = DECODE_STORED;
                                }
                                goto case DECODE_STORED;/* fall through */
                                case DECODE_STORED: {
                                        int more = outputWindow.CopyStored(input, uncomprLen);
                                        uncomprLen -= more;
                                        if (uncomprLen == 0) {
                                                mode = DECODE_BLOCKS;
                                                return true;
                                        }
                                        return !input.IsNeedingInput;
                                }
                                
                                case DECODE_DYN_HEADER:
                                        if (!dynHeader.Decode(input)) {
                                                return false;
                                        }
                                        
                                        litlenTree = dynHeader.BuildLitLenTree();
                                        distTree = dynHeader.BuildDistTree();
                                        mode = DECODE_HUFFMAN;
                                        goto case DECODE_HUFFMAN; /* fall through */
                                case DECODE_HUFFMAN:
                                case DECODE_HUFFMAN_LENBITS:
                                case DECODE_HUFFMAN_DIST:
                                case DECODE_HUFFMAN_DISTBITS:
                                        return DecodeHuffman();
                                case FINISHED:
                                        return false;
                                default:
                                        throw new FormatException();
                        }
                }
                        
                /// <summary>
                /// Sets the preset dictionary.  This should only be called, if
                /// needsDictionary() returns true and it should set the same
                /// dictionary, that was used for deflating.  The getAdler()
                /// function returns the checksum of the dictionary needed.
                /// </summary>
                /// <param name="buffer">
                /// the dictionary.
                /// </param>
                /// <exception cref="System.InvalidOperationException">
                /// if no dictionary is needed.
                /// </exception>
                /// <exception cref="System.ArgumentException">
                /// if the dictionary checksum is wrong.
                /// </exception>
                public void SetDictionary(byte[] buffer)
                {
                        SetDictionary(buffer, 0, buffer.Length);
                }
                
                /// <summary>
                /// Sets the preset dictionary.  This should only be called, if
                /// needsDictionary() returns true and it should set the same
                /// dictionary, that was used for deflating.  The getAdler()
                /// function returns the checksum of the dictionary needed.
                /// </summary>
                /// <param name="buffer">
                /// the dictionary.
                /// </param>
                /// <param name="off">
                /// the offset into buffer where the dictionary starts.
                /// </param>
                /// <param name="len">
                /// the length of the dictionary.
                /// </param>
                /// <exception cref="System.InvalidOperationException">
                /// if no dictionary is needed.
                /// </exception>
                /// <exception cref="System.ArgumentException">
                /// if the dictionary checksum is wrong.
                /// </exception>
                /// <exception cref="System.ArgumentOutOfRangeException">
                /// if the off and/or len are wrong.
                /// </exception>
                public void SetDictionary(byte[] buffer, int off, int len)
                {
                        if (!IsNeedingDictionary) {
                                throw new InvalidOperationException();
                        }
                        
                        adler.Update(buffer, off, len);
                        if ((int) adler.Value != readAdler) {
                                throw new ArgumentException("Wrong adler checksum");
                        }
                        adler.Reset();
                        outputWindow.CopyDict(buffer, off, len);
                        mode = DECODE_BLOCKS;
                }
                
                /// <summary>
                /// Sets the input.  This should only be called, if needsInput()
                /// returns true.
                /// </summary>
                /// <param name="buf">
                /// the input.
                /// </param>
                /// <exception cref="System.InvalidOperationException">
                /// if no input is needed.
                /// </exception>
                public void SetInput(byte[] buf)
                {
                        SetInput(buf, 0, buf.Length);
                }
                
                /// <summary>
                /// Sets the input.  This should only be called, if needsInput()
                /// returns true.
                /// </summary>
                /// <param name="buf">
                /// the input.
                /// </param>
                /// <param name="off">
                /// the offset into buffer where the input starts.
                /// </param>
                /// <param name="len">
                /// the length of the input.
                /// </param>
                /// <exception cref="System.InvalidOperationException">
                /// if no input is needed.
                /// </exception>
                /// <exception cref="System.ArgumentOutOfRangeException">
                /// if the off and/or len are wrong.
                /// </exception>
                public void SetInput(byte[] buf, int off, int len)
                {
                        input.SetInput(buf, off, len);
                        totalIn += len;
                }
                
                /// <summary>
                /// Inflates the compressed stream to the output buffer.  If this
                /// returns 0, you should check, whether needsDictionary(),
                /// needsInput() or finished() returns true, to determine why no
                /// further output is produced.
                /// </summary>
                /// <param name = "buf">
                /// the output buffer.
                /// </param>
                /// <returns>
                /// the number of bytes written to the buffer, 0 if no further
                /// output can be produced.
                /// </returns>
                /// <exception cref="System.ArgumentOutOfRangeException">
                /// if buf has length 0.
                /// </exception>
                /// <exception cref="System.FormatException">
                /// if deflated stream is invalid.
                /// </exception>
                public int Inflate(byte[] buf)
                {
                        return Inflate(buf, 0, buf.Length);
                }
                
                /// <summary>
                /// Inflates the compressed stream to the output buffer.  If this
                /// returns 0, you should check, whether needsDictionary(),
                /// needsInput() or finished() returns true, to determine why no
                /// further output is produced.
                /// </summary>
                /// <param name = "buf">
                /// the output buffer.
                /// </param>
                /// <param name = "off">
                /// the offset into buffer where the output should start.
                /// </param>
                /// <param name = "len">
                /// the maximum length of the output.
                /// </param>
                /// <returns>
                /// the number of bytes written to the buffer, 0 if no further output can be produced.
                /// </returns>
                /// <exception cref="System.ArgumentOutOfRangeException">
                /// if len is &lt;= 0.
                /// </exception>
                /// <exception cref="System.ArgumentOutOfRangeException">
                /// if the off and/or len are wrong.
                /// </exception>
                /// <exception cref="System.FormatException">
                /// if deflated stream is invalid.
                /// </exception>
                public int Inflate(byte[] buf, int off, int len)
                {
                        if (len <= 0) {
                                throw new ArgumentOutOfRangeException("len <= 0");
                        }
                        int count = 0;
                        int more;
                        do {
                                if (mode != DECODE_CHKSUM) {
                                        /* Don't give away any output, if we are waiting for the
                                        * checksum in the input stream.
                                        *
                                        * With this trick we have always:
                                        *   needsInput() and not finished()
                                        *   implies more output can be produced.
                                        */
                                        more = outputWindow.CopyOutput(buf, off, len);
                                        adler.Update(buf, off, more);
                                        off += more;
                                        count += more;
                                        totalOut += more;
                                        len -= more;
                                        if (len == 0) {
                                                return count;
                                        }
                                }
                        } while (Decode() || (outputWindow.GetAvailable() > 0 &&
                                              mode != DECODE_CHKSUM));
                        return count;
                }
                
                /// <summary>
                /// Returns true, if the input buffer is empty.
                /// You should then call setInput(). 
                /// NOTE: This method also returns true when the stream is finished.
                /// </summary>
                public bool IsNeedingInput {
                        get {
                                return input.IsNeedingInput;
                        }
                }
                
                /// <summary>
                /// Returns true, if a preset dictionary is needed to inflate the input.
                /// </summary>
                public bool IsNeedingDictionary {
                        get {
                                return mode == DECODE_DICT && neededBits == 0;
                        }
                }
                
                /// <summary>
                /// Returns true, if the inflater has finished.  This means, that no
                /// input is needed and no output can be produced.
                /// </summary>
                public bool IsFinished {
                        get {
                                return mode == FINISHED && outputWindow.GetAvailable() == 0;
                        }
                }
                
                /// <summary>
                /// Gets the adler checksum.  This is either the checksum of all
                /// uncompressed bytes returned by inflate(), or if needsDictionary()
                /// returns true (and thus no output was yet produced) this is the
                /// adler checksum of the expected dictionary.
                /// </summary>
                /// <returns>
                /// the adler checksum.
                /// </returns>
                public int Adler {
                        get {
                                return IsNeedingDictionary ? readAdler : (int) adler.Value;
                        }
                }
                
                /// <summary>
                /// Gets the total number of output bytes returned by inflate().
                /// </summary>
                /// <returns>
                /// the total number of output bytes.
                /// </returns>
                public int TotalOut {
                        get {
                                return totalOut;
                        }
                }
                
                /// <summary>
                /// Gets the total number of processed compressed input bytes.
                /// </summary>
                /// <returns>
                /// the total number of bytes of processed input bytes.
                /// </returns>
                public int TotalIn {
                        get {
                                return totalIn - RemainingInput;
                        }
                }
                
                /// <summary>
                /// Gets the number of unprocessed input.  Useful, if the end of the
                /// stream is reached and you want to further process the bytes after
                /// the deflate stream.
                /// </summary>
                /// <returns>
                /// the number of bytes of the input which were not processed.
                /// </returns>
                public int RemainingInput {
                        get {
                                return input.AvailableBytes;
                        }
                }
        }
}

namespace NZlib.Compression {
        
        public class InflaterDynHeader
        {
                private const int LNUM   = 0;
                private const int DNUM   = 1;
                private const int BLNUM  = 2;
                private const int BLLENS = 3;
                private const int LLENS  = 4;
                private const int DLENS  = 5;
                private const int LREPS  = 6;
                private const int DREPS  = 7;
                private const int FINISH = 8;
                
                private byte[] blLens;
                private byte[] litlenLens;
                private byte[] distLens;
                
                private InflaterHuffmanTree blTree;
                
                private int mode;
                private int lnum, dnum, blnum;
                private int repBits;
                private byte repeatedLen;
                private int ptr;
                
                private static int[] BL_ORDER = { 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15 };
                
                public InflaterDynHeader()
                {
                }
                
                public bool Decode(StreamManipulator input)
                {
                        decode_loop:
                        for (;;) {
                                switch (mode) {
                                        case LNUM:
                                                lnum = input.PeekBits(5);
                                                if (lnum < 0) {
                                                        return false;
                                                }
                                                lnum += 257;
                                                input.DropBits(5);
                                                litlenLens = new byte[lnum];
                                                //          System.err.println("LNUM: "+lnum);
                                                mode = DNUM;
                                                goto case DNUM;/* fall through */
                                        case DNUM:
                                                dnum = input.PeekBits(5);
                                                if (dnum < 0) {
                                                        return false;
                                                }
                                                dnum++;
                                                input.DropBits(5);
                                                distLens = new byte[dnum];
                                                //          System.err.println("DNUM: "+dnum);
                                                mode = BLNUM;
                                                goto case BLNUM;/* fall through */
                                        case BLNUM:
                                                blnum = input.PeekBits(4);
                                                if (blnum < 0) {
                                                        return false;
                                                }
                                                blnum += 4;
                                                input.DropBits(4);
                                                blLens = new byte[19];
                                                ptr = 0;
                                                //          System.err.println("BLNUM: "+blnum);
                                                mode = BLLENS;
                                                goto case BLLENS;/* fall through */
                                        case BLLENS:
                                                while (ptr < blnum) {
                                                        int len = input.PeekBits(3);
                                                        if (len < 0) {
                                                                return false;
                                                        }
                                                        input.DropBits(3);
                                                        //              System.err.println("blLens["+BL_ORDER[ptr]+"]: "+len);
                                                        blLens[BL_ORDER[ptr]] = (byte) len;
                                                        ptr++;
                                                }
                                                blTree = new InflaterHuffmanTree(blLens);
                                                blLens = null;
                                                ptr = 0;
                                                mode = LLENS;
                                                goto case LLENS;/* fall through */
                                        case LLENS:
                                                while (ptr < lnum) {
                                                        int symbol = blTree.GetSymbol(input);
                                                        if (symbol < 0) {
                                                                return false;
                                                        }
                                                        switch (symbol) {
                                                                default:
                                                                        //                  System.err.println("litlenLens["+ptr+"]: "+symbol);
                                                                        litlenLens[ptr++] = (byte) symbol;
                                                                        break;
                                                                case 16: /* repeat last len 3-6 times */
                                                                        if (ptr == 0) {
                                                                                throw new Exception("Repeating, but no prev len");
                                                                        }
                                                                        
                                                                        //                  System.err.println("litlenLens["+ptr+"]: repeat");
                                                                        repeatedLen = litlenLens[ptr-1];
                                                                        repBits = 2;
                                                                        for (int i = 3; i-- > 0; ) {
                                                                                if (ptr >= lnum) {
                                                                                        throw new Exception();
                                                                                }
                                                                                litlenLens[ptr++] = repeatedLen;
                                                                        }
                                                                        mode = LREPS;
                                                                        goto decode_loop;
                                                                case 17: /* repeat zero 3-10 times */
                                                                        //                  System.err.println("litlenLens["+ptr+"]: zero repeat");
                                                                        repeatedLen = 0;
                                                                        repBits = 3;
                                                                        for (int i = 3; i-- > 0; ) {
                                                                                if (ptr >= lnum) {
                                                                                        throw new Exception();
                                                                                }
                                                                                litlenLens[ptr++] = repeatedLen;
                                                                        }
                                                                        mode = LREPS;
                                                                        goto decode_loop;
                                                                case 18: /* repeat zero 11-138 times */
                                                                        //                  System.err.println("litlenLens["+ptr+"]: zero repeat");
                                                                        repeatedLen = 0;
                                                                        repBits = 7;
                                                                        for (int i = 11; i-- > 0; ) {
                                                                                if (ptr >= lnum) {
                                                                                        throw new Exception();
                                                                                }
                                                                                litlenLens[ptr++] = repeatedLen;
                                                                        }
                                                                        mode = LREPS;
                                                                        goto decode_loop;
                                                        }
                                                }
                                                ptr = 0;
                                                mode = DLENS;
                                                goto case DLENS;/* fall through */
                                                case DLENS:
                                                        while (ptr < dnum) {
                                                                int symbol = blTree.GetSymbol(input);
                                                                if (symbol < 0) {
                                                                        return false;
                                                                }
                                                                switch (symbol) {
                                                                        default:
                                                                                distLens[ptr++] = (byte) symbol;
                                                                                //                  System.err.println("distLens["+ptr+"]: "+symbol);
                                                                                break;
                                                                        case 16: /* repeat last len 3-6 times */
                                                                                if (ptr == 0) {
                                                                                        throw new Exception("Repeating, but no prev len");
                                                                                }
                                                                                //                  System.err.println("distLens["+ptr+"]: repeat");
                                                                                repeatedLen = distLens[ptr-1];
                                                                                repBits = 2;
                                                                                for (int i = 3; i-- > 0; ) {
                                                                                        if (ptr >= dnum) {
                                                                                                throw new Exception();
                                                                                        }
                                                                                        distLens[ptr++] = repeatedLen;
                                                                                }
                                                                                mode = DREPS;
                                                                                goto decode_loop;
                                                                        case 17: /* repeat zero 3-10 times */
                                                                                //                  System.err.println("distLens["+ptr+"]: repeat zero");
                                                                                repeatedLen = 0;
                                                                                repBits = 3;
                                                                                for (int i = 3; i-- > 0; ) {
                                                                                        if (ptr >= dnum) {
                                                                                                throw new Exception();
                                                                                        }
                                                                                        distLens[ptr++] = repeatedLen;
                                                                                }
                                                                                mode = DREPS;
                                                                                goto decode_loop;
                                                                        case 18: /* repeat zero 11-138 times */
                                                                                //                  System.err.println("distLens["+ptr+"]: repeat zero");
                                                                                repeatedLen = 0;
                                                                                repBits = 7;
                                                                                for (int i = 11; i-- > 0; ) {
                                                                                        if (ptr >= dnum) {
                                                                                                throw new Exception();
                                                                                        }
                                                                                        distLens[ptr++] = repeatedLen;
                                                                                }
                                                                                mode = DREPS;
                                                                                goto decode_loop;
                                                                }
                                                        }
                                                        mode = FINISH;
                                                return true;
                                        case LREPS:
                                                {
                                                        int count = input.PeekBits(repBits);
                                                        if (count < 0) {
                                                                return false;
                                                        }
                                                        input.DropBits(repBits);
                                                        //            System.err.println("litlenLens repeat: "+repBits);
                                                        while (count-- > 0) {
                                                                if (ptr >= lnum) {
                                                                        throw new Exception();
                                                                }
                                                                litlenLens[ptr++] = repeatedLen;
                                                        }
                                                }
                                                mode = LLENS;
                                                goto decode_loop;
                                        case DREPS:
                                                {
                                                        int count = input.PeekBits(repBits);
                                                        if (count < 0) {
                                                                return false;
                                                        }
                                                        input.DropBits(repBits);
                                                        while (count-- > 0) {
                                                                if (ptr >= dnum) {
                                                                        throw new Exception();
                                                                }
                                                                distLens[ptr++] = repeatedLen;
                                                        }
                                                }
                                                mode = DLENS;
                                                goto decode_loop;
                                }
                        }
                }
                
                public InflaterHuffmanTree BuildLitLenTree()
                {
                        return new InflaterHuffmanTree(litlenLens);
                }
                
                public InflaterHuffmanTree BuildDistTree()
                {
                        return new InflaterHuffmanTree(distLens);
                }
        }
}

namespace NZlib.Compression {
        
        public class InflaterHuffmanTree 
        {
                private static int MAX_BITLEN = 15;
                private short[] tree;
                
                public static InflaterHuffmanTree defLitLenTree, defDistTree;
                
                static InflaterHuffmanTree()
                {
                        try {
                                byte[] codeLengths = new byte[288];
                                int i = 0;
                                while (i < 144) {
                                        codeLengths[i++] = 8;
                                }
                                while (i < 256) {
                                        codeLengths[i++] = 9;
                                }
                                while (i < 280) {
                                        codeLengths[i++] = 7;
                                }
                                while (i < 288) {
                                        codeLengths[i++] = 8;
                                }
                                defLitLenTree = new InflaterHuffmanTree(codeLengths);
                                
                                codeLengths = new byte[32];
                                i = 0;
                                while (i < 32) {
                                        codeLengths[i++] = 5;
                                }
                                defDistTree = new InflaterHuffmanTree(codeLengths);
                        } catch (Exception) {
                                throw new ApplicationException("InflaterHuffmanTree: static tree length illegal");
                        }
                }
                
                /// <summary>
                /// Constructs a Huffman tree from the array of code lengths.
                /// </summary>
                /// <param name = "codeLengths">
                /// the array of code lengths
                /// </param>
                public InflaterHuffmanTree(byte[] codeLengths)
                {
                        BuildTree(codeLengths);
                }
                
                private void BuildTree(byte[] codeLengths)
                {
                        int[] blCount  = new int[MAX_BITLEN + 1];
                        int[] nextCode = new int[MAX_BITLEN + 1];
                        
                        for (int i = 0; i < codeLengths.Length; i++) {
                                int bits = codeLengths[i];
                                if (bits > 0)
                                        blCount[bits]++;
                        }
                        
                        int code = 0;
                        int treeSize = 512;
                        for (int bits = 1; bits <= MAX_BITLEN; bits++) {
                                nextCode[bits] = code;
                                code += blCount[bits] << (16 - bits);
                                if (bits >= 10) {
                                        /* We need an extra table for bit lengths >= 10. */
                                        int start = nextCode[bits] & 0x1ff80;
                                        int end   = code & 0x1ff80;
                                        treeSize += (end - start) >> (16 - bits);
                                }
                        }
                        if (code != 65536) {
                                throw new Exception("Code lengths don't add up properly.");
                        }
                        /* Now create and fill the extra tables from longest to shortest
                        * bit len.  This way the sub trees will be aligned.
                        */
                        tree = new short[treeSize];
                        int treePtr = 512;
                        for (int bits = MAX_BITLEN; bits >= 10; bits--) {
                                int end   = code & 0x1ff80;
                                code -= blCount[bits] << (16 - bits);
                                int start = code & 0x1ff80;
                                for (int i = start; i < end; i += 1 << 7) {
                                        tree[DeflaterHuffman.BitReverse(i)] = (short) ((-treePtr << 4) | bits);
                                        treePtr += 1 << (bits-9);
                                }
                        }
                        
                        for (int i = 0; i < codeLengths.Length; i++) {
                                int bits = codeLengths[i];
                                if (bits == 0) {
                                        continue;
                                }
                                code = nextCode[bits];
                                int revcode = DeflaterHuffman.BitReverse(code);
                                if (bits <= 9) {
                                        do {
                                                tree[revcode] = (short) ((i << 4) | bits);
                                                revcode += 1 << bits;
                                        } while (revcode < 512);
                                } else {
                                        int subTree = tree[revcode & 511];
                                        int treeLen = 1 << (subTree & 15);
                                        subTree = -(subTree >> 4);
                                        do {
                                                tree[subTree | (revcode >> 9)] = (short) ((i << 4) | bits);
                                                revcode += 1 << bits;
                                        } while (revcode < treeLen);
                                }
                                nextCode[bits] = code + (1 << (16 - bits));
                        }
                        
                }
                
                /// <summary>
                /// Reads the next symbol from input.  The symbol is encoded using the
                /// huffman tree.
                /// </summary>
                /// <param name="input">
                /// input the input source.
                /// </param>
                /// <returns>
                /// the next symbol, or -1 if not enough input is available.
                /// </returns>
                public int GetSymbol(StreamManipulator input)
                {
                        int lookahead, symbol;
                        if ((lookahead = input.PeekBits(9)) >= 0) {
                                if ((symbol = tree[lookahead]) >= 0) {
                                        input.DropBits(symbol & 15);
                                        return symbol >> 4;
                                }
                                int subtree = -(symbol >> 4);
                                int bitlen = symbol & 15;
                                if ((lookahead = input.PeekBits(bitlen)) >= 0) {
                                        symbol = tree[subtree | (lookahead >> 9)];
                                        input.DropBits(symbol & 15);
                                        return symbol >> 4;
                                } else {
                                        int bits = input.AvailableBits;
                                        lookahead = input.PeekBits(bits);
                                        symbol = tree[subtree | (lookahead >> 9)];
                                        if ((symbol & 15) <= bits) {
                                                input.DropBits(symbol & 15);
                                                return symbol >> 4;
                                        } else {
                                                return -1;
                                        }
                                }
                        } else {
                                int bits = input.AvailableBits;
                                lookahead = input.PeekBits(bits);
                                symbol = tree[lookahead];
                                if (symbol >= 0 && (symbol & 15) <= bits) {
                                        input.DropBits(symbol & 15);
                                        return symbol >> 4;
                                } else {
                                        return -1;
                                }
                        }
                }
        }
}

namespace NZlib.Compression {
        
        /// <summary>
        /// This class is general purpose class for writing data to a buffer.
        /// 
        /// It allows you to write bits as well as bytes
        /// Based on DeflaterPending.java
        /// 
        /// author of the original java version : Jochen Hoenicke
        /// </summary>
        public class PendingBuffer
        {
                protected byte[] buf;
                int    start;
                int    end;
                
                uint    bits;
                int    bitCount;
                
                public PendingBuffer() : this( 4096 )
                {
                        
                }
                
                public PendingBuffer(int bufsize)
                {
                        buf = new byte[bufsize];
                }
                
                public void Reset() 
                {
                        start = end = bitCount = 0;
                }
                
                public void WriteByte(int b)
                {
                        if (DeflaterConstants.DEBUGGING && start != 0)
                                throw new Exception();
                        buf[end++] = (byte) b;
                }
                
                public void WriteShort(int s)
                {
                        if (DeflaterConstants.DEBUGGING && start != 0) {
                                throw new Exception();
                        }
                        buf[end++] = (byte) s;
                        buf[end++] = (byte) (s >> 8);
                }
                
                public void WriteInt(int s)
                {
                        if (DeflaterConstants.DEBUGGING && start != 0) {
                                throw new Exception();
                        }
                        buf[end++] = (byte) s;
                        buf[end++] = (byte) (s >> 8);
                        buf[end++] = (byte) (s >> 16);
                        buf[end++] = (byte) (s >> 24);
                }
                
                public void WriteBlock(byte[] block, int offset, int len)
                {
                        if (DeflaterConstants.DEBUGGING && start != 0) {
                                throw new Exception();
                        }
                        System.Array.Copy(block, offset, buf, end, len);
                        end += len;
                }
                
                public int BitCount {
                        get {
                                return bitCount;
                        }
                }
                
                public void AlignToByte() 
                {
                        if (DeflaterConstants.DEBUGGING && start != 0) {
                                throw new Exception();
                        }
                        if (bitCount > 0) {
                                buf[end++] = (byte) bits;
                                if (bitCount > 8) {
                                        buf[end++] = (byte) (bits >> 8);
                                }
                        }
                        bits = 0;
                        bitCount = 0;
                }
                
                public void WriteBits(int b, int count)
                {
                        if (DeflaterConstants.DEBUGGING && start != 0) {
                                throw new Exception();
                        }
//                      if (DeflaterConstants.DEBUGGING) {
//                              Console.WriteLine("writeBits("+b+","+count+")");
//                      }
                        bits |= (uint)(b << bitCount);
                        bitCount += count;
                        if (bitCount >= 16) {
                                buf[end++] = (byte) bits;
                                buf[end++] = (byte) (bits >> 8);
                                bits >>= 16;
                                bitCount -= 16;
                        }
                }
                
                public void WriteShortMSB(int s) 
                {
                        if (DeflaterConstants.DEBUGGING && start != 0) {
                                throw new Exception();
                        }
                        buf[end++] = (byte) (s >> 8);
                        buf[end++] = (byte) s;
                }
                
                public bool IsFlushed {
                        get {
                                return end == 0;
                        }
                }
                
                /// <summary>
                /// Flushes the pending buffer into the given output array.  If the
                /// output array is to small, only a partial flush is done.
                /// </summary>
                /// <param name="output">
                /// the output array;
                /// </param>
                /// <param name="offset">
                /// the offset into output array;
                /// </param>
                /// <param name="length">               
                /// length the maximum number of bytes to store;
                /// </param>
                /// <exception name="ArgumentOutOfRangeException">
                /// IndexOutOfBoundsException if offset or length are invalid.
                /// </exception>
                public int Flush(byte[] output, int offset, int length) 
                {
                        if (bitCount >= 8) {
                                buf[end++] = (byte) bits;
                                bits >>= 8;
                                bitCount -= 8;
                        }
                        if (length > end - start) {
                                length = end - start;
                                System.Array.Copy(buf, start, output, offset, length);
                                start = 0;
                                end = 0;
                        } else {
                                System.Array.Copy(buf, start, output, offset, length);
                                start += length;
                        }
                        return length;
                }
                
                public byte[] ToByteArray()
                {
                        byte[] ret = new byte[ end - start ];
                        System.Array.Copy(buf, start, ret, 0, ret.Length);
                        start = 0;
                        end = 0;
                        return ret;
                }
        }
}       

namespace NZlib.Checksums {
        
        /// <summary>
        /// Computes Adler32 checksum for a stream of data. An Adler32
        /// checksum is not as reliable as a CRC32 checksum, but a lot faster to
        /// compute.
        /// 
        /// The specification for Adler32 may be found in RFC 1950.
        /// ZLIB Compressed Data Format Specification version 3.3)
        /// 
        /// 
        /// From that document:
        /// 
        ///      "ADLER32 (Adler-32 checksum)
        ///       This contains a checksum value of the uncompressed data
        ///       (excluding any dictionary data) computed according to Adler-32
        ///       algorithm. This algorithm is a 32-bit extension and improvement
        ///       of the Fletcher algorithm, used in the ITU-T X.224 / ISO 8073
        ///       standard.
        /// 
        ///       Adler-32 is composed of two sums accumulated per byte: s1 is
        ///       the sum of all bytes, s2 is the sum of all s1 values. Both sums
        ///       are done modulo 65521. s1 is initialized to 1, s2 to zero.  The
        ///       Adler-32 checksum is stored as s2*65536 + s1 in most-
        ///       significant-byte first (network) order."
        /// 
        ///  "8.2. The Adler-32 algorithm
        /// 
        ///    The Adler-32 algorithm is much faster than the CRC32 algorithm yet
        ///    still provides an extremely low probability of undetected errors.
        /// 
        ///    The modulo on unsigned long accumulators can be delayed for 5552
        ///    bytes, so the modulo operation time is negligible.  If the bytes
        ///    are a, b, c, the second sum is 3a + 2b + c + 3, and so is position
        ///    and order sensitive, unlike the first sum, which is just a
        ///    checksum.  That 65521 is prime is important to avoid a possible
        ///    large class of two-byte errors that leave the check unchanged.
        ///    (The Fletcher checksum uses 255, which is not prime and which also
        ///    makes the Fletcher check insensitive to single byte changes 0 -
        ///    255.)
        /// 
        ///    The sum s1 is initialized to 1 instead of zero to make the length
        ///    of the sequence part of s2, so that the length does not have to be
        ///    checked separately. (Any sequence of zeroes has a Fletcher
        ///    checksum of zero.)"
        /// </summary>
        /// <see cref="NZlib.Streams.InflaterInputStream"/>
        /// <see cref="NZlib.Streams.DeflaterOutputStream"/>
        public sealed class Adler32 : IChecksum
        {
                /// <summary>
                /// largest prime smaller than 65536
                /// </summary>
                readonly static uint BASE = 65521;
                
                uint checksum;
                
                /// <summary>
                /// Returns the Adler32 data checksum computed so far.
                /// </summary>
                public long Value {
                        get {
                                return (long) checksum & 0xFFFFFFFFL;
                        }
                }
                
                /// <summary>
                /// Creates a new instance of the <code>Adler32</code> class.
                /// The checksum starts off with a value of 1.
                /// </summary>
                public Adler32()
                {
                        Reset();
                }
                
                /// <summary>
                /// Resets the Adler32 checksum to the initial value.
                /// </summary>
                public void Reset()
                {
                        checksum = 1; //Initialize to 1
                }
                
                /// <summary>
                /// Updates the checksum with the byte b.
                /// </summary>
                /// <param name="bval">
                /// the data value to add. The high byte of the int is ignored.
                /// </param>
                public void Update(int bval)
                {
                        //We could make a length 1 byte array and call update again, but I
                        //would rather not have that overhead
                        uint s1 = checksum & 0xFFFF;
                        uint s2 = checksum >> 16;
                        
                        s1 = (s1 + ((uint)bval & 0xFF)) % BASE;
                        s2 = (s1 + s2) % BASE;
                        
                        checksum = (s2 << 16) + s1;
                }
                
                /// <summary>
                /// Updates the checksum with the bytes taken from the array.
                /// </summary>
                /// <param name="buffer">
                /// buffer an array of bytes
                /// </param>
                public void Update(byte[] buffer)
                {
                        Update(buffer, 0, buffer.Length);
                }
                
                /// <summary>
                /// Updates the checksum with the bytes taken from the array.
                /// </summary>
                /// <param name="buf">
                /// an array of bytes
                /// </param>
                /// <param name="off">
                /// the start of the data used for this update
                /// </param>
                /// <param name="len">
                /// the number of bytes to use for this update
                /// </param>
                public void Update(byte[] buf, int off, int len)
                {
                        if (buf == null) {
                                throw new ArgumentNullException("buf");
                        }
                        
                        if (off < 0 || len < 0 || off + len > buf.Length) {
                                throw new ArgumentOutOfRangeException();
                        }
                        
                        //(By Per Bothner)
                        uint s1 = checksum & 0xFFFF;
                        uint s2 = checksum >> 16;
                        
                        while (len > 0) {
                                // We can defer the modulo operation:
                                // s1 maximally grows from 65521 to 65521 + 255 * 3800
                                // s2 maximally grows by 3800 * median(s1) = 2090079800 < 2^31
                                int n = 3800;
                                if (n > len) {
                                        n = len;
                                }
                                len -= n;
                                while (--n >= 0) {
                                        s1 = s1 + (uint)(buf[off++] & 0xFF);
                                        s2 = s2 + s1;
                                }
                                s1 %= BASE;
                                s2 %= BASE;
                        }
                        
                        checksum = (s2 << 16) | s1;
                }
        }
}

namespace NZlib.Checksums {
        
        /// <summary>
        /// Generate a table for a byte-wise 32-bit CRC calculation on the polynomial:
        /// x^32+x^26+x^23+x^22+x^16+x^12+x^11+x^10+x^8+x^7+x^5+x^4+x^2+x+1.
        ///
        /// Polynomials over GF(2) are represented in binary, one bit per coefficient,
        /// with the lowest powers in the most significant bit.  Then adding polynomials
        /// is just exclusive-or, and multiplying a polynomial by x is a right shift by
        /// one.  If we call the above polynomial p, and represent a byte as the
        /// polynomial q, also with the lowest power in the most significant bit (so the
        /// byte 0xb1 is the polynomial x^7+x^3+x+1), then the CRC is (q*x^32) mod p,
        /// where a mod b means the remainder after dividing a by b.
        ///
        /// This calculation is done using the shift-register method of multiplying and
        /// taking the remainder.  The register is initialized to zero, and for each
        /// incoming bit, x^32 is added mod p to the register if the bit is a one (where
        /// x^32 mod p is p+x^32 = x^26+...+1), and the register is multiplied mod p by
        /// x (which is shifting right by one and adding x^32 mod p if the bit shifted
        /// out is a one).  We start with the highest power (least significant bit) of
        /// q and repeat for all eight bits of q.
        ///
        /// The table is simply the CRC of all possible eight bit values.  This is all
        /// the information needed to generate CRC's on data a byte at a time for all
        /// combinations of CRC register values and incoming bytes.
        /// </summary>
        public sealed class Crc32 : IChecksum
        {
                readonly static uint CrcSeed = 0xFFFFFFFF;
                
                readonly static uint[] CrcTable = new uint[] {
                        0x00000000, 0x77073096, 0xEE0E612C, 0x990951BA, 0x076DC419,
                        0x706AF48F, 0xE963A535, 0x9E6495A3, 0x0EDB8832, 0x79DCB8A4,
                        0xE0D5E91E, 0x97D2D988, 0x09B64C2B, 0x7EB17CBD, 0xE7B82D07,
                        0x90BF1D91, 0x1DB71064, 0x6AB020F2, 0xF3B97148, 0x84BE41DE,
                        0x1ADAD47D, 0x6DDDE4EB, 0xF4D4B551, 0x83D385C7, 0x136C9856,
                        0x646BA8C0, 0xFD62F97A, 0x8A65C9EC, 0x14015C4F, 0x63066CD9,
                        0xFA0F3D63, 0x8D080DF5, 0x3B6E20C8, 0x4C69105E, 0xD56041E4,
                        0xA2677172, 0x3C03E4D1, 0x4B04D447, 0xD20D85FD, 0xA50AB56B,
                        0x35B5A8FA, 0x42B2986C, 0xDBBBC9D6, 0xACBCF940, 0x32D86CE3,
                        0x45DF5C75, 0xDCD60DCF, 0xABD13D59, 0x26D930AC, 0x51DE003A,
                        0xC8D75180, 0xBFD06116, 0x21B4F4B5, 0x56B3C423, 0xCFBA9599,
                        0xB8BDA50F, 0x2802B89E, 0x5F058808, 0xC60CD9B2, 0xB10BE924,
                        0x2F6F7C87, 0x58684C11, 0xC1611DAB, 0xB6662D3D, 0x76DC4190,
                        0x01DB7106, 0x98D220BC, 0xEFD5102A, 0x71B18589, 0x06B6B51F,
                        0x9FBFE4A5, 0xE8B8D433, 0x7807C9A2, 0x0F00F934, 0x9609A88E,
                        0xE10E9818, 0x7F6A0DBB, 0x086D3D2D, 0x91646C97, 0xE6635C01,
                        0x6B6B51F4, 0x1C6C6162, 0x856530D8, 0xF262004E, 0x6C0695ED,
                        0x1B01A57B, 0x8208F4C1, 0xF50FC457, 0x65B0D9C6, 0x12B7E950,
                        0x8BBEB8EA, 0xFCB9887C, 0x62DD1DDF, 0x15DA2D49, 0x8CD37CF3,
                        0xFBD44C65, 0x4DB26158, 0x3AB551CE, 0xA3BC0074, 0xD4BB30E2,
                        0x4ADFA541, 0x3DD895D7, 0xA4D1C46D, 0xD3D6F4FB, 0x4369E96A,
                        0x346ED9FC, 0xAD678846, 0xDA60B8D0, 0x44042D73, 0x33031DE5,
                        0xAA0A4C5F, 0xDD0D7CC9, 0x5005713C, 0x270241AA, 0xBE0B1010,
                        0xC90C2086, 0x5768B525, 0x206F85B3, 0xB966D409, 0xCE61E49F,
                        0x5EDEF90E, 0x29D9C998, 0xB0D09822, 0xC7D7A8B4, 0x59B33D17,
                        0x2EB40D81, 0xB7BD5C3B, 0xC0BA6CAD, 0xEDB88320, 0x9ABFB3B6,
                        0x03B6E20C, 0x74B1D29A, 0xEAD54739, 0x9DD277AF, 0x04DB2615,
                        0x73DC1683, 0xE3630B12, 0x94643B84, 0x0D6D6A3E, 0x7A6A5AA8,
                        0xE40ECF0B, 0x9309FF9D, 0x0A00AE27, 0x7D079EB1, 0xF00F9344, 
                        0x8708A3D2, 0x1E01F268, 0x6906C2FE, 0xF762575D, 0x806567CB,
                        0x196C3671, 0x6E6B06E7, 0xFED41B76, 0x89D32BE0, 0x10DA7A5A,
                        0x67DD4ACC, 0xF9B9DF6F, 0x8EBEEFF9, 0x17B7BE43, 0x60B08ED5,
                        0xD6D6A3E8, 0xA1D1937E, 0x38D8C2C4, 0x4FDFF252, 0xD1BB67F1,
                        0xA6BC5767, 0x3FB506DD, 0x48B2364B, 0xD80D2BDA, 0xAF0A1B4C,
                        0x36034AF6, 0x41047A60, 0xDF60EFC3, 0xA867DF55, 0x316E8EEF,
                        0x4669BE79, 0xCB61B38C, 0xBC66831A, 0x256FD2A0, 0x5268E236,
                        0xCC0C7795, 0xBB0B4703, 0x220216B9, 0x5505262F, 0xC5BA3BBE,
                        0xB2BD0B28, 0x2BB45A92, 0x5CB36A04, 0xC2D7FFA7, 0xB5D0CF31,
                        0x2CD99E8B, 0x5BDEAE1D, 0x9B64C2B0, 0xEC63F226, 0x756AA39C,
                        0x026D930A, 0x9C0906A9, 0xEB0E363F, 0x72076785, 0x05005713,
                        0x95BF4A82, 0xE2B87A14, 0x7BB12BAE, 0x0CB61B38, 0x92D28E9B,
                        0xE5D5BE0D, 0x7CDCEFB7, 0x0BDBDF21, 0x86D3D2D4, 0xF1D4E242,
                        0x68DDB3F8, 0x1FDA836E, 0x81BE16CD, 0xF6B9265B, 0x6FB077E1,
                        0x18B74777, 0x88085AE6, 0xFF0F6A70, 0x66063BCA, 0x11010B5C,
                        0x8F659EFF, 0xF862AE69, 0x616BFFD3, 0x166CCF45, 0xA00AE278,
                        0xD70DD2EE, 0x4E048354, 0x3903B3C2, 0xA7672661, 0xD06016F7,
                        0x4969474D, 0x3E6E77DB, 0xAED16A4A, 0xD9D65ADC, 0x40DF0B66,
                        0x37D83BF0, 0xA9BCAE53, 0xDEBB9EC5, 0x47B2CF7F, 0x30B5FFE9,
                        0xBDBDF21C, 0xCABAC28A, 0x53B39330, 0x24B4A3A6, 0xBAD03605,
                        0xCDD70693, 0x54DE5729, 0x23D967BF, 0xB3667A2E, 0xC4614AB8,
                        0x5D681B02, 0x2A6F2B94, 0xB40BBE37, 0xC30C8EA1, 0x5A05DF1B, 
                        0x2D02EF8D
                };
                
                /// <summary>
                /// The crc data checksum so far.
                /// </summary>
                uint crc = 0;
                
                /// <summary>
                /// Returns the CRC32 data checksum computed so far.
                /// </summary>
                public long Value {
                        get {
                                return (long)crc;
                        }
                }
                
                /// <summary>
                /// Resets the CRC32 data checksum as if no update was ever called.
                /// </summary>
                public void Reset() 
                { 
                        crc = 0; 
                }
                
                /// <summary>
                /// Updates the checksum with the int bval.
                /// </summary>
                /// <param name = "bval">
                /// the byte is taken as the lower 8 bits of bval
                /// </param>
                public void Update(int bval)
                {
                        crc ^= CrcSeed;
                        crc  = CrcTable[(crc ^ bval) & 0xFF] ^ (crc >> 8);
                        crc ^= CrcSeed;
                }
                
                /// <summary>
                /// Updates the checksum with the bytes taken from the array.
                /// </summary>
                /// <param name="buffer">
                /// buffer an array of bytes
                /// </param>
                public void Update(byte[] buffer)
                {
                        Update(buffer, 0, buffer.Length);
                }
                
                /// <summary>
                /// Adds the byte array to the data checksum.
                /// </summary>
                /// <param name = "buf">
                /// the buffer which contains the data
                /// </param>
                /// <param name = "off">
                /// the offset in the buffer where the data starts
                /// </param>
                /// <param name = "len">
                /// the length of the data
                /// </param>
                public void Update(byte[] buf, int off, int len)
                {
                        if (buf == null) {
                                throw new ArgumentNullException("buf");
                        }
                        
                        if (off < 0 || len < 0 || off + len > buf.Length) {
                                throw new ArgumentOutOfRangeException();
                        }
                        
                        crc ^= CrcSeed;
                        
                        while (--len >= 0) {
                                crc = CrcTable[(crc ^ buf[off++]) & 0xFF] ^ (crc >> 8);
                        }
                        
                        crc ^= CrcSeed;
                }
        }
}

namespace NZlib.Checksums {
        
        /// <summary>
        /// Interface to compute a data checksum used by checked input/output streams.
        /// A data checksum can be updated by one byte or with a byte array. After each
        /// update the value of the current checksum can be returned by calling
        /// <code>getValue</code>. The complete checksum object can also be reset
        /// so it can be used again with new data.
        /// </summary>
        public interface IChecksum
        {
                /// <summary>
                /// Returns the data checksum computed so far.
                /// </summary>
                long Value {
                        get;
                }
                
                /// <summary>
                /// Resets the data checksum as if no update was ever called.
                /// </summary>
                void Reset();
                
                /// <summary>
                /// Adds one byte to the data checksum.
                /// </summary>
                /// <param name = "bval">
                /// the data value to add. The high byte of the int is ignored.
                /// </param>
                void Update(int bval);
                
                /// <summary>
                /// Updates the data checksum with the bytes taken from the array.
                /// </summary>
                /// <param name="buffer">
                /// buffer an array of bytes
                /// </param>
                void Update(byte[] buffer);
                
                /// <summary>
                /// Adds the byte array to the data checksum.
                /// </summary>
                /// <param name = "buf">
                /// the buffer which contains the data
                /// </param>
                /// <param name = "off">
                /// the offset in the buffer where the data starts
                /// </param>
                /// <param name = "len">
                /// the length of the data
                /// </param>
                void Update(byte[] buf, int off, int len);
        }
}

namespace NZlib.Streams {
        
        /// <summary>
        /// Contains the output from the Inflation process.
        /// We need to have a window so that we can refer backwards into the output stream
        /// to repeat stuff.
        ///
        /// author of the original java version : John Leuner
        /// </summary>
        public class OutputWindow
        {
                private static int WINDOW_SIZE = 1 << 15;
                private static int WINDOW_MASK = WINDOW_SIZE - 1;
                
                private byte[] window = new byte[WINDOW_SIZE]; //The window is 2^15 bytes
                private int window_end  = 0;
                private int window_filled = 0;
                
                public void Write(int abyte)
                {
                        if (window_filled++ == WINDOW_SIZE) {
                                throw new InvalidOperationException("Window full");
                        }
                        window[window_end++] = (byte) abyte;
                        window_end &= WINDOW_MASK;
                }
                
                
                private void SlowRepeat(int rep_start, int len, int dist)
                {
                        while (len-- > 0) {
                                window[window_end++] = window[rep_start++];
                                window_end &= WINDOW_MASK;
                                rep_start &= WINDOW_MASK;
                        }
                }
                
                public void Repeat(int len, int dist)
                {
                        if ((window_filled += len) > WINDOW_SIZE) {
                                throw new InvalidOperationException("Window full");
                        }
                        
                        int rep_start = (window_end - dist) & WINDOW_MASK;
                        int border = WINDOW_SIZE - len;
                        if (rep_start <= border && window_end < border) {
                                if (len <= dist) {
                                        System.Array.Copy(window, rep_start, window, window_end, len);
                                        window_end += len;
                                }                               else {
                                        /* We have to copy manually, since the repeat pattern overlaps.
                                        */
                                        while (len-- > 0) {
                                                window[window_end++] = window[rep_start++];
                                        }
                                }
                        } else {
                                SlowRepeat(rep_start, len, dist);
                        }
                }
                
                public int CopyStored(StreamManipulator input, int len)
                {
                        len = Math.Min(Math.Min(len, WINDOW_SIZE - window_filled), input.AvailableBytes);
                        int copied;
                        
                        int tailLen = WINDOW_SIZE - window_end;
                        if (len > tailLen) {
                                copied = input.CopyBytes(window, window_end, tailLen);
                                if (copied == tailLen) {
                                        copied += input.CopyBytes(window, 0, len - tailLen);
                                }
                        } else {
                                copied = input.CopyBytes(window, window_end, len);
                        }
                        
                        window_end = (window_end + copied) & WINDOW_MASK;
                        window_filled += copied;
                        return copied;
                }
                
                public void CopyDict(byte[] dict, int offset, int len)
                {
                        if (window_filled > 0) {
                                throw new InvalidOperationException();
                        }
                        
                        if (len > WINDOW_SIZE) {
                                offset += len - WINDOW_SIZE;
                                len = WINDOW_SIZE;
                        }
                        System.Array.Copy(dict, offset, window, 0, len);
                        window_end = len & WINDOW_MASK;
                }
                
                public int GetFreeSpace()
                {
                        return WINDOW_SIZE - window_filled;
                }
                
                public int GetAvailable()
                {
                        return window_filled;
                }
                
                public int CopyOutput(byte[] output, int offset, int len)
                {
                        int copy_end = window_end;
                        if (len > window_filled) {
                                len = window_filled;
                        } else {
                                copy_end = (window_end - window_filled + len) & WINDOW_MASK;
                        }
                        
                        int copied = len;
                        int tailLen = len - copy_end;
                        
                        if (tailLen > 0) {
                                System.Array.Copy(window, WINDOW_SIZE - tailLen,
                                                  output, offset, tailLen);
                                offset += tailLen;
                                len = copy_end;
                        }
                        System.Array.Copy(window, copy_end - len, output, offset, len);
                        window_filled -= copied;
                        if (window_filled < 0) {
                                throw new InvalidOperationException();
                        }
                        return copied;
                }
                
                public void Reset()
                {
                        window_filled = window_end = 0;
                }
        }
}

namespace NZlib.Streams {
        
        /// <summary>
        /// This class allows us to retrieve a specified amount of bits from
        /// the input buffer, as well as copy big byte blocks.
        ///
        /// It uses an int buffer to store up to 31 bits for direct
        /// manipulation.  This guarantees that we can get at least 16 bits,
        /// but we only need at most 15, so this is all safe.
        ///
        /// There are some optimizations in this class, for example, you must
        /// never peek more then 8 bits more than needed, and you must first
        /// peek bits before you may drop them.  This is not a general purpose
        /// class but optimized for the behaviour of the Inflater.
        ///
        /// authors of the original java version : John Leuner, Jochen Hoenicke
        /// </summary>
        public class StreamManipulator
        {
                private byte[] window;
                private int window_start = 0;
                private int window_end = 0;
                
                private uint buffer = 0;
                private int bits_in_buffer = 0;
                
                /// <summary>
                /// Get the next n bits but don't increase input pointer.  n must be
                /// less or equal 16 and if you if this call succeeds, you must drop
                /// at least n-8 bits in the next call.
                /// </summary>
                /// <returns>
                /// the value of the bits, or -1 if not enough bits available.  */
                /// </returns>
                public int PeekBits(int n)
                {
                        if (bits_in_buffer < n) {
                                if (window_start == window_end) {
                                        return -1;
                                }
                                buffer |= (uint)((window[window_start++] & 0xff |
                                                 (window[window_start++] & 0xff) << 8) << bits_in_buffer);
                                bits_in_buffer += 16;
                        }
                        return (int)(buffer & ((1 << n) - 1));
                }
                
                /// <summary>
                /// Drops the next n bits from the input.  You should have called peekBits
                /// with a bigger or equal n before, to make sure that enough bits are in
                /// the bit buffer.
                /// </summary>
                public void DropBits(int n)
                {
                        buffer >>= n;
                        bits_in_buffer -= n;
                }
                
                /// <summary>
                /// Gets the next n bits and increases input pointer.  This is equivalent
                /// to peekBits followed by dropBits, except for correct error handling.
                /// </summary>
                /// <returns>
                /// the value of the bits, or -1 if not enough bits available.
                /// </returns>
                public int GetBits(int n)
                {
                        int bits = PeekBits(n);
                        if (bits >= 0) {
                                DropBits(n);
                        }
                        return bits;
                }
                
                /// <summary>
                /// Gets the number of bits available in the bit buffer.  This must be
                /// only called when a previous peekBits() returned -1.
                /// </summary>
                /// <returns>
                /// the number of bits available.
                /// </returns>
                public int AvailableBits {
                        get {
                                return bits_in_buffer;
                        }
                }
                
                /// <summary>
                /// Gets the number of bytes available.
                /// </summary>
                /// <returns>
                /// the number of bytes available.
                /// </returns>
                public int AvailableBytes {
                        get {
                                return window_end - window_start + (bits_in_buffer >> 3);
                        }
                }
                
                /// <summary>
                /// Skips to the next byte boundary.
                /// </summary>
                public void SkipToByteBoundary()
                {
                        buffer >>= (bits_in_buffer & 7);
                        bits_in_buffer &= ~7;
                }
                
                public bool IsNeedingInput {
                        get {
                                return window_start == window_end;
                        }
                }
                
                /// <summary>
                /// Copies length bytes from input buffer to output buffer starting
                /// at output[offset].  You have to make sure, that the buffer is
                /// byte aligned.  If not enough bytes are available, copies fewer
                /// bytes.
                /// </summary>
                /// <param name="output">
                /// the buffer.
                /// </param>
                /// <param name="offset">
                /// the offset in the buffer.
                /// </param>
                /// <param name="length">
                /// the length to copy, 0 is allowed.
                /// </param>
                /// <returns>
                /// the number of bytes copied, 0 if no byte is available.
                /// </returns>
                public int CopyBytes(byte[] output, int offset, int length)
                {
                        if (length < 0) {
                                throw new ArgumentOutOfRangeException("length negative");
                        }
                        if ((bits_in_buffer & 7) != 0)   {
                                /* bits_in_buffer may only be 0 or 8 */
                                throw new InvalidOperationException("Bit buffer is not aligned!");
                        }
                        
                        int count = 0;
                        while (bits_in_buffer > 0 && length > 0) {
                                output[offset++] = (byte) buffer;
                                buffer >>= 8;
                                bits_in_buffer -= 8;
                                length--;
                                count++;
                        }
                        if (length == 0) {
                                return count;
                        }
                        
                        int avail = window_end - window_start;
                        if (length > avail) {
                                length = avail;
                        }
                        System.Array.Copy(window, window_start, output, offset, length);
                        window_start += length;
                        
                        if (((window_start - window_end) & 1) != 0) {
                                /* We always want an even number of bytes in input, see peekBits */
                                buffer = (uint)(window[window_start++] & 0xff);
                                bits_in_buffer = 8;
                        }
                        return count + length;
                }
                
                public StreamManipulator()
                {
                }
                
                public void Reset()
                {
                        buffer = (uint)(window_start = window_end = bits_in_buffer = 0);
                }
                
                public void SetInput(byte[] buf, int off, int len)
                {
                        if (window_start < window_end) {
                                throw new InvalidOperationException("Old input was not completely processed");
                        }
                        
                        int end = off + len;
                        
                        /* We want to throw an ArrayIndexOutOfBoundsException early.  The
                        * check is very tricky: it also handles integer wrap around.
                        */
                        if (0 > off || off > end || end > buf.Length) {
                                throw new ArgumentOutOfRangeException();
                        }
                        
                        if ((len & 1) != 0) {
                                /* We always want an even number of bytes in input, see peekBits */
                                buffer |= (uint)((buf[off++] & 0xff) << bits_in_buffer);
                                bits_in_buffer += 8;
                        }
                        
                        window = buf;
                        window_start = off;
                        window_end = end;
                }
        }
}