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