Hello community, here is the log from the commit of package reveng for openSUSE:Factory checked in at 2019-05-07 23:20:57 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ Comparing /work/SRC/openSUSE:Factory/reveng (Old) and /work/SRC/openSUSE:Factory/.reveng.new.5148 (New) ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ Package is "reveng" Tue May 7 23:20:57 2019 rev:4 rq:701415 version:2.0.0 Changes: -------- --- /work/SRC/openSUSE:Factory/reveng/reveng.changes 2019-05-02 19:19:41.225672886 +0200 +++ /work/SRC/openSUSE:Factory/.reveng.new.5148/reveng.changes 2019-05-07 23:20:59.177195914 +0200 @@ -1,0 +2,8 @@ +Mon May 6 17:56:07 UTC 2019 - Martin Hauke <mardnh@gmx.de> + +- Update to version 2.0.0 + * Much faster brute force search for generator polynomials if + the most compact difference between right-aligned arguments is + not more than twice the specified WIDTH. + +------------------------------------------------------------------- Old: ---- reveng-1.6.3.tar.xz New: ---- reveng-2.0.0.tar.xz ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ Other differences: ------------------ ++++++ reveng.spec ++++++ --- /var/tmp/diff_new_pack.J28pwR/_old 2019-05-07 23:20:59.845197516 +0200 +++ /var/tmp/diff_new_pack.J28pwR/_new 2019-05-07 23:20:59.849197525 +0200 @@ -18,7 +18,7 @@ Name: reveng -Version: 1.6.3 +Version: 2.0.0 Release: 0 Summary: An arbitrary-precision CRC calculator and algorithm finder License: GPL-3.0-or-later ++++++ reveng-1.6.3.tar.xz -> reveng-2.0.0.tar.xz ++++++ diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/reveng-1.6.3/CHANGES new/reveng-2.0.0/CHANGES --- old/reveng-1.6.3/CHANGES 2019-04-20 15:43:54.000000000 +0200 +++ new/reveng-2.0.0/CHANGES 2019-05-06 17:50:46.000000000 +0200 @@ -19,6 +19,11 @@ Revision history of CRC RevEng +2.0.0 6 May 2019 + * Much faster brute force search for generator polynomials if + the most compact difference between right-aligned arguments is + not more than twice the specified WIDTH. + 1.6.3 20 April 2019 * Added algorithm CRC-32/CD-ROM-EDC from the CRC Catalogue. * Model class of CRC-16/ARC, CRC-16/GSM changed to 'attested'. diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/reveng-1.6.3/README new/reveng-2.0.0/README --- old/reveng-1.6.3/README 2019-04-20 18:53:29.000000000 +0200 +++ new/reveng-2.0.0/README 2019-05-07 18:28:22.000000000 +0200 @@ -357,7 +357,9 @@ other whitespace), and if the digits are maskable in the system character encoding, as digits 0-9 are in ASCII, EBCDIC and UTF-8. This is because the lowest bits of - each byte are extracted as described above. + each byte are extracted as described above. The -e + switch can be used to verify that the messages are being + read as expected. -A OBITS Specifies the number of bits per character in output. -f @@ -535,11 +537,21 @@ then RefIn = True, RefOut = True. Crossed-endian algorithms are also uncommon and the program will not search for them. -To find the Poly value when Init is not known, there must be at least -two arguments having the same length. +The search for the Poly value proceeds much faster if the most compact +difference between any two right-aligned arguments is limited to a few +bytes in length. The search space is then determined by the length of +the difference, less the length of the generator polynomial. When the +CRC algorithm is wide, try for instance to obtain a pair of codewords +where the message portion differs only in the last byte or two. Even if +the difference at the end of the message portion is as long as the +checksum itself, the number of trial divisions needed is still cut in +half. -To find both the Init and XorOut values, there must be at least two -arguments having different lengths; otherwise there is only enough +To find the Poly value when Init is not known, at least two of the given +arguments must have the same length. + +To find both the Init and XorOut values, at least two of the given +arguments must have different lengths; otherwise there is only enough information to determine one value, given the other. If all arguments have the same length then, by default, CRC RevEng fixes XorOut at zero and calculates Init accordingly. (In hardware it is easier to set a @@ -574,6 +586,18 @@ (but excluding) a specified polynomial, from a specified polynomial upwards, or from one polynomial up to (but excluding) another. +Where a compact difference between arguments has been found, the +polynomial that is searched for is not the generator itself, but its +shorter cofactor whose value is determined by the difference between the +message portions of the arguments. Candidate generator polynomials are +then obtained by dividing the difference by the cofactor, and taking the +quotient when the remainder is zero. In such cases it is this cofactor +whose width and value is displayed in the progress messages; the width +is displayed for information purposes, but should not be entered at the +command line when restarting a search. Only the width of the CRC +algorithm itself should be entered, along with the polynomial value +printed in the most recent progress message. + Polynomial range searching is enabled using [-p POLY] -q QPOLY, where POLY and QPOLY are hex strings. -p POLY, if given, must precede -q QPOLY. To start searching at a polynomial, use -p POLY -q 0. To @@ -581,27 +605,29 @@ between two polynomial values, use -p POLY -q QPOLY. Range limiting does not apply to the initial check against the preset -models, or to Init or XorOut values, which are computed using a fast, -efficient algorithm. +models, or to Init or XorOut values, which are computed using Ewing's +fast, efficient algorithm. For example, to split a 32-bit search into four processes: - reveng -w 32 -q 40000000 -s c98964f6b9 a5fa49f2fd 13370aee7df0 - reveng -w 32 -p 40000000 -q 80000000 \ - -s c98964f6b9 a5fa49f2fd 13370aee7df0 - reveng -w 32 -p 80000000 -q c0000000 \ - -s c98964f6b9 a5fa49f2fd 13370aee7df0 - reveng -w 32 -p c0000000 -q 0 \ - -s c98964f6b9 a5fa49f2fd 13370aee7df0 + reveng -w 32 -q 40000000 -F -s \ + 123456789aaf946042 edcb8434325a439fbd 2468ace03238f64e + reveng -w 32 -p 40000000 -q 80000000 -F -s \ + 123456789aaf946042 edcb8434325a439fbd 2468ace03238f64e + reveng -w 32 -p 80000000 -q c0000000 -F -s \ + 123456789aaf946042 edcb8434325a439fbd 2468ace03238f64e + reveng -w 32 -p c0000000 -q 0 -F -s \ + 123456789aaf946042 edcb8434325a439fbd 2468ace03238f64e To continue an interrupted search: NB: If an either-endian search is stopped while RefIn/RefOut = False then it takes two further command lines to complete the search: one big-endian range search, and one little-endian full search. - reveng -w 32 -p 50000001 -q 0 -b \ - -s c98964f6b9 a5fa49f2fd 13370aee7df0 - reveng -w 32 -l -s c98964f6b9 a5fa49f2fd 13370aee7df0 + reveng -w 32 -p 50000001 -q 0 -b -F -s \ + 123456789aaf946042 edcb8434325a439fbd 2468ace03238f64e + reveng -w 32 -l -F -s \ + 123456789aaf946042 edcb8434325a439fbd 2468ace03238f64e The full list of search options is as follows: @@ -656,8 +682,9 @@ SEARCH EXAMPLES reveng -w 16 -l -F -s 31816b 32c16a 31326a0a - reveng -w 32 -p 04c11db7 -l -s c98964f6b9 a5fa49f2fd 13370aee7df0 reveng -w 32 -l -s c98964f6b9 a5fa49f2fd 13370aee7df0 + reveng -w 32 -l -F -s \ + 123456789aaf946042 edcb8434325a439fbd 2468ace03238f64e A comprehensive list is being compiled. diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/reveng-1.6.3/bin/armtubeos/README new/reveng-2.0.0/bin/armtubeos/README --- old/reveng-1.6.3/bin/armtubeos/README 2019-03-11 13:52:54.000000000 +0100 +++ new/reveng-2.0.0/bin/armtubeos/README 2019-05-07 17:47:43.000000000 +0200 @@ -1,5 +1,5 @@ System requirements of ARM Tube OS binary -Greg Cook, 11 March 2019 +Greg Cook, 7 May 2019 CRC RevEng has been tested on a 16MB SPROW ARM7TDMI Coprocessor running ARM Tube OS version 0.45, with OS 1.20 on the host. Installation on @@ -18,17 +18,24 @@ codes with bit 2 set (see RISC OS 3 Programmer's Reference Manual, volume 2, page 79) -On this hardware a brute force search for a 32-bit CRC algorithm, given -two 5-byte codewords and a 6-byte codeword, completes in approximately -22 hours with the cache enabled, or approximately 168 hours with the -cache disabled. Progress reports are returned at intervals of around -41 minutes or 5 hours 14 minutes, respectively. - -It is not possible to use *GO to re-execute the binary image after -loading: CRC RevEng does not receive the command line arguments -following the *GO address. +It is not possible to use *Go to re-execute the binary image after +loading; CRC RevEng does not receive the command line arguments +following the *Go address. + +Estimated brute force search times, including loading time, and progress +report intervals on the SPROW ARM7TDMI Coprocessor are as follows:- + +CRC Codeword *Cache On *Cache Off +width lengths Runtime Reports Runtime Reports +(bits) (bytes) + +32 5,5,6 9s - 9s - +32 8,8,7 15h06m 56m36s 120h53m 7h33m +32 9,9,8 31h07m 58m20s 259h04m 8h06m +64 12,11,12,12,17, 45s - 5m09s - + 11,12,8,9* + +*First nine codewords from the CRC-64/XZ entry in the CRC Catalogue. The ARM Tube OS binary also runs as a statically-linked image under RISC OS, at twice the size of the RISC OS binary. - -This list is provisional and will be updated on further testing. Binary files old/reveng-1.6.3/bin/armtubeos/reveng and new/reveng-2.0.0/bin/armtubeos/reveng differ diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/reveng-1.6.3/bin/armtubeos/reveng.inf new/reveng-2.0.0/bin/armtubeos/reveng.inf --- old/reveng-1.6.3/bin/armtubeos/reveng.inf 2019-04-20 16:41:36.000000000 +0200 +++ new/reveng-2.0.0/bin/armtubeos/reveng.inf 2019-05-06 23:04:59.000000000 +0200 @@ -1 +1 @@ -$.reveng 8000 8000 10A6F CRC=11E6 +$.reveng 8000 8000 10C6F CRC=F3D2 Binary files old/reveng-1.6.3/bin/i386-linux/reveng and new/reveng-2.0.0/bin/i386-linux/reveng differ Binary files old/reveng-1.6.3/bin/raspbian/reveng and new/reveng-2.0.0/bin/raspbian/reveng differ Binary files old/reveng-1.6.3/bin/riscos/reveng and new/reveng-2.0.0/bin/riscos/reveng differ Binary files old/reveng-1.6.3/bin/win32/reveng.exe and new/reveng-2.0.0/bin/win32/reveng.exe differ diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/reveng-1.6.3/cli.c new/reveng-2.0.0/cli.c --- old/reveng-1.6.3/cli.c 2019-03-24 18:07:04.000000000 +0100 +++ new/reveng-2.0.0/cli.c 2019-04-30 18:24:30.000000000 +0200 @@ -1,5 +1,5 @@ /* cli.c - * Greg Cook, 24/Mar/2019 + * Greg Cook, 29/Apr/2019 */ /* CRC RevEng: arbitrary-precision CRC calculator and algorithm finder @@ -298,7 +298,7 @@ if(mode == 'v') prev(&apoly); - crc = pcrc(apoly, model.spoly, model.init, model.xorout, model.flags); + crc = pcrc(apoly, model.spoly, model.init, model.xorout, model.flags, 0); if(mode == 'v') prev(&crc); @@ -401,7 +401,7 @@ if(pset.flags & P_REFOUT) prev(&apoly); for(qptr = apolys; qptr < pptr; ++qptr) { - crc = pcrc(*qptr, pset.spoly, pset.init, apoly, 0); + crc = pcrc(*qptr, pset.spoly, pset.init, apoly, 0, 0); if(ptst(crc)) { pfree(&crc); break; diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/reveng-1.6.3/model.c new/reveng-2.0.0/model.c --- old/reveng-1.6.3/model.c 2019-03-04 21:03:45.000000000 +0100 +++ new/reveng-2.0.0/model.c 2019-04-30 18:24:31.000000000 +0200 @@ -193,7 +193,7 @@ /* 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); + check = pcrc(checkstr, model->spoly, model->init, pzero, model->flags, 0); pfree(&checkstr); if(model->flags & P_REFOUT) prev(&check); @@ -208,7 +208,7 @@ xorout=pclone(model->xorout); if(model->flags & P_REFOUT) prev(&xorout); - magic = pcrc(xorout, model->spoly, pzero, pzero, model->flags); + magic = pcrc(xorout, model->spoly, pzero, pzero, model->flags, 0); pfree(&xorout); if(model->flags & P_REFIN) prev(&magic); diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/reveng-1.6.3/poly.c new/reveng-2.0.0/poly.c --- old/reveng-1.6.3/poly.c 2019-03-04 21:03:48.000000000 +0100 +++ new/reveng-2.0.0/poly.c 2019-05-03 21:36:56.000000000 +0200 @@ -1,5 +1,5 @@ /* poly.c - * Greg Cook, 23/Feb/2019 + * Greg Cook, 3/May/2019 */ /* CRC RevEng: arbitrary-precision CRC calculator and algorithm finder @@ -22,7 +22,8 @@ * along with CRC RevEng. If not, see <https://www.gnu.org/licenses/>. */ -/* 2017-11-28: added braces, redundant statement skipped in prev() +/* 2019-04-29: added quotient argument to pcrc(), pmod() + * 2017-11-28: added braces, redundant statement skipped in prev() * 2016-06-27: pcmp() shortcut returns 0 when pointers identical * 2015-07-29: discard leading $, &, 0x from argument to strtop() * 2015-04-03: added direct mode to strtop() @@ -81,8 +82,8 @@ */ #include <limits.h> -#include <stdio.h> #include <stdlib.h> +#include <stdio.h> #include "reveng.h" static bmp_t getwrd(const poly_t poly, unsigned long iter); @@ -311,7 +312,7 @@ char * ptostr(const poly_t poly, int flags, int bperhx) { /* Returns a malloc()-ed string containing a hexadecimal - * representation of poly. See phxsubs(). + * representation of poly. See pxsubs(). */ return(pxsubs(poly, flags, bperhx, 0UL, poly.length)); } @@ -890,8 +891,9 @@ } poly_t -pmod(const poly_t dividend, const poly_t divisor) { - /* Divide dividend by normalised divisor and return the remainder +pmod(const poly_t dividend, const poly_t divisor, poly_t *quotient) { + /* Divide dividend by normalised divisor and return the remainder. + * Place the quotient in quotient unless it is NULL. * 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. @@ -900,17 +902,18 @@ /* 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); + poly_t result = pcrc(dividend, subdivisor, pzero, pzero, 0, quotient); 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) { +pcrc(const poly_t message, const poly_t divisor, const poly_t init, const poly_t xorout, int flags, poly_t *quotient) { /* 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. + * Place the quotient in quotient unless it is NULL. * 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 @@ -919,7 +922,7 @@ * 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; + bmp_t probe, rem, dvsr, quot = BMP_C(0), *qptr, *rptr, *sptr; const bmp_t *bptr, *eptr; poly_t result = PZERO; @@ -927,22 +930,47 @@ max = message.length; else if(message.length > divisor.length) max = message.length - divisor.length; + if(quotient) + palloc(quotient, max); bptr=message.bitmap; eptr=message.bitmap+SIZE(message.length); + qptr=quotient ? quotient->bitmap : 0; 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(qptr) { + for(iter = 0UL, ofs = BMP_BIT; iter < max; ++iter) { + if(ofs == BMP_BIT) { + ofs = BMP_BIT - 1UL; + rem ^= *bptr++; + } + if(rem & probe) { + rem = (rem << 1) ^ dvsr; + quot |= (BMP_C(1) << ofs); + } else { + rem <<= 1; + } + if(!ofs--) { + ofs = BMP_BIT; + *qptr++ = quot; + quot = BMP_C(0); + } + } + if(quot) + *qptr = quot; + } else { + 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(rem & probe) - rem = (rem << 1) ^ dvsr; - else - rem <<= 1; } if(bptr < eptr) /* max < message.length */ @@ -969,6 +997,8 @@ ofs = 0UL; sptr = rptr = result.bitmap; ++sptr; + if(qptr) + *qptr++ = *rptr; /* 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 @@ -978,13 +1008,21 @@ *rptr++ = *sptr++; } ++ofs; - if(*result.bitmap & probe) + if(*result.bitmap & probe) { psum(&result, divisor, ofs); + } } rptr = result.bitmap; + if(qptr) { + if(!probe) + *qptr = *rptr; + else if(ofs) + *qptr = *rptr & ~(~BMP_C(0) >> ofs); + } ++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); } diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/reveng-1.6.3/reveng.c new/reveng-2.0.0/reveng.c --- old/reveng-1.6.3/reveng.c 2019-03-04 21:03:51.000000000 +0100 +++ new/reveng-2.0.0/reveng.c 2019-05-06 22:42:06.000000000 +0200 @@ -1,5 +1,5 @@ /* reveng.c - * Greg Cook, 23/Feb/2019 + * Greg Cook, 3/May/2019 */ /* CRC RevEng: arbitrary-precision CRC calculator and algorithm finder @@ -22,7 +22,8 @@ * along with CRC RevEng. If not, see <https://www.gnu.org/licenses/>. */ -/* 2013-09-16: calini(), calout() work on shortest argument +/* 2019-04-30: brute-force short factor if shortest diff <= 2n + * 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() @@ -54,6 +55,7 @@ #include "reveng.h" static poly_t *modpol(const poly_t init, int rflags, int args, const poly_t *argpolys); +static void dispch(const model_t *guess, int *resc, model_t **result, const poly_t divisor, 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); @@ -64,7 +66,7 @@ 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; + poly_t *pworks, *wptr, rem, factor, gpoly = PZERO, qqpoly = PZERO, *gptr = 0; model_t *result = NULL, *rptr; int resc = 0; unsigned long spin = 0, seq = 0; @@ -74,72 +76,106 @@ * Produce a list of differences between the arguments. */ pworks = modpol(guess->init, rflags, args, argpolys); + /* If no differences are returned, there is nothing to do. */ if(!pworks || !plen(*pworks)) { free(pworks); goto requit; } - /* Initialise the guessed poly to the starting value. */ - gpoly = pclone(guess->spoly); + /* If the shortest difference is the right length for the + * generator polynomial (with its top bit), then it *is* + * the generator polynomial. + */ + else if(plen(*pworks) == plen(guess->spoly) + 1UL) { + pcpy(&gpoly, *pworks); + pshift(&gpoly,gpoly,0UL,1UL,plen(gpoly),0UL); + dispch(guess, &resc, &result, gpoly, rflags, args, argpolys); + pfree(&gpoly); + goto requit; + } + /* Otherwise initialise the trial factor to the starting value. */ + factor = pclone(guess->spoly); + if(rflags & R_HAVEQ) + qqpoly = pclone(qpoly); + + /* Truncate trial factor if shortest difference is compact. */ + if(plen(*pworks) <= (plen(guess->spoly)) << 1) { + pright(&factor, plen(*pworks) - plen(guess->spoly) - 1UL); + if(rflags & R_HAVEQ) + pright(&qqpoly, plen(*pworks) - plen(guess->spoly) - 1UL); + /* Point gptr to gpoly so that pcrc() returns the quotient. */ + gptr = &gpoly; + } + /* 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); + if(plen(factor)) + pshift(&factor, factor, 0UL, 0UL, plen(factor) - 1UL, 1UL); - while(piter(&gpoly) && (~rflags & R_HAVEQ || pcmp(&gpoly, &qpoly) < 0)) { + while(piter(&factor) && (~rflags & R_HAVEQ || pcmp(&factor, &qqpoly) < 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++); + uprog(factor, 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(gptr) { + /* divide first difference by cofactor to get generator */ + wptr = pworks; + if(plen(*wptr)) { + rem = pcrc(*wptr, factor, pzero, pzero, 0, 0); + if(ptst(rem)) { + pfree(&rem); + } else { + pfree(&rem); + /* test generator against other differences */ + rem = pcrc(*pworks, factor, pzero, pzero, 0, &gpoly); + pfree(&rem); + pshift(&gpoly,gpoly,0UL,1UL,plen(gpoly),0UL); + for(++wptr; plen(*wptr); ++wptr) { + rem = pcrc(*wptr, gpoly, pzero, pzero, 0, 0); + if(ptst(rem)) { + pfree(&rem); + break; + } else + pfree(&rem); + } + } + } + } else { + for(wptr = pworks; plen(*wptr); ++wptr) { + /* straight divide message by poly, don't multiply by x^n */ + rem = pcrc(*wptr, factor, pzero, pzero, 0, 0); + if(ptst(rem)) { + pfree(&rem); + break; + } else + pfree(&rem); + } } - /* If gpoly divides all the differences, it is a + /* If factor 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); + /* gpoly || factor is a candidate poly */ + dispch(guess, &resc, &result, gptr ? gpoly : factor, rflags, args, argpolys); } - if(!piter(&gpoly)) + if(!piter(&factor)) break; } - /* Finished with gpoly and the differences list, free them. + /* Finished with factor and the differences list, free them. */ + pfree(&qqpoly); pfree(&gpoly); + pfree(&factor); 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); + dispch(guess, &resc, &result, guess->spoly, rflags, args, argpolys); requit: if(!(result = realloc(result, ++resc * sizeof(model_t)))) @@ -222,6 +258,19 @@ } static void +dispch(const model_t *guess, int *resc, model_t **result, const poly_t divisor, int rflags, int args, const poly_t *argpolys) { + if(rflags & R_HAVEI && rflags & R_HAVEX) + chkres(resc, result, divisor, guess->init, guess->flags, guess->xorout, args, argpolys); + else if(rflags & R_HAVEI) + calout(resc, result, divisor, guess->init, guess->flags, args, argpolys); + else if(rflags & R_HAVEX) + calini(resc, result, divisor, guess->flags, guess->xorout, args, argpolys); + else + engini(resc, result, divisor, guess->flags, args, argpolys); +} + + +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). @@ -275,22 +324,22 @@ psum(&apoly, pone, blen - alen); /* >= 1 */ } if(plen(apoly) > dlen) { - mat[dlen] = pcrc(apoly, divisor, pzero, pzero, 0); + mat[dlen] = pcrc(apoly, divisor, pzero, pzero, 0, 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); + apoly = pcrc(*aptr, divisor, pzero, pzero, 0, 0); + bpoly = pcrc(*bptr, divisor, pzero, apoly, 0, 0); /* Populate the matrix */ palloc(&apoly, 1UL); for(jptr=mat; jptr<mat+dlen; ++jptr) *jptr = pzero; for(iptr = jptr++; jptr < mat + (dlen << 1); iptr = jptr++) - *jptr = pcrc(apoly, divisor, *iptr, pzero, P_MULXN); + *jptr = pcrc(apoly, divisor, *iptr, pzero, P_MULXN, 0); pfree(&apoly); /* Transpose the matrix, augment with the Init contribution @@ -377,7 +426,7 @@ } } - xorout = pcrc(*aptr, divisor, init, pzero, 0); + xorout = pcrc(*aptr, divisor, init, pzero, 0, 0); /* On little-endian algorithms, the calculations yield * the reverse of the actual xorout: in the Williams * model, the refout stage intervenes between init and @@ -427,7 +476,7 @@ arg = pclone(*aptr); prev(&arg); - init = pcrc(arg, rcpdiv, rxor, pzero, 0); + init = pcrc(arg, rcpdiv, rxor, pzero, 0, 0); pfree(&arg); pfree(&rxor); pfree(&rcpdiv); @@ -461,7 +510,7 @@ prev(&xor); for(; aptr < eptr; ++aptr) { - crc = pcrc(*aptr, divisor, init, xor, 0); + crc = pcrc(*aptr, divisor, init, xor, 0, 0); if(ptst(crc)) { pfree(&crc); break; diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/reveng-1.6.3/reveng.h new/reveng-2.0.0/reveng.h --- old/reveng-1.6.3/reveng.h 2019-03-24 18:08:37.000000000 +0100 +++ new/reveng-2.0.0/reveng.h 2019-04-30 18:23:28.000000000 +0200 @@ -1,5 +1,5 @@ /* reveng.h - * Greg Cook, 24/Mar/2019 + * Greg Cook, 29/Apr/2019 */ /* CRC RevEng: arbitrary-precision CRC calculator and algorithm finder @@ -93,7 +93,7 @@ /* Global definitions */ /* CRC RevEng version string */ -#define VERSION "1.6.3" +#define VERSION "2.0.0" /* bmpbit.c */ typedef BMP_T bmp_t; @@ -166,8 +166,8 @@ 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 poly_t pmod(const poly_t dividend, const poly_t divisor, poly_t *quotient); +extern poly_t pcrc(const poly_t message, const poly_t divisor, const poly_t init, const poly_t xorout, int flags, poly_t *quotient); extern int piter(poly_t *poly); extern void palloc(poly_t *poly, unsigned long length); extern void pfree(poly_t *poly); diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/reveng-1.6.3/reveng.rc new/reveng-2.0.0/reveng.rc --- old/reveng-1.6.3/reveng.rc 2019-03-24 18:09:26.000000000 +0100 +++ new/reveng-2.0.0/reveng.rc 2019-05-01 00:31:48.000000000 +0200 @@ -1,5 +1,5 @@ /* reveng.rc - * Greg Cook, 24/Mar/2019 + * Greg Cook, 30/Apr/2019 */ /* CRC RevEng: arbitrary-precision CRC calculator and algorithm finder @@ -30,11 +30,11 @@ #include <windows.h> -#define VER_FILEVERSION 1,6,3,0 -#define VER_FILEVERSION_STR "1.6.3.0\0" +#define VER_FILEVERSION 2,0,0,0 +#define VER_FILEVERSION_STR "2.0.0.0\0" -#define VER_PRODUCTVERSION 1,6,3,0 -#define VER_PRODUCTVERSION_STR "1.6.3\0" +#define VER_PRODUCTVERSION 2,0,0,0 +#define VER_PRODUCTVERSION_STR "2.0.0\0" #ifndef DEBUG #define VER_DEBUG 0