]> git.zerfleddert.de Git - proxmark3-svn/blob - client/reveng/poly.c
CHG: some desfire changes from @bforbort fork. *untested*
[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 = ~(~0 << 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 = ~(~0 << 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 /* claim remaining bits of last word (as we use public function pshift()) */
797 poly->length = fulllength;
798
799 /* reverse and swap words in the array, leaving it right-justified */
800 while(leftidx < rightidx) {
801 /* rightidx > 0 */
802 accu = rev(poly->bitmap[--rightidx], BMP_BIT);
803 poly->bitmap[rightidx] = rev(poly->bitmap[leftidx], BMP_BIT);
804 poly->bitmap[leftidx++] = accu;
805 }
806 /* shift polynomial to left edge if required */
807 if(ofs)
808 pshift(poly, *poly, 0UL, ofs, fulllength, 0UL);
809 }
810
811 void
812 prevch(poly_t *poly, int bperhx) {
813 /* Reverse each group of bperhx bits in a polynomial.
814 * Does not clean poly.
815 */
816 unsigned long iter = 0, idx, ofs;
817 bmp_t mask, accu;
818
819 if(bperhx < 2 || bperhx > BMP_BIT)
820 return;
821 if(poly->length % bperhx)
822 praloc(poly, bperhx - (poly->length % bperhx) + poly->length);
823 mask = ~BMP_C(0) >> (BMP_BIT - bperhx);
824 for(iter = (unsigned long) (bperhx - 1); iter < poly->length; iter += bperhx) {
825 accu = getwrd(*poly, iter) & mask;
826 accu ^= rev(accu, bperhx);
827 idx = IDX(iter);
828 ofs = OFS(iter);
829 poly->bitmap[idx] ^= accu << ofs;
830 if(ofs + bperhx > (unsigned int) BMP_BIT)
831 /* (BMP_BIT - 1UL - (iter) % BMP_BIT) + bperhx > BMP_BIT
832 * (-1UL - (iter) % BMP_BIT) + bperhx > 0
833 * (- (iter % BMP_BIT)) + bperhx > 1
834 * - (iter % BMP_BIT) > 1 - bperhx
835 * iter % BMP_BIT < bperhx - 1, iter >= bperhx - 1
836 * iter >= BMP_BIT
837 * idx >= 1
838 */
839 poly->bitmap[idx-1] ^= accu >> (BMP_BIT - ofs);
840 }
841 }
842
843 void
844 prcp(poly_t *poly) {
845 /* Reciprocate a chopped polynomial. Use prev() on whole
846 * polynomials.
847 * On exit, poly is SEMI-NORMALISED.
848 */
849 unsigned long first;
850
851 praloc(poly, RNDUP(poly->length));
852 prev(poly);
853 first = pfirst(*poly);
854 if(first >= poly->length) {
855 pfree(poly);
856 return;
857 }
858 pshift(poly, *poly, 0UL, first + 1UL, poly->length, 1UL);
859 piter(poly);
860 }
861
862 void
863 pinv(poly_t *poly) {
864 /* Invert a polynomial, i.e. add 1 (modulo 2) to the coefficient of each term
865 * on exit, poly is CLEAN.
866 */
867 unsigned long idx, size = SIZE(poly->length);
868
869 for(idx = 0UL; idx<size; ++idx)
870 poly->bitmap[idx] = ~poly->bitmap[idx];
871 if(LOFS(poly->length))
872 poly->bitmap[size - 1UL] &= ~(~BMP_C(0) >> LOFS(poly->length));
873 }
874
875 poly_t
876 pmod(const poly_t dividend, const poly_t divisor) {
877 /* Divide dividend by normalised divisor and return the remainder
878 * This function generates a temporary 'chopped' divisor for pcrc()
879 * If calling repeatedly with a constant divisor, produce a chopped copy
880 * with pchop() and call pcrc() directly for higher efficiency.
881 * dividend and divisor must be CLEAN.
882 */
883
884 /* perhaps generate an error if divisor is zero */
885 poly_t subdivisor = psubs(divisor, 0UL, pfirst(divisor) + 1UL, plast(divisor), 0UL);
886 poly_t result = pcrc(dividend, subdivisor, pzero, pzero, 0);
887 pfree(&subdivisor);
888 return(result);
889 }
890
891 poly_t
892 pcrc(const poly_t message, const poly_t divisor, const poly_t init, const poly_t xorout, int flags) {
893 /* Divide message by divisor and return the remainder.
894 * init is added to divisor, highest terms aligned, before
895 * division.
896 * xorout is added to the remainder, highest terms aligned.
897 * If P_MULXN is set in flags, message is multiplied by x^n
898 * (i.e. trailing zeroes equal to the CRC width are appended)
899 * before adding init and division. Set P_MULXN for most CRC
900 * calculations.
901 * All inputs must be CLEAN.
902 * If all inputs are CLEAN, the returned poly_t will be CLEAN.
903 */
904 unsigned long max = 0UL, iter, ofs, resiter;
905 bmp_t probe, rem, dvsr, *rptr, *sptr;
906 const bmp_t *bptr, *eptr;
907 poly_t result = PZERO;
908
909 if(flags & P_MULXN)
910 max = message.length;
911 else if(message.length > divisor.length)
912 max = message.length - divisor.length;
913 bptr=message.bitmap;
914 eptr=message.bitmap+SIZE(message.length);
915 probe=~(~BMP_C(0) >> 1);
916 if(divisor.length <= (unsigned long) BMP_BIT
917 && init.length <= (unsigned long) BMP_BIT) {
918 rem = init.length ? *init.bitmap : BMP_C(0);
919 dvsr = divisor.length ? *divisor.bitmap : BMP_C(0);
920 for(iter = 0UL, ofs = 0UL; iter < max; ++iter, --ofs) {
921 if(!ofs) {
922 ofs = BMP_BIT;
923 rem ^= *bptr++;
924 }
925 if(rem & probe)
926 rem = (rem << 1) ^ dvsr;
927 else
928 rem <<= 1;
929 }
930 if(bptr < eptr)
931 /* max < message.length */
932 rem ^= *bptr >> OFS(BMP_BIT - 1UL + max);
933 if(init.length > max && init.length - max > divisor.length) {
934 palloc(&result, init.length - max);
935 *result.bitmap = rem;
936 } else if(divisor.length) {
937 palloc(&result, divisor.length);
938 *result.bitmap = rem;
939 }
940 } else {
941 /* allocate maximum size plus one word for shifted divisors and one word containing zero.
942 * This also ensures that result[1] exists
943 */
944 palloc(&result, (init.length > divisor.length ? init.length : divisor.length) + (unsigned long) (BMP_BIT << 1));
945 /*if there is content in init, there will be an extra word in result to clear it */
946 psum(&result, init, 0UL);
947 if(max)
948 *result.bitmap ^= *bptr++;
949 for(iter = 0UL, ofs = 0UL; iter < max; ++iter, probe >>= 1) {
950 if(!probe) {
951 probe = ~(~BMP_C(0) >> 1);
952 ofs = 0UL;
953 sptr = rptr = result.bitmap;
954 ++sptr;
955 /* iter < max <= message.length, so bptr is valid
956 * shift result one word to the left, splicing in a message word
957 * and clearing the last active word
958 */
959 *rptr++ = *sptr++ ^ *bptr++;
960 for(resiter = (unsigned long) (BMP_BIT << 1); resiter < result.length; resiter += BMP_BIT)
961 *rptr++ = *sptr++;
962 }
963 ++ofs;
964 if(*result.bitmap & probe)
965 psum(&result, divisor, ofs);
966 }
967 rptr = result.bitmap;
968 ++rptr;
969 while(bptr < eptr)
970 *rptr++ ^= *bptr++;
971 /* 0 <= ofs <= BMP_BIT, location of the first bit of the result */
972 pshift(&result, result, 0UL, ofs, (init.length > max + divisor.length ? init.length - max - divisor.length : 0UL) + divisor.length + ofs, 0UL);
973 }
974 psum(&result, xorout, 0UL);
975 return(result);
976 }
977
978 int
979 piter(poly_t *poly) {
980 /* Replace poly with the 'next' polynomial of equal length.
981 * Returns zero if the next polynomial is all zeroes, a nonzero
982 * value otherwise.
983 * Does not clean poly.
984 */
985 bmp_t *bptr;
986 if(!poly->length) return(0);
987
988 bptr = poly->bitmap + IDX(poly->length - 1UL);
989 *bptr += BMP_C(1) << OFS(poly->length - 1UL);
990 while(bptr != poly->bitmap && !*bptr)
991 ++(*--bptr);
992 return(*bptr != BMP_C(0));
993 }
994
995 void
996 palloc(poly_t *poly, unsigned long length) {
997 /* Replaces poly with a CLEAN object of the specified length,
998 * consisting of all zeroes.
999 * It is safe to call with length = 0, in which case the object
1000 * is freed.
1001 * poly may or may not be WELL-FORMED.
1002 * On exit, poly is CLEAN.
1003 */
1004 unsigned long size = SIZE(length);
1005
1006 poly->length = 0UL;
1007 free(poly->bitmap);
1008 poly->bitmap = NULL;
1009 if(!length) return;
1010 if(!size)
1011 size = IDX(length) + 1UL;
1012 poly->bitmap = (bmp_t *) calloc(size, sizeof(bmp_t));
1013 if(poly->bitmap) {
1014 poly->length = length;
1015 } else
1016 uerror("cannot allocate memory for poly");
1017 }
1018
1019 void
1020 pfree(poly_t *poly) {
1021 /* Frees poly's bitmap storage and sets poly equal to the empty
1022 * polynomial (PZERO).
1023 * poly may or may not be WELL-FORMED.
1024 * On exit, poly is CLEAN.
1025 */
1026
1027 /* palloc(poly, 0UL); */
1028
1029 poly->length = 0UL;
1030 free(poly->bitmap);
1031 poly->bitmap = NULL;
1032 }
1033
1034 void
1035 praloc(poly_t *poly, unsigned long length) {
1036 /* Trims or extends poly to length at the right edge, appending
1037 * zeroes if necessary.
1038 * On entry, poly may or may not be WELL-FORMED.
1039 * On exit, poly is CLEAN.
1040 */
1041 unsigned long oldsize, size = SIZE(length);
1042 if(!poly) return;
1043 if(!length) {
1044 poly->length = 0UL;
1045 free(poly->bitmap);
1046 poly->bitmap = NULL;
1047 return;
1048 }
1049 if(!size)
1050 size = IDX(length) + 1UL;
1051 if(!poly->bitmap)
1052 poly->length = 0UL;
1053 oldsize = SIZE(poly->length);
1054 if(oldsize != size)
1055 /* reallocate if array pointer is null or array resized */
1056 poly->bitmap = (bmp_t *) realloc((void *)poly->bitmap, size * sizeof(bmp_t));
1057 if(poly->bitmap) {
1058 if(poly->length < length) {
1059 /* poly->length >= 0, length > 0, size > 0.
1060 * poly expanded. clear old last word and all new words
1061 */
1062 if(LOFS(poly->length))
1063 poly->bitmap[oldsize - 1UL] &= ~(~BMP_C(0) >> LOFS(poly->length));
1064 while(oldsize < size)
1065 poly->bitmap[oldsize++] = BMP_C(0);
1066 } else if(LOFS(length))
1067 /* poly->length >= length > 0.
1068 * poly shrunk. clear new last word
1069 */
1070 poly->bitmap[size - 1UL] &= ~(~BMP_C(0) >> LOFS(length));
1071 poly->length = length;
1072 } else
1073 uerror("cannot reallocate memory for poly");
1074 }
1075
1076 int
1077 pmpar(const poly_t poly, const poly_t mask) {
1078 /* Return even parity of poly masked with mask.
1079 * Poly and mask must be CLEAN.
1080 */
1081 bmp_t res = BMP_C(0);
1082 int i = BMP_SUB;
1083 const bmp_t *pptr = poly.bitmap, *mptr = mask.bitmap;
1084 const bmp_t *const pend = poly.bitmap + SIZE(poly.length);
1085 const bmp_t *const mend = mask.bitmap + SIZE(mask.length);
1086
1087 while(pptr < pend && mptr < mend)
1088 res ^= *pptr++ & *mptr++;
1089 do
1090 res ^= res >> i;
1091 while(i >>= 1);
1092
1093 return((int) (res & BMP_C(1)));
1094 }
1095
1096 int
1097 pident(const poly_t a, const poly_t b) {
1098 /* Return nonzero if a and b have the same length
1099 * and point to the same bitmap.
1100 * a and b need not be CLEAN.
1101 */
1102 return(a.length == b.length && a.bitmap == b.bitmap);
1103 }
1104
1105 /* Private functions */
1106
1107 static bmp_t
1108 getwrd(const poly_t poly, unsigned long iter) {
1109 /* Fetch unaligned word from poly where LSB of result is
1110 * bit iter of the bitmap (counting from zero). If iter exceeds
1111 * the length of poly then zeroes are appended as necessary.
1112 * Factored from ptostr().
1113 * poly must be CLEAN.
1114 */
1115 bmp_t accu = BMP_C(0);
1116 unsigned long idx, size;
1117 int ofs;
1118
1119 idx = IDX(iter);
1120 ofs = OFS(iter);
1121 size = SIZE(poly.length);
1122
1123 if(idx < size)
1124 accu |= poly.bitmap[idx] >> ofs;
1125 if(idx && idx <= size && ofs > 0)
1126 accu |= poly.bitmap[idx - 1UL] << (BMP_BIT - ofs);
1127 return(accu);
1128 }
1129
1130 static bmp_t
1131 rev(bmp_t accu, int bits) {
1132 /* Returns the bitmap word argument with the given number of
1133 * least significant bits reversed and the rest cleared.
1134 */
1135 static const unsigned char revtab[256] = {
1136 0x00,0x80,0x40,0xc0,0x20,0xa0,0x60,0xe0,
1137 0x10,0x90,0x50,0xd0,0x30,0xb0,0x70,0xf0,
1138 0x08,0x88,0x48,0xc8,0x28,0xa8,0x68,0xe8,
1139 0x18,0x98,0x58,0xd8,0x38,0xb8,0x78,0xf8,
1140 0x04,0x84,0x44,0xc4,0x24,0xa4,0x64,0xe4,
1141 0x14,0x94,0x54,0xd4,0x34,0xb4,0x74,0xf4,
1142 0x0c,0x8c,0x4c,0xcc,0x2c,0xac,0x6c,0xec,
1143 0x1c,0x9c,0x5c,0xdc,0x3c,0xbc,0x7c,0xfc,
1144 0x02,0x82,0x42,0xc2,0x22,0xa2,0x62,0xe2,
1145 0x12,0x92,0x52,0xd2,0x32,0xb2,0x72,0xf2,
1146 0x0a,0x8a,0x4a,0xca,0x2a,0xaa,0x6a,0xea,
1147 0x1a,0x9a,0x5a,0xda,0x3a,0xba,0x7a,0xfa,
1148 0x06,0x86,0x46,0xc6,0x26,0xa6,0x66,0xe6,
1149 0x16,0x96,0x56,0xd6,0x36,0xb6,0x76,0xf6,
1150 0x0e,0x8e,0x4e,0xce,0x2e,0xae,0x6e,0xee,
1151 0x1e,0x9e,0x5e,0xde,0x3e,0xbe,0x7e,0xfe,
1152 0x01,0x81,0x41,0xc1,0x21,0xa1,0x61,0xe1,
1153 0x11,0x91,0x51,0xd1,0x31,0xb1,0x71,0xf1,
1154 0x09,0x89,0x49,0xc9,0x29,0xa9,0x69,0xe9,
1155 0x19,0x99,0x59,0xd9,0x39,0xb9,0x79,0xf9,
1156 0x05,0x85,0x45,0xc5,0x25,0xa5,0x65,0xe5,
1157 0x15,0x95,0x55,0xd5,0x35,0xb5,0x75,0xf5,
1158 0x0d,0x8d,0x4d,0xcd,0x2d,0xad,0x6d,0xed,
1159 0x1d,0x9d,0x5d,0xdd,0x3d,0xbd,0x7d,0xfd,
1160 0x03,0x83,0x43,0xc3,0x23,0xa3,0x63,0xe3,
1161 0x13,0x93,0x53,0xd3,0x33,0xb3,0x73,0xf3,
1162 0x0b,0x8b,0x4b,0xcb,0x2b,0xab,0x6b,0xeb,
1163 0x1b,0x9b,0x5b,0xdb,0x3b,0xbb,0x7b,0xfb,
1164 0x07,0x87,0x47,0xc7,0x27,0xa7,0x67,0xe7,
1165 0x17,0x97,0x57,0xd7,0x37,0xb7,0x77,0xf7,
1166 0x0f,0x8f,0x4f,0xcf,0x2f,0xaf,0x6f,0xef,
1167 0x1f,0x9f,0x5f,0xdf,0x3f,0xbf,0x7f,0xff
1168 };
1169 bmp_t result = BMP_C(0);
1170 while(bits > 8) {
1171 bits -= 8;
1172 result = result << 8 | revtab[accu & 0xff];
1173 accu >>= 8;
1174 }
1175 result = result << bits | (bmp_t) (revtab[accu & 0xff] >> (8 - bits));
1176 return(result);
1177 }
1178
1179 static void
1180 prhex(char **spp, bmp_t bits, int flags, int bperhx) {
1181 /* Appends a hexadecimal string representing the bperhx least
1182 * significant bits of bits to an external string.
1183 * spp points to a character pointer that in turn points to the
1184 * end of a hex string being built. prhex() advances this
1185 * second pointer by the number of characters written.
1186 * The unused MSBs of bits MUST be cleared.
1187 * Set P_UPPER in flags to write A-F in uppercase.
1188 */
1189 static const char hex[] = "0123456789abcdef0123456789ABCDEF";
1190 const int upper = (flags & P_UPPER ? 0x10 : 0);
1191 while(bperhx > 0) {
1192 bperhx -= ((bperhx + 3) & 3) + 1;
1193 *(*spp)++ = hex[(bits >> bperhx & BMP_C(0xf)) | upper];
1194 }
1195 }
Impressum, Datenschutz