home *** CD-ROM | disk | FTP | other *** search
/ RISC DISC 2 / RISC_DISC_2.iso / pd_share / utilities / cli / pgp2 / contrib / langtool / c / crc < prev    next >
Encoding:
Text File  |  1994-05-06  |  3.4 KB  |  97 lines
  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.  
  97.