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