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 | } |