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