common/crc16.c

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