| // Tree.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:29:50> | |
| // | |
| // ------------------------------------------------------------------ | |
| // | |
| // This module defines classes for zlib compression and | |
| // decompression. This code is derived from the jzlib implementation of | |
| // zlib. In keeping with the license for jzlib, the copyright to that | |
| // code is below. | |
| // | |
| // ------------------------------------------------------------------ | |
| // | |
| // 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 OfficeOpenXml.Packaging.Ionic.Zlib | |
| { | |
| sealed class Tree | |
| { | |
| private static readonly int HEAP_SIZE = (2 * InternalConstants.L_CODES + 1); | |
| // extra bits for each length code | |
| internal static readonly int[] ExtraLengthBits = new int[] | |
| { | |
| 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 = new int[] | |
| { | |
| 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 | |
| }; | |
| // extra bits for each bit length code | |
| internal static readonly int[] extra_blbits = new int[]{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 3, 7}; | |
| internal static readonly sbyte[] bl_order = new sbyte[]{16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15}; | |
| // The lengths of the bit length codes are sent in order of decreasing | |
| // probability, to avoid transmitting the lengths for unused bit | |
| // length codes. | |
| internal const int Buf_size = 8 * 2; | |
| // see definition of array dist_code below | |
| //internal const int DIST_CODE_LEN = 512; | |
| private static readonly sbyte[] _dist_code = new sbyte[] | |
| { | |
| 0, 1, 2, 3, 4, 4, 5, 5, 6, 6, 6, 6, 7, 7, 7, 7, | |
| 8, 8, 8, 8, 8, 8, 8, 8, 9, 9, 9, 9, 9, 9, 9, 9, | |
| 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, | |
| 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, | |
| 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, | |
| 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, | |
| 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, | |
| 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, | |
| 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, | |
| 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, | |
| 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, | |
| 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, | |
| 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, | |
| 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, | |
| 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, | |
| 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, | |
| 0, 0, 16, 17, 18, 18, 19, 19, 20, 20, 20, 20, 21, 21, 21, 21, | |
| 22, 22, 22, 22, 22, 22, 22, 22, 23, 23, 23, 23, 23, 23, 23, 23, | |
| 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, | |
| 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, | |
| 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, | |
| 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, | |
| 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, | |
| 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, | |
| 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, | |
| 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, | |
| 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, | |
| 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, | |
| 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, | |
| 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, | |
| 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, | |
| 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29 | |
| }; | |
| internal static readonly sbyte[] LengthCode = new sbyte[] | |
| { | |
| 0, 1, 2, 3, 4, 5, 6, 7, 8, 8, 9, 9, 10, 10, 11, 11, | |
| 12, 12, 12, 12, 13, 13, 13, 13, 14, 14, 14, 14, 15, 15, 15, 15, | |
| 16, 16, 16, 16, 16, 16, 16, 16, 17, 17, 17, 17, 17, 17, 17, 17, | |
| 18, 18, 18, 18, 18, 18, 18, 18, 19, 19, 19, 19, 19, 19, 19, 19, | |
| 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, | |
| 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, | |
| 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, | |
| 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, | |
| 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, | |
| 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, | |
| 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, | |
| 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, | |
| 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, | |
| 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, | |
| 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, | |
| 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 28 | |
| }; | |
| internal static readonly int[] LengthBase = new int[] | |
| { | |
| 0, 1, 2, 3, 4, 5, 6, 7, 8, 10, 12, 14, 16, 20, 24, 28, | |
| 32, 40, 48, 56, 64, 80, 96, 112, 128, 160, 192, 224, 0 | |
| }; | |
| internal static readonly int[] DistanceBase = new int[] | |
| { | |
| 0, 1, 2, 3, 4, 6, 8, 12, 16, 24, 32, 48, 64, 96, 128, 192, | |
| 256, 384, 512, 768, 1024, 1536, 2048, 3072, 4096, 6144, 8192, 12288, 16384, 24576 | |
| }; | |
| /// <summary> | |
| /// Map from a distance to a distance code. | |
| /// </summary> | |
| /// <remarks> | |
| /// No side effects. _dist_code[256] and _dist_code[257] are never used. | |
| /// </remarks> | |
| internal static int DistanceCode(int dist) | |
| { | |
| return (dist < 256) | |
| ? _dist_code[dist] | |
| : _dist_code[256 + SharedUtils.URShift(dist, 7)]; | |
| } | |
| internal short[] dyn_tree; // the dynamic tree | |
| internal int max_code; // largest code with non zero frequency | |
| internal StaticTree staticTree; // the corresponding static tree | |
| // Compute the optimal bit lengths for a tree and update the total bit length | |
| // for the current block. | |
| // IN assertion: the fields freq and dad are set, heap[heap_max] and | |
| // above are the tree nodes sorted by increasing frequency. | |
| // OUT assertions: the field len is set to the optimal bit length, the | |
| // array bl_count contains the frequencies for each bit length. | |
| // The length opt_len is updated; static_len is also updated if stree is | |
| // not null. | |
| internal void gen_bitlen(DeflateManager s) | |
| { | |
| short[] tree = dyn_tree; | |
| short[] stree = staticTree.treeCodes; | |
| int[] extra = staticTree.extraBits; | |
| int base_Renamed = staticTree.extraBase; | |
| int max_length = staticTree.maxLength; | |
| int h; // heap index | |
| int n, m; // iterate over the tree elements | |
| int bits; // bit length | |
| int xbits; // extra bits | |
| short f; // frequency | |
| int overflow = 0; // number of elements with bit length too large | |
| for (bits = 0; bits <= InternalConstants.MAX_BITS; bits++) | |
| s.bl_count[bits] = 0; | |
| // In a first pass, compute the optimal bit lengths (which may | |
| // overflow in the case of the bit length tree). | |
| tree[s.heap[s.heap_max] * 2 + 1] = 0; // root of the heap | |
| for (h = s.heap_max + 1; h < HEAP_SIZE; h++) | |
| { | |
| n = s.heap[h]; | |
| bits = tree[tree[n * 2 + 1] * 2 + 1] + 1; | |
| if (bits > max_length) | |
| { | |
| bits = max_length; overflow++; | |
| } | |
| tree[n * 2 + 1] = (short) bits; | |
| // We overwrite tree[n*2+1] which is no longer needed | |
| if (n > max_code) | |
| continue; // not a leaf node | |
| s.bl_count[bits]++; | |
| xbits = 0; | |
| if (n >= base_Renamed) | |
| xbits = extra[n - base_Renamed]; | |
| f = tree[n * 2]; | |
| s.opt_len += f * (bits + xbits); | |
| if (stree != null) | |
| s.static_len += f * (stree[n * 2 + 1] + xbits); | |
| } | |
| if (overflow == 0) | |
| return ; | |
| // This happens for example on obj2 and pic of the Calgary corpus | |
| // Find the first bit length which could increase: | |
| do | |
| { | |
| bits = max_length - 1; | |
| while (s.bl_count[bits] == 0) | |
| bits--; | |
| s.bl_count[bits]--; // move one leaf down the tree | |
| s.bl_count[bits + 1] = (short) (s.bl_count[bits + 1] + 2); // move one overflow item as its brother | |
| s.bl_count[max_length]--; | |
| // The brother of the overflow item also moves one step up, | |
| // but this does not affect bl_count[max_length] | |
| overflow -= 2; | |
| } | |
| while (overflow > 0); | |
| for (bits = max_length; bits != 0; bits--) | |
| { | |
| n = s.bl_count[bits]; | |
| while (n != 0) | |
| { | |
| m = s.heap[--h]; | |
| if (m > max_code) | |
| continue; | |
| if (tree[m * 2 + 1] != bits) | |
| { | |
| s.opt_len = (int) (s.opt_len + ((long) bits - (long) tree[m * 2 + 1]) * (long) tree[m * 2]); | |
| tree[m * 2 + 1] = (short) bits; | |
| } | |
| n--; | |
| } | |
| } | |
| } | |
| // Construct one Huffman tree and assigns the code bit strings and lengths. | |
| // Update the total bit length for the current block. | |
| // IN assertion: the field freq is set for all tree elements. | |
| // OUT assertions: the fields len and code are set to the optimal bit length | |
| // and corresponding code. The length opt_len is updated; static_len is | |
| // also updated if stree is not null. The field max_code is set. | |
| internal void build_tree(DeflateManager s) | |
| { | |
| short[] tree = dyn_tree; | |
| short[] stree = staticTree.treeCodes; | |
| int elems = staticTree.elems; | |
| int n, m; // iterate over heap elements | |
| int max_code = -1; // largest code with non zero frequency | |
| int node; // new node being created | |
| // Construct the initial heap, with least frequent element in | |
| // heap[1]. The sons of heap[n] are heap[2*n] and heap[2*n+1]. | |
| // heap[0] is not used. | |
| s.heap_len = 0; | |
| s.heap_max = HEAP_SIZE; | |
| for (n = 0; n < elems; n++) | |
| { | |
| if (tree[n * 2] != 0) | |
| { | |
| s.heap[++s.heap_len] = max_code = n; | |
| s.depth[n] = 0; | |
| } | |
| else | |
| { | |
| tree[n * 2 + 1] = 0; | |
| } | |
| } | |
| // The pkzip format requires that at least one distance code exists, | |
| // and that at least one bit should be sent even if there is only one | |
| // possible code. So to avoid special checks later on we force at least | |
| // two codes of non zero frequency. | |
| while (s.heap_len < 2) | |
| { | |
| node = s.heap[++s.heap_len] = (max_code < 2?++max_code:0); | |
| tree[node * 2] = 1; | |
| s.depth[node] = 0; | |
| s.opt_len--; | |
| if (stree != null) | |
| s.static_len -= stree[node * 2 + 1]; | |
| // node is 0 or 1 so it does not have extra bits | |
| } | |
| this.max_code = max_code; | |
| // The elements heap[heap_len/2+1 .. heap_len] are leaves of the tree, | |
| // establish sub-heaps of increasing lengths: | |
| for (n = s.heap_len / 2; n >= 1; n--) | |
| s.pqdownheap(tree, n); | |
| // Construct the Huffman tree by repeatedly combining the least two | |
| // frequent nodes. | |
| node = elems; // next internal node of the tree | |
| do | |
| { | |
| // n = node of least frequency | |
| n = s.heap[1]; | |
| s.heap[1] = s.heap[s.heap_len--]; | |
| s.pqdownheap(tree, 1); | |
| m = s.heap[1]; // m = node of next least frequency | |
| s.heap[--s.heap_max] = n; // keep the nodes sorted by frequency | |
| s.heap[--s.heap_max] = m; | |
| // Create a new node father of n and m | |
| tree[node * 2] = unchecked((short) (tree[n * 2] + tree[m * 2])); | |
| s.depth[node] = (sbyte) (System.Math.Max((byte) s.depth[n], (byte) s.depth[m]) + 1); | |
| tree[n * 2 + 1] = tree[m * 2 + 1] = (short) node; | |
| // and insert the new node in the heap | |
| s.heap[1] = node++; | |
| s.pqdownheap(tree, 1); | |
| } | |
| while (s.heap_len >= 2); | |
| s.heap[--s.heap_max] = s.heap[1]; | |
| // At this point, the fields freq and dad are set. We can now | |
| // generate the bit lengths. | |
| gen_bitlen(s); | |
| // The field len is now set, we can generate the bit codes | |
| gen_codes(tree, max_code, s.bl_count); | |
| } | |
| // Generate the codes for a given tree and bit counts (which need not be | |
| // optimal). | |
| // IN assertion: the array bl_count contains the bit length statistics for | |
| // the given tree and the field len is set for all tree elements. | |
| // OUT assertion: the field code is set for all tree elements of non | |
| // zero code length. | |
| internal static void gen_codes(short[] tree, int max_code, short[] bl_count) | |
| { | |
| short[] next_code = new short[InternalConstants.MAX_BITS + 1]; // next code value for each bit length | |
| short code = 0; // running code value | |
| int bits; // bit index | |
| int n; // code index | |
| // The distribution counts are first used to generate the code values | |
| // without bit reversal. | |
| for (bits = 1; bits <= InternalConstants.MAX_BITS; bits++) | |
| unchecked { | |
| next_code[bits] = code = (short) ((code + bl_count[bits - 1]) << 1); | |
| } | |
| // Check that the bit counts in bl_count are consistent. The last code | |
| // must be all ones. | |
| //Assert (code + bl_count[MAX_BITS]-1 == (1<<MAX_BITS)-1, | |
| // "inconsistent bit counts"); | |
| //Tracev((stderr,"\ngen_codes: max_code %d ", max_code)); | |
| for (n = 0; n <= max_code; n++) | |
| { | |
| int len = tree[n * 2 + 1]; | |
| if (len == 0) | |
| continue; | |
| // Now reverse the bits | |
| tree[n * 2] = unchecked((short) (bi_reverse(next_code[len]++, len))); | |
| } | |
| } | |
| // Reverse the first len bits of a code, using straightforward code (a faster | |
| // method would use a table) | |
| // IN assertion: 1 <= len <= 15 | |
| internal static int bi_reverse(int code, int len) | |
| { | |
| int res = 0; | |
| do | |
| { | |
| res |= code & 1; | |
| code >>= 1; //SharedUtils.URShift(code, 1); | |
| res <<= 1; | |
| } | |
| while (--len > 0); | |
| return res >> 1; | |
| } | |
| } | |
| } |