Zlib.cs 18 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492
  1. // Zlib.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-November-07 05:26:55>
  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, but significantly modified. The object model is not the same,
  25. // and many of the behaviors are new or different. Nonetheless, in
  26. // keeping with the license for jzlib, the copyright to that code is
  27. // included below.
  28. //
  29. // ------------------------------------------------------------------
  30. //
  31. // Copyright (c) 2000,2001,2002,2003 ymnk, JCraft,Inc. All rights reserved.
  32. //
  33. // Redistribution and use in source and binary forms, with or without
  34. // modification, are permitted provided that the following conditions are met:
  35. //
  36. // 1. Redistributions of source code must retain the above copyright notice,
  37. // this list of conditions and the following disclaimer.
  38. //
  39. // 2. Redistributions in binary form must reproduce the above copyright
  40. // notice, this list of conditions and the following disclaimer in
  41. // the documentation and/or other materials provided with the distribution.
  42. //
  43. // 3. The names of the authors may not be used to endorse or promote products
  44. // derived from this software without specific prior written permission.
  45. //
  46. // THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED WARRANTIES,
  47. // INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
  48. // FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL JCRAFT,
  49. // INC. OR ANY CONTRIBUTORS TO THIS SOFTWARE BE LIABLE FOR ANY DIRECT, INDIRECT,
  50. // INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  51. // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA,
  52. // OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
  53. // LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
  54. // NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE,
  55. // EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  56. //
  57. // -----------------------------------------------------------------------
  58. //
  59. // This program is based on zlib-1.1.3; credit to authors
  60. // Jean-loup Gailly(jloup@gzip.org) and Mark Adler(madler@alumni.caltech.edu)
  61. // and contributors of zlib.
  62. //
  63. // -----------------------------------------------------------------------
  64. using System;
  65. using System.IO;
  66. namespace SharpCompress.Compressors.Deflate
  67. {
  68. /// <summary>
  69. /// The compression level to be used when using a DeflateStream or ZlibStream with CompressionMode.Compress.
  70. /// </summary>
  71. public enum CompressionLevel
  72. {
  73. /// <summary>
  74. /// None means that the data will be simply stored, with no change at all.
  75. /// If you are producing ZIPs for use on Mac OSX, be aware that archives produced with CompressionLevel.None
  76. /// cannot be opened with the default zip reader. Use a different CompressionLevel.
  77. /// </summary>
  78. None = 0,
  79. /// <summary>
  80. /// Same as None.
  81. /// </summary>
  82. Level0 = 0,
  83. /// <summary>
  84. /// The fastest but least effective compression.
  85. /// </summary>
  86. BestSpeed = 1,
  87. /// <summary>
  88. /// A synonym for BestSpeed.
  89. /// </summary>
  90. Level1 = 1,
  91. /// <summary>
  92. /// A little slower, but better, than level 1.
  93. /// </summary>
  94. Level2 = 2,
  95. /// <summary>
  96. /// A little slower, but better, than level 2.
  97. /// </summary>
  98. Level3 = 3,
  99. /// <summary>
  100. /// A little slower, but better, than level 3.
  101. /// </summary>
  102. Level4 = 4,
  103. /// <summary>
  104. /// A little slower than level 4, but with better compression.
  105. /// </summary>
  106. Level5 = 5,
  107. /// <summary>
  108. /// The default compression level, with a good balance of speed and compression efficiency.
  109. /// </summary>
  110. Default = 6,
  111. /// <summary>
  112. /// A synonym for Default.
  113. /// </summary>
  114. Level6 = 6,
  115. /// <summary>
  116. /// Pretty good compression!
  117. /// </summary>
  118. Level7 = 7,
  119. /// <summary>
  120. /// Better compression than Level7!
  121. /// </summary>
  122. Level8 = 8,
  123. /// <summary>
  124. /// The "best" compression, where best means greatest reduction in size of the input data stream.
  125. /// This is also the slowest compression.
  126. /// </summary>
  127. BestCompression = 9,
  128. /// <summary>
  129. /// A synonym for BestCompression.
  130. /// </summary>
  131. Level9 = 9
  132. }
  133. /// <summary>
  134. /// Describes options for how the compression algorithm is executed. Different strategies
  135. /// work better on different sorts of data. The strategy parameter can affect the compression
  136. /// ratio and the speed of compression but not the correctness of the compresssion.
  137. /// </summary>
  138. public enum CompressionStrategy
  139. {
  140. /// <summary>
  141. /// The default strategy is probably the best for normal data.
  142. /// </summary>
  143. Default = 0,
  144. /// <summary>
  145. /// The <c>Filtered</c> strategy is intended to be used most effectively with data produced by a
  146. /// filter or predictor. By this definition, filtered data consists mostly of small
  147. /// values with a somewhat random distribution. In this case, the compression algorithm
  148. /// is tuned to compress them better. The effect of <c>Filtered</c> is to force more Huffman
  149. /// coding and less string matching; it is a half-step between <c>Default</c> and <c>HuffmanOnly</c>.
  150. /// </summary>
  151. Filtered = 1,
  152. /// <summary>
  153. /// Using <c>HuffmanOnly</c> will force the compressor to do Huffman encoding only, with no
  154. /// string matching.
  155. /// </summary>
  156. HuffmanOnly = 2
  157. }
  158. /// <summary>
  159. /// A general purpose exception class for exceptions in the Zlib library.
  160. /// </summary>
  161. public class ZlibException : Exception
  162. {
  163. /// <summary>
  164. /// The ZlibException class captures exception information generated
  165. /// by the Zlib library.
  166. /// </summary>
  167. public ZlibException()
  168. {
  169. }
  170. /// <summary>
  171. /// This ctor collects a message attached to the exception.
  172. /// </summary>
  173. /// <param name="s"></param>
  174. public ZlibException(String s)
  175. : base(s)
  176. {
  177. }
  178. }
  179. internal class SharedUtils
  180. {
  181. /// <summary>
  182. /// Performs an unsigned bitwise right shift with the specified number
  183. /// </summary>
  184. /// <param name="number">Number to operate on</param>
  185. /// <param name="bits">Ammount of bits to shift</param>
  186. /// <returns>The resulting number from the shift operation</returns>
  187. public static int URShift(int number, int bits)
  188. {
  189. return (int)((uint)number >> bits);
  190. }
  191. #if NOT
  192. /// <summary>
  193. /// Performs an unsigned bitwise right shift with the specified number
  194. /// </summary>
  195. /// <param name="number">Number to operate on</param>
  196. /// <param name="bits">Ammount of bits to shift</param>
  197. /// <returns>The resulting number from the shift operation</returns>
  198. public static long URShift(long number, int bits)
  199. {
  200. return (long) ((UInt64)number >> bits);
  201. }
  202. #endif
  203. /// <summary>
  204. /// Reads a number of characters from the current source TextReader and writes
  205. /// the data to the target array at the specified index.
  206. /// </summary>
  207. ///
  208. /// <param name="sourceTextReader">The source TextReader to read from</param>
  209. /// <param name="target">Contains the array of characteres read from the source TextReader.</param>
  210. /// <param name="start">The starting index of the target array.</param>
  211. /// <param name="count">The maximum number of characters to read from the source TextReader.</param>
  212. ///
  213. /// <returns>
  214. /// The number of characters read. The number will be less than or equal to
  215. /// count depending on the data available in the source TextReader. Returns -1
  216. /// if the end of the stream is reached.
  217. /// </returns>
  218. public static Int32 ReadInput(TextReader sourceTextReader, byte[] target, int start, int count)
  219. {
  220. // Returns 0 bytes if not enough space in target
  221. if (target.Length == 0)
  222. {
  223. return 0;
  224. }
  225. char[] charArray = new char[target.Length];
  226. int bytesRead = sourceTextReader.Read(charArray, start, count);
  227. // Returns -1 if EOF
  228. if (bytesRead == 0)
  229. {
  230. return -1;
  231. }
  232. for (int index = start; index < start + bytesRead; index++)
  233. {
  234. target[index] = (byte)charArray[index];
  235. }
  236. return bytesRead;
  237. }
  238. }
  239. internal static class InternalConstants
  240. {
  241. internal static readonly int MAX_BITS = 15;
  242. internal static readonly int BL_CODES = 19;
  243. internal static readonly int D_CODES = 30;
  244. internal static readonly int LITERALS = 256;
  245. internal static readonly int LENGTH_CODES = 29;
  246. internal static readonly int L_CODES = (LITERALS + 1 + LENGTH_CODES);
  247. // Bit length codes must not exceed MAX_BL_BITS bits
  248. internal static readonly int MAX_BL_BITS = 7;
  249. // repeat previous bit length 3-6 times (2 bits of repeat count)
  250. internal static readonly int REP_3_6 = 16;
  251. // repeat a zero length 3-10 times (3 bits of repeat count)
  252. internal static readonly int REPZ_3_10 = 17;
  253. // repeat a zero length 11-138 times (7 bits of repeat count)
  254. internal static readonly int REPZ_11_138 = 18;
  255. }
  256. internal sealed class StaticTree
  257. {
  258. internal static readonly short[] lengthAndLiteralsTreeCodes =
  259. {
  260. 12, 8, 140, 8, 76, 8, 204, 8, 44, 8, 172,
  261. 8, 108, 8, 236, 8,
  262. 28, 8, 156, 8, 92, 8, 220, 8, 60, 8, 188,
  263. 8, 124, 8, 252, 8,
  264. 2, 8, 130, 8, 66, 8, 194, 8, 34, 8, 162, 8
  265. , 98, 8, 226, 8,
  266. 18, 8, 146, 8, 82, 8, 210, 8, 50, 8, 178,
  267. 8, 114, 8, 242, 8,
  268. 10, 8, 138, 8, 74, 8, 202, 8, 42, 8, 170,
  269. 8, 106, 8, 234, 8,
  270. 26, 8, 154, 8, 90, 8, 218, 8, 58, 8, 186,
  271. 8, 122, 8, 250, 8,
  272. 6, 8, 134, 8, 70, 8, 198, 8, 38, 8, 166, 8
  273. , 102, 8, 230, 8,
  274. 22, 8, 150, 8, 86, 8, 214, 8, 54, 8, 182,
  275. 8, 118, 8, 246, 8,
  276. 14, 8, 142, 8, 78, 8, 206, 8, 46, 8, 174,
  277. 8, 110, 8, 238, 8,
  278. 30, 8, 158, 8, 94, 8, 222, 8, 62, 8, 190,
  279. 8, 126, 8, 254, 8,
  280. 1, 8, 129, 8, 65, 8, 193, 8, 33, 8, 161, 8
  281. , 97, 8, 225, 8,
  282. 17, 8, 145, 8, 81, 8, 209, 8, 49, 8, 177,
  283. 8, 113, 8, 241, 8,
  284. 9, 8, 137, 8, 73, 8, 201, 8, 41, 8, 169, 8
  285. , 105, 8, 233, 8,
  286. 25, 8, 153, 8, 89, 8, 217, 8, 57, 8, 185,
  287. 8, 121, 8, 249, 8,
  288. 5, 8, 133, 8, 69, 8, 197, 8, 37, 8, 165, 8
  289. , 101, 8, 229, 8,
  290. 21, 8, 149, 8, 85, 8, 213, 8, 53, 8, 181,
  291. 8, 117, 8, 245, 8,
  292. 13, 8, 141, 8, 77, 8, 205, 8, 45, 8, 173,
  293. 8, 109, 8, 237, 8,
  294. 29, 8, 157, 8, 93, 8, 221, 8, 61, 8, 189,
  295. 8, 125, 8, 253, 8,
  296. 19, 9, 275, 9, 147, 9, 403, 9, 83, 9, 339,
  297. 9, 211, 9, 467, 9,
  298. 51, 9, 307, 9, 179, 9, 435, 9, 115, 9, 371
  299. , 9, 243, 9, 499, 9,
  300. 11, 9, 267, 9, 139, 9, 395, 9, 75, 9, 331,
  301. 9, 203, 9, 459, 9,
  302. 43, 9, 299, 9, 171, 9, 427, 9, 107, 9, 363
  303. , 9, 235, 9, 491, 9,
  304. 27, 9, 283, 9, 155, 9, 411, 9, 91, 9, 347,
  305. 9, 219, 9, 475, 9,
  306. 59, 9, 315, 9, 187, 9, 443, 9, 123, 9, 379
  307. , 9, 251, 9, 507, 9,
  308. 7, 9, 263, 9, 135, 9, 391, 9, 71, 9, 327,
  309. 9, 199, 9, 455, 9,
  310. 39, 9, 295, 9, 167, 9, 423, 9, 103, 9, 359
  311. , 9, 231, 9, 487, 9,
  312. 23, 9, 279, 9, 151, 9, 407, 9, 87, 9, 343,
  313. 9, 215, 9, 471, 9,
  314. 55, 9, 311, 9, 183, 9, 439, 9, 119, 9, 375
  315. , 9, 247, 9, 503, 9,
  316. 15, 9, 271, 9, 143, 9, 399, 9, 79, 9, 335,
  317. 9, 207, 9, 463, 9,
  318. 47, 9, 303, 9, 175, 9, 431, 9, 111, 9, 367
  319. , 9, 239, 9, 495, 9,
  320. 31, 9, 287, 9, 159, 9, 415, 9, 95, 9, 351,
  321. 9, 223, 9, 479, 9,
  322. 63, 9, 319, 9, 191, 9, 447, 9, 127, 9, 383
  323. , 9, 255, 9, 511, 9,
  324. 0, 7, 64, 7, 32, 7, 96, 7, 16, 7, 80, 7,
  325. 48, 7, 112, 7,
  326. 8, 7, 72, 7, 40, 7, 104, 7, 24, 7, 88, 7,
  327. 56, 7, 120, 7,
  328. 4, 7, 68, 7, 36, 7, 100, 7, 20, 7, 84, 7,
  329. 52, 7, 116, 7,
  330. 3, 8, 131, 8, 67, 8, 195, 8, 35, 8, 163, 8
  331. , 99, 8, 227, 8
  332. };
  333. internal static readonly short[] distTreeCodes =
  334. {
  335. 0, 5, 16, 5, 8, 5, 24, 5, 4, 5, 20, 5, 12, 5, 28, 5,
  336. 2, 5, 18, 5, 10, 5, 26, 5, 6, 5, 22, 5, 14, 5, 30, 5,
  337. 1, 5, 17, 5, 9, 5, 25, 5, 5, 5, 21, 5, 13, 5, 29, 5,
  338. 3, 5, 19, 5, 11, 5, 27, 5, 7, 5, 23, 5
  339. };
  340. // extra bits for each bit length code
  341. internal static readonly int[] extra_blbits = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 3, 7};
  342. internal static readonly StaticTree Literals;
  343. internal static readonly StaticTree Distances;
  344. internal static readonly StaticTree BitLengths;
  345. internal short[] treeCodes; // static tree or null
  346. internal int[] extraBits; // extra bits for each code or null
  347. internal int extraBase; // base index for extra_bits
  348. internal int elems; // max number of elements in the tree
  349. internal int maxLength; // max bit length for the codes
  350. private StaticTree(short[] treeCodes, int[] extraBits, int extraBase, int elems, int maxLength)
  351. {
  352. this.treeCodes = treeCodes;
  353. this.extraBits = extraBits;
  354. this.extraBase = extraBase;
  355. this.elems = elems;
  356. this.maxLength = maxLength;
  357. }
  358. static StaticTree()
  359. {
  360. Literals = new StaticTree(lengthAndLiteralsTreeCodes, DeflateManager.ExtraLengthBits,
  361. InternalConstants.LITERALS + 1, InternalConstants.L_CODES,
  362. InternalConstants.MAX_BITS);
  363. Distances = new StaticTree(distTreeCodes, DeflateManager.ExtraDistanceBits, 0, InternalConstants.D_CODES,
  364. InternalConstants.MAX_BITS);
  365. BitLengths = new StaticTree(null, extra_blbits, 0, InternalConstants.BL_CODES, InternalConstants.MAX_BL_BITS);
  366. }
  367. }
  368. /// <summary>
  369. /// Computes an Adler-32 checksum.
  370. /// </summary>
  371. /// <remarks>
  372. /// The Adler checksum is similar to a CRC checksum, but faster to compute, though less
  373. /// reliable. It is used in producing RFC1950 compressed streams. The Adler checksum
  374. /// is a required part of the "ZLIB" standard. Applications will almost never need to
  375. /// use this class directly.
  376. /// </remarks>
  377. internal sealed class Adler
  378. {
  379. // largest prime smaller than 65536
  380. private static readonly uint BASE = 65521U;
  381. // NMAX is the largest n such that 255n(n+1)/2 + (n+1)(BASE-1) <= 2^32-1
  382. private static readonly int NMAX = 5552;
  383. internal static uint Adler32(uint adler, byte[] buf, int index, int len)
  384. {
  385. if (buf == null)
  386. {
  387. return 1;
  388. }
  389. uint s1 = adler & 0xffffU;
  390. uint s2 = (adler >> 16) & 0xffffU;
  391. while (len > 0)
  392. {
  393. int k = len < NMAX ? len : NMAX;
  394. len -= k;
  395. while (k >= 16)
  396. {
  397. //s1 += (buf[index++] & 0xff); s2 += s1;
  398. s1 += buf[index++];
  399. s2 += s1;
  400. s1 += buf[index++];
  401. s2 += s1;
  402. s1 += buf[index++];
  403. s2 += s1;
  404. s1 += buf[index++];
  405. s2 += s1;
  406. s1 += buf[index++];
  407. s2 += s1;
  408. s1 += buf[index++];
  409. s2 += s1;
  410. s1 += buf[index++];
  411. s2 += s1;
  412. s1 += buf[index++];
  413. s2 += s1;
  414. s1 += buf[index++];
  415. s2 += s1;
  416. s1 += buf[index++];
  417. s2 += s1;
  418. s1 += buf[index++];
  419. s2 += s1;
  420. s1 += buf[index++];
  421. s2 += s1;
  422. s1 += buf[index++];
  423. s2 += s1;
  424. s1 += buf[index++];
  425. s2 += s1;
  426. s1 += buf[index++];
  427. s2 += s1;
  428. s1 += buf[index++];
  429. s2 += s1;
  430. k -= 16;
  431. }
  432. if (k != 0)
  433. {
  434. do
  435. {
  436. s1 += buf[index++];
  437. s2 += s1;
  438. }
  439. while (--k != 0);
  440. }
  441. s1 %= BASE;
  442. s2 %= BASE;
  443. }
  444. return (s2 << 16) | s1;
  445. }
  446. }
  447. }