Search the FAQ Archives

3 - A - B - C - D - E - F - G - H - I - J - K - L - M
N - O - P - Q - R - S - T - U - V - W - X - Y - Z
faqs.org - Internet FAQ Archives

comp.compression Frequently Asked Questions (part 1/3)
Section - [51] I need a CRC algorithm

( Part1 - Part2 - Part3 - Single Page )
[ Usenet FAQs | Web FAQs | Documents | RFC Index | Business Photos and Profiles ]


Top Document: comp.compression Frequently Asked Questions (part 1/3)
Previous Document: [50] What is this 'tar' compression program?
Next Document: [52] What about those people who continue to ask frequently asked questions in spite of the frequently asked questions document?
See reader questions & answers on this topic! - Help others by sharing your knowledge

As its name implies (Cyclic Redundancy Check) a crc adds redundancy whereas
the topic of this group is to remove it. Yet this question comes up often in
comp.compression.

The file ftp://ftp.rocksoft.com/clients/rocksoft/papers/ is a pretty
comprehensive description of the whole CRC concept, including a C program.

See also:
- Schwaderer W.D., "CRC Calculation", April 85 PC Tech Journal, pp.118-133.
- "Calculating CRCs by Bits and Bytes", BYTE Magazine, September 1986
- Ramabadran T.V., Gaitonde S.S., "A tutorial on CRC computations", IEEE
  Micro, Aug 1988.
- the source of all archivers, such as the file makecrc.c in the Info-ZIP
  sources (see extension .zip in item 2)

For the related topic of Reed-Solomon encoding, see the Error Correcting Codes
Home Page http://hideki.iis.u-tokyo.ac.jp/~robert/codes.html


The following C code (by Rob Warnock <rpw3@sgi.com>) does CRC-32 in
BigEndian/BigEndian byte/bit order.  That is, the data is sent most
significant byte first, and each of the bits within a byte is sent most
significant bit first, as in FDDI. You will need to twiddle with it to do
Ethernet CRC, i.e., BigEndian/LittleEndian byte/bit order. [Left as an
exercise for the reader.]

The CRCs this code generates agree with the vendor-supplied Verilog models
of several of the popular FDDI "MAC" chips.

u_long crc32_table[256];
/* Initialized first time "crc32()" is called. If you prefer, you can
 * statically initialize it at compile time. [Another exercise.]
 */

u_long crc32(u_char *buf, int len)
{
        u_char *p;
        u_long  crc;

        if (!crc32_table[1])    /* if not already done, */
                init_crc32();   /* build table */
        crc = 0xffffffff;       /* preload shift register, per CRC-32 spec */
        for (p = buf; len > 0; ++p, --len)
                crc = (crc << 8) ^ crc32_table[(crc >> 24) ^ *p];
        return ~crc;            /* transmit complement, per CRC-32 spec */
}

/*
 * Build auxiliary table for parallel byte-at-a-time CRC-32.
 */
#define CRC32_POLY 0x04c11db7     /* AUTODIN II, Ethernet, & FDDI */

init_crc32()
{
        int i, j;
        u_long c;

        for (i = 0; i < 256; ++i) {
                for (c = i << 24, j = 8; j > 0; --j)
                        c = c & 0x80000000 ? (c << 1) ^ CRC32_POLY : (c << 1);
                crc32_table[i] = c;
        }
}

User Contributions:

Comment about this article, ask questions, or add new information about this topic:

CAPTCHA