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