// 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: <2011-August-03 19:52:15>//// ------------------------------------------------------------------//// 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 Ionic.Zlib{     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)                {                    max_count = 138; min_count = 3;                }                else if (curlen == nextlen)                {                    max_count = 6; min_count = 3;                }                else                {                    max_count = 7; min_count = 4;                }            }        }         // Construct the Huffman tree for the bit lengths and return the index in        // bl_order of the last bit length code to send.        internal int build_bl_tree()        {            int max_blindex; // index of last bit length code of non zero freq 

Lines 1–500 of 1882. Load more