zDeflate.cs

#region License
/* zlib.h -- interface of the 'zlib' general purpose compression library
  version 1.2.13, October 13th, 2022

  Copyright (C) 1995-2022 Jean-loup Gailly and Mark Adler

  This software is provided 'as-is', without any express or implied
  warranty.  In no event will the authors be held liable for any damages
  arising from the use of this software.

  Permission is granted to anyone to use this software for any purpose,
  including commercial applications, and to alter it and redistribute it
  freely, subject to the following restrictions:

  1. The origin of this software must not be misrepresented; you must not
     claim that you wrote the original software. If you use this software
     in a product, an acknowledgment in the product documentation would be
     appreciated but is not required.
  2. Altered source versions must be plainly marked as such, and must not be
     misrepresented as being the original software.
  3. This notice may not be removed or altered from any source distribution.

  Jean-loup Gailly        Mark Adler
  jloup@gzip.org          madler@alumni.caltech.edu


  The data format used by the zlib library is described by RFCs (Request for
  Comments) 1950 to 1952 in the files http://tools.ietf.org/html/rfc1950
  (zlib format), rfc1951 (deflate format) and rfc1952 (gzip format).
*/
#endregion
using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Reflection.Emit;
using System.Runtime.InteropServices;
using System.Security.Cryptography;
using System.Security.Policy;
using System.Text.RegularExpressions;
using DeflateLib.Internal;

namespace DeflateLib
{
    public class zDeflate : zStream
    {
        #region Delegates

        private delegate block_state CompressFunc(zDeflate z, zFlush flush);

        #endregion

        #region Constants

        /// <summary>
        /// If you use the zlib library in a product, an acknowledgment is welcome
        /// in the documentation of your product.If for some reason you cannot
        /// include such an acknowledgment, I would appreciate that you keep this
        /// copyright string in the executable of your product.
        /// </summary>
        public static readonly string deflate_copyright = "Deflate 1.2.13 Copyright 1995-2022 Jean-loup Gailly and Mark Adler";

        /// <summary>
        /// Number of length codes, not counting the special END_BLOCK code
        /// </summary>
        private const int LENGTH_CODES = 29;

        /// <summary>
        /// Number of literal bytes 0..255
        /// </summary>
        internal const int LITERALS = 256;

        /// <summary>
        /// Number of Literal or Length codes, including the END_BLOCK code
        /// </summary>
        internal const int L_CODES = (LITERALS + 1 + LENGTH_CODES);

        /// <summary>
        /// Number of distance codes
        /// </summary>
        internal const int D_CODES = 30;

        /// <summary>
        /// Number of codes used to transfer the bit lengths
        /// </summary>
        internal const int BL_CODES = 19;

        /// <summary>
        /// Maximum heap size
        /// </summary>
        internal const int HEAP_SIZE = (2 * L_CODES + 1);

        /// <summary>
        /// All codes must not exceed MAX_BITS bits
        /// </summary>
        internal const int MAX_BITS = 15;

        /// <summary>
        /// Size of bit buffer in bi_buf
        /// </summary>
        internal const int Buf_size = 16;

        /// <summary>
        /// Minimum amount of lookahead, except at the end of the input file.
        /// </summary>
        private const int MIN_LOOKAHEAD = zUtil.MAX_MATCH + zUtil.MIN_MATCH + 1;

        /// <summary>
        /// Number of bytes after end of data in window to initialize in order to avoid
        /// memory checker errors from longest match routines
        /// </summary>
        private const int WIN_INIT = zUtil.MAX_MATCH;

        private const int TOO_FAR = 4096;

        /// <summary>
        /// Maximum stored block length in deflate format (not including header).
        /// </summary>
        private const int MAX_STORED = 65535;

        /// <summary>
        /// Table that configures compression level 0 to 9
        /// </summary>
#if FASTEST
        private static readonly Config[] configuration_table = new Config[]
        {
            /*      good lazy nice chain */
            /* 0 */ new Config( 0,   0,   0,    0, deflate_stored), /* store only */
            /* 1 */ new Config( 4,   4,   8,    4, deflate_fast), /* max speed, no lazy matches */
        };
#else
        private static readonly Config[] configuration_table = new Config[]
        {
            /*      good lazy nice chain */
            /* 0 */ new Config( 0,   0,   0,    0, deflate_stored), /* store only */
            /* 1 */ new Config( 4,   4,   8,    4, deflate_fast), /* max speed, no lazy matches */
            /* 2 */ new Config( 4,   5,  16,    8, deflate_fast),
            /* 3 */ new Config( 4,   6,  32,   32, deflate_fast),

            /* 4 */ new Config( 4,   4,  16,   16, deflate_slow), /* lazy matches */
            /* 5 */ new Config( 8,  16,  32,   32, deflate_slow), 
            /* 6 */ new Config( 8,  16, 128,  128, deflate_slow),
            /* 7 */ new Config( 8,  32, 128,  256, deflate_slow),
            /* 8 */ new Config(32, 128, 258, 1024, deflate_slow),
            /* 9 */ new Config(32, 258, 258, 4096, deflate_slow), /* max compression */
        };
#endif

#endregion

        #region Variables

        private DeflateState _state;

#endregion

        #region Init

        public zDeflate(zCOMPRESSION level = zCOMPRESSION.DEFAULT, 
            int method = zConstants.Z_DEFLATED, 
            int windowBits = zConstants.MAX_WBITS, 
            int memLevel = zUtil.DEF_MEM_LEVEL, 
            zSTRATEGY strategy = zSTRATEGY.DEFAULT, 
            string version = zConstants.ZLIB_VERSION)
        {
            var ret = deflateInit2(level, method, windowBits, memLevel, strategy, version);
            if (ret != zRetCode.Z_OK)
            {
                ERR_RETURN(ret);
                throw new Exception(msg);
            }
        }

        private zRetCode deflateInit2(zCOMPRESSION level,
            int method,
            int windowBits,
            int memLevel,
            zSTRATEGY strategy,
            string version)
        {
            int wrap = 1;

            if (version == null || version[0] != zConstants.ZLIB_VERSION[0])
                return zRetCode.Z_VERSION_ERROR;

            msg = null;

#if FASTEST
            if (level != 0) level = zCOMPRESSION.LEVEL_1;
#else
            if (level == zCOMPRESSION.DEFAULT)
                level = zCOMPRESSION.LEVEL_6;
#endif

            if (windowBits < 0) /* suppress zlib wrapper */
            {
                wrap = 0;
                if (windowBits < -15)
                    return zRetCode.Z_STREAM_ERROR;
                windowBits = -windowBits;
            }
#if GZIP
            else if (windowBits > 15)
            {
                wrap = 2;           /* write gzip wrapper instead */
                windowBits -= 16;
            }
#endif

            if (memLevel < 1 || memLevel > zConstants.MAX_MEM_LEVEL ||
                method != zConstants.Z_DEFLATED || windowBits < 8 ||
                windowBits > 15 || level < zCOMPRESSION.NO ||
                level > zCOMPRESSION.BEST || strategy < zSTRATEGY.DEFAULT
                || strategy > zSTRATEGY.FIXED || (windowBits == 8 && wrap != 1))
            {
                throw new ArgumentException("Parameter error");
            }

            if (windowBits == 8) windowBits = 9;  /* until 256-byte window bug fixed */
            _state = new DeflateState();
            _state.strm = this;
            _state.status = DeflateStatus.INIT; /* to pass state test in deflateReset() */

            _state.wrap = wrap;
            _state.gzhead = null;
            _state.w_bits = (uint)windowBits;
            _state.w_size = 1 << windowBits;
            _state.w_mask = _state.w_size - 1;

            _state.hash_bits = memLevel + 7;
            _state.hash_size = 1 << (_state.hash_bits);
            _state.hash_mask = _state.hash_size - 1;
            _state.hash_shift = (int) ((_state.hash_bits + zUtil.MIN_MATCH - 1u) / zUtil.MIN_MATCH);

            _state.window = new byte[_state.w_size * 2];
            _state.prev = new ushort[_state.w_size];
            _state.head = new ushort[_state.hash_size];

            // Zero because nothing written to s->window yet
            _state.high_water = 0;

            // 16K elements by default
            _state.lit_bufsize = 1u << (memLevel + 6);

            /* We overlay pending_buf and sym_buf. This works since the average size
             * for length/distance pairs over any compressed block is assured to be 31
             * bits or less.
             *
             * Analysis: The longest fixed codes are a length code of 8 bits plus 5
             * extra bits, for lengths 131 to 257. The longest fixed distance codes are
             * 5 bits plus 13 extra bits, for distances 16385 to 32768. The longest
             * possible fixed-codes length/distance pair is then 31 bits total.
             *
             * sym_buf starts one-fourth of the way into pending_buf. So there are
             * three bytes in sym_buf for every four bytes in pending_buf. Each symbol
             * in sym_buf is three bytes -- two for the distance and one for the
             * literal/length. As each symbol is consumed, the pointer to the next
             * sym_buf value to read moves forward three bytes. From that symbol, up to
             * 31 bits are written to pending_buf. The closest the written pending_buf
             * bits gets to the next sym_buf symbol to read is just before the last
             * code is written. At that time, 31*(n - 2) bits have been written, just
             * after 24*(n - 2) bits have been consumed from sym_buf. sym_buf starts at
             * 8*n bits into pending_buf. (Note that the symbol buffer fills when n - 1
             * symbols are written.) The closest the writing gets to what is unread is
             * then n + 14 bits. Here n is lit_bufsize, which is 16384 by default, and
             * can range from 128 to 32768.
             *
             * Therefore, at a minimum, there are 142 bits of space between what is
             * written and what is read in the overlain buffers, so the symbols cannot
             * be overwritten by the compressed data. That space is actually 139 bits,
             * due to the three-bit fixed-code block header.
             *
             * That covers the case where either Z_FIXED is specified, forcing fixed
             * codes, or when the use of fixed codes is chosen, because that choice
             * results in a smaller compressed block than dynamic codes. That latter
             * condition then assures that the above analysis also covers all dynamic
             * blocks. A dynamic-code block will only be chosen to be emitted if it has
             * fewer bits than a fixed-code block would for the same set of symbols.
             * Therefore its average symbol length is assured to be less than 31. So
             * the compressed data for a dynamic block also cannot overwrite the
             * symbols from which it is being constructed.
             */

            //Impl detail: Original uses pointers, we use counters into "buffer"
            _state.buffer = new byte[_state.lit_bufsize * 4];
            //_state.pending_buf_size = (uint)_state.buffer.Length;
            //_state.pending_buf = 0;
            _state.sym_buf = _state.lit_bufsize;

            /* We avoid equality with lit_bufsize*3 because of wraparound at 64K
             * on 16 bit machines and because stored blocks are restricted to
             * 64K-1 bytes.
             */
            _state.sym_end = (_state.lit_bufsize - 1u) * 3u;

            _state.level = (int)level;
            _state.strategy = strategy;
            _state.method = (byte)method;

            return deflateReset();
        }

        internal zRetCode deflateReset()
        {
            zRetCode ret = deflateResetKeep();
            if (ret == zRetCode.Z_OK)
                lm_init(_state);
            return ret;
        }

        internal zRetCode deflateResetKeep()
        {
            if (deflateStateCheck())
            {
                return zRetCode.Z_STREAM_ERROR;
            }

            total_in = total_out = 0;
            msg = null;
            data_type = (int) zDataType.UNKNOWN;

            var s = _state;
            s.pending = 0;
            s.pending_out = s.pending_buf;

            if (s.wrap < 0)
            {
                s.wrap -= s.wrap; /* was made negative by deflate(..., Z_FINISH); */
            }
            s.status =
#if GZIP
                s.wrap == 2 ? DeflateStatus.GZIP :
#endif
                DeflateStatus.INIT;
            adler =
#if GZIP
                s.wrap == 2 ? CRC32.Update(0u, null, 0, 0) :
#endif
                Adler32.Compute(0, null, 0, 0);
            s.last_flush = (zFlush) (-2);

            DeflateTrees.tr_init(s);

            return zRetCode.Z_OK;
        }

        private void lm_init(DeflateState s)
        {
            s.window_size = 2 * s.w_size;

            CLEAR_HASH(s);

            /* Set the default configuration parameters:
             */
            s.max_lazy_match = configuration_table[s.level].max_lazy;
            s.good_match = configuration_table[s.level].good_length;
            s.nice_match = configuration_table[s.level].nice_length;
            s.max_chain_length = configuration_table[s.level].max_chain;

            s.strstart = 0;
            s.block_start = 0;
            s.lookahead = 0;
            s.insert = 0;
            s.match_length = s.prev_length = zUtil.MIN_MATCH - 1;
            s.match_available = 0;
            s.ins_h = 0;
        }

        /// <summary>
        /// Check for a valid deflate stream state.
        /// </summary>
        /// <returns>False if all OK</returns>
        private bool deflateStateCheck()
        {
            var s = _state;
            return (s == null || s.strm != this || (s.status != DeflateStatus.INIT &&
                                                s.status != DeflateStatus.GZIP &&
                                                s.status != DeflateStatus.EXTRA &&
                                                s.status != DeflateStatus.NAME &&
                                                s.status != DeflateStatus.COMMENT &&
                                                s.status != DeflateStatus.HCRC &&
                                                s.status != DeflateStatus.BUSY &&
                                                s.status != DeflateStatus.FINISH));
        }

        private static void CLEAR_HASH(DeflateState s)
        {
            for (int c = 0; c < s.head.Length; c++) s.head[c] = 0;
        }

#endregion

        #region Deflate

        public zRetCode Deflate(zFlush flush)
        {
            // Value of flush param for previous deflate call
            zFlush old_flush;

            if (deflateStateCheck() || flush > zFlush.Z_BLOCK || flush < zFlush.Z_NO_FLUSH)
            {
                return zRetCode.Z_STREAM_ERROR;
            }
            var s = _state;

            if (_out == null ||
                (avail_in != 0 && _in == null) ||
                (s.status == DeflateStatus.FINISH && flush != zFlush.Z_FINISH))
            {
                return ERR_RETURN(zRetCode.Z_STREAM_ERROR);
            }
            if (avail_out == 0) return ERR_RETURN(zRetCode.Z_BUF_ERROR);

            old_flush = s.last_flush;
            s.last_flush = flush;

            /* Flush as much pending output as possible */
            if (s.pending != 0)
            {
                flush_pending();
                if (avail_out == 0)
                {
                    /* Since avail_out is 0, deflate will be called again with
                     * more output space, but possibly with both pending and
                     * avail_in equal to zero. There won't be anything to do,
                     * but this is not an error situation so make sure we
                     * return OK instead of BUF_ERROR at next call of deflate:
                     */
                    s.last_flush = (zFlush) (-1);
                    return zRetCode.Z_OK;
                }

            /* Make sure there is something to do and avoid duplicate consecutive
             * flushes. For repeated and useless calls with Z_FINISH, we keep
             * returning Z_STREAM_END instead of Z_BUF_ERROR.
             */
            } else if (avail_in == 0 && RANK(flush) <= RANK(old_flush) &&
                       flush != zFlush.Z_FINISH)
            {
                return ERR_RETURN(zRetCode.Z_BUF_ERROR);
            }

            /* User must not provide more input after the first FINISH: */
            if (s.status == DeflateStatus.FINISH && avail_in != 0)
            {
                return ERR_RETURN(zRetCode.Z_BUF_ERROR);
            }

            /* Write the header */
            if (s.wrap == 0 && s.status == DeflateStatus.INIT)
                s.status = DeflateStatus.BUSY;
            else if (s.status == DeflateStatus.INIT)
            {
                /* zlib header */
                uint header = (zConstants.Z_DEFLATED + ((s.w_bits - 8) << 4)) << 8;
                uint level_flags;

                if (s.strategy >= zSTRATEGY.HUFFMAN_ONLY || s.level < 2)
                    level_flags = 0;
                else if (s.level < 6)
                    level_flags = 1;
                else if (s.level == 6)
                    level_flags = 2;
                else
                    level_flags = 3;

                header |= (level_flags << 6);
                if (s.strstart != 0) header |= zConstants.PRESET_DICT;
                header += 31 - (header % 31);

                putShortMSB(header);

                /* Save the adler32 of the preset dictionary: */
                if (s.strstart != 0)
                {
                    putShortMSB((uint)(adler >> 16));
                    putShortMSB((uint)(adler & 0xffff));
                }
                adler = Adler32.Compute(0, null, 0, 0);
                s.status = DeflateStatus.BUSY;

                flush_pending();
                if (s.pending != 0)
                {
                    s.last_flush = (zFlush)(-1);
                    return zRetCode.Z_OK;
                }
            }

#if GZIP
            if (s.status == DeflateStatus.GZIP)
            {
                /* gzip header */
                adler = CRC32.Update(0, null, 0, 0);
                s.put_byte(31);
                s.put_byte(139);
                s.put_byte(8);
                if (s.gzhead == null)
                {
                    s.put_byte(0);
                    s.put_byte(0);
                    s.put_byte(0);
                    s.put_byte(0);
                    s.put_byte(0);
                    s.put_byte((byte) (s.level == 9 ? 2 :
                        (s.strategy >= zSTRATEGY.HUFFMAN_ONLY || s.level < 2 ?
                         4 : 0)));
                    s.put_byte(zUtil.OS_CODE);
                    s.status = DeflateStatus.BUSY;

                    /* Compression must start with an empty pending buffer */
                    flush_pending();
                    if (s.pending != 0)
                    {
                        s.last_flush = (zFlush)(-1);
                        return zRetCode.Z_OK;
                    }
                }
                else
                {
                    s.put_byte((byte) ((s.gzhead.text ? 1 : 0) +
                                       (s.gzhead.hcrc ? 2 : 0) +
                                       (s.gzhead.extra == null ? 0 : 4) +
                                       (s.gzhead.name == null ? 0 : 8) +
                                       (s.gzhead.comment == null ? 0 : 16)
                                      ));
                    s.put_byte((Byte)(s.gzhead.time & 0xff));
                    s.put_byte((Byte)((s.gzhead.time >> 8) & 0xff));
                    s.put_byte((Byte)((s.gzhead.time >> 16) & 0xff));
                    s.put_byte((Byte)((s.gzhead.time >> 24) & 0xff));
                    s.put_byte((byte)(s.level == 9 ? 2 :
                        (s.strategy >= zSTRATEGY.HUFFMAN_ONLY || s.level < 2 ?
                         4 : 0)));
                    s.put_byte((byte) (s.gzhead.os & 0xff));
                    if (s.gzhead.extra != null)
                    {
                        s.put_byte((byte) (s.gzhead.extra_len & 0xff));
                        s.put_byte((byte) ((s.gzhead.extra_len >> 8) & 0xff));
                    }
                    if (s.gzhead.hcrc)
                        adler = CRC32.Update(adler, s.buffer, s.pending_buf, s.pending);

                    s.gzindex = 0;
                    s.status = DeflateStatus.EXTRA;
                }
            }
            if (s.status == DeflateStatus.EXTRA)
            {
                if (s.gzhead.extra != null)
                {
                    var beg = s.pending; /* start of bytes to update crc */
                    int left = ((s.gzhead.extra_len & 0xffff) - s.gzindex);
                    while (s.pending + left > s.pending_buf_size)
                    {
                        int copy = s.pending_buf_size - s.pending;
                        Buffer.BlockCopy(s.gzhead.extra, s.gzindex,
                            s.buffer, (/*s.pending_buf +*/ s.pending), copy);
                        s.pending = s.pending_buf_size;
                        HCRC_UPDATE(beg);
                        s.gzindex += copy;
                        flush_pending();
                        if (s.pending != 0)
                        {
                            s.last_flush = (zFlush) (-1);
                            return zRetCode.Z_OK;
                        }
                        beg = 0;
                        left -= copy;
                    }
                    Buffer.BlockCopy(s.gzhead.extra, s.gzindex,
                        s.buffer, (/*s.pending_buf +*/ s.pending), left);
                    s.pending += left;
                    HCRC_UPDATE(beg);
                    s.gzindex = 0;
                }
                s.status = DeflateStatus.NAME;
            }
            if (s.status == DeflateStatus.NAME)
            {
                if (s.gzhead.name != null)
                {
                    int beg = s.pending;
                    int val;
                    do
                    {
                        if (s.pending == s.pending_buf_size)
                        {
                            HCRC_UPDATE(beg);
                            flush_pending();
                            if (s.pending != 0)
                            {
                                s.last_flush = (zFlush)(-1);
                                return zRetCode.Z_OK;
                            }
                            beg = 0;
                        }
                        val = s.gzhead.name[s.gzindex++];
                        s.put_byte((byte) val);
                    } while (val != 0);
                    HCRC_UPDATE(beg);
                    s.gzindex = 0;
                }
                s.status = DeflateStatus.COMMENT;
            }
            if (s.status == DeflateStatus.COMMENT)
            {
                if (s.gzhead.comment != null)
                {
                    int beg = s.pending;
                    int val;
                    do
                    {
                        if (s.pending == s.pending_buf_size)
                        {
                            HCRC_UPDATE(beg);
                            flush_pending();
                            if (s.pending != 0)
                            {
                                s.last_flush = (zFlush)(-1);
                                return zRetCode.Z_OK;
                            }
                            beg = 0;
                        }
                        val = s.gzhead.comment[s.gzindex++];
                        s.put_byte((byte)val);
                    } while (val != 0);
                    HCRC_UPDATE(beg);
                }
                s.status = DeflateStatus.HCRC;
            }
            if (s.status == DeflateStatus.HCRC)
            {
                if (s.gzhead.hcrc)
                {
                    if (s.pending + 2 > s.pending_buf_size)
                    {
                        flush_pending();
                        if (s.pending != 0) 
                        {
                            s.last_flush = (zFlush)(-1);
                            return zRetCode.Z_OK;
                        }
                    }
                    s.put_byte((byte)(adler & 0xff));
                    s.put_byte((byte)((adler >> 8) & 0xff));
                    adler = CRC32.Update(0, null, 0, 0);
                }
                s.status = DeflateStatus.BUSY;

                /* Compression must start with an empty pending buffer */
                flush_pending();
                if (s.pending != 0)
                {
                    s.last_flush = (zFlush)(-1);
                    return zRetCode.Z_OK;
                }
            }
#endif

            /* Start a new block or continue the current one.
            */
            if (avail_in != 0 || s.lookahead != 0 ||
                (flush != zFlush.Z_NO_FLUSH && s.status != DeflateStatus.FINISH))
            {
                block_state bstate = 
                    s.level == 0 ? deflate_stored(this, flush) :
                    s.strategy == zSTRATEGY.HUFFMAN_ONLY ? deflate_huff(this, flush) :
                    s.strategy == zSTRATEGY.RLE ? deflate_rle(this, flush) :
                    configuration_table[s.level].func(this, flush);

                if (bstate == block_state.finish_started || bstate == block_state.finish_done)
                {
                    s.status = DeflateStatus.FINISH;
                }
                if (bstate == block_state.need_more || bstate == block_state.finish_started)
                {
                    if (avail_out == 0)
                    {
                        s.last_flush = (zFlush)(-1); /* avoid BUF_ERROR next call, see above */
                    }
                    return zRetCode.Z_OK;
                    /* If flush != Z_NO_FLUSH && avail_out == 0, the next call
                     * of deflate should use the same flush parameter to make sure
                     * that the flush is complete. So we don't have to output an
                     * empty block here, this will be done at next call. This also
                     * ensures that for a very small output buffer, we emit at most
                     * one empty block.
                     */
                }
                if (bstate == block_state.block_done)
                {
                    if (flush == zFlush.Z_PARTIAL_FLUSH)
                    {
                        DeflateTrees.tr_align(s);
                    }
                    /* FULL_FLUSH or SYNC_FLUSH */
                    else if (flush != zFlush.Z_BLOCK)
                    {
                        DeflateTrees.stored_block(s, null, 0, 0, 0);
                        /* For a full flush, this empty block will be recognized
                         * as a special marker by inflate_sync().
                         */
                        if (flush == zFlush.Z_FULL_FLUSH)
                        {
                            CLEAR_HASH(s);  /* forget history */
                            if (s.lookahead == 0)
                            {
                                s.strstart = 0;
                                s.block_start = 0;
                                s.insert = 0;
                            }
                        }
                    }
                    flush_pending();
                    if (avail_out == 0)
                    {
                        s.last_flush = (zFlush)(-1); /* avoid BUF_ERROR next call, see above */
                        return zRetCode.Z_OK;
                    }
                }
            }

            if (flush != zFlush.Z_FINISH) return zRetCode.Z_OK;
            if (s.wrap <= 0) return zRetCode.Z_STREAM_END;

            // Write the trailer
#if GZIP
            if (s.wrap == 2)
            {
                s.put_byte((byte)(adler & 0xff));
                s.put_byte((byte)((adler >> 8) & 0xff));
                s.put_byte((byte)((adler >> 16) & 0xff));
                s.put_byte((byte)((adler >> 24) & 0xff));
                s.put_byte((byte)(total_in & 0xff));
                s.put_byte((byte)((total_in >> 8) & 0xff));
                s.put_byte((byte)((total_in >> 16) & 0xff));
                s.put_byte((byte)((total_in >> 24) & 0xff));
            }
            else
#endif
            {
                putShortMSB((uint)(adler >> 16));
                putShortMSB((uint)(adler & 0xffff));
            }
            flush_pending();
            /* If avail_out is zero, the application will call deflate again
             * to flush the rest.
             */
            if (s.wrap > 0) s.wrap = -s.wrap; /* write the trailer only once! */
            return s.pending != 0 ? zRetCode.Z_OK : zRetCode.Z_STREAM_END;
        }

        public zRetCode DeflateEnd()
        {
            if (deflateStateCheck()) return zRetCode.Z_STREAM_ERROR;

            var status = _state.status;
            _state.buffer = null;
            _state = null;

            return status == DeflateStatus.BUSY ? zRetCode.Z_DATA_ERROR : zRetCode.Z_OK;
        }

        private void flush_pending()
        {
            var s = _state;

            DeflateTrees.flush_bits(s);
            var len = s.pending;
            if (len > avail_out)
            {
                len = avail_out;
            }
            if (len == 0) return;

            Buffer.BlockCopy(s.buffer, s.pending_out, _out, next_out, len);
            next_out += len;
            s.pending_out += len;
            total_out += len;
            avail_out -= len;
            s.pending -= len;
            if (s.pending == 0)
            {
                s.pending_out = s.pending_buf;
            }
        }

        /// <summary>
        /// Put a short in the pending buffer. The 16-bit value is put in MSB order.
        /// IN assertion: the stream state is correct and there is enough room in
        /// pending_buf.
        /// </summary>
        private void putShortMSB(uint b)
        {
            _state.put_byte((byte)(b >> 8));
            _state.put_byte((byte)(b & 0xff));
        }

        #endregion

        #region Deflate store

        /// <summary>
        /// Copy without compression as much as possible from the input stream, return
        /// the current block state.
        ///
        /// In case deflateParams() is used to later switch to a non-zero compression
        /// level, s->matches (otherwise unused when storing) keeps track of the number
        /// of hash table slides to perform.If s->matches is 1, then one hash table
        /// slide will be done when switching.If s->matches is 2, the maximum value
        /// allowed here, then the hash table will be cleared, since two or more slides
        /// is the same as a clear.
        ///
        /// deflate_stored() is written to minimize the number of times an input byte is
        /// copied.It is most efficient with large input and output buffers, which
        /// maximizes the opportunities to have a single copy from next_in to next_out.
        /// </summary>
        private static block_state deflate_stored(zDeflate z, zFlush flush)
        {
            return z.deflate_stored(z._state, flush);
        }

        private block_state deflate_stored(DeflateState s, zFlush flush)
        { 
            // Smallest worthy block size when not flushing or finishing. By default
            // this is 32K. This can be as small as 507 bytes for memLevel == 1. For
            // large input and output buffers, the stored block size will be larger.
            int min_block = Math.Min(s.pending_buf_size - 5, s.w_size);

            // Copy as many min_block or larger stored blocks directly to next_out as
            // possible. If flushing, copy the remaining available input to next_out as
            // stored blocks, if there is enough space.
            int len, have;
            int left;
            int last = 0;
            int used = avail_in;
            do
            {
                // Set len to the maximum size block that we can copy directly with the
                // available input data and output space. Set left to how much of that
                // would be copied from what's left in the window.
                len = MAX_STORED;       // Maximum deflate stored block length
                have = (s.bi_valid + 42) >> 3;      // Number of header bytes
                if (avail_out < have)                     // Need room for header
                    break;
                // Maximum stored block length that will fit in avail_out:
                have = avail_out - have;
                left = (int) s.strstart - s.block_start; // Bytes left in window
                if (len > left + avail_in)
                    len = left + avail_in;                // Limit len to the input
                if (len > have)
                    len = have;                           // Limit len to the output

                // If the stored block would be less than min_block in length, or if
                // unable to copy all of the available input when flushing, then try
                // copying to the window and the pending buffer instead. Also don't
                // write an empty block when flushing -- deflate() does that.
                if (len < min_block && ((len == 0 && flush != zFlush.Z_FINISH) ||
                                        flush == zFlush.Z_NO_FLUSH ||
                                        len != left + avail_in))
                    break;

                // Make a dummy stored block in pending to get the header bytes,
                // including any pending bits. This also updates the debugging counts.
                last = flush == zFlush.Z_FINISH && len == left + avail_in ? 1 : 0;
                DeflateTrees.stored_block(s, null, 0, 0, last);

                // Replace the lengths in the dummy stored block with len.
                s.buffer[/*s.pending_buf +*/ s.pending - 4] = (byte) len;
                s.buffer[/*s.pending_buf +*/ s.pending - 3] = (byte) (len >> 8);
                s.buffer[/*s.pending_buf +*/ s.pending - 2] = (byte) ~len;
                s.buffer[/*s.pending_buf +*/ s.pending - 1] = (byte) (~len >> 8);

                // Write the stored block header bytes.
                flush_pending();

#if ZLIB_DEBUG
                // Update debugging counts for the data about to be copied.
                s.compressed_len += len << 3;
                s.bits_sent += len << 3;
#endif

                // Copy uncompressed bytes from the window to next_out.
                if (left != 0)
                {
                    if (left > len)
                        left = (int) len;
                    Buffer.BlockCopy(s.window, s.block_start, _out, next_out, left);
                    next_out += left;
                    avail_out -= left;
                    total_out += left;
                    s.block_start += left;
                    len -= left;
                }

                // Copy uncompressed bytes directly from next_in to next_out, updating
                // the check value.
                if (len != 0)
                {
                    read_buf(_out, next_out, (int) len);
                    next_out += (int)len;
                    avail_out -= len;
                    total_out += len;
                }
            } while (last == 0);

            // Update the sliding window with the last s->w_size bytes of the copied
            // data, or append all of the copied data to the existing window if less
            // than s->w_size bytes were copied. Also update the number of bytes to
            // insert in the hash tables, in the event that deflateParams() switches to
            // a non-zero compression level.
            used -= avail_in;      // number of input bytes directly copied
            if (used != 0)
            {
                // If any input was used, then no unused input remains in the window,
                // therefore s->block_start == s->strstart.
                if (used >= s.w_size)
                {    // supplant the previous history
                    s.matches = 2;         // clear hash
                    Buffer.BlockCopy(_in, (int) (next_in - s.w_size), s.window, 0, (int) s.w_size);
                    s.strstart = s.w_size;
                    s.insert = s.strstart;
                }
                else
                {
                    if (s.window_size - s.strstart <= used)
                    {
                        // Slide the window down.
                        s.strstart -= s.w_size;
                        Buffer.BlockCopy(s.window, (int) s.w_size, s.window, 0, (int) s.strstart);
                        if (s.matches < 2)
                            s.matches++;   // add a pending slide_hash()
                        if (s.insert > s.strstart)
                            s.insert = s.strstart;
                    }
                    Buffer.BlockCopy(_in, (int) (next_in - used), s.window, (int) s.strstart, (int) used);
                    s.strstart += used;
                    s.insert += Math.Min(used, s.w_size - s.insert);
                }
                s.block_start = (int) s.strstart;
            }
            if (s.high_water < s.strstart)
                s.high_water = s.strstart;

            // If the last block was written to next_out, then done.
            if (last != 0)
                return block_state.finish_done;

            // If flushing and all input has been consumed, then done.
            if (flush != zFlush.Z_NO_FLUSH && flush != zFlush.Z_FINISH &&
                avail_in == 0 && (int)s.strstart == s.block_start)
                return block_state.block_done;

            // Fill the window with any remaining input.
            have = s.window_size - s.strstart;
            if (avail_in > have && s.block_start >= (int)s.w_size)
            {
                // Slide the window down.
                s.block_start -= (int) s.w_size;
                s.strstart -= s.w_size;
                Buffer.BlockCopy(s.window, (int) s.w_size, s.window, 0, (int) s.strstart);
                if (s.matches < 2)
                    s.matches++;           // add a pending slide_hash()
                have += s.w_size;          // more space now
                if (s.insert > s.strstart)
                    s.insert = s.strstart;
            }
            if (have > avail_in)
                have = avail_in;
            if (have != 0)
            {
                read_buf(s.window, (int) s.strstart, (int) have);
                s.strstart += have;
                s.insert += Math.Min(have, s.w_size - s.insert);
            }
            if (s.high_water < s.strstart)
                s.high_water = s.strstart;

            // There was not enough avail_out to write a complete worthy or flushed
            // stored block to next_out. Write a stored block to pending instead, if we
            // have enough input for a worthy block, or if flushing and there is enough
            // room for the remaining input as a stored block in the pending buffer.
            have = (s.bi_valid + 42) >> 3;         // number of header bytes
            // Maximum stored block length that will fit in pending:
            have = Math.Min(s.pending_buf_size - have, MAX_STORED);
            min_block = Math.Min(have, s.w_size);
            left = (int) (s.strstart - s.block_start);
            if (left >= min_block ||
                ((left != 0 || flush == zFlush.Z_FINISH) && flush != zFlush.Z_NO_FLUSH &&
                 avail_in == 0 && left <= have))
            {
                len = Math.Min(left, have);
                last = flush == zFlush.Z_FINISH && avail_in == 0 &&
                       len == left ? 1 : 0;
                DeflateTrees.stored_block(s, s.window, s.block_start, len, last);
                s.block_start += (int) len;
                flush_pending();
            }

            // We've done all we can with the available input and output.
            return last != 0 ? block_state.finish_started : block_state.need_more;
        }

#endregion

        #region Deflate fast

        /// <summary>
        /// Compress as much as possible from the input stream, return the current
        /// block state.
        /// This function does not perform lazy evaluation of matches and inserts
        /// new strings in the dictionary only for unmatched strings or for short
        /// matches.It is used only for the fast compression options.
        /// </summary>
        private static block_state deflate_fast(zDeflate z, zFlush flush)
        {
            return z.deflate_fast(z._state, flush);
        }

        private block_state deflate_fast(DeflateState s, zFlush flush)
        {
            int hash_head;       // head of the hash chain
            bool bflush;           // set if current block must be flushed

            for (; ; )
            {
                // Make sure that we always have enough lookahead, except
                // at the end of the input file. We need MAX_MATCH bytes
                // for the next match, plus MIN_MATCH bytes to insert the
                // string following the next match.
                if (s.lookahead < MIN_LOOKAHEAD)
                {
                    fill_window(s);
                    if (s.lookahead < MIN_LOOKAHEAD && flush == zFlush.Z_NO_FLUSH)
                    {
                        return block_state.need_more;
                    }
                    if (s.lookahead == 0) break; // flush the current block
                }

                // Insert the string window[strstart .. strstart + 2] in the
                // dictionary, and set hash_head to the head of the hash chain:
                hash_head = 0;
                if (s.lookahead >= zUtil.MIN_MATCH)
                {
                    INSERT_STRING(s, s.strstart, out hash_head);
                }

                // Find the longest match, discarding those <= prev_length.
                // At this point we have always match_length < MIN_MATCH
                if (hash_head != 0 && s.strstart - hash_head <= MAX_DIST(s))
                {
                    // To simplify the code, we prevent matches with the string
                    // of window index 0 (in particular we have to avoid a match
                    // of the string with itself at the start of the input file).
                    s.match_length = longest_match(s, hash_head);
                    // longest_match() sets match_start
                }
                if (s.match_length >= zUtil.MIN_MATCH)
                {
                    //check_match(s, s->strstart, s->match_start, s->match_length);

                    DeflateTrees.tally_dist(s, (ushort) (s.strstart - s.match_start),
                                   (byte) (s.match_length - zUtil.MIN_MATCH), out bflush);

                    s.lookahead -= s.match_length;

                    // Insert new strings in the hash table only if the match length
                    // is not too large. This saves time but degrades compression.
# if !FASTEST
                    if (s.match_length <= s.max_insert_length &&
                        s.lookahead >= zUtil.MIN_MATCH)
                    {
                        s.match_length--; // String at strstart already in table
                        do
                        {
                            s.strstart++;
                            INSERT_STRING(s, s.strstart, out hash_head);
                            // strstart never exceeds WSIZE-MAX_MATCH, so there are
                            // always MIN_MATCH bytes ahead.
                        } while (--s.match_length != 0);
                        s.strstart++;
                    }
                    else
#endif
                    {
                        s.strstart += s.match_length;
                        s.match_length = 0;
                        s.ins_h = s.window[s.strstart];
                        UPDATE_HASH(s, ref s.ins_h, s.window[s.strstart + 1]);
                        if (zUtil.MIN_MATCH != 3)
                            throw new NotImplementedException("Call UPDATE_HASH() MIN_MATCH-3 more times");
                        // If lookahead < MIN_MATCH, ins_h is garbage, but it does not
                        // matter since it will be recomputed at next deflate call.
                    }
                }
                else
                {
                    // No match, output a literal byte
                    DeflateTrees.tally_lit(s, s.window[s.strstart], out bflush);
                    s.lookahead--;
                    s.strstart++;
                }
                if (bflush)
                {
                    //FLUSH_BLOCK(s, 0);
                    FLUSH_BLOCK_ONLY(s, 0);
                    if (avail_out == 0)
                        return block_state.need_more;
                }
            }
            s.insert = s.strstart < zUtil.MIN_MATCH - 1 ? s.strstart : zUtil.MIN_MATCH - 1;
            if (flush == zFlush.Z_FINISH)
            {
                //FLUSH_BLOCK(s, 1);
                FLUSH_BLOCK_ONLY(s, 1);
                if (avail_out == 0)
                    return block_state.finish_started;
                return block_state.finish_done;
            }
            if (s.sym_next != 0)
            {
                //FLUSH_BLOCK(s, 0);
                FLUSH_BLOCK_ONLY(s, 0);
                if (avail_out == 0)
                    return block_state.need_more;
            }
            return block_state.block_done;
        }

        #endregion

        #region Deflate slow
#if !FASTEST
        /// <summary>
        /// Uses lazy evaluation for matches: a match is finally adopted only if there is
        /// no better match at the next window position.
        /// </summary>
        private static block_state deflate_slow(zDeflate z, zFlush flush)
        {
            return z.deflate_slow(z._state, flush);
        }

        private block_state deflate_slow(DeflateState s, zFlush flush)
        {
            //Head of hash chain
            int hash_head;

            //Set if current block must be flushed
            bool bflush;

            //Process the input block.
            while (true)
            {
                // Make sure that we always have enough lookahead, except
                // at the end of the input file. We need MAX_MATCH bytes
                // for the next match, plus MIN_MATCH bytes to insert the
                // string following the next match.
                if (s.lookahead < MIN_LOOKAHEAD)
                {
                    fill_window(s);
                    if (s.lookahead < MIN_LOOKAHEAD && flush == zFlush.Z_NO_FLUSH)
                    {
                        return block_state.need_more;
                    }
                    if (s.lookahead == 0)
                    {
                        // Flush the current block
                        break;
                    }
                }

                // Insert the string window[strstart .. strstart + 2] in the
                // dictionary, and set hash_head to the head of the hash chain:
                hash_head = 0;
                if (s.lookahead >= zUtil.MIN_MATCH)
                {
                    INSERT_STRING(s, s.strstart, out hash_head);
                }

                // Find the longest match, discarding those <= prev_length
                s.prev_length = s.match_length;
                s.prev_match = s.match_start;
                s.match_length = zUtil.MIN_MATCH - 1;

                if (hash_head != 0 && s.prev_length < s.max_lazy_match &&
                    s.strstart - hash_head <= MAX_DIST(s))
                {
                    // To simplify the code, we prevent matches with the string
                    // of window index 0(in particular we have to avoid a match
                    // of the string with itself at the start of the input file).
                    s.match_length = longest_match(s, hash_head);
                    // longest_match sets match_start

                    if (TOO_FAR <= 32767)
                    {
                        if (s.match_length <= 5 && (s.strategy == zSTRATEGY.FILTERED ||
                            (s.match_length == zUtil.MIN_MATCH && s.strstart - s.match_start > TOO_FAR)))
                        {
                            s.match_length = zUtil.MIN_MATCH - 1;
                        }
                    } 
                    else
                    {
#pragma warning disable CS0162 // Unreachable code detected
                        if (s.match_length <= 5 && (s.strategy == zSTRATEGY.FILTERED))
                        {
                            s.match_length = zUtil.MIN_MATCH - 1;
                        }
#pragma warning restore CS0162 // Unreachable code detected
                    }
                }

                // If there was a match at the previous step and the current
                // match is not better, output the previous match:
                if (s.prev_length >= zUtil.MIN_MATCH && s.match_length <= s.prev_length)
                {
                    // Do not insert strings in hash table beyond this
                    int max_insert = s.strstart + s.lookahead - zUtil.MIN_MATCH;

                    //Unimplemented debug function:
                    //check_match(s, s->strstart - 1, s->prev_match, s->prev_length);

                    DeflateTrees.tally_dist(s, (ushort) (s.strstart - 1 - s.prev_match),
                        (byte) (s.prev_length - zUtil.MIN_MATCH), out bflush);

                    // Insert in hash table all strings up to the end of the match.
                    // strstart - 1 and strstart are already inserted. If there is not
                    // enough lookahead, the last two strings are not inserted in
                    // the hash table.
                    s.lookahead -= s.prev_length - 1;
                    s.prev_length -= 2;
                    do
                    {
                        if (++s.strstart <= max_insert)
                        {
                            INSERT_STRING(s, s.strstart, out hash_head);
                        }
                    } while (--s.prev_length != 0);
                    s.match_available = 0;
                    s.match_length = zUtil.MIN_MATCH - 1;
                    s.strstart++;

                    if (bflush)
                    {
                        //FLUSH_BLOCK(s, 0);
                        FLUSH_BLOCK_ONLY(s, 0);
                        if (s.strm.avail_out == 0)
                            return block_state.need_more;
                    }
                }
                else if (s.match_available != 0)
                {
                    // If there was no match at the previous position, output a
                    // single literal. If there was a match but the current match
                    // is longer, truncate the previous match to a single literal.
                    DeflateTrees.tally_lit(s, s.window[s.strstart - 1], out bflush);
                    if (bflush)
                    {
                        FLUSH_BLOCK_ONLY(s, 0);
                    }
                    s.strstart++;
                    s.lookahead--;
                    if (avail_out == 0) return block_state.need_more;
                }
                else
                {
                    /* There is no previous match to compare with, wait for
                     * the next step to decide.
                     */
                    s.match_available = 1;
                    s.strstart++;
                    s.lookahead--;
                }
            }
            Debug.Assert(flush != zFlush.Z_NO_FLUSH, "no flush?");
            if (s.match_available != 0)
            {
                DeflateTrees.tally_lit(s, s.window[s.strstart - 1], out bflush);
                s.match_available = 0;
            }
            s.insert = s.strstart < zUtil.MIN_MATCH - 1 ? s.strstart : zUtil.MIN_MATCH - 1;
            if (flush == zFlush.Z_FINISH)
            {
                //FLUSH_BLOCK(s, 1);
                FLUSH_BLOCK_ONLY(s, 1);
                if (avail_out == 0) 
                    return block_state.finish_started;
                return block_state.finish_done;
            }
            if (s.sym_next != 0)
            {
                //FLUSH_BLOCK(s, 0);
                FLUSH_BLOCK_ONLY(s, 0);
                if (avail_out == 0) 
                    return block_state.need_more;
            }
            return block_state.block_done;
        }
#endif
#endregion

        #region Deflate huff

        /// <summary>
        /// For Z_HUFFMAN_ONLY, do not look for matches.  Do not maintain a hash table.
        /// (It will be regenerated if this run of deflate switches away from Huffman.)
        /// </summary>
        private static block_state deflate_huff(zDeflate z, zFlush flush)
        { 
            return z.deflate_huff(z._state, flush);
        }

        private block_state deflate_huff(DeflateState s, zFlush flush)
        {
            bool bflush;             // Set if current block must be flushed 

            for (; ; )
            {
                // Make sure that we have a literal to write.
                if (s.lookahead == 0)
                {
                    fill_window(s);
                    if (s.lookahead == 0)
                    {
                        if (flush == zFlush.Z_NO_FLUSH)
                            return block_state.need_more;
                        break;      // flush the current block 
                    }
                }

                /* Output a literal byte */
                s.match_length = 0;
                DeflateTrees.tally_lit(s, s.window[s.strstart], out bflush);
                s.lookahead--;
                s.strstart++;
                if (bflush)
                {
                    //FLUSH_BLOCK(s, 0);
                    FLUSH_BLOCK_ONLY(s, 0);
                    if (s.strm.avail_out == 0)
                        return block_state.need_more;
                }
            }
            s.insert = 0;
            if (flush == zFlush.Z_FINISH)
            {
                //FLUSH_BLOCK(s, 1);
                FLUSH_BLOCK_ONLY(s, 1);
                if (avail_out == 0)
                    return block_state.finish_started;
                return block_state.finish_done;
            }
            if (s.sym_next != 0) {
                //FLUSH_BLOCK(s, 0);
                FLUSH_BLOCK_ONLY(s, 0);
                if (s.strm.avail_out == 0)
                    return block_state.need_more;
            }
            return block_state.block_done;
        }

        #endregion

        #region Deflate rle

        private static block_state deflate_rle(zDeflate z, zFlush flush)
        { 
            return z.deflate_rle(z._state, flush);
        }

        /// <summary>
        /// For Z_RLE, simply look for runs of bytes, generate matches only of distance
        /// one.Do not maintain a hash table.  (It will be regenerated if this run of
        /// deflate switches away from Z_RLE.)
        /// </summary>
        private block_state deflate_rle(DeflateState s, zFlush flush)
        {
            bool bflush;           // Set if current block must be flushed
            int prev;              // Byte at distance one to match
            int scan, strend;      // Scan goes up to strend for length of run

            for (; ; )
            {
                /* Make sure that we always have enough lookahead, except
                 * at the end of the input file. We need MAX_MATCH bytes
                 * for the longest run, plus one for the unrolled loop.
                 */
                if (s.lookahead <= zUtil.MAX_MATCH)
                {
                    fill_window(s);
                    if (s.lookahead <= zUtil.MAX_MATCH && flush == zFlush.Z_NO_FLUSH)
                    {
                        return block_state.need_more;
                    }
                    if (s.lookahead == 0) break; /* flush the current block */
                }

                /* See how many times the previous byte repeats */
                s.match_length = 0;
                if (s.lookahead >= zUtil.MIN_MATCH && s.strstart > 0)
                {
                    scan = s.strstart - 1;
                    prev = s.window[scan];
                    if (prev == s.window[++scan] && prev == s.window[++scan] 
                        && prev == s.window[++scan])
                    {
                        strend = s.strstart + zUtil.MAX_MATCH;
                        while (prev == s.window[++scan] && prev == s.window[++scan] &&
                               prev == s.window[++scan] && prev == s.window[++scan] &&
                               prev == s.window[++scan] && prev == s.window[++scan] &&
                               prev == s.window[++scan] && prev == s.window[++scan] &&
                               scan < strend);
                        s.match_length = zUtil.MAX_MATCH - (strend - scan);
                        if (s.match_length > s.lookahead)
                            s.match_length = s.lookahead;
                    }
                    Debug.Assert(scan <= s.window_size - 1,
                           "wild scan");
                }

                /* Emit match if have run of MIN_MATCH or longer, else emit literal */
                if (s.match_length >= zUtil.MIN_MATCH)
                {
                    //check_match(s, s->strstart, s->strstart - 1, s->match_length);

                    DeflateTrees.tally_dist(s, 1, 
                        (byte) (s.match_length - zUtil.MIN_MATCH), out bflush);

                    s.lookahead -= s.match_length;
                    s.strstart += s.match_length;
                    s.match_length = 0;
                }
                else
                {
                    /* No match, output a literal byte */
                    DeflateTrees.tally_lit(s, s.window[s.strstart], out bflush);
                    s.lookahead--;
                    s.strstart++;
                }
                if (bflush)
                {
                    //FLUSH_BLOCK(s, 0);
                    FLUSH_BLOCK_ONLY(s, 0);
                    if (s.strm.avail_out == 0)
                        return block_state.need_more;
                }
            }
            s.insert = 0;
            if (flush == zFlush.Z_FINISH)
            {
                //FLUSH_BLOCK(s, 1);
                FLUSH_BLOCK_ONLY(s, 1);
                if (avail_out == 0)
                    return block_state.finish_started;
                return block_state.finish_done;
            }
            if (s.sym_next != 0)
            {
                //FLUSH_BLOCK(s, 0);
                FLUSH_BLOCK_ONLY(s, 0);
                if (s.strm.avail_out == 0)
                    return block_state.need_more;
            }
            return block_state.block_done;
        }

        #endregion

#if !FASTEST
        /// <summary>
        /// Set match_start to the longest match starting at the given string and
        /// return its length.Matches shorter or equal to prev_length are discarded,
        /// in which case the result is equal to prev_length and match_start is
        /// garbage.
        /// IN assertions: cur_match is the head of the hash chain for the current
        ///   string (strstart) and its distance is <= MAX_DIST, and prev_length >= 1
        /// OUT assertion: the match length is not greater than s->lookahead.
        /// </summary>
        private int longest_match(DeflateState s, int cur_match)
        {
            int chain_length = s.max_chain_length; // max hash chain length
            byte[] scan = s.window;                 // current string
            int scan_pt = (int) s.strstart;
            int len;                                // Length of current match
            int match_pt;                           // matched string, points at "scan"
            int best_len = (int) s.prev_length;     // best match length so far
            int nice_match = s.nice_match;          // stop if match long enough

            // Stop when cur_match becomes <= limit. To simplify the code,
            // we prevent matches with the string of window index 0.
            int limit = s.strstart > MAX_DIST(s) ?
                s.strstart - MAX_DIST(s) : 0;

            ushort[] prev = s.prev;
            int wmask = s.w_mask;

            int strend_pt = (int)(s.strstart + zUtil.MAX_MATCH);
            byte scan_end1 = scan[scan_pt + best_len - 1];
            byte scan_end = scan[scan_pt + best_len];

            Debug.Assert(s.hash_bits >= 8 && zUtil.MAX_MATCH == 258, "Code too clever");

            // Do not waste too much time if we already have a good match:
            if (s.prev_length >= s.good_match)
            {
                chain_length >>= 2;
            }
            // Do not look for matches beyond the end of the input. This is necessary
            // to make deflate deterministic.
            if (nice_match > s.lookahead) nice_match = (int) s.lookahead;

            Debug.Assert(s.strstart <= s.window_size - MIN_LOOKAHEAD, "need lookahead");

            do
            {
                Debug.Assert(cur_match < s.strstart, "no future");
                match_pt = (int)cur_match;

                // Skip to next match if the match length cannot increase
                // or if the match length is less than 2.Note that the checks below
                // for insufficient lookahead only occur occasionally for performance
                // reasons.  Therefore uninitialized memory will be accessed, and
                // conditional jumps will be made that depend on those values.
                // However the length of the match is limited to the lookahead, so
                // the output of deflate is not affected by the uninitialized values.
                if (scan[match_pt + best_len] != scan_end ||
                    scan[match_pt + best_len - 1] != scan_end1 ||
                    scan[match_pt] != scan[scan_pt] ||
                    scan[++match_pt] != scan[scan_pt + 1])
                    continue;

                // The check at best_len - 1 can be removed because it will be made
                // again later. (This heuristic is not always a win.)
                // It is not necessary to compare scan[2] and match[2] since they
                // are always equal when the other bytes match, given that
                // the hash keys are equal and that HASH_BITS >= 8.
                scan_pt += 2;
                match_pt++;
                Debug.Assert(scan[scan_pt] == scan[match_pt], "match[2]?");

                // We check for insufficient lookahead only every 8th comparison;
                // the 256th check will be made at strstart + 258.
                while (scan[++scan_pt] == scan[++match_pt] && scan[++scan_pt] == scan[++match_pt] &&
                       scan[++scan_pt] == scan[++match_pt] && scan[++scan_pt] == scan[++match_pt] &&
                       scan[++scan_pt] == scan[++match_pt] && scan[++scan_pt] == scan[++match_pt] &&
                       scan[++scan_pt] == scan[++match_pt] && scan[++scan_pt] == scan[++match_pt] &&
                       scan_pt < strend_pt) /* NOP */
                    ;

                    Debug.Assert(scan_pt < s.window_size - 1, "wild scan");

                len = (int)(zUtil.MAX_MATCH - (strend_pt - scan_pt));
                scan_pt = strend_pt - (int)zUtil.MAX_MATCH;

                if (len > best_len)
                {
                    s.match_start = cur_match;
                    best_len = len;
                    if (len >= nice_match) break;
                    scan_end1 = scan[scan_pt + best_len - 1];
                    scan_end = scan[scan_pt + best_len];
                }

            } while ((cur_match = prev[cur_match & wmask]) > limit && --chain_length != 0);

            if (best_len <= s.lookahead) return best_len;
            return s.lookahead;
        }
#else
        private uint longest_match(DeflateState s, uint cur_match)
        {
            throw new NotImplementedException("Fastest longest match");
        }
#endif

        private void fill_window(DeflateState s)
        {
            int n;
            int more; //Amount of free space at the end of the window.
            int wsize = s.w_size;
            
            do
            {
                more = s.window_size - s.lookahead - s.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 (s.strstart >= wsize + MAX_DIST(s))
                {
                    Buffer.BlockCopy(s.window, (int)wsize, s.window, 0, (int)(wsize - more));
                    s.match_start -= wsize;
                    s.strstart -= wsize;
                    s.block_start -= (int)wsize;
                    if (s.insert > s.strstart)
                        s.insert = s.strstart;
                    slide_hash(s);
                    more += wsize;
                }
                if (avail_in == 0) break;

                n = read_buf(s.window, s.strstart + s.lookahead, more);
                s.lookahead += n;

                // Initialize the hash value now that we have some input
                if (s.lookahead + s.insert > zUtil.MIN_MATCH)
                {
                    int str = s.strstart - s.insert;
                    s.ins_h = s.window[str];
                    UPDATE_HASH(s, ref s.ins_h, s.window[str + 1]);
                    if (zUtil.MIN_MATCH != 3)
                    {
                        throw new NotImplementedException("Call UPDATE_HASH() MIN_MATCH - 3 more times");
                    }
                    while (s.insert != 0)
                    {
                        UPDATE_HASH(s, ref s.ins_h, s.window[str + zUtil.MIN_MATCH - 1]);
#if !FASTEST
                        s.prev[str & s.w_mask] = s.head[s.ins_h];
#endif
                        s.head[s.ins_h] = (ushort)str;
                        str++;
                        s.insert--;
                        if (s.lookahead + s.insert < zUtil.MIN_MATCH)
                            break;
                    }
                }
                // If the whole input has less than MIN_MATCH bytes, ins_h is garbage,
                // but this is not important since only literal bytes will be emitted.
            } while (s.lookahead < MIN_LOOKAHEAD && avail_in != 0);

            // If the WIN_INIT bytes after the end of the current data have never been
            // written, then zero those bytes in order to avoid memory check reports of
            // the use of uninitialized (or uninitialised as Julian writes) bytes by
            // the longest match routines.  Update the high water mark for the next
            // time through here.  WIN_INIT is set to MAX_MATCH since the longest match
            // routines allow scanning to strstart + MAX_MATCH, ignoring lookahead.
            if (s.high_water < s.window_size)
            {
                int curr = s.strstart + s.lookahead;
                int init;

                if (s.high_water < curr)
                {
                    // Previous high water mark below current data -- zero WIN_INIT
                    // bytes or up to end of window, whichever is less.
                    init = s.window_size - curr;
                    if (init > WIN_INIT)
                        init = WIN_INIT;
                    for(int c=0, i = (int) (curr); c < init; c++, i++)
                    {
                        s.window[i] = 0;
                    }
                    s.high_water = curr + init;
                }
                else if (s.high_water < curr + WIN_INIT)
                {
                    // High water mark at or above current data, but below current data
                    // plus WIN_INIT -- zero out to current data plus WIN_INIT, or up
                    // to end of window, whichever is less.
                    init = curr + WIN_INIT - s.high_water;
                    if (init > s.window_size - s.high_water)
                        init = s.window_size - s.high_water;
                    for (int c = 0, i = s.high_water; c < init; c++, i++)
                    {
                        s.window[i] = 0;
                    }
                }
            }
        }

        private void slide_hash(DeflateState s)
        {
            int n, m;
            ushort[] p;
            int wsize = s.w_size;

            n = s.hash_size;
            p = s.head;
            int p_pos = (int) n;
            do
            {
                m = p[p_pos--];
                p[p_pos] = (ushort) (m > wsize ? m - wsize : 0);
            } while (--n != 0);
            n = wsize;
#if !FASTEST
            p = s.prev;
            p_pos = (int) n;
            do
            {
                m = p[p_pos--];
                p[p_pos] = (ushort)(m > wsize ? m - wsize : 0);
            } while (--n != 0);
#endif
        }

        private int read_buf(byte[] buf, int pos, int size)
        {
            int len = avail_in;

            if (len > size)
            {
                len = size;
            }

            avail_in -= len;

            Buffer.BlockCopy(_in, next_in, buf, pos, (int)len);
            if (_state.wrap == 1)
            {
                adler = Adler32.Compute(adler, buf, pos, (int)len);
            }
#if GZIP
            else if (_state.wrap == 2)
            {
                adler = CRC32.Update(adler, buf, pos, (int)len);
            }
#endif
            next_in += (int) len;
            total_in += len;

            return len;
        }

        private zRetCode ERR_RETURN(zRetCode code)
        {
            msg = zUtil.errmsg[zRetCode.Z_NEED_DICT - code];
            return code;
        }

        private int RANK(zFlush f)
        {
            return (((int)f) * 2) - (((int)f) > 4 ? 9 : 0);
        }

        private void HCRC_UPDATE(int beg)
        {
            var s = _state;
            if (s.gzhead.hcrc && s.pending > beg)
            {
                adler = CRC32.Update(adler, s.buffer, /*s.pending_buf +*/ beg, s.pending - beg);
            }
        }

        private int MAX_DIST(DeflateState s) 
        {
            return s.w_size - MIN_LOOKAHEAD;
        }

        private void UPDATE_HASH(DeflateState s, ref int h, byte c)
        {
            h = ((h << s.hash_shift) ^ c) & s.hash_mask;
        }

#if FASTEST
        private void INSERT_STRING(DeflateState s, uint str, out uint match_head)
        {
            UPDATE_HASH(s, ref s.ins_h, s.window[str + zUtil.MIN_MATCH - 1]);
            match_head = s.head[s.ins_h];
            s.head[s.ins_h] = (ushort)str;
        }
#else
        private void INSERT_STRING(DeflateState s, int str, out int match_head)
        {
            UPDATE_HASH(s, ref s.ins_h, s.window[str + zUtil.MIN_MATCH - 1]);
            match_head = s.prev[str & s.w_mask] = s.head[s.ins_h];
            s.head[s.ins_h] = (ushort)str;
        }
#endif

        /* ===========================================================================
         * Flush the current block, with given end-of-file flag.
         * IN assertion: strstart is set to the end of the current match.
         */
        private void FLUSH_BLOCK_ONLY(DeflateState s, uint last)
        {
            if (s.block_start >= 0)
            {
                DeflateTrees.flush_block(s, s.window, s.block_start, s.strstart - s.block_start, (int)last);
            }
            else
            {
                DeflateTrees.flush_block(s, null, 0, s.strstart - s.block_start, (int)last);
            }
           s.block_start = s.strstart;
           flush_pending();
        }

        ///* Same but force premature exit if necessary. */
        //private block_state FLUSH_BLOCK(DeflateState s, uint last) 
        //{   //Don't uncomment, copy this code. 
        //    FLUSH_BLOCK_ONLY(s, last);
        //    if (s.strm.avail_out == 0) 
        //        return (last != 0) ? block_state.finish_started : block_state.need_more;
        //}

#region Support classes

        private class Config
        {
            /// <summary>
            /// Reduce lazy search above this match length
            /// </summary>
            public readonly ushort good_length;

            /// <summary>
            /// Do not perform lazy search above this match length
            /// </summary>
            public readonly ushort max_lazy;

            /// <summary>
            /// Quit search above this match length
            /// </summary>
            public readonly ushort nice_length;

            public readonly ushort max_chain;

            /// <summary>
            /// Function used for compressing the data
            /// </summary>
            public readonly CompressFunc func;

            internal Config(ushort good_length, ushort max_lazy, ushort nice_length, ushort max_chain, CompressFunc func)
            {
                this.good_length = good_length;
                this.max_lazy = max_lazy;
                this.nice_length = nice_length;
                this.max_chain = max_chain;
                this.func = func;
            }
        }

        private enum block_state
        {
            /// <summary>
            /// Block not completed, need more input or more output
            /// </summary>
            need_more,

            /// <summary>
            /// Block flush performed
            /// </summary>
            block_done,

            /// <summary>
            /// Finish started, need only more output at next deflate
            /// </summary>
            finish_started,

            /// <summary>
            /// Finish done, accept no more input or output
            /// </summary>
            finish_done
        }

#endregion
    }
}