[proxmark3-svn] / client / reveng / reveng.c

/* reveng.c
 * Greg Cook, 9/Apr/2015
 */

/* CRC RevEng, an arbitrary-precision CRC calculator and algorithm finder
 * Copyright (C) 2010, 2011, 2012, 2013, 2014, 2015  Gregory Cook
 *
 * This file is part of CRC RevEng.
 *
 * CRC RevEng is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * CRC RevEng is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with CRC RevEng.  If not, see <http://www.gnu.org/licenses/>.
 */

/* 2013-09-16: calini(), calout() work on shortest argument
 * 2013-06-11: added sequence number to uprog() calls
 * 2013-02-08: added polynomial range search
 * 2013-01-18: refactored model checking to pshres(); renamed chkres()
 * 2012-05-24: efficiently build Init contribution string
 * 2012-05-24: removed broken search for crossed-endian algorithms
 * 2012-05-23: rewrote engini() after Ewing; removed modini()
 * 2011-01-17: fixed ANSI C warnings
 * 2011-01-08: fixed calini(), modini() caters for crossed-endian algos
 * 2011-01-04: renamed functions, added calini(), factored pshres();
 *	       rewrote engini() and implemented quick Init search
 * 2011-01-01: reveng() initialises terminating entry, addparms()
 *	       initialises all fields
 * 2010-12-26: renamed CRC RevEng. right results, rejects polys faster
 * 2010-12-24: completed, first tests (unsuccessful)
 * 2010-12-21: completed modulate(), partial sketch of reveng()
 * 2010-12-19: started reveng
 */

/* reveng() can in theory be modified to search for polynomials shorter
 * than the full width as well, but this imposes a heavy time burden on
 * the full width search, which is the primary use case, as well as
 * complicating the search range function introduced in version 1.1.0.
 * It is more effective to search for each shorter width directly.
 */

#include <stdlib.h>

#define FILE void
#include "reveng.h"

static poly_t *modpol(const poly_t init, int rflags, int args, const poly_t *argpolys);
static void engini(int *resc, model_t **result, const poly_t divisor, int flags, int args, const poly_t *argpolys);
static void calout(int *resc, model_t **result, const poly_t divisor, const poly_t init, int flags, int args, const poly_t *argpolys);
static void calini(int *resc, model_t **result, const poly_t divisor, int flags, const poly_t xorout, int args, const poly_t *argpolys);
static void chkres(int *resc, model_t **result, const poly_t divisor, const poly_t init, int flags, const poly_t xorout, int args, const poly_t *argpolys);

static const poly_t pzero = PZERO;

model_t *
reveng(const model_t *guess, const poly_t qpoly, int rflags, int args, const poly_t *argpolys) {
	/* Complete the parameters of a model by calculation or brute search. */
	poly_t *pworks, *wptr, rem, gpoly;
	model_t *result = NULL, *rptr;
	int resc = 0;
	unsigned long spin = 0, seq = 0;

	if(~rflags & R_HAVEP) {
		/* The poly is not known.
		 * Produce a list of differences between the arguments.
		 */
		pworks = modpol(guess->init, rflags, args, argpolys);
		if(!pworks || !plen(*pworks)) {
			free(pworks);
			goto requit;
		}
		/* Initialise the guessed poly to the starting value. */
		gpoly = pclone(guess->spoly);
		/* Clear the least significant term, to be set in the
		 * loop. qpoly does not need fixing as it is only
		 * compared with odd polys.
		 */
		if(plen(gpoly))
			pshift(&gpoly, gpoly, 0UL, 0UL, plen(gpoly) - 1UL, 1UL);

		while(piter(&gpoly) && (~rflags & R_HAVEQ || pcmp(&gpoly, &qpoly) < 0)) {
			/* For each possible poly of this size, try
			 * dividing all the differences in the list.
			 */
			if(!(spin++ & R_SPMASK)) {
				uprog(gpoly, guess->flags, seq++);
			}
			for(wptr = pworks; plen(*wptr); ++wptr) {
				/* straight divide message by poly, don't multiply by x^n */
				rem = pcrc(*wptr, gpoly, pzero, pzero, 0);
				if(ptst(rem)) {
					pfree(&rem);
					break;
				} else
					pfree(&rem);
			}
			/* If gpoly divides all the differences, it is a
			 * candidate.  Search for an Init value for this
			 * poly or if Init is known, log the result.
			 */
			if(!plen(*wptr)) {
				/* gpoly is a candidate poly */
				if(rflags & R_HAVEI && rflags & R_HAVEX)
					chkres(&resc, &result, gpoly, guess->init, guess->flags, guess->xorout, args, argpolys);
				else if(rflags & R_HAVEI)
					calout(&resc, &result, gpoly, guess->init, guess->flags, args, argpolys);
				else if(rflags & R_HAVEX)
					calini(&resc, &result, gpoly, guess->flags, guess->xorout, args, argpolys);
				else
					engini(&resc, &result, gpoly, guess->flags, args, argpolys);
			}
			if(!piter(&gpoly))
				break;
		}
		/* Finished with gpoly and the differences list, free them.
		 */
		pfree(&gpoly);
		for(wptr = pworks; plen(*wptr); ++wptr)
			pfree(wptr);
		free(pworks);
	}
	else if(rflags & R_HAVEI && rflags & R_HAVEX)
		/* All parameters are known!  Submit the result if we get here */
		chkres(&resc, &result, guess->spoly, guess->init, guess->flags, guess->xorout, args, argpolys);
	else if(rflags & R_HAVEI)
		/* Poly and Init are known, calculate XorOut */
		calout(&resc, &result, guess->spoly, guess->init, guess->flags, args, argpolys);
	else if(rflags & R_HAVEX)
		/* Poly and XorOut are known, calculate Init */
		calini(&resc, &result, guess->spoly, guess->flags, guess->xorout, args, argpolys);
	else
		/* Poly is known but not Init; search for Init. */
		engini(&resc, &result, guess->spoly, guess->flags, args, argpolys);

requit:
	if(!(result = realloc(result, ++resc * sizeof(model_t))))
		uerror("cannot reallocate result array");
	rptr = result + resc - 1;
	rptr->spoly  = pzero;
	rptr->init   = pzero;
	rptr->flags  = 0;
	rptr->xorout = pzero;
	rptr->check  = pzero;
	rptr->name   = NULL;

	return(result);
}

static poly_t *
modpol(const poly_t init, int rflags, int args, const poly_t *argpolys) {
	/* Produce, in ascending length order, a list of differences
	 * between the arguments in the list by summing pairs of arguments.
	 * If R_HAVEI is not set in rflags, only pairs of equal length are
	 * summed.
	 * Otherwise, sums of right-aligned pairs are also returned, with
	 * the supplied init poly added to the leftmost terms of each
	 * poly of the pair.
	 */
	poly_t work, swap, *result, *rptr, *iptr;
	const poly_t *aptr, *bptr, *eptr = argpolys + args;
	unsigned long alen, blen;

	if(args < 2) return(NULL);

	if(!(result = malloc(((((args - 1) * args) >> 1) + 1) * sizeof(poly_t))))
		uerror("cannot allocate memory for codeword table");

	rptr = result;

	for(aptr = argpolys; aptr < eptr; ++aptr) {
		alen = plen(*aptr);
		for(bptr = aptr + 1; bptr < eptr; ++bptr) {
			blen = plen(*bptr);
			if(alen == blen) {
				work = pclone(*aptr);
				psum(&work, *bptr, 0UL);
			} else if(rflags & R_HAVEI && alen < blen) {
				work = pclone(*bptr);
				psum(&work, *aptr, blen - alen);
				psum(&work, init, 0UL);
				psum(&work, init, blen - alen);
			} else if(rflags & R_HAVEI /* && alen > blen */) {
				work = pclone(*aptr);
				psum(&work, *bptr, alen - blen);
				psum(&work, init, 0UL);
				psum(&work, init, alen - blen);
			} else
				work = pzero;

			if(plen(work))
				pnorm(&work);
			if((blen = plen(work))) {
				/* insert work into result[] in ascending order of length */
				for(iptr = result; iptr < rptr; ++iptr) {
					if(plen(work) < plen(*iptr)) {
						swap = *iptr;
						*iptr = work;
						work = swap;
					}
					else if(plen(*iptr) == blen && !pcmp(&work, iptr)) {
						pfree(&work);
						work = *--rptr;
						break;
					}
				}
				*rptr++ = work;
			}
		}
	}
	*rptr = pzero;
	return(result);
}

static void
engini(int *resc, model_t **result, const poly_t divisor, int flags, int args, const poly_t *argpolys) {
	/* Search for init values implied by the arguments.
	 * Method from: Ewing, Gregory C. (March 2010).
	 * "Reverse-Engineering a CRC Algorithm". Christchurch:
	 * University of Canterbury.
	 * <http://www.cosc.canterbury.ac.nz/greg.ewing/essays/
	 * CRC-Reverse-Engineering.html>
	 */
	poly_t apoly = PZERO, bpoly, pone = PZERO, *mat, *jptr;
	const poly_t *aptr, *bptr, *iptr;
	unsigned long alen, blen, dlen, ilen, i, j;
	int cy;

	dlen = plen(divisor);

	/* Allocate the CRC matrix */
	if(!(mat = (poly_t *) malloc((dlen << 1) * sizeof(poly_t))))
		uerror("cannot allocate memory for CRC matrix");

	/* Find arguments of the two shortest lengths */
	alen = blen = plen(*(aptr = bptr = iptr = argpolys));
	for(++iptr; iptr < argpolys + args; ++iptr) {
		ilen = plen(*iptr);
		if(ilen < alen) {
			bptr = aptr; blen = alen;
			aptr = iptr; alen = ilen;
		} else if(ilen > alen && (aptr == bptr || ilen < blen)) {
			bptr = iptr; blen = ilen;
		}
	}
	if(aptr == bptr) {
		/* if no arguments are suitable, calculate Init with an
		 * assumed XorOut of 0.  Create a padded XorOut
		 */
		palloc(&apoly, dlen);
		calini(resc, result, divisor, flags, apoly, args, argpolys);
		pfree(&apoly);
		free(mat);
		return;
	}

	/* Find the potential contribution of the bottom bit of Init */
	palloc(&pone, 1UL);
	piter(&pone);
	if(blen < (dlen << 1)) {
		palloc(&apoly, dlen); /* >= 1 */
		psum(&apoly, pone, (dlen << 1) - 1UL - blen); /* >= 0 */
		psum(&apoly, pone, (dlen << 1) - 1UL - alen); /* >= 1 */
	} else {
		palloc(&apoly, blen - dlen + 1UL); /* > dlen */
		psum(&apoly, pone, 0UL);
		psum(&apoly, pone, blen - alen); /* >= 1 */
	}
	if(plen(apoly) > dlen) {
		mat[dlen] = pcrc(apoly, divisor, pzero, pzero, 0);
		pfree(&apoly);
	} else {
		mat[dlen] = apoly;
	}

	/* Find the actual contribution of Init */
	apoly = pcrc(*aptr, divisor, pzero, pzero, 0);
	bpoly = pcrc(*bptr, divisor, pzero, apoly, 0);

	/* Populate the matrix */
	palloc(&apoly, 1UL);
	for(jptr=mat; jptr<mat+dlen; ++jptr)
		*jptr = pzero;
	for(iptr = jptr++; jptr < mat + (dlen << 1); iptr = jptr++)
		*jptr = pcrc(apoly, divisor, *iptr, pzero, P_MULXN);
	pfree(&apoly);

	/* Transpose the matrix, augment with the Init contribution
	 * and convert to row echelon form
	 */
	for(i=0UL; i<dlen; ++i) {
		apoly = pzero;
		iptr = mat + (dlen << 1);
		for(j=0UL; j<dlen; ++j)
			ppaste(&apoly, *--iptr, i, j, j + 1UL, dlen + 1UL);
		if(ptst(apoly))
			ppaste(&apoly, bpoly, i, dlen, dlen + 1UL, dlen + 1UL);
		j = pfirst(apoly);
		while(j < dlen && !pident(mat[j], pzero)) {
			psum(&apoly, mat[j], 0UL); /* pfirst(apoly) > j */
			j = pfirst(apoly);
		}
		if(j < dlen)
			mat[j] = apoly; /* pident(mat[j], pzero) || pfirst(mat[j]) == j */
		else
			pfree(&apoly);
	}
	palloc(&bpoly, dlen + 1UL);
	psum(&bpoly, pone, dlen);

	/* Iterate through all solutions */
	do {
		/* Solve the matrix by Gaussian elimination.
		 * The parity of the result, masked by each row, should be even.
		 */
		cy = 1;
		apoly = pclone(bpoly);
		jptr = mat + dlen;
		for(i=0UL; i<dlen; ++i) {
			/* Compute next bit of Init */
			if(pmpar(apoly, *--jptr))
				psum(&apoly, pone, dlen - 1UL - i);
			/* Toggle each zero row with carry, for next iteration */
			if(cy) {
			       if(pident(*jptr, pzero)) {
				       /* 0 to 1, no carry */
				       *jptr = bpoly;
				       cy = 0;
			       } else if(pident(*jptr, bpoly)) {
				       /* 1 to 0, carry forward */
				       *jptr = pzero;
			       }
			}
		}

		/* Trim the augment mask bit */
		praloc(&apoly, dlen);

		/* Test the Init value and add to results if correct */
		calout(resc, result, divisor, apoly, flags, args, argpolys);
		pfree(&apoly);
	} while(!cy);
	pfree(&pone);
	pfree(&bpoly);

	/* Free the matrix. */
	for(jptr=mat; jptr < mat + (dlen << 1); ++jptr)
		pfree(jptr);
	free(mat);
}

static void
calout(int *resc, model_t **result, const poly_t divisor, const poly_t init, int flags, int args, const poly_t *argpolys) {
	/* Calculate Xorout, check it against all the arguments and
	 * add to results if consistent.
	 */
	poly_t xorout;
	const poly_t *aptr, *iptr;
	unsigned long alen, ilen;

	if(args < 1) return;

	/* find argument of the shortest length */
	alen = plen(*(aptr = iptr = argpolys));
	for(++iptr; iptr < argpolys + args; ++iptr) {
		ilen = plen(*iptr);
		if(ilen < alen) {
			aptr = iptr; alen = ilen;
		}
	}

	xorout = pcrc(*aptr, divisor, init, pzero, 0);
	/* On little-endian algorithms, the calculations yield
	 * the reverse of the actual xorout: in the Williams
	 * model, the refout stage intervenes between init and
	 * xorout.
	 */
	if(flags & P_REFOUT)
		prev(&xorout);

	/* Submit the model to the results table.
	 * Could skip the shortest argument but we wish to check our
	 * calculation.
	 */
	chkres(resc, result, divisor, init, flags, xorout, args, argpolys);
	pfree(&xorout);
}

static void
calini(int *resc, model_t **result, const poly_t divisor, int flags, const poly_t xorout, int args, const poly_t *argpolys) {
	/* Calculate Init, check it against all the arguments and add to
	 * results if consistent.
	 */
	poly_t rcpdiv, rxor, arg, init;
	const poly_t *aptr, *iptr;
	unsigned long alen, ilen;

	if(args < 1) return;

	/* find argument of the shortest length */
	alen = plen(*(aptr = iptr = argpolys));
	for(++iptr; iptr < argpolys + args; ++iptr) {
		ilen = plen(*iptr);
		if(ilen < alen) {
			aptr = iptr; alen = ilen;
		}
	}

	rcpdiv = pclone(divisor);
	prcp(&rcpdiv);
	/* If the algorithm is reflected, an ordinary CRC requires the
	 * model's XorOut to be reversed, as XorOut follows the RefOut
	 * stage.  To reverse the CRC calculation we need rxor to be the
	 * mirror image of the forward XorOut.
	 */
	rxor = pclone(xorout);
	if(~flags & P_REFOUT)
		prev(&rxor);
	arg = pclone(*aptr);
	prev(&arg);

	init = pcrc(arg, rcpdiv, rxor, pzero, 0);
	pfree(&arg);
	pfree(&rxor);
	pfree(&rcpdiv);
	prev(&init);

	/* Submit the model to the results table.
	 * Could skip the shortest argument but we wish to check our
	 * calculation.
	 */
	chkres(resc, result, divisor, init, flags, xorout, args, argpolys);
	pfree(&init);
}

static void
chkres(int *resc, model_t **result, const poly_t divisor, const poly_t init, int flags, const poly_t xorout, int args, const poly_t *argpolys) {
	/* Checks a model against the argument list, and adds to the
	 * external results table if consistent.
	 * Extends the result array and update the external pointer if
	 * necessary.
	 */
	model_t *rptr;
	poly_t xor, crc;
	const poly_t *aptr = argpolys, *const eptr = argpolys + args;

	/* If the algorithm is reflected, an ordinary CRC requires the
	 * model's XorOut to be reversed, as XorOut follows the RefOut
	 * stage.
	 */
	xor = pclone(xorout);
	if(flags & P_REFOUT)
		prev(&xor);

	for(; aptr < eptr; ++aptr) {
		crc = pcrc(*aptr, divisor, init, xor, 0);
		if(ptst(crc)) {
			pfree(&crc);
			break;
		} else {
			pfree(&crc);
		}
	}
	pfree(&xor);
	if(aptr != eptr) return;

	if(!(*result = realloc(*result, ++*resc * sizeof(model_t))))
		uerror("cannot reallocate result array");

	rptr = *result + *resc - 1;
	rptr->spoly  = pclone(divisor);
	rptr->init   = pclone(init);
	rptr->flags  = flags;
	rptr->xorout = pclone(xorout);
	rptr->name   = NULL;

	/* compute check value for this model */
	mcheck(rptr);

	/* callback to notify new model */
	ufound(rptr);
}
Commit	Line	Data
fe81b478	1	/* reveng.c
	2	* Greg Cook, 9/Apr/2015
	3	*/
	4
	5	/* CRC RevEng, an arbitrary-precision CRC calculator and algorithm finder
	6	* Copyright (C) 2010, 2011, 2012, 2013, 2014, 2015 Gregory Cook
	7	*
	8	* This file is part of CRC RevEng.
	9	*
	10	* CRC RevEng is free software: you can redistribute it and/or modify
	11	* it under the terms of the GNU General Public License as published by
	12	* the Free Software Foundation, either version 3 of the License, or
	13	* (at your option) any later version.
	14	*
	15	* CRC RevEng is distributed in the hope that it will be useful,
	16	* but WITHOUT ANY WARRANTY; without even the implied warranty of
	17	* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
	18	* GNU General Public License for more details.
	19	*
	20	* You should have received a copy of the GNU General Public License
	21	* along with CRC RevEng. If not, see <http://www.gnu.org/licenses/>.
	22	*/
	23
	24	/* 2013-09-16: calini(), calout() work on shortest argument
	25	* 2013-06-11: added sequence number to uprog() calls
	26	* 2013-02-08: added polynomial range search
	27	* 2013-01-18: refactored model checking to pshres(); renamed chkres()
	28	* 2012-05-24: efficiently build Init contribution string
	29	* 2012-05-24: removed broken search for crossed-endian algorithms
	30	* 2012-05-23: rewrote engini() after Ewing; removed modini()
	31	* 2011-01-17: fixed ANSI C warnings
	32	* 2011-01-08: fixed calini(), modini() caters for crossed-endian algos
	33	* 2011-01-04: renamed functions, added calini(), factored pshres();
	34	* rewrote engini() and implemented quick Init search
	35	* 2011-01-01: reveng() initialises terminating entry, addparms()
	36	* initialises all fields
	37	* 2010-12-26: renamed CRC RevEng. right results, rejects polys faster
	38	* 2010-12-24: completed, first tests (unsuccessful)
	39	* 2010-12-21: completed modulate(), partial sketch of reveng()
	40	* 2010-12-19: started reveng
	41	*/
	42
	43	/* reveng() can in theory be modified to search for polynomials shorter
	44	* than the full width as well, but this imposes a heavy time burden on
	45	* the full width search, which is the primary use case, as well as
	46	* complicating the search range function introduced in version 1.1.0.
	47	* It is more effective to search for each shorter width directly.
	48	*/
	49
	50	#include <stdlib.h>
	51
	52	#define FILE void
	53	#include "reveng.h"
	54
	55	static poly_t modpol(const poly_t init, int rflags, int args, const poly_t argpolys);
	56	static void engini(int resc, model_t result, const poly_t divisor, int flags, int args, const poly_t argpolys);
	57	static void calout(int resc, model_t result, const poly_t divisor, const poly_t init, int flags, int args, const poly_t argpolys);
	58	static void calini(int resc, model_t result, const poly_t divisor, int flags, const poly_t xorout, int args, const poly_t argpolys);
	59	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);
	60
	61	static const poly_t pzero = PZERO;
	62
	63	model_t *
	64	reveng(const model_t guess, const poly_t qpoly, int rflags, int args, const poly_t argpolys) {
65	/* Complete the parameters of a model by calculation or brute search. */
66	poly_t pworks, wptr, rem, gpoly;
67	model_t result = NULL, rptr;
68	int resc = 0;
69	unsigned long spin = 0, seq = 0;
70
71	if(~rflags & R_HAVEP) {
72	/* The poly is not known.
73	* Produce a list of differences between the arguments.
74	*/
75	pworks = modpol(guess->init, rflags, args, argpolys);
76	if(!pworks \|\| !plen(*pworks)) {
77	free(pworks);
78	goto requit;
79	}
80	/* Initialise the guessed poly to the starting value. */
81	gpoly = pclone(guess->spoly);
82	/* Clear the least significant term, to be set in the
83	* loop. qpoly does not need fixing as it is only
84	* compared with odd polys.
85	*/
86	if(plen(gpoly))
87	pshift(&gpoly, gpoly, 0UL, 0UL, plen(gpoly) - 1UL, 1UL);
88
89	while(piter(&gpoly) && (~rflags & R_HAVEQ \|\| pcmp(&gpoly, &qpoly) < 0)) {
90	/* For each possible poly of this size, try
91	* dividing all the differences in the list.
92	*/
93	if(!(spin++ & R_SPMASK)) {
94	uprog(gpoly, guess->flags, seq++);
95	}
96	for(wptr = pworks; plen(*wptr); ++wptr) {
97	/* straight divide message by poly, don't multiply by x^n */
98	rem = pcrc(*wptr, gpoly, pzero, pzero, 0);
99	if(ptst(rem)) {
100	pfree(&rem);
101	break;
102	} else
103	pfree(&rem);
104	}
105	/* If gpoly divides all the differences, it is a
106	* candidate. Search for an Init value for this
107	* poly or if Init is known, log the result.
108	*/
109	if(!plen(*wptr)) {
110	/* gpoly is a candidate poly */
111	if(rflags & R_HAVEI && rflags & R_HAVEX)
112	chkres(&resc, &result, gpoly, guess->init, guess->flags, guess->xorout, args, argpolys);
113	else if(rflags & R_HAVEI)
114	calout(&resc, &result, gpoly, guess->init, guess->flags, args, argpolys);
115	else if(rflags & R_HAVEX)
116	calini(&resc, &result, gpoly, guess->flags, guess->xorout, args, argpolys);
117	else
118	engini(&resc, &result, gpoly, guess->flags, args, argpolys);
119	}
120	if(!piter(&gpoly))
121	break;
122	}
123	/* Finished with gpoly and the differences list, free them.
124	*/
125	pfree(&gpoly);
126	for(wptr = pworks; plen(*wptr); ++wptr)
127	pfree(wptr);
128	free(pworks);
129	}
130	else if(rflags & R_HAVEI && rflags & R_HAVEX)
131	/* All parameters are known! Submit the result if we get here */
132	chkres(&resc, &result, guess->spoly, guess->init, guess->flags, guess->xorout, args, argpolys);
133	else if(rflags & R_HAVEI)
134	/* Poly and Init are known, calculate XorOut */
135	calout(&resc, &result, guess->spoly, guess->init, guess->flags, args, argpolys);
136	else if(rflags & R_HAVEX)
137	/* Poly and XorOut are known, calculate Init */
138	calini(&resc, &result, guess->spoly, guess->flags, guess->xorout, args, argpolys);
139	else
140	/* Poly is known but not Init; search for Init. */
141	engini(&resc, &result, guess->spoly, guess->flags, args, argpolys);
142
143	requit:
144	if(!(result = realloc(result, ++resc * sizeof(model_t))))
145	uerror("cannot reallocate result array");
146	rptr = result + resc - 1;
147	rptr->spoly = pzero;
148	rptr->init = pzero;
149	rptr->flags = 0;
150	rptr->xorout = pzero;
151	rptr->check = pzero;
152	rptr->name = NULL;
153
154	return(result);
155	}
156
157	static poly_t *
158	modpol(const poly_t init, int rflags, int args, const poly_t *argpolys) {
159	/* Produce, in ascending length order, a list of differences
160	* between the arguments in the list by summing pairs of arguments.
161	* If R_HAVEI is not set in rflags, only pairs of equal length are
162	* summed.
163	* Otherwise, sums of right-aligned pairs are also returned, with
164	* the supplied init poly added to the leftmost terms of each
165	* poly of the pair.
166	*/
167	poly_t work, swap, result, rptr, *iptr;
168	const poly_t aptr, bptr, *eptr = argpolys + args;
169	unsigned long alen, blen;
170
171	if(args < 2) return(NULL);
172
173	if(!(result = malloc(((((args - 1) * args) >> 1) + 1) * sizeof(poly_t))))
174	uerror("cannot allocate memory for codeword table");
175
176	rptr = result;
177
178	for(aptr = argpolys; aptr < eptr; ++aptr) {
179	alen = plen(*aptr);
180	for(bptr = aptr + 1; bptr < eptr; ++bptr) {
181	blen = plen(*bptr);
182	if(alen == blen) {
183	work = pclone(*aptr);
184	psum(&work, *bptr, 0UL);
185	} else if(rflags & R_HAVEI && alen < blen) {
186	work = pclone(*bptr);
187	psum(&work, *aptr, blen - alen);
188	psum(&work, init, 0UL);
189	psum(&work, init, blen - alen);
190	} else if(rflags & R_HAVEI /* && alen > blen */) {
191	work = pclone(*aptr);
192	psum(&work, *bptr, alen - blen);
193	psum(&work, init, 0UL);
194	psum(&work, init, alen - blen);
195	} else
196	work = pzero;
197
198	if(plen(work))
199	pnorm(&work);
200	if((blen = plen(work))) {
201	/* insert work into result[] in ascending order of length */
202	for(iptr = result; iptr < rptr; ++iptr) {
203	if(plen(work) < plen(*iptr)) {
204	swap = *iptr;
205	*iptr = work;
206	work = swap;
207	}
208	else if(plen(*iptr) == blen && !pcmp(&work, iptr)) {
209	pfree(&work);
210	work = *--rptr;
211	break;
212	}
213	}
214	*rptr++ = work;
215	}
216	}
217	}
218	*rptr = pzero;
219	return(result);
220	}
221
222	static void
223	engini(int resc, model_t result, const poly_t divisor, int flags, int args, const poly_t argpolys) {
224	/* Search for init values implied by the arguments.
225	* Method from: Ewing, Gregory C. (March 2010).
226	* "Reverse-Engineering a CRC Algorithm". Christchurch:
227	* University of Canterbury.
228	* <http://www.cosc.canterbury.ac.nz/greg.ewing/essays/
229	* CRC-Reverse-Engineering.html>
230	*/
231	poly_t apoly = PZERO, bpoly, pone = PZERO, mat, jptr;
232	const poly_t aptr, bptr, *iptr;
233	unsigned long alen, blen, dlen, ilen, i, j;
234	int cy;
235
236	dlen = plen(divisor);
237
238	/* Allocate the CRC matrix */
239	if(!(mat = (poly_t ) malloc((dlen << 1) sizeof(poly_t))))
240	uerror("cannot allocate memory for CRC matrix");
241
242	/* Find arguments of the two shortest lengths */
243	alen = blen = plen(*(aptr = bptr = iptr = argpolys));
244	for(++iptr; iptr < argpolys + args; ++iptr) {
245	ilen = plen(*iptr);
246	if(ilen < alen) {
247	bptr = aptr; blen = alen;
248	aptr = iptr; alen = ilen;
249	} else if(ilen > alen && (aptr == bptr \|\| ilen < blen)) {
250	bptr = iptr; blen = ilen;
251	}
252	}
253	if(aptr == bptr) {
254	/* if no arguments are suitable, calculate Init with an
255	* assumed XorOut of 0. Create a padded XorOut
256	*/
257	palloc(&apoly, dlen);
258	calini(resc, result, divisor, flags, apoly, args, argpolys);
259	pfree(&apoly);
bf824347	260	free(mat);
fe81b478	261	return;
	262	}
	263
	264	/* Find the potential contribution of the bottom bit of Init */
	265	palloc(&pone, 1UL);
	266	piter(&pone);
	267	if(blen < (dlen << 1)) {
	268	palloc(&apoly, dlen); /* >= 1 */
	269	psum(&apoly, pone, (dlen << 1) - 1UL - blen); /* >= 0 */
	270	psum(&apoly, pone, (dlen << 1) - 1UL - alen); /* >= 1 */
	271	} else {
	272	palloc(&apoly, blen - dlen + 1UL); /* > dlen */
	273	psum(&apoly, pone, 0UL);
	274	psum(&apoly, pone, blen - alen); /* >= 1 */
	275	}
	276	if(plen(apoly) > dlen) {
	277	mat[dlen] = pcrc(apoly, divisor, pzero, pzero, 0);
	278	pfree(&apoly);
	279	} else {
	280	mat[dlen] = apoly;
	281	}
	282
	283	/* Find the actual contribution of Init */
	284	apoly = pcrc(*aptr, divisor, pzero, pzero, 0);
	285	bpoly = pcrc(*bptr, divisor, pzero, apoly, 0);
	286
	287	/* Populate the matrix */
	288	palloc(&apoly, 1UL);
	289	for(jptr=mat; jptr<mat+dlen; ++jptr)
	290	*jptr = pzero;
	291	for(iptr = jptr++; jptr < mat + (dlen << 1); iptr = jptr++)
	292	jptr = pcrc(apoly, divisor, iptr, pzero, P_MULXN);
	293	pfree(&apoly);
	294
	295	/* Transpose the matrix, augment with the Init contribution
	296	* and convert to row echelon form
	297	*/
	298	for(i=0UL; i<dlen; ++i) {
	299	apoly = pzero;
	300	iptr = mat + (dlen << 1);
	301	for(j=0UL; j<dlen; ++j)
	302	ppaste(&apoly, *--iptr, i, j, j + 1UL, dlen + 1UL);
	303	if(ptst(apoly))
	304	ppaste(&apoly, bpoly, i, dlen, dlen + 1UL, dlen + 1UL);
	305	j = pfirst(apoly);
	306	while(j < dlen && !pident(mat[j], pzero)) {
	307	psum(&apoly, mat[j], 0UL); /* pfirst(apoly) > j */
	308	j = pfirst(apoly);
	309	}
	310	if(j < dlen)
	311	mat[j] = apoly; /* pident(mat[j], pzero) \|\| pfirst(mat[j]) == j */
	312	else
	313	pfree(&apoly);
	314	}
	315	palloc(&bpoly, dlen + 1UL);
	316	psum(&bpoly, pone, dlen);
	317
	318	/* Iterate through all solutions */
	319	do {
	320	/* Solve the matrix by Gaussian elimination.
	321	* The parity of the result, masked by each row, should be even.
	322	*/
	323	cy = 1;
	324	apoly = pclone(bpoly);
325	jptr = mat + dlen;
326	for(i=0UL; i<dlen; ++i) {
327	/* Compute next bit of Init */
328	if(pmpar(apoly, *--jptr))
329	psum(&apoly, pone, dlen - 1UL - i);
330	/* Toggle each zero row with carry, for next iteration */
331	if(cy) {
332	if(pident(*jptr, pzero)) {
333	/* 0 to 1, no carry */
334	*jptr = bpoly;
335	cy = 0;
336	} else if(pident(*jptr, bpoly)) {
337	/* 1 to 0, carry forward */
338	*jptr = pzero;
339	}
340	}
341	}
342
343	/* Trim the augment mask bit */
344	praloc(&apoly, dlen);
345
346	/* Test the Init value and add to results if correct */
347	calout(resc, result, divisor, apoly, flags, args, argpolys);
348	pfree(&apoly);
349	} while(!cy);
350	pfree(&pone);
351	pfree(&bpoly);
352
353	/* Free the matrix. */
354	for(jptr=mat; jptr < mat + (dlen << 1); ++jptr)
355	pfree(jptr);
356	free(mat);
357	}
358
359	static void
360	calout(int resc, model_t result, const poly_t divisor, const poly_t init, int flags, int args, const poly_t argpolys) {
361	/* Calculate Xorout, check it against all the arguments and
362	* add to results if consistent.
363	*/
364	poly_t xorout;
365	const poly_t aptr, iptr;
366	unsigned long alen, ilen;
367
368	if(args < 1) return;
369
370	/* find argument of the shortest length */
371	alen = plen(*(aptr = iptr = argpolys));
372	for(++iptr; iptr < argpolys + args; ++iptr) {
373	ilen = plen(*iptr);
374	if(ilen < alen) {
375	aptr = iptr; alen = ilen;
376	}
377	}
378
379	xorout = pcrc(*aptr, divisor, init, pzero, 0);
380	/* On little-endian algorithms, the calculations yield
381	* the reverse of the actual xorout: in the Williams
382	* model, the refout stage intervenes between init and
383	* xorout.
384	*/
385	if(flags & P_REFOUT)
386	prev(&xorout);
387
388	/* Submit the model to the results table.
389	* Could skip the shortest argument but we wish to check our
390	* calculation.
391	*/
392	chkres(resc, result, divisor, init, flags, xorout, args, argpolys);
393	pfree(&xorout);
394	}
395
396	static void
397	calini(int resc, model_t result, const poly_t divisor, int flags, const poly_t xorout, int args, const poly_t argpolys) {
398	/* Calculate Init, check it against all the arguments and add to
399	* results if consistent.
400	*/
401	poly_t rcpdiv, rxor, arg, init;
402	const poly_t aptr, iptr;
403	unsigned long alen, ilen;
404
405	if(args < 1) return;
406
407	/* find argument of the shortest length */
408	alen = plen(*(aptr = iptr = argpolys));
409	for(++iptr; iptr < argpolys + args; ++iptr) {
410	ilen = plen(*iptr);
411	if(ilen < alen) {
412	aptr = iptr; alen = ilen;
413	}
414	}
415
416	rcpdiv = pclone(divisor);
417	prcp(&rcpdiv);
418	/* If the algorithm is reflected, an ordinary CRC requires the
419	* model's XorOut to be reversed, as XorOut follows the RefOut
420	* stage. To reverse the CRC calculation we need rxor to be the
421	* mirror image of the forward XorOut.
422	*/
423	rxor = pclone(xorout);
424	if(~flags & P_REFOUT)
425	prev(&rxor);
426	arg = pclone(*aptr);
427	prev(&arg);
428
429	init = pcrc(arg, rcpdiv, rxor, pzero, 0);
430	pfree(&arg);
431	pfree(&rxor);
432	pfree(&rcpdiv);
433	prev(&init);
434
435	/* Submit the model to the results table.
436	* Could skip the shortest argument but we wish to check our
437	* calculation.
438	*/
439	chkres(resc, result, divisor, init, flags, xorout, args, argpolys);
440	pfree(&init);
441	}
442
443	static void
444	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) {
445	/* Checks a model against the argument list, and adds to the
446	* external results table if consistent.
447	* Extends the result array and update the external pointer if
448	* necessary.
449	*/
450	model_t *rptr;
451	poly_t xor, crc;
452	const poly_t aptr = argpolys, const eptr = argpolys + args;
453
454	/* If the algorithm is reflected, an ordinary CRC requires the
455	* model's XorOut to be reversed, as XorOut follows the RefOut
456	* stage.
457	*/
458	xor = pclone(xorout);
459	if(flags & P_REFOUT)
460	prev(&xor);
461
462	for(; aptr < eptr; ++aptr) {
463	crc = pcrc(*aptr, divisor, init, xor, 0);
464	if(ptst(crc)) {
465	pfree(&crc);
466	break;
467	} else {
468	pfree(&crc);
469	}
470	}
471	pfree(&xor);
472	if(aptr != eptr) return;
473
474	if(!(result = realloc(result, ++resc sizeof(model_t))))
475	uerror("cannot reallocate result array");
476
477	rptr = result + resc - 1;
478	rptr->spoly = pclone(divisor);
479	rptr->init = pclone(init);
480	rptr->flags = flags;
481	rptr->xorout = pclone(xorout);
482	rptr->name = NULL;
483
484	/* compute check value for this model */
485	mcheck(rptr);
486
487	/* callback to notify new model */
488	ufound(rptr);
489	}