Return to makecrc.c CVS log

Up to [MW Coherent from dump] / coherent / g / usr / bin / gzip

Annotation of coherent/g/usr/bin/gzip/makecrc.c, revision 1.1

1.1     ! root        1: /* Not copyrighted 1990 Mark Adler */
        !             2: 
        !             3: #ifndef lint
        !             4: static char rcsid[] = "$Id: makecrc.c,v 0.5 1992/12/21 18:56:56 jloup Exp $";
        !             5: #endif
        !             6: 
        !             7: #include <stdio.h>
        !             8: 
        !             9: main()
        !            10: /*
        !            11:   Generate a table for a byte-wise 32-bit CRC calculation on the polynomial:
        !            12:   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.
        !            13: 
        !            14:   Polynomials over GF(2) are represented in binary, one bit per coefficient,
        !            15:   with the lowest powers in the most significant bit.  Then adding polynomials
        !            16:   is just exclusive-or, and multiplying a polynomial by x is a right shift by
        !            17:   one.  If we call the above polynomial p, and represent a byte as the
        !            18:   polynomial q, also with the lowest power in the most significant bit (so the
        !            19:   byte 0xb1 is the polynomial x^7+x^3+x+1), then the CRC is (q*x^32) mod p,
        !            20:   where a mod b means the remainder after dividing a by b.
        !            21: 
        !            22:   This calculation is done using the shift-register method of multiplying and
        !            23:   taking the remainder.  The register is initialized to zero, and for each
        !            24:   incoming bit, x^32 is added mod p to the register if the bit is a one (where
        !            25:   x^32 mod p is p+x^32 = x^26+...+1), and the register is multiplied mod p by
        !            26:   x (which is shifting right by one and adding x^32 mod p if the bit shifted
        !            27:   out is a one).  We start with the highest power (least significant bit) of
        !            28:   q and repeat for all eight bits of q.
        !            29: 
        !            30:   The table is simply the CRC of all possible eight bit values.  This is all
        !            31:   the information needed to generate CRC's on data a byte at a time for all
        !            32:   combinations of CRC register values and incoming bytes.  The table is
        !            33:   written to stdout as 256 long hexadecimal values in C language format.
        !            34: */
        !            35: {
        !            36:   unsigned long c;      /* crc shift register */
        !            37:   unsigned long e;      /* polynomial exclusive-or pattern */
        !            38:   int i;                /* counter for all possible eight bit values */
        !            39:   int k;                /* byte being shifted into crc apparatus */
        !            40: 
        !            41:   /* terms of polynomial defining this crc (except x^32): */
        !            42:   static int p[] = {0,1,2,4,5,7,8,10,11,12,16,22,23,26};
        !            43: 
        !            44:   /* Make exclusive-or pattern from polynomial */
        !            45:   e = 0;
        !            46:   for (i = 0; i < sizeof(p)/sizeof(int); i++)
        !            47:     e |= 1L << (31 - p[i]);
        !            48: 
        !            49:   /* Compute and print table of CRC's, five per line */
        !            50:   printf("  0x00000000L");
        !            51:   for (i = 1; i < 256; i++)
        !            52:   {
        !            53:     c = 0;
        !            54:     for (k = i | 256; k != 1; k >>= 1)
        !            55:     {
        !            56:       c = c & 1 ? (c >> 1) ^ e : c >> 1;
        !            57:       if (k & 1)
        !            58:         c ^= e;
        !            59:     }
        !            60:     printf(i % 5 ? ", 0x%08lxL" : ",\n  0x%08lxL", c);
        !            61:   }
        !            62:   putchar('\n');
        !            63:   return 0;
        !            64: }

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.