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

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.