crc16ccitt.c

   1 /*
   2  * derived from crctester.c
   3  * original header:
   4  * ----------------------------------------------------------------------------
   5  * CRC tester v1.3 written on 4th of February 2003 by Sven Reifegerste (zorc/reflex)
   6  * This is the complete compilable C program, consisting only of this .c file.
   7  * No guarantee for any mistakes.
   8  *
   9  * changes to CRC tester v1.2:
  10  *
  11  * - remove unneccessary (!(polynom&1)) test for invalid polynoms
  12  *   (now also XMODEM parameters 0x8408 work in c-code as they should)
  13  *
  14  * changes to CRC tester v1.1:
  15  *
  16  * - include an crc&0crcmask after converting non-direct to direct initial
  17  *   value to avoid overflow
  18  *
  19  * changes to CRC tester v1.0:
  20  *
  21  * - most int's were replaced by unsigned long's to allow longer input strings
  22  *   and avoid overflows and unnecessary type-casting's
  23  * ----------------------------------------------------------------------------
  24  */
  25
  26 static const int order = 16;
  27 static const unsigned long polynom = 0x1021;
  28 static const int direct = 1;
  29 static const unsigned long crcinit = 0xffff;
  30 static const unsigned long crcxor = 0x0000;
  31 static const int refin = 1;
  32 static const int refout = 0;
  33
  34 // 'order' [1..32] is the CRC polynom order, counted without the leading '1' bit
  35 // 'polynom' is the CRC polynom without leading '1' bit
  36 // 'direct' [0,1] specifies the kind of algorithm: 1=direct, no augmented zero bits
  37 // 'crcinit' is the initial CRC value belonging to that algorithm
  38 // 'crcxor' is the final XOR value
  39 // 'refin' [0,1] specifies if a data byte is reflected before processing (UART) or not
  40 // 'refout' [0,1] specifies if the CRC will be reflected before XOR
  41
  42
  43 // internal global values:
  44
  45 static unsigned long crcmask;
  46 static unsigned long crchighbit;
  47 static unsigned long crcinit_direct;
  48 static unsigned long crcinit_nondirect;
  49 static unsigned long crctab[256];
  50
  51
  52 // subroutines
  53
  54 static unsigned long reflect (unsigned long crc, int bitnum) {
  55
  56         // reflects the lower 'bitnum' bits of 'crc'
  57
  58         unsigned long i, j=1, crcout=0;
  59
  60         for (i=(unsigned long)1<<(bitnum-1); i; i>>=1) {
  61                 if (crc & i) crcout|=j;
  62                 j<<= 1;
  63         }
  64         return (crcout);
  65 }
  66
  67
  68
  69 static void generate_crc_table(void)
  70 {
  71         // make CRC lookup table used by table algorithms
  72
  73         int i, j;
  74         unsigned long bit, crc;
  75
  76         for (i=0; i<256; i++) {
  77
  78                 crc=(unsigned long)i;
  79                 if (refin) crc=reflect(crc, 8);
  80                 crc<<= order-8;
  81
  82                 for (j=0; j<8; j++) {
  83
  84                         bit = crc & crchighbit;
  85                         crc<<= 1;
  86                         if (bit) crc^= polynom;
  87                 }
  88
  89                 if (refin) crc = reflect(crc, order);
  90                 crc&= crcmask;
  91                 crctab[i]= crc;
  92         }
  93 }
  94
  95
  96 static unsigned long crctablefast (unsigned char* p, unsigned long len)
  97 {
  98         // fast lookup table algorithm without augmented zero bytes, e.g. used in pkzip.
  99         // only usable with polynom orders of 8, 16, 24 or 32.
 100
 101         unsigned long crc = crcinit_direct;
 102
 103         if (refin) crc = reflect(crc, order);
 104
 105         if (!refin) while (len--) crc = (crc << 8) ^ crctab[ ((crc >> (order-8)) & 0xff) ^ *p++];
 106         else while (len--) crc = (crc >> 8) ^ crctab[ (crc & 0xff) ^ *p++];
 107
 108         if (refout^refin) crc = reflect(crc, order);
 109         crc^= crcxor;
 110         crc&= crcmask;
 111
 112         return(crc);
 113 }
 114
 115 static unsigned long crctable (unsigned char* p, unsigned long len)
 116 {
 117         // normal lookup table algorithm with augmented zero bytes.
 118         // only usable with polynom orders of 8, 16, 24 or 32.
 119
 120         unsigned long crc = crcinit_nondirect;
 121
 122         if (refin)
 123                 crc = reflect(crc, order);
 124
 125         if (!refin)
 126                 while (len--)
 127                         crc = ((crc << 8) | *p++) ^ crctab[ (crc >> (order-8))  & 0xff];
 128         else
 129                 while (len--)
 130                         crc = ((crc >> 8) | (*p++ << (order-8))) ^ crctab[ crc & 0xff];
 131
 132         if (!refin)
 133                 while (++len < order/8)
 134                         crc = (crc << 8) ^ crctab[ (crc >> (order-8))  & 0xff];
 135         else
 136                 while (++len < order/8)
 137                         crc = (crc >> 8) ^ crctab[crc & 0xff];
 138
 139         if (refout^refin)
 140                 crc = reflect(crc, order);
 141         crc^= crcxor;
 142         crc&= crcmask;
 143
 144         return(crc);
 145 }
 146
 147
 148
 149 unsigned long crcbitbybit(unsigned char* p, unsigned long len) {
 150
 151         // bit by bit algorithm with augmented zero bytes.
 152         // does not use lookup table, suited for polynom orders between 1...32.
 153
 154         unsigned long i, j, c, bit;
 155         unsigned long crc = crcinit_nondirect;
 156
 157         for (i=0; i<len; i++) {
 158
 159                 c = (unsigned long)*p++;
 160                 if (refin)
 161                         c = reflect(c, 8);
 162
 163                 for (j=0x80; j; j>>=1) {
 164                         bit = crc & crchighbit;
 165                         crc<<= 1;
 166                         if (c & j)
 167                                 crc|= 1;
 168                         if (bit)
 169                                 crc^= polynom;
 170                 }
 171         }
 172
 173         for (i=0; i<order; i++) {
 174                 bit = crc & crchighbit;
 175                 crc <<= 1;
 176                 if (bit)
 177                         crc^= polynom;
 178         }
 179
 180         if (refout)
 181                 crc=reflect(crc, order);
 182         crc ^= crcxor;
 183         crc &= crcmask;
 184
 185         return(crc);
 186 }
 187
 188
 189
 190 unsigned long crcbitbybitfast(unsigned char* p, unsigned long len) {
 191
 192         // fast bit by bit algorithm without augmented zero bytes.
 193         // does not use lookup table, suited for polynom orders between 1...32.
 194
 195         unsigned long i, j, c, bit;
 196         unsigned long crc = crcinit_direct;
 197
 198         for (i=0; i<len; i++) {
 199                 c = (unsigned long)*p++;
 200                 if (refin)
 201                         c = reflect(c, 8);
 202
 203                 for (j=0x80; j; j>>=1) {
 204                         bit = crc & crchighbit;
 205                         crc <<= 1;
 206                         if (c & j)
 207                                 bit^= crchighbit;
 208                         if (bit)
 209                                 crc^= polynom;
 210                 }
 211         }
 212
 213         if (refout)
 214                 crc=reflect(crc, order);
 215         crc^= crcxor;
 216         crc&= crcmask;
 217
 218         return(crc);
 219 }
 220
 221 void crc16ccitt_init(void)
 222 {
 223         int i;
 224         unsigned long bit, crc;
 225
 226         crcmask = ((((unsigned long)1<<(order-1))-1)<<1)|1;
 227         crchighbit = (unsigned long)1<<(order-1);
 228
 229         generate_crc_table();
 230
 231         if (!direct) {
 232                 crcinit_nondirect = crcinit;
 233                 crc = crcinit;
 234                 for (i=0; i<order; i++) {
 235                         bit = crc & crchighbit;
 236                         crc <<= 1;
 237                         if (bit)
 238                                 crc^= polynom;
 239                 }
 240                 crc &= crcmask;
 241                 crcinit_direct = crc;
 242         } else {
 243                 crcinit_direct = crcinit;
 244                 crc = crcinit;
 245                 for (i=0; i<order; i++) {
 246                         bit = crc & 1;
 247                         if (bit)
 248                                 crc^= polynom;
 249                         crc >>= 1;
 250                         if (bit)
 251                                 crc|= crchighbit;
 252                 }
 253                 crcinit_nondirect = crc;
 254         }
 255 }
 256
 257 unsigned short crc16ccitt (unsigned char *data, int len)
 258 {
 259         // call CRC algorithms using the CRC parameters above and print result to the console
 260         return crcbitbybitfast((unsigned char *)data, len);
 261 }
 262
 263 #if 0
 264 int main() {
 265
 266         // test program for checking four different CRC computing types that are:
 267         // crcbit(), crcbitfast(), crctable() and crctablefast(), see above.
 268         // parameters are at the top of this program.
 269         // Result will be printed on the console.
 270
 271         int i;
 272         unsigned long bit, crc;
 273
 274
 275         // at first, compute constant bit masks for whole CRC and CRC high bit
 276
 277         crcmask = ((((unsigned long)1<<(order-1))-1)<<1)|1;
 278         crchighbit = (unsigned long)1<<(order-1);
 279
 280
 281         // check parameters
 282
 283         if (order < 1 || order > 32) {
 284                 printf("ERROR, invalid order, it must be between 1..32.\n");
 285                 return(0);
 286         }
 287
 288         if (polynom != (polynom & crcmask)) {
 289                 printf("ERROR, invalid polynom.\n");
 290                 return(0);
 291         }
 292
 293         if (crcinit != (crcinit & crcmask)) {
 294                 printf("ERROR, invalid crcinit.\n");
 295                 return(0);
 296         }
 297
 298         if (crcxor != (crcxor & crcmask)) {
 299                 printf("ERROR, invalid crcxor.\n");
 300                 return(0);
 301         }
 302
 303
 304         // generate lookup table
 305
 306         generate_crc_table();
 307
 308
 309         // compute missing initial CRC value
 310
 311         if (!direct) {
 312
 313                 crcinit_nondirect = crcinit;
 314                 crc = crcinit;
 315                 for (i=0; i<order; i++) {
 316
 317                         bit = crc & crchighbit;
 318                         crc<<= 1;
 319                         if (bit) crc^= polynom;
 320                 }
 321                 crc&= crcmask;
 322                 crcinit_direct = crc;
 323         }
 324
 325         else {
 326
 327                 crcinit_direct = crcinit;
 328                 crc = crcinit;
 329                 for (i=0; i<order; i++) {
 330
 331                         bit = crc & 1;
 332                         if (bit) crc^= polynom;
 333                         crc >>= 1;
 334                         if (bit) crc|= crchighbit;
 335                 }
 336                 crcinit_nondirect = crc;
 337         }
 338
 339
 340         // call CRC algorithms using the CRC parameters above and print result to the console
 341
 342         printf("\n");
 343         printf("CRC tester v1.1 written on 13/01/2003 by Sven Reifegerste (zorc/reflex)\n");
 344         printf("-----------------------------------------------------------------------\n");
 345         printf("\n");
 346         printf("Parameters:\n");
 347         printf("\n");
 348         printf(" polynom             :  0x%x\n", polynom);
 349         printf(" order               :  %d\n", order);
 350         printf(" crcinit             :  0x%x direct, 0x%x nondirect\n", crcinit_direct, crcinit_nondirect);
 351         printf(" crcxor              :  0x%x\n", crcxor);
 352         printf(" refin               :  %d\n", refin);
 353         printf(" refout              :  %d\n", refout);
 354         printf("\n");
 355         printf(" data string         :  '%s' (%d bytes)\n", string, strlen(string));
 356         printf("\n");
 357         printf("Results:\n");
 358         printf("\n");
 359
 360         printf(" crc bit by bit      :  0x%x\n", crcbitbybit((unsigned char *)string, strlen(string)));
 361         printf(" crc bit by bit fast :  0x%x\n", crcbitbybitfast((unsigned char *)string, strlen(string)));
 362         if (!(order&7)) printf(" crc table           :  0x%x\n", crctable((unsigned char *)string, strlen(string)));
 363         if (!(order&7)) printf(" crc table fast      :  0x%x\n", crctablefast((unsigned char *)string, strlen(string)));
 364
 365         return(0);
 366 }
 367 #endif