Return to crc.c CVS log

Up to [PGP] / pgp / contrib / langtool

Annotation of pgp/contrib/langtool/crc.c, revision 1.1.1.1

1.1       root        1: /************************************************************************/
                      2: 
                      3: /* CRC Routines. */
                      4: /*     These CRC functions are derived from code in chapter 19 of the book 
                      5:        "C Programmer's Guide to Serial Communications", by Joe Campbell.
                      6:        Generalized to any CRC width by Philip Zimmermann.
                      7: */
                      8: 
                      9: #define byte unsigned char
                     10: 
                     11: #define CRCBITS 24     /* may be 16, 24, or 32 */
                     12: /* #define crcword unsigned short */   /* if CRCBITS is 16 */
                     13: #define crcword unsigned long          /* if CRCBITS is 24 or 32 */
                     14: /* #define maskcrc(crc) ((crcword)(crc)) */    /* if CRCBITS is 16 or 32 */
                     15: #define maskcrc(crc) ((crc) & 0xffffffL)       /* if CRCBITS is 24 */
                     16: #define CRCHIBIT ((crcword) (1L<<(CRCBITS-1))) /* 0x8000 if CRCBITS is 16 */
                     17: #define CRCSHIFTS (CRCBITS-8)
                     18: 
                     19: /*     Notes on making a good 24-bit CRC--
                     20:        The primitive irreducible polynomial of degree 23 over GF(2),
                     21:        040435651 (octal), comes from Appendix C of "Error Correcting Codes,
                     22:        2nd edition" by Peterson and Weldon, page 490.  This polynomial was
                     23:        chosen for its uniform density of ones and zeros, which has better
                     24:        error detection properties than polynomials with a minimal number of
                     25:        nonzero terms.  Multiplying this primitive degree-23 polynomial by
                     26:        the polynomial x+1 yields the additional property of detecting any
                     27:        odd number of bits in error, which means it adds parity.  This 
                     28:        approach was recommended by Neal Glover.
                     29: 
                     30:        To multiply the polynomial 040435651 by x+1, shift it left 1 bit and
                     31:        bitwise add (xor) the unshifted version back in.  Dropping the unused 
                     32:        upper bit (bit 24) produces a CRC-24 generator bitmask of 041446373 
                     33:        octal, or 0x864cfb hex.  
                     34: 
                     35:        You can detect spurious leading zeros or framing errors in the 
                     36:        message by initializing the CRC accumulator to some agreed-upon 
                     37:        nonzero "random-like" value, but this is a bit nonstandard.  
                     38: */
                     39: 
                     40: #define CCITTCRC 0x1021 /* CCITT's 16-bit CRC generator polynomial */
                     41: #define PRZCRC 0x864cfbL /* PRZ's 24-bit CRC generator polynomial */
                     42: #define CRCINIT 0xB704CEL      /* Init value for CRC accumulator */
                     43: 
                     44: crcword crctable[256];         /* Table for speeding up CRC's */
                     45: 
                     46: /*     crchware simulates CRC hardware circuit.  Generates true CRC
                     47:        directly, without requiring extra NULL bytes to be appended 
                     48:        to the message.
                     49:        Returns new updated CRC accumulator.
                     50: */
                     51: crcword crchware(byte ch, crcword poly, crcword accum)
                     52: {      int i;
                     53:        crcword data;
                     54:        data = ch;
                     55:        data <<= CRCSHIFTS;     /* shift data to line up with MSB of accum */
                     56:        i = 8;          /* counts 8 bits of data */
                     57:        do
                     58:        {       /* if MSB of (data XOR accum) is TRUE, shift and subtract poly */
                     59:                if ((data ^ accum) & CRCHIBIT)
                     60:                        accum = (accum<<1) ^ poly;
                     61:                else
                     62:                        accum <<= 1;
                     63:                data <<= 1;
                     64:        } while (--i);  /* counts 8 bits of data */
                     65:        return (maskcrc(accum));
                     66: }      /* crchware */
                     67: 
                     68: 
                     69: /*     mk_crctbl derives a CRC lookup table from the CRC polynomial.
                     70:        The table is used later by crcupdate function given below.
                     71:        mk_crctbl only needs to be called once at the dawn of time.
                     72: */
                     73: void mk_crctbl(crcword poly)
                     74: {      int i;
                     75:        for (i=0; i<256; i++)
                     76:                crctable[i] = crchware((byte) i, poly, 0);
                     77: }      /* mk_crctbl */
                     78: 
                     79: 
                     80: /*     crcupdate calculates a CRC using the fast table-lookup method.
                     81:        Returns new updated CRC accumulator.
                     82: */
                     83: crcword crcupdate(byte data, register crcword accum)
                     84: {      byte combined_value;
                     85: 
                     86:        /* XOR the MSByte of the accum with the data byte */
                     87:        combined_value = (accum >> CRCSHIFTS) ^ data;
                     88:        accum = (accum << 8) ^ crctable[combined_value];
                     89:        return (maskcrc(accum));
                     90: }      /* crcupdate */
                     91: 
                     92: /* Initialize the CRC table using our codes */
                     93: void init_crc()
                     94: {      mk_crctbl(PRZCRC);
                     95: }
                     96: 

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