crc16ccitt.c

   1 /*
   2  * derived from crctester.c 2011 by Nils Faerber <nils.faerber@kernelconcepts.de>
   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)
 104                 crc = reflect(crc, order);
 105
 106         if (!refin)
 107                 while (len--)
 108                         crc = (crc << 8) ^ crctab[ ((crc >> (order-8)) & 0xff) ^ *p++];
 109         else
 110                 while (len--)
 111                         crc = (crc >> 8) ^ crctab[ (crc & 0xff) ^ *p++];
 112
 113         if (refout^refin)
 114                 crc = reflect(crc, order);
 115
 116         crc^= crcxor;
 117         crc&= crcmask;
 118
 119         return(crc);
 120 }
 121
 122 static unsigned long crctable (unsigned char* p, unsigned long len)
 123 {
 124         /* normal lookup table algorithm with augmented zero bytes. */
 125         /* only usable with polynom orders of 8, 16, 24 or 32. */
 126
 127         unsigned long crc = crcinit_nondirect;
 128
 129         if (refin)
 130                 crc = reflect(crc, order);
 131
 132         if (!refin)
 133                 while (len--)
 134                         crc = ((crc << 8) | *p++) ^ crctab[ (crc >> (order-8))  & 0xff];
 135         else
 136                 while (len--)
 137                         crc = ((crc >> 8) | (*p++ << (order-8))) ^ crctab[ crc & 0xff];
 138
 139         if (!refin)
 140                 while (++len < order/8)
 141                         crc = (crc << 8) ^ crctab[ (crc >> (order-8))  & 0xff];
 142         else
 143                 while (++len < order/8)
 144                         crc = (crc >> 8) ^ crctab[crc & 0xff];
 145
 146         if (refout^refin)
 147                 crc = reflect(crc, order);
 148
 149         crc^= crcxor;
 150         crc&= crcmask;
 151
 152         return(crc);
 153 }
 154
 155
 156
 157 unsigned long crcbitbybit(unsigned char* p, unsigned long len) {
 158
 159         /* bit by bit algorithm with augmented zero bytes. */
 160         /* does not use lookup table, suited for polynom orders between 1...32. */
 161
 162         unsigned long i, j, c, bit;
 163         unsigned long crc = crcinit_nondirect;
 164
 165         for (i=0; i<len; i++) {
 166
 167                 c = (unsigned long)*p++;
 168                 if (refin)
 169                         c = reflect(c, 8);
 170
 171                 for (j=0x80; j; j>>=1) {
 172                         bit = crc & crchighbit;
 173                         crc<<= 1;
 174                         if (c & j)
 175                                 crc|= 1;
 176                         if (bit)
 177                                 crc^= polynom;
 178                 }
 179         }
 180
 181         for (i=0; i<order; i++) {
 182                 bit = crc & crchighbit;
 183                 crc <<= 1;
 184                 if (bit)
 185                         crc^= polynom;
 186         }
 187
 188         if (refout)
 189                 crc=reflect(crc, order);
 190
 191         crc ^= crcxor;
 192         crc &= crcmask;
 193
 194         return(crc);
 195 }
 196
 197
 198
 199 unsigned long crcbitbybitfast(unsigned char* p, unsigned long len) {
 200
 201         // fast bit by bit algorithm without augmented zero bytes.
 202         // does not use lookup table, suited for polynom orders between 1...32.
 203
 204         unsigned long i, j, c, bit;
 205         unsigned long crc = crcinit_direct;
 206
 207         for (i=0; i<len; i++) {
 208                 c = (unsigned long)*p++;
 209                 if (refin)
 210                         c = reflect(c, 8);
 211
 212                 for (j=0x80; j; j>>=1) {
 213                         bit = crc & crchighbit;
 214                         crc <<= 1;
 215                         if (c & j)
 216                                 bit^= crchighbit;
 217                         if (bit)
 218                                 crc^= polynom;
 219                 }
 220         }
 221
 222         if (refout)
 223                 crc=reflect(crc, order);
 224         crc^= crcxor;
 225         crc&= crcmask;
 226
 227         return(crc);
 228 }
 229
 230 void crc16ccitt_init(void)
 231 {
 232         int i;
 233         unsigned long bit, crc;
 234
 235         crcmask = ((((unsigned long)1<<(order-1))-1)<<1)|1;
 236         crchighbit = (unsigned long)1<<(order-1);
 237
 238         generate_crc_table();
 239
 240         if (!direct) {
 241                 crcinit_nondirect = crcinit;
 242                 crc = crcinit;
 243                 for (i=0; i<order; i++) {
 244                         bit = crc & crchighbit;
 245                         crc <<= 1;
 246                         if (bit)
 247                                 crc^= polynom;
 248                 }
 249                 crc &= crcmask;
 250                 crcinit_direct = crc;
 251         } else {
 252                 crcinit_direct = crcinit;
 253                 crc = crcinit;
 254                 for (i=0; i<order; i++) {
 255                         bit = crc & 1;
 256                         if (bit)
 257                                 crc^= polynom;
 258                         crc >>= 1;
 259                         if (bit)
 260                                 crc|= crchighbit;
 261                 }
 262                 crcinit_nondirect = crc;
 263         }
 264 }
 265
 266 unsigned short crc16ccitt (unsigned char *data, int len)
 267 {
 268         // call CRC algorithms using the CRC parameters above and print result to the console
 269         return crcbitbybitfast((unsigned char *)data, len);
 270 }
 271
 272 #if 0
 273 int main() {
 274
 275         // test program for checking four different CRC computing types that are:
 276         // crcbit(), crcbitfast(), crctable() and crctablefast(), see above.
 277         // parameters are at the top of this program.
 278         // Result will be printed on the console.
 279
 280         int i;
 281         unsigned long bit, crc;
 282
 283
 284         // at first, compute constant bit masks for whole CRC and CRC high bit
 285
 286         crcmask = ((((unsigned long)1<<(order-1))-1)<<1)|1;
 287         crchighbit = (unsigned long)1<<(order-1);
 288
 289
 290         // check parameters
 291
 292         if (order < 1 || order > 32) {
 293                 printf("ERROR, invalid order, it must be between 1..32.\n");
 294                 return(0);
 295         }
 296
 297         if (polynom != (polynom & crcmask)) {
 298                 printf("ERROR, invalid polynom.\n");
 299                 return(0);
 300         }
 301
 302         if (crcinit != (crcinit & crcmask)) {
 303                 printf("ERROR, invalid crcinit.\n");
 304                 return(0);
 305         }
 306
 307         if (crcxor != (crcxor & crcmask)) {
 308                 printf("ERROR, invalid crcxor.\n");
 309                 return(0);
 310         }
 311
 312
 313         // generate lookup table
 314
 315         generate_crc_table();
 316
 317
 318         // compute missing initial CRC value
 319
 320         if (!direct) {
 321
 322                 crcinit_nondirect = crcinit;
 323                 crc = crcinit;
 324                 for (i=0; i<order; i++) {
 325
 326                         bit = crc & crchighbit;
 327                         crc<<= 1;
 328                         if (bit) crc^= polynom;
 329                 }
 330                 crc&= crcmask;
 331                 crcinit_direct = crc;
 332         }
 333
 334         else {
 335
 336                 crcinit_direct = crcinit;
 337                 crc = crcinit;
 338                 for (i=0; i<order; i++) {
 339
 340                         bit = crc & 1;
 341                         if (bit) crc^= polynom;
 342                         crc >>= 1;
 343                         if (bit) crc|= crchighbit;
 344                 }
 345                 crcinit_nondirect = crc;
 346         }
 347
 348
 349         // call CRC algorithms using the CRC parameters above and print result to the console
 350
 351         printf("\n");
 352         printf("CRC tester v1.1 written on 13/01/2003 by Sven Reifegerste (zorc/reflex)\n");
 353         printf("-----------------------------------------------------------------------\n");
 354         printf("\n");
 355         printf("Parameters:\n");
 356         printf("\n");
 357         printf(" polynom             :  0x%x\n", polynom);
 358         printf(" order               :  %d\n", order);
 359         printf(" crcinit             :  0x%x direct, 0x%x nondirect\n", crcinit_direct, crcinit_nondirect);
 360         printf(" crcxor              :  0x%x\n", crcxor);
 361         printf(" refin               :  %d\n", refin);
 362         printf(" refout              :  %d\n", refout);
 363         printf("\n");
 364         printf(" data string         :  '%s' (%d bytes)\n", string, strlen(string));
 365         printf("\n");
 366         printf("Results:\n");
 367         printf("\n");
 368
 369         printf(" crc bit by bit      :  0x%x\n", crcbitbybit((unsigned char *)string, strlen(string)));
 370         printf(" crc bit by bit fast :  0x%x\n", crcbitbybitfast((unsigned char *)string, strlen(string)));
 371         if (!(order&7)) printf(" crc table           :  0x%x\n", crctable((unsigned char *)string, strlen(string)));
 372         if (!(order&7)) printf(" crc table fast      :  0x%x\n", crctablefast((unsigned char *)string, strlen(string)));
 373
 374         return(0);
 375 }
 376 #endif
 377