context: // Deflate.cs
  // ------------------------------------------------------------------
  //
  // Copyright (c) 2009 Dino Chiesa and Microsoft Corporation.  
  // All rights reserved.
  //
  // This code module is part of DotNetZip, a zipfile class library.
  //
  // ------------------------------------------------------------------
  //
  // This code is licensed under the Microsoft Public License. 
  // See the file License.txt for the license details.
  // More info on: http://dotnetzip.codeplex.com
  //
  // ------------------------------------------------------------------
  //
  // last saved (in emacs): 
  // Time-stamp: <2009-October-28 13:44:59>
  //
  // ------------------------------------------------------------------
  //
  // This module defines logic for handling the Deflate or compression.
  //
  // This code is based on multiple sources: 
  // - the original zlib v1.2.3 source, which is Copyright (C) 1995-2005 Jean-loup Gailly.
  // - the original jzlib, which is Copyright (c) 2000-2003 ymnk, JCraft,Inc. 
  //
  // However, this code is significantly different from both.  
  // The object model is not the same, and many of the behaviors are different.
  //
  // In keeping with the license for these other works, the copyrights for 
  // jzlib and zlib are here.
  //
  // -----------------------------------------------------------------------
  // Copyright (c) 2000,2001,2002,2003 ymnk, JCraft,Inc. All rights reserved.
  // 
  // Redistribution and use in source and binary forms, with or without
  // modification, are permitted provided that the following conditions are met:
  // 
  // 1. Redistributions of source code must retain the above copyright notice,
  // this list of conditions and the following disclaimer.
  // 
  // 2. Redistributions in binary form must reproduce the above copyright 
  // notice, this list of conditions and the following disclaimer in 
  // the documentation and/or other materials provided with the distribution.
  // 
  // 3. The names of the authors may not be used to endorse or promote products
  // derived from this software without specific prior written permission.
  // 
  // THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED WARRANTIES,
  // INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
  // FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL JCRAFT,
  // INC. OR ANY CONTRIBUTORS TO THIS SOFTWARE BE LIABLE FOR ANY DIRECT, INDIRECT,
  // INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA,
  // OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
  // LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
  // NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE,
  // EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  // 
  // -----------------------------------------------------------------------
  //
  // This program is based on zlib-1.1.3; credit to authors
  // Jean-loup Gailly(jloup@gzip.org) and Mark Adler(madler@alumni.caltech.edu)
  // and contributors of zlib.
  //
  // -----------------------------------------------------------------------
  
  
  using System;
  
  namespace PMDCP.Compression.Zlib
  {
  
      /// <summary>
      /// Describes how to flush the current deflate operation. 
      /// </summary>
      /// <remarks>
      /// The different FlushType values are useful when using a Deflate in a streaming application.
      /// </remarks>
      public enum FlushType
      {
          /// <summary>No flush at all.</summary>
          None = 0,
  
          /// <summary>Closes the current block, but doesn't flush it to
          /// the output. Used internally only in hypothetical
          /// scenarios.  This was supposed to be removed by Zlib, but it is
          /// still in use in some edge cases. 
          /// </summary>
          Partial,
  
          /// <summary>
          /// Use this during compression to specify that all pending output should be
          /// flushed to the output buffer and the output should be aligned on a byte
          /// boundary.  You might use this in a streaming communication scenario, so that
          /// the decompressor can get all input data available so far.  When using this
          /// with a ZlibCodec, <c>AvailableBytesIn</c> will be zero after the call if
          /// enough output space has been provided before the call.  Flushing will
          /// degrade compression and so it should be used only when necessary.
          /// </summary>
          Sync,
  
          /// <summary>
          /// Use this during compression to specify that all output should be flushed, as
          /// with <c>FlushType.Sync</c>, but also, the compression state should be reset
          /// so that decompression can restart from this point if previous compressed
          /// data has been damaged or if random access is desired.  Using
          /// <c>FlushType.Full</c> too often can significantly degrade the compression.
          /// </summary>
          Full,
  
          /// <summary>Signals the end of the compression/decompression stream.</summary>
          Finish,
      }
  
      internal enum BlockState
      {
          NeedMore = 0,       // block not completed, need more input or more output
          BlockDone,          // block flush performed
          FinishStarted,              // finish started, need only more output at next deflate
          FinishDone          // finish done, accept no more input or output
      }
  
      internal enum DeflateFlavor
      {
          Store,
          Fast,
          Slow
      }
  
      internal sealed class DeflateManager
      {
          private static readonly int MEM_LEVEL_MAX = 9;
          private static readonly int MEM_LEVEL_DEFAULT = 8;
  
          internal delegate BlockState CompressFunc(FlushType flush);
  
          internal class Config
          {
              // Use a faster search when the previous match is longer than this
              internal int GoodLength; // reduce lazy search above this match length
  
              // Attempt to find a better match only when the current match is
              // strictly smaller than this value. This mechanism is used only for
              // compression levels >= 4.  For levels 1,2,3: MaxLazy is actually
              // MaxInsertLength. (See DeflateFast)
  
              internal int MaxLazy;    // do not perform lazy search above this match length
  
              internal int NiceLength; // quit search above this match length
  
              // To speed up deflation, hash chains are never searched beyond this
              // length.  A higher limit improves compression ratio but degrades the speed.
  
              internal int MaxChainLength;
  
              internal DeflateFlavor Flavor;
  
              private Config(int goodLength, int maxLazy, int niceLength, int maxChainLength, DeflateFlavor flavor)
              {
                  this.GoodLength = goodLength;
                  this.MaxLazy = maxLazy;
                  this.NiceLength = niceLength;
                  this.MaxChainLength = maxChainLength;
                  this.Flavor = flavor;
              }
  
              public static Config Lookup(CompressionLevel level)
              {
                  return Table[(int)level];
              }
  
  
              static Config()
              {
                  Table = new Config[] {
                      new Config(0, 0, 0, 0, DeflateFlavor.Store),
                      new Config(4, 4, 8, 4, DeflateFlavor.Fast),
                      new Config(4, 5, 16, 8, DeflateFlavor.Fast),
                      new Config(4, 6, 32, 32, DeflateFlavor.Fast),
  
                      new Config(4, 4, 16, 16, DeflateFlavor.Slow),
                      new Config(8, 16, 32, 32, DeflateFlavor.Slow),
                      new Config(8, 16, 128, 128, DeflateFlavor.Slow),
                      new Config(8, 32, 128, 256, DeflateFlavor.Slow),
                      new Config(32, 128, 258, 1024, DeflateFlavor.Slow),
                      new Config(32, 258, 258, 4096, DeflateFlavor.Slow),
                  };
              }
  
              private static readonly Config[] Table;
          }
  
  
          private CompressFunc DeflateFunction;
  
          private static readonly System.String[] _ErrorMessage = new System.String[]
          {
              "need dictionary",
              "stream end",
              "",
              "file error",
              "stream error",
              "data error",
              "insufficient memory",
              "buffer error",
              "incompatible version",
              ""
          };
  
          // preset dictionary flag in zlib header
          private static readonly int PRESET_DICT = 0x20;
  
          private static readonly int INIT_STATE = 42;
          private static readonly int BUSY_STATE = 113;
          private static readonly int FINISH_STATE = 666;
  
          // The deflate compression method
          private static readonly int Z_DEFLATED = 8;
  
          private static readonly int STORED_BLOCK = 0;
          private static readonly int STATIC_TREES = 1;
          private static readonly int DYN_TREES = 2;
  
          // The three kinds of block type
          private static readonly int Z_BINARY = 0;
          private static readonly int Z_ASCII = 1;
          private static readonly int Z_UNKNOWN = 2;
  
          private static readonly int Buf_size = 8 * 2;
  
          private static readonly int MIN_MATCH = 3;
          private static readonly int MAX_MATCH = 258;
  
          private static readonly int MIN_LOOKAHEAD = (MAX_MATCH + MIN_MATCH + 1);
  
          private static readonly int HEAP_SIZE = (2 * InternalConstants.L_CODES + 1);
  
          private static readonly int END_BLOCK = 256;
  
          internal ZlibCodec _codec; // the zlib encoder/decoder
          internal int status;       // as the name implies
          internal byte[] pending;   // output still pending - waiting to be compressed
          internal int nextPending;  // index of next pending byte to output to the stream
          internal int pendingCount; // number of bytes in the pending buffer
  
          internal sbyte data_type;  // UNKNOWN, BINARY or ASCII
          internal int last_flush;   // value of flush param for previous deflate call
  
          internal int w_size;       // LZ77 window size (32K by default)
          internal int w_bits;       // log2(w_size)  (8..16)
          internal int w_mask;       // w_size - 1
  
          //internal byte[] dictionary;
          internal byte[] window;
  
          // Sliding window. Input bytes are read into the second half of the window,
          // and move to the first half later to keep a dictionary of at least wSize
          // bytes. With this organization, matches are limited to a distance of
          // wSize-MAX_MATCH bytes, but this ensures that IO is always
          // performed with a length multiple of the block size. 
          //
          // To do: use the user input buffer as sliding window.
  
          internal int window_size;
          // Actual size of window: 2*wSize, except when the user input buffer
          // is directly used as sliding window.
  
          internal short[] prev;
          // Link to older string with same hash index. To limit the size of this
          // array to 64K, this link is maintained only for the last 32K strings.
          // An index in this array is thus a window index modulo 32K.
  
          internal short[] head;  // Heads of the hash chains or NIL.
  
          internal int ins_h;     // hash index of string to be inserted
          internal int hash_size; // number of elements in hash table
          internal int hash_bits; // log2(hash_size)
          internal int hash_mask; // hash_size-1
  
          // Number of bits by which ins_h must be shifted at each input
          // step. It must be such that after MIN_MATCH steps, the oldest
          // byte no longer takes part in the hash key, that is:
          // hash_shift * MIN_MATCH >= hash_bits
          internal int hash_shift;
  
          // Window position at the beginning of the current output block. Gets
          // negative when the window is moved backwards.
  
          internal int block_start;
  
          Config config;
          internal int match_length;    // length of best match
          internal int prev_match;      // previous match
          internal int match_available; // set if previous match exists
          internal int strstart;        // start of string to insert into.....????
          internal int match_start;     // start of matching string
          internal int lookahead;       // number of valid bytes ahead in window
  
          // Length of the best match at previous step. Matches not greater than this
          // are discarded. This is used in the lazy match evaluation.
          internal int prev_length;
  
          // Insert new strings in the hash table only if the match length is not
          // greater than this length. This saves time but degrades compression.
          // max_insert_length is used only for compression levels <= 3.
  
          internal CompressionLevel compressionLevel; // compression level (1..9)
          internal CompressionStrategy compressionStrategy; // favor or force Huffman coding
  
  
          internal short[] dyn_ltree;         // literal and length tree
          internal short[] dyn_dtree;         // distance tree
          internal short[] bl_tree;           // Huffman tree for bit lengths
  
          internal Tree treeLiterals = new Tree();  // desc for literal tree
          internal Tree treeDistances = new Tree();  // desc for distance tree
          internal Tree treeBitLengths = new Tree(); // desc for bit length tree
  
          // number of codes at each bit length for an optimal tree
          internal short[] bl_count = new short[InternalConstants.MAX_BITS + 1];
  
          // heap used to build the Huffman trees
          internal int[] heap = new int[2 * InternalConstants.L_CODES + 1];
  
          internal int heap_len;              // number of elements in the heap
          internal int heap_max;              // element of largest frequency
  
          // The sons of heap[n] are heap[2*n] and heap[2*n+1]. heap[0] is not used.
          // The same heap array is used to build all trees.
  
          // Depth of each subtree used as tie breaker for trees of equal frequency
          internal sbyte[] depth = new sbyte[2 * InternalConstants.L_CODES + 1];
  
          internal int _lengthOffset;                 // index for literals or lengths 
  
  
          // Size of match buffer for literals/lengths.  There are 4 reasons for
          // limiting lit_bufsize to 64K:
          //   - frequencies can be kept in 16 bit counters
          //   - if compression is not successful for the first block, all input
          //     data is still in the window so we can still emit a stored block even
          //     when input comes from standard input.  (This can also be done for
          //     all blocks if lit_bufsize is not greater than 32K.)
          //   - if compression is not successful for a file smaller than 64K, we can
          //     even emit a stored file instead of a stored block (saving 5 bytes).
          //     This is applicable only for zip (not gzip or zlib).
          //   - creating new Huffman trees less frequently may not provide fast
          //     adaptation to changes in the input data statistics. (Take for
          //     example a binary file with poorly compressible code followed by
          //     a highly compressible string table.) Smaller buffer sizes give
          //     fast adaptation but have of course the overhead of transmitting
          //     trees more frequently.
  
          internal int lit_bufsize;
  
          internal int last_lit;     // running index in l_buf
  
          // Buffer for distances. To simplify the code, d_buf and l_buf have
          // the same number of elements. To use different lengths, an extra flag
          // array would be necessary.
  
          internal int _distanceOffset;        // index into pending; points to distance data??
  
          internal int opt_len;      // bit length of current block with optimal trees
          internal int static_len;   // bit length of current block with static trees
          internal int matches;      // number of string matches in current block
          internal int last_eob_len; // bit length of EOB code for last block
  
          // Output buffer. bits are inserted starting at the bottom (least
          // significant bits).
          internal short bi_buf;
  
          // Number of valid bits in bi_buf.  All bits above the last valid bit
          // are always zero.
          internal int bi_valid;
  
  
          internal DeflateManager()
          {
              dyn_ltree = new short[HEAP_SIZE * 2];
              dyn_dtree = new short[(2 * InternalConstants.D_CODES + 1) * 2]; // distance tree
              bl_tree = new short[(2 * InternalConstants.BL_CODES + 1) * 2]; // Huffman tree for bit lengths
          }
  
  
          // lm_init
          private void _InitializeLazyMatch()
          {
              window_size = 2 * w_size;
  
              // clear the hash - workitem 9063
              Array.Clear(head, 0, hash_size);
              //for (int i = 0; i < hash_size; i++) head[i] = 0;
  
              config = Config.Lookup(compressionLevel);
              SetDeflater();
  
              strstart = 0;
              block_start = 0;
              lookahead = 0;
              match_length = prev_length = MIN_MATCH - 1;
              match_available = 0;
              ins_h = 0;
          }
  
          // Initialize the tree data structures for a new zlib stream.
          private void _InitializeTreeData()
          {
              treeLiterals.dyn_tree = dyn_ltree;
              treeLiterals.staticTree = StaticTree.Literals;
  
              treeDistances.dyn_tree = dyn_dtree;
              treeDistances.staticTree = StaticTree.Distances;
  
              treeBitLengths.dyn_tree = bl_tree;
              treeBitLengths.staticTree = StaticTree.BitLengths;
  
              bi_buf = 0;
              bi_valid = 0;
              last_eob_len = 8; // enough lookahead for inflate
  
              // Initialize the first block of the first file:
              _InitializeBlocks();
          }
  
          internal void _InitializeBlocks()
          {
              // Initialize the trees.
              for (int i = 0; i < InternalConstants.L_CODES; i++)
                  dyn_ltree[i * 2] = 0;
              for (int i = 0; i < InternalConstants.D_CODES; i++)
                  dyn_dtree[i * 2] = 0;
              for (int i = 0; i < InternalConstants.BL_CODES; i++)
                  bl_tree[i * 2] = 0;
  
              dyn_ltree[END_BLOCK * 2] = 1;
              opt_len = static_len = 0;
              last_lit = matches = 0;
          }
  
          // Restore the heap property by moving down the tree starting at node k,
          // exchanging a node with the smallest of its two sons if necessary, stopping
          // when the heap property is re-established (each father smaller than its
          // two sons).
          internal void pqdownheap(short[] tree, int k)
          {
              int v = heap[k];
              int j = k << 1; // left son of k
              while (j <= heap_len)
              {
                  // Set j to the smallest of the two sons:
                  if (j < heap_len && _IsSmaller(tree, heap[j + 1], heap[j], depth))
                  {
                      j++;
                  }
                  // Exit if v is smaller than both sons
                  if (_IsSmaller(tree, v, heap[j], depth))
                      break;
  
                  // Exchange v with the smallest son
                  heap[k] = heap[j]; k = j;
                  // And continue down the tree, setting j to the left son of k
                  j <<= 1;
              }
              heap[k] = v;
          }
  
          internal static bool _IsSmaller(short[] tree, int n, int m, sbyte[] depth)
          {
              short tn2 = tree[n * 2];
              short tm2 = tree[m * 2];
              return (tn2 < tm2 || (tn2 == tm2 && depth[n] <= depth[m]));
          }
  
  
          // Scan a literal or distance tree to determine the frequencies of the codes
          // in the bit length tree.
          internal void scan_tree(short[] tree, int max_code)
          {
              int n; // iterates over all tree elements
              int prevlen = -1; // last emitted length
              int curlen; // length of current code
              int nextlen = (int)tree[0 * 2 + 1]; // length of next code
              int count = 0; // repeat count of the current code
              int max_count = 7; // max repeat count
              int min_count = 4; // min repeat count
  
              if (nextlen == 0)
              {
                  max_count = 138; min_count = 3;
              }
              tree[(max_code + 1) * 2 + 1] = (short)0x7fff; // guard //??
  
              for (n = 0; n <= max_code; n++)
              {
                  curlen = nextlen; nextlen = (int)tree[(n + 1) * 2 + 1];
                  if (++count < max_count && curlen == nextlen)
                  {
                      continue;
                  }
                  else if (count < min_count)
                  {
                      bl_tree[curlen * 2] = (short)(bl_tree[curlen * 2] + count);
                  }
                  else if (curlen != 0)
                  {
                      if (curlen != prevlen)
                          bl_tree[curlen * 2]++;
                      bl_tree[InternalConstants.REP_3_6 * 2]++;
                  }
                  else if (count <= 10)
                  {
                      bl_tree[InternalConstants.REPZ_3_10 * 2]++;
                  }
                  else
                  {
                      bl_tree[InternalConstants.REPZ_11_138 * 2]++;
                  }
                  count = 0; prevlen = curlen;
                  if (nextlen == 0)
                  {
  
gt:                     max_count = 138; min_count = 3;