home *** CD-ROM | disk | FTP | other *** search
/ Source Code 1992 March / Source_Code_CD-ROM_Walnut_Creek_March_1992.iso / usenet / altsrcs / 1 / 1478 < prev    next >
Internet Message Format  |  1990-12-28  |  7KB
  1. From: dan@Apple.COM (Dan Allen)
  2. Newsgroups: alt.sources
  3. Subject: [sci.crypt] CRC C Code
  4. Message-ID: <1990Jun18.215243.9319@math.lsa.umich.edu>
  5. Date: 18 Jun 90 21:52:43 GMT
  6.  
  7. Archive-name: updcrc/18-Jun-90
  8. Original-posting-by: dan@Apple.COM (Dan Allen)
  9. Original-subject: CRC C Code
  10. Reposted-by: emv@math.lsa.umich.edu (Edward Vielmetti)
  11.  
  12. [Reposted from sci.crypt.
  13. Comments on this service to emv@math.lsa.umich.edu (Edward Vielmetti).]
  14.  
  15. Several people have asked me for the better CRC code that I received due
  16. to my earlier request for code to calculate CRC polynomials.  Here is
  17. one of the better pieces of code that I received...
  18.  
  19. ----------------------------- CUT HERE ----------------------------
  20.  
  21. /* updcrc(3), crc(1) - calculate crc polynomials
  22.  *
  23.  * Calculate, intelligently, the CRC of a dataset incrementally given a
  24.  * buffer full at a time.
  25.  *
  26.  * Usage:
  27.  *      newcrc = updcrc( oldcrc, bufadr, buflen )
  28.  *              unsigned int oldcrc, buflen;
  29.  *              char *bufadr;
  30.  *
  31.  * Compiling with -DTEST creates a program to print the CRC of stdin to stdout.
  32.  * Compile with -DMAKETAB to print values for crctab to stdout.  If you change
  33.  *      the CRC polynomial parameters, be sure to do this and change
  34.  *      crctab's initial value.
  35.  *
  36.  * Notes:
  37.  *  Regards the data stream as an integer whose MSB is the MSB of the first
  38.  *  byte recieved.  This number is 'divided' (using xor instead of subtraction)
  39.  *  by the crc-polynomial P.
  40.  *  XMODEM does things a little differently, essentially treating the LSB of
  41.  * the first data byte as the MSB of the integer. Define SWAPPED to make
  42.  * things behave in this manner.
  43.  *
  44.  * Author:      Mark G. Mendel, 7/86
  45.  *              UUCP: ihnp4!umn-cs!hyper!mark, GEnie: mgm
  46.  */
  47.  
  48. /* The CRC polynomial.
  49.  * These 4 values define the crc-polynomial.
  50.  * If you change them, you must change crctab[]'s initial value to what is
  51.  * printed by initcrctab() [see 'compile with -DMAKETAB' above].
  52.  */
  53.     /* Value used by:                   CITT    XMODEM  ARC     */
  54. #define P        0xA001  /* the poly:   0x1021  0x1021  A001    */
  55. #define INIT_CRC 0L      /* init value: -1      0       0       */
  56. #define SWAPPED          /* bit order:  undef   defined defined */
  57. #define W       16       /* bits in CRC:16      16      16      */
  58.  
  59.     /* data type that holds a W-bit unsigned integer */
  60. #if W <= 16
  61. #  define WTYPE unsigned short
  62. #else
  63. #  define WTYPE   unsigned long
  64. #endif
  65.  
  66.     /* the number of bits per char: don't change it. */
  67. #define B       8
  68.  
  69. static WTYPE crctab[1<<B] = /* as calculated by initcrctab() */ {
  70. 0x0,  0xc0c1,  0xc181,  0x140,  0xc301,  0x3c0,  0x280,  0xc241,
  71. 0xc601,  0x6c0,  0x780,  0xc741,  0x500,  0xc5c1,  0xc481,  0x440,
  72. 0xcc01,  0xcc0,  0xd80,  0xcd41,  0xf00,  0xcfc1,  0xce81,  0xe40,
  73. 0xa00,  0xcac1,  0xcb81,  0xb40,  0xc901,  0x9c0,  0x880,  0xc841,
  74. 0xd801,  0x18c0,  0x1980,  0xd941,  0x1b00,  0xdbc1,  0xda81,  0x1a40,
  75. 0x1e00,  0xdec1,  0xdf81,  0x1f40,  0xdd01,  0x1dc0,  0x1c80,  0xdc41,
  76. 0x1400,  0xd4c1,  0xd581,  0x1540,  0xd701,  0x17c0,  0x1680,  0xd641,
  77. 0xd201,  0x12c0,  0x1380,  0xd341,  0x1100,  0xd1c1,  0xd081,  0x1040,
  78. 0xf001,  0x30c0,  0x3180,  0xf141,  0x3300,  0xf3c1,  0xf281,  0x3240,
  79. 0x3600,  0xf6c1,  0xf781,  0x3740,  0xf501,  0x35c0,  0x3480,  0xf441,
  80. 0x3c00,  0xfcc1,  0xfd81,  0x3d40,  0xff01,  0x3fc0,  0x3e80,  0xfe41,
  81. 0xfa01,  0x3ac0,  0x3b80,  0xfb41,  0x3900,  0xf9c1,  0xf881,  0x3840,
  82. 0x2800,  0xe8c1,  0xe981,  0x2940,  0xeb01,  0x2bc0,  0x2a80,  0xea41,
  83. 0xee01,  0x2ec0,  0x2f80,  0xef41,  0x2d00,  0xedc1,  0xec81,  0x2c40,
  84. 0xe401,  0x24c0,  0x2580,  0xe541,  0x2700,  0xe7c1,  0xe681,  0x2640,
  85. 0x2200,  0xe2c1,  0xe381,  0x2340,  0xe101,  0x21c0,  0x2080,  0xe041,
  86. 0xa001,  0x60c0,  0x6180,  0xa141,  0x6300,  0xa3c1,  0xa281,  0x6240,
  87. 0x6600,  0xa6c1,  0xa781,  0x6740,  0xa501,  0x65c0,  0x6480,  0xa441,
  88. 0x6c00,  0xacc1,  0xad81,  0x6d40,  0xaf01,  0x6fc0,  0x6e80,  0xae41,
  89. 0xaa01,  0x6ac0,  0x6b80,  0xab41,  0x6900,  0xa9c1,  0xa881,  0x6840,
  90. 0x7800,  0xb8c1,  0xb981,  0x7940,  0xbb01,  0x7bc0,  0x7a80,  0xba41,
  91. 0xbe01,  0x7ec0,  0x7f80,  0xbf41,  0x7d00,  0xbdc1,  0xbc81,  0x7c40,
  92. 0xb401,  0x74c0,  0x7580,  0xb541,  0x7700,  0xb7c1,  0xb681,  0x7640,
  93. 0x7200,  0xb2c1,  0xb381,  0x7340,  0xb101,  0x71c0,  0x7080,  0xb041,
  94. 0x5000,  0x90c1,  0x9181,  0x5140,  0x9301,  0x53c0,  0x5280,  0x9241,
  95. 0x9601,  0x56c0,  0x5780,  0x9741,  0x5500,  0x95c1,  0x9481,  0x5440,
  96. 0x9c01,  0x5cc0,  0x5d80,  0x9d41,  0x5f00,  0x9fc1,  0x9e81,  0x5e40,
  97. 0x5a00,  0x9ac1,  0x9b81,  0x5b40,  0x9901,  0x59c0,  0x5880,  0x9841,
  98. 0x8801,  0x48c0,  0x4980,  0x8941,  0x4b00,  0x8bc1,  0x8a81,  0x4a40,
  99. 0x4e00,  0x8ec1,  0x8f81,  0x4f40,  0x8d01,  0x4dc0,  0x4c80,  0x8c41,
  100. 0x4400,  0x84c1,  0x8581,  0x4540,  0x8701,  0x47c0,  0x4680,  0x8641,
  101. 0x8201,  0x42c0,  0x4380,  0x8341,  0x4100,  0x81c1,  0x8081,  0x4040,
  102. } ;
  103.  
  104. WTYPE
  105. updcrc( icrc, icp, icnt )
  106.     WTYPE icrc;
  107.     unsigned char *icp;
  108.     int icnt;
  109. {
  110.     register WTYPE crc = icrc;
  111.     register unsigned char *cp = icp;
  112.     register int cnt = icnt;
  113.  
  114.     while( cnt-- ) {
  115. #ifndef SWAPPED
  116.         crc = (crc<<B) ^ crctab[(crc>>(W-B)) ^ *cp++];
  117. #else
  118.         crc = (crc>>B) ^ crctab[(crc & ((1<<B)-1)) ^ *cp++];
  119. #endif SWAPPED
  120.     }
  121.  
  122.     return( crc );
  123. }
  124.  
  125. #ifdef MAKETAB
  126.  
  127. #include <stdio.h>
  128. main()
  129. {
  130.     initcrctab();
  131. }
  132.  
  133. initcrctab()
  134. {
  135.     register  int b, i;
  136.     WTYPE v;
  137.  
  138.  
  139.     for( b = 0; b <= (1<<B)-1; ++b ) {
  140. #ifndef SWAPPED
  141.         for( v = b<<(W-B), i = B; --i >= 0; )
  142.             v = v & ((WTYPE)1<<(W-1)) ? (v<<1)^P : v<<1;
  143. #else
  144.         for( v = b, i = B; --i >= 0; )
  145.             v = v & 1 ? (v>>1)^P : v>>1;
  146. #endif
  147.         crctab[b] = v;
  148.  
  149.         printf( "0x%lx,", v & ((1L<<W)-1L));
  150.         if( (b&7) == 7 )
  151.             printf("\n" );
  152.         else
  153.             printf("  ");
  154.     }
  155. }
  156. #endif
  157.  
  158. #ifdef TEST
  159.  
  160. #include <stdio.h>
  161. #include <fcntl.h>
  162.  
  163. #define MAXBUF  4096
  164.  
  165. main( ac, av )
  166.     int ac; char **av;
  167. {
  168.     int fd;
  169.     int nr;
  170.     int i;
  171.     char buf[MAXBUF];
  172.     WTYPE crc, crc2;
  173.  
  174.     fd = 0;
  175.     if( ac > 1 )
  176.         if( (fd = open( av[1], O_RDONLY )) < 0 ) {
  177.             perror( av[1] );
  178.             exit( -1 );
  179.         }
  180.     crc = crc2 = INIT_CRC;
  181.  
  182.     while( (nr = read( fd, buf, MAXBUF )) > 0 ) {
  183.         crc = updcrc( crc, buf, nr );
  184.     }
  185.  
  186.     if( nr != 0 )
  187.         perror( "reading" );
  188.     else {
  189.         printf( "%lx\n", crc );
  190.     }
  191.  
  192. #ifdef MAGICCHECK
  193.     /* tack one's complement of crc onto data stream, and
  194.        continue crc calculation.  Should get a constant (magic number)
  195.        dependent only on P, not the data.
  196.      */
  197.     crc2 = crc ^ -1L;
  198.     for( nr = W-B; nr >= 0; nr -= B ) {
  199.         buf[0] = (crc2 >> nr);
  200.         crc = updcrc(crc, buf, 1);
  201.     }
  202.  
  203.     /* crc should now equal magic */
  204.     buf[0] = buf[1] = buf[2] = buf[3] = 0;
  205.     printf( "magic test: %lx =?= %lx\n", crc, updcrc(-1, buf, W/B));
  206. #endif MAGICCHECK
  207. }
  208.  
  209. #endif
  210.