1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151161171181191201211221231241251261271281291301311321331341351361371381391401411421431441451461471481491501511521531541551561571581591601611621631641651661671681691701711721731741751761771781791801811821831841851861871881891901911921931941951961971981992002012022032042052062072082092102112122132142152162172182192202212222232242252262272282292302312322332342352362372382392402412422432442452462472482492502512522532542552562572582592602612622632642652662672682692702712722732742752762772782792802812822832842852862872882892902912922932942952962972982993003013023033043053063073083093103113123133143153163173183193203213223233243253263273283293303313323333343353363373383393403413423433443453463473483493503513523533543553563573583593603613623633643653663673683693703713723733743753763773783793803813823833843853863873883893903913923933943953963973983994004014024034044054064074084094104114124134144154164174184194204214224234244254264274284294304314324334344354364374384394404414424434444454464474484494504514524534544554564574584594604614624634644654664674684694704714724734744754764774784794804814824834844854864874884894904914924934944954964974984995005015025035045055065075085095105115125135145155165175185195205215225235245255265275285295305315325335345355365375385395405415425435445455465475485495505515525535545555565575585595605615625635645655665675685695705715725735745755765775785795805815825835845855865875885895905915925935945955965975985996006016026036046056066076086096106116126136146156166176186196206216226236246256266276286296306316326336346356366376386396406416426436446456466476486496506516526536546556566576586596606616626636646656666676686696706716726736746756766776786796806816826836846856866876886896906916926936946956966976986997007017027037047057067077087097107117127137147157167177187197207217227237247257267277287297307317327337347357367377387397407417427437447457467477487497507517527537547557567577587597607617627637647657667677687697707717727737747757767777787797807817827837847857867877887897907917927937947957967977987998008018028038048058068078088098108118128138148158168178188198208218228238248258268278288298308318328338348358368378388398408418428438448458468478488498508518528538548558568578588598608618628638648658668678688698708718728738748758768778788798808818828838848858868878888898908918928938948958968978988999009019029039049059069079089099109119129139149159169179189199209219229239249259269279289299309319329339349359369379389399409419429439449459469479489499509519529539549559569579589599609619629639649659669679689699709719729739749759769779789799809819829839849859869879889899909919929939949959969979989991000100110021003100410051006100710081009101010111012101310141015101610171018101910201021102210231024102510261027102810291030103110321033103410351036103710381039104010411042104310441045104610471048104910501051105210531054105510561057105810591060106110621063106410651066106710681069107010711072107310741075107610771078107910801081108210831084108510861087108810891090109110921093109410951096109710981099110011011102110311041105110611071108110911101111111211131114111511161117111811191120112111221123112411251126112711281129113011311132113311341135113611371138113911401141114211431144114511461147114811491150115111521153115411551156115711581159116011611162116311641165116611671168116911701171117211731174117511761177117811791180118111821183118411851186118711881189119011911192119311941195119611971198119912001201120212031204120512061207120812091210121112121213121412151216121712181219122012211222122312241225122612271228122912301231123212331234123512361237123812391240124112421243124412451246124712481249125012511252125312541255125612571258125912601261126212631264126512661267126812691270127112721273127412751276127712781279128012811282128312841285128612871288128912901291129212931294129512961297129812991300130113021303130413051306130713081309131013111312131313141315131613171318131913201321132213231324132513261327132813291330133113321333133413351336133713381339134013411342134313441345134613471348134913501351135213531354135513561357135813591360136113621363136413651366136713681369137013711372137313741375137613771378137913801381138213831384138513861387138813891390139113921393139413951396139713981399140014011402140314041405140614071408140914101411141214131414141514161417141814191420142114221423142414251426142714281429143014311432143314341435143614371438143914401441144214431444144514461447144814491450145114521453145414551456145714581459146014611462146314641465146614671468146914701471147214731474147514761477147814791480148114821483148414851486148714881489149014911492149314941495149614971498149915001501150215031504150515061507150815091510151115121513151415151516151715181519152015211522152315241525152615271528152915301531153215331534153515361537153815391540154115421543154415451546154715481549155015511552155315541555155615571558155915601561156215631564156515661567156815691570157115721573157415751576157715781579158015811582158315841585158615871588158915901591159215931594159515961597159815991600160116021603160416051606160716081609161016111612161316141615161616171618161916201621162216231624162516261627162816291630163116321633163416351636163716381639164016411642164316441645164616471648164916501651165216531654165516561657165816591660166116621663166416651666166716681669167016711672167316741675167616771678167916801681168216831684168516861687168816891690169116921693169416951696169716981699170017011702170317041705170617071708170917101711171217131714171517161717171817191720172117221723172417251726172717281729173017311732173317341735173617371738173917401741174217431744174517461747174817491750175117521753175417551756175717581759176017611762176317641765176617671768176917701771177217731774177517761777177817791780178117821783178417851786178717881789179017911792179317941795179617971798179918001801180218031804180518061807180818091810181118121813181418151816181718181819182018211822182318241825182618271828182918301831183218331834183518361837183818391840184118421843184418451846184718481849185018511852185318541855185618571858185918601861186218631864186518661867186818691870187118721873187418751876187718781879188018811882188318841885188618871888188918901891189218931894189518961897189818991900190119021903190419051906190719081909191019111912191319141915191619171918191919201921192219231924192519261927192819291930193119321933193419351936193719381939194019411942194319441945194619471948194919501951195219531954195519561957195819591960196119621963196419651966196719681969197019711972197319741975197619771978197919801981198219831984198519861987 |
- // 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 SharpCompress.Compressors.Deflate
- {
- internal sealed partial class DeflateManager
- {
- // extra bits for each length code
- internal static readonly int[] ExtraLengthBits =
- {
- 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2,
- 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0
- };
- // extra bits for each distance code
- internal static readonly int[] ExtraDistanceBits =
- {
- 0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6,
- 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, 12, 12, 13, 13
- };
- 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
- }
- private const int MEM_LEVEL_MAX = 9;
- private const 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)
- {
- GoodLength = goodLength;
- MaxLazy = maxLazy;
- NiceLength = niceLength;
- MaxChainLength = maxChainLength;
- Flavor = flavor;
- }
- public static Config Lookup(CompressionLevel level)
- {
- return Table[(int)level];
- }
- static Config()
- {
- Table = new[]
- {
- 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 String[] _ErrorMessage =
- {
- "need dictionary",
- "stream end",
- "",
- "file error",
- "stream error",
- "data error",
- "insufficient memory",
- "buffer error",
- "incompatible version",
- ""
- };
- // preset dictionary flag in zlib header
- private const int PRESET_DICT = 0x20;
- private const int INIT_STATE = 42;
- private const int BUSY_STATE = 113;
- private const int FINISH_STATE = 666;
- // The deflate compression method
- private const int Z_DEFLATED = 8;
- private const int STORED_BLOCK = 0;
- private const int STATIC_TREES = 1;
- private const int DYN_TREES = 2;
- // The three kinds of block type
- private const int Z_BINARY = 0;
- private const int Z_ASCII = 1;
- private const int Z_UNKNOWN = 2;
- private const int Buf_size = 8 * 2;
- private const int MIN_MATCH = 3;
- private const int MAX_MATCH = 258;
- private const int MIN_LOOKAHEAD = (MAX_MATCH + MIN_MATCH + 1);
- private static readonly int HEAP_SIZE = (2 * InternalConstants.L_CODES + 1);
- private const 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.
- private short[] head; // Heads of the hash chains or NIL.
- private int ins_h; // hash index of string to be inserted
- private int hash_size; // number of elements in hash table
- private int hash_bits; // log2(hash_size)
- private 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
- private int hash_shift;
- // Window position at the beginning of the current output block. Gets
- // negative when the window is moved backwards.
- private int blockStart;
- private Config config;
- private int match_length; // length of best match
- private int prev_match; // previous match
- private int match_available; // set if previous match exists
- private int strstart; // start of string to insert into.....????
- private int match_start; // start of matching string
- private 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.
- private 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.
- private CompressionLevel compressionLevel; // compression level (1..9)
- private CompressionStrategy compressionStrategy; // favor or force Huffman coding
- private readonly short[] dyn_ltree; // literal and length tree
- private readonly short[] dyn_dtree; // distance tree
- private readonly short[] bl_tree; // Huffman tree for bit lengths
- private readonly Tree treeLiterals = new Tree(); // desc for literal tree
- private readonly Tree treeDistances = new Tree(); // desc for distance tree
- private readonly Tree treeBitLengths = new Tree(); // desc for bit length tree
- // number of codes at each bit length for an optimal tree
- private readonly short[] bl_count = new short[InternalConstants.MAX_BITS + 1];
- // heap used to build the Huffman trees
- private readonly int[] heap = new int[2 * InternalConstants.L_CODES + 1];
- private int heap_len; // number of elements in the heap
- private 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
- private readonly sbyte[] depth = new sbyte[2 * InternalConstants.L_CODES + 1];
- private 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;
- blockStart = 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 ScanTree(short[] tree, int maxCode)
- {
- int n; // iterates over all tree elements
- int prevlen = -1; // last emitted length
- int curlen; // length of current code
- int nextlen = 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[(maxCode + 1) * 2 + 1] = 0x7fff; // guard //??
- for (n = 0; n <= maxCode; n++)
- {
- curlen = nextlen;
- nextlen = tree[(n + 1) * 2 + 1];
- if (++count < max_count && curlen == nextlen)
- {
- continue;
- }
- 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 BuildBlTree()
- {
- int max_blindex; // index of last bit length code of non zero freq
- // Determine the bit length frequencies for literal and distance trees
- ScanTree(dyn_ltree, treeLiterals.max_code);
- ScanTree(dyn_dtree, treeDistances.max_code);
- // Build the bit length tree:
- treeBitLengths.build_tree(this);
- // opt_len now includes the length of the tree representations, except
- // the lengths of the bit lengths codes and the 5+5+4 bits for the counts.
- // Determine the number of bit length codes to send. The pkzip format
- // requires that at least 4 bit length codes be sent. (appnote.txt says
- // 3 but the actual value used is 4.)
- for (max_blindex = InternalConstants.BL_CODES - 1; max_blindex >= 3; max_blindex--)
- {
- if (bl_tree[Tree.bl_order[max_blindex] * 2 + 1] != 0)
- {
- break;
- }
- }
- // Update opt_len to include the bit length tree and counts
- opt_len += 3 * (max_blindex + 1) + 5 + 5 + 4;
- return max_blindex;
- }
- // Send the header for a block using dynamic Huffman trees: the counts, the
- // lengths of the bit length codes, the literal tree and the distance tree.
- // IN assertion: lcodes >= 257, dcodes >= 1, blcodes >= 4.
- internal void send_all_trees(int lcodes, int dcodes, int blcodes)
- {
- int rank; // index in bl_order
- send_bits(lcodes - 257, 5); // not +255 as stated in appnote.txt
- send_bits(dcodes - 1, 5);
- send_bits(blcodes - 4, 4); // not -3 as stated in appnote.txt
- for (rank = 0; rank < blcodes; rank++)
- {
- send_bits(bl_tree[Tree.bl_order[rank] * 2 + 1], 3);
- }
- send_tree(dyn_ltree, lcodes - 1); // literal tree
- send_tree(dyn_dtree, dcodes - 1); // distance tree
- }
- // Send a literal or distance tree in compressed form, using the codes in
- // bl_tree.
- internal void send_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 = 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;
- }
- for (n = 0; n <= max_code; n++)
- {
- curlen = nextlen;
- nextlen = tree[(n + 1) * 2 + 1];
- if (++count < max_count && curlen == nextlen)
- {
- continue;
- }
- if (count < min_count)
- {
- do
- {
- send_code(curlen, bl_tree);
- }
- while (--count != 0);
- }
- else if (curlen != 0)
- {
- if (curlen != prevlen)
- {
- send_code(curlen, bl_tree);
- count--;
- }
- send_code(InternalConstants.REP_3_6, bl_tree);
- send_bits(count - 3, 2);
- }
- else if (count <= 10)
- {
- send_code(InternalConstants.REPZ_3_10, bl_tree);
- send_bits(count - 3, 3);
- }
- else
- {
- send_code(InternalConstants.REPZ_11_138, bl_tree);
- send_bits(count - 11, 7);
- }
- 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;
- }
- }
- }
- // Output a block of bytes on the stream.
- // IN assertion: there is enough room in pending_buf.
- private void put_bytes(byte[] p, int start, int len)
- {
- Array.Copy(p, start, pending, pendingCount, len);
- pendingCount += len;
- }
- #if NOTNEEDED
- private void put_byte(byte c)
- {
- pending[pendingCount++] = c;
- }
- internal void put_short(int b)
- {
- unchecked
- {
- pending[pendingCount++] = (byte)b;
- pending[pendingCount++] = (byte)(b >> 8);
- }
- }
- internal void putShortMSB(int b)
- {
- unchecked
- {
- pending[pendingCount++] = (byte)(b >> 8);
- pending[pendingCount++] = (byte)b;
- }
- }
- #endif
- internal void send_code(int c, short[] tree)
- {
- int c2 = c * 2;
- send_bits((tree[c2] & 0xffff), (tree[c2 + 1] & 0xffff));
- }
- #pragma warning disable 675 // workaround for Visual Studio 2015 compiler bug: https://github.com/dotnet/roslyn/issues/4027
- internal void send_bits(int value, int length)
- {
- int len = length;
- unchecked
- {
- if (bi_valid > Buf_size - len)
- {
- //int val = value;
- // bi_buf |= (val << bi_valid);
- bi_buf |= (short)((value << bi_valid) & 0xffff);
- //put_short(bi_buf);
- pending[pendingCount++] = (byte)bi_buf;
- pending[pendingCount++] = (byte)(bi_buf >> 8);
- bi_buf = (short)((uint)value >> (Buf_size - bi_valid));
- bi_valid += len - Buf_size;
- }
- else
- {
- // bi_buf |= (value) << bi_valid;
- bi_buf |= (short)((value << bi_valid) & 0xffff);
- bi_valid += len;
- }
- }
- }
- #pragma warning restore 675
- // Send one empty static block to give enough lookahead for inflate.
- // This takes 10 bits, of which 7 may remain in the bit buffer.
- // The current inflate code requires 9 bits of lookahead. If the
- // last two codes for the previous block (real code plus EOB) were coded
- // on 5 bits or less, inflate may have only 5+3 bits of lookahead to decode
- // the last real code. In this case we send two empty static blocks instead
- // of one. (There are no problems if the previous block is stored or fixed.)
- // To simplify the code, we assume the worst case of last real code encoded
- // on one bit only.
- internal void _tr_align()
- {
- send_bits(STATIC_TREES << 1, 3);
- send_code(END_BLOCK, StaticTree.lengthAndLiteralsTreeCodes);
- bi_flush();
- // Of the 10 bits for the empty block, we have already sent
- // (10 - bi_valid) bits. The lookahead for the last real code (before
- // the EOB of the previous block) was thus at least one plus the length
- // of the EOB plus what we have just sent of the empty static block.
- if (1 + last_eob_len + 10 - bi_valid < 9)
- {
- send_bits(STATIC_TREES << 1, 3);
- send_code(END_BLOCK, StaticTree.lengthAndLiteralsTreeCodes);
- bi_flush();
- }
- last_eob_len = 7;
- }
- // Save the match info and tally the frequency counts. Return true if
- // the current block must be flushed.
- internal bool _tr_tally(int dist, int lc)
- {
- pending[_distanceOffset + last_lit * 2] = unchecked((byte)((uint)dist >> 8));
- pending[_distanceOffset + last_lit * 2 + 1] = unchecked((byte)dist);
- pending[_lengthOffset + last_lit] = unchecked((byte)lc);
- last_lit++;
- if (dist == 0)
- {
- // lc is the unmatched char
- dyn_ltree[lc * 2]++;
- }
- else
- {
- matches++;
- // Here, lc is the match length - MIN_MATCH
- dist--; // dist = match distance - 1
- dyn_ltree[(Tree.LengthCode[lc] + InternalConstants.LITERALS + 1) * 2]++;
- dyn_dtree[Tree.DistanceCode(dist) * 2]++;
- }
- if ((last_lit & 0x1fff) == 0 && (int)compressionLevel > 2)
- {
- // Compute an upper bound for the compressed length
- int out_length = last_lit << 3;
- int in_length = strstart - blockStart;
- int dcode;
- for (dcode = 0; dcode < InternalConstants.D_CODES; dcode++)
- {
- out_length =
- (int)(out_length + dyn_dtree[dcode * 2] * (5L + ExtraDistanceBits[dcode]));
- }
- out_length >>= 3;
- if ((matches < (last_lit / 2)) && out_length < in_length / 2)
- {
- return true;
- }
- }
- return (last_lit == lit_bufsize - 1) || (last_lit == lit_bufsize);
- // dinoch - wraparound?
- // We avoid equality with lit_bufsize because of wraparound at 64K
- // on 16 bit machines and because stored blocks are restricted to
- // 64K-1 bytes.
- }
- // Send the block data compressed using the given Huffman trees
- internal void send_compressed_block(short[] ltree, short[] dtree)
- {
- int distance; // distance of matched string
- int lc; // match length or unmatched char (if dist == 0)
- int lx = 0; // running index in l_buf
- int code; // the code to send
- int extra; // number of extra bits to send
- if (last_lit != 0)
- {
- do
- {
- int ix = _distanceOffset + lx * 2;
- distance = ((pending[ix] << 8) & 0xff00) |
- (pending[ix + 1] & 0xff);
- lc = (pending[_lengthOffset + lx]) & 0xff;
- lx++;
- if (distance == 0)
- {
- send_code(lc, ltree); // send a literal byte
- }
- else
- {
- // literal or match pair
- // Here, lc is the match length - MIN_MATCH
- code = Tree.LengthCode[lc];
- // send the length code
- send_code(code + InternalConstants.LITERALS + 1, ltree);
- extra = ExtraLengthBits[code];
- if (extra != 0)
- {
- // send the extra length bits
- lc -= Tree.LengthBase[code];
- send_bits(lc, extra);
- }
- distance--; // dist is now the match distance - 1
- code = Tree.DistanceCode(distance);
- // send the distance code
- send_code(code, dtree);
- extra = ExtraDistanceBits[code];
- if (extra != 0)
- {
- // send the extra distance bits
- distance -= Tree.DistanceBase[code];
- send_bits(distance, extra);
- }
- }
- // Check that the overlay between pending and d_buf+l_buf is ok:
- }
- while (lx < last_lit);
- }
- send_code(END_BLOCK, ltree);
- last_eob_len = ltree[END_BLOCK * 2 + 1];
- }
- // Set the data type to ASCII or BINARY, using a crude approximation:
- // binary if more than 20% of the bytes are <= 6 or >= 128, ascii otherwise.
- // IN assertion: the fields freq of dyn_ltree are set and the total of all
- // frequencies does not exceed 64K (to fit in an int on 16 bit machines).
- internal void set_data_type()
- {
- int n = 0;
- int ascii_freq = 0;
- int bin_freq = 0;
- while (n < 7)
- {
- bin_freq += dyn_ltree[n * 2];
- n++;
- }
- while (n < 128)
- {
- ascii_freq += dyn_ltree[n * 2];
- n++;
- }
- while (n < InternalConstants.LITERALS)
- {
- bin_freq += dyn_ltree[n * 2];
- n++;
- }
- data_type = (sbyte)(bin_freq > (ascii_freq >> 2) ? Z_BINARY : Z_ASCII);
- }
- // Flush the bit buffer, keeping at most 7 bits in it.
- internal void bi_flush()
- {
- if (bi_valid == 16)
- {
- pending[pendingCount++] = (byte)bi_buf;
- pending[pendingCount++] = (byte)(bi_buf >> 8);
- bi_buf = 0;
- bi_valid = 0;
- }
- else if (bi_valid >= 8)
- {
- //put_byte((byte)bi_buf);
- pending[pendingCount++] = (byte)bi_buf;
- bi_buf >>= 8;
- bi_valid -= 8;
- }
- }
- // Flush the bit buffer and align the output on a byte boundary
- internal void bi_windup()
- {
- if (bi_valid > 8)
- {
- pending[pendingCount++] = (byte)bi_buf;
- pending[pendingCount++] = (byte)(bi_buf >> 8);
- }
- else if (bi_valid > 0)
- {
- //put_byte((byte)bi_buf);
- pending[pendingCount++] = (byte)bi_buf;
- }
- bi_buf = 0;
- bi_valid = 0;
- }
- // Copy a stored block, storing first the length and its
- // one's complement if requested.
- internal void copy_block(int buf, int len, bool header)
- {
- bi_windup(); // align on byte boundary
- last_eob_len = 8; // enough lookahead for inflate
- if (header)
- {
- unchecked
- {
- //put_short((short)len);
- pending[pendingCount++] = (byte)len;
- pending[pendingCount++] = (byte)(len >> 8);
- //put_short((short)~len);
- pending[pendingCount++] = (byte)~len;
- pending[pendingCount++] = (byte)(~len >> 8);
- }
- }
- put_bytes(window, buf, len);
- }
- internal void flush_block_only(bool eof)
- {
- _tr_flush_block(blockStart >= 0 ? blockStart : -1, strstart - blockStart, eof);
- blockStart = strstart;
- _codec.flush_pending();
- }
- // Copy without compression as much as possible from the input stream, return
- // the current block state.
- // This function does not insert new strings in the dictionary since
- // uncompressible data is probably not useful. This function is used
- // only for the level=0 compression option.
- // NOTE: this function should be optimized to avoid extra copying from
- // window to pending_buf.
- internal BlockState DeflateNone(FlushType flush)
- {
- // Stored blocks are limited to 0xffff bytes, pending is limited
- // to pending_buf_size, and each stored block has a 5 byte header:
- int max_block_size = 0xffff;
- int max_start;
- if (max_block_size > pending.Length - 5)
- {
- max_block_size = pending.Length - 5;
- }
- // Copy as much as possible from input to output:
- while (true)
- {
- // Fill the window as much as possible:
- if (lookahead <= 1)
- {
- _fillWindow();
- if (lookahead == 0 && flush == FlushType.None)
- {
- return BlockState.NeedMore;
- }
- if (lookahead == 0)
- {
- break; // flush the current block
- }
- }
- strstart += lookahead;
- lookahead = 0;
- // Emit a stored block if pending will be full:
- max_start = blockStart + max_block_size;
- if (strstart == 0 || strstart >= max_start)
- {
- // strstart == 0 is possible when wraparound on 16-bit machine
- lookahead = strstart - max_start;
- strstart = max_start;
- flush_block_only(false);
- if (_codec.AvailableBytesOut == 0)
- {
- return BlockState.NeedMore;
- }
- }
- // Flush if we may have to slide, otherwise block_start may become
- // negative and the data will be gone:
- if (strstart - blockStart >= w_size - MIN_LOOKAHEAD)
- {
- flush_block_only(false);
- if (_codec.AvailableBytesOut == 0)
- {
- return BlockState.NeedMore;
- }
- }
- }
- flush_block_only(flush == FlushType.Finish);
- if (_codec.AvailableBytesOut == 0)
- {
- return (flush == FlushType.Finish) ? BlockState.FinishStarted : BlockState.NeedMore;
- }
- return flush == FlushType.Finish ? BlockState.FinishDone : BlockState.BlockDone;
- }
- // Send a stored block
- internal void _tr_stored_block(int buf, int stored_len, bool eof)
- {
- send_bits((STORED_BLOCK << 1) + (eof ? 1 : 0), 3); // send block type
- copy_block(buf, stored_len, true); // with header
- }
- // Determine the best encoding for the current block: dynamic trees, static
- // trees or store, and output the encoded block to the zip file.
- internal void _tr_flush_block(int buf, int stored_len, bool eof)
- {
- int opt_lenb, static_lenb; // opt_len and static_len in bytes
- int max_blindex = 0; // index of last bit length code of non zero freq
- // Build the Huffman trees unless a stored block is forced
- if (compressionLevel > 0)
- {
- // Check if the file is ascii or binary
- if (data_type == Z_UNKNOWN)
- {
- set_data_type();
- }
- // Construct the literal and distance trees
- treeLiterals.build_tree(this);
- treeDistances.build_tree(this);
- // At this point, opt_len and static_len are the total bit lengths of
- // the compressed block data, excluding the tree representations.
- // Build the bit length tree for the above two trees, and get the index
- // in bl_order of the last bit length code to send.
- max_blindex = BuildBlTree();
- // Determine the best encoding. Compute first the block length in bytes
- opt_lenb = (opt_len + 3 + 7) >> 3;
- static_lenb = (static_len + 3 + 7) >> 3;
- if (static_lenb <= opt_lenb)
- {
- opt_lenb = static_lenb;
- }
- }
- else
- {
- opt_lenb = static_lenb = stored_len + 5; // force a stored block
- }
- if (stored_len + 4 <= opt_lenb && buf != -1)
- {
- // 4: two words for the lengths
- // The test buf != NULL is only necessary if LIT_BUFSIZE > WSIZE.
- // Otherwise we can't have processed more than WSIZE input bytes since
- // the last block flush, because compression would have been
- // successful. If LIT_BUFSIZE <= WSIZE, it is never too late to
- // transform a block into a stored block.
- _tr_stored_block(buf, stored_len, eof);
- }
- else if (static_lenb == opt_lenb)
- {
- send_bits((STATIC_TREES << 1) + (eof ? 1 : 0), 3);
- send_compressed_block(StaticTree.lengthAndLiteralsTreeCodes, StaticTree.distTreeCodes);
- }
- else
- {
- send_bits((DYN_TREES << 1) + (eof ? 1 : 0), 3);
- send_all_trees(treeLiterals.max_code + 1, treeDistances.max_code + 1, max_blindex + 1);
- send_compressed_block(dyn_ltree, dyn_dtree);
- }
- // The above check is made mod 2^32, for files larger than 512 MB
- // and uLong implemented on 32 bits.
- _InitializeBlocks();
- if (eof)
- {
- bi_windup();
- }
- }
- // Fill the window when the lookahead becomes insufficient.
- // Updates strstart and lookahead.
- //
- // IN assertion: lookahead < MIN_LOOKAHEAD
- // OUT assertions: strstart <= window_size-MIN_LOOKAHEAD
- // At least one byte has been read, or avail_in == 0; reads are
- // performed for at least two bytes (required for the zip translate_eol
- // option -- not supported here).
- private void _fillWindow()
- {
- int n, m;
- int p;
- int more; // Amount of free space at the end of the window.
- do
- {
- more = (window_size - lookahead - strstart);
- // Deal with !@#$% 64K limit:
- if (more == 0 && strstart == 0 && lookahead == 0)
- {
- more = w_size;
- }
- else if (more == -1)
- {
- // Very unlikely, but possible on 16 bit machine if strstart == 0
- // and lookahead == 1 (input done one byte at time)
- more--;
- // 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.
- }
- else if (strstart >= w_size + w_size - MIN_LOOKAHEAD)
- {
- Array.Copy(window, w_size, window, 0, w_size);
- match_start -= w_size;
- strstart -= w_size; // we now have strstart >= MAX_DIST
- blockStart -= w_size;
- // Slide the hash table (could be avoided with 32 bit values
- // at the expense of memory usage). We slide even when level == 0
- // to keep the hash table consistent if we switch back to level > 0
- // later. (Using level 0 permanently is not an optimal usage of
- // zlib, so we don't care about this pathological case.)
- n = hash_size;
- p = n;
- do
- {
- m = (head[--p] & 0xffff);
- head[p] = (short)((m >= w_size) ? (m - w_size) : 0);
- }
- while (--n != 0);
- n = w_size;
- p = n;
- do
- {
- m = (prev[--p] & 0xffff);
- prev[p] = (short)((m >= w_size) ? (m - w_size) : 0);
- // If n is not on any hash chain, prev[n] is garbage but
- // its value will never be used.
- }
- while (--n != 0);
- more += w_size;
- }
- if (_codec.AvailableBytesIn == 0)
- {
- return;
- }
- // If there was no sliding:
- // strstart <= WSIZE+MAX_DIST-1 && lookahead <= MIN_LOOKAHEAD - 1 &&
- // more == window_size - lookahead - strstart
- // => more >= window_size - (MIN_LOOKAHEAD-1 + WSIZE + MAX_DIST-1)
- // => more >= window_size - 2*WSIZE + 2
- // In the BIG_MEM or MMAP case (not yet supported),
- // window_size == input_size + MIN_LOOKAHEAD &&
- // strstart + s->lookahead <= input_size => more >= MIN_LOOKAHEAD.
- // Otherwise, window_size == 2*WSIZE so more >= 2.
- // If there was sliding, more >= WSIZE. So in all cases, more >= 2.
- n = _codec.read_buf(window, strstart + lookahead, more);
- lookahead += n;
- // Initialize the hash value now that we have some input:
- if (lookahead >= MIN_MATCH)
- {
- ins_h = window[strstart] & 0xff;
- ins_h = (((ins_h) << hash_shift) ^ (window[strstart + 1] & 0xff)) & hash_mask;
- }
- // 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 (lookahead < MIN_LOOKAHEAD && _codec.AvailableBytesIn != 0);
- }
- // 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.
- internal BlockState DeflateFast(FlushType flush)
- {
- // short hash_head = 0; // head of the hash chain
- int hash_head = 0; // head of the hash chain
- bool bflush; // set if current block must be flushed
- 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 (lookahead < MIN_LOOKAHEAD)
- {
- _fillWindow();
- if (lookahead < MIN_LOOKAHEAD && flush == FlushType.None)
- {
- return BlockState.NeedMore;
- }
- if (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:
- if (lookahead >= MIN_MATCH)
- {
- ins_h = (((ins_h) << hash_shift) ^ (window[(strstart) + (MIN_MATCH - 1)] & 0xff)) & hash_mask;
- // prev[strstart&w_mask]=hash_head=head[ins_h];
- hash_head = (head[ins_h] & 0xffff);
- prev[strstart & w_mask] = head[ins_h];
- head[ins_h] = unchecked((short)strstart);
- }
- // Find the longest match, discarding those <= prev_length.
- // At this point we have always match_length < MIN_MATCH
- if (hash_head != 0L && ((strstart - hash_head) & 0xffff) <= w_size - MIN_LOOKAHEAD)
- {
- // 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).
- if (compressionStrategy != CompressionStrategy.HuffmanOnly)
- {
- match_length = longest_match(hash_head);
- }
- // longest_match() sets match_start
- }
- if (match_length >= MIN_MATCH)
- {
- // check_match(strstart, match_start, match_length);
- bflush = _tr_tally(strstart - match_start, match_length - MIN_MATCH);
- lookahead -= 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 (match_length <= config.MaxLazy && lookahead >= MIN_MATCH)
- {
- match_length--; // string at strstart already in hash table
- do
- {
- strstart++;
- ins_h = ((ins_h << hash_shift) ^ (window[(strstart) + (MIN_MATCH - 1)] & 0xff)) & hash_mask;
- // prev[strstart&w_mask]=hash_head=head[ins_h];
- hash_head = (head[ins_h] & 0xffff);
- prev[strstart & w_mask] = head[ins_h];
- head[ins_h] = unchecked((short)strstart);
- // strstart never exceeds WSIZE-MAX_MATCH, so there are
- // always MIN_MATCH bytes ahead.
- }
- while (--match_length != 0);
- strstart++;
- }
- else
- {
- strstart += match_length;
- match_length = 0;
- ins_h = window[strstart] & 0xff;
- ins_h = (((ins_h) << hash_shift) ^ (window[strstart + 1] & 0xff)) & hash_mask;
- // 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
- bflush = _tr_tally(0, window[strstart] & 0xff);
- lookahead--;
- strstart++;
- }
- if (bflush)
- {
- flush_block_only(false);
- if (_codec.AvailableBytesOut == 0)
- {
- return BlockState.NeedMore;
- }
- }
- }
- flush_block_only(flush == FlushType.Finish);
- if (_codec.AvailableBytesOut == 0)
- {
- if (flush == FlushType.Finish)
- {
- return BlockState.FinishStarted;
- }
- return BlockState.NeedMore;
- }
- return flush == FlushType.Finish ? BlockState.FinishDone : BlockState.BlockDone;
- }
- // Same as above, but achieves better compression. We use a lazy
- // evaluation for matches: a match is finally adopted only if there is
- // no better match at the next window position.
- internal BlockState DeflateSlow(FlushType flush)
- {
- // short hash_head = 0; // head of hash chain
- int hash_head = 0; // head of hash chain
- bool bflush; // set if current block must be flushed
- // 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 (lookahead < MIN_LOOKAHEAD)
- {
- _fillWindow();
- if (lookahead < MIN_LOOKAHEAD && flush == FlushType.None)
- {
- return BlockState.NeedMore;
- }
- if (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:
- if (lookahead >= MIN_MATCH)
- {
- ins_h = (((ins_h) << hash_shift) ^ (window[(strstart) + (MIN_MATCH - 1)] & 0xff)) & hash_mask;
- // prev[strstart&w_mask]=hash_head=head[ins_h];
- hash_head = (head[ins_h] & 0xffff);
- prev[strstart & w_mask] = head[ins_h];
- head[ins_h] = unchecked((short)strstart);
- }
- // Find the longest match, discarding those <= prev_length.
- prev_length = match_length;
- prev_match = match_start;
- match_length = MIN_MATCH - 1;
- if (hash_head != 0 && prev_length < config.MaxLazy &&
- ((strstart - hash_head) & 0xffff) <= w_size - MIN_LOOKAHEAD)
- {
- // 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).
- if (compressionStrategy != CompressionStrategy.HuffmanOnly)
- {
- match_length = longest_match(hash_head);
- }
- // longest_match() sets match_start
- if (match_length <= 5 && (compressionStrategy == CompressionStrategy.Filtered ||
- (match_length == MIN_MATCH && strstart - match_start > 4096)))
- {
- // If prev_match is also MIN_MATCH, match_start is garbage
- // but we will ignore the current match anyway.
- match_length = MIN_MATCH - 1;
- }
- }
- // If there was a match at the previous step and the current
- // match is not better, output the previous match:
- if (prev_length >= MIN_MATCH && match_length <= prev_length)
- {
- int max_insert = strstart + lookahead - MIN_MATCH;
- // Do not insert strings in hash table beyond this.
- // check_match(strstart-1, prev_match, prev_length);
- bflush = _tr_tally(strstart - 1 - prev_match, prev_length - MIN_MATCH);
- // 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.
- lookahead -= (prev_length - 1);
- prev_length -= 2;
- do
- {
- if (++strstart <= max_insert)
- {
- ins_h = (((ins_h) << hash_shift) ^ (window[(strstart) + (MIN_MATCH - 1)] & 0xff)) &
- hash_mask;
- //prev[strstart&w_mask]=hash_head=head[ins_h];
- hash_head = (head[ins_h] & 0xffff);
- prev[strstart & w_mask] = head[ins_h];
- head[ins_h] = unchecked((short)strstart);
- }
- }
- while (--prev_length != 0);
- match_available = 0;
- match_length = MIN_MATCH - 1;
- strstart++;
- if (bflush)
- {
- flush_block_only(false);
- if (_codec.AvailableBytesOut == 0)
- {
- return BlockState.NeedMore;
- }
- }
- }
- else if (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.
- bflush = _tr_tally(0, window[strstart - 1] & 0xff);
- if (bflush)
- {
- flush_block_only(false);
- }
- strstart++;
- lookahead--;
- if (_codec.AvailableBytesOut == 0)
- {
- return BlockState.NeedMore;
- }
- }
- else
- {
- // There is no previous match to compare with, wait for
- // the next step to decide.
- match_available = 1;
- strstart++;
- lookahead--;
- }
- }
- if (match_available != 0)
- {
- bflush = _tr_tally(0, window[strstart - 1] & 0xff);
- match_available = 0;
- }
- flush_block_only(flush == FlushType.Finish);
- if (_codec.AvailableBytesOut == 0)
- {
- if (flush == FlushType.Finish)
- {
- return BlockState.FinishStarted;
- }
- return BlockState.NeedMore;
- }
- return flush == FlushType.Finish ? BlockState.FinishDone : BlockState.BlockDone;
- }
- internal int longest_match(int cur_match)
- {
- int chain_length = config.MaxChainLength; // max hash chain length
- int scan = strstart; // current string
- int match; // matched string
- int len; // length of current match
- int best_len = prev_length; // best match length so far
- int limit = strstart > (w_size - MIN_LOOKAHEAD) ? strstart - (w_size - MIN_LOOKAHEAD) : 0;
- int niceLength = config.NiceLength;
- // Stop when cur_match becomes <= limit. To simplify the code,
- // we prevent matches with the string of window index 0.
- int wmask = w_mask;
- int strend = strstart + MAX_MATCH;
- byte scan_end1 = window[scan + best_len - 1];
- byte scan_end = window[scan + best_len];
- // The code is optimized for HASH_BITS >= 8 and MAX_MATCH-2 multiple of 16.
- // It is easy to get rid of this optimization if necessary.
- // Do not waste too much time if we already have a good match:
- if (prev_length >= config.GoodLength)
- {
- chain_length >>= 2;
- }
- // Do not look for matches beyond the end of the input. This is necessary
- // to make deflate deterministic.
- if (niceLength > lookahead)
- {
- niceLength = lookahead;
- }
- do
- {
- match = cur_match;
- // Skip to next match if the match length cannot increase
- // or if the match length is less than 2:
- if (window[match + best_len] != scan_end ||
- window[match + best_len - 1] != scan_end1 ||
- window[match] != window[scan] ||
- window[++match] != window[scan + 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 += 2;
- match++;
- // We check for insufficient lookahead only every 8th comparison;
- // the 256th check will be made at strstart+258.
- do
- {
- }
- while (window[++scan] == window[++match] &&
- window[++scan] == window[++match] &&
- window[++scan] == window[++match] &&
- window[++scan] == window[++match] &&
- window[++scan] == window[++match] &&
- window[++scan] == window[++match] &&
- window[++scan] == window[++match] &&
- window[++scan] == window[++match] && scan < strend);
- len = MAX_MATCH - (strend - scan);
- scan = strend - MAX_MATCH;
- if (len > best_len)
- {
- match_start = cur_match;
- best_len = len;
- if (len >= niceLength)
- {
- break;
- }
- scan_end1 = window[scan + best_len - 1];
- scan_end = window[scan + best_len];
- }
- }
- while ((cur_match = (prev[cur_match & wmask] & 0xffff)) > limit && --chain_length != 0);
- if (best_len <= lookahead)
- {
- return best_len;
- }
- return lookahead;
- }
- private bool Rfc1950BytesEmitted;
- internal bool WantRfc1950HeaderBytes { get; set; } = true;
- internal int Initialize(ZlibCodec codec, CompressionLevel level)
- {
- return Initialize(codec, level, ZlibConstants.WindowBitsMax);
- }
- internal int Initialize(ZlibCodec codec, CompressionLevel level, int bits)
- {
- return Initialize(codec, level, bits, MEM_LEVEL_DEFAULT, CompressionStrategy.Default);
- }
- internal int Initialize(ZlibCodec codec, CompressionLevel level, int bits,
- CompressionStrategy compressionStrategy)
- {
- return Initialize(codec, level, bits, MEM_LEVEL_DEFAULT, compressionStrategy);
- }
- internal int Initialize(ZlibCodec codec, CompressionLevel level, int windowBits, int memLevel,
- CompressionStrategy strategy)
- {
- _codec = codec;
- _codec.Message = null;
- // validation
- if (windowBits < 9 || windowBits > 15)
- {
- throw new ZlibException("windowBits must be in the range 9..15.");
- }
- if (memLevel < 1 || memLevel > MEM_LEVEL_MAX)
- {
- throw new ZlibException(String.Format("memLevel must be in the range 1.. {0}", MEM_LEVEL_MAX));
- }
- _codec.dstate = this;
- w_bits = windowBits;
- w_size = 1 << w_bits;
- w_mask = w_size - 1;
- hash_bits = memLevel + 7;
- hash_size = 1 << hash_bits;
- hash_mask = hash_size - 1;
- hash_shift = ((hash_bits + MIN_MATCH - 1) / MIN_MATCH);
- window = new byte[w_size * 2];
- prev = new short[w_size];
- head = new short[hash_size];
- // for memLevel==8, this will be 16384, 16k
- lit_bufsize = 1 << (memLevel + 6);
- // Use a single array as the buffer for data pending compression,
- // the output distance codes, and the output length codes (aka tree).
- // orig comment: This works just fine since the average
- // output size for (length,distance) codes is <= 24 bits.
- pending = new byte[lit_bufsize * 4];
- _distanceOffset = lit_bufsize;
- _lengthOffset = (1 + 2) * lit_bufsize;
- // So, for memLevel 8, the length of the pending buffer is 65536. 64k.
- // The first 16k are pending bytes.
- // The middle slice, of 32k, is used for distance codes.
- // The final 16k are length codes.
- compressionLevel = level;
- compressionStrategy = strategy;
- Reset();
- return ZlibConstants.Z_OK;
- }
- internal void Reset()
- {
- _codec.TotalBytesIn = _codec.TotalBytesOut = 0;
- _codec.Message = null;
- //strm.data_type = Z_UNKNOWN;
- pendingCount = 0;
- nextPending = 0;
- Rfc1950BytesEmitted = false;
- status = (WantRfc1950HeaderBytes) ? INIT_STATE : BUSY_STATE;
- _codec._Adler32 = Adler.Adler32(0, null, 0, 0);
- last_flush = (int)FlushType.None;
- _InitializeTreeData();
- _InitializeLazyMatch();
- }
- internal int End()
- {
- if (status != INIT_STATE && status != BUSY_STATE && status != FINISH_STATE)
- {
- return ZlibConstants.Z_STREAM_ERROR;
- }
- // Deallocate in reverse order of allocations:
- pending = null;
- head = null;
- prev = null;
- window = null;
- // free
- // dstate=null;
- return status == BUSY_STATE ? ZlibConstants.Z_DATA_ERROR : ZlibConstants.Z_OK;
- }
- private void SetDeflater()
- {
- switch (config.Flavor)
- {
- case DeflateFlavor.Store:
- DeflateFunction = DeflateNone;
- break;
- case DeflateFlavor.Fast:
- DeflateFunction = DeflateFast;
- break;
- case DeflateFlavor.Slow:
- DeflateFunction = DeflateSlow;
- break;
- }
- }
- internal int SetParams(CompressionLevel level, CompressionStrategy strategy)
- {
- int result = ZlibConstants.Z_OK;
- if (compressionLevel != level)
- {
- Config newConfig = Config.Lookup(level);
- // change in the deflate flavor (Fast vs slow vs none)?
- if (newConfig.Flavor != config.Flavor && _codec.TotalBytesIn != 0)
- {
- // Flush the last buffer:
- result = _codec.Deflate(FlushType.Partial);
- }
- compressionLevel = level;
- config = newConfig;
- SetDeflater();
- }
- // no need to flush with change in strategy? Really?
- compressionStrategy = strategy;
- return result;
- }
- internal int SetDictionary(byte[] dictionary)
- {
- int length = dictionary.Length;
- int index = 0;
- if (dictionary == null || status != INIT_STATE)
- {
- throw new ZlibException("Stream error.");
- }
- _codec._Adler32 = Adler.Adler32(_codec._Adler32, dictionary, 0, dictionary.Length);
- if (length < MIN_MATCH)
- {
- return ZlibConstants.Z_OK;
- }
- if (length > w_size - MIN_LOOKAHEAD)
- {
- length = w_size - MIN_LOOKAHEAD;
- index = dictionary.Length - length; // use the tail of the dictionary
- }
- Array.Copy(dictionary, index, window, 0, length);
- strstart = length;
- blockStart = length;
- // Insert all strings in the hash table (except for the last two bytes).
- // s->lookahead stays null, so s->ins_h will be recomputed at the next
- // call of fill_window.
- ins_h = window[0] & 0xff;
- ins_h = (((ins_h) << hash_shift) ^ (window[1] & 0xff)) & hash_mask;
- for (int n = 0; n <= length - MIN_MATCH; n++)
- {
- ins_h = (((ins_h) << hash_shift) ^ (window[(n) + (MIN_MATCH - 1)] & 0xff)) & hash_mask;
- prev[n & w_mask] = head[ins_h];
- head[ins_h] = (short)n;
- }
- return ZlibConstants.Z_OK;
- }
- internal int Deflate(FlushType flush)
- {
- int old_flush;
- if (_codec.OutputBuffer == null ||
- (_codec.InputBuffer == null && _codec.AvailableBytesIn != 0) ||
- (status == FINISH_STATE && flush != FlushType.Finish))
- {
- _codec.Message = _ErrorMessage[ZlibConstants.Z_NEED_DICT - (ZlibConstants.Z_STREAM_ERROR)];
- throw new ZlibException(String.Format("Something is fishy. [{0}]", _codec.Message));
- //return ZlibConstants.Z_STREAM_ERROR;
- }
- if (_codec.AvailableBytesOut == 0)
- {
- _codec.Message = _ErrorMessage[ZlibConstants.Z_NEED_DICT - (ZlibConstants.Z_BUF_ERROR)];
- throw new ZlibException("OutputBuffer is full (AvailableBytesOut == 0)");
- //return ZlibConstants.Z_BUF_ERROR;
- }
- old_flush = last_flush;
- last_flush = (int)flush;
- // Write the zlib (rfc1950) header bytes
- if (status == INIT_STATE)
- {
- int header = (Z_DEFLATED + ((w_bits - 8) << 4)) << 8;
- int level_flags = (((int)compressionLevel - 1) & 0xff) >> 1;
- if (level_flags > 3)
- {
- level_flags = 3;
- }
- header |= (level_flags << 6);
- if (strstart != 0)
- {
- header |= PRESET_DICT;
- }
- header += 31 - (header % 31);
- status = BUSY_STATE;
- //putShortMSB(header);
- unchecked
- {
- pending[pendingCount++] = (byte)(header >> 8);
- pending[pendingCount++] = (byte)header;
- }
- // Save the adler32 of the preset dictionary:
- if (strstart != 0)
- {
- ////putShortMSB((int)(SharedUtils.URShift(_codec._Adler32, 16)));
- //putShortMSB((int)((UInt64)_codec._Adler32 >> 16));
- //putShortMSB((int)(_codec._Adler32 & 0xffff));
- pending[pendingCount++] = (byte)((_codec._Adler32 & 0xFF000000) >> 24);
- pending[pendingCount++] = (byte)((_codec._Adler32 & 0x00FF0000) >> 16);
- pending[pendingCount++] = (byte)((_codec._Adler32 & 0x0000FF00) >> 8);
- pending[pendingCount++] = (byte)(_codec._Adler32 & 0x000000FF);
- }
- _codec._Adler32 = Adler.Adler32(0, null, 0, 0);
- }
- // Flush as much pending output as possible
- if (pendingCount != 0)
- {
- _codec.flush_pending();
- if (_codec.AvailableBytesOut == 0)
- {
- //System.out.println(" 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:
- last_flush = -1;
- return ZlibConstants.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_BUFF_ERROR.
- }
- else if (_codec.AvailableBytesIn == 0 &&
- (int)flush <= old_flush &&
- flush != FlushType.Finish)
- {
- // workitem 8557
- // Not sure why this needs to be an error.
- // pendingCount == 0, which means there's nothing to deflate.
- // And the caller has not asked for a FlushType.Finish, but...
- // that seems very non-fatal. We can just say "OK" and do nthing.
- // _codec.Message = z_errmsg[ZlibConstants.Z_NEED_DICT - (ZlibConstants.Z_BUF_ERROR)];
- // throw new ZlibException("AvailableBytesIn == 0 && flush<=old_flush && flush != FlushType.Finish");
- return ZlibConstants.Z_OK;
- }
- // User must not provide more input after the first FINISH:
- if (status == FINISH_STATE && _codec.AvailableBytesIn != 0)
- {
- _codec.Message = _ErrorMessage[ZlibConstants.Z_NEED_DICT - (ZlibConstants.Z_BUF_ERROR)];
- throw new ZlibException("status == FINISH_STATE && _codec.AvailableBytesIn != 0");
- }
- // Start a new block or continue the current one.
- if (_codec.AvailableBytesIn != 0 || lookahead != 0 || (flush != FlushType.None && status != FINISH_STATE))
- {
- BlockState bstate = DeflateFunction(flush);
- if (bstate == BlockState.FinishStarted || bstate == BlockState.FinishDone)
- {
- status = FINISH_STATE;
- }
- if (bstate == BlockState.NeedMore || bstate == BlockState.FinishStarted)
- {
- if (_codec.AvailableBytesOut == 0)
- {
- last_flush = -1; // avoid BUF_ERROR next call, see above
- }
- return ZlibConstants.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 == BlockState.BlockDone)
- {
- if (flush == FlushType.Partial)
- {
- _tr_align();
- }
- else
- {
- // FlushType.Full or FlushType.Sync
- _tr_stored_block(0, 0, false);
- // For a full flush, this empty block will be recognized
- // as a special marker by inflate_sync().
- if (flush == FlushType.Full)
- {
- // clear hash (forget the history)
- for (int i = 0; i < hash_size; i++)
- {
- head[i] = 0;
- }
- }
- }
- _codec.flush_pending();
- if (_codec.AvailableBytesOut == 0)
- {
- last_flush = -1; // avoid BUF_ERROR at next call, see above
- return ZlibConstants.Z_OK;
- }
- }
- }
- if (flush != FlushType.Finish)
- {
- return ZlibConstants.Z_OK;
- }
- if (!WantRfc1950HeaderBytes || Rfc1950BytesEmitted)
- {
- return ZlibConstants.Z_STREAM_END;
- }
- // Write the zlib trailer (adler32)
- pending[pendingCount++] = (byte)((_codec._Adler32 & 0xFF000000) >> 24);
- pending[pendingCount++] = (byte)((_codec._Adler32 & 0x00FF0000) >> 16);
- pending[pendingCount++] = (byte)((_codec._Adler32 & 0x0000FF00) >> 8);
- pending[pendingCount++] = (byte)(_codec._Adler32 & 0x000000FF);
- //putShortMSB((int)(SharedUtils.URShift(_codec._Adler32, 16)));
- //putShortMSB((int)(_codec._Adler32 & 0xffff));
- _codec.flush_pending();
- // If avail_out is zero, the application will call deflate again
- // to flush the rest.
- Rfc1950BytesEmitted = true; // write the trailer only once!
- return pendingCount != 0 ? ZlibConstants.Z_OK : ZlibConstants.Z_STREAM_END;
- }
- }
- }
|