common/crc16.c

   1 //-----------------------------------------------------------------------------
   2 // This code is licensed to you under the terms of the GNU GPL, version 2 or,
   3 // at your option, any later version. See the LICENSE.txt file for the text of
   4 // the license.
   5 //-----------------------------------------------------------------------------
   6 // CRC16
   7 //-----------------------------------------------------------------------------
   8 #include "crc16.h"
   9
  10 #include <string.h>
  11 #include "commonutil.h"
  12
  13 static uint16_t crc_table[256];
  14 static bool crc_table_init = false;
  15 static CrcType_t current_crc_type = CRC_NONE;
  16
  17 void init_table(CrcType_t crctype) {
  18
  19     // same crc algo, and initialised already
  20     if (crctype == current_crc_type && crc_table_init)
  21         return;
  22
  23     // not the same crc algo. reset table.
  24     if (crctype != current_crc_type)
  25         reset_table();
  26
  27     current_crc_type = crctype;
  28
  29     switch (crctype) {
  30         case CRC_14443_A:
  31         case CRC_14443_B:
  32         case CRC_15693:
  33         case CRC_ICLASS:
  34         case CRC_CRYPTORF:
  35             generate_table(CRC16_POLY_CCITT, true);
  36             break;
  37         case CRC_FELICA:
  38         case CRC_XMODEM:
  39             generate_table(CRC16_POLY_CCITT, false);
  40             break;
  41         case CRC_LEGIC:
  42             generate_table(CRC16_POLY_LEGIC, true);
  43             break;
  44         case CRC_CCITT:
  45             generate_table(CRC16_POLY_CCITT, false);
  46             break;
  47         case CRC_KERMIT:
  48             generate_table(CRC16_POLY_CCITT, true);
  49             break;
  50         case CRC_11784:
  51             generate_table(CRC16_POLY_CCITT, false);
  52             break;
  53         case CRC_NONE:
  54             crc_table_init = false;
  55             current_crc_type = CRC_NONE;
  56             break;
  57     }
  58 }
  59
  60 void generate_table(uint16_t polynomial, bool refin) {
  61
  62     for (uint16_t i = 0; i < 256; i++) {
  63         uint16_t c, crc = 0;
  64         if (refin)
  65             c = reflect8(i) << 8;
  66         else
  67             c = i << 8;
  68
  69         for (uint16_t j = 0; j < 8; j++) {
  70
  71             if ((crc ^ c) & 0x8000)
  72                 crc = (crc << 1) ^ polynomial;
  73             else
  74                 crc =   crc << 1;
  75
  76             c = c << 1;
  77         }
  78         if (refin)
  79             crc = reflect16(crc);
  80
  81         crc_table[i] = crc;
  82     }
  83     crc_table_init = true;
  84 }
  85
  86 void reset_table(void) {
  87     memset(crc_table, 0, sizeof(crc_table));
  88     crc_table_init = false;
  89     current_crc_type = CRC_NONE;
  90 }
  91
  92 // table lookup LUT solution
  93 uint16_t crc16_fast(uint8_t const *d, size_t n, uint16_t initval, bool refin, bool refout) {
  94
  95     // fast lookup table algorithm without augmented zero bytes, e.g. used in pkzip.
  96     // only usable with polynom orders of 8, 16, 24 or 32.
  97     if (n == 0)
  98         return (~initval);
  99
 100     uint16_t crc = initval;
 101
 102     if (refin)
 103         crc = reflect16(crc);
 104
 105     if (!refin)
 106         while (n--) crc = (crc << 8) ^ crc_table[((crc >> 8) ^ *d++) & 0xFF ];
 107     else
 108         while (n--) crc = (crc >> 8) ^ crc_table[(crc & 0xFF) ^ *d++];
 109
 110     if (refout ^ refin)
 111         crc = reflect16(crc);
 112
 113     return crc;
 114 }
 115
 116 // bit looped solution  TODO REMOVED
 117 uint16_t update_crc16_ex(uint16_t crc, uint8_t c, uint16_t polynomial) {
 118     uint16_t tmp = 0;
 119     uint16_t v = (crc ^ c) & 0xff;
 120
 121     for (uint16_t i = 0; i < 8; i++) {
 122
 123         if ((tmp ^ v) & 1)
 124             tmp = (tmp >> 1) ^ polynomial;
 125         else
 126             tmp >>= 1;
 127
 128         v >>= 1;
 129     }
 130     return ((crc >> 8) ^ tmp) & 0xffff;
 131 }
 132 uint16_t update_crc16(uint16_t crc, uint8_t c) {
 133     return update_crc16_ex(crc, c, CRC16_POLY_CCITT);
 134 }
 135
 136 // two ways.  msb or lsb loop.
 137 uint16_t Crc16(uint8_t const *d, size_t length, uint16_t remainder, uint16_t polynomial, bool refin, bool refout) {
 138     if (length == 0)
 139         return (~remainder);
 140
 141     for (uint32_t i = 0; i < length; ++i) {
 142         uint8_t c = d[i];
 143         if (refin) c = reflect8(c);
 144
 145         // xor in at msb
 146         remainder ^= (c << 8);
 147
 148         // 8 iteration loop
 149         for (uint8_t j = 8; j; --j) {
 150             if (remainder & 0x8000) {
 151                 remainder = (remainder << 1) ^ polynomial;
 152             } else {
 153                 remainder <<=  1;
 154             }
 155         }
 156     }
 157     if (refout)
 158         remainder = reflect16(remainder);
 159
 160     return remainder;
 161 }
 162
 163 void compute_crc(CrcType_t ct, const uint8_t *d, size_t n, uint8_t *first, uint8_t *second) {
 164
 165     // can't calc a crc on less than 1 byte
 166     if (n == 0) return;
 167
 168     init_table(ct);
 169
 170     uint16_t crc = 0;
 171     switch (ct) {
 172         case CRC_14443_A:
 173             crc = crc16_a(d, n);
 174             break;
 175         case CRC_CRYPTORF:
 176         case CRC_14443_B:
 177         case CRC_15693:
 178             crc = crc16_x25(d, n);
 179             break;
 180         case CRC_ICLASS:
 181             crc = crc16_iclass(d, n);
 182             break;
 183         case CRC_FELICA:
 184         case CRC_XMODEM:
 185             crc = crc16_xmodem(d, n);
 186             break;
 187         case CRC_CCITT:
 188             crc = crc16_ccitt(d, n);
 189             break;
 190         case CRC_KERMIT:
 191             crc = crc16_kermit(d, n);
 192             break;
 193         case CRC_11784:
 194             crc = crc16_fdxb(d, n);
 195             break;
 196         case CRC_LEGIC:
 197             // TODO
 198             return;
 199         case CRC_NONE:
 200             return;
 201     }
 202     *first = (crc & 0xFF);
 203     *second = ((crc >> 8) & 0xFF);
 204 }
 205 uint16_t Crc16ex(CrcType_t ct, const uint8_t *d, size_t n) {
 206
 207     // can't calc a crc on less than 3 byte. (1byte + 2 crc bytes)
 208     if (n < 3) return 0;
 209
 210     init_table(ct);
 211     switch (ct) {
 212         case CRC_14443_A:
 213             return crc16_a(d, n);
 214         case CRC_CRYPTORF:
 215         case CRC_14443_B:
 216         case CRC_15693:
 217             return crc16_x25(d, n);
 218         case CRC_ICLASS:
 219             return crc16_iclass(d, n);
 220         case CRC_FELICA:
 221         case CRC_XMODEM:
 222             return crc16_xmodem(d, n);
 223         case CRC_CCITT:
 224             return crc16_ccitt(d, n);
 225         case CRC_KERMIT:
 226             return crc16_kermit(d, n);
 227         case CRC_11784:
 228             return crc16_fdxb(d, n);
 229         case CRC_LEGIC:
 230             // TODO
 231             return 0;
 232         case CRC_NONE:
 233         default:
 234             break;
 235     }
 236     return 0;
 237 }
 238
 239 // check CRC
 240 // ct   crc type
 241 // d    buffer with data
 242 // n    length (including crc)
 243 //
 244 //  This function uses the message + crc bytes in order to compare the "residue" afterwards.
 245 // crc16 algos like CRC-A become 0x0000
 246 // while CRC-15693 become 0x0F47
 247 // If calculated with crc bytes,  the residue should be 0xF0B8
 248 bool check_crc(CrcType_t ct, const uint8_t *d, size_t n) {
 249
 250     // can't calc a crc on less than 3 byte. (1byte + 2 crc bytes)
 251     if (n < 3) return false;
 252
 253     init_table(ct);
 254
 255     switch (ct) {
 256         case CRC_14443_A:
 257             return (crc16_a(d, n) == 0);
 258         case CRC_CRYPTORF:
 259         case CRC_14443_B:
 260             return (crc16_x25(d, n) == X25_CRC_CHECK);
 261         case CRC_15693:
 262             return (crc16_x25(d, n) == X25_CRC_CHECK);
 263         case CRC_ICLASS:
 264             return (crc16_iclass(d, n) == 0);
 265         case CRC_FELICA:
 266         case CRC_XMODEM:
 267             return (crc16_xmodem(d, n) == 0);
 268         case CRC_CCITT:
 269             return (crc16_ccitt(d, n) == 0);
 270         case CRC_KERMIT:
 271             return (crc16_kermit(d, n) == 0);
 272         case CRC_11784:
 273             return (crc16_fdxb(d, n) == 0);
 274         case CRC_LEGIC:
 275             // TODO
 276             return false;
 277         case CRC_NONE:
 278         default:
 279             break;
 280     }
 281     return false;
 282 }
 283
 284 // poly=0x1021  init=0xffff  refin=false  refout=false  xorout=0x0000  check=0x29b1  residue=0x0000  name="CRC-16/CCITT-FALSE"
 285 uint16_t crc16_ccitt(uint8_t const *d, size_t n) {
 286     return crc16_fast(d, n, 0xffff, false, false);
 287 }
 288
 289 // FDX-B ISO11784/85) uses KERMIT/CCITT
 290 // poly 0x xx  init=0x000  refin=false  refout=true  xorout=0x0000 ...
 291 uint16_t crc16_fdxb(uint8_t const *d, size_t n) {
 292     return crc16_fast(d, n, 0x0000, false, true);
 293 }
 294
 295 // poly=0x1021  init=0x0000  refin=true  refout=true  xorout=0x0000 name="KERMIT"
 296 uint16_t crc16_kermit(uint8_t const *d, size_t n) {
 297     return crc16_fast(d, n, 0x0000, true, true);
 298 }
 299
 300 // FeliCa uses XMODEM
 301 // poly=0x1021  init=0x0000  refin=false  refout=false  xorout=0x0000 name="XMODEM"
 302 uint16_t crc16_xmodem(uint8_t const *d, size_t n) {
 303     return crc16_fast(d, n, 0x0000, false, false);
 304 }
 305
 306 // Following standards uses X-25
 307 //   ISO 15693,
 308 //   ISO 14443 CRC-B
 309 //   ISO/IEC 13239 (formerly ISO/IEC 3309)
 310 // poly=0x1021  init=0xffff  refin=true  refout=true  xorout=0xffff name="X-25"
 311 uint16_t crc16_x25(uint8_t const *d, size_t n) {
 312     uint16_t crc = crc16_fast(d, n, 0xffff, true, true);
 313     crc = ~crc;
 314     return crc;
 315 }
 316 // CRC-A (14443-3)
 317 // poly=0x1021 init=0xc6c6 refin=true refout=true xorout=0x0000 name="CRC-A"
 318 uint16_t crc16_a(uint8_t const *d, size_t n) {
 319     return crc16_fast(d, n, 0xC6C6, true, true);
 320 }
 321
 322 // iClass crc
 323 // initvalue  0x4807 reflected 0xE012
 324 // poly       0x1021 reflected 0x8408
 325 // poly=0x1021  init=0x4807  refin=true  refout=true  xorout=0x0BC3  check=0xF0B8  name="CRC-16/ICLASS"
 326 uint16_t crc16_iclass(uint8_t const *d, size_t n) {
 327     return crc16_fast(d, n, 0x4807, true, true);
 328 }
 329
 330 // This CRC-16 is used in Legic Advant systems.
 331 // poly=0xB400,  init=depends  refin=true  refout=true  xorout=0x0000  check=  name="CRC-16/LEGIC"
 332 uint16_t crc16_legic(uint8_t const *d, size_t n, uint8_t uidcrc) {
 333     uint16_t initial = uidcrc << 8 | uidcrc;
 334     return crc16_fast(d, n, initial, true, true);
 335 }
 336