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