cmdhflegic.c \
cmdhficlass.c \
cmdhfmf.c \
- cmdhfmfu.c \
+ cmdhfmfu.c \
cmdhw.c \
cmdlf.c \
cmdlfio.c \
aes.c\
protocols.c\
sha1.c\
-
+ cmdcrc.c\
+ reveng/reveng.c\
+ reveng/cli.c\
+ reveng/bmpbit.c\
+ reveng/model.c\
+ reveng/poly.c\
+ reveng/getopt.c\
COREOBJS = $(CORESRCS:%.c=$(OBJDIR)/%.o)
CMDOBJS = $(CMDSRCS:%.c=$(OBJDIR)/%.o)
--- /dev/null
+//-----------------------------------------------------------------------------
+// Copyright (C) 2015 iceman <iceman at iuse.se>
+//
+// This code is licensed to you under the terms of the GNU GPL, version 2 or,
+// at your option, any later version. See the LICENSE.txt file for the text of
+// the license.
+//-----------------------------------------------------------------------------
+// CRC Calculations from the software reveng commands
+//-----------------------------------------------------------------------------
+
+#include <stdio.h>
+#include <string.h>
+#include "cmdmain.h"
+#include "cmdparser.h"
+#include "cmdcrc.h"
+#include "reveng/reveng.h"
+//#include "reveng/cli.h"
+static int CmdHelp(const char *Cmd);
+
+int CmdCrcCalc(const char *Cmd)
+{
+ int argc = 0;
+ char Cmd2[CMD_BUFFER_SIZE] = {0x00};
+ char *argv[3];
+
+ for (int i = 0; i < 50; i++)
+ if (Cmd[i]==0x00) argc=i;
+
+ memcpy(Cmd2, Cmd, argc);
+ argv[1]=Cmd2;
+ reveng_main(argc, argv);
+ return 0;
+}
+
+static command_t CommandTable[] =
+{
+ {"help", CmdHelp, 1, "This help"},
+ {"calc", CmdCrcCalc, 1, "{ Calculate CRC's }"},
+ {NULL, NULL, 0, NULL}
+};
+
+int CmdCrc(const char *Cmd)
+{
+ CmdsParse(CommandTable, Cmd);
+ return 0;
+}
+
+int CmdHelp(const char *Cmd)
+{
+ CmdsHelp(CommandTable);
+ return 0;
+}
--- /dev/null
+//-----------------------------------------------------------------------------
+// Copyright (C) 2015 iceman <iceman at iuse.se>
+//
+// This code is licensed to you under the terms of the GNU GPL, version 2 or,
+// at your option, any later version. See the LICENSE.txt file for the text of
+// the license.
+//-----------------------------------------------------------------------------
+// CRC Calculations from the software reveng commands
+//-----------------------------------------------------------------------------
+
+#ifndef CMDCRC_H__
+#define CMDCRC_H__
+
+int CmdCrc(const char *Cmd);
+int CmdCrcCalc(const char *Cmd);
+#endif
#include "cmdmain.h"
#include "util.h"
#include "cmdscript.h"
+#include "cmdcrc.h"
unsigned int current_command = CMD_UNKNOWN;
static int CmdQuit(const char *Cmd);
//For storing command that are received from the device
-#define CMD_BUFFER_SIZE 50
static UsbCommand cmdBuffer[CMD_BUFFER_SIZE];
//Points to the next empty position to write to
static int cmd_head;//Starts as 0
static command_t CommandTable[] =
{
{"help", CmdHelp, 1, "This help. Use '<command> help' for details of a particular command."},
+ {"crc", CmdCrc, 1, "Crc calculations from the software reveng1-30"},
{"data", CmdData, 1, "{ Plot window / data buffer manipulation... }"},
- {"hf", CmdHF, 1, "{ High Frequency commands... }"},
+ {"hf", CmdHF, 1, "{ High Frequency commands... }"},
{"hw", CmdHW, 1, "{ Hardware commands... }"},
- {"lf", CmdLF, 1, "{ Low Frequency commands... }"},
- {"script", CmdScript, 1,"{ Scripting commands }"},
+ {"lf", CmdLF, 1, "{ Low Frequency commands... }"},
+ {"script",CmdScript,1,"{ Scripting commands }"},
{"quit", CmdQuit, 1, "Exit program"},
{"exit", CmdQuit, 1, "Exit program"},
{NULL, NULL, 0, NULL}
bool WaitForResponse(uint32_t cmd, UsbCommand* response);
void clearCommandBuffer();
command_t* getTopLevelCommandTable();
+
+//For storing command that are received from the device
+#define CMD_BUFFER_SIZE 50
+
#endif
--- /dev/null
+/* bmpbit.c
+ * Greg Cook, 9/Apr/2015
+ */
+
+/* CRC RevEng, an arbitrary-precision CRC calculator and algorithm finder
+ * Copyright (C) 2010, 2011, 2012, 2013, 2014, 2015 Gregory Cook
+ *
+ * This file is part of CRC RevEng.
+ *
+ * CRC RevEng is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * CRC RevEng is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with CRC RevEng. If not, see <http://www.gnu.org/licenses/>.
+ */
+
+#ifdef BMPTST
+# include <stdio.h>
+# include <stdlib.h>
+#else
+# define FILE void
+#endif
+#include "reveng.h"
+
+#if (defined BMPTST) || (BMP_BIT < 32)
+/* Size in bits of a bmp_t. Not necessarily a power of two. */
+int bmpbit;
+
+/* The highest power of two that is strictly less than BMP_BIT.
+ * Initialises the index of a binary search for set bits in a bmp_t.
+ * (Computed correctly for BMP_BIT >= 2)
+ */
+int bmpsub;
+
+void
+setbmp(void) {
+ /* Initialise BMP_BIT and BMP_SUB for the local architecture. */
+ bmp_t bmpmax = ~(bmp_t) 0;
+
+ bmpbit = 0; bmpsub = 1;
+
+ while(bmpmax) {
+ bmpmax <<= 1;
+ ++bmpbit;
+ }
+
+ while((bmpsub | (bmpsub - 1)) < bmpbit - 1)
+ bmpsub <<= 1;
+}
+#endif
+
+#ifdef BMPTST
+int
+main(int argc, char *argv[]) {
+ /* check the compile-time bitmap width is correct, otherwise
+ * searches run forever. */
+# if BMP_BIT > 0
+ setbmp();
+ if(BMP_BIT != bmpbit || BMP_SUB != bmpsub) {
+ fprintf(stderr,"reveng: configuration fault. Update "
+ "config.h with these definitions and "
+ "recompile:\n"
+ "\t#define BMP_BIT %d\n"
+ "\t#define BMP_SUB %d\n",
+ bmpbit, bmpsub);
+ exit(EXIT_FAILURE);
+ }
+# endif /* BMP_BIT > 0 */
+ /* check the bitmap constant macro */
+ if(~(bmp_t) 0 != ~BMP_C(0)) {
+ fprintf(stderr, "reveng: configuration fault. Edit "
+ "the definition of BMP_C() in config.h to "
+ "match BMP_T and recompile.\n");
+ exit(EXIT_FAILURE);
+ }
+ exit(EXIT_SUCCESS);
+}
+
+#endif /* BMPTST */
--- /dev/null
+/* cli.c
+ * Greg Cook, 9/Apr/2015
+ */
+
+/* CRC RevEng, an arbitrary-precision CRC calculator and algorithm finder
+ * Copyright (C) 2010, 2011, 2012, 2013, 2014, 2015 Gregory Cook
+ *
+ * This file is part of CRC RevEng.
+ *
+ * CRC RevEng is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * CRC RevEng is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with CRC RevEng. If not, see <http://www.gnu.org/licenses/>.
+ */
+
+/* 2015-04-03: added -z
+ * 2013-09-16: do not search with -M
+ * 2013-06-11: uprog() suppresses first progress report
+ * 2013-04-22: uprog() prints poly same as mtostr()
+ * 2013-02-07: added -q, uprog(), removed -W, R_ODDLY
+ * 2012-05-24: -D dumps parameters of all models
+ * 2012-03-03: added code to test sort order of model table
+ * 2012-02-20: set stdin to binary (MinGW). offer -D if preset unknown.
+ * 2011-09-06: -s reads arguments once. stdin not closed.
+ * 2011-09-06: fixed bad argument-freeing loops.
+ * 2011-08-27: validates BMP_C()
+ * 2011-08-26: validates BMPBIT and BMPSUB
+ * 2011-08-25: fixed Init/Xorout reflection logic in -V and -v
+ * 2011-01-17: fixed ANSI C warnings
+ * 2011-01-15: added NOFORCE
+ * 2011-01-14: added -k, -P
+ * 2011-01-10: reorganised switches, added -V, -X
+ * 2010-12-26: renamed CRC RevEng
+ * 2010-12-18: implemented -c, -C
+ * 2010-12-14: added and implemented -d, -D, fixed -ipx entry
+ * 2010-12-11: implemented -e. first tests
+ * 2010-12-10: finalised option processing. started input validation
+ * 2010-12-07: started cli
+ */
+
+#include <stdio.h>
+#include <stdlib.h>
+#include "getopt.h"
+#ifdef _WIN32
+# include <io.h>
+# include <fcntl.h>
+# ifndef STDIN_FILENO
+# define STDIN_FILENO 0
+# endif /* STDIN_FILENO */
+#endif /* _WIN32 */
+
+#include "reveng.h"
+
+static FILE *oread(const char *);
+static poly_t rdpoly(const char *, int, int);
+static void usage(void);
+
+static const char *myname = "reveng"; /* name of our program */
+
+int reveng_main(int argc, char *argv[]) {
+ /* Command-line interface for CRC RevEng.
+ * Process options and switches in the argument list and
+ * run the required function.
+ */
+
+ /* default values */
+ model_t model = {
+ PZERO, /* no CRC polynomial, user must specify */
+ PZERO, /* Init = 0 */
+ P_BE, /* RefIn = false, RefOut = false, plus P_RTJUST setting in reveng.h */
+ PZERO, /* XorOut = 0 */
+ PZERO, /* check value unused */
+ NULL /* no model name */
+ };
+ int ibperhx = 8, obperhx = 8;
+ int rflags = 0, uflags = 0; /* search and UI flags */
+
+ unsigned long width = 0UL;
+ int c, mode = 0, args, psets, pass;
+ poly_t apoly, crc, qpoly = PZERO, *apolys, *pptr = NULL, *qptr = NULL;
+ model_t pset = model, *candmods, *mptr;
+ char *string;
+
+ //myname = argv[0];
+
+ /* stdin must be binary */
+#ifdef _WIN32
+ _setmode(STDIN_FILENO, _O_BINARY);
+#endif /* _WIN32 */
+
+ SETBMP();
+
+ do {
+ c=getopt(argc, argv, "?A:BDFLMP:SVXa:bcdefhi:k:lm:p:q:rstuvw:x:yz");
+ switch(c) {
+ case 'A': /* A: bits per output character */
+ case 'a': /* a: bits per character */
+ if((obperhx = atoi(optarg)) > BMP_BIT) {
+ fprintf(stderr,"%s: argument to -%c must be between 1 and %d\n", myname, c, BMP_BIT);
+ return 0;
+ //exit(EXIT_FAILURE);
+ }
+ if(c == 'a') ibperhx = obperhx;
+ break;
+ case 'b': /* b big-endian (RefIn = false, RefOut = false ) */
+ model.flags &= ~P_REFIN;
+ rflags |= R_HAVERI;
+ /* fall through: */
+ case 'B': /* B big-endian output (RefOut = false) */
+ model.flags &= ~P_REFOUT;
+ rflags |= R_HAVERO;
+ mnovel(&model);
+ /* fall through: */
+ case 'r': /* r right-justified */
+ model.flags |= P_RTJUST;
+ break;
+ case 'c': /* c calculate CRC */
+ case 'D': /* D list primary model names */
+ case 'd': /* d dump CRC model */
+ case 'e': /* e echo arguments */
+ case 's': /* s search for algorithm */
+ case 'v': /* v calculate reversed CRC */
+ if(mode) {
+ fprintf(stderr,"%s: more than one mode switch specified. Use %s -h for help.\n", myname, myname);
+ return 0;
+ //exit(EXIT_FAILURE);
+ }
+ mode = c;
+ break;
+ case 'F': /* F force search */
+#ifndef NOFORCE
+ uflags |= C_FORCE;
+#endif
+ break;
+ case 'f': /* f arguments are filenames */
+ uflags |= C_INFILE;
+ break;
+ case 'h': /* h get help / usage */
+ case 'u': /* u get help / usage */
+ case '?': /* ? get help / usage */
+ default:
+ usage();
+ return 0;
+ //exit(EXIT_FAILURE);
+ break;
+ case 'i': /* i: Init value */
+ pptr = &model.init;
+ rflags |= R_HAVEI;
+ goto ippx;
+ case 'k': /* k: polynomial in Koopman notation */
+ pfree(&model.spoly);
+ model.spoly = strtop(optarg, 0, 4);
+ pkchop(&model.spoly);
+ width = plen(model.spoly);
+ rflags |= R_HAVEP;
+ mnovel(&model);
+ break;
+ case 'l': /* l little-endian input and output */
+ model.flags |= P_REFIN;
+ rflags |= R_HAVERI;
+ /* fall through: */
+ case 'L': /* L little-endian output */
+ model.flags |= P_REFOUT;
+ rflags |= R_HAVERO;
+ mnovel(&model);
+ /* fall through: */
+ case 't': /* t left-justified */
+ model.flags &= ~P_RTJUST;
+ break;
+ case 'm': /* m: select preset CRC model */
+ if(!(c = mbynam(&model, optarg))) {
+ fprintf(stderr,"%s: preset model '%s' not found. Use %s -D to list presets.\n", myname, optarg, myname);
+ return 0;
+ //exit(EXIT_FAILURE);
+ }
+ if(c < 0)
+ uerror("no preset models available");
+ /* must set width so that parameter to -ipx is not zeroed */
+ width = plen(model.spoly);
+ rflags |= R_HAVEP | R_HAVEI | R_HAVERI | R_HAVERO | R_HAVEX;
+ break;
+ case 'M': /* M non-augmenting algorithm */
+ model.flags &= ~P_MULXN;
+ break;
+ case 'P': /* P: reversed polynomial */
+ case 'p': /* p: polynomial */
+ pptr = &model.spoly;
+ rflags &= ~R_HAVEQ;
+ rflags |= R_HAVEP;
+ippx:
+ pfree(pptr);
+ *pptr = strtop(optarg, 0, 4);
+ pright(pptr, width);
+ if(c == 'P')
+ prev(pptr);
+ mnovel(&model);
+ break;
+ case 'q': /* q: range end polynomial */
+ pptr = &qpoly;
+ rflags &= ~R_HAVEP;
+ rflags |= R_HAVEQ;
+ goto ippx;
+ case 'S': /* s space between output characters */
+ model.flags |= P_SPACE;
+ break;
+ case 'V': /* v reverse algorithm */
+ /* Distinct from the -v switch as the
+ * user will have to reverse his or her
+ * own arguments. The user cannot dump
+ * the model generated by -v either.
+ */
+ mrev(&model);
+ break;
+ case 'w': /* w: CRC width = order - 1 */
+ width = (unsigned long) atol(optarg);
+ break;
+ case 'X': /* X print uppercase hex */
+ model.flags |= P_UPPER;
+ break;
+ case 'x': /* x: XorOut value */
+ pptr = &model.xorout;
+ rflags |= R_HAVEX;
+ goto ippx;
+ case 'y': /* y little-endian byte order in files */
+ model.flags |= P_LTLBYT;
+ break;
+ case 'z': /* z raw binary arguments */
+ model.flags |= P_DIRECT;
+ break;
+ case -1: /* no more options, continue */
+ ;
+ }
+ } while(c != -1);
+
+ /* canonicalise the model, so the one we dump is the one we
+ * calculate with (not with -s, spoly may be blank which will
+ * normalise to zero and clear init and xorout.)
+ */
+ if(mode != 's')
+ mcanon(&model);
+
+ switch(mode) {
+ case 'v': /* v calculate reversed CRC */
+ /* Distinct from the -V switch as this causes
+ * the arguments and output to be reversed as well.
+ */
+ /* reciprocate Poly */
+ prcp(&model.spoly);
+
+ /* mrev() does:
+ * if(refout) prev(init); else prev(xorout);
+ * but here the entire argument polynomial is
+ * reflected, not just the characters, so RefIn
+ * and RefOut are not inverted as with -V.
+ * Consequently Init is the mirror image of the
+ * one resulting from -V, and so we have:
+ */
+ if(~model.flags & P_REFOUT) {
+ prev(&model.init);
+ prev(&model.xorout);
+ }
+
+ /* swap init and xorout */
+ apoly = model.init;
+ model.init = model.xorout;
+ model.xorout = apoly;
+
+ /* fall through: */
+ case 'c': /* c calculate CRC */
+
+ /* validate inputs */
+ /* if(plen(model.spoly) == 0) {
+ * fprintf(stderr,"%s: no polynomial specified for -%c (add -w WIDTH -p POLY)\n", myname, mode);
+ * exit(EXIT_FAILURE);
+ * }
+ */
+
+ /* in the Williams model, xorout is applied after the refout stage.
+ * as refout is part of ptostr(), we reverse xorout here.
+ */
+ if(model.flags & P_REFOUT)
+ prev(&model.xorout);
+
+ for(; optind < argc; ++optind) {
+ if(uflags & C_INFILE)
+ apoly = rdpoly(argv[optind], model.flags, ibperhx);
+ else
+ apoly = strtop(argv[optind], model.flags, ibperhx);
+
+ if(mode == 'v')
+ prev(&apoly);
+
+ crc = pcrc(apoly, model.spoly, model.init, model.xorout, model.flags);
+
+ if(mode == 'v')
+ prev(&crc);
+
+ string = ptostr(crc, model.flags, obperhx);
+ puts(string);
+ free(string);
+ pfree(&crc);
+ pfree(&apoly);
+ }
+ break;
+ case 'D': /* D dump all models */
+ args = mcount();
+ if(!args)
+ uerror("no preset models available");
+ for(mode = 0; mode < args; ++mode) {
+ mbynum(&model, mode);
+ mcanon(&model);
+ ufound(&model);
+ }
+ break;
+ case 'd': /* d dump CRC model */
+ /* maybe we don't want to do this:
+ * either attaching names to arbitrary models or forcing to a preset
+ * mmatch(&model, M_OVERWR);
+ */
+ if(~model.flags & P_MULXN)
+ uerror("not a Williams model compliant algorithm");
+ string = mtostr(&model);
+ puts(string);
+ free(string);
+ break;
+ case 'e': /* e echo arguments */
+ for(; optind < argc; ++optind) {
+ if(uflags & C_INFILE)
+ apoly = rdpoly(argv[optind], model.flags, ibperhx);
+ else
+ apoly = strtop(argv[optind], model.flags, ibperhx);
+
+ psum(&apoly, model.init, 0UL);
+ string = ptostr(apoly, model.flags, obperhx);
+ puts(string);
+ free(string);
+ pfree(&apoly);
+ }
+ break;
+ case 's': /* s search for algorithm */
+ if(!width)
+ uerror("must specify positive -k or -w before -s");
+ if(~model.flags & P_MULXN)
+ uerror("cannot search for non-Williams compliant models");
+ praloc(&model.spoly, width);
+ praloc(&model.init, width);
+ praloc(&model.xorout, width);
+ if(!plen(model.spoly))
+ palloc(&model.spoly, width);
+ else
+ width = plen(model.spoly);
+
+ /* special case if qpoly is zero, search to end of range */
+ if(!ptst(qpoly))
+ rflags &= ~R_HAVEQ;
+
+ /* allocate argument array */
+ args = argc - optind;
+ if(!(apolys = malloc(args * sizeof(poly_t))))
+ uerror("cannot allocate memory for argument list");
+
+ for(pptr = apolys; optind < argc; ++optind) {
+ if(uflags & C_INFILE)
+ *pptr++ = rdpoly(argv[optind], model.flags, ibperhx);
+ else
+ *pptr++ = strtop(argv[optind], model.flags, ibperhx);
+ }
+ /* exit value of pptr is used hereafter! */
+
+ /* if endianness not specified, try
+ * little-endian then big-endian.
+ * NB: crossed-endian algorithms will not be
+ * searched.
+ */
+
+ /* scan against preset models */
+ if(~uflags & C_FORCE) {
+ pass = 0;
+ do {
+ psets = mcount();
+ while(psets) {
+ mbynum(&pset, --psets);
+ /* skip if different width, or refin or refout don't match */
+ if(plen(pset.spoly) != width || (model.flags ^ pset.flags) & (P_REFIN | P_REFOUT))
+ continue;
+ /* skip if the preset doesn't match specified parameters */
+ if(rflags & R_HAVEP && pcmp(&model.spoly, &pset.spoly))
+ continue;
+ if(rflags & R_HAVEI && psncmp(&model.init, &pset.init))
+ continue;
+ if(rflags & R_HAVEX && psncmp(&model.xorout, &pset.xorout))
+ continue;
+ apoly = pclone(pset.xorout);
+ if(pset.flags & P_REFOUT)
+ prev(&apoly);
+ for(qptr = apolys; qptr < pptr; ++qptr) {
+ crc = pcrc(*qptr, pset.spoly, pset.init, apoly, 0);
+ if(ptst(crc)) {
+ pfree(&crc);
+ break;
+ } else
+ pfree(&crc);
+ }
+ pfree(&apoly);
+ if(qptr == pptr) {
+ /* the selected model solved all arguments */
+ mcanon(&pset);
+ ufound(&pset);
+ uflags |= C_RESULT;
+ }
+ }
+ mfree(&pset);
+
+ /* toggle refIn/refOut and reflect arguments */
+ if(~rflags & R_HAVERI) {
+ model.flags ^= P_REFIN | P_REFOUT;
+ for(qptr = apolys; qptr < pptr; ++qptr)
+ prevch(qptr, ibperhx);
+ }
+ } while(~rflags & R_HAVERI && ++pass < 2);
+ }
+ if(uflags & C_RESULT) {
+ for(qptr = apolys; qptr < pptr; ++qptr)
+ pfree(qptr);
+ return 1;
+ //exit(EXIT_SUCCESS);
+ }
+ if(!(model.flags & P_REFIN) != !(model.flags & P_REFOUT))
+ uerror("cannot search for crossed-endian models");
+ pass = 0;
+ do {
+ mptr = candmods = reveng(&model, qpoly, rflags, args, apolys);
+ if(mptr && plen(mptr->spoly))
+ uflags |= C_RESULT;
+ while(mptr && plen(mptr->spoly)) {
+ /* results were printed by the callback
+ * string = mtostr(mptr);
+ * puts(string);
+ * free(string);
+ */
+ mfree(mptr++);
+ }
+ free(candmods);
+ if(~rflags & R_HAVERI) {
+ model.flags ^= P_REFIN | P_REFOUT;
+ for(qptr = apolys; qptr < pptr; ++qptr)
+ prevch(qptr, ibperhx);
+ }
+ } while(~rflags & R_HAVERI && ++pass < 2);
+ for(qptr = apolys; qptr < pptr; ++qptr)
+ pfree(qptr);
+ free(apolys);
+ if(~uflags & C_RESULT)
+ uerror("no models found");
+ break;
+ default: /* no mode specified */
+ fprintf(stderr, "%s: no mode switch specified. Use %s -h for help.\n", myname, myname);
+ return 0;
+ //exit(EXIT_FAILURE);
+ }
+
+ return 1;
+ //exit(EXIT_SUCCESS);
+}
+
+void
+ufound(const model_t *model) {
+ /* Callback function to report each model found */
+ char *string;
+
+ if(!model) return;
+ /* generated models will be canonical */
+ string = mtostr(model);
+ puts(string);
+ free(string);
+}
+
+void
+uerror(const char *msg) {
+ /* Callback function to report fatal errors */
+ fprintf(stderr, "%s: %s\n", myname, msg);
+ exit(EXIT_FAILURE);
+}
+
+void
+uprog(const poly_t gpoly, int flags, unsigned long seq) {
+ /* Callback function to report search progress */
+ char *string;
+
+ /* Suppress first report in CLI */
+ if(!seq)
+ return;
+ string = ptostr(gpoly, P_RTJUST, 4);
+ fprintf(stderr, "%s: searching: width=%ld poly=0x%s refin=%s refout=%s\n",
+ myname, plen(gpoly), string,
+ (flags & P_REFIN ? "true" : "false"),
+ (flags & P_REFOUT ? "true" : "false")
+ );
+ free(string);
+}
+
+static poly_t
+rdpoly(const char *name, int flags, int bperhx) {
+ /* read poly from file in chunks and report errors */
+
+ poly_t apoly = PZERO, chunk = PZERO;
+ FILE *input;
+
+ input = oread(name);
+ while(!feof(input) && !ferror(input)) {
+ chunk = filtop(input, BUFFER, flags, bperhx);
+ psum(&apoly, chunk, plen(apoly));
+ pfree(&chunk);
+ }
+ if(ferror(input)) {
+ fprintf(stderr,"%s: error condition on file '%s'\n", myname, name);
+ exit(EXIT_FAILURE);
+ }
+ /* close file unless stdin */
+ if(input == stdin)
+ /* reset EOF condition */
+ clearerr(input);
+ else if(fclose(input)) {
+ fprintf(stderr,"%s: error closing file '%s'\n", myname, name);
+ exit(EXIT_FAILURE);
+ }
+ return(apoly);
+}
+
+static FILE *
+oread(const char *name) {
+ /* open file for reading and report errors */
+ FILE *handle;
+
+ /* recognise special name '-' as standard input */
+ if(*name == '-' && name[1] == '\0')
+ return(stdin);
+ if(!(handle = fopen(name, "rb"))) {
+ fprintf(stderr, "%s: cannot open '%s' for reading\n", myname, name);
+ exit(EXIT_FAILURE);
+ }
+ return(handle);
+}
+
+static void
+usage(void) {
+ /* print usage if asked, or if syntax incorrect */
+ fprintf(stderr,
+ "CRC RevEng, an arbitrary-precision CRC calculator and algorithm finder\n"
+ "Usage:\t");
+ fputs(myname, stderr);
+ fprintf(stderr,
+ "\t-cdDesvhu? [-bBfFlLMrStVXyz]\n"
+ "\t\t[-a BITS] [-A OBITS] [-i INIT] [-k KPOLY] [-m MODEL]\n"
+ "\t\t[-p POLY] [-P RPOLY] [-q QPOLY] [-w WIDTH] [-x XOROUT]\n"
+ "\t\t[STRING...]\n"
+ "Options:\n"
+ "\t-a BITS\t\tbits per character (1 to %d)\n"
+ "\t-A OBITS\tbits per output character (1 to %d)\n"
+ "\t-i INIT\t\tinitial register value\n"
+ "\t-k KPOLY\tgenerator in Koopman notation (implies WIDTH)\n"
+ "\t-m MODEL\tpreset CRC algorithm\n"
+ "\t-p POLY\t\tgenerator or search range start polynomial\n"
+ "\t-P RPOLY\treversed generator polynomial\n",
+ BMP_BIT, BMP_BIT);
+ fprintf(stderr,
+ "\t-q QPOLY\tsearch range end polynomial\n"
+ "\t-w WIDTH\tregister size, in bits\n"
+ "\t-x XOROUT\tfinal register XOR value\n"
+ "Modifier switches:\n"
+ "\t-b big-endian CRC\t\t-B big-endian CRC output\n"
+ "\t-f read files named in STRINGs\t-F find presets less quickly\n"
+ "\t-l little-endian CRC\t\t-L little-endian CRC output\n"
+ "\t-M non-augmenting algorithm\t-r right-justified output\n"
+ "\t-S print spaces between chars\t-t left-justified output\n"
+ "\t-V reverse algorithm only\t-X print uppercase hex\n"
+ "\t-y low bytes first in files\t-z raw binary STRINGs\n");
+ fprintf(stderr,
+ "Mode switches:\n"
+ "\t-c calculate CRCs\t\t-d dump algorithm parameters\n"
+ "\t-D list preset algorithms\t-e echo (and reformat) input\n"
+ "\t-s search for algorithm\t\t-v calculate reversed CRCs\n"
+ "\t-h | -u | -? show this help\n"
+ "\n"
+ "Copyright (C) 2010, 2011, 2012, 2013, 2014, 2015 Gregory Cook\n"
+ "This is free software; see the source for copying conditions. There is NO\n"
+ "warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.\n"
+ "Version "
+ VERSION
+ "\t\t\t\t <http://reveng.sourceforge.net/>\n");
+}
--- /dev/null
+/* config.h
+ * Greg Cook, 9/Apr/2015
+ */
+
+/* CRC RevEng, an arbitrary-precision CRC calculator and algorithm finder
+ * Copyright (C) 2010, 2011, 2012, 2013, 2014, 2015 Gregory Cook
+ *
+ * This file is part of CRC RevEng.
+ *
+ * CRC RevEng is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * CRC RevEng is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with CRC RevEng. If not, see <http://www.gnu.org/licenses/>.
+ */
+
+#ifndef CONFIG_H
+#define CONFIG_H 1
+
+/*****************************************
+ * *
+ * Start of user configuration options *
+ * *
+ *****************************************/
+
+/* A type to contain polynomial coefficient bitmaps.
+ * Can be changed to 'unsigned long long' for some extended compilers.
+ * Adjust BMP_C(), BMP_BIT and BMP_SUB below if this is changed.
+ */
+
+#define BMP_T unsigned long
+
+/* Creates an appropriate numeric constant for bmp_t.
+ * If the underlying type is 'unsigned long long', change UL to ULL.
+ */
+
+#define BMP_C(n) (n##UL)
+
+/* Define BMPMACRO to turn the definitions of the size of a bmp_t into
+ * compile-time constants. This improves efficiency but makes the code
+ * platform-specific.
+ */
+
+/* #define BMPMACRO 1 */
+
+/* Some enterprise users may wish to disable the -F switch to minimise CPU
+ * usage. To do this, define the macro NOFORCE.
+ */
+
+/* #define NOFORCE 1 */
+
+/* Define PRESETS to compile CRC RevEng with the preset models from the
+ * CRC Catalogue. This implies BMPMACRO and so makes the code platform-
+ * specific.
+ */
+
+/* #define PRESETS 1 */
+
+/* Macros defining the size of a bmp_t.
+ * Their values only matter if PRESETS and/or BMPMACRO are defined, in
+ * which case edit the macros below to suit your architecture.
+ * Otherwise, BMP_BIT and BMP_SUB will be redefined as aliases of bmpbit
+ * and bmpsub, global objects initialised at run time.
+ */
+
+/* Size in bits of a bmp_t. Not necessarily a power of two. */
+
+#define BMP_BIT 32
+
+/* The highest power of two that is strictly less than BMP_BIT.
+ * Initialises the index of a binary search for set bits in a bmp_t.
+ */
+
+#define BMP_SUB 16
+
+/*****************************************
+ * *
+ * End of user configuration options *
+ * *
+ *****************************************/
+
+#endif /* CONFIG_H */
--- /dev/null
+/*----------------------------------------------------------------------
+
+ Replacement for Unix "getopt()", for DOS/Windows/etc.
+
+ getopt.c 1.3 2003/09/17 16:17:59
+
+ Copyright (C) 1998, 2003 by David A. Hinds -- All Rights Reserved
+
+ This file is part of ASPEX.
+
+ ASPEX is free software; you can redistribute it and/or modify it
+ under the terms of the GNU General Public License as published by
+ the Free Software Foundation; either version 2 of the License, or
+ (at your option) any later version.
+
+ ASPEX is distributed in the hope that it will be useful, but
+ WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ General Public License for more details.
+
+ You should have received a copy of the GNU General Public License
+ along with ASPEX; if not, write to the Free Software Foundation,
+ Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+
+----------------------------------------------------------------------*/
+
+#include "string.h"
+#include "stdio.h"
+#include "getopt.h"
+
+char *optarg;
+int optind = 1, opterr, optopt;
+
+int getopt(int argc, char *argv[], const char *optstring)
+{
+ static int pos = 0;
+ char *str;
+
+ if (pos == 0) {
+ if ((optind >= argc) || (*argv[optind] != '-'))
+ return EOF;
+ pos = 1;
+ if (argv[optind][pos] == '\0')
+ return EOF;
+ }
+
+ str = strchr(optstring, argv[optind][pos]);
+ if (str == NULL) {
+ optopt = argv[optind][pos];
+ if (opterr)
+ fprintf(stderr, "%s: illegal option -- %c\n", argv[0],
+ optopt);
+ return '?';
+ }
+
+ if (str[1] == ':') {
+ if (argv[optind][pos+1] != '\0') {
+ optarg = &argv[optind][pos+1];
+ return *str;
+ }
+ optind++;
+ if (optind >= argc) {
+ optopt = *str;
+ if (opterr)
+ fprintf(stderr, "%s: option requires an argument -- %c\n",
+ argv[0], optopt);
+ return '?';
+ }
+ optarg = argv[optind];
+ optind++; pos = 0;
+ return *str;
+ }
+ else {
+ pos++;
+ if (argv[optind][pos] == '\0') {
+ optind++;
+ pos = 0;
+ }
+ return *str;
+ }
+}
--- /dev/null
+/*
+ getopt.h 1.2 2003/09/17 16:17:59
+
+ Copyright (C) 1998, 2003 by David A. Hinds -- All Rights Reserved
+
+ This file is part of ASPEX.
+
+ ASPEX is free software; you can redistribute it and/or modify it
+ under the terms of the GNU General Public License as published by
+ the Free Software Foundation; either version 2 of the License, or
+ (at your option) any later version.
+
+ ASPEX is distributed in the hope that it will be useful, but
+ WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ General Public License for more details.
+
+ You should have received a copy of the GNU General Public License
+ along with ASPEX; if not, write to the Free Software Foundation,
+ Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+*/
+
+extern char *optarg;
+extern int optind, opterr, optopt;
+int getopt(int argc, char *argv[], const char *optstring);
--- /dev/null
+/* model.c
+ * Greg Cook, 9/Apr/2015
+ */
+
+/* CRC RevEng, an arbitrary-precision CRC calculator and algorithm finder
+ * Copyright (C) 2010, 2011, 2012, 2013, 2014, 2015 Gregory Cook
+ *
+ * This file is part of CRC RevEng.
+ *
+ * CRC RevEng is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * CRC RevEng is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with CRC RevEng. If not, see <http://www.gnu.org/licenses/>.
+ */
+
+/* 2014-01-14: added CRC-8/DVB-S2
+ * 2014-01-11: corrected CRC-40/GSM, added alias CRC-8/AES
+ * 2013-10-14: added CRC-13/BBC and six cdma2000 algorithms
+ * 2013-06-11: ensure BMP_BIT is an integer constant to compile presets
+ * 2013-01-20: big polynomials autogenerated, corrected CRC-82/DARC
+ * 2012-07-19: added CRC-8/EBU
+ * 2012-07-16: added CRC-15/MPT1327
+ * 2012-05-25: removed CRC-1/PARITY-EVEN, CRC-1/PARITY-ODD
+ * 2012-04-12: added model CRC-31/PHILIPS
+ * 2012-03-03: single-line Williams model string conversion
+ * 2012-02-20: corrected model CRC-6/DARC
+ * 2011-09-03: added mrev(), mnovel()
+ * 2011-08-28: added model CRC-64/XZ
+ * 2011-04-30: added models CRC-16/TMS37157 and CRC-A, and alias CRC-B
+ * 2011-02-10: made preset models ANSI C compliant
+ * 2011-01-17: fixed ANSI C warnings (except preset models)
+ * 2011-01-01: added mbynum(), mcount()
+ * 2010-12-26: renamed CRC RevEng
+ * 2010-12-18: minor change to mtostr() output format
+ * 2010-12-15: added mcmp(), mmatch()
+ * 2010-12-14: finished mbynam(), mnames(), mtostr()
+ * 2010-12-13: restarted with PCONST macros
+ * 2010-12-12: was having so much fun I didn't think to try compiling. :(
+ * 2010-12-12: started models.c
+ */
+
+#include <ctype.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include "reveng.h"
+
+/* Private declarations */
+
+struct mpreset {
+ const unsigned long width; /* width of CRC algorithm */
+ const bmp_t *const bspoly; /* polynomial with highest-order term removed. length determines CRC width */
+ const bmp_t *const binit; /* initial register value. length == poly.length */
+ const int flags; /* P_REFIN and P_REFOUT indicate reflected input/output */
+ const bmp_t *const bxorout; /* final register XOR mask. length == poly.length */
+ const bmp_t *const bcheck; /* optional check value, the CRC of the UTF-8 string "123456789" */
+ const char *const name; /* optional canonical name of the model */
+};
+
+struct malias {
+ const char *name;
+ const struct mpreset *model;
+ const int isprimry;
+};
+
+#ifdef PRESETS
+# if BMP_BIT < 32
+# error config.h: BMP_BIT must be an integer constant macro to compile presets
+# else /* BMP_BIT */
+
+/* Big polynomial constants. */
+
+/* Directives for relink.pl */
+/* CONSTANT b40 = (40, 0x0004820009) */
+/* CONSTANT b40a = (40, 0xffffffffff) */
+/* CONSTANT b40b = (40, 0xd4164fc646) */
+/* CONSTANT b64 = (64, 0x42f0e1eba9ea3693) */
+/* CONSTANT b64a = (64, 0x6c40df5f0b497347) */
+/* CONSTANT b64b = (64, 0xffffffffffffffff) */
+/* CONSTANT b64c = (64, 0x62ec59e3f1a4f00a) */
+/* CONSTANT b64d = (64, 0x995dc9bbdf1939fa) */
+/* CONSTANT b82 = (82, 0x0308c0111011401440411) */
+/* CONSTANT b82a = (82, 0x09ea83f625023801fd612) */
+
+/* The next section was generated by relink.pl from the directives above. */
+
+/* DO NOT EDIT the section below, INCLUDING the next comment. */
+/* BEGIN AUTO-GENERATED CONSTANTS */
+# if BMP_BIT >= 40
+static const bmp_t b40[] = {
+ BMP_C(0x0004820009) << (BMP_BIT - 40),
+};
+static const bmp_t b40a[] = {
+ BMP_C(0xffffffffff) << (BMP_BIT - 40),
+};
+static const bmp_t b40b[] = {
+ BMP_C(0xd4164fc646) << (BMP_BIT - 40),
+};
+# else /* BMP_BIT */
+static const bmp_t b40[] = {
+ BMP_C(0x00048200) << (BMP_BIT - 32) | BMP_C(0x04) >> (39 - BMP_BIT),
+ BMP_C(0x09) << (BMP_BIT * 2 - 40),
+};
+static const bmp_t b40a[] = {
+ BMP_C(0xffffffff) << (BMP_BIT - 32) | BMP_C(0x7f) >> (39 - BMP_BIT),
+ BMP_C(0xff) << (BMP_BIT * 2 - 40),
+};
+static const bmp_t b40b[] = {
+ BMP_C(0xd4164fc6) << (BMP_BIT - 32) | BMP_C(0x23) >> (39 - BMP_BIT),
+ BMP_C(0x46) << (BMP_BIT * 2 - 40),
+};
+# endif /* BMP_BIT */
+
+# if BMP_BIT >= 64
+static const bmp_t b64[] = {
+ BMP_C(0x42f0e1eba9ea3693) << (BMP_BIT - 64),
+};
+static const bmp_t b64a[] = {
+ BMP_C(0x6c40df5f0b497347) << (BMP_BIT - 64),
+};
+static const bmp_t b64b[] = {
+ BMP_C(0xffffffffffffffff) << (BMP_BIT - 64),
+};
+static const bmp_t b64c[] = {
+ BMP_C(0x62ec59e3f1a4f00a) << (BMP_BIT - 64),
+};
+static const bmp_t b64d[] = {
+ BMP_C(0x995dc9bbdf1939fa) << (BMP_BIT - 64),
+};
+# else /* BMP_BIT */
+static const bmp_t b64[] = {
+ BMP_C(0x42f0e1eb) << (BMP_BIT - 32) | BMP_C(0x54f51b49) >> (63 - BMP_BIT),
+ BMP_C(0xa9ea3693) << (BMP_BIT * 2 - 64),
+};
+static const bmp_t b64a[] = {
+ BMP_C(0x6c40df5f) << (BMP_BIT - 32) | BMP_C(0x05a4b9a3) >> (63 - BMP_BIT),
+ BMP_C(0x0b497347) << (BMP_BIT * 2 - 64),
+};
+static const bmp_t b64b[] = {
+ BMP_C(0xffffffff) << (BMP_BIT - 32) | BMP_C(0x7fffffff) >> (63 - BMP_BIT),
+ BMP_C(0xffffffff) << (BMP_BIT * 2 - 64),
+};
+static const bmp_t b64c[] = {
+ BMP_C(0x62ec59e3) << (BMP_BIT - 32) | BMP_C(0x78d27805) >> (63 - BMP_BIT),
+ BMP_C(0xf1a4f00a) << (BMP_BIT * 2 - 64),
+};
+static const bmp_t b64d[] = {
+ BMP_C(0x995dc9bb) << (BMP_BIT - 32) | BMP_C(0x6f8c9cfd) >> (63 - BMP_BIT),
+ BMP_C(0xdf1939fa) << (BMP_BIT * 2 - 64),
+};
+# endif /* BMP_BIT */
+
+# if BMP_BIT >= 82
+static const bmp_t b82[] = {
+ BMP_C(0x0308c0111011401440411) << (BMP_BIT - 82),
+};
+static const bmp_t b82a[] = {
+ BMP_C(0x09ea83f625023801fd612) << (BMP_BIT - 82),
+};
+# elif BMP_BIT >= 41
+static const bmp_t b82[] = {
+ BMP_C(0x01846008880) << (BMP_BIT - 41) | BMP_C(0x08a00a20208) >> (81 - BMP_BIT),
+ BMP_C(0x11401440411) << (BMP_BIT * 2 - 82),
+};
+static const bmp_t b82a[] = {
+ BMP_C(0x04f541fb128) << (BMP_BIT - 41) | BMP_C(0x011c00feb09) >> (81 - BMP_BIT),
+ BMP_C(0x023801fd612) << (BMP_BIT * 2 - 82),
+};
+# else /* BMP_BIT */
+static const bmp_t b82[] = {
+ BMP_C(0x0c230044) << (BMP_BIT - 32) | BMP_C(0x040) >> (40 - BMP_BIT),
+ BMP_C(0x40450051) << (BMP_BIT * 2 - 64) | BMP_C(0x00104) >> (80 - BMP_BIT * 2),
+ BMP_C(0x00411) << (BMP_BIT * 3 - 82),
+};
+static const bmp_t b82a[] = {
+ BMP_C(0x27aa0fd8) << (BMP_BIT - 32) | BMP_C(0x094) >> (40 - BMP_BIT),
+ BMP_C(0x9408e007) << (BMP_BIT * 2 - 64) | BMP_C(0x0f584) >> (80 - BMP_BIT * 2),
+ BMP_C(0x3d612) << (BMP_BIT * 3 - 82),
+};
+# endif /* BMP_BIT */
+
+/* END AUTO-GENERATED CONSTANTS */
+/* DO NOT EDIT the section above, INCLUDING the previous comment. */
+
+/* Array of the polynomial bitmaps used in the model table. */
+static const bmp_t b32[] = {
+ BMP_C(0x00000000) << (BMP_BIT - 32), /* 0 -- 5, 00 */
+ BMP_C(0x000000af) << (BMP_BIT - 32), /* 1 -- 32,000000af */
+ BMP_C(0x00010000) << (BMP_BIT - 32), /* 2 -- 16, 0001 */
+ BMP_C(0x00020000) << (BMP_BIT - 32), /* 3 -- 15, 0001 */
+ BMP_C(0x007e0000) << (BMP_BIT - 32), /* 4 -- 16, 007e */
+ BMP_C(0x007f0000) << (BMP_BIT - 32), /* 5 -- 16, 007f */
+ BMP_C(0x03400000) << (BMP_BIT - 32), /* 6 -- 11, 01a */
+ BMP_C(0x0376e6e7) << (BMP_BIT - 32), /* 7 -- 32,0376e6e7 */
+ BMP_C(0x04c11db7) << (BMP_BIT - 32), /* 8 -- 32,04c11db7 */
+ BMP_C(0x05890000) << (BMP_BIT - 32), /* 9 -- 16, 0589 */
+ BMP_C(0x07000000) << (BMP_BIT - 32), /* 10 -- 8, 07 */
+ BMP_C(0x09823b6e) << (BMP_BIT - 32), /* 11 -- 31,04c11db7 */
+ BMP_C(0x0b3c0000) << (BMP_BIT - 32), /* 12 -- 15, 059e */
+ BMP_C(0x0c000000) << (BMP_BIT - 32), /* 13 -- 6, 03 */
+ BMP_C(0x0fb30000) << (BMP_BIT - 32), /* 14 -- 16, 0fb3 */
+ BMP_C(0x10210000) << (BMP_BIT - 32), /* 15 -- 16, 1021 */
+ BMP_C(0x12000000) << (BMP_BIT - 32), /* 16 -- 7, 09 */
+ BMP_C(0x15000000) << (BMP_BIT - 32), /* 17 -- 8, 15 */
+ BMP_C(0x18000000) << (BMP_BIT - 32), /* 18 -- 6, 06 */
+ BMP_C(0x19d3c8d8) << (BMP_BIT - 32), /* 19 -- 31,0ce9e46c */
+ BMP_C(0x1c000000) << (BMP_BIT - 32), /* 20 -- 6, 07 */
+ BMP_C(0x1d000000) << (BMP_BIT - 32), /* 21 -- 8, 1d */
+ BMP_C(0x1d0f0000) << (BMP_BIT - 32), /* 22 -- 16, 1d0f */
+ BMP_C(0x1edc6f41) << (BMP_BIT - 32), /* 23 -- 32,1edc6f41 */
+ BMP_C(0x1f23b800) << (BMP_BIT - 32), /* 24 -- 24, 1f23b8 */
+ BMP_C(0x20140000) << (BMP_BIT - 32), /* 25 -- 14, 0805 */
+ BMP_C(0x20b40000) << (BMP_BIT - 32), /* 26 -- 14, 082d */
+ BMP_C(0x21890000) << (BMP_BIT - 32), /* 27 -- 16, 2189 */
+ BMP_C(0x21cf0200) << (BMP_BIT - 32), /* 28 -- 24, 21cf02 */
+ BMP_C(0x25000000) << (BMP_BIT - 32), /* 29 -- 8, 25 */
+ BMP_C(0x26b10000) << (BMP_BIT - 32), /* 30 -- 16, 26b1 */
+ BMP_C(0x27d00000) << (BMP_BIT - 32), /* 31 -- 13, 04fa */
+ BMP_C(0x28000000) << (BMP_BIT - 32), /* 32 -- 5, 05 */
+ BMP_C(0x29b10000) << (BMP_BIT - 32), /* 33 -- 16, 29b1 */
+ BMP_C(0x30000000) << (BMP_BIT - 32), /* 34 -- 4, 3 */
+ BMP_C(0x3010bf7f) << (BMP_BIT - 32), /* 35 -- 32,3010bf7f */
+ BMP_C(0x31000000) << (BMP_BIT - 32), /* 36 -- 8, 31 */
+ BMP_C(0x31c30000) << (BMP_BIT - 32), /* 37 -- 16, 31c3 */
+ BMP_C(0x34000000) << (BMP_BIT - 32), /* 38 -- 6, 0d */
+ BMP_C(0x340bc6d9) << (BMP_BIT - 32), /* 39 -- 32,340bc6d9 */
+ BMP_C(0x38000000) << (BMP_BIT - 32), /* 40 -- 5, 07 */
+ BMP_C(0x39000000) << (BMP_BIT - 32), /* 41 -- 8, 39 */
+ BMP_C(0x3d650000) << (BMP_BIT - 32), /* 42 -- 16, 3d65 */
+ BMP_C(0x44c20000) << (BMP_BIT - 32), /* 43 -- 16, 44c2 */
+ BMP_C(0x48000000) << (BMP_BIT - 32), /* 44 -- 5, 09 */
+ BMP_C(0x4acc0000) << (BMP_BIT - 32), /* 45 -- 15, 2566 */
+ BMP_C(0x4b370000) << (BMP_BIT - 32), /* 46 -- 16, 4b37 */
+ BMP_C(0x4c060000) << (BMP_BIT - 32), /* 47 -- 16, 4c06 */
+ BMP_C(0x55000000) << (BMP_BIT - 32), /* 48 -- 8, 55 */
+ BMP_C(0x5d6dcb00) << (BMP_BIT - 32), /* 49 -- 24, 5d6dcb */
+ BMP_C(0x60000000) << (BMP_BIT - 32), /* 50 -- 3, 3 */
+ BMP_C(0x63d00000) << (BMP_BIT - 32), /* 51 -- 16, 63d0 */
+ BMP_C(0x64000000) << (BMP_BIT - 32), /* 52 -- 6, 19 */
+ BMP_C(0x66400000) << (BMP_BIT - 32), /* 53 -- 10, 199 */
+ BMP_C(0x6f910000) << (BMP_BIT - 32), /* 54 -- 16, 6f91 */
+ BMP_C(0x70000000) << (BMP_BIT - 32), /* 55 -- 4, 7 */
+ BMP_C(0x70a00000) << (BMP_BIT - 32), /* 56 -- 11, 385 */
+ BMP_C(0x765e7680) << (BMP_BIT - 32), /* 57 -- 32,765e7680 */
+ BMP_C(0x7979bd00) << (BMP_BIT - 32), /* 58 -- 24, 7979bd */
+ BMP_C(0x7e000000) << (BMP_BIT - 32), /* 59 -- 8, 7e */
+ BMP_C(0x80050000) << (BMP_BIT - 32), /* 60 -- 16, 8005 */
+ BMP_C(0x800d0000) << (BMP_BIT - 32), /* 61 -- 16, 800d */
+ BMP_C(0x80f00000) << (BMP_BIT - 32), /* 62 -- 12, 80f */
+ BMP_C(0x814141ab) << (BMP_BIT - 32), /* 63 -- 32,814141ab */
+ BMP_C(0x864cfb00) << (BMP_BIT - 32), /* 64 -- 24, 864cfb */
+ BMP_C(0x87315576) << (BMP_BIT - 32), /* 65 -- 32,87315576 */
+ BMP_C(0x89ec0000) << (BMP_BIT - 32), /* 66 -- 16, 89ec */
+ BMP_C(0x8b320000) << (BMP_BIT - 32), /* 67 -- 15, 4599 */
+ BMP_C(0x8bb70000) << (BMP_BIT - 32), /* 68 -- 16, 8bb7 */
+ BMP_C(0x8cc00000) << (BMP_BIT - 32), /* 69 -- 10, 233 */
+ BMP_C(0x906e0000) << (BMP_BIT - 32), /* 70 -- 16, 906e */
+ BMP_C(0x97000000) << (BMP_BIT - 32), /* 71 -- 8, 97 */
+ BMP_C(0x98000000) << (BMP_BIT - 32), /* 72 -- 6, 26 */
+ BMP_C(0x9b000000) << (BMP_BIT - 32), /* 73 -- 8, 9b */
+ BMP_C(0x9c000000) << (BMP_BIT - 32), /* 74 -- 6, 27 */
+ BMP_C(0x9e000000) << (BMP_BIT - 32), /* 75 -- 7, 4f */
+ BMP_C(0x9ecf0000) << (BMP_BIT - 32), /* 76 -- 16, 9ecf */
+ BMP_C(0xa0970000) << (BMP_BIT - 32), /* 77 -- 16, a097 */
+ BMP_C(0xa1000000) << (BMP_BIT - 32), /* 78 -- 8, a1 */
+ BMP_C(0xa6000000) << (BMP_BIT - 32), /* 79 -- 7, 53 */
+ BMP_C(0xa8000000) << (BMP_BIT - 32), /* 80 -- 5, 15 */
+ BMP_C(0xa833982b) << (BMP_BIT - 32), /* 81 -- 32,a833982b */
+ BMP_C(0xabcdef00) << (BMP_BIT - 32), /* 82 -- 24, abcdef */
+ BMP_C(0xb2aa0000) << (BMP_BIT - 32), /* 83 -- 16, b2aa */
+ BMP_C(0xb4600000) << (BMP_BIT - 32), /* 84 -- 11, 5a3 */
+ BMP_C(0xb4c80000) << (BMP_BIT - 32), /* 85 -- 16, b4c8 */
+ BMP_C(0xb704ce00) << (BMP_BIT - 32), /* 86 -- 24, b704ce */
+ BMP_C(0xbb3d0000) << (BMP_BIT - 32), /* 87 -- 16, bb3d */
+ BMP_C(0xbc000000) << (BMP_BIT - 32), /* 88 -- 8, bc */
+ BMP_C(0xbd0be338) << (BMP_BIT - 32), /* 89 -- 32,bd0be338 */
+ BMP_C(0xbf050000) << (BMP_BIT - 32), /* 90 -- 16, bf05 */
+ BMP_C(0xc0000000) << (BMP_BIT - 32), /* 91 -- 3, 6 */
+ BMP_C(0xc2b70000) << (BMP_BIT - 32), /* 92 -- 16, c2b7 */
+ BMP_C(0xc6c60000) << (BMP_BIT - 32), /* 93 -- 16, c6c6 */
+ BMP_C(0xc8000000) << (BMP_BIT - 32), /* 94 -- 5, 19 */
+ BMP_C(0xc8670000) << (BMP_BIT - 32), /* 95 -- 16, c867 */
+ BMP_C(0xcbf43926) << (BMP_BIT - 32), /* 96 -- 32,cbf43926 */
+ BMP_C(0xd0000000) << (BMP_BIT - 32), /* 97 -- 8, d0 */
+ BMP_C(0xd02a0000) << (BMP_BIT - 32), /* 98 -- 15, 6815 */
+ BMP_C(0xd0db0000) << (BMP_BIT - 32), /* 99 -- 16, d0db */
+ BMP_C(0xd4d00000) << (BMP_BIT - 32), /* 100 -- 12, d4d */
+ BMP_C(0xd5000000) << (BMP_BIT - 32), /* 101 -- 8, d5 */
+ BMP_C(0xd64e0000) << (BMP_BIT - 32), /* 102 -- 16, d64e */
+ BMP_C(0xda000000) << (BMP_BIT - 32), /* 103 -- 8, da */
+ BMP_C(0xdaf00000) << (BMP_BIT - 32), /* 104 -- 12, daf */
+ BMP_C(0xe0000000) << (BMP_BIT - 32), /* 105 -- 3, 7 */
+ BMP_C(0xe3069283) << (BMP_BIT - 32), /* 106 -- 32,e3069283 */
+ BMP_C(0xe5cc0000) << (BMP_BIT - 32), /* 107 -- 16, e5cc */
+ BMP_C(0xe7a80000) << (BMP_BIT - 32), /* 108 -- 13, 1cf5 */
+ BMP_C(0xea000000) << (BMP_BIT - 32), /* 109 -- 7, 75 */
+ BMP_C(0xea820000) << (BMP_BIT - 32), /* 110 -- 16, ea82 */
+ BMP_C(0xec000000) << (BMP_BIT - 32), /* 111 -- 6, 3b */
+ BMP_C(0xf1300000) << (BMP_BIT - 32), /* 112 -- 12, f13 */
+ BMP_C(0xf4000000) << (BMP_BIT - 32), /* 113 -- 8, f4 */
+ BMP_C(0xf5b00000) << (BMP_BIT - 32), /* 114 -- 12, f5b */
+ BMP_C(0xf6400000) << (BMP_BIT - 32), /* 115 -- 10, 3d9 */
+ BMP_C(0xf8000000) << (BMP_BIT - 32), /* 116 -- 5, 1f */
+ BMP_C(0xfc000000) << (BMP_BIT - 32), /* 117 -- 6, 3f */
+ BMP_C(0xfc891918) << (BMP_BIT - 32), /* 118 -- 32,fc891918 */
+ BMP_C(0xfd000000) << (BMP_BIT - 32), /* 119 -- 8, fd */
+ BMP_C(0xfe000000) << (BMP_BIT - 32), /* 120 -- 7, 7f */
+ BMP_C(0xfedcba00) << (BMP_BIT - 32), /* 121 -- 24, fedcba */
+ BMP_C(0xfee80000) << (BMP_BIT - 32), /* 122 -- 16, fee8 */
+ BMP_C(0xff000000) << (BMP_BIT - 32), /* 123 -- 8, ff */
+ BMP_C(0xffc00000) << (BMP_BIT - 32), /* 124 -- 10, 3ff */
+ BMP_C(0xfff00000) << (BMP_BIT - 32), /* 125 -- 12, fff */
+ BMP_C(0xffff0000) << (BMP_BIT - 32), /* 126 -- 16, ffff */
+ BMP_C(0xfffffffe) << (BMP_BIT - 32), /* 127 -- 31,7fffffff */
+ BMP_C(0xffffffff) << (BMP_BIT - 32), /* 128 -- 32,ffffffff */
+};
+
+/* Table of preset CRC models.
+ * Sorted by left-justified polynomial for bsearch().
+ */
+static const struct mpreset models[] = {
+ {32UL, b32+ 1, 0, P_BE, 0, b32+ 89, "XFER" }, /* 0 */
+ {40UL, b40, 0, P_BE, b40a, b40b, "CRC-40/GSM" }, /* 1 */
+ {32UL, b32+ 8, 0, P_BE, b32+128, b32+ 57, "CRC-32/POSIX" }, /* 2 */
+ {32UL, b32+ 8, b32+128, P_BE, 0, b32+ 7, "CRC-32/MPEG-2" }, /* 3 */
+ {32UL, b32+ 8, b32+128, P_BE, b32+128, b32+118, "CRC-32/BZIP2" }, /* 4 */
+ {32UL, b32+ 8, b32+128, P_LE, 0, b32+ 39, "JAMCRC" }, /* 5 */
+ {32UL, b32+ 8, b32+128, P_LE, b32+128, b32+ 96, "CRC-32" }, /* 6 */
+ {16UL, b32+ 9, 0, P_BE, 0, b32+ 5, "CRC-16/DECT-X" }, /* 7 */
+ {16UL, b32+ 9, 0, P_BE, b32+ 2, b32+ 4, "CRC-16/DECT-R" }, /* 8 */
+ { 8UL, b32+ 10, 0, P_BE, 0, b32+113, "CRC-8" }, /* 9 */
+ { 8UL, b32+ 10, 0, P_BE, b32+ 48, b32+ 78, "CRC-8/ITU" }, /* 10 */
+ { 8UL, b32+ 10, b32+123, P_LE, 0, b32+ 97, "CRC-8/ROHC" }, /* 11 */
+ {31UL, b32+ 11, b32+127, P_BE, b32+127, b32+ 19, "CRC-31/PHILIPS" }, /* 12 */
+ { 6UL, b32+ 13, 0, P_LE, 0, b32+ 18, "CRC-6/ITU" }, /* 13 */
+ {82UL, b82, 0, P_LE, 0, b82a, "CRC-82/DARC" }, /* 14 */
+ {16UL, b32+ 15, 0, P_BE, 0, b32+ 37, "XMODEM" }, /* 15 */
+ {16UL, b32+ 15, 0, P_LE, 0, b32+ 27, "KERMIT" }, /* 16 */
+ {16UL, b32+ 15, b32+ 22, P_BE, 0, b32+107, "CRC-16/AUG-CCITT" }, /* 17 */
+ {16UL, b32+ 15, b32+ 66, P_LE, 0, b32+ 30, "CRC-16/TMS37157" }, /* 18 */
+ {16UL, b32+ 15, b32+ 83, P_LE, 0, b32+ 51, "CRC-16/RIELLO" }, /* 19 */
+ {16UL, b32+ 15, b32+ 93, P_LE, 0, b32+ 90, "CRC-A" }, /* 20 */
+ {16UL, b32+ 15, b32+126, P_BE, 0, b32+ 33, "CRC-16/CCITT-FALSE"}, /* 21 */
+ {16UL, b32+ 15, b32+126, P_BE, b32+126, b32+102, "CRC-16/GENIBUS" }, /* 22 */
+ {16UL, b32+ 15, b32+126, P_LE, 0, b32+ 54, "CRC-16/MCRF4XX" }, /* 23 */
+ {16UL, b32+ 15, b32+126, P_LE, b32+126, b32+ 70, "X-25" }, /* 24 */
+ { 7UL, b32+ 16, 0, P_BE, 0, b32+109, "CRC-7" }, /* 25 */
+ { 6UL, b32+ 20, b32+117, P_BE, 0, b32+111, "CRC-6/CDMA2000-B" }, /* 26 */
+ { 8UL, b32+ 21, b32+119, P_BE, 0, b32+ 59, "CRC-8/I-CODE" }, /* 27 */
+ { 8UL, b32+ 21, b32+123, P_LE, 0, b32+ 71, "CRC-8/EBU" }, /* 28 */
+ {32UL, b32+ 23, b32+128, P_LE, b32+128, b32+106, "CRC-32C" }, /* 29 */
+ {14UL, b32+ 25, 0, P_LE, 0, b32+ 26, "CRC-14/DARC" }, /* 30 */
+ { 5UL, b32+ 32, b32+116, P_LE, b32+116, b32+ 94, "CRC-5/USB" }, /* 31 */
+ { 4UL, b32+ 34, 0, P_LE, 0, b32+ 55, "CRC-4/ITU" }, /* 32 */
+ { 8UL, b32+ 36, 0, P_LE, 0, b32+ 78, "CRC-8/MAXIM" }, /* 33 */
+ { 8UL, b32+ 41, 0, P_LE, 0, b32+ 17, "CRC-8/DARC" }, /* 34 */
+ {16UL, b32+ 42, 0, P_BE, b32+126, b32+ 92, "CRC-16/EN-13757" }, /* 35 */
+ {16UL, b32+ 42, 0, P_LE, b32+126, b32+110, "CRC-16/DNP" }, /* 36 */
+ {64UL, b64, 0, P_BE, 0, b64a, "CRC-64" }, /* 37 */
+ {64UL, b64, b64b, P_BE, b64b, b64c, "CRC-64/WE" }, /* 38 */
+ {64UL, b64, b64b, P_LE, b64b, b64d, "CRC-64/XZ" }, /* 39 */
+ { 5UL, b32+ 44, b32+ 44, P_BE, 0, b32+ 0, "CRC-5/EPC" }, /* 40 */
+ {24UL, b32+ 49, b32+ 82, P_BE, 0, b32+ 24, "CRC-24/FLEXRAY-B" }, /* 41 */
+ {24UL, b32+ 49, b32+121, P_BE, 0, b32+ 58, "CRC-24/FLEXRAY-A" }, /* 42 */
+ { 3UL, b32+ 50, b32+105, P_LE, 0, b32+ 91, "CRC-3/ROHC" }, /* 43 */
+ { 6UL, b32+ 52, 0, P_LE, 0, b32+ 72, "CRC-6/DARC" }, /* 44 */
+ {11UL, b32+ 56, b32+ 6, P_BE, 0, b32+ 84, "CRC-11" }, /* 45 */
+ {16UL, b32+ 60, 0, P_BE, 0, b32+122, "CRC-16/BUYPASS" }, /* 46 */
+ {16UL, b32+ 60, 0, P_LE, 0, b32+ 87, "ARC" }, /* 47 */
+ {16UL, b32+ 60, 0, P_LE, b32+126, b32+ 43, "CRC-16/MAXIM" }, /* 48 */
+ {16UL, b32+ 60, b32+ 61, P_BE, 0, b32+ 76, "CRC-16/DDS-110" }, /* 49 */
+ {16UL, b32+ 60, b32+126, P_LE, 0, b32+ 46, "MODBUS" }, /* 50 */
+ {16UL, b32+ 60, b32+126, P_LE, b32+126, b32+ 85, "CRC-16/USB" }, /* 51 */
+ {12UL, b32+ 62, 0, P_BE, 0, b32+114, "CRC-12/DECT" }, /* 52 */
+ {12UL, b32+ 62, 0, P_BELE, 0, b32+104, "CRC-12/3GPP" }, /* 53 */
+ {32UL, b32+ 63, 0, P_BE, 0, b32+ 35, "CRC-32Q" }, /* 54 */
+ {24UL, b32+ 64, b32+ 86, P_BE, 0, b32+ 28, "CRC-24" }, /* 55 */
+ {15UL, b32+ 67, 0, P_BE, 0, b32+ 12, "CRC-15" }, /* 56 */
+ {16UL, b32+ 68, 0, P_BE, 0, b32+ 99, "CRC-16/T10-DIF" }, /* 57 */
+ {10UL, b32+ 69, 0, P_BE, 0, b32+ 53, "CRC-10" }, /* 58 */
+ { 8UL, b32+ 73, 0, P_LE, 0, b32+ 29, "CRC-8/WCDMA" }, /* 59 */
+ { 8UL, b32+ 73, b32+123, P_BE, 0, b32+103, "CRC-8/CDMA2000" }, /* 60 */
+ { 6UL, b32+ 74, b32+117, P_BE, 0, b32+ 38, "CRC-6/CDMA2000-A" }, /* 61 */
+ { 7UL, b32+ 75, b32+120, P_LE, 0, b32+ 79, "CRC-7/ROHC" }, /* 62 */
+ {16UL, b32+ 77, 0, P_BE, 0, b32+ 14, "CRC-16/TELEDISK" }, /* 63 */
+ { 5UL, b32+ 80, 0, P_LE, 0, b32+ 40, "CRC-5/ITU" }, /* 64 */
+ {32UL, b32+ 81, b32+128, P_LE, b32+128, b32+ 65, "CRC-32D" }, /* 65 */
+ {16UL, b32+ 95, b32+126, P_BE, 0, b32+ 47, "CRC-16/CDMA2000" }, /* 66 */
+ {15UL, b32+ 98, 0, P_BE, b32+ 3, b32+ 45, "CRC-15/MPT1327" }, /* 67 */
+ { 8UL, b32+101, 0, P_BE, 0, b32+ 88, "CRC-8/DVB-S2" }, /* 68 */
+ {13UL, b32+108, 0, P_BE, 0, b32+ 31, "CRC-13/BBC" }, /* 69 */
+ {12UL, b32+112, b32+125, P_BE, 0, b32+100, "CRC-12/CDMA2000" }, /* 70 */
+ {10UL, b32+115, b32+124, P_BE, 0, b32+ 69, "CRC-10/CDMA2000" }, /* 71 */
+};
+# define NPRESETS 72
+
+/* List of names with pointers to models, pre-sorted for use with bsearch() */
+static const struct malias aliases[] = {
+ {"ARC", models+47, 1}, /* 0 */
+ {"B-CRC-32", models+ 4, 0}, /* 1 */
+ {"CKSUM", models+ 2, 0}, /* 2 */
+ {"CRC-10", models+58, 1}, /* 3 */
+ {"CRC-10/CDMA2000", models+71, 1}, /* 4 */
+ {"CRC-11", models+45, 1}, /* 5 */
+ {"CRC-12/3GPP", models+53, 1}, /* 6 */
+ {"CRC-12/CDMA2000", models+70, 1}, /* 7 */
+ {"CRC-12/DECT", models+52, 1}, /* 8 */
+ {"CRC-13/BBC", models+69, 1}, /* 9 */
+ {"CRC-14/DARC", models+30, 1}, /* 10 */
+ {"CRC-15", models+56, 1}, /* 11 */
+ {"CRC-15/MPT1327", models+67, 1}, /* 12 */
+ {"CRC-16", models+47, 0}, /* 13 */
+ {"CRC-16/ACORN", models+15, 0}, /* 14 */
+ {"CRC-16/ARC", models+47, 0}, /* 15 */
+ {"CRC-16/AUG-CCITT", models+17, 1}, /* 16 */
+ {"CRC-16/BUYPASS", models+46, 1}, /* 17 */
+ {"CRC-16/CCITT", models+16, 0}, /* 18 */
+ {"CRC-16/CCITT-FALSE", models+21, 1}, /* 19 */
+ {"CRC-16/CCITT-TRUE", models+16, 0}, /* 20 */
+ {"CRC-16/CDMA2000", models+66, 1}, /* 21 */
+ {"CRC-16/DARC", models+22, 0}, /* 22 */
+ {"CRC-16/DDS-110", models+49, 1}, /* 23 */
+ {"CRC-16/DECT-R", models+ 8, 1}, /* 24 */
+ {"CRC-16/DECT-X", models+ 7, 1}, /* 25 */
+ {"CRC-16/DNP", models+36, 1}, /* 26 */
+ {"CRC-16/EN-13757", models+35, 1}, /* 27 */
+ {"CRC-16/EPC", models+22, 0}, /* 28 */
+ {"CRC-16/GENIBUS", models+22, 1}, /* 29 */
+ {"CRC-16/I-CODE", models+22, 0}, /* 30 */
+ {"CRC-16/IBM-SDLC", models+24, 0}, /* 31 */
+ {"CRC-16/ISO-HDLC", models+24, 0}, /* 32 */
+ {"CRC-16/LHA", models+47, 0}, /* 33 */
+ {"CRC-16/MAXIM", models+48, 1}, /* 34 */
+ {"CRC-16/MCRF4XX", models+23, 1}, /* 35 */
+ {"CRC-16/RIELLO", models+19, 1}, /* 36 */
+ {"CRC-16/SPI-FUJITSU", models+17, 0}, /* 37 */
+ {"CRC-16/T10-DIF", models+57, 1}, /* 38 */
+ {"CRC-16/TELEDISK", models+63, 1}, /* 39 */
+ {"CRC-16/TMS37157", models+18, 1}, /* 40 */
+ {"CRC-16/USB", models+51, 1}, /* 41 */
+ {"CRC-16/VERIFONE", models+46, 0}, /* 42 */
+ {"CRC-24", models+55, 1}, /* 43 */
+ {"CRC-24/FLEXRAY-A", models+42, 1}, /* 44 */
+ {"CRC-24/FLEXRAY-B", models+41, 1}, /* 45 */
+ {"CRC-24/OPENPGP", models+55, 0}, /* 46 */
+ {"CRC-3/ROHC", models+43, 1}, /* 47 */
+ {"CRC-31/PHILIPS", models+12, 1}, /* 48 */
+ {"CRC-32", models+ 6, 1}, /* 49 */
+ {"CRC-32/AAL5", models+ 4, 0}, /* 50 */
+ {"CRC-32/ADCCP", models+ 6, 0}, /* 51 */
+ {"CRC-32/BZIP2", models+ 4, 1}, /* 52 */
+ {"CRC-32/CASTAGNOLI", models+29, 0}, /* 53 */
+ {"CRC-32/DECT-B", models+ 4, 0}, /* 54 */
+ {"CRC-32/ISCSI", models+29, 0}, /* 55 */
+ {"CRC-32/MPEG-2", models+ 3, 1}, /* 56 */
+ {"CRC-32/POSIX", models+ 2, 1}, /* 57 */
+ {"CRC-32C", models+29, 1}, /* 58 */
+ {"CRC-32D", models+65, 1}, /* 59 */
+ {"CRC-32Q", models+54, 1}, /* 60 */
+ {"CRC-4/ITU", models+32, 1}, /* 61 */
+ {"CRC-40/GSM", models+ 1, 1}, /* 62 */
+ {"CRC-5/EPC", models+40, 1}, /* 63 */
+ {"CRC-5/ITU", models+64, 1}, /* 64 */
+ {"CRC-5/USB", models+31, 1}, /* 65 */
+ {"CRC-6/CDMA2000-A", models+61, 1}, /* 66 */
+ {"CRC-6/CDMA2000-B", models+26, 1}, /* 67 */
+ {"CRC-6/DARC", models+44, 1}, /* 68 */
+ {"CRC-6/ITU", models+13, 1}, /* 69 */
+ {"CRC-64", models+37, 1}, /* 70 */
+ {"CRC-64/WE", models+38, 1}, /* 71 */
+ {"CRC-64/XZ", models+39, 1}, /* 72 */
+ {"CRC-7", models+25, 1}, /* 73 */
+ {"CRC-7/ROHC", models+62, 1}, /* 74 */
+ {"CRC-8", models+ 9, 1}, /* 75 */
+ {"CRC-8/AES", models+28, 0}, /* 76 */
+ {"CRC-8/CDMA2000", models+60, 1}, /* 77 */
+ {"CRC-8/DARC", models+34, 1}, /* 78 */
+ {"CRC-8/DVB-S2", models+68, 1}, /* 79 */
+ {"CRC-8/EBU", models+28, 1}, /* 80 */
+ {"CRC-8/I-CODE", models+27, 1}, /* 81 */
+ {"CRC-8/ITU", models+10, 1}, /* 82 */
+ {"CRC-8/MAXIM", models+33, 1}, /* 83 */
+ {"CRC-8/ROHC", models+11, 1}, /* 84 */
+ {"CRC-8/WCDMA", models+59, 1}, /* 85 */
+ {"CRC-82/DARC", models+14, 1}, /* 86 */
+ {"CRC-A", models+20, 1}, /* 87 */
+ {"CRC-B", models+24, 0}, /* 88 */
+ {"CRC-CCITT", models+16, 0}, /* 89 */
+ {"CRC-IBM", models+47, 0}, /* 90 */
+ {"DOW-CRC", models+33, 0}, /* 91 */
+ {"JAMCRC", models+ 5, 1}, /* 92 */
+ {"KERMIT", models+16, 1}, /* 93 */
+ {"MODBUS", models+50, 1}, /* 94 */
+ {"PKZIP", models+ 6, 0}, /* 95 */
+ {"R-CRC-16", models+ 8, 0}, /* 96 */
+ {"X-25", models+24, 1}, /* 97 */
+ {"X-CRC-12", models+52, 0}, /* 98 */
+ {"X-CRC-16", models+ 7, 0}, /* 99 */
+ {"XFER", models+ 0, 1}, /* 100 */
+ {"XMODEM", models+15, 1}, /* 101 */
+ {"ZMODEM", models+15, 0}, /* 102 */
+ {NULL, NULL, 0}, /* terminating entry */
+};
+# define NALIASES 103
+
+# endif /* BMP_BIT */
+#else /* PRESETS */
+
+static const struct mpreset models[] = {
+ { 0UL, 0, 0, P_BE, 0, 0, NULL }, /* terminating entry */
+};
+# define NPRESETS 0
+
+static const struct malias aliases[] = {
+ {NULL, NULL, 0}, /* terminating entry */
+};
+# define NALIASES 0
+
+#endif /* PRESETS */
+
+static const poly_t pzero = PZERO;
+
+static int acmp(const struct malias *, const struct malias *);
+static void munpack(model_t *, const struct mpreset *);
+
+/* copy a parameter of a preset into a model */
+#define MUNPACK(parm) \
+ praloc(&dest->parm, (src->b##parm ? src->width : 0UL)); \
+ for(iter=0UL, idx=0UL; iter < dest->parm.length; iter += BMP_BIT, ++idx)\
+ dest->parm.bitmap[idx] = src->b##parm[idx];
+
+/* Definitions */
+
+void
+mcpy(model_t *dest, const model_t *src) {
+ /* Copies the parameters of src to dest.
+ * dest must be an initialised model.
+ */
+ if(!dest || !src) return;
+ pcpy(&dest->spoly, src->spoly);
+ pcpy(&dest->init, src->init);
+ pcpy(&dest->xorout, src->xorout);
+ pcpy(&dest->check, src->check);
+ dest->flags = src->flags;
+ /* link to the name as it is static */
+ dest->name = src->name;
+}
+
+void
+mfree(model_t *model) {
+ /* Frees the parameters of model. */
+ if(!model) return;
+ pfree(&model->spoly);
+ pfree(&model->init);
+ pfree(&model->xorout);
+ pfree(&model->check);
+ /* not name as it is static */
+ /* not model either, it might point to an array! */
+}
+
+int
+mcmp(const model_t *a, const model_t *b) {
+ /* Compares a and b for identical effect, i.e. disregarding
+ * trailing zeroes in parameter polys.
+ * Intended for bsearch() to find a matching model in models[].
+ */
+ int result;
+ if(!a || !b) return(!b - !a);
+ if((result = psncmp(&a->spoly, &b->spoly))) return(result);
+ if((result = psncmp(&a->init, &b->init))) return(result);
+ if((a->flags & P_REFIN) && (~b->flags & P_REFIN)) return(1);
+ if((~a->flags & P_REFIN) && (b->flags & P_REFIN)) return(-1);
+ if((a->flags & P_REFOUT) && (~b->flags & P_REFOUT)) return(1);
+ if((~a->flags & P_REFOUT) && (b->flags & P_REFOUT)) return(-1);
+ return(psncmp(&a->xorout, &b->xorout));
+}
+
+int
+mbynam(model_t *dest, const char *key) {
+ /* Sets parameters in dest according to the model named by key.
+ */
+ struct malias akey = {NULL, NULL, 0}, *aptr;
+ char *ukey, *uptr;
+
+ if(!aliases->name)
+ return(-1);
+ if(!(ukey = malloc((size_t) 1 + strlen(key))))
+ uerror("cannot allocate memory for comparison string");
+ akey.name = uptr = ukey;
+ do
+ *uptr++ = toupper(*key);
+ while(*key++);
+
+ aptr = bsearch(&akey, aliases, NALIASES, sizeof(struct malias), (int (*)(const void *, const void *)) &acmp);
+ free(ukey);
+
+ if(aptr == NULL)
+ return(0);
+ munpack(dest, aptr->model);
+ return(1);
+}
+
+void
+mbynum(model_t *dest, int num) {
+ /* Sets parameters in dest according to the model indexed by num. */
+ if(num > NPRESETS)
+ num = NPRESETS;
+ munpack(dest, models+num);
+}
+
+int
+mcount(void) {
+ /* Returns the number of preset models. */
+ return(NPRESETS);
+}
+
+char *
+mnames(void) {
+ /* Returns a malloc()-ed string of the names of all preset
+ * models, separated by newlines and terminated by NULL.
+ * Aliases are not listed.
+ */
+ size_t size = 0;
+ char *string, *sptr;
+ const struct malias *aptr = aliases;
+
+ while(aptr->name) {
+ if(aptr->isprimry)
+ size += strlen(aptr->name) + 1;
+ ++aptr;
+ }
+ if(!size) return(NULL);
+ if((string = malloc(size))) {
+ aptr = aliases;
+ sptr = string;
+ while(aptr->name) {
+ if(aptr->isprimry) {
+ strcpy(sptr, aptr->name);
+ sptr += strlen(aptr->name);
+ *sptr++ = '\n';
+ }
+ ++aptr;
+ }
+ *--sptr = '\0';
+ } else
+ uerror("cannot allocate memory for list of models");
+
+ return(string);
+}
+
+char *
+mtostr(const model_t *model) {
+ /* Returns a malloc()-ed string containing a Williams model
+ * record representing the input model.
+ * mcanon() should be called on the argument before printing.
+ */
+ size_t size;
+ char *polystr, *initstr, *xorotstr, *checkstr, strbuf[512], *string = NULL;
+
+ if(!model) return(NULL);
+ polystr = ptostr(model->spoly, P_RTJUST, 4);
+ initstr = ptostr(model->init, P_RTJUST, 4);
+ xorotstr = ptostr(model->xorout, P_RTJUST, 4);
+ checkstr = ptostr(model->check, P_RTJUST, 4);
+
+ sprintf(strbuf, "%lu", plen(model->spoly));
+ size =
+ 70
+ + (model->name && *model->name ? 2 + strlen(model->name) : 6)
+ + strlen(strbuf)
+ + (polystr && *polystr ? strlen(polystr) : 6)
+ + (initstr && *initstr ? strlen(initstr) : 6)
+ + (model->flags & P_REFIN ? 4 : 5)
+ + (model->flags & P_REFOUT ? 4 : 5)
+ + (xorotstr && *xorotstr ? strlen(xorotstr) : 6)
+ + (checkstr && *checkstr ? strlen(checkstr) : 6);
+ if((string = malloc(size))) {
+ sprintf(strbuf, "\"%s\"", model->name);
+ sprintf(string,
+ "width=%lu "
+ "poly=0x%s "
+ "init=0x%s "
+ "refin=%s "
+ "refout=%s "
+ "xorout=0x%s "
+ "check=0x%s "
+ "name=%s",
+ plen(model->spoly),
+ polystr && *polystr ? polystr : "(none)",
+ initstr && *initstr ? initstr : "(none)",
+ (model->flags & P_REFIN) ? "true" : "false",
+ (model->flags & P_REFOUT) ? "true" : "false",
+ xorotstr && *xorotstr ? xorotstr : "(none)",
+ checkstr && *checkstr ? checkstr : "(none)",
+ (model->name && *model->name) ? strbuf : "(none)");
+ }
+ free(polystr);
+ free(initstr);
+ free(xorotstr);
+ free(checkstr);
+ if(!string)
+ uerror("cannot allocate memory for model description");
+ return(string);
+}
+
+void
+mmatch(model_t *model, int flags) {
+ /* searches models[] for a model matching the argument, and links a name if found
+ * if flags & M_OVERWR, copies the found model onto the argument. */
+ model_t *mptr;
+ if(!model) return;
+
+ mptr = bsearch(model, models, NPRESETS, sizeof(model_t), (int (*)(const void *, const void *)) &mcmp);
+ if(mptr) {
+ model->name = mptr->name;
+ if(flags & M_OVERWR)
+ mcpy(model, mptr);
+ }
+}
+
+void
+mcanon(model_t *model) {
+ /* canonicalise a model */
+ unsigned long dlen;
+
+ if(!model) return;
+
+ /* extending on the right here. This preserves the functionality
+ * of a presumed working model.
+ */
+ psnorm(&model->spoly);
+ dlen = plen(model->spoly);
+ praloc(&model->init, dlen);
+ praloc(&model->xorout, dlen);
+
+ if(!plen(model->check))
+ mcheck(model);
+}
+
+void
+mcheck(model_t *model) {
+ /* calculate a check for the model */
+ poly_t checkstr, check;
+
+ /* generate the check string with the correct bit order */
+ checkstr = strtop("313233343536373839", model->flags, 8);
+ check = pcrc(checkstr, model->spoly, model->init, pzero, model->flags);
+ if(model->flags & P_REFOUT)
+ prev(&check);
+ psum(&check, model->xorout, 0UL);
+ model->check = check;
+ pfree(&checkstr);
+}
+
+void
+mrev(model_t *model) {
+ /* reverse the model to calculate reversed CRCs */
+ /* Here we invert RefIn and RefOut so that the user need only
+ * reverse the order of characters in the arguments, not the
+ * characters themselves. If RefOut=True, the mirror image of
+ * Init seen through RefOut becomes XorOut, and as RefOut
+ * becomes false, the XorOut value moved to Init stays upright.
+ * If RefOut=False, Init transfers to XorOut without reflection
+ * but the new Init must be reflected to present the same image,
+ * as RefOut becomes true.
+ */
+ poly_t temp;
+
+ prcp(&model->spoly);
+ if(model->flags & P_REFOUT)
+ prev(&model->init);
+ else
+ prev(&model->xorout);
+
+ /* exchange init and xorout */
+ temp = model->init;
+ model->init = model->xorout;
+ model->xorout = temp;
+
+ /* invert refin and refout */
+ model->flags ^= P_REFIN | P_REFOUT;
+
+ mnovel(model);
+}
+
+void
+mnovel(model_t *model) {
+ /* remove name and check string from modified model */
+ model->name = NULL;
+ pfree(&model->check);
+}
+
+static int
+acmp(const struct malias *a, const struct malias *b) {
+ /* compares two aliases, for use in bsearch */
+ if(!a || !b) return(!b - !a);
+ if(!a->name || !b->name) return(!b->name - !a->name);
+ return(strcmp(a->name, b->name));
+}
+
+static void
+munpack(model_t *dest, const struct mpreset *src) {
+ /* Copies the parameters of src to dest.
+ * dest must be an initialised model.
+ */
+ unsigned long iter, idx;
+ if(!dest || !src) return;
+ MUNPACK(spoly);
+ MUNPACK(init);
+ MUNPACK(xorout);
+ MUNPACK(check);
+ dest->flags = src->flags;
+ /* link to the name as it is static */
+ dest->name = src->name;
+}
--- /dev/null
+/* poly.c
+ * Greg Cook, 9/Apr/2015
+ */
+
+/* CRC RevEng, an arbitrary-precision CRC calculator and algorithm finder
+ * Copyright (C) 2010, 2011, 2012, 2013, 2014, 2015 Gregory Cook
+ *
+ * This file is part of CRC RevEng.
+ *
+ * CRC RevEng is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * CRC RevEng is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with CRC RevEng. If not, see <http://www.gnu.org/licenses/>.
+ */
+
+/* 2015-04-03: added direct mode to strtop()
+ * 2014-01-11: added LOFS(), RNDUP()
+ * 2013-09-16: SIZE(), IDX(), OFS() macros bitshift if BMP_POF2
+ * 2013-02-07: conditional non-2^n fix, pmpar() return mask constant type
+ * 2013-01-17: fixed pfirst(), plast() for non-2^n BMP_BIT
+ * 2012-07-16: added pident()
+ * 2012-05-23: added pmpar()
+ * 2012-03-03: internal lookup tables stored better
+ * 2012-03-02: fixed full-width masking in filtop()
+ * 2011-09-06: added prevch()
+ * 2011-08-27: fixed zero test in piter()
+ * 2011-01-17: fixed ANSI C warnings, uses bmp_t type
+ * 2011-01-15: palloc() and praloc() gracefully handle lengths slightly
+ * less than ULONG_MAX
+ * 2011-01-15: strtop() error on invalid argument. pkchop() special case
+ * when argument all zeroes
+ * 2011-01-14: added pkchop()
+ * 2011-01-04: fixed bogus final length calculation in wide pcrc()
+ * 2011-01-02: faster, more robust prcp()
+ * 2011-01-01: commented functions, full const declarations, all-LUT rev()
+ * 2010-12-26: renamed CRC RevEng
+ * 2010-12-18: removed pmods(), finished pcrc(), added piter()
+ * 2010-12-17: roughed out pcrc(). difficult, etiam aberat musa heri :(
+ * 2010-12-15: added psnorm(), psncmp(); optimised pnorm(); fix to praloc()
+ * 2010-12-14: strtop() resets count between passes
+ * 2010-12-12: added pright()
+ * 2010-12-11: filtop won't read more than length bits
+ * 2010-12-10: finished filtop. 26 public functions
+ * 2010-12-05: finished strtop, pxsubs; unit tests
+ * 2010-12-02: project started
+ */
+
+/* Note: WELL-FORMED poly_t objects have a valid bitmap pointer pointing
+ * to a malloc()-ed array of at least as many bits as stated in its
+ * length field. Any poly_t with a length of 0 is also a WELL-FORMED
+ * poly_t (whatever value the bitmap pointer has.)
+ * All poly_t objects passed to and from functions must be WELL-FORMED
+ * unless otherwise stated.
+ *
+ * CLEAN (or CANONICAL) poly_t objects are WELL-FORMED objects in which
+ * all spare bits in the bitmap word containing the last bit are zero.
+ * (Any excess allocated words will not be accessed.)
+ *
+ * SEMI-NORMALISED poly_t objects are CLEAN objects in which the last
+ * bit, at position (length - 1), is one.
+ *
+ * NORMALISED poly_t objects are SEMI-NORMALISED objects in which the
+ * first bit is one.
+ *
+ * pfree() should be called on every poly_t object (including
+ * those returned by functions) after its last use.
+ * As always, free() should be called on every malloc()-ed string after
+ * its last use.
+ */
+
+#include <limits.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include "reveng.h"
+
+static bmp_t getwrd(const poly_t poly, unsigned long iter);
+static bmp_t rev(bmp_t accu, int bits);
+static void prhex(char **spp, bmp_t bits, int flags, int bperhx);
+
+static const poly_t pzero = PZERO;
+
+/* word number (0..m-1) of var'th bit (0..n-1) */
+#if BMP_POF2 >= 5
+# define IDX(var) ((var) >> BMP_POF2)
+#else
+# define IDX(var) ((var) / BMP_BIT)
+#endif
+
+/* size of polynomial with var bits */
+#if BMP_POF2 >= 5
+# define SIZE(var) ((BMP_BIT - 1UL + (var)) >> BMP_POF2)
+#else
+# define SIZE(var) ((BMP_BIT - 1UL + (var)) / BMP_BIT)
+#endif
+
+/* polynomial length rounded up to BMP_BIT */
+#ifdef BMP_POF2
+# define RNDUP(var) (~(BMP_BIT - 1UL) & (BMP_BIT - 1UL + (var)))
+#else
+# define RNDUP(var) ((BMP_BIT - (var) % BMP_BIT) % BMP_BIT + (var))
+#endif
+
+/* bit offset (0..BMP_BIT-1, 0 = LSB) of var'th bit (0..n-1) */
+#ifdef BMP_POF2
+# define OFS(var) ((int) ((BMP_BIT - 1UL) & ~(var)))
+#else
+# define OFS(var) ((int) (BMP_BIT - 1UL - (var) % BMP_BIT))
+#endif
+
+/* bit offset (0..BMP_BIT-1, 0 = MSB) of var'th bit (0..n-1) */
+#ifdef BMP_POF2
+# define LOFS(var) ((int) ((BMP_BIT - 1UL) & (var)))
+#else
+# define LOFS(var) ((int) ((var) % BMP_BIT))
+#endif
+
+poly_t
+filtop(FILE *input, unsigned long length, int flags, int bperhx) {
+ /* reads binary data from input into a poly_t until EOF or until
+ * length bits are read. Characters are read until
+ * ceil(bperhx / CHAR_BIT) bits are collected; if P_LTLBYT is
+ * set in flags then the first character contains the LSB,
+ * otherwise the last one does. The least significant bperhx
+ * bits are taken, reflected (if P_REFIN) and appended to the
+ * result, then more characters are read. The maximum number of
+ * characters read is
+ * floor(length / bperhx) * ceil(bperhx / * CHAR_BIT).
+ * The returned poly_t is CLEAN.
+ */
+
+ bmp_t accu = BMP_C(0);
+ bmp_t mask = bperhx == BMP_BIT ? ~BMP_C(0) : (BMP_C(1) << bperhx) - BMP_C(1);
+ unsigned long iter = 0UL, idx;
+ int cmask = ~(~0 << CHAR_BIT), c;
+ int count = 0, ofs;
+ poly_t poly = PZERO;
+ if(bperhx == 0) return(poly);
+
+ length -= length % bperhx;
+ palloc(&poly, length); /* >= 0 */
+
+ while(iter < length && (c = fgetc(input)) != EOF) {
+ if(flags & P_LTLBYT)
+ accu |= (bmp_t) (c & cmask) << count;
+ else
+ accu = (accu << CHAR_BIT) | (bmp_t) (c & cmask);
+ count += CHAR_BIT;
+ if(count >= bperhx) {
+ /* the low bperhx bits of accu contain bits of the poly.*/
+ iter += bperhx;
+ count = 0;
+ if(flags & P_REFIN)
+ accu = rev(accu, bperhx);
+ accu &= mask;
+
+ /* iter >= bperhx > 0 */
+ idx = IDX(iter - 1UL);
+ ofs = OFS(iter - 1UL);
+ poly.bitmap[idx] |= accu << ofs;
+ if(ofs + bperhx > BMP_BIT) {
+ poly.bitmap[idx-1] |= accu >> (BMP_BIT - ofs);
+ }
+ accu = BMP_C(0); /* only needed for P_LTLBYT */
+ }
+ }
+ praloc(&poly, iter);
+ return(poly);
+}
+
+poly_t
+strtop(const char *string, int flags, int bperhx) {
+ /* Converts a hex or character string to a poly_t.
+ * Each character is converted to a hex nibble yielding 4 bits
+ * unless P_DIRECT, when each character yields CHAR_BIT bits.
+ * Nibbles and characters are accumulated left-to-right
+ * unless P_DIRECT && P_LTLBYT, when they are accumulated
+ * right-to-left without reflection.
+ * As soon as at least bperhx bits are accumulated, the
+ * rightmost bperhx bits are reflected (if P_REFIN)
+ * and appended to the poly. When !P_DIRECT:
+ * bperhx=8 reads hex nibbles in pairs
+ * bperhx=7 reads hex nibbles in pairs and discards
+ * b3 of first nibble
+ * bperhx=4 reads hex nibbles singly
+ * bperhx=3 reads octal
+ * bperhx=1 reads longhand binary
+ * in theory if !P_REFIN, bperhx can be any multiple of 4
+ * with equal effect
+ * The returned poly_t is CLEAN.
+ */
+
+ /* make two passes, one to determine the poly size
+ * one to populate the bitmap
+ */
+ unsigned long length = 1UL, idx;
+ bmp_t accu;
+ bmp_t mask = bperhx == BMP_BIT ? ~BMP_C(0) : (BMP_C(1) << bperhx) - BMP_C(1);
+ int pass, count, ofs;
+ int cmask = ~(~0 << CHAR_BIT), c;
+ const char *s;
+
+ poly_t poly = PZERO;
+ if(bperhx > BMP_BIT || bperhx <= 0 || string == NULL || *string == '\0')
+ return(poly);
+
+ for(pass=0; pass<2 && length > 0UL; ++pass) {
+ s = string;
+ length = 0UL;
+ count = 0;
+ accu = BMP_C(0);
+ while((c = *s++)) {
+ if(flags & P_DIRECT) {
+ if(flags & P_LTLBYT)
+ accu |= (bmp_t) (c & cmask) << count;
+ else
+ accu = (accu << CHAR_BIT) | (bmp_t) (c & cmask);
+ count += CHAR_BIT;
+ } else {
+ if(c == ' ' || c == '\t' || c == '\r' || c == '\n') continue;
+ accu <<= 4;
+ count += 4;
+ switch(c) {
+ case '0':
+ case '1':
+ case '2':
+ case '3':
+ case '4':
+ case '5':
+ case '6':
+ case '7':
+ case '8':
+ case '9':
+ accu |= (bmp_t) c - '0';
+ break;
+ case 'A':
+ case 'a':
+ accu |= BMP_C(0xa);
+ break;
+ case 'B':
+ case 'b':
+ accu |= BMP_C(0xb);
+ break;
+ case 'C':
+ case 'c':
+ accu |= BMP_C(0xc);
+ break;
+ case 'D':
+ case 'd':
+ accu |= BMP_C(0xd);
+ break;
+ case 'E':
+ case 'e':
+ accu |= BMP_C(0xe);
+ break;
+ case 'F':
+ case 'f':
+ accu |= BMP_C(0xf);
+ break;
+ default:
+ uerror("invalid character in hexadecimal argument");
+ }
+ }
+
+ if(count >= bperhx) {
+ /* the low bperhx bits of accu contain bits of the poly.
+ * in pass 0, increment length by bperhx.
+ * in pass 1, put the low bits of accu into the bitmap. */
+ length += bperhx;
+ count = 0;
+ if(pass == 1) {
+ if(flags & P_REFIN)
+ accu = rev(accu, bperhx);
+ accu &= mask;
+
+ /* length >= bperhx > 0 */
+ idx = IDX(length - 1);
+ ofs = OFS(length - 1);
+ poly.bitmap[idx] |= accu << ofs;
+ if(ofs + bperhx > BMP_BIT)
+ poly.bitmap[idx-1] |= accu >> (BMP_BIT - ofs);
+ accu = BMP_C(0); /* only needed for P_LTLBYT */
+ }
+ }
+ }
+ if(pass == 0) palloc(&poly, length);
+ }
+ return(poly);
+}
+
+char *
+ptostr(const poly_t poly, int flags, int bperhx) {
+ /* Returns a malloc()-ed string containing a hexadecimal
+ * representation of poly. See phxsubs().
+ */
+ return(pxsubs(poly, flags, bperhx, 0UL, poly.length));
+}
+
+char *
+pxsubs(const poly_t poly, int flags, int bperhx, unsigned long start, unsigned long end) {
+ /* Returns a malloc()-ed string containing a hexadecimal
+ * representation of a portion of poly, from bit offset start to
+ * (end - 1) inclusive. The output is grouped into words of
+ * bperhx bits each. If P_RTJUST then the first word is padded
+ * with zeroes at the MSB end to make a whole number of words,
+ * otherwise the last word is padded at the LSB end. After
+ * justification the bperhx bits of each word are reversed (if
+ * P_REFOUT) and printed as a hex sequence, with words
+ * optionally separated by spaces (P_SPACE).
+ * If end exceeds the length of poly then zero bits are appended
+ * to make up the difference, in which case poly must be CLEAN.
+ */
+ char *string, *sptr;
+ unsigned long size, iter;
+ bmp_t accu;
+ bmp_t mask = bperhx == BMP_BIT ? ~BMP_C(0) : (BMP_C(1) << bperhx) - BMP_C(1);
+ int cperhx, part;
+
+ if(bperhx <= 0 || bperhx > BMP_BIT) return(NULL);
+
+ if(start > poly.length) start = poly.length;
+ if(end > poly.length) end = poly.length;
+ if(end < start) end = start;
+
+ cperhx = (bperhx + 3) >> 2;
+ if(flags & P_SPACE) ++cperhx;
+
+ size = (end - start + bperhx - 1UL) / bperhx;
+ size *= cperhx;
+ if(!size || ~flags & P_SPACE) ++size; /* for trailing null */
+
+ if(!(sptr = string = (char *) malloc(size)))
+ uerror("cannot allocate memory for string");
+
+ size = end - start;
+ part = (int) size % bperhx;
+ if(part && flags & P_RTJUST) {
+ iter = start + part;
+ accu = getwrd(poly, iter - 1UL) & ((BMP_C(1) << part) - BMP_C(1));
+ if(flags & P_REFOUT)
+ /* best to reverse over bperhx rather than part, I think
+ * e.g. converting a 7-bit poly to 8-bit little-endian hex
+ */
+ accu = rev(accu, bperhx);
+ prhex(&sptr, accu, flags, bperhx);
+ if(flags & P_SPACE && size > iter) *sptr++ = ' ';
+ } else {
+ iter = start;
+ }
+
+ while((iter+=bperhx) <= end) {
+ accu = getwrd(poly, iter - 1UL) & mask;
+ if(flags & P_REFOUT)
+ accu = rev(accu, bperhx);
+ prhex(&sptr, accu, flags, bperhx);
+ if(flags & P_SPACE && size > iter) *sptr++ = ' ';
+ }
+
+ if(part && ~flags & P_RTJUST) {
+ accu = getwrd(poly, end - 1UL);
+ if(flags & P_REFOUT)
+ accu = rev(accu, part);
+ else
+ accu = accu << (bperhx - part) & mask;
+ prhex(&sptr, accu, flags, bperhx);
+ }
+ *sptr = '\0';
+ return(string);
+}
+
+poly_t
+pclone(const poly_t poly) {
+ /* Returns a freestanding copy of poly. Does not clean poly or
+ * the result.
+ */
+ poly_t clone = PZERO;
+
+ pcpy(&clone, poly);
+ return(clone);
+}
+
+void
+pcpy(poly_t *dest, const poly_t src) {
+ /* Assigns (copies) src into dest. Does not clean src or dest.
+ */
+ unsigned long iter, idx;
+
+ praloc(dest, src.length);
+ for(iter=0UL, idx=0UL; iter < src.length; iter += BMP_BIT, ++idx)
+ dest->bitmap[idx] = src.bitmap[idx];
+}
+
+void
+pcanon(poly_t *poly) {
+ /* Converts poly into a CLEAN object by freeing unused bitmap words
+ * and clearing any bits in the last word beyond the last bit.
+ * The length field has absolute priority over the contents of the bitmap.
+ * Canonicalisation differs from normalisation in that leading and trailing
+ * zero terms are significant and preserved.
+ * poly may or may not be WELL-FORMED.
+ */
+ praloc(poly, poly->length);
+}
+
+void
+pnorm(poly_t *poly) {
+ /* Converts poly into a NORMALISED object by removing leading
+ * and trailing zeroes, so that the polynomial starts and ends
+ * with significant terms.
+ * poly may or may not be WELL-FORMED.
+ */
+ unsigned long first;
+
+ /* call pcanon() here so pfirst() and plast() return the correct
+ * results
+ */
+ pcanon(poly);
+ first = pfirst(*poly);
+ if(first)
+ pshift(poly, *poly, 0UL, first, plast(*poly), 0UL);
+ else
+ praloc(poly, plast(*poly));
+}
+
+void
+psnorm(poly_t *poly) {
+ /* Converts poly into a SEMI-NORMALISED object by removing
+ * trailing zeroes, so that the polynomial ends with a
+ * significant term.
+ * poly may or may not be WELL-FORMED.
+ */
+
+ /* call pcanon() here so plast() returns the correct result */
+ pcanon(poly);
+ praloc(poly, plast(*poly));
+}
+
+void
+pchop(poly_t *poly) {
+ /* Normalise poly, then chop off the highest significant term
+ * (produces a SEMI-NORMALISED object). poly becomes a suitable
+ * divisor for pcrc().
+ * poly may or may not be WELL-FORMED.
+ */
+
+ /* call pcanon() here so pfirst() and plast() return correct
+ * results
+ */
+ pcanon(poly);
+ pshift(poly, *poly, 0UL, pfirst(*poly) + 1UL, plast(*poly), 0UL);
+}
+
+void
+pkchop(poly_t *poly) {
+ /* Convert poly from Koopman notation to chopped form (produces
+ * a SEMI-NORMALISED object). poly becomes a suitable divisor
+ * for pcrc().
+ * poly may or may not be WELL-FORMED.
+ */
+ unsigned long first;
+
+ /* call pcanon() here so pfirst() returns the correct result */
+ pcanon(poly);
+ first = pfirst(*poly);
+ if(first >= poly->length) {
+ pfree(poly);
+ return;
+ }
+ pshift(poly, *poly, 0UL, first + 1UL, poly->length, 1UL);
+ piter(poly);
+}
+
+unsigned long
+plen(const poly_t poly) {
+ /* Return length of polynomial.
+ * poly may or may not be WELL-FORMED.
+ */
+ return(poly.length);
+}
+
+int
+pcmp(const poly_t *a, const poly_t *b) {
+ /* Compares poly_t objects for identical sizes and contents.
+ * a and b must be CLEAN.
+ * Defines a total order relation for sorting, etc. although
+ * mathematically, polynomials of equal degree are no greater or
+ * less than one another.
+ */
+ unsigned long iter;
+ bmp_t *aptr, *bptr;
+
+ if(!a || !b) return(!b - !a);
+ if(a->length < b->length) return(-1);
+ if(a->length > b->length) return(1);
+ aptr = a->bitmap;
+ bptr = b->bitmap;
+ for(iter=0UL; iter < a->length; iter += BMP_BIT) {
+ if(*aptr < *bptr)
+ return(-1);
+ if(*aptr++ > *bptr++)
+ return(1);
+ }
+ return(0);
+}
+
+int
+psncmp(const poly_t *a, const poly_t *b) {
+ /* Compares polys for identical effect, i.e. as though the
+ * shorter poly were padded with zeroes to the length of the
+ * longer.
+ * a and b must still be CLEAN, therefore psncmp() is *not*
+ * identical to pcmp() on semi-normalised polys as psnorm()
+ * clears the slack space.
+ */
+ unsigned long length, iter, idx;
+ bmp_t aword, bword;
+ if(!a || !b) return(!b - !a);
+ length = (a->length > b->length) ? a->length : b->length;
+ for(iter = 0UL, idx = 0UL; iter < length; iter += BMP_BIT, ++idx) {
+ aword = (iter < a->length) ? a->bitmap[idx] : BMP_C(0);
+ bword = (iter < b->length) ? b->bitmap[idx] : BMP_C(0);
+ if(aword < bword)
+ return(-1);
+ if(aword > bword)
+ return(1);
+ }
+ return(0);
+}
+
+
+int
+ptst(const poly_t poly) {
+ /* Tests whether a polynomial equals zero. Returns 0 if equal,
+ * a nonzero value otherwise.
+ * poly must be CLEAN.
+ */
+ unsigned long iter;
+ bmp_t *bptr;
+ if(!poly.bitmap) return(0);
+ for(iter = 0UL, bptr = poly.bitmap; iter < poly.length; iter += BMP_BIT)
+ if(*bptr++) return(1);
+ return(0);
+}
+
+unsigned long
+pfirst(const poly_t poly) {
+ /* Returns the index of the first nonzero term in poly. If none
+ * is found, returns the length of poly.
+ * poly must be CLEAN.
+ */
+ unsigned long idx = 0UL, size = SIZE(poly.length);
+ bmp_t accu = BMP_C(0); /* initialiser for Acorn C */
+ unsigned int probe = BMP_SUB, ofs = 0;
+
+ while(idx < size && !(accu = poly.bitmap[idx])) ++idx;
+ if(idx >= size) return(poly.length);
+ while(probe) {
+#ifndef BMP_POF2
+ while((ofs | probe) >= (unsigned int) BMP_BIT) probe >>= 1;
+#endif
+ if(accu >> (ofs | probe)) ofs |= probe;
+ probe >>= 1;
+ }
+
+ return(BMP_BIT - 1UL - ofs + idx * BMP_BIT);
+}
+
+unsigned long
+plast(const poly_t poly) {
+ /* Returns 1 plus the index of the last nonzero term in poly.
+ * If none is found, returns zero.
+ * poly must be CLEAN.
+ */
+ unsigned long idx, size = SIZE(poly.length);
+ bmp_t accu;
+ unsigned int probe = BMP_SUB, ofs = 0;
+
+ if(!poly.length) return(0UL);
+ idx = size - 1UL;
+ while(idx && !(accu = poly.bitmap[idx])) --idx;
+ if(!idx && !(accu = poly.bitmap[idx])) return(0UL);
+ /* now accu == poly.bitmap[idx] and contains last significant term */
+ while(probe) {
+#ifndef BMP_POF2
+ while((ofs | probe) >= (unsigned int) BMP_BIT) probe >>= 1;
+#endif
+ if(accu << (ofs | probe)) ofs |= probe;
+ probe >>= 1;
+ }
+
+ return(idx * BMP_BIT + ofs + 1UL);
+}
+
+poly_t
+psubs(const poly_t src, unsigned long head, unsigned long start, unsigned long end, unsigned long tail) {
+ poly_t dest = PZERO;
+ pshift(&dest, src, head, start, end, tail);
+ return(dest);
+}
+
+void
+pright(poly_t *poly, unsigned long length) {
+ /* Trims or extends poly to length at the left edge, prepending
+ * zeroes if necessary. Analogous to praloc() except the
+ * rightmost terms of poly are preserved.
+ * On entry, poly may or may not be WELL-FORMED.
+ * On exit, poly is CLEAN.
+ */
+
+ if(length > poly->length)
+ pshift(poly, *poly, length - poly->length, 0UL, poly->length, 0UL);
+ else if(length < poly->length)
+ pshift(poly, *poly, 0UL, poly->length - length, poly->length, 0UL);
+ else
+ praloc(poly, poly->length);
+}
+
+void
+pshift(poly_t *dest, const poly_t src, unsigned long head, unsigned long start, unsigned long end, unsigned long tail) {
+ /* copies bits start to end-1 of src to dest, plus the number of leading and trailing zeroes given by head and tail.
+ * end may exceed the length of src in which case more zeroes are appended.
+ * dest may point to src, in which case the poly is edited in place.
+ * On exit, dest is CLEAN.
+ */
+
+ unsigned long length, fulllength, size, fullsize, iter, idx, datidx;
+ /* condition inputs; end, head and tail may be any value */
+ if(end < start) end = start;
+
+ length = end - start + head;
+ fulllength = length + tail;
+ if(fulllength > src.length)
+ praloc(dest, fulllength);
+ else
+ praloc(dest, src.length);
+
+ /* number of words in new poly */
+ size = SIZE(length);
+ fullsize = SIZE(fulllength);
+ /* array index of first word ending up with source material */
+ datidx = IDX(head);
+
+ if(head > start && end > start) {
+ /* shifting right, size > 0 */
+ /* index of the source bit ending up in the LSB of the last word
+ * size * BMP_BIT >= length > head > 0 */
+ iter = size * BMP_BIT - head - 1UL;
+ for(idx = size - 1UL; idx > datidx; iter -= BMP_BIT, --idx)
+ dest->bitmap[idx] = getwrd(src, iter);
+ dest->bitmap[idx] = getwrd(src, iter);
+ /* iter == size * BMP_BIT - head - 1 - BMP_BIT * (size - 1 - datidx)
+ * == BMP_BIT * (size - size + 1 + datidx) - head - 1
+ * == BMP_BIT * (1 + head / BMP_BIT) - head - 1
+ * == BMP_BIT + head - head % BMP_BIT - head - 1
+ * == BMP_BIT - head % BMP_BIT - 1
+ * >= 0
+ */
+ } else if(head <= start) {
+ /* shifting left or copying */
+ /* index of the source bit ending up in the LSB of bitmap[idx] */
+ iter = start - head + BMP_BIT - 1UL;
+ for(idx = datidx; idx < size; iter += BMP_BIT, ++idx)
+ dest->bitmap[idx] = getwrd(src, iter);
+ }
+
+ /* clear head */
+ for(idx = 0UL; idx < datidx; ++idx)
+ dest->bitmap[idx] = BMP_C(0);
+ if(size)
+ dest->bitmap[datidx] &= ~BMP_C(0) >> LOFS(head);
+
+ /* clear tail */
+ if(LOFS(length))
+ dest->bitmap[size - 1UL] &= ~(~BMP_C(0) >> LOFS(length));
+ for(idx = size; idx < fullsize; ++idx)
+ dest->bitmap[idx] = BMP_C(0);
+
+ /* call praloc to shrink poly if required */
+ if(dest->length > fulllength)
+ praloc(dest, fulllength);
+}
+
+void
+ppaste(poly_t *dest, const poly_t src, unsigned long skip, unsigned long seek, unsigned long end, unsigned long fulllength) {
+ /* pastes terms of src, starting from skip, to positions seek to end-1 of dest
+ * then sets length of dest to fulllength (>= end)
+ * to paste n terms of src, give end = seek + n
+ * to truncate dest at end of paste, set fulllength = end
+ * to avoid truncating, set fulllength = plen(*dest)
+ * dest may point to src, in which case the poly is edited in place.
+ * src must be CLEAN in the case that the end is overrun.
+ * On exit, dest is CLEAN.
+ */
+ bmp_t mask;
+ unsigned long seekidx, endidx, iter;
+ int seekofs;
+ if(end < seek) end = seek;
+ if(fulllength < end) fulllength = end;
+
+ /* expand dest if necessary. don't shrink as dest may be src */
+ if(fulllength > dest->length)
+ praloc(dest, fulllength);
+ seekidx = IDX(seek);
+ endidx = IDX(end);
+ seekofs = OFS(seek);
+ /* index of the source bit ending up in the LSB of the first modified word */
+ iter = skip + seekofs;
+ if(seekidx == endidx) {
+ /* paste affects one word (traps end = seek case) */
+ mask = ((BMP_C(1) << seekofs) - (BMP_C(1) << OFS(end))) << 1;
+ dest->bitmap[seekidx] = (dest->bitmap[seekidx] & ~mask) | (getwrd(src, iter) & mask);
+ } else if(seek > skip) {
+ /* shifting right */
+ /* index of the source bit ending up in the LSB of the last modified word */
+ iter += (endidx - seekidx) * BMP_BIT;
+ mask = ~BMP_C(0) >> LOFS(end);
+ dest->bitmap[endidx] = (dest->bitmap[endidx] & mask) | (getwrd(src, iter) & ~mask);
+ for(iter -= BMP_BIT, --endidx; endidx > seekidx; iter -= BMP_BIT, --endidx)
+ dest->bitmap[endidx] = getwrd(src, iter);
+ mask = ~BMP_C(0) >> LOFS(seek);
+ dest->bitmap[endidx] = (dest->bitmap[endidx] & ~mask) | (getwrd(src, iter) & mask);
+ /* iter == skip + seekofs + (endidx - seekidx) * BMP_BIT - BMP_BIT * (endidx - seekidx)
+ * == skip + seekofs + BMP_BIT * (endidx - seekidx - endidx + seekidx)
+ * == skip + seekofs
+ * >= 0
+ */
+ } else {
+ /* shifting left or copying */
+ mask = ~BMP_C(0) >> LOFS(seek);
+ dest->bitmap[seekidx] = (dest->bitmap[seekidx] & ~mask) | (getwrd(src, iter) & mask);
+ for(iter += BMP_BIT, ++seekidx; seekidx < endidx; iter += BMP_BIT, ++seekidx)
+ dest->bitmap[seekidx] = getwrd(src, iter);
+ mask = ~BMP_C(0) >> LOFS(end);
+ dest->bitmap[seekidx] = (dest->bitmap[seekidx] & mask) | (getwrd(src, iter) & ~mask);
+ }
+ /* shrink poly if required */
+ if(dest->length > fulllength)
+ praloc(dest, fulllength);
+}
+
+void
+pdiff(poly_t *dest, const poly_t src, unsigned long ofs) {
+ /* Subtract src from dest (modulo 2) at offset ofs.
+ * In modulo 2 arithmetic, subtraction is equivalent to addition
+ * We include an alias for those who wish to retain the distinction
+ * src and dest must be CLEAN.
+ */
+ psum(dest, src, ofs);
+}
+
+void
+psum(poly_t *dest, const poly_t src, unsigned long ofs) {
+ /* Adds src to dest (modulo 2) at offset ofs.
+ * When ofs == dest->length, catenates src on to dest.
+ * src and dest must be CLEAN.
+ */
+ unsigned long fulllength, idx, iter, end;
+
+ fulllength = ofs + src.length;
+ if(fulllength > dest->length)
+ praloc(dest, fulllength);
+ /* array index of first word in dest to be modified */
+ idx = IDX(ofs);
+ /* index of bit in src to be added to LSB of dest->bitmap[idx] */
+ iter = OFS(ofs);
+ /* stop value for iter */
+ end = BMP_BIT - 1UL + src.length;
+ for(; iter < end; iter += BMP_BIT, ++idx)
+ dest->bitmap[idx] ^= getwrd(src, iter);
+}
+
+void
+prev(poly_t *poly) {
+ /* Reverse or reciprocate a polynomial.
+ * On exit, poly is CLEAN.
+ */
+ unsigned long leftidx = 0UL, rightidx = SIZE(poly->length);
+ unsigned long ofs = LOFS(BMP_BIT - LOFS(poly->length));
+ unsigned long fulllength = poly->length + ofs;
+ bmp_t accu;
+
+ if(ofs)
+ /* removable optimisation */
+ if(poly->length < (unsigned long) BMP_BIT) {
+ *poly->bitmap = rev(*poly->bitmap >> ofs, (int) poly->length) << ofs;
+ return;
+ }
+
+ /* claim remaining bits of last word (as we use public function pshift()) */
+ poly->length = fulllength;
+
+ /* reverse and swap words in the array, leaving it right-justified */
+ while(leftidx < rightidx) {
+ /* rightidx > 0 */
+ accu = rev(poly->bitmap[--rightidx], BMP_BIT);
+ poly->bitmap[rightidx] = rev(poly->bitmap[leftidx], BMP_BIT);
+ poly->bitmap[leftidx++] = accu;
+ }
+ /* shift polynomial to left edge if required */
+ if(ofs)
+ pshift(poly, *poly, 0UL, ofs, fulllength, 0UL);
+}
+
+void
+prevch(poly_t *poly, int bperhx) {
+ /* Reverse each group of bperhx bits in a polynomial.
+ * Does not clean poly.
+ */
+ unsigned long iter = 0, idx, ofs;
+ bmp_t mask, accu;
+
+ if(bperhx < 2 || bperhx > BMP_BIT)
+ return;
+ if(poly->length % bperhx)
+ praloc(poly, bperhx - (poly->length % bperhx) + poly->length);
+ mask = ~BMP_C(0) >> (BMP_BIT - bperhx);
+ for(iter = (unsigned long) (bperhx - 1); iter < poly->length; iter += bperhx) {
+ accu = getwrd(*poly, iter) & mask;
+ accu ^= rev(accu, bperhx);
+ idx = IDX(iter);
+ ofs = OFS(iter);
+ poly->bitmap[idx] ^= accu << ofs;
+ if(ofs + bperhx > (unsigned int) BMP_BIT)
+ /* (BMP_BIT - 1UL - (iter) % BMP_BIT) + bperhx > BMP_BIT
+ * (-1UL - (iter) % BMP_BIT) + bperhx > 0
+ * (- (iter % BMP_BIT)) + bperhx > 1
+ * - (iter % BMP_BIT) > 1 - bperhx
+ * iter % BMP_BIT < bperhx - 1, iter >= bperhx - 1
+ * iter >= BMP_BIT
+ * idx >= 1
+ */
+ poly->bitmap[idx-1] ^= accu >> (BMP_BIT - ofs);
+ }
+}
+
+void
+prcp(poly_t *poly) {
+ /* Reciprocate a chopped polynomial. Use prev() on whole
+ * polynomials.
+ * On exit, poly is SEMI-NORMALISED.
+ */
+ unsigned long first;
+
+ praloc(poly, RNDUP(poly->length));
+ prev(poly);
+ first = pfirst(*poly);
+ if(first >= poly->length) {
+ pfree(poly);
+ return;
+ }
+ pshift(poly, *poly, 0UL, first + 1UL, poly->length, 1UL);
+ piter(poly);
+}
+
+void
+pinv(poly_t *poly) {
+ /* Invert a polynomial, i.e. add 1 (modulo 2) to the coefficient of each term
+ * on exit, poly is CLEAN.
+ */
+ unsigned long idx, size = SIZE(poly->length);
+
+ for(idx = 0UL; idx<size; ++idx)
+ poly->bitmap[idx] = ~poly->bitmap[idx];
+ if(LOFS(poly->length))
+ poly->bitmap[size - 1UL] &= ~(~BMP_C(0) >> LOFS(poly->length));
+}
+
+poly_t
+pmod(const poly_t dividend, const poly_t divisor) {
+ /* Divide dividend by normalised divisor and return the remainder
+ * This function generates a temporary 'chopped' divisor for pcrc()
+ * If calling repeatedly with a constant divisor, produce a chopped copy
+ * with pchop() and call pcrc() directly for higher efficiency.
+ * dividend and divisor must be CLEAN.
+ */
+
+ /* perhaps generate an error if divisor is zero */
+ poly_t subdivisor = psubs(divisor, 0UL, pfirst(divisor) + 1UL, plast(divisor), 0UL);
+ poly_t result = pcrc(dividend, subdivisor, pzero, pzero, 0);
+ pfree(&subdivisor);
+ return(result);
+}
+
+poly_t
+pcrc(const poly_t message, const poly_t divisor, const poly_t init, const poly_t xorout, int flags) {
+ /* Divide message by divisor and return the remainder.
+ * init is added to divisor, highest terms aligned, before
+ * division.
+ * xorout is added to the remainder, highest terms aligned.
+ * If P_MULXN is set in flags, message is multiplied by x^n
+ * (i.e. trailing zeroes equal to the CRC width are appended)
+ * before adding init and division. Set P_MULXN for most CRC
+ * calculations.
+ * All inputs must be CLEAN.
+ * If all inputs are CLEAN, the returned poly_t will be CLEAN.
+ */
+ unsigned long max = 0UL, iter, ofs, resiter;
+ bmp_t probe, rem, dvsr, *rptr, *sptr;
+ const bmp_t *bptr, *eptr;
+ poly_t result = PZERO;
+
+ if(flags & P_MULXN)
+ max = message.length;
+ else if(message.length > divisor.length)
+ max = message.length - divisor.length;
+ bptr=message.bitmap;
+ eptr=message.bitmap+SIZE(message.length);
+ probe=~(~BMP_C(0) >> 1);
+ if(divisor.length <= (unsigned long) BMP_BIT
+ && init.length <= (unsigned long) BMP_BIT) {
+ rem = init.length ? *init.bitmap : BMP_C(0);
+ dvsr = divisor.length ? *divisor.bitmap : BMP_C(0);
+ for(iter = 0UL, ofs = 0UL; iter < max; ++iter, --ofs) {
+ if(!ofs) {
+ ofs = BMP_BIT;
+ rem ^= *bptr++;
+ }
+ if(rem & probe)
+ rem = (rem << 1) ^ dvsr;
+ else
+ rem <<= 1;
+ }
+ if(bptr < eptr)
+ /* max < message.length */
+ rem ^= *bptr >> OFS(BMP_BIT - 1UL + max);
+ if(init.length > max && init.length - max > divisor.length) {
+ palloc(&result, init.length - max);
+ *result.bitmap = rem;
+ } else if(divisor.length) {
+ palloc(&result, divisor.length);
+ *result.bitmap = rem;
+ }
+ } else {
+ /* allocate maximum size plus one word for shifted divisors and one word containing zero.
+ * This also ensures that result[1] exists
+ */
+ palloc(&result, (init.length > divisor.length ? init.length : divisor.length) + (unsigned long) (BMP_BIT << 1));
+ /*if there is content in init, there will be an extra word in result to clear it */
+ psum(&result, init, 0UL);
+ if(max)
+ *result.bitmap ^= *bptr++;
+ for(iter = 0UL, ofs = 0UL; iter < max; ++iter, probe >>= 1) {
+ if(!probe) {
+ probe = ~(~BMP_C(0) >> 1);
+ ofs = 0UL;
+ sptr = rptr = result.bitmap;
+ ++sptr;
+ /* iter < max <= message.length, so bptr is valid
+ * shift result one word to the left, splicing in a message word
+ * and clearing the last active word
+ */
+ *rptr++ = *sptr++ ^ *bptr++;
+ for(resiter = (unsigned long) (BMP_BIT << 1); resiter < result.length; resiter += BMP_BIT)
+ *rptr++ = *sptr++;
+ }
+ ++ofs;
+ if(*result.bitmap & probe)
+ psum(&result, divisor, ofs);
+ }
+ rptr = result.bitmap;
+ ++rptr;
+ while(bptr < eptr)
+ *rptr++ ^= *bptr++;
+ /* 0 <= ofs <= BMP_BIT, location of the first bit of the result */
+ pshift(&result, result, 0UL, ofs, (init.length > max + divisor.length ? init.length - max - divisor.length : 0UL) + divisor.length + ofs, 0UL);
+ }
+ psum(&result, xorout, 0UL);
+ return(result);
+}
+
+int
+piter(poly_t *poly) {
+ /* Replace poly with the 'next' polynomial of equal length.
+ * Returns zero if the next polynomial is all zeroes, a nonzero
+ * value otherwise.
+ * Does not clean poly.
+ */
+ bmp_t *bptr;
+ if(!poly->length) return(0);
+
+ bptr = poly->bitmap + IDX(poly->length - 1UL);
+ *bptr += BMP_C(1) << OFS(poly->length - 1UL);
+ while(bptr != poly->bitmap && !*bptr)
+ ++(*--bptr);
+ return(*bptr != BMP_C(0));
+}
+
+void
+palloc(poly_t *poly, unsigned long length) {
+ /* Replaces poly with a CLEAN object of the specified length,
+ * consisting of all zeroes.
+ * It is safe to call with length = 0, in which case the object
+ * is freed.
+ * poly may or may not be WELL-FORMED.
+ * On exit, poly is CLEAN.
+ */
+ unsigned long size = SIZE(length);
+
+ poly->length = 0UL;
+ free(poly->bitmap);
+ poly->bitmap = NULL;
+ if(!length) return;
+ if(!size)
+ size = IDX(length) + 1UL;
+ poly->bitmap = (bmp_t *) calloc(size, sizeof(bmp_t));
+ if(poly->bitmap) {
+ poly->length = length;
+ } else
+ uerror("cannot allocate memory for poly");
+}
+
+void
+pfree(poly_t *poly) {
+ /* Frees poly's bitmap storage and sets poly equal to the empty
+ * polynomial (PZERO).
+ * poly may or may not be WELL-FORMED.
+ * On exit, poly is CLEAN.
+ */
+
+ /* palloc(poly, 0UL); */
+
+ poly->length = 0UL;
+ free(poly->bitmap);
+ poly->bitmap = NULL;
+}
+
+void
+praloc(poly_t *poly, unsigned long length) {
+ /* Trims or extends poly to length at the right edge, appending
+ * zeroes if necessary.
+ * On entry, poly may or may not be WELL-FORMED.
+ * On exit, poly is CLEAN.
+ */
+ unsigned long oldsize, size = SIZE(length);
+ if(!poly) return;
+ if(!length) {
+ poly->length = 0UL;
+ free(poly->bitmap);
+ poly->bitmap = NULL;
+ return;
+ }
+ if(!size)
+ size = IDX(length) + 1UL;
+ if(!poly->bitmap)
+ poly->length = 0UL;
+ oldsize = SIZE(poly->length);
+ if(oldsize != size)
+ /* reallocate if array pointer is null or array resized */
+ poly->bitmap = (bmp_t *) realloc((void *)poly->bitmap, size * sizeof(bmp_t));
+ if(poly->bitmap) {
+ if(poly->length < length) {
+ /* poly->length >= 0, length > 0, size > 0.
+ * poly expanded. clear old last word and all new words
+ */
+ if(LOFS(poly->length))
+ poly->bitmap[oldsize - 1UL] &= ~(~BMP_C(0) >> LOFS(poly->length));
+ while(oldsize < size)
+ poly->bitmap[oldsize++] = BMP_C(0);
+ } else if(LOFS(length))
+ /* poly->length >= length > 0.
+ * poly shrunk. clear new last word
+ */
+ poly->bitmap[size - 1UL] &= ~(~BMP_C(0) >> LOFS(length));
+ poly->length = length;
+ } else
+ uerror("cannot reallocate memory for poly");
+}
+
+int
+pmpar(const poly_t poly, const poly_t mask) {
+ /* Return even parity of poly masked with mask.
+ * Poly and mask must be CLEAN.
+ */
+ bmp_t res = BMP_C(0);
+ int i = BMP_SUB;
+ const bmp_t *pptr = poly.bitmap, *mptr = mask.bitmap;
+ const bmp_t *const pend = poly.bitmap + SIZE(poly.length);
+ const bmp_t *const mend = mask.bitmap + SIZE(mask.length);
+
+ while(pptr < pend && mptr < mend)
+ res ^= *pptr++ & *mptr++;
+ do
+ res ^= res >> i;
+ while(i >>= 1);
+
+ return((int) (res & BMP_C(1)));
+}
+
+int
+pident(const poly_t a, const poly_t b) {
+ /* Return nonzero if a and b have the same length
+ * and point to the same bitmap.
+ * a and b need not be CLEAN.
+ */
+ return(a.length == b.length && a.bitmap == b.bitmap);
+}
+
+/* Private functions */
+
+static bmp_t
+getwrd(const poly_t poly, unsigned long iter) {
+ /* Fetch unaligned word from poly where LSB of result is
+ * bit iter of the bitmap (counting from zero). If iter exceeds
+ * the length of poly then zeroes are appended as necessary.
+ * Factored from ptostr().
+ * poly must be CLEAN.
+ */
+ bmp_t accu = BMP_C(0);
+ unsigned long idx, size;
+ int ofs;
+
+ idx = IDX(iter);
+ ofs = OFS(iter);
+ size = SIZE(poly.length);
+
+ if(idx < size)
+ accu |= poly.bitmap[idx] >> ofs;
+ if(idx && idx <= size && ofs > 0)
+ accu |= poly.bitmap[idx - 1UL] << (BMP_BIT - ofs);
+ return(accu);
+}
+
+static bmp_t
+rev(bmp_t accu, int bits) {
+ /* Returns the bitmap word argument with the given number of
+ * least significant bits reversed and the rest cleared.
+ */
+ static const unsigned char revtab[256] = {
+ 0x00,0x80,0x40,0xc0,0x20,0xa0,0x60,0xe0,
+ 0x10,0x90,0x50,0xd0,0x30,0xb0,0x70,0xf0,
+ 0x08,0x88,0x48,0xc8,0x28,0xa8,0x68,0xe8,
+ 0x18,0x98,0x58,0xd8,0x38,0xb8,0x78,0xf8,
+ 0x04,0x84,0x44,0xc4,0x24,0xa4,0x64,0xe4,
+ 0x14,0x94,0x54,0xd4,0x34,0xb4,0x74,0xf4,
+ 0x0c,0x8c,0x4c,0xcc,0x2c,0xac,0x6c,0xec,
+ 0x1c,0x9c,0x5c,0xdc,0x3c,0xbc,0x7c,0xfc,
+ 0x02,0x82,0x42,0xc2,0x22,0xa2,0x62,0xe2,
+ 0x12,0x92,0x52,0xd2,0x32,0xb2,0x72,0xf2,
+ 0x0a,0x8a,0x4a,0xca,0x2a,0xaa,0x6a,0xea,
+ 0x1a,0x9a,0x5a,0xda,0x3a,0xba,0x7a,0xfa,
+ 0x06,0x86,0x46,0xc6,0x26,0xa6,0x66,0xe6,
+ 0x16,0x96,0x56,0xd6,0x36,0xb6,0x76,0xf6,
+ 0x0e,0x8e,0x4e,0xce,0x2e,0xae,0x6e,0xee,
+ 0x1e,0x9e,0x5e,0xde,0x3e,0xbe,0x7e,0xfe,
+ 0x01,0x81,0x41,0xc1,0x21,0xa1,0x61,0xe1,
+ 0x11,0x91,0x51,0xd1,0x31,0xb1,0x71,0xf1,
+ 0x09,0x89,0x49,0xc9,0x29,0xa9,0x69,0xe9,
+ 0x19,0x99,0x59,0xd9,0x39,0xb9,0x79,0xf9,
+ 0x05,0x85,0x45,0xc5,0x25,0xa5,0x65,0xe5,
+ 0x15,0x95,0x55,0xd5,0x35,0xb5,0x75,0xf5,
+ 0x0d,0x8d,0x4d,0xcd,0x2d,0xad,0x6d,0xed,
+ 0x1d,0x9d,0x5d,0xdd,0x3d,0xbd,0x7d,0xfd,
+ 0x03,0x83,0x43,0xc3,0x23,0xa3,0x63,0xe3,
+ 0x13,0x93,0x53,0xd3,0x33,0xb3,0x73,0xf3,
+ 0x0b,0x8b,0x4b,0xcb,0x2b,0xab,0x6b,0xeb,
+ 0x1b,0x9b,0x5b,0xdb,0x3b,0xbb,0x7b,0xfb,
+ 0x07,0x87,0x47,0xc7,0x27,0xa7,0x67,0xe7,
+ 0x17,0x97,0x57,0xd7,0x37,0xb7,0x77,0xf7,
+ 0x0f,0x8f,0x4f,0xcf,0x2f,0xaf,0x6f,0xef,
+ 0x1f,0x9f,0x5f,0xdf,0x3f,0xbf,0x7f,0xff
+ };
+ bmp_t result = BMP_C(0);
+ while(bits > 8) {
+ bits -= 8;
+ result = result << 8 | revtab[accu & 0xff];
+ accu >>= 8;
+ }
+ result = result << bits | (bmp_t) (revtab[accu & 0xff] >> (8 - bits));
+ return(result);
+}
+
+static void
+prhex(char **spp, bmp_t bits, int flags, int bperhx) {
+ /* Appends a hexadecimal string representing the bperhx least
+ * significant bits of bits to an external string.
+ * spp points to a character pointer that in turn points to the
+ * end of a hex string being built. prhex() advances this
+ * second pointer by the number of characters written.
+ * The unused MSBs of bits MUST be cleared.
+ * Set P_UPPER in flags to write A-F in uppercase.
+ */
+ static const char hex[] = "0123456789abcdef0123456789ABCDEF";
+ const int upper = (flags & P_UPPER ? 0x10 : 0);
+ while(bperhx > 0) {
+ bperhx -= ((bperhx + 3) & 3) + 1;
+ *(*spp)++ = hex[(bits >> bperhx & BMP_C(0xf)) | upper];
+ }
+}
--- /dev/null
+/* reveng.c
+ * Greg Cook, 9/Apr/2015
+ */
+
+/* CRC RevEng, an arbitrary-precision CRC calculator and algorithm finder
+ * Copyright (C) 2010, 2011, 2012, 2013, 2014, 2015 Gregory Cook
+ *
+ * This file is part of CRC RevEng.
+ *
+ * CRC RevEng is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * CRC RevEng is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with CRC RevEng. If not, see <http://www.gnu.org/licenses/>.
+ */
+
+/* 2013-09-16: calini(), calout() work on shortest argument
+ * 2013-06-11: added sequence number to uprog() calls
+ * 2013-02-08: added polynomial range search
+ * 2013-01-18: refactored model checking to pshres(); renamed chkres()
+ * 2012-05-24: efficiently build Init contribution string
+ * 2012-05-24: removed broken search for crossed-endian algorithms
+ * 2012-05-23: rewrote engini() after Ewing; removed modini()
+ * 2011-01-17: fixed ANSI C warnings
+ * 2011-01-08: fixed calini(), modini() caters for crossed-endian algos
+ * 2011-01-04: renamed functions, added calini(), factored pshres();
+ * rewrote engini() and implemented quick Init search
+ * 2011-01-01: reveng() initialises terminating entry, addparms()
+ * initialises all fields
+ * 2010-12-26: renamed CRC RevEng. right results, rejects polys faster
+ * 2010-12-24: completed, first tests (unsuccessful)
+ * 2010-12-21: completed modulate(), partial sketch of reveng()
+ * 2010-12-19: started reveng
+ */
+
+/* reveng() can in theory be modified to search for polynomials shorter
+ * than the full width as well, but this imposes a heavy time burden on
+ * the full width search, which is the primary use case, as well as
+ * complicating the search range function introduced in version 1.1.0.
+ * It is more effective to search for each shorter width directly.
+ */
+
+#include <stdlib.h>
+
+#define FILE void
+#include "reveng.h"
+
+static poly_t *modpol(const poly_t init, int rflags, int args, const poly_t *argpolys);
+static void engini(int *resc, model_t **result, const poly_t divisor, int flags, int args, const poly_t *argpolys);
+static void calout(int *resc, model_t **result, const poly_t divisor, const poly_t init, int flags, int args, const poly_t *argpolys);
+static void calini(int *resc, model_t **result, const poly_t divisor, int flags, const poly_t xorout, int args, const poly_t *argpolys);
+static void chkres(int *resc, model_t **result, const poly_t divisor, const poly_t init, int flags, const poly_t xorout, int args, const poly_t *argpolys);
+
+static const poly_t pzero = PZERO;
+
+model_t *
+reveng(const model_t *guess, const poly_t qpoly, int rflags, int args, const poly_t *argpolys) {
+ /* Complete the parameters of a model by calculation or brute search. */
+ poly_t *pworks, *wptr, rem, gpoly;
+ model_t *result = NULL, *rptr;
+ int resc = 0;
+ unsigned long spin = 0, seq = 0;
+
+ if(~rflags & R_HAVEP) {
+ /* The poly is not known.
+ * Produce a list of differences between the arguments.
+ */
+ pworks = modpol(guess->init, rflags, args, argpolys);
+ if(!pworks || !plen(*pworks)) {
+ free(pworks);
+ goto requit;
+ }
+ /* Initialise the guessed poly to the starting value. */
+ gpoly = pclone(guess->spoly);
+ /* Clear the least significant term, to be set in the
+ * loop. qpoly does not need fixing as it is only
+ * compared with odd polys.
+ */
+ if(plen(gpoly))
+ pshift(&gpoly, gpoly, 0UL, 0UL, plen(gpoly) - 1UL, 1UL);
+
+ while(piter(&gpoly) && (~rflags & R_HAVEQ || pcmp(&gpoly, &qpoly) < 0)) {
+ /* For each possible poly of this size, try
+ * dividing all the differences in the list.
+ */
+ if(!(spin++ & R_SPMASK)) {
+ uprog(gpoly, guess->flags, seq++);
+ }
+ for(wptr = pworks; plen(*wptr); ++wptr) {
+ /* straight divide message by poly, don't multiply by x^n */
+ rem = pcrc(*wptr, gpoly, pzero, pzero, 0);
+ if(ptst(rem)) {
+ pfree(&rem);
+ break;
+ } else
+ pfree(&rem);
+ }
+ /* If gpoly divides all the differences, it is a
+ * candidate. Search for an Init value for this
+ * poly or if Init is known, log the result.
+ */
+ if(!plen(*wptr)) {
+ /* gpoly is a candidate poly */
+ if(rflags & R_HAVEI && rflags & R_HAVEX)
+ chkres(&resc, &result, gpoly, guess->init, guess->flags, guess->xorout, args, argpolys);
+ else if(rflags & R_HAVEI)
+ calout(&resc, &result, gpoly, guess->init, guess->flags, args, argpolys);
+ else if(rflags & R_HAVEX)
+ calini(&resc, &result, gpoly, guess->flags, guess->xorout, args, argpolys);
+ else
+ engini(&resc, &result, gpoly, guess->flags, args, argpolys);
+ }
+ if(!piter(&gpoly))
+ break;
+ }
+ /* Finished with gpoly and the differences list, free them.
+ */
+ pfree(&gpoly);
+ for(wptr = pworks; plen(*wptr); ++wptr)
+ pfree(wptr);
+ free(pworks);
+ }
+ else if(rflags & R_HAVEI && rflags & R_HAVEX)
+ /* All parameters are known! Submit the result if we get here */
+ chkres(&resc, &result, guess->spoly, guess->init, guess->flags, guess->xorout, args, argpolys);
+ else if(rflags & R_HAVEI)
+ /* Poly and Init are known, calculate XorOut */
+ calout(&resc, &result, guess->spoly, guess->init, guess->flags, args, argpolys);
+ else if(rflags & R_HAVEX)
+ /* Poly and XorOut are known, calculate Init */
+ calini(&resc, &result, guess->spoly, guess->flags, guess->xorout, args, argpolys);
+ else
+ /* Poly is known but not Init; search for Init. */
+ engini(&resc, &result, guess->spoly, guess->flags, args, argpolys);
+
+requit:
+ if(!(result = realloc(result, ++resc * sizeof(model_t))))
+ uerror("cannot reallocate result array");
+ rptr = result + resc - 1;
+ rptr->spoly = pzero;
+ rptr->init = pzero;
+ rptr->flags = 0;
+ rptr->xorout = pzero;
+ rptr->check = pzero;
+ rptr->name = NULL;
+
+ return(result);
+}
+
+static poly_t *
+modpol(const poly_t init, int rflags, int args, const poly_t *argpolys) {
+ /* Produce, in ascending length order, a list of differences
+ * between the arguments in the list by summing pairs of arguments.
+ * If R_HAVEI is not set in rflags, only pairs of equal length are
+ * summed.
+ * Otherwise, sums of right-aligned pairs are also returned, with
+ * the supplied init poly added to the leftmost terms of each
+ * poly of the pair.
+ */
+ poly_t work, swap, *result, *rptr, *iptr;
+ const poly_t *aptr, *bptr, *eptr = argpolys + args;
+ unsigned long alen, blen;
+
+ if(args < 2) return(NULL);
+
+ if(!(result = malloc(((((args - 1) * args) >> 1) + 1) * sizeof(poly_t))))
+ uerror("cannot allocate memory for codeword table");
+
+ rptr = result;
+
+ for(aptr = argpolys; aptr < eptr; ++aptr) {
+ alen = plen(*aptr);
+ for(bptr = aptr + 1; bptr < eptr; ++bptr) {
+ blen = plen(*bptr);
+ if(alen == blen) {
+ work = pclone(*aptr);
+ psum(&work, *bptr, 0UL);
+ } else if(rflags & R_HAVEI && alen < blen) {
+ work = pclone(*bptr);
+ psum(&work, *aptr, blen - alen);
+ psum(&work, init, 0UL);
+ psum(&work, init, blen - alen);
+ } else if(rflags & R_HAVEI /* && alen > blen */) {
+ work = pclone(*aptr);
+ psum(&work, *bptr, alen - blen);
+ psum(&work, init, 0UL);
+ psum(&work, init, alen - blen);
+ } else
+ work = pzero;
+
+ if(plen(work))
+ pnorm(&work);
+ if((blen = plen(work))) {
+ /* insert work into result[] in ascending order of length */
+ for(iptr = result; iptr < rptr; ++iptr) {
+ if(plen(work) < plen(*iptr)) {
+ swap = *iptr;
+ *iptr = work;
+ work = swap;
+ }
+ else if(plen(*iptr) == blen && !pcmp(&work, iptr)) {
+ pfree(&work);
+ work = *--rptr;
+ break;
+ }
+ }
+ *rptr++ = work;
+ }
+ }
+ }
+ *rptr = pzero;
+ return(result);
+}
+
+static void
+engini(int *resc, model_t **result, const poly_t divisor, int flags, int args, const poly_t *argpolys) {
+ /* Search for init values implied by the arguments.
+ * Method from: Ewing, Gregory C. (March 2010).
+ * "Reverse-Engineering a CRC Algorithm". Christchurch:
+ * University of Canterbury.
+ * <http://www.cosc.canterbury.ac.nz/greg.ewing/essays/
+ * CRC-Reverse-Engineering.html>
+ */
+ poly_t apoly = PZERO, bpoly, pone = PZERO, *mat, *jptr;
+ const poly_t *aptr, *bptr, *iptr;
+ unsigned long alen, blen, dlen, ilen, i, j;
+ int cy;
+
+ dlen = plen(divisor);
+
+ /* Allocate the CRC matrix */
+ if(!(mat = (poly_t *) malloc((dlen << 1) * sizeof(poly_t))))
+ uerror("cannot allocate memory for CRC matrix");
+
+ /* Find arguments of the two shortest lengths */
+ alen = blen = plen(*(aptr = bptr = iptr = argpolys));
+ for(++iptr; iptr < argpolys + args; ++iptr) {
+ ilen = plen(*iptr);
+ if(ilen < alen) {
+ bptr = aptr; blen = alen;
+ aptr = iptr; alen = ilen;
+ } else if(ilen > alen && (aptr == bptr || ilen < blen)) {
+ bptr = iptr; blen = ilen;
+ }
+ }
+ if(aptr == bptr) {
+ /* if no arguments are suitable, calculate Init with an
+ * assumed XorOut of 0. Create a padded XorOut
+ */
+ palloc(&apoly, dlen);
+ calini(resc, result, divisor, flags, apoly, args, argpolys);
+ pfree(&apoly);
+ return;
+ }
+
+ /* Find the potential contribution of the bottom bit of Init */
+ palloc(&pone, 1UL);
+ piter(&pone);
+ if(blen < (dlen << 1)) {
+ palloc(&apoly, dlen); /* >= 1 */
+ psum(&apoly, pone, (dlen << 1) - 1UL - blen); /* >= 0 */
+ psum(&apoly, pone, (dlen << 1) - 1UL - alen); /* >= 1 */
+ } else {
+ palloc(&apoly, blen - dlen + 1UL); /* > dlen */
+ psum(&apoly, pone, 0UL);
+ psum(&apoly, pone, blen - alen); /* >= 1 */
+ }
+ if(plen(apoly) > dlen) {
+ mat[dlen] = pcrc(apoly, divisor, pzero, pzero, 0);
+ pfree(&apoly);
+ } else {
+ mat[dlen] = apoly;
+ }
+
+ /* Find the actual contribution of Init */
+ apoly = pcrc(*aptr, divisor, pzero, pzero, 0);
+ bpoly = pcrc(*bptr, divisor, pzero, apoly, 0);
+
+ /* Populate the matrix */
+ palloc(&apoly, 1UL);
+ for(jptr=mat; jptr<mat+dlen; ++jptr)
+ *jptr = pzero;
+ for(iptr = jptr++; jptr < mat + (dlen << 1); iptr = jptr++)
+ *jptr = pcrc(apoly, divisor, *iptr, pzero, P_MULXN);
+ pfree(&apoly);
+
+ /* Transpose the matrix, augment with the Init contribution
+ * and convert to row echelon form
+ */
+ for(i=0UL; i<dlen; ++i) {
+ apoly = pzero;
+ iptr = mat + (dlen << 1);
+ for(j=0UL; j<dlen; ++j)
+ ppaste(&apoly, *--iptr, i, j, j + 1UL, dlen + 1UL);
+ if(ptst(apoly))
+ ppaste(&apoly, bpoly, i, dlen, dlen + 1UL, dlen + 1UL);
+ j = pfirst(apoly);
+ while(j < dlen && !pident(mat[j], pzero)) {
+ psum(&apoly, mat[j], 0UL); /* pfirst(apoly) > j */
+ j = pfirst(apoly);
+ }
+ if(j < dlen)
+ mat[j] = apoly; /* pident(mat[j], pzero) || pfirst(mat[j]) == j */
+ else
+ pfree(&apoly);
+ }
+ palloc(&bpoly, dlen + 1UL);
+ psum(&bpoly, pone, dlen);
+
+ /* Iterate through all solutions */
+ do {
+ /* Solve the matrix by Gaussian elimination.
+ * The parity of the result, masked by each row, should be even.
+ */
+ cy = 1;
+ apoly = pclone(bpoly);
+ jptr = mat + dlen;
+ for(i=0UL; i<dlen; ++i) {
+ /* Compute next bit of Init */
+ if(pmpar(apoly, *--jptr))
+ psum(&apoly, pone, dlen - 1UL - i);
+ /* Toggle each zero row with carry, for next iteration */
+ if(cy) {
+ if(pident(*jptr, pzero)) {
+ /* 0 to 1, no carry */
+ *jptr = bpoly;
+ cy = 0;
+ } else if(pident(*jptr, bpoly)) {
+ /* 1 to 0, carry forward */
+ *jptr = pzero;
+ }
+ }
+ }
+
+ /* Trim the augment mask bit */
+ praloc(&apoly, dlen);
+
+ /* Test the Init value and add to results if correct */
+ calout(resc, result, divisor, apoly, flags, args, argpolys);
+ pfree(&apoly);
+ } while(!cy);
+ pfree(&pone);
+ pfree(&bpoly);
+
+ /* Free the matrix. */
+ for(jptr=mat; jptr < mat + (dlen << 1); ++jptr)
+ pfree(jptr);
+ free(mat);
+}
+
+static void
+calout(int *resc, model_t **result, const poly_t divisor, const poly_t init, int flags, int args, const poly_t *argpolys) {
+ /* Calculate Xorout, check it against all the arguments and
+ * add to results if consistent.
+ */
+ poly_t xorout;
+ const poly_t *aptr, *iptr;
+ unsigned long alen, ilen;
+
+ if(args < 1) return;
+
+ /* find argument of the shortest length */
+ alen = plen(*(aptr = iptr = argpolys));
+ for(++iptr; iptr < argpolys + args; ++iptr) {
+ ilen = plen(*iptr);
+ if(ilen < alen) {
+ aptr = iptr; alen = ilen;
+ }
+ }
+
+ xorout = pcrc(*aptr, divisor, init, pzero, 0);
+ /* On little-endian algorithms, the calculations yield
+ * the reverse of the actual xorout: in the Williams
+ * model, the refout stage intervenes between init and
+ * xorout.
+ */
+ if(flags & P_REFOUT)
+ prev(&xorout);
+
+ /* Submit the model to the results table.
+ * Could skip the shortest argument but we wish to check our
+ * calculation.
+ */
+ chkres(resc, result, divisor, init, flags, xorout, args, argpolys);
+ pfree(&xorout);
+}
+
+static void
+calini(int *resc, model_t **result, const poly_t divisor, int flags, const poly_t xorout, int args, const poly_t *argpolys) {
+ /* Calculate Init, check it against all the arguments and add to
+ * results if consistent.
+ */
+ poly_t rcpdiv, rxor, arg, init;
+ const poly_t *aptr, *iptr;
+ unsigned long alen, ilen;
+
+ if(args < 1) return;
+
+ /* find argument of the shortest length */
+ alen = plen(*(aptr = iptr = argpolys));
+ for(++iptr; iptr < argpolys + args; ++iptr) {
+ ilen = plen(*iptr);
+ if(ilen < alen) {
+ aptr = iptr; alen = ilen;
+ }
+ }
+
+ rcpdiv = pclone(divisor);
+ prcp(&rcpdiv);
+ /* If the algorithm is reflected, an ordinary CRC requires the
+ * model's XorOut to be reversed, as XorOut follows the RefOut
+ * stage. To reverse the CRC calculation we need rxor to be the
+ * mirror image of the forward XorOut.
+ */
+ rxor = pclone(xorout);
+ if(~flags & P_REFOUT)
+ prev(&rxor);
+ arg = pclone(*aptr);
+ prev(&arg);
+
+ init = pcrc(arg, rcpdiv, rxor, pzero, 0);
+ pfree(&arg);
+ pfree(&rxor);
+ pfree(&rcpdiv);
+ prev(&init);
+
+ /* Submit the model to the results table.
+ * Could skip the shortest argument but we wish to check our
+ * calculation.
+ */
+ chkres(resc, result, divisor, init, flags, xorout, args, argpolys);
+ pfree(&init);
+}
+
+static void
+chkres(int *resc, model_t **result, const poly_t divisor, const poly_t init, int flags, const poly_t xorout, int args, const poly_t *argpolys) {
+ /* Checks a model against the argument list, and adds to the
+ * external results table if consistent.
+ * Extends the result array and update the external pointer if
+ * necessary.
+ */
+ model_t *rptr;
+ poly_t xor, crc;
+ const poly_t *aptr = argpolys, *const eptr = argpolys + args;
+
+ /* If the algorithm is reflected, an ordinary CRC requires the
+ * model's XorOut to be reversed, as XorOut follows the RefOut
+ * stage.
+ */
+ xor = pclone(xorout);
+ if(flags & P_REFOUT)
+ prev(&xor);
+
+ for(; aptr < eptr; ++aptr) {
+ crc = pcrc(*aptr, divisor, init, xor, 0);
+ if(ptst(crc)) {
+ pfree(&crc);
+ break;
+ } else {
+ pfree(&crc);
+ }
+ }
+ pfree(&xor);
+ if(aptr != eptr) return;
+
+ if(!(*result = realloc(*result, ++*resc * sizeof(model_t))))
+ uerror("cannot reallocate result array");
+
+ rptr = *result + *resc - 1;
+ rptr->spoly = pclone(divisor);
+ rptr->init = pclone(init);
+ rptr->flags = flags;
+ rptr->xorout = pclone(xorout);
+ rptr->name = NULL;
+
+ /* compute check value for this model */
+ mcheck(rptr);
+
+ /* callback to notify new model */
+ ufound(rptr);
+}
--- /dev/null
+/* reveng.h
+ * Greg Cook, 9/Apr/2015
+ */
+
+/* CRC RevEng, an arbitrary-precision CRC calculator and algorithm finder
+ * Copyright (C) 2010, 2011, 2012, 2013, 2014, 2015 Gregory Cook
+ *
+ * This file is part of CRC RevEng.
+ *
+ * CRC RevEng is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * CRC RevEng is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with CRC RevEng. If not, see <http://www.gnu.org/licenses/>.
+ */
+
+#ifndef REVENG_H
+#define REVENG_H 1
+
+/* Configuration options */
+
+#include "config.h"
+
+#ifndef BMP_T
+# error config.h: BMP_T must be defined as unsigned long or a longer unsigned type
+#endif
+
+#ifndef BMP_C
+# error config.h: BMP_C() must define a BMP_T constant
+#endif
+
+#if !defined PRESETS && !defined BMPMACRO
+# undef BMP_BIT
+# undef BMP_SUB
+#endif
+
+#undef BMP_POF2
+
+#ifdef BMP_BIT
+# ifndef BMP_SUB
+# error config.h: BMP_SUB must be defined as the highest power of two that is strictly less than BMP_BIT
+# elif BMP_BIT < 32
+# error config.h: BMP_BIT must be at least 32
+# elif BMP_SUB < 16
+# error config.h: BMP_SUB must be at least 16
+# elif (BMP_SUB >= BMP_BIT || BMP_SUB << 1 < BMP_BIT || BMP_SUB & (BMP_SUB - 1))
+# error config.h: BMP_SUB must be defined as the highest power of two that is strictly less than BMP_BIT
+# else /* BMP_SUB */
+# define SETBMP()
+# endif /* BMP_SUB */
+# if BMP_BIT == 32
+# define BMP_POF2 5
+# elif BMP_BIT == 64
+# define BMP_POF2 6
+# elif BMP_BIT == 128
+# define BMP_POF2 7
+# elif BMP_BIT == 256
+# define BMP_POF2 8
+# elif BMP_BIT == 512
+# define BMP_POF2 9
+# elif BMP_BIT == 1024
+# define BMP_POF2 10
+# elif BMP_BIT == 2048
+# define BMP_POF2 11
+# elif BMP_BIT == 4096
+# define BMP_POF2 12
+# elif BMP_BIT == 8192
+# define BMP_POF2 13
+# elif BMP_BIT == 16384
+# define BMP_POF2 14
+# elif BMP_BIT == 32768
+# define BMP_POF2 15
+# elif BMP_BIT == 65536
+# define BMP_POF2 16
+/* may extend list as required */
+# elif (BMP_BIT & (BMP_BIT - 1)) == 0
+# define BMP_POF2 1
+# endif
+#else /* BMP_BIT */
+# define BMP_BIT bmpbit
+# define BMP_SUB bmpsub
+# define SETBMP() setbmp()
+#endif /* BMP_BIT */
+
+/* Global definitions */
+
+/* CRC RevEng version string */
+#define VERSION "1.3.0"
+
+/* bmpbit.c */
+typedef BMP_T bmp_t;
+
+extern int bmpbit, bmpsub;
+extern void setbmp(void);
+
+/* poly.c */
+#define P_REFIN 1
+#define P_REFOUT 2
+#define P_MULXN 4
+#define P_RTJUST 8
+#define P_UPPER 16
+#define P_SPACE 32
+#define P_LTLBYT 64
+#define P_DIRECT 128
+
+/* default flags */
+#define P_BE (P_RTJUST | P_MULXN)
+#define P_LE (P_REFIN | P_REFOUT | P_MULXN)
+#define P_BELE (P_REFOUT | P_MULXN)
+#define P_LEBE (P_REFIN | P_RTJUST | P_MULXN)
+
+/* A poly_t constant representing the polynomial 0. */
+#define PZERO {0UL, (bmp_t *) 0}
+
+typedef struct {
+ unsigned long length; /* number of significant bits */
+ bmp_t *bitmap; /* bitmap, MSB first, */
+ /* left-justified in each word */
+} poly_t;
+
+extern poly_t filtop(FILE *input, unsigned long length, int flags, int bperhx);
+extern poly_t strtop(const char *string, int flags, int bperhx);
+extern char *ptostr(const poly_t poly, int flags, int bperhx);
+extern char *pxsubs(const poly_t poly, int flags, int bperhx, unsigned long start, unsigned long end);
+extern poly_t pclone(const poly_t poly);
+extern void pcpy(poly_t *dest, const poly_t src);
+extern void pcanon(poly_t *poly);
+extern void pnorm(poly_t *poly);
+extern void psnorm(poly_t *poly);
+extern void pchop(poly_t *poly);
+extern void pkchop(poly_t *poly);
+extern unsigned long plen(const poly_t poly);
+extern int pcmp(const poly_t *a, const poly_t *b);
+extern int psncmp(const poly_t *a, const poly_t *b);
+extern int ptst(const poly_t poly);
+extern unsigned long pfirst(const poly_t poly);
+extern unsigned long plast(const poly_t poly);
+extern poly_t psubs(const poly_t src, unsigned long head, unsigned long start, unsigned long end, unsigned long tail);
+extern void pright(poly_t *poly, unsigned long length);
+extern void pshift(poly_t *dest, const poly_t src, unsigned long head, unsigned long start, unsigned long end, unsigned long tail);
+extern void ppaste(poly_t *dest, const poly_t src, unsigned long skip, unsigned long seek, unsigned long end, unsigned long fulllength);
+extern void pdiff(poly_t *dest, const poly_t src, unsigned long ofs);
+extern void psum(poly_t *dest, const poly_t src, unsigned long ofs);
+extern void prev(poly_t *poly);
+extern void prevch(poly_t *poly, int bperhx);
+extern void prcp(poly_t *poly);
+extern void pinv(poly_t *poly);
+extern poly_t pmod(const poly_t dividend, const poly_t divisor);
+extern poly_t pcrc(const poly_t message, const poly_t divisor, const poly_t init, const poly_t xorout, int flags);
+extern int piter(poly_t *poly);
+extern void palloc(poly_t *poly, unsigned long length);
+extern void pfree(poly_t *poly);
+extern void praloc(poly_t *poly, unsigned long length);
+extern int pmpar(const poly_t poly, const poly_t mask);
+extern int pident(const poly_t a, const poly_t b);
+
+/* model.c */
+#define M_OVERWR 256
+
+typedef struct {
+ poly_t spoly; /* polynomial with highest-order term removed. length determines CRC width */
+ poly_t init; /* initial register value. length == poly.length */
+ int flags; /* P_REFIN and P_REFOUT indicate reflected input/output */
+ poly_t xorout; /* final register XOR mask. length == poly.length */
+ poly_t check; /* optional check value, the CRC of the UTF-8 string "123456789" */
+ const char *name; /* optional canonical name of the model */
+} model_t;
+
+extern void mcpy(model_t *dest, const model_t *src);
+extern void mfree(model_t *model);
+extern int mcmp(const model_t *a, const model_t *b);
+extern int mbynam(model_t *dest, const char *key);
+extern void mbynum(model_t *dest, int num);
+extern int mcount(void);
+extern char *mnames(void);
+extern char *mtostr(const model_t *model);
+extern void mmatch(model_t *model, int flags);
+extern void mcanon(model_t *model);
+extern void mcheck(model_t *model);
+extern void mrev(model_t *model);
+extern void mnovel(model_t *model);
+
+/* reveng.c */
+#define R_HAVEP 512
+#define R_HAVEI 1024
+#define R_HAVERI 2048
+#define R_HAVERO 4096
+#define R_HAVEX 8192
+#define R_HAVEQ 16384
+
+#define R_SPMASK 0x7FFFFFFUL
+
+extern model_t *reveng(const model_t *guess, const poly_t qpoly, int rflags, int args, const poly_t *argpolys);
+
+/* cli.c */
+#define C_INFILE 1
+#define C_FORCE 2
+#define C_RESULT 4
+
+#define BUFFER 32768
+
+extern int reveng_main(int argc, char *argv[]);
+extern void ufound(const model_t *model);
+extern void uerror(const char *msg);
+extern void uprog(const poly_t gpoly, int flags, unsigned long seq);
+
+#endif /* REVENG_H */
projects / proxmark3-svn / commitdiff