CRC32.cs 9.8 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293
  1. // Crc32.cs
  2. // ------------------------------------------------------------------
  3. //
  4. // Copyright (c) 2006-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: <2010-January-16 13:16:27>
  19. //
  20. // ------------------------------------------------------------------
  21. //
  22. // Implements the CRC algorithm, which is used in zip files. The zip format calls for
  23. // the zipfile to contain a CRC for the unencrypted byte stream of each file.
  24. //
  25. // It is based on example source code published at
  26. // http://www.vbaccelerator.com/home/net/code/libraries/CRC32/Crc32_zip_CRC32_CRC32_cs.asp
  27. //
  28. // This implementation adds a tweak of that code for use within zip creation. While
  29. // computing the CRC we also compress the byte stream, in the same read loop. This
  30. // avoids the need to read through the uncompressed stream twice - once to compute CRC
  31. // and another time to compress.
  32. //
  33. // ------------------------------------------------------------------
  34. using System;
  35. using System.IO;
  36. namespace SharpCompress.Compressors.Deflate
  37. {
  38. /// <summary>
  39. /// Calculates a 32bit Cyclic Redundancy Checksum (CRC) using the same polynomial
  40. /// used by Zip. This type is used internally by DotNetZip; it is generally not used
  41. /// directly by applications wishing to create, read, or manipulate zip archive
  42. /// files.
  43. /// </summary>
  44. internal class CRC32
  45. {
  46. private const int BUFFER_SIZE = 8192;
  47. private static readonly UInt32[] crc32Table;
  48. private UInt32 runningCrc32Result = 0xFFFFFFFF;
  49. static CRC32()
  50. {
  51. unchecked
  52. {
  53. // PKZip specifies CRC32 with a polynomial of 0xEDB88320;
  54. // This is also the CRC-32 polynomial used bby Ethernet, FDDI,
  55. // bzip2, gzip, and others.
  56. // Often the polynomial is shown reversed as 0x04C11DB7.
  57. // For more details, see http://en.wikipedia.org/wiki/Cyclic_redundancy_check
  58. UInt32 dwPolynomial = 0xEDB88320;
  59. UInt32 i, j;
  60. crc32Table = new UInt32[256];
  61. UInt32 dwCrc;
  62. for (i = 0; i < 256; i++)
  63. {
  64. dwCrc = i;
  65. for (j = 8; j > 0; j--)
  66. {
  67. if ((dwCrc & 1) == 1)
  68. {
  69. dwCrc = (dwCrc >> 1) ^ dwPolynomial;
  70. }
  71. else
  72. {
  73. dwCrc >>= 1;
  74. }
  75. }
  76. crc32Table[i] = dwCrc;
  77. }
  78. }
  79. }
  80. /// <summary>
  81. /// indicates the total number of bytes read on the CRC stream.
  82. /// This is used when writing the ZipDirEntry when compressing files.
  83. /// </summary>
  84. public Int64 TotalBytesRead { get; private set; }
  85. /// <summary>
  86. /// Indicates the current CRC for all blocks slurped in.
  87. /// </summary>
  88. public Int32 Crc32Result => unchecked((Int32)(~runningCrc32Result));
  89. /// <summary>
  90. /// Returns the CRC32 for the specified stream.
  91. /// </summary>
  92. /// <param name="input">The stream over which to calculate the CRC32</param>
  93. /// <returns>the CRC32 calculation</returns>
  94. public UInt32 GetCrc32(Stream input)
  95. {
  96. return GetCrc32AndCopy(input, null);
  97. }
  98. /// <summary>
  99. /// Returns the CRC32 for the specified stream, and writes the input into the
  100. /// output stream.
  101. /// </summary>
  102. /// <param name="input">The stream over which to calculate the CRC32</param>
  103. /// <param name="output">The stream into which to deflate the input</param>
  104. /// <returns>the CRC32 calculation</returns>
  105. public UInt32 GetCrc32AndCopy(Stream input, Stream output)
  106. {
  107. if (input == null)
  108. {
  109. throw new ZlibException("The input stream must not be null.");
  110. }
  111. unchecked
  112. {
  113. //UInt32 crc32Result;
  114. //crc32Result = 0xFFFFFFFF;
  115. var buffer = new byte[BUFFER_SIZE];
  116. int readSize = BUFFER_SIZE;
  117. TotalBytesRead = 0;
  118. int count = input.Read(buffer, 0, readSize);
  119. if (output != null)
  120. {
  121. output.Write(buffer, 0, count);
  122. }
  123. TotalBytesRead += count;
  124. while (count > 0)
  125. {
  126. SlurpBlock(buffer, 0, count);
  127. count = input.Read(buffer, 0, readSize);
  128. if (output != null)
  129. {
  130. output.Write(buffer, 0, count);
  131. }
  132. TotalBytesRead += count;
  133. }
  134. return ~runningCrc32Result;
  135. }
  136. }
  137. /// <summary>
  138. /// Get the CRC32 for the given (word,byte) combo. This is a computation
  139. /// defined by PKzip.
  140. /// </summary>
  141. /// <param name="W">The word to start with.</param>
  142. /// <param name="B">The byte to combine it with.</param>
  143. /// <returns>The CRC-ized result.</returns>
  144. public Int32 ComputeCrc32(Int32 W, byte B)
  145. {
  146. return _InternalComputeCrc32((UInt32)W, B);
  147. }
  148. internal Int32 _InternalComputeCrc32(UInt32 W, byte B)
  149. {
  150. return (Int32)(crc32Table[(W ^ B) & 0xFF] ^ (W >> 8));
  151. }
  152. /// <summary>
  153. /// Update the value for the running CRC32 using the given block of bytes.
  154. /// This is useful when using the CRC32() class in a Stream.
  155. /// </summary>
  156. /// <param name="block">block of bytes to slurp</param>
  157. /// <param name="offset">starting point in the block</param>
  158. /// <param name="count">how many bytes within the block to slurp</param>
  159. public void SlurpBlock(byte[] block, int offset, int count)
  160. {
  161. if (block == null)
  162. {
  163. throw new ZlibException("The data buffer must not be null.");
  164. }
  165. for (int i = 0; i < count; i++)
  166. {
  167. int x = offset + i;
  168. runningCrc32Result = ((runningCrc32Result) >> 8) ^
  169. crc32Table[(block[x]) ^ ((runningCrc32Result) & 0x000000FF)];
  170. }
  171. TotalBytesRead += count;
  172. }
  173. // pre-initialize the crc table for speed of lookup.
  174. private uint gf2_matrix_times(uint[] matrix, uint vec)
  175. {
  176. uint sum = 0;
  177. int i = 0;
  178. while (vec != 0)
  179. {
  180. if ((vec & 0x01) == 0x01)
  181. {
  182. sum ^= matrix[i];
  183. }
  184. vec >>= 1;
  185. i++;
  186. }
  187. return sum;
  188. }
  189. private void gf2_matrix_square(uint[] square, uint[] mat)
  190. {
  191. for (int i = 0; i < 32; i++)
  192. {
  193. square[i] = gf2_matrix_times(mat, mat[i]);
  194. }
  195. }
  196. /// <summary>
  197. /// Combines the given CRC32 value with the current running total.
  198. /// </summary>
  199. /// <remarks>
  200. /// This is useful when using a divide-and-conquer approach to calculating a CRC.
  201. /// Multiple threads can each calculate a CRC32 on a segment of the data, and then
  202. /// combine the individual CRC32 values at the end.
  203. /// </remarks>
  204. /// <param name="crc">the crc value to be combined with this one</param>
  205. /// <param name="length">the length of data the CRC value was calculated on</param>
  206. public void Combine(int crc, int length)
  207. {
  208. var even = new uint[32]; // even-power-of-two zeros operator
  209. var odd = new uint[32]; // odd-power-of-two zeros operator
  210. if (length == 0)
  211. {
  212. return;
  213. }
  214. uint crc1 = ~runningCrc32Result;
  215. var crc2 = (uint)crc;
  216. // put operator for one zero bit in odd
  217. odd[0] = 0xEDB88320; // the CRC-32 polynomial
  218. uint row = 1;
  219. for (int i = 1; i < 32; i++)
  220. {
  221. odd[i] = row;
  222. row <<= 1;
  223. }
  224. // put operator for two zero bits in even
  225. gf2_matrix_square(even, odd);
  226. // put operator for four zero bits in odd
  227. gf2_matrix_square(odd, even);
  228. var len2 = (uint)length;
  229. // apply len2 zeros to crc1 (first square will put the operator for one
  230. // zero byte, eight zero bits, in even)
  231. do
  232. {
  233. // apply zeros operator for this bit of len2
  234. gf2_matrix_square(even, odd);
  235. if ((len2 & 1) == 1)
  236. {
  237. crc1 = gf2_matrix_times(even, crc1);
  238. }
  239. len2 >>= 1;
  240. if (len2 == 0)
  241. {
  242. break;
  243. }
  244. // another iteration of the loop with odd and even swapped
  245. gf2_matrix_square(odd, even);
  246. if ((len2 & 1) == 1)
  247. {
  248. crc1 = gf2_matrix_times(odd, crc1);
  249. }
  250. len2 >>= 1;
  251. }
  252. while (len2 != 0);
  253. crc1 ^= crc2;
  254. runningCrc32Result = ~crc1;
  255. //return (int) crc1;
  256. }
  257. // private member vars
  258. }
  259. }