crc32.h

CRC32算法, 可以对字符串或文件进行CRC32计算, 带进度条.内含VC++6.0源码

//	   the conditional probability of undetected error for the (n, n-r)
//	   code, given that a (b:p) burst occurred, is equal to the probability
//	   of undetected errors for the same code (the same generating
//	   polynomial), shortened to block length b, when this shortened code is
//	   used with a binary symmetric channel with channel (sporadic,
//	   independent) bit error probability p.
//
//	   For the IEEE-802.3 used CRC32, Fujiwara et al. [Fujiwara89] measured
//	   the weights of all words of all shortened versions of the IEEE 802.3
//	   code of 32 check bits.  This code is generated by a primitive
//	   polynomial of degree 32:
//
//	   g(x) = x^32 + x^26 + x^23 + x^22 + x^16 + x^12 + x^11 + x^10 + x^8 +
//	   x^7 + x^5 + x^4 + x^2 + x + 1 and hence the designed distance of it
//	   is only 3.  This distance holds for codes as long as 2^32-1.
//	   However, the frame format of the MAC (Media Access Control) of the
//	   data link layer in IEEE 802.3, as well as that of the data link layer
//	   for the Ethernet (1980) forbid lengths exceeding 12,144 bits.  Thus,
//	   only such bounded lengths are investigated in [Fujiwara89].  For
//	   shortened versions, the minimum distance was found to be 4 for
//	   lengths 4096 to 12,144; 5 for lengths 512 to 2048; and even 15 for
//	   lengths 33 through 42.  A chart of results of calculations of Pud is
//	   presented in [Fujiwara89] from which we can see that for codes of
//	   length 12,144 and BSC of epsilon = 10^-5 - 10^-4,
//	   Pud(12,144,epsilon)= 10^-14 - 10^-13 and for epsilon = 10^-4 - 10^-3,
//	   Pud(512,epsilon) = 10^-15, Pud(1024,epsilon) = 10^-14,
//	   Pud(2048,epsilon) = 10^-13, Pud(4096,epsilon) = 10^-12 - 10^-11, and
//	   Pud(8192,epsilon) = 10^-10 which is rather close to 2^-32.
//
//	   Castagnoli, et. al. [Castagnoli93] extended Fujiwara's technique for
//	   efficiently calculating the minimum distance through the weight
//	   distribution of the dual code and explored a large number of CRC
//	   codes with 24 and 32 redundancy bit.  They explored several codes
//	   built as a multiplication of several lower degree irreducible
//	   polynomials.
//
//	   In the popular class of (x+1)*deg31-irreducible-polynomial they
//	   explored 47000 polynomials (not all the possible ones).  The best
//	   they found has d=6 up to block lengths of 5275 and d=4 up to 2^31-1
//	   (bits).
//
//	   The investigation was done in 1993 with a special purpose processor.
//
//	   By comparison, the IEEE-802 code has d=4 up to at least 64,000 bits
//	   (Fujikura stopped looking at 12,144) and d=3 up to 2^32-1 bits.
//
//
//
//
//
//	Sheinwald, et. al.           Informational                      [Page 6]
//	
//	RFC 3385                iSCSI CRC Considerations          September 2002
//
//
//	   CRC32/4 (we will refer to it as CRC32C for the remainder of this
//	   memo) is 11EDC6F41;  IEEE-802 CRC is 104C11DB7, denoting the
//	   coefficients as a bit vector.
//
//	   [Stone98] evaluated the performance of CRC (the AAL5 CRC that is the
//	   same as IEEE802) and the TCP and Fletcher checksums on large amounts
//	   of data.  The results of this experiment indicate a serious weakness
//	   of the checksums on real-data that stems from the fact that checksums
//	   do not spread the "hot spots" in input data.  However, the results
//	   show that Fletcher behaves by a factor of 2 better than the regular
//	   TCP checksum.
//
//	4. Probability of Undetected Errors - Burst Error
//
//	4.1 CRC32C (Derivations from [Wolf94j])
//
//	   Wolf [Wolf94j] found a 32-bit polynomial of the form g(x) = (1+x)p(x)
//	   for which the conditional probability of undetected error, given that
//	   a burst of length 33 occurred, is at most (i.e., maximized over all
//	   possible channel bit error probabilities within the burst) 4 * 10^-
//	   10.
//
//	   We will now figure the probability of undetected error, given that a
//	   burst of length 34 occurred, using the result derived in this paper,
//	   namely that for a given code, for all b in the range 32 < b < n, the
//	   conditional probability of undetected error for the (n, n-32) code,
//	   given that a (b:p) burst occurred, is equal to the probability of
//	   undetected errors for the same code (the same generating polynomial),
//	   shortened to block length b, when this shortened code is used with a
//	   binary symmetric channel with channel (sporadic, independent) bit
//	   error probability p.
//
//	   The approximation formula for Pud of sporadic errors, if the weights
//	   Ai are distributed binomially, is:
//
//	   Pud(C, epsilon) =~= Sigma[for i=d to n] ((n choose i) / 2^r )*(1-
//	   epsilon)^(n-i) * epsilon^i .
//
//	   Assuming a very small epsilon, this expression is dominated by i=d.
//	   From [Fujiwara89] we know that for 32-bit CRC, for such small n,
//	   d=15.  Thus, when n grows from 33 to 34, we find that the
//	   approximation of Pud grows by (34 choose 15) / (33 choose 15) =
//	   34/19; when n grows further to 35, Pud grows by another 35/20.
//
//	   Taking, from Wolf [Wolf94j], the most generous conditional
//	   probability, computed with the bit error probability p* that
//	   maximizes Pub(p|b), we derive: Pud(p*|33) = 4 x 10^{-10}, yielding
//	   Pud(p*|34) = 7.15 x 10^{-10} and Pud(p*|35) = 1.25 x 10^{-9}.
//
//
//
//	Sheinwald, et. al.           Informational                      [Page 7]
//	
//	RFC 3385                iSCSI CRC Considerations          September 2002
//
//
//	   For the density function of the burst length, we assume the Rayleigh
//	   density function (the discretization thereof to integers), which is
//	   the density of the absolute values of complex numbers of Gauss
//	   distribution:
//
//		  f(x) = x / a^2  exp {-x^2 / 2a^2 }     , x>0 .
//
//	   This density function has a peak at the parameter a and it decreases
//	   smoothly as x increases.
//
//	   We take three consecutive bits as the most common burst event once an
//	   error does occur, and thus a=3.
//
//	   Now, the probability that a burst of length b occurs in a specific
//	   position is the burst error rate, which we estimate as 10^{-10},
//	   times f(b).  Calculating for b=33 we find f(33) = 1.94 x 10^{-26}.
//	   Together, we found that the probability that a burst of length 33
//	   occurred, starting at a specific position, is 1.94 x 10^{-36}.
//
//	   Multiplying this by the generous upper bound on the probability that
//	   this burst error is not detected, Pud(p*|33), we get that the
//	   probability that a burst occurred at a specific position, and is not
//	   detected, is 7.79 x 10 ^{-46}.
//
//	   Going again along this path of calculations, this time for b=34 we
//	   find that f(34) = 4.85*10^{-28}.  Multiplying by 10^{-10} and by
//	   Pud(p*|34) = 7.15*10^{-10} we find that the probability that a burst
//	   of length 34 occurred at a specific position, and is not detected, is
//	   3.46*10^{-47}.
//
//	   Last, computing for b=35, we get 1*10^{-29} * 10^{-10} * 1.25*10^{-9}
//	   = 1.25*10^{-48}.
//
//	   It looks like the total can be approximated at 10^-45 which is within
//	   the bounds of what we are looking for.
//
//	   When we multiply this by the length of the code (because thus far we
//	   calculated for a specific position) we have 10^-45 * 6.5*10^4 =
//	   6.5*10^-41 as an upper bound on the probability of undetected burst
//	   error for a code of length 8K Bytes.
//
//	   We can also apply this overestimation for IEEE 802.3.
//
//	   Comment: 2^{-32} = 2.33*10^{-10}.
//
//
//
//
//
//
//
//	Sheinwald, et. al.           Informational                      [Page 8]
//	
//	RFC 3385                iSCSI CRC Considerations          September 2002
//
//
//	5. Probability of Undetected Errors - Independent Errors
//
//	5.1 CRC (Derivations from [Castagnoli93])
//
//	   It is reported in [Castagnoli93] that for BER = epsilon=10^-6, Pud
//	   for a single bit error, for a code of length 8KB, for both cases,
//	   IEEE-802.3 and CRC32C is 10^{-20}.  They also report that CRC32C has
//	   distance 4, and IEEE either 3 or 4 for this code length.  From this,
//	   and the minimum distance of the code of this length, we conclude that
//	   with our estimation of epsilon, namely 10^{-11}, we should multiply
//	   the reported result by {10^{-5}}^4 = 10^{-20} for CRC32C, and either
//	   10^{-15} or 10^{-20} for IEEE802.3.
//
//	5.2 Checksums
//
//	   For independent bit errors, Pud of CRC is approximately 12,000 better
//	   than Fletcher, and 22,000 better than Adler.  For burst errors, by
//	   the simple examples that exist for three consecutive values that can
//	   produce an undetected burst, we take the factor to be at least the
//	   same.
//
//	   If in three consecutive bytes, the error values are x, -2x, x then
//	   the error is undetected.  Even for this error pattern alone, the
//	   conditional probability of undetected error, assuming a uniform
//	   distribution of data, is 2^-16 = 1.5 * 10^-5.  The probability that a
//	   burst of length 3 bytes occurs, is f(24) = 3*10^-14.  Together:
//	   4.5*10^-19.  Multiplying this by the length of the code, we get close
//	   to 4.5*10^-16, way worse than the vicinity of 10^-40.
//
//	   The numbers in the table in Section 7 below reflect a more "tolerant"
//	   difference (10*4).
//
//	6. Incremental CRC Updates
//
//	   In some protocols the packet header changes frequently.  If the CRC
//	   includes the changing part, the CRC will have to be recomputed.  This
//	   raises two issues:
//
//		  - the complete computation is expensive
//		  - the packet is not protected against unwanted changes
//			between the last check and the recomputation
//
//	   Fortunately, changes in the header do not imply a need for completed
//	   CRC computation.  The reason is the linearity of the CRC function.
//	   Namely, with I1 and I2 denoting two equal-length blocks of
//	   information bits, CRC(I) denoting the CRC check bits calculated for
//	   I, and + denoting bitwise modulo-2 addition, we have CRC(I1+I2) =
//	   CRC(I1)+CRC(I2).
//
//
//
//	Sheinwald, et. al.           Informational                      [Page 9]
//	
//	RFC 3385                iSCSI CRC Considerations          September 2002
//
//
//	   Hence, for an IP packet, made of a header h followed by data d
//	   followed by CRC bits c = CRC(h d), arriving at a node, which updates
//	   header h to become h', the implied update of c is an addition of
//	   CRC(h'-h 0), where 0 is an all 0 block of the length of the data
//	   block d, and addition and subtraction are bitwise modulo 2.
//
//	   We know that a predetermined permutation of bits does not change
//	   distance and weight statistics of the codewords.  It follows that
//	   such a transformation does not change the probability of undetected
//	   errors.
//
//	   We can then conceive the packet as if it was built from data d
//	   followed by header h, compute the CRC accordingly, c=CRC(d h), and
//	   update at the node with an addition of CRC(0 h'-h)=CRC(h'-h), but on
//	   transmission, send the header part before the data and the CRC bits.
//	   This will allow a faster computation of the CRC, while still letting
//	   the header part lead (no change to the protocol).
//
//	   Error detection, i.e., computing the CRC bits by the data and header
//	   parts that arrive, and comparing them with the CRC part that arrives
//	   together with them, can be done at the final, end-target node only,
//	   and the detected errors will include unwanted changes introduced by
//	   the intermediate nodes.
//
//	   The analysis of the undetected error probability remains valid
//	   according to the following rationale:
//
//	   The packet started its way as a codeword.  On its way, several
//	   codewords were added to it (any information followed by the
//	   corresponding CRC is a codeword).  Let e denote the totality of
//	   errors added to the packet, on its long, multi-hop journey.  Because
//	   the code is linear (i.e., the sum of two codewords is also a
//	   codeword) the packet arriving to the end-target node is some codeword
//	   + e, and hence, as in our preceding analysis, e is undetected if and
//	   only if it is a codeword by itself.  This fact is the basis of our
//	   above analysis, and hence that analysis applies here too.  (See a
//	   detailed discussion at [braun01].)
//
//	7. Complexity of Hardware Implementation
//
//	   Comparing the cost of various CRC polynomials, we used a tool
//	   available at http://www.easics.com/webtools/crctool to implement CRC
//	   generators/checkers for various CRC polynomials.  The program gives
//	   either Verilog or VHDL code after specifying a polynomial, as well as
//	   the number of data bits, k, to be handled in one clock cycle.  For a
//	   serial implementation, k would be one.
//
//
//
//
//
//	Sheinwald, et. al.           Informational                     [Page 10]
//	
//	RFC 3385                iSCSI CRC Considerations          September 2002
//
//
//	   The cost for either one generator or checker is shown in the
//	   following table.
//
//	   The number of 2-input XOR gates, for an un-optimized implementation,
//	   required for various values of k:
//
//	   +----------------------------------------------+
//	   | Polynomial  | k=32     | k=64     | k=128    |
//	   +----------------------------------------------+
//	   | CCITT-CRC32 | 488      | 740      | 1430     |
//	   +----------------------------------------------+
//	   | IEEE-802    | 872      | 1390     | 2518     |
//	   +----------------------------------------------+
//	   | CRC32Q(Wolf)| 944      | 1444     | 2534     |
//	   +----------------------------------------------+
//	   | CRC32C      | 1036     | 1470     | 2490     |
//	   +----------------------------------------------+
//
//	   After optimizing (sharing terms) and in terms of Cells (4 cells per 2
//	   input AND, 7 cells per 2 input XOR, 3 cells per inverter) the cost
//	   for two candidate polynomials is shown in the following table.
//
//	   +-----------------------------------+
//	   | Polynomial  | k=32     | k=64     |
//	   +-----------------------------------+
//	   | CCITT-CRC32 | 1855     | 3572     |
//	   +-----------------------------------+
//	   | CRC32C      | 4784     | 7111     |
//	   +-----------------------------------+
//
//	   For 32-bit datapath, CCITT-CRC32 requires 40% of the number of cells
//	   required by the CRC32C.  For a 64-bit datapath, CCITT-CRC32 requires
//	   50% of the number of cells.
//
//	   The total size of one of our smaller chips is roughly 1 million
//	   cells.  The fraction represented by the CRC circuit is less than 1%.
//
//	8. Implementation of CRC32C
//
//	8.1 A Serial Implementation in Hardware
//
//	   A serial implementation that processes one data bit at a time and
//	   performs simultaneous multiplication of the data polynomial by x^32
//	   and division by the CRC32C polynomial is described in the following
//	   Verilog [ieee1364] code.
//
//
//
//
//
//
//	Sheinwald, et. al.           Informational                     [Page 11]
//	
//	RFC 3385                iSCSI CRC Considerations          September 2002
//
//
//	   /////////////////////////////////////////////////////////////////////