client/deps/reveng/model.c

   1 /* model.c
   2  * Greg Cook, 23/Feb/2019
   3  */
   4
   5 /* CRC RevEng: arbitrary-precision CRC calculator and algorithm finder
   6  * Copyright (C) 2010, 2011, 2012, 2013, 2014, 2015, 2016, 2017, 2018,
   7  * 2019  Gregory Cook
   8  *
   9  * This file is part of CRC RevEng.
  10  *
  11  * CRC RevEng is free software: you can redistribute it and/or modify
  12  * it under the terms of the GNU General Public License as published by
  13  * the Free Software Foundation, either version 3 of the License, or
  14  * (at your option) any later version.
  15  *
  16  * CRC RevEng is distributed in the hope that it will be useful,
  17  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  18  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  19  * GNU General Public License for more details.
  20  *
  21  * You should have received a copy of the GNU General Public License
  22  * along with CRC RevEng.  If not, see <https://www.gnu.org/licenses/>.
  23  */
  24
  25 /* 2018-12-17: mnovel() clears class flags
  26  * 2017-02-19: revised residue calculation for crossed-endian models
  27  * 2017-02-05: added magic field
  28  * 2016-02-22: split off preset.c
  29  * 2012-03-03: single-line Williams model string conversion
  30  * 2011-09-03: added mrev(), mnovel()
  31  * 2011-01-17: fixed ANSI C warnings (except preset models)
  32  * 2010-12-26: renamed CRC RevEng
  33  * 2010-12-18: minor change to mtostr() output format
  34  * 2010-12-15: added mcmp()
  35  * 2010-12-14: finished mtostr()
  36  * 2010-12-12: started models.c
  37  */
  38
  39 #include <stdio.h>
  40 #include <stdlib.h>
  41 #include <string.h>
  42 #include <inttypes.h>
  43 #include "reveng.h"
  44
  45 /* Private declarations */
  46
  47 static const poly_t pzero = PZERO;
  48
  49 /* Definitions */
  50
  51 void mcpy(model_t *dest, const model_t *src) {
  52     /* Copies the parameters of src to dest.
  53      * dest must be an initialised model.
  54      */
  55     if (!dest || !src) return;
  56     pcpy(&dest->spoly, src->spoly);
  57     pcpy(&dest->init, src->init);
  58     pcpy(&dest->xorout, src->xorout);
  59     pcpy(&dest->check, src->check);
  60     pcpy(&dest->magic, src->magic);
  61     dest->flags = src->flags;
  62     /* link to the name as it is static */
  63     dest->name = src->name;
  64 }
  65
  66 void mfree(model_t *model) {
  67     /* Frees the parameters of model. */
  68     if (!model) return;
  69     pfree(&model->spoly);
  70     pfree(&model->init);
  71     pfree(&model->xorout);
  72     pfree(&model->check);
  73     pfree(&model->magic);
  74     /* not name as it is static */
  75     /* not model either, it might point to an array! */
  76 }
  77
  78 int mcmp(const model_t *a, const model_t *b) {
  79     /* Compares a and b for identical effect, i.e. disregarding
  80      * trailing zeroes in parameter polys.
  81      * Intended for bsearch().
  82      */
  83     int result;
  84     if (!a || !b) return (!b - !a);
  85     if ((result = psncmp(&a->spoly, &b->spoly))) return (result);
  86     if ((result = psncmp(&a->init, &b->init))) return (result);
  87     if ((a->flags & P_REFIN) && (~b->flags & P_REFIN)) return (1);
  88     if ((~a->flags & P_REFIN) && (b->flags & P_REFIN)) return (-1);
  89     if ((a->flags & P_REFOUT) && (~b->flags & P_REFOUT)) return (1);
  90     if ((~a->flags & P_REFOUT) && (b->flags & P_REFOUT)) return (-1);
  91     return (psncmp(&a->xorout, &b->xorout));
  92 }
  93
  94 char *mtostr(const model_t *model) {
  95     /* Returns a malloc()-ed string containing a Williams model
  96      * record representing the input model.
  97      * mcanon() should be called on the argument before printing.
  98      */
  99     size_t size;
 100     char *polystr, *initstr, *xorotstr, *checkstr, *magicstr,
 101          strbuf[512], *string = NULL;
 102
 103     if (!model) return (NULL);
 104     polystr = ptostr(model->spoly, P_RTJUST, 4);
 105     initstr = ptostr(model->init, P_RTJUST, 4);
 106     xorotstr = ptostr(model->xorout, P_RTJUST, 4);
 107     checkstr = ptostr(model->check, P_RTJUST, 4);
 108     magicstr = ptostr(model->magic, P_RTJUST, 4);
 109
 110     snprintf(strbuf, sizeof(strbuf), "%lu", plen(model->spoly));
 111     size =
 112         82
 113         + strlen(strbuf)
 114         + (polystr && *polystr ? strlen(polystr) : 6)
 115         + (initstr && *initstr ? strlen(initstr) : 6)
 116         + ((model->flags & P_REFIN) ? 4 : 5)
 117         + ((model->flags & P_REFOUT) ? 4 : 5)
 118         + (xorotstr && *xorotstr ? strlen(xorotstr) : 6)
 119         + (checkstr && *checkstr ? strlen(checkstr) : 6)
 120         + (magicstr && *magicstr ? strlen(magicstr) : 6)
 121         + (model->name && *model->name ? 2 + strlen(model->name) : 6);
 122     if ((string = calloc(size, sizeof(uint8_t)))) {
 123         snprintf(strbuf, sizeof(strbuf), "\"%s\"", model->name);
 124         snprintf(string, size * sizeof(uint8_t),
 125                  "width=%lu  "
 126                  "poly=0x%s  "
 127                  "init=0x%s  "
 128                  "refin=%s  "
 129                  "refout=%s  "
 130                  "xorout=0x%s  "
 131                  "check=0x%s  "
 132                  "residue=0x%s  "
 133                  "name=%s",
 134                  plen(model->spoly),
 135                  polystr && *polystr ? polystr : "(none)",
 136                  initstr && *initstr ? initstr :  "(none)",
 137                  (model->flags & P_REFIN) ? "true" : "false",
 138                  (model->flags & P_REFOUT) ? "true" : "false",
 139                  xorotstr && *xorotstr ? xorotstr : "(none)",
 140                  checkstr && *checkstr ? checkstr : "(none)",
 141                  magicstr && *magicstr ? magicstr : "(none)",
 142                  (model->name && *model->name) ? strbuf : "(none)");
 143     }
 144     free(polystr);
 145     free(initstr);
 146     free(xorotstr);
 147     free(checkstr);
 148     free(magicstr);
 149     if (!string)
 150         uerror("cannot allocate memory for model description");
 151     return (string);
 152 }
 153
 154 void mcanon(model_t *model) {
 155     /* canonicalise a model */
 156     unsigned long dlen;
 157
 158     if (!model) return;
 159
 160     /* extending on the right here. This preserves the functionality
 161      * of a presumed working model.
 162      */
 163     psnorm(&model->spoly);
 164     dlen = plen(model->spoly);
 165     praloc(&model->init, dlen);
 166     praloc(&model->xorout, dlen);
 167
 168     /* only calculate Check if missing.  Relying on all functions
 169      * changing parameters to call mnovel().  This is to ensure that
 170      * the Check value stored in the preset table is printed when
 171      * the model is dumped.  If something goes wrong with the
 172      * calculator then the discrepancy with the stored Check value
 173      * might be noticed.  Storing the Check value with each preset
 174      * is highly preferred.
 175      */
 176     if (!(plen(model->check) && plen(model->magic)))
 177         mcheck(model);
 178 }
 179
 180 void mcheck(model_t *model) {
 181     /* calculate a check for the model */
 182     poly_t checkstr, check, xorout, magic;
 183
 184     /* erase existing check and magic.  Models with these
 185      * fields recalculated should have no name.
 186      */
 187     mnovel(model);
 188
 189     /* generate the check string with the correct bit order */
 190     checkstr = strtop("313233343536373839", model->flags, 8);
 191     check = pcrc(checkstr, model->spoly, model->init, pzero, model->flags);
 192     pfree(&checkstr);
 193     if (model->flags & P_REFOUT)
 194         prev(&check);
 195     psum(&check, model->xorout, 0UL);
 196     model->check = check;
 197
 198     /* calculate residue by emulating receipt of error-free message
 199      * The residue of a crossed-endian model is calculated assuming
 200      * that the characters of the received CRC are specially
 201      * reflected before submitting the codeword.
 202      */
 203     xorout = pclone(model->xorout);
 204     if (model->flags & P_REFOUT)
 205         prev(&xorout);
 206     magic = pcrc(xorout, model->spoly, pzero, pzero, model->flags);
 207     pfree(&xorout);
 208     if (model->flags & P_REFIN)
 209         prev(&magic);
 210     model->magic = magic;
 211 }
 212
 213 void mrev(model_t *model) {
 214     /* reverse the model to calculate reversed CRCs */
 215     /* Here we invert RefIn and RefOut so that the user need only
 216      * reverse the order of characters in the arguments, not the
 217      * characters themselves.  If RefOut=True, the mirror image of
 218      * Init seen through RefOut becomes XorOut, and as RefOut
 219      * becomes false, the XorOut value moved to Init stays upright.
 220      * If RefOut=False, Init transfers to XorOut without reflection
 221      * but the new Init must be reflected to present the same image,
 222      * as RefOut becomes true.
 223      */
 224     poly_t temp;
 225
 226     prcp(&model->spoly);
 227     if (model->flags & P_REFOUT)
 228         prev(&model->init);
 229     else
 230         prev(&model->xorout);
 231
 232     /* exchange init and xorout */
 233     temp = model->init;
 234     model->init = model->xorout;
 235     model->xorout = temp;
 236
 237     /* invert refin and refout */
 238     model->flags ^= P_REFIN | P_REFOUT;
 239
 240     mnovel(model);
 241 }
 242
 243 void mnovel(model_t *model) {
 244     /* remove name and check string from modified model */
 245     /* previous classification no longer applies */
 246     model->name = NULL;
 247     model->flags &= ~P_CLMASK;
 248     pfree(&model->check);
 249     pfree(&model->magic);
 250 }