From fe81b4781103a51117b904681ad2c259bf16c084 Mon Sep 17 00:00:00 2001 From: marshmellow42 Date: Sat, 6 Jun 2015 01:09:54 -0400 Subject: [PATCH] add reveng-1.30 new command menu: crc help crc calc crc calc -h for help on command set --- client/Makefile | 10 +- client/cmdcrc.c | 52 ++ client/cmdcrc.h | 16 + client/cmdmain.c | 9 +- client/cmdmain.h | 4 + client/reveng/bmpbit.c | 86 +++ client/reveng/cli.c | 599 ++++++++++++++++++++ client/reveng/config.h | 89 +++ client/reveng/getopt.c | 81 +++ client/reveng/getopt.h | 25 + client/reveng/model.c | 823 +++++++++++++++++++++++++++ client/reveng/poly.c | 1195 ++++++++++++++++++++++++++++++++++++++++ client/reveng/reveng.c | 488 ++++++++++++++++ client/reveng/reveng.h | 214 +++++++ 14 files changed, 3685 insertions(+), 6 deletions(-) create mode 100644 client/cmdcrc.c create mode 100644 client/cmdcrc.h create mode 100644 client/reveng/bmpbit.c create mode 100644 client/reveng/cli.c create mode 100644 client/reveng/config.h create mode 100644 client/reveng/getopt.c create mode 100644 client/reveng/getopt.h create mode 100644 client/reveng/model.c create mode 100644 client/reveng/poly.c create mode 100644 client/reveng/reveng.c create mode 100644 client/reveng/reveng.h diff --git a/client/Makefile b/client/Makefile index d7126da6..bd8b891f 100644 --- a/client/Makefile +++ b/client/Makefile @@ -84,7 +84,7 @@ CMDSRCS = nonce2key/crapto1.c\ cmdhflegic.c \ cmdhficlass.c \ cmdhfmf.c \ - cmdhfmfu.c \ + cmdhfmfu.c \ cmdhw.c \ cmdlf.c \ cmdlfio.c \ @@ -103,7 +103,13 @@ CMDSRCS = nonce2key/crapto1.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) diff --git a/client/cmdcrc.c b/client/cmdcrc.c new file mode 100644 index 00000000..22eed561 --- /dev/null +++ b/client/cmdcrc.c @@ -0,0 +1,52 @@ +//----------------------------------------------------------------------------- +// Copyright (C) 2015 iceman +// +// 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 +#include +#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; +} diff --git a/client/cmdcrc.h b/client/cmdcrc.h new file mode 100644 index 00000000..c37ba2b1 --- /dev/null +++ b/client/cmdcrc.h @@ -0,0 +1,16 @@ +//----------------------------------------------------------------------------- +// Copyright (C) 2015 iceman +// +// 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 diff --git a/client/cmdmain.c b/client/cmdmain.c index 512aa13c..0cc578f6 100644 --- a/client/cmdmain.c +++ b/client/cmdmain.c @@ -25,6 +25,7 @@ #include "cmdmain.h" #include "util.h" #include "cmdscript.h" +#include "cmdcrc.h" unsigned int current_command = CMD_UNKNOWN; @@ -33,7 +34,6 @@ static int CmdHelp(const char *Cmd); 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 @@ -43,11 +43,12 @@ static int cmd_tail;//Starts as 0 static command_t CommandTable[] = { {"help", CmdHelp, 1, "This help. Use ' 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} diff --git a/client/cmdmain.h b/client/cmdmain.h index 0cf2b35d..aa87052c 100644 --- a/client/cmdmain.h +++ b/client/cmdmain.h @@ -19,4 +19,8 @@ bool WaitForResponseTimeout(uint32_t cmd, UsbCommand* response, size_t ms_timeou 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 diff --git a/client/reveng/bmpbit.c b/client/reveng/bmpbit.c new file mode 100644 index 00000000..39a29e61 --- /dev/null +++ b/client/reveng/bmpbit.c @@ -0,0 +1,86 @@ +/* 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 . + */ + +#ifdef BMPTST +# include +# include +#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 */ diff --git a/client/reveng/cli.c b/client/reveng/cli.c new file mode 100644 index 00000000..a24445db --- /dev/null +++ b/client/reveng/cli.c @@ -0,0 +1,599 @@ +/* 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 . + */ + +/* 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 +#include +#include "getopt.h" +#ifdef _WIN32 +# include +# include +# 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 \n"); +} diff --git a/client/reveng/config.h b/client/reveng/config.h new file mode 100644 index 00000000..88957e8c --- /dev/null +++ b/client/reveng/config.h @@ -0,0 +1,89 @@ +/* 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 . + */ + +#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 */ diff --git a/client/reveng/getopt.c b/client/reveng/getopt.c new file mode 100644 index 00000000..55d8e8c5 --- /dev/null +++ b/client/reveng/getopt.c @@ -0,0 +1,81 @@ +/*---------------------------------------------------------------------- + + 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; + } +} diff --git a/client/reveng/getopt.h b/client/reveng/getopt.h new file mode 100644 index 00000000..e9a83540 --- /dev/null +++ b/client/reveng/getopt.h @@ -0,0 +1,25 @@ +/* + 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); diff --git a/client/reveng/model.c b/client/reveng/model.c new file mode 100644 index 00000000..2d45b2fe --- /dev/null +++ b/client/reveng/model.c @@ -0,0 +1,823 @@ +/* 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 . + */ + +/* 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 +#include +#include +#include +#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; +} diff --git a/client/reveng/poly.c b/client/reveng/poly.c new file mode 100644 index 00000000..1e22b8d2 --- /dev/null +++ b/client/reveng/poly.c @@ -0,0 +1,1195 @@ +/* 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 . + */ + +/* 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 +#include +#include +#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; idxbitmap[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]; + } +} diff --git a/client/reveng/reveng.c b/client/reveng/reveng.c new file mode 100644 index 00000000..3c6da126 --- /dev/null +++ b/client/reveng/reveng.c @@ -0,0 +1,488 @@ +/* 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 . + */ + +/* 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 + +#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. + * + */ + 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 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; ispoly = 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); +} diff --git a/client/reveng/reveng.h b/client/reveng/reveng.h new file mode 100644 index 00000000..48dcb31c --- /dev/null +++ b/client/reveng/reveng.h @@ -0,0 +1,214 @@ +/* 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 . + */ + +#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 */ -- 2.39.5