Script 'mail_helper' called by obssrc Hello community, here is the log from the commit of package reveng for openSUSE:Factory checked in at 2022-01-03 10:49:51 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ Comparing /work/SRC/openSUSE:Factory/reveng (Old) and /work/SRC/openSUSE:Factory/.reveng.new.1896 (New) ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Package is "reveng" Mon Jan 3 10:49:51 2022 rev:10 rq:943478 version:3.0.0 Changes: -------- --- /work/SRC/openSUSE:Factory/reveng/reveng.changes 2021-12-29 21:11:31.774313789 +0100 +++ /work/SRC/openSUSE:Factory/.reveng.new.1896/reveng.changes 2022-01-03 10:50:36.411607729 +0100 @@ -1,0 +2,8 @@ +Sat Jan 1 21:48:22 UTC 2022 - Martin Hauke <[email protected]> + +- Update to version 3.0.0 + * Reduces or eliminates brute force search for POLY in many + cases by finding the greatest common divisor of differences + between codewords. + +------------------------------------------------------------------- Old: ---- reveng-2.1.2.tar.xz New: ---- reveng-3.0.0.tar.xz ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ Other differences: ------------------ ++++++ reveng.spec ++++++ --- /var/tmp/diff_new_pack.LRkoOd/_old 2022-01-03 10:50:36.899607916 +0100 +++ /var/tmp/diff_new_pack.LRkoOd/_new 2022-01-03 10:50:36.903607918 +0100 @@ -1,8 +1,8 @@ # # spec file for package reveng # -# Copyright (c) 2021 SUSE LLC -# Copyright (c) 2017-2021, Martin Hauke <[email protected]> +# Copyright (c) 2022 SUSE LLC +# Copyright (c) 2017-2022, Martin Hauke <[email protected]> # # All modifications and additions to the file contributed by third parties # remain the property of their copyright owners, unless otherwise agreed @@ -18,7 +18,7 @@ Name: reveng -Version: 2.1.2 +Version: 3.0.0 Release: 0 Summary: An arbitrary-precision CRC calculator and algorithm finder License: GPL-3.0-or-later ++++++ reveng-2.1.2.tar.xz -> reveng-3.0.0.tar.xz ++++++ diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/reveng-2.1.2/CHANGES new/reveng-3.0.0/CHANGES --- old/reveng-2.1.2/CHANGES 2021-12-24 20:19:37.000000000 +0100 +++ new/reveng-3.0.0/CHANGES 2021-12-31 18:37:44.000000000 +0100 @@ -19,6 +19,11 @@ Revision history of CRC RevEng +3.0.0 31 December 2021 + * Reduces or eliminates brute force search for POLY in many + cases by finding the greatest common divisor of differences + between codewords (thanks to Wang Ruikang). + 2.1.2 24 December 2021 * Added algorithm CRC-8/HITAG from the CRC Catalogue. Binary files old/reveng-2.1.2/bin/armtubeos/reveng and new/reveng-3.0.0/bin/armtubeos/reveng differ diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/reveng-2.1.2/bin/armtubeos/reveng.inf new/reveng-3.0.0/bin/armtubeos/reveng.inf --- old/reveng-2.1.2/bin/armtubeos/reveng.inf 2021-12-24 21:55:05.000000000 +0100 +++ new/reveng-3.0.0/bin/armtubeos/reveng.inf 2021-12-31 19:10:29.000000000 +0100 @@ -1 +1 @@ -$.reveng 8000 8000 10D2F CRC=0856 +$.reveng 8000 8000 10C9F CRC=6C19 Binary files old/reveng-2.1.2/bin/i386-linux/reveng and new/reveng-3.0.0/bin/i386-linux/reveng differ Binary files old/reveng-2.1.2/bin/raspbian/reveng and new/reveng-3.0.0/bin/raspbian/reveng differ Binary files old/reveng-2.1.2/bin/riscos/reveng and new/reveng-3.0.0/bin/riscos/reveng differ Binary files old/reveng-2.1.2/bin/win32/reveng.exe and new/reveng-3.0.0/bin/win32/reveng.exe differ diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/reveng-2.1.2/reveng.c new/reveng-3.0.0/reveng.c --- old/reveng-2.1.2/reveng.c 2021-12-24 20:19:37.000000000 +0100 +++ new/reveng-3.0.0/reveng.c 2021-12-31 19:02:22.000000000 +0100 @@ -1,5 +1,5 @@ /* reveng.c - * Greg Cook, 24/Dec/2021 + * Greg Cook, 31/Dec/2021 */ /* 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/>. */ -/* 2019-12-07: skip equivalent forms +/* 2019-12-31: modpol() passes only GCD to reveng() + * 2019-12-07: skip equivalent forms * 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 @@ -52,10 +53,11 @@ #include <stdlib.h> -#define FILE void +#include <stdio.h> +/* #define FILE void */ #include "reveng.h" -static poly_t *modpol(const poly_t init, int rflags, int args, const poly_t *argpolys); +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); @@ -67,7 +69,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 = PZERO, factor = PZERO, gpoly = PZERO, qqpoly = PZERO; + poly_t pwork, rem = PZERO, factor = PZERO, gpoly = PZERO, qqpoly = PZERO; model_t *result = NULL, *rptr; int resc = 0; unsigned long spin = 0, seq = 0; @@ -79,27 +81,25 @@ dispch(guess, &resc, &result, guess->spoly, rflags, args, argpolys); } else { /* The poly is not known. - * Produce a list of differences between the arguments. + * Produce the GCD of all differences between the arguments. */ if(!plen(guess->spoly)) goto requit; - pworks = modpol(guess->init, rflags, args, argpolys); + pwork = modpol(guess->init, rflags, args, argpolys); /* If too short a difference is returned, there is nothing to do. */ - if(!pworks) - goto requit; - else if(plen(*pworks) < plen(guess->spoly) + 1UL) + if(plen(pwork) < plen(guess->spoly) + 1UL) goto rpquit; - /* plen(*pworks) >= 2 */ + /* plen(pwork) >= 2 */ /* 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); + else if(plen(pwork) == plen(guess->spoly) + 1UL) { + pcpy(&gpoly, pwork); /* Chop the generator. + 1 term is present * as differences come normalized from modpol(). */ - pshift(&gpoly,gpoly,0UL,1UL,plen(gpoly),0UL); /* plen(gpoly) >= 1 */ + pshift(&gpoly,gpoly, 0UL, 1UL, plen(gpoly), 0UL); /* plen(gpoly) >= 1 */ dispch(guess, &resc, &result, gpoly, rflags, args, argpolys); goto rpquit; } @@ -112,18 +112,18 @@ * if shortest difference is compact. */ rflags &= ~R_SHORT; - if(plen(*pworks) <= (plen(factor)) << 1) { /* plen(*pworks) >= 4, plen(factor) >= 2 */ + if(plen(pwork) <= (plen(factor)) << 1) { /* plen(pwork) >= 4, plen(factor) >= 2 */ rflags |= R_SHORT; if((rflags & R_HAVEQ) || ptst(factor)) { /* Validate range polynomials. * Ensure proper behaviour if the search space is * naively divided up as per the README. */ - palloc(&rem, plen(*pworks) - plen(factor) - 1UL); /* >= 1 */ + palloc(&rem, plen(pwork) - plen(factor) - 1UL); /* >= 1 */ pinv(&rem); pright(&rem, plen(factor)); /* >= 1 */ - /* If start polynomial out of range, do not search. */ + /* If start polynomial out of range, do not search. */ if(pcmp(&rem, &factor) < 0) goto rpquit; /* If end polynomial out of range, do not compare, @@ -133,11 +133,11 @@ rflags &= ~R_HAVEQ; /* Otherwise truncate end polynomial. */ else if(rflags & R_HAVEQ) - pright(&qqpoly, plen(*pworks) - plen(factor) - 1UL); /* >= 1 */ + pright(&qqpoly, plen(pwork) - plen(factor) - 1UL); /* >= 1 */ pfree(&rem); } /* Truncate trial factor. */ - pright(&factor, plen(*pworks) - plen(factor) - 1UL); /* >= 1 */ + pright(&factor, plen(pwork) - plen(factor) - 1UL); /* >= 1 */ } /* Clear the least significant term, to be set in the @@ -149,69 +149,48 @@ /* plen(factor) >= 1 */ 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. + * dividing the GCD of the differences. */ if(!(spin++ & R_SPMASK)) { uprog(factor, guess->flags, seq++); } if(rflags & R_SHORT) { - /* test whether cofactor divides shortest difference */ - wptr = pworks; - rem = pcrc(*wptr, factor, pzero, pzero, 0, NULL); - if(ptst(rem)) { - pfree(&rem); - } else { + /* test whether cofactor divides the GCD */ + rem = pcrc(pwork, factor, pzero, pzero, 0, NULL); + if(!ptst(rem)) { pfree(&rem); /* repeat division to get generator polynomial * then test generator against other differences */ - rem = pcrc(*wptr, factor, pzero, pzero, 0, &gpoly); - pfree(&rem); + rem = pcrc(pwork, factor, pzero, pzero, 0, &gpoly); /* chop generator and ensure + 1 term */ pshift(&gpoly,gpoly,0UL,1UL,plen(gpoly) - 1UL,1UL); piter(&gpoly); /* plen(gpoly) >= 1 */ - - for(++wptr; plen(*wptr); ++wptr) { - rem = pcrc(*wptr, gpoly, pzero, pzero, 0, NULL); - 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); - } + /* straight divide message by poly, don't multiply by x^n */ + rem = pcrc(pwork, factor, pzero, pzero, 0, 0); } /* 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)) { + if(!ptst(rem)) { /* gpoly || factor is a candidate poly */ dispch(guess, &resc, &result, (rflags & R_SHORT) ? gpoly : factor, rflags, args, argpolys); } + pfree(&rem); if(!piter(&factor)) break; } - /* Finished with factor and the differences list, free them. + /* Finished with factor and the GCD, free them. */ rpquit: pfree(&rem); pfree(&qqpoly); pfree(&gpoly); pfree(&factor); - for(wptr = pworks; plen(*wptr); ++wptr) - pfree(wptr); - free(pworks); + pfree(&pwork); } requit: @@ -231,26 +210,22 @@ /* Private functions */ -static poly_t * +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. + /* Produce the greatest common divisor (GCD) of differences + * between pairs of arguments in argpolys[0..args-1]. * 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 + * Otherwise, sums of right-aligned pairs are included, 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; + poly_t gcd = PZERO, work, rem; + const poly_t *aptr, *bptr, *const eptr = argpolys + args; unsigned long alen, blen; + unsigned int nogcd = 2U; - 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; + if(args < 2) return(gcd); for(aptr = argpolys; aptr < eptr; ++aptr) { alen = plen(*aptr); @@ -274,26 +249,38 @@ 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; + if(plen(work)) { + /* combine work with running gcd */ + if((nogcd >>= 1)) + pcpy(&gcd, work); + else while(plen(work)) { + /* ptst(gcd) != 0 */ + + /* fixup for the way pmod() works. + * this emulates one iteration of + * a correct loop whereby + * (short, long) -> (long, short) + * since + * poly_mod(short, long) == short + * whereas pmod() left-aligns operands + */ + if(plen(gcd) < plen(work)) { + rem = gcd; + gcd = work; + work = rem; } + rem = pmod(gcd, work, NULL); + pfree(&gcd); + gcd = work; + work = rem; + rem = pzero; + pnorm(&work); } - *rptr++ = work; } + pfree(&work); } } - *rptr = pzero; - return(result); + return(gcd); } static void diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/reveng-2.1.2/reveng.h new/reveng-3.0.0/reveng.h --- old/reveng-2.1.2/reveng.h 2021-12-24 20:19:37.000000000 +0100 +++ new/reveng-3.0.0/reveng.h 2021-12-31 18:37:44.000000000 +0100 @@ -1,5 +1,5 @@ /* reveng.h - * Greg Cook, 24/Dec/2021 + * Greg Cook, 31/Dec/2021 */ /* CRC RevEng: arbitrary-precision CRC calculator and algorithm finder @@ -93,7 +93,7 @@ /* Global definitions */ /* CRC RevEng version string */ -#define VERSION "2.1.2" +#define VERSION "3.0.0" /* bmpbit.c */ typedef BMP_T bmp_t; diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/reveng-2.1.2/reveng.rc new/reveng-3.0.0/reveng.rc --- old/reveng-2.1.2/reveng.rc 2021-12-24 20:19:37.000000000 +0100 +++ new/reveng-3.0.0/reveng.rc 2021-12-31 19:02:22.000000000 +0100 @@ -1,5 +1,5 @@ /* reveng.rc - * Greg Cook, 24/Dec/2021 + * Greg Cook, 31/Dec/2021 */ /* CRC RevEng: arbitrary-precision CRC calculator and algorithm finder @@ -30,11 +30,11 @@ #include <windows.h> -#define VER_FILEVERSION 2,1,2,0 -#define VER_FILEVERSION_STR "2.1.2.0\0" +#define VER_FILEVERSION 3,0,0,0 +#define VER_FILEVERSION_STR "3.0.0.0\0" -#define VER_PRODUCTVERSION 2,1,2,0 -#define VER_PRODUCTVERSION_STR "2.1.2\0" +#define VER_PRODUCTVERSION 3,0,0,0 +#define VER_PRODUCTVERSION_STR "3.0.0\0" #ifndef DEBUG #define VER_DEBUG 0
