| 1 | // Inftree.cs
|
|---|
| 2 | // ------------------------------------------------------------------
|
|---|
| 3 | //
|
|---|
| 4 | // Copyright (c) 2009 Dino Chiesa and Microsoft Corporation.
|
|---|
| 5 | // All rights reserved.
|
|---|
| 6 | //
|
|---|
| 7 | // This code module is part of DotNetZip, a zipfile class library.
|
|---|
| 8 | //
|
|---|
| 9 | // ------------------------------------------------------------------
|
|---|
| 10 | //
|
|---|
| 11 | // This code is licensed under the Microsoft Public License.
|
|---|
| 12 | // See the file License.txt for the license details.
|
|---|
| 13 | // More info on: http://dotnetzip.codeplex.com
|
|---|
| 14 | //
|
|---|
| 15 | // ------------------------------------------------------------------
|
|---|
| 16 | //
|
|---|
| 17 | // last saved (in emacs):
|
|---|
| 18 | // Time-stamp: <2009-October-28 12:43:54>
|
|---|
| 19 | //
|
|---|
| 20 | // ------------------------------------------------------------------
|
|---|
| 21 | //
|
|---|
| 22 | // This module defines classes used in decompression. This code is derived
|
|---|
| 23 | // from the jzlib implementation of zlib. In keeping with the license for jzlib,
|
|---|
| 24 | // the copyright to that code is below.
|
|---|
| 25 | //
|
|---|
| 26 | // ------------------------------------------------------------------
|
|---|
| 27 | //
|
|---|
| 28 | // Copyright (c) 2000,2001,2002,2003 ymnk, JCraft,Inc. All rights reserved.
|
|---|
| 29 | //
|
|---|
| 30 | // Redistribution and use in source and binary forms, with or without
|
|---|
| 31 | // modification, are permitted provided that the following conditions are met:
|
|---|
| 32 | //
|
|---|
| 33 | // 1. Redistributions of source code must retain the above copyright notice,
|
|---|
| 34 | // this list of conditions and the following disclaimer.
|
|---|
| 35 | //
|
|---|
| 36 | // 2. Redistributions in binary form must reproduce the above copyright
|
|---|
| 37 | // notice, this list of conditions and the following disclaimer in
|
|---|
| 38 | // the documentation and/or other materials provided with the distribution.
|
|---|
| 39 | //
|
|---|
| 40 | // 3. The names of the authors may not be used to endorse or promote products
|
|---|
| 41 | // derived from this software without specific prior written permission.
|
|---|
| 42 | //
|
|---|
| 43 | // THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED WARRANTIES,
|
|---|
| 44 | // INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
|
|---|
| 45 | // FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL JCRAFT,
|
|---|
| 46 | // INC. OR ANY CONTRIBUTORS TO THIS SOFTWARE BE LIABLE FOR ANY DIRECT, INDIRECT,
|
|---|
| 47 | // INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
|
|---|
| 48 | // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA,
|
|---|
| 49 | // OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
|
|---|
| 50 | // LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
|
|---|
| 51 | // NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE,
|
|---|
| 52 | // EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
|
|---|
| 53 | //
|
|---|
| 54 | // -----------------------------------------------------------------------
|
|---|
| 55 | //
|
|---|
| 56 | // This program is based on zlib-1.1.3; credit to authors
|
|---|
| 57 | // Jean-loup Gailly(jloup@gzip.org) and Mark Adler(madler@alumni.caltech.edu)
|
|---|
| 58 | // and contributors of zlib.
|
|---|
| 59 | //
|
|---|
| 60 | // -----------------------------------------------------------------------
|
|---|
| 61 |
|
|---|
| 62 |
|
|---|
| 63 |
|
|---|
| 64 | using System;
|
|---|
| 65 | namespace OfficeOpenXml.Packaging.Ionic.Zlib
|
|---|
| 66 | {
|
|---|
| 67 |
|
|---|
| 68 | sealed class InfTree
|
|---|
| 69 | {
|
|---|
| 70 |
|
|---|
| 71 | private const int MANY = 1440;
|
|---|
| 72 |
|
|---|
| 73 | private const int Z_OK = 0;
|
|---|
| 74 | private const int Z_STREAM_END = 1;
|
|---|
| 75 | private const int Z_NEED_DICT = 2;
|
|---|
| 76 | private const int Z_ERRNO = - 1;
|
|---|
| 77 | private const int Z_STREAM_ERROR = - 2;
|
|---|
| 78 | private const int Z_DATA_ERROR = - 3;
|
|---|
| 79 | private const int Z_MEM_ERROR = - 4;
|
|---|
| 80 | private const int Z_BUF_ERROR = - 5;
|
|---|
| 81 | private const int Z_VERSION_ERROR = - 6;
|
|---|
| 82 |
|
|---|
| 83 | internal const int fixed_bl = 9;
|
|---|
| 84 | internal const int fixed_bd = 5;
|
|---|
| 85 |
|
|---|
| 86 | //UPGRADE_NOTE: Final was removed from the declaration of 'fixed_tl'. "ms-help://MS.VSCC.v80/dv_commoner/local/redirect.htm?index='!DefaultContextWindowIndex'&keyword='jlca1003'"
|
|---|
| 87 | internal static readonly int[] fixed_tl = new int[]{96, 7, 256, 0, 8, 80, 0, 8, 16, 84, 8, 115, 82, 7, 31, 0, 8, 112, 0, 8, 48, 0, 9, 192, 80, 7, 10, 0, 8, 96, 0, 8, 32, 0, 9, 160, 0, 8, 0, 0, 8, 128, 0, 8, 64, 0, 9, 224, 80, 7, 6, 0, 8, 88, 0, 8, 24, 0, 9, 144, 83, 7, 59, 0, 8, 120, 0, 8, 56, 0, 9, 208, 81, 7, 17, 0, 8, 104, 0, 8, 40, 0, 9, 176, 0, 8, 8, 0, 8, 136, 0, 8, 72, 0, 9, 240, 80, 7, 4, 0, 8, 84, 0, 8, 20, 85, 8, 227, 83, 7, 43, 0, 8, 116, 0, 8, 52, 0, 9, 200, 81, 7, 13, 0, 8, 100, 0, 8, 36, 0, 9, 168, 0, 8, 4, 0, 8, 132, 0, 8, 68, 0, 9, 232, 80, 7, 8, 0, 8, 92, 0, 8, 28, 0, 9, 152, 84, 7, 83, 0, 8, 124, 0, 8, 60, 0, 9, 216, 82, 7, 23, 0, 8, 108, 0, 8, 44, 0, 9, 184, 0, 8, 12, 0, 8, 140, 0, 8, 76, 0, 9, 248, 80, 7, 3, 0, 8, 82, 0, 8, 18, 85, 8, 163, 83, 7, 35, 0, 8, 114, 0, 8, 50, 0, 9, 196, 81, 7, 11, 0, 8, 98, 0, 8, 34, 0, 9, 164, 0, 8, 2, 0, 8, 130, 0, 8, 66, 0, 9, 228, 80, 7, 7, 0, 8, 90, 0, 8, 26, 0, 9, 148, 84, 7, 67, 0, 8, 122, 0, 8, 58, 0, 9, 212, 82, 7, 19, 0, 8, 106, 0, 8, 42, 0, 9, 180, 0, 8, 10, 0, 8, 138, 0, 8, 74, 0, 9, 244, 80, 7, 5, 0, 8, 86, 0, 8, 22, 192, 8, 0, 83, 7, 51, 0, 8, 118, 0, 8, 54, 0, 9, 204, 81, 7, 15, 0, 8, 102, 0, 8, 38, 0, 9, 172, 0, 8, 6, 0, 8, 134, 0, 8, 70, 0, 9, 236, 80, 7, 9, 0, 8, 94, 0, 8, 30, 0, 9, 156, 84, 7, 99, 0, 8, 126, 0, 8, 62, 0, 9, 220, 82, 7, 27, 0, 8, 110, 0, 8, 46, 0, 9, 188, 0, 8, 14, 0, 8, 142, 0, 8, 78, 0, 9, 252, 96, 7, 256, 0, 8, 81, 0, 8, 17, 85, 8, 131, 82, 7, 31, 0, 8, 113, 0, 8, 49, 0, 9, 194, 80, 7, 10, 0, 8, 97, 0, 8, 33, 0, 9, 162, 0, 8, 1, 0, 8, 129, 0, 8, 65, 0, 9, 226, 80, 7, 6, 0, 8, 89, 0, 8, 25, 0, 9, 146, 83, 7, 59, 0, 8, 121, 0, 8, 57, 0, 9, 210, 81, 7, 17, 0, 8, 105, 0, 8, 41, 0, 9, 178, 0, 8, 9, 0, 8, 137, 0, 8, 73, 0, 9, 242, 80, 7, 4, 0, 8, 85, 0, 8, 21, 80, 8, 258, 83, 7, 43, 0, 8, 117, 0, 8, 53, 0, 9, 202, 81, 7, 13, 0, 8, 101, 0, 8, 37, 0, 9, 170, 0, 8, 5, 0, 8, 133, 0, 8, 69, 0, 9, 234, 80, 7, 8, 0, 8, 93, 0, 8, 29, 0, 9, 154, 84, 7, 83, 0, 8, 125, 0, 8, 61, 0, 9, 218, 82, 7, 23, 0, 8, 109, 0, 8, 45, 0, 9, 186,
|
|---|
| 88 | 0, 8, 13, 0, 8, 141, 0, 8, 77, 0, 9, 250, 80, 7, 3, 0, 8, 83, 0, 8, 19, 85, 8, 195, 83, 7, 35, 0, 8, 115, 0, 8, 51, 0, 9, 198, 81, 7, 11, 0, 8, 99, 0, 8, 35, 0, 9, 166, 0, 8, 3, 0, 8, 131, 0, 8, 67, 0, 9, 230, 80, 7, 7, 0, 8, 91, 0, 8, 27, 0, 9, 150, 84, 7, 67, 0, 8, 123, 0, 8, 59, 0, 9, 214, 82, 7, 19, 0, 8, 107, 0, 8, 43, 0, 9, 182, 0, 8, 11, 0, 8, 139, 0, 8, 75, 0, 9, 246, 80, 7, 5, 0, 8, 87, 0, 8, 23, 192, 8, 0, 83, 7, 51, 0, 8, 119, 0, 8, 55, 0, 9, 206, 81, 7, 15, 0, 8, 103, 0, 8, 39, 0, 9, 174, 0, 8, 7, 0, 8, 135, 0, 8, 71, 0, 9, 238, 80, 7, 9, 0, 8, 95, 0, 8, 31, 0, 9, 158, 84, 7, 99, 0, 8, 127, 0, 8, 63, 0, 9, 222, 82, 7, 27, 0, 8, 111, 0, 8, 47, 0, 9, 190, 0, 8, 15, 0, 8, 143, 0, 8, 79, 0, 9, 254, 96, 7, 256, 0, 8, 80, 0, 8, 16, 84, 8, 115, 82, 7, 31, 0, 8, 112, 0, 8, 48, 0, 9, 193, 80, 7, 10, 0, 8, 96, 0, 8, 32, 0, 9, 161, 0, 8, 0, 0, 8, 128, 0, 8, 64, 0, 9, 225, 80, 7, 6, 0, 8, 88, 0, 8, 24, 0, 9, 145, 83, 7, 59, 0, 8, 120, 0, 8, 56, 0, 9, 209, 81, 7, 17, 0, 8, 104, 0, 8, 40, 0, 9, 177, 0, 8, 8, 0, 8, 136, 0, 8, 72, 0, 9, 241, 80, 7, 4, 0, 8, 84, 0, 8, 20, 85, 8, 227, 83, 7, 43, 0, 8, 116, 0, 8, 52, 0, 9, 201, 81, 7, 13, 0, 8, 100, 0, 8, 36, 0, 9, 169, 0, 8, 4, 0, 8, 132, 0, 8, 68, 0, 9, 233, 80, 7, 8, 0, 8, 92, 0, 8, 28, 0, 9, 153, 84, 7, 83, 0, 8, 124, 0, 8, 60, 0, 9, 217, 82, 7, 23, 0, 8, 108, 0, 8, 44, 0, 9, 185, 0, 8, 12, 0, 8, 140, 0, 8, 76, 0, 9, 249, 80, 7, 3, 0, 8, 82, 0, 8, 18, 85, 8, 163, 83, 7, 35, 0, 8, 114, 0, 8, 50, 0, 9, 197, 81, 7, 11, 0, 8, 98, 0, 8, 34, 0, 9, 165, 0, 8, 2, 0, 8, 130, 0, 8, 66, 0, 9, 229, 80, 7, 7, 0, 8, 90, 0, 8, 26, 0, 9, 149, 84, 7, 67, 0, 8, 122, 0, 8, 58, 0, 9, 213, 82, 7, 19, 0, 8, 106, 0, 8, 42, 0, 9, 181, 0, 8, 10, 0, 8, 138, 0, 8, 74, 0, 9, 245, 80, 7, 5, 0, 8, 86, 0, 8, 22, 192, 8, 0, 83, 7, 51, 0, 8, 118, 0, 8, 54, 0, 9, 205, 81, 7, 15, 0, 8, 102, 0, 8, 38, 0, 9, 173, 0, 8, 6, 0, 8, 134, 0, 8, 70, 0, 9, 237, 80, 7, 9, 0, 8, 94, 0, 8, 30, 0, 9, 157, 84, 7, 99, 0, 8, 126, 0, 8, 62, 0, 9, 221, 82, 7, 27, 0, 8, 110, 0, 8, 46, 0, 9, 189, 0, 8,
|
|---|
| 89 | 14, 0, 8, 142, 0, 8, 78, 0, 9, 253, 96, 7, 256, 0, 8, 81, 0, 8, 17, 85, 8, 131, 82, 7, 31, 0, 8, 113, 0, 8, 49, 0, 9, 195, 80, 7, 10, 0, 8, 97, 0, 8, 33, 0, 9, 163, 0, 8, 1, 0, 8, 129, 0, 8, 65, 0, 9, 227, 80, 7, 6, 0, 8, 89, 0, 8, 25, 0, 9, 147, 83, 7, 59, 0, 8, 121, 0, 8, 57, 0, 9, 211, 81, 7, 17, 0, 8, 105, 0, 8, 41, 0, 9, 179, 0, 8, 9, 0, 8, 137, 0, 8, 73, 0, 9, 243, 80, 7, 4, 0, 8, 85, 0, 8, 21, 80, 8, 258, 83, 7, 43, 0, 8, 117, 0, 8, 53, 0, 9, 203, 81, 7, 13, 0, 8, 101, 0, 8, 37, 0, 9, 171, 0, 8, 5, 0, 8, 133, 0, 8, 69, 0, 9, 235, 80, 7, 8, 0, 8, 93, 0, 8, 29, 0, 9, 155, 84, 7, 83, 0, 8, 125, 0, 8, 61, 0, 9, 219, 82, 7, 23, 0, 8, 109, 0, 8, 45, 0, 9, 187, 0, 8, 13, 0, 8, 141, 0, 8, 77, 0, 9, 251, 80, 7, 3, 0, 8, 83, 0, 8, 19, 85, 8, 195, 83, 7, 35, 0, 8, 115, 0, 8, 51, 0, 9, 199, 81, 7, 11, 0, 8, 99, 0, 8, 35, 0, 9, 167, 0, 8, 3, 0, 8, 131, 0, 8, 67, 0, 9, 231, 80, 7, 7, 0, 8, 91, 0, 8, 27, 0, 9, 151, 84, 7, 67, 0, 8, 123, 0, 8, 59, 0, 9, 215, 82, 7, 19, 0, 8, 107, 0, 8, 43, 0, 9, 183, 0, 8, 11, 0, 8, 139, 0, 8, 75, 0, 9, 247, 80, 7, 5, 0, 8, 87, 0, 8, 23, 192, 8, 0, 83, 7, 51, 0, 8, 119, 0, 8, 55, 0, 9, 207, 81, 7, 15, 0, 8, 103, 0, 8, 39, 0, 9, 175, 0, 8, 7, 0, 8, 135, 0, 8, 71, 0, 9, 239, 80, 7, 9, 0, 8, 95, 0, 8, 31, 0, 9, 159, 84, 7, 99, 0, 8, 127, 0, 8, 63, 0, 9, 223, 82, 7, 27, 0, 8, 111, 0, 8, 47, 0, 9, 191, 0, 8, 15, 0, 8, 143, 0, 8, 79, 0, 9, 255};
|
|---|
| 90 | //UPGRADE_NOTE: Final was removed from the declaration of 'fixed_td'. "ms-help://MS.VSCC.v80/dv_commoner/local/redirect.htm?index='!DefaultContextWindowIndex'&keyword='jlca1003'"
|
|---|
| 91 | internal static readonly int[] fixed_td = new int[]{80, 5, 1, 87, 5, 257, 83, 5, 17, 91, 5, 4097, 81, 5, 5, 89, 5, 1025, 85, 5, 65, 93, 5, 16385, 80, 5, 3, 88, 5, 513, 84, 5, 33, 92, 5, 8193, 82, 5, 9, 90, 5, 2049, 86, 5, 129, 192, 5, 24577, 80, 5, 2, 87, 5, 385, 83, 5, 25, 91, 5, 6145, 81, 5, 7, 89, 5, 1537, 85, 5, 97, 93, 5, 24577, 80, 5, 4, 88, 5, 769, 84, 5, 49, 92, 5, 12289, 82, 5, 13, 90, 5, 3073, 86, 5, 193, 192, 5, 24577};
|
|---|
| 92 |
|
|---|
| 93 | // Tables for deflate from PKZIP's appnote.txt.
|
|---|
| 94 | //UPGRADE_NOTE: Final was removed from the declaration of 'cplens'. "ms-help://MS.VSCC.v80/dv_commoner/local/redirect.htm?index='!DefaultContextWindowIndex'&keyword='jlca1003'"
|
|---|
| 95 | internal static readonly int[] cplens = new int[]{3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31, 35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258, 0, 0};
|
|---|
| 96 |
|
|---|
| 97 | // see note #13 above about 258
|
|---|
| 98 | //UPGRADE_NOTE: Final was removed from the declaration of 'cplext'. "ms-help://MS.VSCC.v80/dv_commoner/local/redirect.htm?index='!DefaultContextWindowIndex'&keyword='jlca1003'"
|
|---|
| 99 | internal static readonly int[] cplext = 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, 112, 112};
|
|---|
| 100 |
|
|---|
| 101 | //UPGRADE_NOTE: Final was removed from the declaration of 'cpdist'. "ms-help://MS.VSCC.v80/dv_commoner/local/redirect.htm?index='!DefaultContextWindowIndex'&keyword='jlca1003'"
|
|---|
| 102 | internal static readonly int[] cpdist = new int[]{1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193, 257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145, 8193, 12289, 16385, 24577};
|
|---|
| 103 |
|
|---|
| 104 | //UPGRADE_NOTE: Final was removed from the declaration of 'cpdext'. "ms-help://MS.VSCC.v80/dv_commoner/local/redirect.htm?index='!DefaultContextWindowIndex'&keyword='jlca1003'"
|
|---|
| 105 | internal static readonly int[] cpdext = 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};
|
|---|
| 106 |
|
|---|
| 107 | // If BMAX needs to be larger than 16, then h and x[] should be uLong.
|
|---|
| 108 | internal const int BMAX = 15; // maximum bit length of any code
|
|---|
| 109 |
|
|---|
| 110 | internal int[] hn = null; // hufts used in space
|
|---|
| 111 | internal int[] v = null; // work area for huft_build
|
|---|
| 112 | internal int[] c = null; // bit length count table
|
|---|
| 113 | internal int[] r = null; // table entry for structure assignment
|
|---|
| 114 | internal int[] u = null; // table stack
|
|---|
| 115 | internal int[] x = null; // bit offsets, then code stack
|
|---|
| 116 |
|
|---|
| 117 | private int huft_build(int[] b, int bindex, int n, int s, int[] d, int[] e, int[] t, int[] m, int[] hp, int[] hn, int[] v)
|
|---|
| 118 | {
|
|---|
| 119 | // Given a list of code lengths and a maximum table size, make a set of
|
|---|
| 120 | // tables to decode that set of codes. Return Z_OK on success, Z_BUF_ERROR
|
|---|
| 121 | // if the given code set is incomplete (the tables are still built in this
|
|---|
| 122 | // case), Z_DATA_ERROR if the input is invalid (an over-subscribed set of
|
|---|
| 123 | // lengths), or Z_MEM_ERROR if not enough memory.
|
|---|
| 124 |
|
|---|
| 125 | int a; // counter for codes of length k
|
|---|
| 126 | int f; // i repeats in table every f entries
|
|---|
| 127 | int g; // maximum code length
|
|---|
| 128 | int h; // table level
|
|---|
| 129 | int i; // counter, current code
|
|---|
| 130 | int j; // counter
|
|---|
| 131 | int k; // number of bits in current code
|
|---|
| 132 | int l; // bits per table (returned in m)
|
|---|
| 133 | int mask; // (1 << w) - 1, to avoid cc -O bug on HP
|
|---|
| 134 | int p; // pointer into c[], b[], or v[]
|
|---|
| 135 | int q; // points to current table
|
|---|
| 136 | int w; // bits before this table == (l * h)
|
|---|
| 137 | int xp; // pointer into x
|
|---|
| 138 | int y; // number of dummy codes added
|
|---|
| 139 | int z; // number of entries in current table
|
|---|
| 140 |
|
|---|
| 141 | // Generate counts for each bit length
|
|---|
| 142 |
|
|---|
| 143 | p = 0; i = n;
|
|---|
| 144 | do
|
|---|
| 145 | {
|
|---|
| 146 | c[b[bindex + p]]++; p++; i--; // assume all entries <= BMAX
|
|---|
| 147 | }
|
|---|
| 148 | while (i != 0);
|
|---|
| 149 |
|
|---|
| 150 | if (c[0] == n)
|
|---|
| 151 | {
|
|---|
| 152 | // null input--all zero length codes
|
|---|
| 153 | t[0] = - 1;
|
|---|
| 154 | m[0] = 0;
|
|---|
| 155 | return Z_OK;
|
|---|
| 156 | }
|
|---|
| 157 |
|
|---|
| 158 | // Find minimum and maximum length, bound *m by those
|
|---|
| 159 | l = m[0];
|
|---|
| 160 | for (j = 1; j <= BMAX; j++)
|
|---|
| 161 | if (c[j] != 0)
|
|---|
| 162 | break;
|
|---|
| 163 | k = j; // minimum code length
|
|---|
| 164 | if (l < j)
|
|---|
| 165 | {
|
|---|
| 166 | l = j;
|
|---|
| 167 | }
|
|---|
| 168 | for (i = BMAX; i != 0; i--)
|
|---|
| 169 | {
|
|---|
| 170 | if (c[i] != 0)
|
|---|
| 171 | break;
|
|---|
| 172 | }
|
|---|
| 173 | g = i; // maximum code length
|
|---|
| 174 | if (l > i)
|
|---|
| 175 | {
|
|---|
| 176 | l = i;
|
|---|
| 177 | }
|
|---|
| 178 | m[0] = l;
|
|---|
| 179 |
|
|---|
| 180 | // Adjust last length count to fill out codes, if needed
|
|---|
| 181 | for (y = 1 << j; j < i; j++, y <<= 1)
|
|---|
| 182 | {
|
|---|
| 183 | if ((y -= c[j]) < 0)
|
|---|
| 184 | {
|
|---|
| 185 | return Z_DATA_ERROR;
|
|---|
| 186 | }
|
|---|
| 187 | }
|
|---|
| 188 | if ((y -= c[i]) < 0)
|
|---|
| 189 | {
|
|---|
| 190 | return Z_DATA_ERROR;
|
|---|
| 191 | }
|
|---|
| 192 | c[i] += y;
|
|---|
| 193 |
|
|---|
| 194 | // Generate starting offsets into the value table for each length
|
|---|
| 195 | x[1] = j = 0;
|
|---|
| 196 | p = 1; xp = 2;
|
|---|
| 197 | while (--i != 0)
|
|---|
| 198 | {
|
|---|
| 199 | // note that i == g from above
|
|---|
| 200 | x[xp] = (j += c[p]);
|
|---|
| 201 | xp++;
|
|---|
| 202 | p++;
|
|---|
| 203 | }
|
|---|
| 204 |
|
|---|
| 205 | // Make a table of values in order of bit lengths
|
|---|
| 206 | i = 0; p = 0;
|
|---|
| 207 | do
|
|---|
| 208 | {
|
|---|
| 209 | if ((j = b[bindex + p]) != 0)
|
|---|
| 210 | {
|
|---|
| 211 | v[x[j]++] = i;
|
|---|
| 212 | }
|
|---|
| 213 | p++;
|
|---|
| 214 | }
|
|---|
| 215 | while (++i < n);
|
|---|
| 216 | n = x[g]; // set n to length of v
|
|---|
| 217 |
|
|---|
| 218 | // Generate the Huffman codes and for each, make the table entries
|
|---|
| 219 | x[0] = i = 0; // first Huffman code is zero
|
|---|
| 220 | p = 0; // grab values in bit order
|
|---|
| 221 | h = - 1; // no tables yet--level -1
|
|---|
| 222 | w = - l; // bits decoded == (l * h)
|
|---|
| 223 | u[0] = 0; // just to keep compilers happy
|
|---|
| 224 | q = 0; // ditto
|
|---|
| 225 | z = 0; // ditto
|
|---|
| 226 |
|
|---|
| 227 | // go through the bit lengths (k already is bits in shortest code)
|
|---|
| 228 | for (; k <= g; k++)
|
|---|
| 229 | {
|
|---|
| 230 | a = c[k];
|
|---|
| 231 | while (a-- != 0)
|
|---|
| 232 | {
|
|---|
| 233 | // here i is the Huffman code of length k bits for value *p
|
|---|
| 234 | // make tables up to required level
|
|---|
| 235 | while (k > w + l)
|
|---|
| 236 | {
|
|---|
| 237 | h++;
|
|---|
| 238 | w += l; // previous table always l bits
|
|---|
| 239 | // compute minimum size table less than or equal to l bits
|
|---|
| 240 | z = g - w;
|
|---|
| 241 | z = (z > l)?l:z; // table size upper limit
|
|---|
| 242 | if ((f = 1 << (j = k - w)) > a + 1)
|
|---|
| 243 | {
|
|---|
| 244 | // try a k-w bit table
|
|---|
| 245 | // too few codes for k-w bit table
|
|---|
| 246 | f -= (a + 1); // deduct codes from patterns left
|
|---|
| 247 | xp = k;
|
|---|
| 248 | if (j < z)
|
|---|
| 249 | {
|
|---|
| 250 | while (++j < z)
|
|---|
| 251 | {
|
|---|
| 252 | // try smaller tables up to z bits
|
|---|
| 253 | if ((f <<= 1) <= c[++xp])
|
|---|
| 254 | break; // enough codes to use up j bits
|
|---|
| 255 | f -= c[xp]; // else deduct codes from patterns
|
|---|
| 256 | }
|
|---|
| 257 | }
|
|---|
| 258 | }
|
|---|
| 259 | z = 1 << j; // table entries for j-bit table
|
|---|
| 260 |
|
|---|
| 261 | // allocate new table
|
|---|
| 262 | if (hn[0] + z > MANY)
|
|---|
| 263 | {
|
|---|
| 264 | // (note: doesn't matter for fixed)
|
|---|
| 265 | return Z_DATA_ERROR; // overflow of MANY
|
|---|
| 266 | }
|
|---|
| 267 | u[h] = q = hn[0]; // DEBUG
|
|---|
| 268 | hn[0] += z;
|
|---|
| 269 |
|
|---|
| 270 | // connect to last table, if there is one
|
|---|
| 271 | if (h != 0)
|
|---|
| 272 | {
|
|---|
| 273 | x[h] = i; // save pattern for backing up
|
|---|
| 274 | r[0] = (sbyte) j; // bits in this table
|
|---|
| 275 | r[1] = (sbyte) l; // bits to dump before this table
|
|---|
| 276 | j = SharedUtils.URShift(i, (w - l));
|
|---|
| 277 | r[2] = (int) (q - u[h - 1] - j); // offset to this table
|
|---|
| 278 | Array.Copy(r, 0, hp, (u[h - 1] + j) * 3, 3); // connect to last table
|
|---|
| 279 | }
|
|---|
| 280 | else
|
|---|
| 281 | {
|
|---|
| 282 | t[0] = q; // first table is returned result
|
|---|
| 283 | }
|
|---|
| 284 | }
|
|---|
| 285 |
|
|---|
| 286 | // set up table entry in r
|
|---|
| 287 | r[1] = (sbyte) (k - w);
|
|---|
| 288 | if (p >= n)
|
|---|
| 289 | {
|
|---|
| 290 | r[0] = 128 + 64; // out of values--invalid code
|
|---|
| 291 | }
|
|---|
| 292 | else if (v[p] < s)
|
|---|
| 293 | {
|
|---|
| 294 | r[0] = (sbyte) (v[p] < 256?0:32 + 64); // 256 is end-of-block
|
|---|
| 295 | r[2] = v[p++]; // simple code is just the value
|
|---|
| 296 | }
|
|---|
| 297 | else
|
|---|
| 298 | {
|
|---|
| 299 | r[0] = (sbyte) (e[v[p] - s] + 16 + 64); // non-simple--look up in lists
|
|---|
| 300 | r[2] = d[v[p++] - s];
|
|---|
| 301 | }
|
|---|
| 302 |
|
|---|
| 303 | // fill code-like entries with r
|
|---|
| 304 | f = 1 << (k - w);
|
|---|
| 305 | for (j = SharedUtils.URShift(i, w); j < z; j += f)
|
|---|
| 306 | {
|
|---|
| 307 | Array.Copy(r, 0, hp, (q + j) * 3, 3);
|
|---|
| 308 | }
|
|---|
| 309 |
|
|---|
| 310 | // backwards increment the k-bit code i
|
|---|
| 311 | for (j = 1 << (k - 1); (i & j) != 0; j = SharedUtils.URShift(j, 1))
|
|---|
| 312 | {
|
|---|
| 313 | i ^= j;
|
|---|
| 314 | }
|
|---|
| 315 | i ^= j;
|
|---|
| 316 |
|
|---|
| 317 | // backup over finished tables
|
|---|
| 318 | mask = (1 << w) - 1; // needed on HP, cc -O bug
|
|---|
| 319 | while ((i & mask) != x[h])
|
|---|
| 320 | {
|
|---|
| 321 | h--; // don't need to update q
|
|---|
| 322 | w -= l;
|
|---|
| 323 | mask = (1 << w) - 1;
|
|---|
| 324 | }
|
|---|
| 325 | }
|
|---|
| 326 | }
|
|---|
| 327 | // Return Z_BUF_ERROR if we were given an incomplete table
|
|---|
| 328 | return y != 0 && g != 1?Z_BUF_ERROR:Z_OK;
|
|---|
| 329 | }
|
|---|
| 330 |
|
|---|
| 331 | internal int inflate_trees_bits(int[] c, int[] bb, int[] tb, int[] hp, ZlibCodec z)
|
|---|
| 332 | {
|
|---|
| 333 | int result;
|
|---|
| 334 | initWorkArea(19);
|
|---|
| 335 | hn[0] = 0;
|
|---|
| 336 | result = huft_build(c, 0, 19, 19, null, null, tb, bb, hp, hn, v);
|
|---|
| 337 |
|
|---|
| 338 | if (result == Z_DATA_ERROR)
|
|---|
| 339 | {
|
|---|
| 340 | z.Message = "oversubscribed dynamic bit lengths tree";
|
|---|
| 341 | }
|
|---|
| 342 | else if (result == Z_BUF_ERROR || bb[0] == 0)
|
|---|
| 343 | {
|
|---|
| 344 | z.Message = "incomplete dynamic bit lengths tree";
|
|---|
| 345 | result = Z_DATA_ERROR;
|
|---|
| 346 | }
|
|---|
| 347 | return result;
|
|---|
| 348 | }
|
|---|
| 349 |
|
|---|
| 350 | internal int inflate_trees_dynamic(int nl, int nd, int[] c, int[] bl, int[] bd, int[] tl, int[] td, int[] hp, ZlibCodec z)
|
|---|
| 351 | {
|
|---|
| 352 | int result;
|
|---|
| 353 |
|
|---|
| 354 | // build literal/length tree
|
|---|
| 355 | initWorkArea(288);
|
|---|
| 356 | hn[0] = 0;
|
|---|
| 357 | result = huft_build(c, 0, nl, 257, cplens, cplext, tl, bl, hp, hn, v);
|
|---|
| 358 | if (result != Z_OK || bl[0] == 0)
|
|---|
| 359 | {
|
|---|
| 360 | if (result == Z_DATA_ERROR)
|
|---|
| 361 | {
|
|---|
| 362 | z.Message = "oversubscribed literal/length tree";
|
|---|
| 363 | }
|
|---|
| 364 | else if (result != Z_MEM_ERROR)
|
|---|
| 365 | {
|
|---|
| 366 | z.Message = "incomplete literal/length tree";
|
|---|
| 367 | result = Z_DATA_ERROR;
|
|---|
| 368 | }
|
|---|
| 369 | return result;
|
|---|
| 370 | }
|
|---|
| 371 |
|
|---|
| 372 | // build distance tree
|
|---|
| 373 | initWorkArea(288);
|
|---|
| 374 | result = huft_build(c, nl, nd, 0, cpdist, cpdext, td, bd, hp, hn, v);
|
|---|
| 375 |
|
|---|
| 376 | if (result != Z_OK || (bd[0] == 0 && nl > 257))
|
|---|
| 377 | {
|
|---|
| 378 | if (result == Z_DATA_ERROR)
|
|---|
| 379 | {
|
|---|
| 380 | z.Message = "oversubscribed distance tree";
|
|---|
| 381 | }
|
|---|
| 382 | else if (result == Z_BUF_ERROR)
|
|---|
| 383 | {
|
|---|
| 384 | z.Message = "incomplete distance tree";
|
|---|
| 385 | result = Z_DATA_ERROR;
|
|---|
| 386 | }
|
|---|
| 387 | else if (result != Z_MEM_ERROR)
|
|---|
| 388 | {
|
|---|
| 389 | z.Message = "empty distance tree with lengths";
|
|---|
| 390 | result = Z_DATA_ERROR;
|
|---|
| 391 | }
|
|---|
| 392 | return result;
|
|---|
| 393 | }
|
|---|
| 394 |
|
|---|
| 395 | return Z_OK;
|
|---|
| 396 | }
|
|---|
| 397 |
|
|---|
| 398 | internal static int inflate_trees_fixed(int[] bl, int[] bd, int[][] tl, int[][] td, ZlibCodec z)
|
|---|
| 399 | {
|
|---|
| 400 | bl[0] = fixed_bl;
|
|---|
| 401 | bd[0] = fixed_bd;
|
|---|
| 402 | tl[0] = fixed_tl;
|
|---|
| 403 | td[0] = fixed_td;
|
|---|
| 404 | return Z_OK;
|
|---|
| 405 | }
|
|---|
| 406 |
|
|---|
| 407 | private void initWorkArea(int vsize)
|
|---|
| 408 | {
|
|---|
| 409 | if (hn == null)
|
|---|
| 410 | {
|
|---|
| 411 | hn = new int[1];
|
|---|
| 412 | v = new int[vsize];
|
|---|
| 413 | c = new int[BMAX + 1];
|
|---|
| 414 | r = new int[3];
|
|---|
| 415 | u = new int[BMAX];
|
|---|
| 416 | x = new int[BMAX + 1];
|
|---|
| 417 | }
|
|---|
| 418 | else
|
|---|
| 419 | {
|
|---|
| 420 | if (v.Length < vsize)
|
|---|
| 421 | {
|
|---|
| 422 | v = new int[vsize];
|
|---|
| 423 | }
|
|---|
| 424 | Array.Clear(v,0,vsize);
|
|---|
| 425 | Array.Clear(c,0,BMAX+1);
|
|---|
| 426 | r[0]=0; r[1]=0; r[2]=0;
|
|---|
| 427 | // for(int i=0; i<BMAX; i++){u[i]=0;}
|
|---|
| 428 | //Array.Copy(c, 0, u, 0, BMAX);
|
|---|
| 429 | Array.Clear(u,0,BMAX);
|
|---|
| 430 | // for(int i=0; i<BMAX+1; i++){x[i]=0;}
|
|---|
| 431 | //Array.Copy(c, 0, x, 0, BMAX + 1);
|
|---|
| 432 | Array.Clear(x,0,BMAX+1);
|
|---|
| 433 | }
|
|---|
| 434 | }
|
|---|
| 435 | }
|
|---|
| 436 | } |
|---|
