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

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.