Tree.cs 20 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487
  1. // Tree.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 13:29:50>
  19. //
  20. // ------------------------------------------------------------------
  21. //
  22. // This module defines classes for zlib compression and
  23. // decompression. This code is derived from the jzlib implementation of
  24. // zlib. In keeping with the license for jzlib, the copyright to that
  25. // code is below.
  26. //
  27. // ------------------------------------------------------------------
  28. //
  29. // Copyright (c) 2000,2001,2002,2003 ymnk, JCraft,Inc. All rights reserved.
  30. //
  31. // Redistribution and use in source and binary forms, with or without
  32. // modification, are permitted provided that the following conditions are met:
  33. //
  34. // 1. Redistributions of source code must retain the above copyright notice,
  35. // this list of conditions and the following disclaimer.
  36. //
  37. // 2. Redistributions in binary form must reproduce the above copyright
  38. // notice, this list of conditions and the following disclaimer in
  39. // the documentation and/or other materials provided with the distribution.
  40. //
  41. // 3. The names of the authors may not be used to endorse or promote products
  42. // derived from this software without specific prior written permission.
  43. //
  44. // THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED WARRANTIES,
  45. // INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
  46. // FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL JCRAFT,
  47. // INC. OR ANY CONTRIBUTORS TO THIS SOFTWARE BE LIABLE FOR ANY DIRECT, INDIRECT,
  48. // INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  49. // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA,
  50. // OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
  51. // LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
  52. // NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE,
  53. // EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  54. //
  55. // -----------------------------------------------------------------------
  56. //
  57. // This program is based on zlib-1.1.3; credit to authors
  58. // Jean-loup Gailly(jloup@gzip.org) and Mark Adler(madler@alumni.caltech.edu)
  59. // and contributors of zlib.
  60. //
  61. // -----------------------------------------------------------------------
  62. using System;
  63. namespace SharpCompress.Compressors.Deflate
  64. {
  65. internal sealed partial class DeflateManager
  66. {
  67. #region Nested type: Tree
  68. private sealed class Tree
  69. {
  70. internal const int Buf_size = 8 * 2;
  71. private static readonly int HEAP_SIZE = (2 * InternalConstants.L_CODES + 1);
  72. internal static readonly sbyte[] bl_order =
  73. {
  74. 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2,
  75. 14,
  76. 1, 15
  77. };
  78. // The lengths of the bit length codes are sent in order of decreasing
  79. // probability, to avoid transmitting the lengths for unused bit
  80. // length codes.
  81. // see definition of array dist_code below
  82. //internal const int DIST_CODE_LEN = 512;
  83. private static readonly sbyte[] _dist_code =
  84. {
  85. 0, 1, 2, 3, 4, 4, 5, 5, 6, 6, 6, 6, 7, 7, 7, 7,
  86. 8, 8, 8, 8, 8, 8, 8, 8, 9, 9, 9, 9, 9, 9, 9, 9,
  87. 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10,
  88. 10, 10,
  89. 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11,
  90. 11, 11,
  91. 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12,
  92. 12, 12,
  93. 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12,
  94. 12, 12,
  95. 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13,
  96. 13, 13,
  97. 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13,
  98. 13, 13,
  99. 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14,
  100. 14, 14,
  101. 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14,
  102. 14, 14,
  103. 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14,
  104. 14, 14,
  105. 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14,
  106. 14, 14,
  107. 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15,
  108. 15, 15,
  109. 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15,
  110. 15, 15,
  111. 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15,
  112. 15, 15,
  113. 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15,
  114. 15, 15,
  115. 0, 0, 16, 17, 18, 18, 19, 19, 20, 20, 20, 20, 21, 21,
  116. 21, 21,
  117. 22, 22, 22, 22, 22, 22, 22, 22, 23, 23, 23, 23, 23, 23,
  118. 23, 23,
  119. 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
  120. 24, 24,
  121. 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
  122. 25, 25,
  123. 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26,
  124. 26, 26,
  125. 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26,
  126. 26, 26,
  127. 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27,
  128. 27, 27,
  129. 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27,
  130. 27, 27,
  131. 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28,
  132. 28, 28,
  133. 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28,
  134. 28, 28,
  135. 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28,
  136. 28, 28,
  137. 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28,
  138. 28, 28,
  139. 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29,
  140. 29, 29,
  141. 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29,
  142. 29, 29,
  143. 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29,
  144. 29, 29,
  145. 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29,
  146. 29, 29
  147. };
  148. internal static readonly sbyte[] LengthCode =
  149. {
  150. 0, 1, 2, 3, 4, 5, 6, 7, 8, 8, 9, 9, 10, 10, 11, 11,
  151. 12, 12, 12, 12, 13, 13, 13, 13, 14, 14, 14, 14, 15, 15
  152. , 15, 15,
  153. 16, 16, 16, 16, 16, 16, 16, 16, 17, 17, 17, 17, 17, 17
  154. , 17, 17,
  155. 18, 18, 18, 18, 18, 18, 18, 18, 19, 19, 19, 19, 19, 19
  156. , 19, 19,
  157. 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20
  158. , 20, 20,
  159. 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21
  160. , 21, 21,
  161. 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22
  162. , 22, 22,
  163. 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23
  164. , 23, 23,
  165. 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24
  166. , 24, 24,
  167. 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24
  168. , 24, 24,
  169. 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25
  170. , 25, 25,
  171. 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25
  172. , 25, 25,
  173. 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26
  174. , 26, 26,
  175. 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26
  176. , 26, 26,
  177. 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27
  178. , 27, 27,
  179. 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27
  180. , 27, 28
  181. };
  182. internal static readonly int[] LengthBase =
  183. {
  184. 0, 1, 2, 3, 4, 5, 6, 7, 8, 10, 12, 14, 16, 20, 24, 28,
  185. 32, 40, 48, 56, 64, 80, 96, 112, 128, 160, 192, 224, 0
  186. };
  187. internal static readonly int[] DistanceBase =
  188. {
  189. 0, 1, 2, 3, 4, 6, 8, 12, 16, 24, 32, 48, 64, 96, 128,
  190. 192,
  191. 256, 384, 512, 768, 1024, 1536, 2048, 3072, 4096, 6144
  192. , 8192, 12288, 16384, 24576
  193. };
  194. internal short[] dyn_tree; // the dynamic tree
  195. internal int max_code; // largest code with non zero frequency
  196. internal StaticTree staticTree; // the corresponding static tree
  197. /// <summary>
  198. /// Map from a distance to a distance code.
  199. /// </summary>
  200. /// <remarks>
  201. /// No side effects. _dist_code[256] and _dist_code[257] are never used.
  202. /// </remarks>
  203. internal static int DistanceCode(int dist)
  204. {
  205. return (dist < 256)
  206. ? _dist_code[dist]
  207. : _dist_code[256 + SharedUtils.URShift(dist, 7)];
  208. }
  209. // Compute the optimal bit lengths for a tree and update the total bit length
  210. // for the current block.
  211. // IN assertion: the fields freq and dad are set, heap[heap_max] and
  212. // above are the tree nodes sorted by increasing frequency.
  213. // OUT assertions: the field len is set to the optimal bit length, the
  214. // array bl_count contains the frequencies for each bit length.
  215. // The length opt_len is updated; static_len is also updated if stree is
  216. // not null.
  217. internal void gen_bitlen(DeflateManager s)
  218. {
  219. short[] tree = dyn_tree;
  220. short[] stree = staticTree.treeCodes;
  221. int[] extra = staticTree.extraBits;
  222. int base_Renamed = staticTree.extraBase;
  223. int max_length = staticTree.maxLength;
  224. int h; // heap index
  225. int n, m; // iterate over the tree elements
  226. int bits; // bit length
  227. int xbits; // extra bits
  228. short f; // frequency
  229. int overflow = 0; // number of elements with bit length too large
  230. for (bits = 0; bits <= InternalConstants.MAX_BITS; bits++)
  231. {
  232. s.bl_count[bits] = 0;
  233. }
  234. // In a first pass, compute the optimal bit lengths (which may
  235. // overflow in the case of the bit length tree).
  236. tree[s.heap[s.heap_max] * 2 + 1] = 0; // root of the heap
  237. for (h = s.heap_max + 1; h < HEAP_SIZE; h++)
  238. {
  239. n = s.heap[h];
  240. bits = tree[tree[n * 2 + 1] * 2 + 1] + 1;
  241. if (bits > max_length)
  242. {
  243. bits = max_length;
  244. overflow++;
  245. }
  246. tree[n * 2 + 1] = (short)bits;
  247. // We overwrite tree[n*2+1] which is no longer needed
  248. if (n > max_code)
  249. {
  250. continue; // not a leaf node
  251. }
  252. s.bl_count[bits]++;
  253. xbits = 0;
  254. if (n >= base_Renamed)
  255. {
  256. xbits = extra[n - base_Renamed];
  257. }
  258. f = tree[n * 2];
  259. s.opt_len += f * (bits + xbits);
  260. if (stree != null)
  261. {
  262. s.static_len += f * (stree[n * 2 + 1] + xbits);
  263. }
  264. }
  265. if (overflow == 0)
  266. {
  267. return;
  268. }
  269. // This happens for example on obj2 and pic of the Calgary corpus
  270. // Find the first bit length which could increase:
  271. do
  272. {
  273. bits = max_length - 1;
  274. while (s.bl_count[bits] == 0)
  275. {
  276. bits--;
  277. }
  278. s.bl_count[bits]--; // move one leaf down the tree
  279. s.bl_count[bits + 1] = (short)(s.bl_count[bits + 1] + 2); // move one overflow item as its brother
  280. s.bl_count[max_length]--;
  281. // The brother of the overflow item also moves one step up,
  282. // but this does not affect bl_count[max_length]
  283. overflow -= 2;
  284. }
  285. while (overflow > 0);
  286. for (bits = max_length; bits != 0; bits--)
  287. {
  288. n = s.bl_count[bits];
  289. while (n != 0)
  290. {
  291. m = s.heap[--h];
  292. if (m > max_code)
  293. {
  294. continue;
  295. }
  296. if (tree[m * 2 + 1] != bits)
  297. {
  298. s.opt_len = (int)(s.opt_len + (bits - (long)tree[m * 2 + 1]) * tree[m * 2]);
  299. tree[m * 2 + 1] = (short)bits;
  300. }
  301. n--;
  302. }
  303. }
  304. }
  305. // Construct one Huffman tree and assigns the code bit strings and lengths.
  306. // Update the total bit length for the current block.
  307. // IN assertion: the field freq is set for all tree elements.
  308. // OUT assertions: the fields len and code are set to the optimal bit length
  309. // and corresponding code. The length opt_len is updated; static_len is
  310. // also updated if stree is not null. The field max_code is set.
  311. internal void build_tree(DeflateManager s)
  312. {
  313. short[] tree = dyn_tree;
  314. short[] stree = staticTree.treeCodes;
  315. int elems = staticTree.elems;
  316. int n, m; // iterate over heap elements
  317. int max_code = -1; // largest code with non zero frequency
  318. int node; // new node being created
  319. // Construct the initial heap, with least frequent element in
  320. // heap[1]. The sons of heap[n] are heap[2*n] and heap[2*n+1].
  321. // heap[0] is not used.
  322. s.heap_len = 0;
  323. s.heap_max = HEAP_SIZE;
  324. for (n = 0; n < elems; n++)
  325. {
  326. if (tree[n * 2] != 0)
  327. {
  328. s.heap[++s.heap_len] = max_code = n;
  329. s.depth[n] = 0;
  330. }
  331. else
  332. {
  333. tree[n * 2 + 1] = 0;
  334. }
  335. }
  336. // The pkzip format requires that at least one distance code exists,
  337. // and that at least one bit should be sent even if there is only one
  338. // possible code. So to avoid special checks later on we force at least
  339. // two codes of non zero frequency.
  340. while (s.heap_len < 2)
  341. {
  342. node = s.heap[++s.heap_len] = (max_code < 2 ? ++max_code : 0);
  343. tree[node * 2] = 1;
  344. s.depth[node] = 0;
  345. s.opt_len--;
  346. if (stree != null)
  347. {
  348. s.static_len -= stree[node * 2 + 1];
  349. }
  350. // node is 0 or 1 so it does not have extra bits
  351. }
  352. this.max_code = max_code;
  353. // The elements heap[heap_len/2+1 .. heap_len] are leaves of the tree,
  354. // establish sub-heaps of increasing lengths:
  355. for (n = s.heap_len / 2; n >= 1; n--)
  356. {
  357. s.pqdownheap(tree, n);
  358. }
  359. // Construct the Huffman tree by repeatedly combining the least two
  360. // frequent nodes.
  361. node = elems; // next internal node of the tree
  362. do
  363. {
  364. // n = node of least frequency
  365. n = s.heap[1];
  366. s.heap[1] = s.heap[s.heap_len--];
  367. s.pqdownheap(tree, 1);
  368. m = s.heap[1]; // m = node of next least frequency
  369. s.heap[--s.heap_max] = n; // keep the nodes sorted by frequency
  370. s.heap[--s.heap_max] = m;
  371. // Create a new node father of n and m
  372. tree[node * 2] = unchecked((short)(tree[n * 2] + tree[m * 2]));
  373. s.depth[node] = (sbyte)(Math.Max((byte)s.depth[n], (byte)s.depth[m]) + 1);
  374. tree[n * 2 + 1] = tree[m * 2 + 1] = (short)node;
  375. // and insert the new node in the heap
  376. s.heap[1] = node++;
  377. s.pqdownheap(tree, 1);
  378. }
  379. while (s.heap_len >= 2);
  380. s.heap[--s.heap_max] = s.heap[1];
  381. // At this point, the fields freq and dad are set. We can now
  382. // generate the bit lengths.
  383. gen_bitlen(s);
  384. // The field len is now set, we can generate the bit codes
  385. gen_codes(tree, max_code, s.bl_count);
  386. }
  387. // Generate the codes for a given tree and bit counts (which need not be
  388. // optimal).
  389. // IN assertion: the array bl_count contains the bit length statistics for
  390. // the given tree and the field len is set for all tree elements.
  391. // OUT assertion: the field code is set for all tree elements of non
  392. // zero code length.
  393. internal static void gen_codes(short[] tree, int max_code, short[] bl_count)
  394. {
  395. var next_code = new short[InternalConstants.MAX_BITS + 1]; // next code value for each bit length
  396. short code = 0; // running code value
  397. int bits; // bit index
  398. int n; // code index
  399. // The distribution counts are first used to generate the code values
  400. // without bit reversal.
  401. for (bits = 1; bits <= InternalConstants.MAX_BITS; bits++)
  402. {
  403. unchecked
  404. {
  405. next_code[bits] = code = (short)((code + bl_count[bits - 1]) << 1);
  406. }
  407. }
  408. // Check that the bit counts in bl_count are consistent. The last code
  409. // must be all ones.
  410. //Assert (code + bl_count[MAX_BITS]-1 == (1<<MAX_BITS)-1,
  411. // "inconsistent bit counts");
  412. //Tracev((stderr,"\ngen_codes: max_code %d ", max_code));
  413. for (n = 0; n <= max_code; n++)
  414. {
  415. int len = tree[n * 2 + 1];
  416. if (len == 0)
  417. {
  418. continue;
  419. }
  420. // Now reverse the bits
  421. tree[n * 2] = unchecked((short)(bi_reverse(next_code[len]++, len)));
  422. }
  423. }
  424. // Reverse the first len bits of a code, using straightforward code (a faster
  425. // method would use a table)
  426. // IN assertion: 1 <= len <= 15
  427. internal static int bi_reverse(int code, int len)
  428. {
  429. int res = 0;
  430. do
  431. {
  432. res |= code & 1;
  433. code >>= 1; //SharedUtils.URShift(code, 1);
  434. res <<= 1;
  435. }
  436. while (--len > 0);
  437. return res >> 1;
  438. }
  439. }
  440. #endregion
  441. }
  442. }