InfTree.cs 25 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576
  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. using System;
  62. namespace SharpCompress.Compressors.Deflate
  63. {
  64. internal sealed class InfTree
  65. {
  66. private const int MANY = 1440;
  67. private const int Z_OK = 0;
  68. private const int Z_STREAM_END = 1;
  69. private const int Z_NEED_DICT = 2;
  70. private const int Z_ERRNO = -1;
  71. private const int Z_STREAM_ERROR = -2;
  72. private const int Z_DATA_ERROR = -3;
  73. private const int Z_MEM_ERROR = -4;
  74. private const int Z_BUF_ERROR = -5;
  75. private const int Z_VERSION_ERROR = -6;
  76. internal const int fixed_bl = 9;
  77. internal const int fixed_bd = 5;
  78. internal const int BMAX = 15; // maximum bit length of any code
  79. //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'"
  80. internal static readonly int[] fixed_tl =
  81. {
  82. 96, 7, 256, 0, 8, 80, 0, 8, 16, 84, 8, 115, 82, 7, 31, 0, 8,
  83. 112, 0, 8, 48, 0, 9, 192, 80, 7, 10, 0, 8, 96, 0, 8, 32, 0, 9,
  84. 160, 0, 8, 0, 0, 8, 128, 0, 8, 64, 0, 9, 224, 80, 7, 6, 0, 8,
  85. 88, 0, 8, 24, 0, 9, 144, 83, 7, 59, 0, 8, 120, 0, 8, 56, 0, 9,
  86. 208, 81, 7, 17, 0, 8, 104, 0, 8, 40, 0, 9, 176, 0, 8, 8, 0, 8,
  87. 136, 0, 8, 72, 0, 9, 240, 80, 7, 4, 0, 8, 84, 0, 8, 20, 85, 8,
  88. 227, 83, 7, 43, 0, 8, 116, 0, 8, 52, 0, 9, 200, 81, 7, 13, 0,
  89. 8, 100, 0, 8, 36, 0, 9, 168, 0, 8, 4, 0, 8, 132, 0, 8, 68, 0,
  90. 9, 232, 80, 7, 8, 0, 8, 92, 0, 8, 28, 0, 9, 152, 84, 7, 83, 0,
  91. 8, 124, 0, 8, 60, 0, 9, 216, 82, 7, 23, 0, 8, 108, 0, 8, 44, 0
  92. , 9, 184, 0, 8, 12, 0, 8, 140, 0, 8, 76, 0, 9, 248, 80, 7, 3,
  93. 0, 8, 82, 0, 8, 18, 85, 8, 163, 83, 7, 35, 0, 8, 114, 0, 8, 50
  94. , 0, 9, 196, 81, 7, 11, 0, 8, 98, 0, 8, 34, 0, 9, 164, 0, 8, 2
  95. , 0, 8, 130, 0, 8, 66, 0, 9, 228, 80, 7, 7, 0, 8, 90, 0, 8, 26
  96. , 0, 9, 148, 84, 7, 67, 0, 8, 122, 0, 8, 58, 0, 9, 212, 82, 7,
  97. 19, 0, 8, 106, 0, 8, 42, 0, 9, 180, 0, 8, 10, 0, 8, 138, 0, 8,
  98. 74, 0, 9, 244, 80, 7, 5, 0, 8, 86, 0, 8, 22, 192, 8, 0, 83, 7,
  99. 51, 0, 8, 118, 0, 8, 54, 0, 9, 204, 81, 7, 15, 0, 8, 102, 0, 8
  100. , 38, 0, 9, 172, 0, 8, 6, 0, 8, 134, 0, 8, 70, 0, 9, 236, 80,
  101. 7, 9, 0, 8, 94, 0, 8, 30, 0, 9, 156, 84, 7, 99, 0, 8, 126, 0,
  102. 8, 62, 0, 9, 220, 82, 7, 27, 0, 8, 110, 0, 8, 46, 0, 9, 188, 0
  103. , 8, 14, 0, 8, 142, 0, 8, 78, 0, 9, 252, 96, 7, 256, 0, 8, 81,
  104. 0, 8, 17, 85, 8, 131, 82, 7, 31, 0, 8, 113, 0, 8, 49, 0, 9,
  105. 194, 80, 7, 10, 0, 8, 97, 0, 8, 33, 0, 9, 162, 0, 8, 1, 0, 8,
  106. 129, 0, 8, 65, 0, 9, 226, 80, 7, 6, 0, 8, 89, 0, 8, 25, 0, 9,
  107. 146, 83, 7, 59, 0, 8, 121, 0, 8, 57, 0, 9, 210, 81, 7, 17, 0,
  108. 8, 105, 0, 8, 41, 0, 9, 178, 0, 8, 9, 0, 8, 137, 0, 8, 73, 0,
  109. 9, 242, 80, 7, 4, 0, 8, 85, 0, 8, 21, 80, 8, 258, 83, 7, 43, 0
  110. , 8, 117, 0, 8, 53, 0, 9, 202, 81, 7, 13, 0, 8, 101, 0, 8, 37,
  111. 0, 9, 170, 0, 8, 5, 0, 8, 133, 0, 8, 69, 0, 9, 234, 80, 7, 8,
  112. 0, 8, 93, 0, 8, 29, 0, 9, 154, 84, 7, 83, 0, 8, 125, 0, 8, 61,
  113. 0, 9, 218, 82, 7, 23, 0, 8, 109, 0, 8, 45, 0, 9, 186,
  114. 0, 8, 13, 0, 8, 141, 0, 8, 77, 0, 9, 250, 80, 7, 3, 0, 8, 83,
  115. 0, 8, 19, 85, 8, 195, 83, 7, 35, 0, 8, 115, 0, 8, 51, 0, 9,
  116. 198, 81, 7, 11, 0, 8, 99, 0, 8, 35, 0, 9, 166, 0, 8, 3, 0, 8,
  117. 131, 0, 8, 67, 0, 9, 230, 80, 7, 7, 0, 8, 91, 0, 8, 27, 0, 9,
  118. 150, 84, 7, 67, 0, 8, 123, 0, 8, 59, 0, 9, 214, 82, 7, 19, 0,
  119. 8, 107, 0, 8, 43, 0, 9, 182, 0, 8, 11, 0, 8, 139, 0, 8, 75, 0,
  120. 9, 246, 80, 7, 5, 0, 8, 87, 0, 8, 23, 192, 8, 0, 83, 7, 51, 0,
  121. 8, 119, 0, 8, 55, 0, 9, 206, 81, 7, 15, 0, 8, 103, 0, 8, 39, 0
  122. , 9, 174, 0, 8, 7, 0, 8, 135, 0, 8, 71, 0, 9, 238, 80, 7, 9, 0
  123. , 8, 95, 0, 8, 31, 0, 9, 158, 84, 7, 99, 0, 8, 127, 0, 8, 63,
  124. 0, 9, 222, 82, 7, 27, 0, 8, 111, 0, 8, 47, 0, 9, 190, 0, 8, 15
  125. , 0, 8, 143, 0, 8, 79, 0, 9, 254, 96, 7, 256, 0, 8, 80, 0, 8,
  126. 16, 84, 8, 115, 82, 7, 31, 0, 8, 112, 0, 8, 48, 0, 9, 193, 80,
  127. 7, 10, 0, 8, 96, 0, 8, 32, 0, 9, 161, 0, 8, 0, 0, 8, 128, 0, 8
  128. , 64, 0, 9, 225, 80, 7, 6, 0, 8, 88, 0, 8, 24, 0, 9, 145, 83,
  129. 7, 59, 0, 8, 120, 0, 8, 56, 0, 9, 209, 81, 7, 17, 0, 8, 104, 0
  130. , 8, 40, 0, 9, 177, 0, 8, 8, 0, 8, 136, 0, 8, 72, 0, 9, 241,
  131. 80, 7, 4, 0, 8, 84, 0, 8, 20, 85, 8, 227, 83, 7, 43, 0, 8, 116
  132. , 0, 8, 52, 0, 9, 201, 81, 7, 13, 0, 8, 100, 0, 8, 36, 0, 9,
  133. 169, 0, 8, 4, 0, 8, 132, 0, 8, 68, 0, 9, 233, 80, 7, 8, 0, 8,
  134. 92, 0, 8, 28, 0, 9, 153, 84, 7, 83, 0, 8, 124, 0, 8, 60, 0, 9,
  135. 217, 82, 7, 23, 0, 8, 108, 0, 8, 44, 0, 9, 185, 0, 8, 12, 0, 8
  136. , 140, 0, 8, 76, 0, 9, 249, 80, 7, 3, 0, 8, 82, 0, 8, 18, 85,
  137. 8, 163, 83, 7, 35, 0, 8, 114, 0, 8, 50, 0, 9, 197, 81, 7, 11,
  138. 0, 8, 98, 0, 8, 34, 0, 9, 165, 0, 8, 2, 0, 8, 130, 0, 8, 66, 0
  139. , 9, 229, 80, 7, 7, 0, 8, 90, 0, 8, 26, 0, 9, 149, 84, 7, 67,
  140. 0, 8, 122, 0, 8, 58, 0, 9, 213, 82, 7, 19, 0, 8, 106, 0, 8, 42
  141. , 0, 9, 181, 0, 8, 10, 0, 8, 138, 0, 8, 74, 0, 9, 245, 80, 7,
  142. 5, 0, 8, 86, 0, 8, 22, 192, 8, 0, 83, 7, 51, 0, 8, 118, 0, 8,
  143. 54, 0, 9, 205, 81, 7, 15, 0, 8, 102, 0, 8, 38, 0, 9, 173, 0, 8
  144. , 6, 0, 8, 134, 0, 8, 70, 0, 9, 237, 80, 7, 9, 0, 8, 94, 0, 8,
  145. 30, 0, 9, 157, 84, 7, 99, 0, 8, 126, 0, 8, 62, 0, 9, 221, 82,
  146. 7, 27, 0, 8, 110, 0, 8, 46, 0, 9, 189, 0, 8,
  147. 14, 0, 8, 142, 0, 8, 78, 0, 9, 253, 96, 7, 256, 0, 8, 81, 0, 8
  148. , 17, 85, 8, 131, 82, 7, 31, 0, 8, 113, 0, 8, 49, 0, 9, 195,
  149. 80, 7, 10, 0, 8, 97, 0, 8, 33, 0, 9, 163, 0, 8, 1, 0, 8, 129,
  150. 0, 8, 65, 0, 9, 227, 80, 7, 6, 0, 8, 89, 0, 8, 25, 0, 9, 147,
  151. 83, 7, 59, 0, 8, 121, 0, 8, 57, 0, 9, 211, 81, 7, 17, 0, 8,
  152. 105, 0, 8, 41, 0, 9, 179, 0, 8, 9, 0, 8, 137, 0, 8, 73, 0, 9,
  153. 243, 80, 7, 4, 0, 8, 85, 0, 8, 21, 80, 8, 258, 83, 7, 43, 0, 8
  154. , 117, 0, 8, 53, 0, 9, 203, 81, 7, 13, 0, 8, 101, 0, 8, 37, 0,
  155. 9, 171, 0, 8, 5, 0, 8, 133, 0, 8, 69, 0, 9, 235, 80, 7, 8, 0,
  156. 8, 93, 0, 8, 29, 0, 9, 155, 84, 7, 83, 0, 8, 125, 0, 8, 61, 0,
  157. 9, 219, 82, 7, 23, 0, 8, 109, 0, 8, 45, 0, 9, 187, 0, 8, 13, 0
  158. , 8, 141, 0, 8, 77, 0, 9, 251, 80, 7, 3, 0, 8, 83, 0, 8, 19,
  159. 85, 8, 195, 83, 7, 35, 0, 8, 115, 0, 8, 51, 0, 9, 199, 81, 7,
  160. 11, 0, 8, 99, 0, 8, 35, 0, 9, 167, 0, 8, 3, 0, 8, 131, 0, 8,
  161. 67, 0, 9, 231, 80, 7, 7, 0, 8, 91, 0, 8, 27, 0, 9, 151, 84, 7,
  162. 67, 0, 8, 123, 0, 8, 59, 0, 9, 215, 82, 7, 19, 0, 8, 107, 0, 8
  163. , 43, 0, 9, 183, 0, 8, 11, 0, 8, 139, 0, 8, 75, 0, 9, 247, 80,
  164. 7, 5, 0, 8, 87, 0, 8, 23, 192, 8, 0, 83, 7, 51, 0, 8, 119, 0,
  165. 8, 55, 0, 9, 207, 81, 7, 15, 0, 8, 103, 0, 8, 39, 0, 9, 175, 0
  166. , 8, 7, 0, 8, 135, 0, 8, 71, 0, 9, 239, 80, 7, 9, 0, 8, 95, 0,
  167. 8, 31, 0, 9, 159, 84, 7, 99, 0, 8, 127, 0, 8, 63, 0, 9, 223,
  168. 82, 7, 27, 0, 8, 111, 0, 8, 47, 0, 9, 191, 0, 8, 15, 0, 8, 143
  169. , 0, 8, 79, 0, 9, 255
  170. };
  171. //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'"
  172. internal static readonly int[] fixed_td =
  173. {
  174. 80, 5, 1, 87, 5, 257, 83, 5, 17, 91, 5, 4097, 81, 5, 5, 89, 5,
  175. 1025, 85, 5, 65, 93, 5, 16385, 80, 5, 3, 88, 5, 513, 84, 5, 33
  176. ,
  177. 92, 5, 8193, 82, 5, 9, 90, 5, 2049, 86, 5, 129, 192, 5, 24577,
  178. 80
  179. , 5, 2, 87, 5, 385, 83, 5, 25, 91, 5, 6145, 81, 5, 7, 89, 5,
  180. 1537
  181. , 85, 5, 97, 93, 5, 24577, 80, 5, 4, 88, 5, 769, 84, 5, 49, 92
  182. , 5
  183. , 12289, 82, 5, 13, 90, 5, 3073, 86, 5, 193, 192, 5, 24577
  184. };
  185. // Tables for deflate from PKZIP's appnote.txt.
  186. //UPGRADE_NOTE: Final was removed from the declaration of 'cplens'. "ms-help://MS.VSCC.v80/dv_commoner/local/redirect.htm?index='!DefaultContextWindowIndex'&keyword='jlca1003'"
  187. internal static readonly int[] cplens =
  188. {
  189. 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31, 35, 43,
  190. 51
  191. , 59, 67, 83, 99, 115, 131, 163, 195, 227, 258, 0, 0
  192. };
  193. // see note #13 above about 258
  194. //UPGRADE_NOTE: Final was removed from the declaration of 'cplext'. "ms-help://MS.VSCC.v80/dv_commoner/local/redirect.htm?index='!DefaultContextWindowIndex'&keyword='jlca1003'"
  195. internal static readonly int[] cplext =
  196. {
  197. 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4
  198. , 4
  199. , 4, 5, 5, 5, 5, 0, 112, 112
  200. };
  201. //UPGRADE_NOTE: Final was removed from the declaration of 'cpdist'. "ms-help://MS.VSCC.v80/dv_commoner/local/redirect.htm?index='!DefaultContextWindowIndex'&keyword='jlca1003'"
  202. internal static readonly int[] cpdist =
  203. {
  204. 1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193, 257,
  205. 385
  206. , 513, 769, 1025, 1537, 2049, 3073, 4097, 6145, 8193, 12289,
  207. 16385,
  208. 24577
  209. };
  210. //UPGRADE_NOTE: Final was removed from the declaration of 'cpdext'. "ms-help://MS.VSCC.v80/dv_commoner/local/redirect.htm?index='!DefaultContextWindowIndex'&keyword='jlca1003'"
  211. internal static readonly int[] cpdext =
  212. {
  213. 0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9
  214. ,
  215. 10, 10, 11, 11, 12, 12, 13, 13
  216. };
  217. // If BMAX needs to be larger than 16, then h and x[] should be uLong.
  218. internal int[] c; // bit length count table
  219. internal int[] hn; // hufts used in space
  220. internal int[] r; // table entry for structure assignment
  221. internal int[] u; // table stack
  222. internal int[] v; // work area for huft_build
  223. internal int[] x; // bit offsets, then code stack
  224. private int huft_build(int[] b, int bindex, int n, int s, int[] d, int[] e, int[] t, int[] m, int[] hp, int[] hn,
  225. int[] v)
  226. {
  227. // Given a list of code lengths and a maximum table size, make a set of
  228. // tables to decode that set of codes. Return Z_OK on success, Z_BUF_ERROR
  229. // if the given code set is incomplete (the tables are still built in this
  230. // case), Z_DATA_ERROR if the input is invalid (an over-subscribed set of
  231. // lengths), or Z_MEM_ERROR if not enough memory.
  232. int a; // counter for codes of length k
  233. int f; // i repeats in table every f entries
  234. int g; // maximum code length
  235. int h; // table level
  236. int i; // counter, current code
  237. int j; // counter
  238. int k; // number of bits in current code
  239. int l; // bits per table (returned in m)
  240. int mask; // (1 << w) - 1, to avoid cc -O bug on HP
  241. int p; // pointer into c[], b[], or v[]
  242. int q; // points to current table
  243. int w; // bits before this table == (l * h)
  244. int xp; // pointer into x
  245. int y; // number of dummy codes added
  246. int z; // number of entries in current table
  247. // Generate counts for each bit length
  248. p = 0;
  249. i = n;
  250. do
  251. {
  252. c[b[bindex + p]]++;
  253. p++;
  254. i--; // assume all entries <= BMAX
  255. }
  256. while (i != 0);
  257. if (c[0] == n)
  258. {
  259. // null input--all zero length codes
  260. t[0] = -1;
  261. m[0] = 0;
  262. return Z_OK;
  263. }
  264. // Find minimum and maximum length, bound *m by those
  265. l = m[0];
  266. for (j = 1; j <= BMAX; j++)
  267. {
  268. if (c[j] != 0)
  269. {
  270. break;
  271. }
  272. }
  273. k = j; // minimum code length
  274. if (l < j)
  275. {
  276. l = j;
  277. }
  278. for (i = BMAX; i != 0; i--)
  279. {
  280. if (c[i] != 0)
  281. {
  282. break;
  283. }
  284. }
  285. g = i; // maximum code length
  286. if (l > i)
  287. {
  288. l = i;
  289. }
  290. m[0] = l;
  291. // Adjust last length count to fill out codes, if needed
  292. for (y = 1 << j; j < i; j++, y <<= 1)
  293. {
  294. if ((y -= c[j]) < 0)
  295. {
  296. return Z_DATA_ERROR;
  297. }
  298. }
  299. if ((y -= c[i]) < 0)
  300. {
  301. return Z_DATA_ERROR;
  302. }
  303. c[i] += y;
  304. // Generate starting offsets into the value table for each length
  305. x[1] = j = 0;
  306. p = 1;
  307. xp = 2;
  308. while (--i != 0)
  309. {
  310. // note that i == g from above
  311. x[xp] = (j += c[p]);
  312. xp++;
  313. p++;
  314. }
  315. // Make a table of values in order of bit lengths
  316. i = 0;
  317. p = 0;
  318. do
  319. {
  320. if ((j = b[bindex + p]) != 0)
  321. {
  322. v[x[j]++] = i;
  323. }
  324. p++;
  325. }
  326. while (++i < n);
  327. n = x[g]; // set n to length of v
  328. // Generate the Huffman codes and for each, make the table entries
  329. x[0] = i = 0; // first Huffman code is zero
  330. p = 0; // grab values in bit order
  331. h = -1; // no tables yet--level -1
  332. w = -l; // bits decoded == (l * h)
  333. u[0] = 0; // just to keep compilers happy
  334. q = 0; // ditto
  335. z = 0; // ditto
  336. // go through the bit lengths (k already is bits in shortest code)
  337. for (; k <= g; k++)
  338. {
  339. a = c[k];
  340. while (a-- != 0)
  341. {
  342. // here i is the Huffman code of length k bits for value *p
  343. // make tables up to required level
  344. while (k > w + l)
  345. {
  346. h++;
  347. w += l; // previous table always l bits
  348. // compute minimum size table less than or equal to l bits
  349. z = g - w;
  350. z = (z > l) ? l : z; // table size upper limit
  351. if ((f = 1 << (j = k - w)) > a + 1)
  352. {
  353. // try a k-w bit table
  354. // too few codes for k-w bit table
  355. f -= (a + 1); // deduct codes from patterns left
  356. xp = k;
  357. if (j < z)
  358. {
  359. while (++j < z)
  360. {
  361. // try smaller tables up to z bits
  362. if ((f <<= 1) <= c[++xp])
  363. {
  364. break; // enough codes to use up j bits
  365. }
  366. f -= c[xp]; // else deduct codes from patterns
  367. }
  368. }
  369. }
  370. z = 1 << j; // table entries for j-bit table
  371. // allocate new table
  372. if (hn[0] + z > MANY)
  373. {
  374. // (note: doesn't matter for fixed)
  375. return Z_DATA_ERROR; // overflow of MANY
  376. }
  377. u[h] = q = hn[0]; // DEBUG
  378. hn[0] += z;
  379. // connect to last table, if there is one
  380. if (h != 0)
  381. {
  382. x[h] = i; // save pattern for backing up
  383. r[0] = (sbyte)j; // bits in this table
  384. r[1] = (sbyte)l; // bits to dump before this table
  385. j = SharedUtils.URShift(i, (w - l));
  386. r[2] = (q - u[h - 1] - j); // offset to this table
  387. Array.Copy(r, 0, hp, (u[h - 1] + j) * 3, 3); // connect to last table
  388. }
  389. else
  390. {
  391. t[0] = q; // first table is returned result
  392. }
  393. }
  394. // set up table entry in r
  395. r[1] = (sbyte)(k - w);
  396. if (p >= n)
  397. {
  398. r[0] = 128 + 64; // out of values--invalid code
  399. }
  400. else if (v[p] < s)
  401. {
  402. r[0] = (sbyte)(v[p] < 256 ? 0 : 32 + 64); // 256 is end-of-block
  403. r[2] = v[p++]; // simple code is just the value
  404. }
  405. else
  406. {
  407. r[0] = (sbyte)(e[v[p] - s] + 16 + 64); // non-simple--look up in lists
  408. r[2] = d[v[p++] - s];
  409. }
  410. // fill code-like entries with r
  411. f = 1 << (k - w);
  412. for (j = SharedUtils.URShift(i, w); j < z; j += f)
  413. {
  414. Array.Copy(r, 0, hp, (q + j) * 3, 3);
  415. }
  416. // backwards increment the k-bit code i
  417. for (j = 1 << (k - 1); (i & j) != 0; j = SharedUtils.URShift(j, 1))
  418. {
  419. i ^= j;
  420. }
  421. i ^= j;
  422. // backup over finished tables
  423. mask = (1 << w) - 1; // needed on HP, cc -O bug
  424. while ((i & mask) != x[h])
  425. {
  426. h--; // don't need to update q
  427. w -= l;
  428. mask = (1 << w) - 1;
  429. }
  430. }
  431. }
  432. // Return Z_BUF_ERROR if we were given an incomplete table
  433. return y != 0 && g != 1 ? Z_BUF_ERROR : Z_OK;
  434. }
  435. internal int inflate_trees_bits(int[] c, int[] bb, int[] tb, int[] hp, ZlibCodec z)
  436. {
  437. int result;
  438. initWorkArea(19);
  439. hn[0] = 0;
  440. result = huft_build(c, 0, 19, 19, null, null, tb, bb, hp, hn, v);
  441. if (result == Z_DATA_ERROR)
  442. {
  443. z.Message = "oversubscribed dynamic bit lengths tree";
  444. }
  445. else if (result == Z_BUF_ERROR || bb[0] == 0)
  446. {
  447. z.Message = "incomplete dynamic bit lengths tree";
  448. result = Z_DATA_ERROR;
  449. }
  450. return result;
  451. }
  452. internal int inflate_trees_dynamic(int nl, int nd, int[] c, int[] bl, int[] bd, int[] tl, int[] td, int[] hp,
  453. ZlibCodec z)
  454. {
  455. int result;
  456. // build literal/length tree
  457. initWorkArea(288);
  458. hn[0] = 0;
  459. result = huft_build(c, 0, nl, 257, cplens, cplext, tl, bl, hp, hn, v);
  460. if (result != Z_OK || bl[0] == 0)
  461. {
  462. if (result == Z_DATA_ERROR)
  463. {
  464. z.Message = "oversubscribed literal/length tree";
  465. }
  466. else if (result != Z_MEM_ERROR)
  467. {
  468. z.Message = "incomplete literal/length tree";
  469. result = Z_DATA_ERROR;
  470. }
  471. return result;
  472. }
  473. // build distance tree
  474. initWorkArea(288);
  475. result = huft_build(c, nl, nd, 0, cpdist, cpdext, td, bd, hp, hn, v);
  476. if (result != Z_OK || (bd[0] == 0 && nl > 257))
  477. {
  478. if (result == Z_DATA_ERROR)
  479. {
  480. z.Message = "oversubscribed distance tree";
  481. }
  482. else if (result == Z_BUF_ERROR)
  483. {
  484. z.Message = "incomplete distance tree";
  485. result = Z_DATA_ERROR;
  486. }
  487. else if (result != Z_MEM_ERROR)
  488. {
  489. z.Message = "empty distance tree with lengths";
  490. result = Z_DATA_ERROR;
  491. }
  492. return result;
  493. }
  494. return Z_OK;
  495. }
  496. internal static int inflate_trees_fixed(int[] bl, int[] bd, int[][] tl, int[][] td, ZlibCodec z)
  497. {
  498. bl[0] = fixed_bl;
  499. bd[0] = fixed_bd;
  500. tl[0] = fixed_tl;
  501. td[0] = fixed_td;
  502. return Z_OK;
  503. }
  504. private void initWorkArea(int vsize)
  505. {
  506. if (hn == null)
  507. {
  508. hn = new int[1];
  509. v = new int[vsize];
  510. c = new int[BMAX + 1];
  511. r = new int[3];
  512. u = new int[BMAX];
  513. x = new int[BMAX + 1];
  514. }
  515. else
  516. {
  517. if (v.Length < vsize)
  518. {
  519. v = new int[vsize];
  520. }
  521. Array.Clear(v, 0, vsize);
  522. Array.Clear(c, 0, BMAX + 1);
  523. r[0] = 0;
  524. r[1] = 0;
  525. r[2] = 0;
  526. // for(int i=0; i<BMAX; i++){u[i]=0;}
  527. //Array.Copy(c, 0, u, 0, BMAX);
  528. Array.Clear(u, 0, BMAX);
  529. // for(int i=0; i<BMAX+1; i++){x[i]=0;}
  530. //Array.Copy(c, 0, x, 0, BMAX + 1);
  531. Array.Clear(x, 0, BMAX + 1);
  532. }
  533. }
  534. }
  535. }