Return to makecrc.c CVS log

Up to [MW Coherent from dump] / coherent / b / bin / zip

Annotation of coherent/b/bin/zip/makecrc.c, revision 1.1

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

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