crc32.h

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

/*
	Copyright 2006 - 2008, All Rights Reserved.

	CRC32算法实现

	作者	- 张鲁夺(zhangluduo)
	MSN		- [e-mail]
	QQ群	- 34064264

	为所有爱我的人和我爱的人努力!
*/


#ifndef _CRC32_H
#define _CRC32_H

class CRC32
{
public:

	CRC32();
	virtual ~CRC32();

private:

	unsigned long m_Table[256];
	unsigned long Reflect(unsigned long ref, char ch);

public:

	void CRCInit	(unsigned long &Result);
	void CRCUpdate	(unsigned char* buffer, unsigned long size, unsigned long &Result);
	void CRCFinal	(unsigned long &Result);
};

#endif

/** for test
	unsigned long CRCResult;
	m_CRC32.CRCInit(CRCResult);
	m_CRC32.CRCUpdate((unsigned char *)"hello", strlen("hello"), CRCResult);
	m_CRC32.CRCFinal(CRCResult);

	CString strResult;
	strResult.Format("The CRC-32 Result is %.8X", CRCResult);
	AfxMessageBox(strResult);
*/





//	FileName : RFC3385.txt
//
//	Network Working Group                                       D. Sheinwald
//	Request for Comments: 3385                                     J. Satran
//	Category: Informational                                              IBM
//																   P. Thaler
//																  V. Cavanna
//																	 Agilent
//															  September 2002
//
//
//		   Internet Protocol Small Computer System Interface (iSCSI)
//			 Cyclic Redundancy Check (CRC)/Checksum Considerations
//
//	Status of this Memo
//
//	   This memo provides information for the Internet community.  It does
//	   not specify an Internet standard of any kind.  Distribution of this
//	   memo is unlimited.
//
//	Copyright Notice
//
//	   Copyright (C) The Internet Society (2002).  All Rights Reserved.
//
//	Abstract
//
//	   In this memo, we attempt to give some estimates for the probability
//	   of undetected errors to facilitate the selection of an error
//	   detection code for the Internet Protocol Small Computer System
//	   Interface (iSCSI).
//
//	   We will also attempt to compare Cyclic Redundancy Checks (CRCs) with
//	   other checksum forms (e.g., Fletcher, Adler, weighted checksums), as
//	   permitted by available data.
//
//	1. Introduction
//
//	   Cyclic Redundancy Check (CRC) codes [Peterson] are shortened cyclic
//	   codes used for error detection.  A number of CRC codes have been
//	   adopted in standards: ATM, IEC, IEEE, CCITT, IBM-SDLC, and more
//	   [Baicheva].  The most important expectation from this kind of code is
//	   a very low probability for undetected errors.  The probability of
//	   undetected errors in such codes has been, and still is, subject to
//	   extensive studies that have included both analytical models and
//	   simulations.  Those codes have been used extensively in
//	   communications and magnetic recording as they demonstrate good "burst
//	   error" detection capabilities, but are also good at detecting several
//	   independent bit errors.  Hardware implementations are very simple and
//	   well known; their simplicity has made them popular with hardware
//
//
//
//
//	Sheinwald, et. al.           Informational                      [Page 1]
//	
//	RFC 3385                iSCSI CRC Considerations          September 2002
//
//
//	   developers for many years.  However, algorithms and software for
//	   effective implementations of CRC are now also widely available
//	   [Williams].
//
//	   The probability of undetected errors depends on the polynomial
//	   selected to generate the code, the error distribution (error model),
//	   and the data length.
//
//	2. Error Models and Goals
//
//	   We will analyze the code behavior under two conditions:
//
//		  - noisy channel - burst errors with an average length of n bits
//		  - low noise channel - independent single bit errors
//
//	   Burst errors are the prevalent natural phenomenon on communication
//	   lines and recording media.  The numbers quoted for them revolve
//	   around the BER (bit error rate).  However, those numbers are
//	   frequently nothing more than a reflection of the Burst Error Rate
//	   multiplied by the average burst length.  In field engineering tests,
//	   three numbers are usually quoted together -- BER, error-free-seconds
//	   and severely-error-seconds; this illustrates our point.
//
//	   Even beyond communication and recording media, the effects of errors
//	   will be bursty.  An example of this is a memory error that will
//	   affect more than a single bit and the total effect will not be very
//	   different from the communication error, or software errors that occur
//	   while manipulating packets will have a burst effect.  Software errors
//	   also result in burst errors.  In addition, serial internal
//	   interconnects will make this type of error the most common within
//	   machines as well.
//
//	   We also analyze the effects of single independent bit errors, since
//	   these may be caused by certain defects.
//
//	   On burst, we assume an average burst error duration of bd, which at a
//	   given transmission rate s, will result in an average burst of a =
//	   bd*s bits.  (E.g., an average burst duration of 3 ns at 1Gbs gives an
//	   average burst of 3 bits.)
//
//	   For the burst error rate, we will take 10^-10.  The numbers quoted
//	   for BER on wired communication channels are between 10^-10 to 10^-12
//	   and we consider the BER as burst-error-rate*average-burst-length.
//	   Nevertheless, please keep in mind that if the channel includes
//	   wireless links, the error rates may be substantially higher.
//
//	   For independent single bit errors, we assume a 10^-11 error rate.
//
//
//
//
//	Sheinwald, et. al.           Informational                      [Page 2]
//	
//	RFC 3385                iSCSI CRC Considerations          September 2002
//
//
//	   Because the error detection mechanisms will have to transport large
//	   amounts of data (petabytes=10^16 bits) without errors, we will target
//	   very low probabilities for undetected errors for all block lengths
//	   (at 10Gb/s that much data can be sent in less than 2 weeks on a
//	   single link).
//
//	   Alternatively, as iSCSI has to perform efficiently, we will require
//	   that the error detection capability of a selected protection
//	   mechanism be very good, at least up to block lengths of 8k bytes
//	   (64kbits).
//
//	   The error detection capability should keep the probability of
//	   undetected errors at values that would be "next-to-impossible".  We
//	   recognize, however, that such attributes are hard to quantify and we
//	   resorted to physics.  The value 10^23 is the Avogadro number while
//	   10^45 is the number of atoms in the known Universe (or it was many
//	   years ago when we read about it) and those are the bounds of
//	   incertitude we could live with.  (10^-23 at worst and 10^-45 if we
//	   can afford it.)  For 8k blocks, the per/bit equivalent would be
//	   (10^-28 to 10^-50).
//
//	3. Background and Literature Survey
//
//	   Each codeword of a binary (n,k) CRC code C consists of n = k+r bits.
//	   The block of r parity bits is computed from the block of k
//	   information bits.  The code has a degree r generator polynomial g(x).
//
//	   The code is linear in the sense that the bitwise addition of any two
//	   codewords yields a codeword.
//
//	   For the minimal m such that g(x) divides (x^m)-1, either n=m, and the
//	   code C comprises the set D of all the multiplications of g(x) modulo
//	   (x^m)-1, or n<m, and C is obtained from D by shortening each word in
//	   the latter in m-n specific positions.  (This also reduces the number
//	   of words since all zero words are then discarded and duplicates are
//	   not maintained.)
//
//	   Error detection at the receiving end is made by computing the parity
//	   bits from the received information block, and comparing them with the
//	   received parity bits.
//
//	   An undetected error occurs when the received word c' is a codeword,
//	   but is different from the c that is transmitted.
//
//	   This is only possible when the error pattern e=c'-c is a codeword by
//	   itself (because of the linearity of the code).  The performance of a
//	   CRC code is measured by the probability Pud of undetected channel
//	   errors.
//
//
//
//	Sheinwald, et. al.           Informational                      [Page 3]
//	
//	RFC 3385                iSCSI CRC Considerations          September 2002
//
//
//	   Let Ai denote the number of codewords of weight i, (i.e., with i 1-
//	   bits).  For a binary symmetric channel (BSC), with sporadic,
//	   independent bit error ratio of probability 0<=epsilon<=0.5, the
//	   probability of undetected errors for the code C is thus given by:
//
//	Pud(C,epsilon) = Sigma[for i=d to n] (Ai*(epsilon^i)*(1-epsilon)^(n-i))
//
//	   where d is the distance of the code:  the minimal weight difference
//	   between two codewords in C which, by the linearity of the code, is
//	   also the minimal weight of any codeword in the code.  Pud can also be
//	   expressed by the weight distribution of the dual code:  the set of
//	   words each of which is orthogonal (bitwise AND yields an even number
//	   of 1-bits) to every word of C.  The fact that Pud can be computed
//	   using the dual code is extremely important; while the number of
//	   codewords in the code is 2^k, the number of codewords in the dual
//	   code is 2^r.  k is in the orders of thousands, and r in the order of
//	   16 or 24 or 32.  If we use Bi to denote the number of codewords in
//	   the dual code which are of weight i, then ([LinCostello]):
//
//	Pud (C,epsilon) = 2^-r Sigma [for i=0 to n] Bi*(1-2*epsilon)^i -
//	(1-epsilon)^n
//
//	   Wolf [Wolf94o] introduced an efficient algorithm for enumerating all
//	   the codewords of a code and finding their weight distribution.
//
//	   Wolf [Wolf82] found that, counter to what was assumed, (1) there
//	   exist codes for which Pud(C,epsilon)>Pud(C,0.5) for some epsilon
//	   not=0.5 and (2) Pud is not always increasing for 0<=epsilon<=0.5.
//	   The value of what was assumed to be the worst Pud is Pud(C,0.5)=(2^-
//	   r) - (2^-n).  This stems from the fact that with epsilon=0.5, all 2^n
//	   received words are equally likely and out of them 2^(n-r)-1 will be
//	   accepted as codewords of no errors, although they are different from
//	   the codeword transmitted.  Previously Pud had been assumed to equal
//	   [2^(n-r)-1]/(2^n-1) or the ratio of the number of non-zero multiples
//	   of the polynomial of degree less than n (each such multiple is
//	   undetected) and the number of possible error polynomials.  With
//	   either formula Pud approaches 1/2^r as n approaches infinity, but
//	   Wolf's formula is more accurate.
//
//	   Wolf [Wolf94j] investigated the CCITT code of r=16 parity bits.  This
//	   code is a member of the family of (shortened codes of) BCH codes of
//	   length 2^(r-1) -1 (r=16 in the CCITT 16-bit case) generated by a
//	   polynomial of the form g(x) =(x+1)p(x) with p(x) being a primitive
//	   polynomial of degree r-1 (=15 in this case).  These codes have a BCH
//	   design distance of 4.  That is, the minimal distance between any two
//	   codewords in the code is at least 4 bits (which is earned by the fact
//
//
//
//
//
//	Sheinwald, et. al.           Informational                      [Page 4]
//	
//	RFC 3385                iSCSI CRC Considerations          September 2002
//
//
//	   that the sequence of powers of alpha, the root of p(x), which are
//	   roots of g(x), includes three consecutive powers -- alpha^0, alpha^1,
//	   alpha^2).  Hence, every 3 single bit errors are detectable.
//
//	   Wolf found that different shortened versions of a given code, of the
//	   same codeword length, perform the same (independent of which specific
//	   indexes are omitted from the original code).  He also found that for
//	   the unshortened codes, all primitive polynomials yield codes of the
//	   same performance.  But for the shortened versions, the choice of the
//	   primitive polynomial does make a difference.  Wolf [Wolf94j] found a
//	   primitive polynomial which (when multiplied by x+1) yields a
//	   generating polynomial that outperforms the CCITT one by an order of
//	   magnitude.  For 32-bit redundancy bits, he found an example of two
//	   polynomials that differ in their probability of undetected burst of
//	   length 33 by 4 orders of magnitude.
//
//	   It so happens, that for some shortened codes, the minimum distance,
//	   or the distribution of the weights, is better than for others derived
//	   from different unshortened codes.
//
//	   Baicheva, et. al. [Baicheva] made a comprehensive comparison of
//	   different generating polynomials of degree 16 of the form g(x) =
//	   (x+1)p(x), and of other forms.  They computed their Pud for code
//	   lengths up to 1024 bits.  They measured their "goodness"  -- if
//	   Pud(C,epsilon)  <= Pud(C,0.5) and being "well-behaved" -- if
//	   Pud(C,epsilon) increases with epsilon in the range (0,0.5).  The
//	   paper gives a comprehensive table that lists which of the polynomials
//	   is good and which is well-behaved for different length ranges.
//
//	   For a single burst error, Wolf [Wolf94J] suggested the model of (b:p)
//	   burst -- the errors only occur within a span of b bits, and within
//	   that span, the errors occur randomly, with a bit error probability 0
//	   <= p <= 1.
//
//	   For p=0.5, which used to be considered the worst case, it is well
//	   known [Wolf94J] that the probability of undetected one burst error of
//	   length b <= r is 0, of length b=r+1 is 2^-(r-1), and of b > r+1, is
//	   2^-r, independently of the choice of the primitive polynomial.
//
//	   With Wolf's definition, where p can be different from 0.5, indeed it
//	   was found that for a given b there are values of p, different from
//	   0.5 which maximize the probability of undetected (b:p) burst error.
//
//
//
//
//
//
//
//
//
//	Sheinwald, et. al.           Informational                      [Page 5]
//	
//	RFC 3385                iSCSI CRC Considerations          September 2002
//
//
//	   Wolf proved that for a given code, for all b in the range r < b < n,