]> git.zerfleddert.de Git - proxmark3-svn/blob - client/reveng/poly.c
e4a8e8f950f307c2c4a52f2d38cdcccac68b9da3
[proxmark3-svn] / client / reveng / poly.c
1 /* poly.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 /* 2015-04-03: added direct mode to strtop()
25 * 2014-01-11: added LOFS(), RNDUP()
26 * 2013-09-16: SIZE(), IDX(), OFS() macros bitshift if BMP_POF2
27 * 2013-02-07: conditional non-2^n fix, pmpar() return mask constant type
28 * 2013-01-17: fixed pfirst(), plast() for non-2^n BMP_BIT
29 * 2012-07-16: added pident()
30 * 2012-05-23: added pmpar()
31 * 2012-03-03: internal lookup tables stored better
32 * 2012-03-02: fixed full-width masking in filtop()
33 * 2011-09-06: added prevch()
34 * 2011-08-27: fixed zero test in piter()
35 * 2011-01-17: fixed ANSI C warnings, uses bmp_t type
36 * 2011-01-15: palloc() and praloc() gracefully handle lengths slightly
37 * less than ULONG_MAX
38 * 2011-01-15: strtop() error on invalid argument. pkchop() special case
39 * when argument all zeroes
40 * 2011-01-14: added pkchop()
41 * 2011-01-04: fixed bogus final length calculation in wide pcrc()
42 * 2011-01-02: faster, more robust prcp()
43 * 2011-01-01: commented functions, full const declarations, all-LUT rev()
44 * 2010-12-26: renamed CRC RevEng
45 * 2010-12-18: removed pmods(), finished pcrc(), added piter()
46 * 2010-12-17: roughed out pcrc(). difficult, etiam aberat musa heri :(
47 * 2010-12-15: added psnorm(), psncmp(); optimised pnorm(); fix to praloc()
48 * 2010-12-14: strtop() resets count between passes
49 * 2010-12-12: added pright()
50 * 2010-12-11: filtop won't read more than length bits
51 * 2010-12-10: finished filtop. 26 public functions
52 * 2010-12-05: finished strtop, pxsubs; unit tests
53 * 2010-12-02: project started
54 */
55
56 /* Note: WELL-FORMED poly_t objects have a valid bitmap pointer pointing
57 * to a malloc()-ed array of at least as many bits as stated in its
58 * length field. Any poly_t with a length of 0 is also a WELL-FORMED
59 * poly_t (whatever value the bitmap pointer has.)
60 * All poly_t objects passed to and from functions must be WELL-FORMED
61 * unless otherwise stated.
62 *
63 * CLEAN (or CANONICAL) poly_t objects are WELL-FORMED objects in which
64 * all spare bits in the bitmap word containing the last bit are zero.
65 * (Any excess allocated words will not be accessed.)
66 *
67 * SEMI-NORMALISED poly_t objects are CLEAN objects in which the last
68 * bit, at position (length - 1), is one.
69 *
70 * NORMALISED poly_t objects are SEMI-NORMALISED objects in which the
71 * first bit is one.
72 *
73 * pfree() should be called on every poly_t object (including
74 * those returned by functions) after its last use.
75 * As always, free() should be called on every malloc()-ed string after
76 * its last use.
77 */
78
79 #include <limits.h>
80 #include <stdio.h>
81 #include <stdlib.h>
82 #include "reveng.h"
83
84 static bmp_t getwrd(const poly_t poly, unsigned long iter);
85 static bmp_t rev(bmp_t accu, int bits);
86 static void prhex(char **spp, bmp_t bits, int flags, int bperhx);
87
88 static const poly_t pzero = PZERO;
89
90 /* word number (0..m-1) of var'th bit (0..n-1) */
91 #if BMP_POF2 >= 5
92 # define IDX(var) ((var) >> BMP_POF2)
93 #else
94 # define IDX(var) ((var) / BMP_BIT)
95 #endif
96
97 /* size of polynomial with var bits */
98 #if BMP_POF2 >= 5
99 # define SIZE(var) ((BMP_BIT - 1UL + (var)) >> BMP_POF2)
100 #else
101 # define SIZE(var) ((BMP_BIT - 1UL + (var)) / BMP_BIT)
102 #endif
103
104 /* polynomial length rounded up to BMP_BIT */
105 #ifdef BMP_POF2
106 # define RNDUP(var) (~(BMP_BIT - 1UL) & (BMP_BIT - 1UL + (var)))
107 #else
108 # define RNDUP(var) ((BMP_BIT - (var) % BMP_BIT) % BMP_BIT + (var))
109 #endif
110
111 /* bit offset (0..BMP_BIT-1, 0 = LSB) of var'th bit (0..n-1) */
112 #ifdef BMP_POF2
113 # define OFS(var) ((int) ((BMP_BIT - 1UL) & ~(var)))
114 #else
115 # define OFS(var) ((int) (BMP_BIT - 1UL - (var) % BMP_BIT))
116 #endif
117
118 /* bit offset (0..BMP_BIT-1, 0 = MSB) of var'th bit (0..n-1) */
119 #ifdef BMP_POF2
120 # define LOFS(var) ((int) ((BMP_BIT - 1UL) & (var)))
121 #else
122 # define LOFS(var) ((int) ((var) % BMP_BIT))
123 #endif
124
125 poly_t
126 filtop(FILE *input, unsigned long length, int flags, int bperhx) {
127 /* reads binary data from input into a poly_t until EOF or until
128 * length bits are read. Characters are read until
129 * ceil(bperhx / CHAR_BIT) bits are collected; if P_LTLBYT is
130 * set in flags then the first character contains the LSB,
131 * otherwise the last one does. The least significant bperhx
132 * bits are taken, reflected (if P_REFIN) and appended to the
133 * result, then more characters are read. The maximum number of
134 * characters read is
135 * floor(length / bperhx) * ceil(bperhx / * CHAR_BIT).
136 * The returned poly_t is CLEAN.
137 */
138
139 bmp_t accu = BMP_C(0);
140 bmp_t mask = bperhx == BMP_BIT ? ~BMP_C(0) : (BMP_C(1) << bperhx) - BMP_C(1);
141 unsigned long iter = 0UL, idx;
142 int cmask = ~(~0U << CHAR_BIT), c;
143 int count = 0, ofs;
144 poly_t poly = PZERO;
145 if(bperhx == 0) return(poly);
146
147 length -= length % bperhx;
148 palloc(&poly, length); /* >= 0 */
149
150 while(iter < length && (c = fgetc(input)) != EOF) {
151 if(flags & P_LTLBYT)
152 accu |= (bmp_t) (c & cmask) << count;
153 else
154 accu = (accu << CHAR_BIT) | (bmp_t) (c & cmask);
155 count += CHAR_BIT;
156 if(count >= bperhx) {
157 /* the low bperhx bits of accu contain bits of the poly.*/
158 iter += bperhx;
159 count = 0;
160 if(flags & P_REFIN)
161 accu = rev(accu, bperhx);
162 accu &= mask;
163
164 /* iter >= bperhx > 0 */
165 idx = IDX(iter - 1UL);
166 ofs = OFS(iter - 1UL);
167 poly.bitmap[idx] |= accu << ofs;
168 if(ofs + bperhx > BMP_BIT) {
169 poly.bitmap[idx-1] |= accu >> (BMP_BIT - ofs);
170 }
171 accu = BMP_C(0); /* only needed for P_LTLBYT */
172 }
173 }
174 praloc(&poly, iter);
175 return(poly);
176 }
177
178 poly_t
179 strtop(const char *string, int flags, int bperhx) {
180 /* Converts a hex or character string to a poly_t.
181 * Each character is converted to a hex nibble yielding 4 bits
182 * unless P_DIRECT, when each character yields CHAR_BIT bits.
183 * Nibbles and characters are accumulated left-to-right
184 * unless P_DIRECT && P_LTLBYT, when they are accumulated
185 * right-to-left without reflection.
186 * As soon as at least bperhx bits are accumulated, the
187 * rightmost bperhx bits are reflected (if P_REFIN)
188 * and appended to the poly. When !P_DIRECT:
189 * bperhx=8 reads hex nibbles in pairs
190 * bperhx=7 reads hex nibbles in pairs and discards
191 * b3 of first nibble
192 * bperhx=4 reads hex nibbles singly
193 * bperhx=3 reads octal
194 * bperhx=1 reads longhand binary
195 * in theory if !P_REFIN, bperhx can be any multiple of 4
196 * with equal effect
197 * The returned poly_t is CLEAN.
198 */
199
200 /* make two passes, one to determine the poly size
201 * one to populate the bitmap
202 */
203 unsigned long length = 1UL, idx;
204 bmp_t accu;
205 bmp_t mask = bperhx == BMP_BIT ? ~BMP_C(0) : (BMP_C(1) << bperhx) - BMP_C(1);
206 int pass, count, ofs;
207 int cmask = ~(~0U << CHAR_BIT), c;
208 const char *s;
209
210 poly_t poly = PZERO;
211 if(bperhx > BMP_BIT || bperhx <= 0 || string == NULL || *string == '\0')
212 return(poly);
213
214 for(pass=0; pass<2 && length > 0UL; ++pass) {
215 s = string;
216 length = 0UL;
217 count = 0;
218 accu = BMP_C(0);
219 while((c = *s++)) {
220 if(flags & P_DIRECT) {
221 if(flags & P_LTLBYT)
222 accu |= (bmp_t) (c & cmask) << count;
223 else
224 accu = (accu << CHAR_BIT) | (bmp_t) (c & cmask);
225 count += CHAR_BIT;
226 } else {
227 if(c == ' ' || c == '\t' || c == '\r' || c == '\n') continue;
228 accu <<= 4;
229 count += 4;
230 switch(c) {
231 case '0':
232 case '1':
233 case '2':
234 case '3':
235 case '4':
236 case '5':
237 case '6':
238 case '7':
239 case '8':
240 case '9':
241 accu |= (bmp_t) c - '0';
242 break;
243 case 'A':
244 case 'a':
245 accu |= BMP_C(0xa);
246 break;
247 case 'B':
248 case 'b':
249 accu |= BMP_C(0xb);
250 break;
251 case 'C':
252 case 'c':
253 accu |= BMP_C(0xc);
254 break;
255 case 'D':
256 case 'd':
257 accu |= BMP_C(0xd);
258 break;
259 case 'E':
260 case 'e':
261 accu |= BMP_C(0xe);
262 break;
263 case 'F':
264 case 'f':
265 accu |= BMP_C(0xf);
266 break;
267 default:
268 uerror("invalid character in hexadecimal argument");
269 }
270 }
271
272 if(count >= bperhx) {
273 /* the low bperhx bits of accu contain bits of the poly.
274 * in pass 0, increment length by bperhx.
275 * in pass 1, put the low bits of accu into the bitmap. */
276 length += bperhx;
277 count = 0;
278 if(pass == 1) {
279 if(flags & P_REFIN)
280 accu = rev(accu, bperhx);
281 accu &= mask;
282
283 /* length >= bperhx > 0 */
284 idx = IDX(length - 1);
285 ofs = OFS(length - 1);
286 poly.bitmap[idx] |= accu << ofs;
287 if(ofs + bperhx > BMP_BIT)
288 poly.bitmap[idx-1] |= accu >> (BMP_BIT - ofs);
289 accu = BMP_C(0); /* only needed for P_LTLBYT */
290 }
291 }
292 }
293 if(pass == 0) palloc(&poly, length);
294 }
295 return(poly);
296 }
297
298 char *
299 ptostr(const poly_t poly, int flags, int bperhx) {
300 /* Returns a malloc()-ed string containing a hexadecimal
301 * representation of poly. See phxsubs().
302 */
303 return(pxsubs(poly, flags, bperhx, 0UL, poly.length));
304 }
305
306 char *
307 pxsubs(const poly_t poly, int flags, int bperhx, unsigned long start, unsigned long end) {
308 /* Returns a malloc()-ed string containing a hexadecimal
309 * representation of a portion of poly, from bit offset start to
310 * (end - 1) inclusive. The output is grouped into words of
311 * bperhx bits each. If P_RTJUST then the first word is padded
312 * with zeroes at the MSB end to make a whole number of words,
313 * otherwise the last word is padded at the LSB end. After
314 * justification the bperhx bits of each word are reversed (if
315 * P_REFOUT) and printed as a hex sequence, with words
316 * optionally separated by spaces (P_SPACE).
317 * If end exceeds the length of poly then zero bits are appended
318 * to make up the difference, in which case poly must be CLEAN.
319 */
320 char *string, *sptr;
321 unsigned long size, iter;
322 bmp_t accu;
323 bmp_t mask = bperhx == BMP_BIT ? ~BMP_C(0) : (BMP_C(1) << bperhx) - BMP_C(1);
324 int cperhx, part;
325
326 if(bperhx <= 0 || bperhx > BMP_BIT) return(NULL);
327
328 if(start > poly.length) start = poly.length;
329 if(end > poly.length) end = poly.length;
330 if(end < start) end = start;
331
332 cperhx = (bperhx + 3) >> 2;
333 if(flags & P_SPACE) ++cperhx;
334
335 size = (end - start + bperhx - 1UL) / bperhx;
336 size *= cperhx;
337 if(!size || ~flags & P_SPACE) ++size; /* for trailing null */
338
339 if(!(sptr = string = (char *) malloc(size)))
340 uerror("cannot allocate memory for string");
341
342 size = end - start;
343 part = (int) size % bperhx;
344 if(part && flags & P_RTJUST) {
345 iter = start + part;
346 accu = getwrd(poly, iter - 1UL) & ((BMP_C(1) << part) - BMP_C(1));
347 if(flags & P_REFOUT)
348 /* best to reverse over bperhx rather than part, I think
349 * e.g. converting a 7-bit poly to 8-bit little-endian hex
350 */
351 accu = rev(accu, bperhx);
352 prhex(&sptr, accu, flags, bperhx);
353 if(flags & P_SPACE && size > iter) *sptr++ = ' ';
354 } else {
355 iter = start;
356 }
357
358 while((iter+=bperhx) <= end) {
359 accu = getwrd(poly, iter - 1UL) & mask;
360 if(flags & P_REFOUT)
361 accu = rev(accu, bperhx);
362 prhex(&sptr, accu, flags, bperhx);
363 if(flags & P_SPACE && size > iter) *sptr++ = ' ';
364 }
365
366 if(part && ~flags & P_RTJUST) {
367 accu = getwrd(poly, end - 1UL);
368 if(flags & P_REFOUT)
369 accu = rev(accu, part);
370 else
371 accu = accu << (bperhx - part) & mask;
372 prhex(&sptr, accu, flags, bperhx);
373 }
374 *sptr = '\0';
375 return(string);
376 }
377
378 poly_t
379 pclone(const poly_t poly) {
380 /* Returns a freestanding copy of poly. Does not clean poly or
381 * the result.
382 */
383 poly_t clone = PZERO;
384
385 pcpy(&clone, poly);
386 return(clone);
387 }
388
389 void
390 pcpy(poly_t *dest, const poly_t src) {
391 /* Assigns (copies) src into dest. Does not clean src or dest.
392 */
393 unsigned long iter, idx;
394
395 praloc(dest, src.length);
396 for(iter=0UL, idx=0UL; iter < src.length; iter += BMP_BIT, ++idx)
397 dest->bitmap[idx] = src.bitmap[idx];
398 }
399
400 void
401 pcanon(poly_t *poly) {
402 /* Converts poly into a CLEAN object by freeing unused bitmap words
403 * and clearing any bits in the last word beyond the last bit.
404 * The length field has absolute priority over the contents of the bitmap.
405 * Canonicalisation differs from normalisation in that leading and trailing
406 * zero terms are significant and preserved.
407 * poly may or may not be WELL-FORMED.
408 */
409 praloc(poly, poly->length);
410 }
411
412 void
413 pnorm(poly_t *poly) {
414 /* Converts poly into a NORMALISED object by removing leading
415 * and trailing zeroes, so that the polynomial starts and ends
416 * with significant terms.
417 * poly may or may not be WELL-FORMED.
418 */
419 unsigned long first;
420
421 /* call pcanon() here so pfirst() and plast() return the correct
422 * results
423 */
424 pcanon(poly);
425 first = pfirst(*poly);
426 if(first)
427 pshift(poly, *poly, 0UL, first, plast(*poly), 0UL);
428 else
429 praloc(poly, plast(*poly));
430 }
431
432 void
433 psnorm(poly_t *poly) {
434 /* Converts poly into a SEMI-NORMALISED object by removing
435 * trailing zeroes, so that the polynomial ends with a
436 * significant term.
437 * poly may or may not be WELL-FORMED.
438 */
439
440 /* call pcanon() here so plast() returns the correct result */
441 pcanon(poly);
442 praloc(poly, plast(*poly));
443 }
444
445 void
446 pchop(poly_t *poly) {
447 /* Normalise poly, then chop off the highest significant term
448 * (produces a SEMI-NORMALISED object). poly becomes a suitable
449 * divisor for pcrc().
450 * poly may or may not be WELL-FORMED.
451 */
452
453 /* call pcanon() here so pfirst() and plast() return correct
454 * results
455 */
456 pcanon(poly);
457 pshift(poly, *poly, 0UL, pfirst(*poly) + 1UL, plast(*poly), 0UL);
458 }
459
460 void
461 pkchop(poly_t *poly) {
462 /* Convert poly from Koopman notation to chopped form (produces
463 * a SEMI-NORMALISED object). poly becomes a suitable divisor
464 * for pcrc().
465 * poly may or may not be WELL-FORMED.
466 */
467 unsigned long first;
468
469 /* call pcanon() here so pfirst() returns the correct result */
470 pcanon(poly);
471 first = pfirst(*poly);
472 if(first >= poly->length) {
473 pfree(poly);
474 return;
475 }
476 pshift(poly, *poly, 0UL, first + 1UL, poly->length, 1UL);
477 piter(poly);
478 }
479
480 unsigned long
481 plen(const poly_t poly) {
482 /* Return length of polynomial.
483 * poly may or may not be WELL-FORMED.
484 */
485 return(poly.length);
486 }
487
488 int
489 pcmp(const poly_t *a, const poly_t *b) {
490 /* Compares poly_t objects for identical sizes and contents.
491 * a and b must be CLEAN.
492 * Defines a total order relation for sorting, etc. although
493 * mathematically, polynomials of equal degree are no greater or
494 * less than one another.
495 */
496 unsigned long iter;
497 bmp_t *aptr, *bptr;
498
499 if(!a || !b) return(!b - !a);
500 if(a->length < b->length) return(-1);
501 if(a->length > b->length) return(1);
502 aptr = a->bitmap;
503 bptr = b->bitmap;
504 for(iter=0UL; iter < a->length; iter += BMP_BIT) {
505 if(*aptr < *bptr)
506 return(-1);
507 if(*aptr++ > *bptr++)
508 return(1);
509 }
510 return(0);
511 }
512
513 int
514 psncmp(const poly_t *a, const poly_t *b) {
515 /* Compares polys for identical effect, i.e. as though the
516 * shorter poly were padded with zeroes to the length of the
517 * longer.
518 * a and b must still be CLEAN, therefore psncmp() is *not*
519 * identical to pcmp() on semi-normalised polys as psnorm()
520 * clears the slack space.
521 */
522 unsigned long length, iter, idx;
523 bmp_t aword, bword;
524 if(!a || !b) return(!b - !a);
525 length = (a->length > b->length) ? a->length : b->length;
526 for(iter = 0UL, idx = 0UL; iter < length; iter += BMP_BIT, ++idx) {
527 aword = (iter < a->length) ? a->bitmap[idx] : BMP_C(0);
528 bword = (iter < b->length) ? b->bitmap[idx] : BMP_C(0);
529 if(aword < bword)
530 return(-1);
531 if(aword > bword)
532 return(1);
533 }
534 return(0);
535 }
536
537
538 int
539 ptst(const poly_t poly) {
540 /* Tests whether a polynomial equals zero. Returns 0 if equal,
541 * a nonzero value otherwise.
542 * poly must be CLEAN.
543 */
544 unsigned long iter;
545 bmp_t *bptr;
546 if(!poly.bitmap) return(0);
547 for(iter = 0UL, bptr = poly.bitmap; iter < poly.length; iter += BMP_BIT)
548 if(*bptr++) return(1);
549 return(0);
550 }
551
552 unsigned long
553 pfirst(const poly_t poly) {
554 /* Returns the index of the first nonzero term in poly. If none
555 * is found, returns the length of poly.
556 * poly must be CLEAN.
557 */
558 unsigned long idx = 0UL, size = SIZE(poly.length);
559 bmp_t accu = BMP_C(0); /* initialiser for Acorn C */
560 unsigned int probe = BMP_SUB, ofs = 0;
561
562 while(idx < size && !(accu = poly.bitmap[idx])) ++idx;
563 if(idx >= size) return(poly.length);
564 while(probe) {
565 #ifndef BMP_POF2
566 while((ofs | probe) >= (unsigned int) BMP_BIT) probe >>= 1;
567 #endif
568 if(accu >> (ofs | probe)) ofs |= probe;
569 probe >>= 1;
570 }
571
572 return(BMP_BIT - 1UL - ofs + idx * BMP_BIT);
573 }
574
575 unsigned long
576 plast(const poly_t poly) {
577 /* Returns 1 plus the index of the last nonzero term in poly.
578 * If none is found, returns zero.
579 * poly must be CLEAN.
580 */
581 unsigned long idx, size = SIZE(poly.length);
582 bmp_t accu;
583 unsigned int probe = BMP_SUB, ofs = 0;
584
585 if(!poly.length) return(0UL);
586 idx = size - 1UL;
587 while(idx && !(accu = poly.bitmap[idx])) --idx;
588 if(!idx && !(accu = poly.bitmap[idx])) return(0UL);
589 /* now accu == poly.bitmap[idx] and contains last significant term */
590 while(probe) {
591 #ifndef BMP_POF2
592 while((ofs | probe) >= (unsigned int) BMP_BIT) probe >>= 1;
593 #endif
594 if(accu << (ofs | probe)) ofs |= probe;
595 probe >>= 1;
596 }
597
598 return(idx * BMP_BIT + ofs + 1UL);
599 }
600
601 poly_t
602 psubs(const poly_t src, unsigned long head, unsigned long start, unsigned long end, unsigned long tail) {
603 poly_t dest = PZERO;
604 pshift(&dest, src, head, start, end, tail);
605 return(dest);
606 }
607
608 void
609 pright(poly_t *poly, unsigned long length) {
610 /* Trims or extends poly to length at the left edge, prepending
611 * zeroes if necessary. Analogous to praloc() except the
612 * rightmost terms of poly are preserved.
613 * On entry, poly may or may not be WELL-FORMED.
614 * On exit, poly is CLEAN.
615 */
616
617 if(length > poly->length)
618 pshift(poly, *poly, length - poly->length, 0UL, poly->length, 0UL);
619 else if(length < poly->length)
620 pshift(poly, *poly, 0UL, poly->length - length, poly->length, 0UL);
621 else
622 praloc(poly, poly->length);
623 }
624
625 void
626 pshift(poly_t *dest, const poly_t src, unsigned long head, unsigned long start, unsigned long end, unsigned long tail) {
627 /* copies bits start to end-1 of src to dest, plus the number of leading and trailing zeroes given by head and tail.
628 * end may exceed the length of src in which case more zeroes are appended.
629 * dest may point to src, in which case the poly is edited in place.
630 * On exit, dest is CLEAN.
631 */
632
633 unsigned long length, fulllength, size, fullsize, iter, idx, datidx;
634 /* condition inputs; end, head and tail may be any value */
635 if(end < start) end = start;
636
637 length = end - start + head;
638 fulllength = length + tail;
639 if(fulllength > src.length)
640 praloc(dest, fulllength);
641 else
642 praloc(dest, src.length);
643
644 /* number of words in new poly */
645 size = SIZE(length);
646 fullsize = SIZE(fulllength);
647 /* array index of first word ending up with source material */
648 datidx = IDX(head);
649
650 if(head > start && end > start) {
651 /* shifting right, size > 0 */
652 /* index of the source bit ending up in the LSB of the last word
653 * size * BMP_BIT >= length > head > 0 */
654 iter = size * BMP_BIT - head - 1UL;
655 for(idx = size - 1UL; idx > datidx; iter -= BMP_BIT, --idx)
656 dest->bitmap[idx] = getwrd(src, iter);
657 dest->bitmap[idx] = getwrd(src, iter);
658 /* iter == size * BMP_BIT - head - 1 - BMP_BIT * (size - 1 - datidx)
659 * == BMP_BIT * (size - size + 1 + datidx) - head - 1
660 * == BMP_BIT * (1 + head / BMP_BIT) - head - 1
661 * == BMP_BIT + head - head % BMP_BIT - head - 1
662 * == BMP_BIT - head % BMP_BIT - 1
663 * >= 0
664 */
665 } else if(head <= start) {
666 /* shifting left or copying */
667 /* index of the source bit ending up in the LSB of bitmap[idx] */
668 iter = start - head + BMP_BIT - 1UL;
669 for(idx = datidx; idx < size; iter += BMP_BIT, ++idx)
670 dest->bitmap[idx] = getwrd(src, iter);
671 }
672
673 /* clear head */
674 for(idx = 0UL; idx < datidx; ++idx)
675 dest->bitmap[idx] = BMP_C(0);
676 if(size)
677 dest->bitmap[datidx] &= ~BMP_C(0) >> LOFS(head);
678
679 /* clear tail */
680 if(LOFS(length))
681 dest->bitmap[size - 1UL] &= ~(~BMP_C(0) >> LOFS(length));
682 for(idx = size; idx < fullsize; ++idx)
683 dest->bitmap[idx] = BMP_C(0);
684
685 /* call praloc to shrink poly if required */
686 if(dest->length > fulllength)
687 praloc(dest, fulllength);
688 }
689
690 void
691 ppaste(poly_t *dest, const poly_t src, unsigned long skip, unsigned long seek, unsigned long end, unsigned long fulllength) {
692 /* pastes terms of src, starting from skip, to positions seek to end-1 of dest
693 * then sets length of dest to fulllength (>= end)
694 * to paste n terms of src, give end = seek + n
695 * to truncate dest at end of paste, set fulllength = end
696 * to avoid truncating, set fulllength = plen(*dest)
697 * dest may point to src, in which case the poly is edited in place.
698 * src must be CLEAN in the case that the end is overrun.
699 * On exit, dest is CLEAN.
700 */
701 bmp_t mask;
702 unsigned long seekidx, endidx, iter;
703 int seekofs;
704 if(end < seek) end = seek;
705 if(fulllength < end) fulllength = end;
706
707 /* expand dest if necessary. don't shrink as dest may be src */
708 if(fulllength > dest->length)
709 praloc(dest, fulllength);
710 seekidx = IDX(seek);
711 endidx = IDX(end);
712 seekofs = OFS(seek);
713 /* index of the source bit ending up in the LSB of the first modified word */
714 iter = skip + seekofs;
715 if(seekidx == endidx) {
716 /* paste affects one word (traps end = seek case) */
717 mask = ((BMP_C(1) << seekofs) - (BMP_C(1) << OFS(end))) << 1;
718 dest->bitmap[seekidx] = (dest->bitmap[seekidx] & ~mask) | (getwrd(src, iter) & mask);
719 } else if(seek > skip) {
720 /* shifting right */
721 /* index of the source bit ending up in the LSB of the last modified word */
722 iter += (endidx - seekidx) * BMP_BIT;
723 mask = ~BMP_C(0) >> LOFS(end);
724 dest->bitmap[endidx] = (dest->bitmap[endidx] & mask) | (getwrd(src, iter) & ~mask);
725 for(iter -= BMP_BIT, --endidx; endidx > seekidx; iter -= BMP_BIT, --endidx)
726 dest->bitmap[endidx] = getwrd(src, iter);
727 mask = ~BMP_C(0) >> LOFS(seek);
728 dest->bitmap[endidx] = (dest->bitmap[endidx] & ~mask) | (getwrd(src, iter) & mask);
729 /* iter == skip + seekofs + (endidx - seekidx) * BMP_BIT - BMP_BIT * (endidx - seekidx)
730 * == skip + seekofs + BMP_BIT * (endidx - seekidx - endidx + seekidx)
731 * == skip + seekofs
732 * >= 0
733 */
734 } else {
735 /* shifting left or copying */
736 mask = ~BMP_C(0) >> LOFS(seek);
737 dest->bitmap[seekidx] = (dest->bitmap[seekidx] & ~mask) | (getwrd(src, iter) & mask);
738 for(iter += BMP_BIT, ++seekidx; seekidx < endidx; iter += BMP_BIT, ++seekidx)
739 dest->bitmap[seekidx] = getwrd(src, iter);
740 mask = ~BMP_C(0) >> LOFS(end);
741 dest->bitmap[seekidx] = (dest->bitmap[seekidx] & mask) | (getwrd(src, iter) & ~mask);
742 }
743 /* shrink poly if required */
744 if(dest->length > fulllength)
745 praloc(dest, fulllength);
746 }
747
748 void
749 pdiff(poly_t *dest, const poly_t src, unsigned long ofs) {
750 /* Subtract src from dest (modulo 2) at offset ofs.
751 * In modulo 2 arithmetic, subtraction is equivalent to addition
752 * We include an alias for those who wish to retain the distinction
753 * src and dest must be CLEAN.
754 */
755 psum(dest, src, ofs);
756 }
757
758 void
759 psum(poly_t *dest, const poly_t src, unsigned long ofs) {
760 /* Adds src to dest (modulo 2) at offset ofs.
761 * When ofs == dest->length, catenates src on to dest.
762 * src and dest must be CLEAN.
763 */
764 unsigned long fulllength, idx, iter, end;
765
766 fulllength = ofs + src.length;
767 if(fulllength > dest->length)
768 praloc(dest, fulllength);
769 /* array index of first word in dest to be modified */
770 idx = IDX(ofs);
771 /* index of bit in src to be added to LSB of dest->bitmap[idx] */
772 iter = OFS(ofs);
773 /* stop value for iter */
774 end = BMP_BIT - 1UL + src.length;
775 for(; iter < end; iter += BMP_BIT, ++idx)
776 dest->bitmap[idx] ^= getwrd(src, iter);
777 }
778
779 void
780 prev(poly_t *poly) {
781 /* Reverse or reciprocate a polynomial.
782 * On exit, poly is CLEAN.
783 */
784 unsigned long leftidx = 0UL, rightidx = SIZE(poly->length);
785 unsigned long ofs = LOFS(BMP_BIT - LOFS(poly->length));
786 unsigned long fulllength = poly->length + ofs;
787 bmp_t accu;
788
789 if(ofs) {
790 /* removable optimisation */
791 if(poly->length < (unsigned long) BMP_BIT) {
792 *poly->bitmap = rev(*poly->bitmap >> ofs, (int) poly->length) << ofs;
793 return;
794 }
795 }
796
797 /* claim remaining bits of last word (as we use public function pshift()) */
798 poly->length = fulllength;
799
800 /* reverse and swap words in the array, leaving it right-justified */
801 while(leftidx < rightidx) {
802 /* rightidx > 0 */
803 accu = rev(poly->bitmap[--rightidx], BMP_BIT);
804 poly->bitmap[rightidx] = rev(poly->bitmap[leftidx], BMP_BIT);
805 poly->bitmap[leftidx++] = accu;
806 }
807 /* shift polynomial to left edge if required */
808 if(ofs)
809 pshift(poly, *poly, 0UL, ofs, fulllength, 0UL);
810 }
811
812 void
813 prevch(poly_t *poly, int bperhx) {
814 /* Reverse each group of bperhx bits in a polynomial.
815 * Does not clean poly.
816 */
817 unsigned long iter = 0, idx, ofs;
818 bmp_t mask, accu;
819
820 if(bperhx < 2 || bperhx > BMP_BIT)
821 return;
822 if(poly->length % bperhx)
823 praloc(poly, bperhx - (poly->length % bperhx) + poly->length);
824 mask = ~BMP_C(0) >> (BMP_BIT - bperhx);
825 for(iter = (unsigned long) (bperhx - 1); iter < poly->length; iter += bperhx) {
826 accu = getwrd(*poly, iter) & mask;
827 accu ^= rev(accu, bperhx);
828 idx = IDX(iter);
829 ofs = OFS(iter);
830 poly->bitmap[idx] ^= accu << ofs;
831 if(ofs + bperhx > (unsigned int) BMP_BIT)
832 /* (BMP_BIT - 1UL - (iter) % BMP_BIT) + bperhx > BMP_BIT
833 * (-1UL - (iter) % BMP_BIT) + bperhx > 0
834 * (- (iter % BMP_BIT)) + bperhx > 1
835 * - (iter % BMP_BIT) > 1 - bperhx
836 * iter % BMP_BIT < bperhx - 1, iter >= bperhx - 1
837 * iter >= BMP_BIT
838 * idx >= 1
839 */
840 poly->bitmap[idx-1] ^= accu >> (BMP_BIT - ofs);
841 }
842 }
843
844 void
845 prcp(poly_t *poly) {
846 /* Reciprocate a chopped polynomial. Use prev() on whole
847 * polynomials.
848 * On exit, poly is SEMI-NORMALISED.
849 */
850 unsigned long first;
851
852 praloc(poly, RNDUP(poly->length));
853 prev(poly);
854 first = pfirst(*poly);
855 if(first >= poly->length) {
856 pfree(poly);
857 return;
858 }
859 pshift(poly, *poly, 0UL, first + 1UL, poly->length, 1UL);
860 piter(poly);
861 }
862
863 void
864 pinv(poly_t *poly) {
865 /* Invert a polynomial, i.e. add 1 (modulo 2) to the coefficient of each term
866 * on exit, poly is CLEAN.
867 */
868 unsigned long idx, size = SIZE(poly->length);
869
870 for(idx = 0UL; idx<size; ++idx)
871 poly->bitmap[idx] = ~poly->bitmap[idx];
872 if(LOFS(poly->length))
873 poly->bitmap[size - 1UL] &= ~(~BMP_C(0) >> LOFS(poly->length));
874 }
875
876 poly_t
877 pmod(const poly_t dividend, const poly_t divisor) {
878 /* Divide dividend by normalised divisor and return the remainder
879 * This function generates a temporary 'chopped' divisor for pcrc()
880 * If calling repeatedly with a constant divisor, produce a chopped copy
881 * with pchop() and call pcrc() directly for higher efficiency.
882 * dividend and divisor must be CLEAN.
883 */
884
885 /* perhaps generate an error if divisor is zero */
886 poly_t subdivisor = psubs(divisor, 0UL, pfirst(divisor) + 1UL, plast(divisor), 0UL);
887 poly_t result = pcrc(dividend, subdivisor, pzero, pzero, 0);
888 pfree(&subdivisor);
889 return(result);
890 }
891
892 poly_t
893 pcrc(const poly_t message, const poly_t divisor, const poly_t init, const poly_t xorout, int flags) {
894 /* Divide message by divisor and return the remainder.
895 * init is added to divisor, highest terms aligned, before
896 * division.
897 * xorout is added to the remainder, highest terms aligned.
898 * If P_MULXN is set in flags, message is multiplied by x^n
899 * (i.e. trailing zeroes equal to the CRC width are appended)
900 * before adding init and division. Set P_MULXN for most CRC
901 * calculations.
902 * All inputs must be CLEAN.
903 * If all inputs are CLEAN, the returned poly_t will be CLEAN.
904 */
905 unsigned long max = 0UL, iter, ofs, resiter;
906 bmp_t probe, rem, dvsr, *rptr, *sptr;
907 const bmp_t *bptr, *eptr;
908 poly_t result = PZERO;
909
910 if(flags & P_MULXN)
911 max = message.length;
912 else if(message.length > divisor.length)
913 max = message.length - divisor.length;
914 bptr=message.bitmap;
915 eptr=message.bitmap+SIZE(message.length);
916 probe=~(~BMP_C(0) >> 1);
917 if(divisor.length <= (unsigned long) BMP_BIT
918 && init.length <= (unsigned long) BMP_BIT) {
919 rem = init.length ? *init.bitmap : BMP_C(0);
920 dvsr = divisor.length ? *divisor.bitmap : BMP_C(0);
921 for(iter = 0UL, ofs = 0UL; iter < max; ++iter, --ofs) {
922 if(!ofs) {
923 ofs = BMP_BIT;
924 rem ^= *bptr++;
925 }
926 if(rem & probe)
927 rem = (rem << 1) ^ dvsr;
928 else
929 rem <<= 1;
930 }
931 if(bptr < eptr)
932 /* max < message.length */
933 rem ^= *bptr >> OFS(BMP_BIT - 1UL + max);
934 if(init.length > max && init.length - max > divisor.length) {
935 palloc(&result, init.length - max);
936 *result.bitmap = rem;
937 } else if(divisor.length) {
938 palloc(&result, divisor.length);
939 *result.bitmap = rem;
940 }
941 } else {
942 /* allocate maximum size plus one word for shifted divisors and one word containing zero.
943 * This also ensures that result[1] exists
944 */
945 palloc(&result, (init.length > divisor.length ? init.length : divisor.length) + (unsigned long) (BMP_BIT << 1));
946 /*if there is content in init, there will be an extra word in result to clear it */
947 psum(&result, init, 0UL);
948 if(max)
949 *result.bitmap ^= *bptr++;
950 for(iter = 0UL, ofs = 0UL; iter < max; ++iter, probe >>= 1) {
951 if(!probe) {
952 probe = ~(~BMP_C(0) >> 1);
953 ofs = 0UL;
954 sptr = rptr = result.bitmap;
955 ++sptr;
956 /* iter < max <= message.length, so bptr is valid
957 * shift result one word to the left, splicing in a message word
958 * and clearing the last active word
959 */
960 *rptr++ = *sptr++ ^ *bptr++;
961 for(resiter = (unsigned long) (BMP_BIT << 1); resiter < result.length; resiter += BMP_BIT)
962 *rptr++ = *sptr++;
963 }
964 ++ofs;
965 if(*result.bitmap & probe)
966 psum(&result, divisor, ofs);
967 }
968 rptr = result.bitmap;
969 ++rptr;
970 while(bptr < eptr)
971 *rptr++ ^= *bptr++;
972 /* 0 <= ofs <= BMP_BIT, location of the first bit of the result */
973 pshift(&result, result, 0UL, ofs, (init.length > max + divisor.length ? init.length - max - divisor.length : 0UL) + divisor.length + ofs, 0UL);
974 }
975 psum(&result, xorout, 0UL);
976 return(result);
977 }
978
979 int
980 piter(poly_t *poly) {
981 /* Replace poly with the 'next' polynomial of equal length.
982 * Returns zero if the next polynomial is all zeroes, a nonzero
983 * value otherwise.
984 * Does not clean poly.
985 */
986 bmp_t *bptr;
987 if(!poly->length) return(0);
988
989 bptr = poly->bitmap + IDX(poly->length - 1UL);
990 *bptr += BMP_C(1) << OFS(poly->length - 1UL);
991 while(bptr != poly->bitmap && !*bptr)
992 ++(*--bptr);
993 return(*bptr != BMP_C(0));
994 }
995
996 void
997 palloc(poly_t *poly, unsigned long length) {
998 /* Replaces poly with a CLEAN object of the specified length,
999 * consisting of all zeroes.
1000 * It is safe to call with length = 0, in which case the object
1001 * is freed.
1002 * poly may or may not be WELL-FORMED.
1003 * On exit, poly is CLEAN.
1004 */
1005 unsigned long size = SIZE(length);
1006
1007 poly->length = 0UL;
1008 free(poly->bitmap);
1009 poly->bitmap = NULL;
1010 if(!length) return;
1011 if(!size)
1012 size = IDX(length) + 1UL;
1013 poly->bitmap = (bmp_t *) calloc(size, sizeof(bmp_t));
1014 if(poly->bitmap) {
1015 poly->length = length;
1016 } else
1017 uerror("cannot allocate memory for poly");
1018 }
1019
1020 void
1021 pfree(poly_t *poly) {
1022 /* Frees poly's bitmap storage and sets poly equal to the empty
1023 * polynomial (PZERO).
1024 * poly may or may not be WELL-FORMED.
1025 * On exit, poly is CLEAN.
1026 */
1027
1028 /* palloc(poly, 0UL); */
1029
1030 poly->length = 0UL;
1031 free(poly->bitmap);
1032 poly->bitmap = NULL;
1033 }
1034
1035 void
1036 praloc(poly_t *poly, unsigned long length) {
1037 /* Trims or extends poly to length at the right edge, appending
1038 * zeroes if necessary.
1039 * On entry, poly may or may not be WELL-FORMED.
1040 * On exit, poly is CLEAN.
1041 */
1042 unsigned long oldsize, size = SIZE(length);
1043 if(!poly) return;
1044 if(!length) {
1045 poly->length = 0UL;
1046 free(poly->bitmap);
1047 poly->bitmap = NULL;
1048 return;
1049 }
1050 if(!size)
1051 size = IDX(length) + 1UL;
1052 if(!poly->bitmap)
1053 poly->length = 0UL;
1054 oldsize = SIZE(poly->length);
1055 if(oldsize != size)
1056 /* reallocate if array pointer is null or array resized */
1057 poly->bitmap = (bmp_t *) realloc((void *)poly->bitmap, size * sizeof(bmp_t));
1058 if(poly->bitmap) {
1059 if(poly->length < length) {
1060 /* poly->length >= 0, length > 0, size > 0.
1061 * poly expanded. clear old last word and all new words
1062 */
1063 if(LOFS(poly->length))
1064 poly->bitmap[oldsize - 1UL] &= ~(~BMP_C(0) >> LOFS(poly->length));
1065 while(oldsize < size)
1066 poly->bitmap[oldsize++] = BMP_C(0);
1067 } else if(LOFS(length))
1068 /* poly->length >= length > 0.
1069 * poly shrunk. clear new last word
1070 */
1071 poly->bitmap[size - 1UL] &= ~(~BMP_C(0) >> LOFS(length));
1072 poly->length = length;
1073 } else
1074 uerror("cannot reallocate memory for poly");
1075 }
1076
1077 int
1078 pmpar(const poly_t poly, const poly_t mask) {
1079 /* Return even parity of poly masked with mask.
1080 * Poly and mask must be CLEAN.
1081 */
1082 bmp_t res = BMP_C(0);
1083 int i = BMP_SUB;
1084 const bmp_t *pptr = poly.bitmap, *mptr = mask.bitmap;
1085 const bmp_t *const pend = poly.bitmap + SIZE(poly.length);
1086 const bmp_t *const mend = mask.bitmap + SIZE(mask.length);
1087
1088 while(pptr < pend && mptr < mend)
1089 res ^= *pptr++ & *mptr++;
1090 do
1091 res ^= res >> i;
1092 while(i >>= 1);
1093
1094 return((int) (res & BMP_C(1)));
1095 }
1096
1097 int
1098 pident(const poly_t a, const poly_t b) {
1099 /* Return nonzero if a and b have the same length
1100 * and point to the same bitmap.
1101 * a and b need not be CLEAN.
1102 */
1103 return(a.length == b.length && a.bitmap == b.bitmap);
1104 }
1105
1106 /* Private functions */
1107
1108 static bmp_t
1109 getwrd(const poly_t poly, unsigned long iter) {
1110 /* Fetch unaligned word from poly where LSB of result is
1111 * bit iter of the bitmap (counting from zero). If iter exceeds
1112 * the length of poly then zeroes are appended as necessary.
1113 * Factored from ptostr().
1114 * poly must be CLEAN.
1115 */
1116 bmp_t accu = BMP_C(0);
1117 unsigned long idx, size;
1118 int ofs;
1119
1120 idx = IDX(iter);
1121 ofs = OFS(iter);
1122 size = SIZE(poly.length);
1123
1124 if(idx < size)
1125 accu |= poly.bitmap[idx] >> ofs;
1126 if(idx && idx <= size && ofs > 0)
1127 accu |= poly.bitmap[idx - 1UL] << (BMP_BIT - ofs);
1128 return(accu);
1129 }
1130
1131 static bmp_t
1132 rev(bmp_t accu, int bits) {
1133 /* Returns the bitmap word argument with the given number of
1134 * least significant bits reversed and the rest cleared.
1135 */
1136 static const unsigned char revtab[256] = {
1137 0x00,0x80,0x40,0xc0,0x20,0xa0,0x60,0xe0,
1138 0x10,0x90,0x50,0xd0,0x30,0xb0,0x70,0xf0,
1139 0x08,0x88,0x48,0xc8,0x28,0xa8,0x68,0xe8,
1140 0x18,0x98,0x58,0xd8,0x38,0xb8,0x78,0xf8,
1141 0x04,0x84,0x44,0xc4,0x24,0xa4,0x64,0xe4,
1142 0x14,0x94,0x54,0xd4,0x34,0xb4,0x74,0xf4,
1143 0x0c,0x8c,0x4c,0xcc,0x2c,0xac,0x6c,0xec,
1144 0x1c,0x9c,0x5c,0xdc,0x3c,0xbc,0x7c,0xfc,
1145 0x02,0x82,0x42,0xc2,0x22,0xa2,0x62,0xe2,
1146 0x12,0x92,0x52,0xd2,0x32,0xb2,0x72,0xf2,
1147 0x0a,0x8a,0x4a,0xca,0x2a,0xaa,0x6a,0xea,
1148 0x1a,0x9a,0x5a,0xda,0x3a,0xba,0x7a,0xfa,
1149 0x06,0x86,0x46,0xc6,0x26,0xa6,0x66,0xe6,
1150 0x16,0x96,0x56,0xd6,0x36,0xb6,0x76,0xf6,
1151 0x0e,0x8e,0x4e,0xce,0x2e,0xae,0x6e,0xee,
1152 0x1e,0x9e,0x5e,0xde,0x3e,0xbe,0x7e,0xfe,
1153 0x01,0x81,0x41,0xc1,0x21,0xa1,0x61,0xe1,
1154 0x11,0x91,0x51,0xd1,0x31,0xb1,0x71,0xf1,
1155 0x09,0x89,0x49,0xc9,0x29,0xa9,0x69,0xe9,
1156 0x19,0x99,0x59,0xd9,0x39,0xb9,0x79,0xf9,
1157 0x05,0x85,0x45,0xc5,0x25,0xa5,0x65,0xe5,
1158 0x15,0x95,0x55,0xd5,0x35,0xb5,0x75,0xf5,
1159 0x0d,0x8d,0x4d,0xcd,0x2d,0xad,0x6d,0xed,
1160 0x1d,0x9d,0x5d,0xdd,0x3d,0xbd,0x7d,0xfd,
1161 0x03,0x83,0x43,0xc3,0x23,0xa3,0x63,0xe3,
1162 0x13,0x93,0x53,0xd3,0x33,0xb3,0x73,0xf3,
1163 0x0b,0x8b,0x4b,0xcb,0x2b,0xab,0x6b,0xeb,
1164 0x1b,0x9b,0x5b,0xdb,0x3b,0xbb,0x7b,0xfb,
1165 0x07,0x87,0x47,0xc7,0x27,0xa7,0x67,0xe7,
1166 0x17,0x97,0x57,0xd7,0x37,0xb7,0x77,0xf7,
1167 0x0f,0x8f,0x4f,0xcf,0x2f,0xaf,0x6f,0xef,
1168 0x1f,0x9f,0x5f,0xdf,0x3f,0xbf,0x7f,0xff
1169 };
1170 bmp_t result = BMP_C(0);
1171 while(bits > 8) {
1172 bits -= 8;
1173 result = result << 8 | revtab[accu & 0xff];
1174 accu >>= 8;
1175 }
1176 result = result << bits | (bmp_t) (revtab[accu & 0xff] >> (8 - bits));
1177 return(result);
1178 }
1179
1180 static void
1181 prhex(char **spp, bmp_t bits, int flags, int bperhx) {
1182 /* Appends a hexadecimal string representing the bperhx least
1183 * significant bits of bits to an external string.
1184 * spp points to a character pointer that in turn points to the
1185 * end of a hex string being built. prhex() advances this
1186 * second pointer by the number of characters written.
1187 * The unused MSBs of bits MUST be cleared.
1188 * Set P_UPPER in flags to write A-F in uppercase.
1189 */
1190 static const char hex[] = "0123456789abcdef0123456789ABCDEF";
1191 const int upper = (flags & P_UPPER ? 0x10 : 0);
1192 while(bperhx > 0) {
1193 bperhx -= ((bperhx + 3) & 3) + 1;
1194 *(*spp)++ = hex[(bits >> bperhx & BMP_C(0xf)) | upper];
1195 }
1196 }
Impressum, Datenschutz