1 /*
2 * GF-Complete: A Comprehensive Open Source Library for Galois Field Arithmetic
3 * James S. Plank, Ethan L. Miller, Kevin M. Greenan,
4 * Benjamin A. Arnold, John A. Burnum, Adam W. Disney, Allen C. McBride.
5 *
6 * gf_wgen.c
7 *
8 * Routines for Galois fields for general w < 32. For specific w,
9 like 4, 8, 16, 32, 64 and 128, see the other files.
10 */
11
12 #include "gf_int.h"
13 #include <stdio.h>
14 #include <stdlib.h>
15
16 struct gf_wgen_table_w8_data {
17 uint8_t *mult;
18 uint8_t *div;
19 uint8_t base;
20 };
21
22 struct gf_wgen_table_w16_data {
23 uint16_t *mult;
24 uint16_t *div;
25 uint16_t base;
26 };
27
28 struct gf_wgen_log_w8_data {
29 uint8_t *log;
30 uint8_t *anti;
31 uint8_t *danti;
32 uint8_t base;
33 };
34
35 struct gf_wgen_log_w16_data {
36 uint16_t *log;
37 uint16_t *anti;
38 uint16_t *danti;
39 uint16_t base;
40 };
41
42 struct gf_wgen_log_w32_data {
43 uint32_t *log;
44 uint32_t *anti;
45 uint32_t *danti;
46 uint32_t base;
47 };
48
49 struct gf_wgen_group_data {
50 uint32_t *reduce;
51 uint32_t *shift;
52 uint32_t mask;
53 uint64_t rmask;
54 int tshift;
55 uint32_t memory;
56 };
57
58 static
59 inline
60 gf_val_32_t gf_wgen_inverse_from_divide (gf_t *gf, gf_val_32_t a)
61 {
62 return gf->divide.w32(gf, 1, a);
63 }
64
65 static
66 inline
67 gf_val_32_t gf_wgen_divide_from_inverse (gf_t *gf, gf_val_32_t a, gf_val_32_t b)
68 {
69 b = gf->inverse.w32(gf, b);
70 return gf->multiply.w32(gf, a, b);
71 }
72
73 static
74 inline
75 gf_val_32_t gf_wgen_euclid (gf_t *gf, gf_val_32_t b)
76 {
77
78 gf_val_32_t e_i, e_im1, e_ip1;
79 gf_val_32_t d_i, d_im1, d_ip1;
80 gf_val_32_t y_i, y_im1, y_ip1;
81 gf_val_32_t c_i;
82
83 if (b == 0) return -1;
84 e_im1 = ((gf_internal_t *) (gf->scratch))->prim_poly;
85 e_i = b;
86 d_im1 = ((gf_internal_t *) (gf->scratch))->w;
87 for (d_i = d_im1; ((1 << d_i) & e_i) == 0; d_i--) ;
88 y_i = 1;
89 y_im1 = 0;
90
91 while (e_i != 1) {
92
93 e_ip1 = e_im1;
94 d_ip1 = d_im1;
95 c_i = 0;
96
97 while (d_ip1 >= d_i) {
98 c_i ^= (1 << (d_ip1 - d_i));
99 e_ip1 ^= (e_i << (d_ip1 - d_i));
100 if (e_ip1 == 0) return 0;
101 while ((e_ip1 & (1 << d_ip1)) == 0) d_ip1--;
102 }
103
104 y_ip1 = y_im1 ^ gf->multiply.w32(gf, c_i, y_i);
105 y_im1 = y_i;
106 y_i = y_ip1;
107
108 e_im1 = e_i;
109 d_im1 = d_i;
110 e_i = e_ip1;
111 d_i = d_ip1;
112 }
113
114 return y_i;
115 }
116
117 gf_val_32_t gf_wgen_extract_word(gf_t *gf, void *start, int bytes, int index)
118 {
119 uint8_t *ptr;
120 uint32_t rv;
121 int rs;
122 int byte, bit, i;
123 gf_internal_t *h;
124
125 h = (gf_internal_t *) gf->scratch;
126 rs = bytes / h->w;
127 byte = index/8;
128 bit = index%8;
129
130 ptr = (uint8_t *) start;
131 ptr += bytes;
132 ptr -= rs;
133 ptr += byte;
134
135 rv = 0;
136 for (i = 0; i < h->w; i++) {
137 rv <<= 1;
138 if ((*ptr) & (1 << bit)) rv |= 1;
139 ptr -= rs;
140 }
141
142 return rv;
143 }
144
145 static
146 inline
147 gf_val_32_t gf_wgen_matrix (gf_t *gf, gf_val_32_t b)
148 {
149 return gf_bitmatrix_inverse(b, ((gf_internal_t *) (gf->scratch))->w,
150 ((gf_internal_t *) (gf->scratch))->prim_poly);
151 }
152
153 static
154 inline
155 uint32_t
156 gf_wgen_shift_multiply (gf_t *gf, uint32_t a32, uint32_t b32)
157 {
158 uint64_t product, i, pp, a, b, one;
159 gf_internal_t *h;
160
161 a = a32;
162 b = b32;
163 h = (gf_internal_t *) gf->scratch;
164 one = 1;
165 pp = h->prim_poly | (one << h->w);
166
167 product = 0;
168
169 for (i = 0; i < (uint64_t)h->w; i++) {
170 if (a & (one << i)) product ^= (b << i);
171 }
172 for (i = h->w*2-1; i >= (uint64_t)h->w; i--) {
173 if (product & (one << i)) product ^= (pp << (i-h->w));
174 }
175 return product;
176 }
177
178 static
179 int gf_wgen_shift_init(gf_t *gf)
180 {
181 SET_FUNCTION(gf,multiply,w32,gf_wgen_shift_multiply)
182 SET_FUNCTION(gf,inverse,w32,gf_wgen_euclid)
183 return 1;
184 }
185
186 static
187 gf_val_32_t
188 gf_wgen_bytwo_b_multiply (gf_t *gf, gf_val_32_t a, gf_val_32_t b)
189 {
190 uint32_t prod, pp, bmask;
191 gf_internal_t *h;
192
193 h = (gf_internal_t *) gf->scratch;
194 pp = h->prim_poly;
195
196 prod = 0;
197 bmask = (1 << (h->w-1));
198
199 while (1) {
200 if (a & 1) prod ^= b;
201 a >>= 1;
202 if (a == 0) return prod;
203 if (b & bmask) {
204 b = ((b << 1) ^ pp);
205 } else {
206 b <<= 1;
207 }
208 }
209 }
210
211 static
212 int gf_wgen_bytwo_b_init(gf_t *gf)
213 {
214 SET_FUNCTION(gf,multiply,w32,gf_wgen_bytwo_b_multiply)
215 SET_FUNCTION(gf,inverse,w32,gf_wgen_euclid)
216 return 1;
217 }
218
219 static
220 inline
221 gf_val_32_t
222 gf_wgen_bytwo_p_multiply (gf_t *gf, gf_val_32_t a, gf_val_32_t b)
223 {
224 uint32_t prod, pp, pmask, amask;
225 gf_internal_t *h;
226
227 h = (gf_internal_t *) gf->scratch;
228 pp = h->prim_poly;
229
230 prod = 0;
231 pmask = (1 << ((h->w)-1)); /*Ben: Had an operator precedence warning here*/
232 amask = pmask;
233
234 while (amask != 0) {
235 if (prod & pmask) {
236 prod = ((prod << 1) ^ pp);
237 } else {
238 prod <<= 1;
239 }
240 if (a & amask) prod ^= b;
241 amask >>= 1;
242 }
243 return prod;
244 }
245
246
247 static
248 int gf_wgen_bytwo_p_init(gf_t *gf)
249 {
250 SET_FUNCTION(gf,multiply,w32,gf_wgen_bytwo_p_multiply)
251 SET_FUNCTION(gf,inverse,w32,gf_wgen_euclid)
252 return 1;
253 }
254
255 static
256 void
257 gf_wgen_group_set_shift_tables(uint32_t *shift, uint32_t val, gf_internal_t *h)
258 {
259 uint32_t i;
260 uint32_t j;
261 int g_s;
262
263 if (h->mult_type == GF_MULT_DEFAULT) {
264 g_s = 2;
265 } else {
266 g_s = h->arg1;
267 }
268
269 shift[0] = 0;
270
271 for (i = 1; i < ((uint32_t)1 << g_s); i <<= 1) {
272 for (j = 0; j < i; j++) shift[i|j] = shift[j]^val;
273 if (val & (1 << (h->w-1))) {
274 val <<= 1;
275 val ^= h->prim_poly;
276 } else {
277 val <<= 1;
278 }
279 }
280 }
281
282 static
283 inline
284 gf_val_32_t
285 gf_wgen_group_s_equals_r_multiply(gf_t *gf, gf_val_32_t a, gf_val_32_t b)
286 {
287 int leftover, rs;
288 uint32_t p, l, ind, a32;
289 int bits_left;
290 int g_s;
291 int w;
292
293 struct gf_wgen_group_data *gd;
294 gf_internal_t *h = (gf_internal_t *) gf->scratch;
295 g_s = h->arg1;
296 w = h->w;
297
298 gd = (struct gf_wgen_group_data *) h->private;
299 gf_wgen_group_set_shift_tables(gd->shift, b, h);
300
301 leftover = w % g_s;
302 if (leftover == 0) leftover = g_s;
303
304 rs = w - leftover;
305 a32 = a;
306 ind = a32 >> rs;
307 a32 <<= leftover;
308 a32 &= gd->mask;
309 p = gd->shift[ind];
310
311 bits_left = rs;
312 rs = w - g_s;
313
314 while (bits_left > 0) {
315 bits_left -= g_s;
316 ind = a32 >> rs;
317 a32 <<= g_s;
318 a32 &= gd->mask;
319 l = p >> rs;
320 p = (gd->shift[ind] ^ gd->reduce[l] ^ (p << g_s)) & gd->mask;
321 }
322 return p;
323 }
324
325 char *bits(uint32_t v)
326 {
327 char *rv;
328 int i, j;
329
330 rv = malloc(30);
331 j = 0;
332 for (i = 27; i >= 0; i--) {
333 rv[j] = '0' + ((v & (1 << i)) ? 1 : 0);
334 j++;
335 }
336 rv[j] = '\0';
337 return rv;
338 }
339 char *bits_56(uint64_t v)
340 {
341 char *rv;
342 int i, j;
343 uint64_t one;
344
345 one = 1;
346
347 rv = malloc(60);
348 j = 0;
349 for (i = 55; i >= 0; i--) {
350 rv[j] = '0' + ((v & (one << i)) ? 1 : 0);
351 j++;
352 }
353 rv[j] = '\0';
354 return rv;
355 }
356
357 static
358 inline
359 gf_val_32_t
360 gf_wgen_group_multiply(gf_t *gf, gf_val_32_t a, gf_val_32_t b)
361 {
362 int i;
363 int leftover;
364 uint64_t p, l, r;
365 uint32_t a32, ind;
366 int g_s, g_r;
367 struct gf_wgen_group_data *gd;
368 int w;
369
370 gf_internal_t *h = (gf_internal_t *) gf->scratch;
371 if (h->mult_type == GF_MULT_DEFAULT) {
372 g_s = 2;
373 g_r = 8;
374 } else {
375 g_s = h->arg1;
376 g_r = h->arg2;
377 }
378 w = h->w;
379 gd = (struct gf_wgen_group_data *) h->private;
380 gf_wgen_group_set_shift_tables(gd->shift, b, h);
381
382 leftover = w % g_s;
383 if (leftover == 0) leftover = g_s;
384
385 a32 = a;
386 ind = a32 >> (w - leftover);
387 p = gd->shift[ind];
388 p <<= g_s;
389 a32 <<= leftover;
390 a32 &= gd->mask;
391
392 i = (w - leftover);
393 while (i > g_s) {
394 ind = a32 >> (w-g_s);
395 p ^= gd->shift[ind];
396 a32 <<= g_s;
397 a32 &= gd->mask;
398 p <<= g_s;
399 i -= g_s;
400 }
401
402 ind = a32 >> (h->w-g_s);
403 p ^= gd->shift[ind];
404
405 for (i = gd->tshift ; i >= 0; i -= g_r) {
406 l = p & (gd->rmask << i);
407 r = gd->reduce[l >> (i+w)];
408 r <<= (i);
409 p ^= r;
410 }
411 return p & gd->mask;
412 }
413
414 static
415 int gf_wgen_group_init(gf_t *gf)
416 {
417 uint32_t i, j, p, index;
418 struct gf_wgen_group_data *gd;
419 gf_internal_t *h = (gf_internal_t *) gf->scratch;
420 uint32_t g_s, g_r;
421
|
(1) Event cond_true: |
Condition "h->mult_type == GF_MULT_DEFAULT", taking true branch. |
422 if (h->mult_type == GF_MULT_DEFAULT) {
423 g_s = 2;
424 g_r = 8;
|
(3) Event if_fallthrough: |
Falling through to end of if statement. |
425 } else {
426 g_s = h->arg1;
427 g_r = h->arg2;
|
(4) Event if_end: |
End of if statement. |
428 }
429 gd = (struct gf_wgen_group_data *) h->private;
|
(5) Event alias: |
Assigning: "gd->shift" = "&gd->memory". "gd->shift" now points to element 0 of "gd->memory" (which consists of 1 4-byte elements). |
| Also see events: |
[assignment][alias][overrun-local] |
430 gd->shift = &(gd->memory);
|
(6) Event alias: |
Assigning: "gd->reduce" = "gd->shift + (1 << g_s)". "gd->reduce" now points to element 4 of "gd->memory" (which consists of 1 4-byte elements). |
| Also see events: |
[assignment][alias][overrun-local] |
431 gd->reduce = gd->shift + (1 << g_s);
|
(7) Event cond_true: |
Condition "h->w != 31", taking true branch. |
432 gd->mask = (h->w != 31) ? ((1 << h->w)-1) : 0x7fffffff;
433
434 gd->rmask = (1 << g_r) - 1;
435 gd->rmask <<= h->w;
436
437 gd->tshift = h->w % g_s;
|
(8) Event cond_true: |
Condition "gd->tshift == 0", taking true branch. |
438 if (gd->tshift == 0) gd->tshift = g_s;
439 gd->tshift = (h->w - gd->tshift);
440 gd->tshift = ((gd->tshift-1)/g_r) * g_r;
441
|
(9) Event overrun-local: |
Overrunning array of 1 4-byte elements at element index 4 (byte offset 19) by dereferencing pointer "gd->reduce + 0". |
| Also see events: |
[assignment][alias][alias] |
442 gd->reduce[0] = 0;
443 for (i = 0; i < ((uint32_t)1 << g_r); i++) {
444 p = 0;
445 index = 0;
446 for (j = 0; j < g_r; j++) {
447 if (i & (1 << j)) {
448 p ^= (h->prim_poly << j);
449 index ^= (h->prim_poly >> (h->w-j));
450 }
451 }
452 gd->reduce[index] = (p & gd->mask);
453 }
454
455 if (g_s == g_r) {
456 SET_FUNCTION(gf,multiply,w32,gf_wgen_group_s_equals_r_multiply)
457 } else {
458 SET_FUNCTION(gf,multiply,w32,gf_wgen_group_multiply)
459 }
460 SET_FUNCTION(gf,divide,w32,NULL)
461 SET_FUNCTION(gf,divide,w32,NULL)
462 return 1;
463 }
464
465
466 static
467 gf_val_32_t
468 gf_wgen_table_8_multiply(gf_t *gf, gf_val_32_t a, gf_val_32_t b)
469 {
470 gf_internal_t *h;
471 struct gf_wgen_table_w8_data *std;
472
473 h = (gf_internal_t *) gf->scratch;
474 std = (struct gf_wgen_table_w8_data *) h->private;
475
476 return (std->mult[(a<<h->w)+b]);
477 }
478
479 static
480 gf_val_32_t
481 gf_wgen_table_8_divide(gf_t *gf, gf_val_32_t a, gf_val_32_t b)
482 {
483 gf_internal_t *h;
484 struct gf_wgen_table_w8_data *std;
485
486 h = (gf_internal_t *) gf->scratch;
487 std = (struct gf_wgen_table_w8_data *) h->private;
488
489 return (std->div[(a<<h->w)+b]);
490 }
491
492 static
493 int gf_wgen_table_8_init(gf_t *gf)
494 {
495 gf_internal_t *h;
496 int w;
497 struct gf_wgen_table_w8_data *std;
498 uint32_t a, b, p;
499
500 h = (gf_internal_t *) gf->scratch;
501 w = h->w;
502 std = (struct gf_wgen_table_w8_data *) h->private;
503
504 std->mult = &(std->base);
505 std->div = std->mult + ((1<<h->w)*(1<<h->w));
506
507 for (a = 0; a < ((uint32_t)1 << w); a++) {
508 std->mult[a] = 0;
509 std->mult[a<<w] = 0;
510 std->div[a] = 0;
511 std->div[a<<w] = 0;
512 }
513
514 for (a = 1; a < ((uint32_t)1 << w); a++) {
515 for (b = 1; b < ((uint32_t)1 << w); b++) {
516 p = gf_wgen_shift_multiply(gf, a, b);
517 std->mult[(a<<w)|b] = p;
518 std->div[(p<<w)|a] = b;
519 }
520 }
521
522 SET_FUNCTION(gf,multiply,w32,gf_wgen_table_8_multiply)
523 SET_FUNCTION(gf,divide,w32,gf_wgen_table_8_divide)
524 return 1;
525 }
526
527 static
528 gf_val_32_t
529 gf_wgen_table_16_multiply(gf_t *gf, gf_val_32_t a, gf_val_32_t b)
530 {
531 gf_internal_t *h;
532 struct gf_wgen_table_w16_data *std;
533
534 h = (gf_internal_t *) gf->scratch;
535 std = (struct gf_wgen_table_w16_data *) h->private;
536
537 return (std->mult[(a<<h->w)+b]);
538 }
539
540 static
541 gf_val_32_t
542 gf_wgen_table_16_divide(gf_t *gf, gf_val_32_t a, gf_val_32_t b)
543 {
544 gf_internal_t *h;
545 struct gf_wgen_table_w16_data *std;
546
547 h = (gf_internal_t *) gf->scratch;
548 std = (struct gf_wgen_table_w16_data *) h->private;
549
550 return (std->div[(a<<h->w)+b]);
551 }
552
553 static
554 int gf_wgen_table_16_init(gf_t *gf)
555 {
556 gf_internal_t *h;
557 int w;
558 struct gf_wgen_table_w16_data *std;
559 uint32_t a, b, p;
560
561 h = (gf_internal_t *) gf->scratch;
562 w = h->w;
563 std = (struct gf_wgen_table_w16_data *) h->private;
564
565 std->mult = &(std->base);
566 std->div = std->mult + ((1<<h->w)*(1<<h->w));
567
568 for (a = 0; a < ((uint32_t)1 << w); a++) {
569 std->mult[a] = 0;
570 std->mult[a<<w] = 0;
571 std->div[a] = 0;
572 std->div[a<<w] = 0;
573 }
574
575 for (a = 1; a < ((uint32_t)1 << w); a++) {
576 for (b = 1; b < ((uint32_t)1 << w); b++) {
577 p = gf_wgen_shift_multiply(gf, a, b);
578 std->mult[(a<<w)|b] = p;
579 std->div[(p<<w)|a] = b;
580 }
581 }
582
583 SET_FUNCTION(gf,multiply,w32,gf_wgen_table_16_multiply)
584 SET_FUNCTION(gf,divide,w32,gf_wgen_table_16_divide)
585 return 1;
586 }
587
588 static
589 int gf_wgen_table_init(gf_t *gf)
590 {
591 gf_internal_t *h;
592
593 h = (gf_internal_t *) gf->scratch;
594 if (h->w <= 8) return gf_wgen_table_8_init(gf);
595 if (h->w <= 14) return gf_wgen_table_16_init(gf);
596
597 /* Returning zero to make the compiler happy, but this won't get
598 executed, because it is tested in _scratch_space. */
599
600 return 0;
601 }
602
603 static
604 gf_val_32_t
605 gf_wgen_log_8_multiply(gf_t *gf, gf_val_32_t a, gf_val_32_t b)
606 {
607 gf_internal_t *h;
608 struct gf_wgen_log_w8_data *std;
609
610 h = (gf_internal_t *) gf->scratch;
611 std = (struct gf_wgen_log_w8_data *) h->private;
612
613 if (a == 0 || b == 0) return 0;
614 return (std->anti[std->log[a]+std->log[b]]);
615 }
616
617 static
618 gf_val_32_t
619 gf_wgen_log_8_divide(gf_t *gf, gf_val_32_t a, gf_val_32_t b)
620 {
621 gf_internal_t *h;
622 struct gf_wgen_log_w8_data *std;
623 int index;
624
625 h = (gf_internal_t *) gf->scratch;
626 std = (struct gf_wgen_log_w8_data *) h->private;
627
628 if (a == 0 || b == 0) return 0;
629 index = std->log[a];
630 index -= std->log[b];
631
632 return (std->danti[index]);
633 }
634
635 static
636 int gf_wgen_log_8_init(gf_t *gf)
637 {
638 gf_internal_t *h;
639 struct gf_wgen_log_w8_data *std;
640 int w;
641 uint32_t a, i;
642 int check = 0;
643
644 h = (gf_internal_t *) gf->scratch;
645 w = h->w;
646 std = (struct gf_wgen_log_w8_data *) h->private;
647
648 std->log = &(std->base);
649 std->anti = std->log + (1<<h->w);
650 std->danti = std->anti + (1<<h->w)-1;
651
652 for (i = 0; i < ((uint32_t)1 << w); i++)
653 std->log[i] = 0;
654
655 a = 1;
656 for(i=0; i < ((uint32_t)1<<w)-1; i++)
657 {
658 if (std->log[a] != 0) check = 1;
659 std->log[a] = i;
660 std->anti[i] = a;
661 std->danti[i] = a;
662 a <<= 1;
663 if(a & (1<<w))
664 a ^= h->prim_poly;
665 //a &= ((1 << w)-1);
666 }
667
668 if (check != 0) {
669 _gf_errno = GF_E_LOGPOLY;
670 return 0;
671 }
672
673 SET_FUNCTION(gf,multiply,w32,gf_wgen_log_8_multiply)
674 SET_FUNCTION(gf,divide,w32,gf_wgen_log_8_divide)
675 return 1;
676 }
677
678 static
679 gf_val_32_t
680 gf_wgen_log_16_multiply(gf_t *gf, gf_val_32_t a, gf_val_32_t b)
681 {
682 gf_internal_t *h;
683 struct gf_wgen_log_w16_data *std;
684
685 h = (gf_internal_t *) gf->scratch;
686 std = (struct gf_wgen_log_w16_data *) h->private;
687
688 if (a == 0 || b == 0) return 0;
689 return (std->anti[std->log[a]+std->log[b]]);
690 }
691
692 static
693 gf_val_32_t
694 gf_wgen_log_16_divide(gf_t *gf, gf_val_32_t a, gf_val_32_t b)
695 {
696 gf_internal_t *h;
697 struct gf_wgen_log_w16_data *std;
698 int index;
699
700 h = (gf_internal_t *) gf->scratch;
701 std = (struct gf_wgen_log_w16_data *) h->private;
702
703 if (a == 0 || b == 0) return 0;
704 index = std->log[a];
705 index -= std->log[b];
706
707 return (std->danti[index]);
708 }
709
710 static
711 int gf_wgen_log_16_init(gf_t *gf)
712 {
713 gf_internal_t *h;
714 struct gf_wgen_log_w16_data *std;
715 int w;
716 uint32_t a, i;
717 int check = 0;
718
719 h = (gf_internal_t *) gf->scratch;
720 w = h->w;
721 std = (struct gf_wgen_log_w16_data *) h->private;
722
723 std->log = &(std->base);
724 std->anti = std->log + (1<<h->w);
725 std->danti = std->anti + (1<<h->w)-1;
726
727 for (i = 0; i < ((uint32_t)1 << w); i++)
728 std->log[i] = 0;
729
730 a = 1;
731 for(i=0; i < ((uint32_t)1<<w)-1; i++)
732 {
733 if (std->log[a] != 0) check = 1;
734 std->log[a] = i;
735 std->anti[i] = a;
736 std->danti[i] = a;
737 a <<= 1;
738 if(a & (1<<w))
739 a ^= h->prim_poly;
740 //a &= ((1 << w)-1);
741 }
742
743 if (check) {
744 if (h->mult_type != GF_MULT_LOG_TABLE) return gf_wgen_shift_init(gf);
745 _gf_errno = GF_E_LOGPOLY;
746 return 0;
747 }
748
749 SET_FUNCTION(gf,multiply,w32,gf_wgen_log_16_multiply)
750 SET_FUNCTION(gf,divide,w32,gf_wgen_log_16_divide)
751 return 1;
752 }
753
754 static
755 gf_val_32_t
756 gf_wgen_log_32_multiply(gf_t *gf, gf_val_32_t a, gf_val_32_t b)
757 {
758 gf_internal_t *h;
759 struct gf_wgen_log_w32_data *std;
760
761 h = (gf_internal_t *) gf->scratch;
762 std = (struct gf_wgen_log_w32_data *) h->private;
763
764 if (a == 0 || b == 0) return 0;
765 return (std->anti[std->log[a]+std->log[b]]);
766 }
767
768 static
769 gf_val_32_t
770 gf_wgen_log_32_divide(gf_t *gf, gf_val_32_t a, gf_val_32_t b)
771 {
772 gf_internal_t *h;
773 struct gf_wgen_log_w32_data *std;
774 int index;
775
776 h = (gf_internal_t *) gf->scratch;
777 std = (struct gf_wgen_log_w32_data *) h->private;
778
779 if (a == 0 || b == 0) return 0;
780 index = std->log[a];
781 index -= std->log[b];
782
783 return (std->danti[index]);
784 }
785
786 static
787 int gf_wgen_log_32_init(gf_t *gf)
788 {
789 gf_internal_t *h;
790 struct gf_wgen_log_w32_data *std;
791 int w;
792 uint32_t a, i;
793 int check = 0;
794
795 h = (gf_internal_t *) gf->scratch;
796 w = h->w;
797 std = (struct gf_wgen_log_w32_data *) h->private;
798
799 std->log = &(std->base);
800 std->anti = std->log + (1<<h->w);
801 std->danti = std->anti + (1<<h->w)-1;
802
803 for (i = 0; i < ((uint32_t)1 << w); i++)
804 std->log[i] = 0;
805
806 a = 1;
807 for(i=0; i < ((uint32_t)1<<w)-1; i++)
808 {
809 if (std->log[a] != 0) check = 1;
810 std->log[a] = i;
811 std->anti[i] = a;
812 std->danti[i] = a;
813 a <<= 1;
814 if(a & (1<<w))
815 a ^= h->prim_poly;
816 //a &= ((1 << w)-1);
817 }
818
819 if (check != 0) {
820 _gf_errno = GF_E_LOGPOLY;
821 return 0;
822 }
823
824 SET_FUNCTION(gf,multiply,w32,gf_wgen_log_32_multiply)
825 SET_FUNCTION(gf,divide,w32,gf_wgen_log_32_divide)
826 return 1;
827 }
828
829 static
830 int gf_wgen_log_init(gf_t *gf)
831 {
832 gf_internal_t *h;
833
834 h = (gf_internal_t *) gf->scratch;
835 if (h->w <= 8) return gf_wgen_log_8_init(gf);
836 if (h->w <= 16) return gf_wgen_log_16_init(gf);
837 if (h->w <= 32) return gf_wgen_log_32_init(gf);
838
839 /* Returning zero to make the compiler happy, but this won't get
840 executed, because it is tested in _scratch_space. */
841
842 return 0;
843 }
844
845 int gf_wgen_scratch_size(int w, int mult_type, int region_type, int divide_type, int arg1, int arg2)
846 {
847
848 switch(mult_type)
849 {
850 case GF_MULT_DEFAULT:
851 if (w <= 8) {
852 return sizeof(gf_internal_t) + sizeof(struct gf_wgen_table_w8_data) +
853 sizeof(uint8_t)*(1 << w)*(1<<w)*2 + 64;
854 } else if (w <= 16) {
855 return sizeof(gf_internal_t) + sizeof(struct gf_wgen_log_w16_data) +
856 sizeof(uint16_t)*(1 << w)*3;
857 } else {
858 return sizeof(gf_internal_t) + sizeof(struct gf_wgen_group_data) +
859 sizeof(uint32_t) * (1 << 2) +
860 sizeof(uint32_t) * (1 << 8) + 64;
861 }
862 case GF_MULT_SHIFT:
863 case GF_MULT_BYTWO_b:
864 case GF_MULT_BYTWO_p:
865 return sizeof(gf_internal_t);
866 break;
867 case GF_MULT_GROUP:
868 return sizeof(gf_internal_t) + sizeof(struct gf_wgen_group_data) +
869 sizeof(uint32_t) * (1 << arg1) +
870 sizeof(uint32_t) * (1 << arg2) + 64;
871 break;
872
873 case GF_MULT_TABLE:
874 if (w <= 8) {
875 return sizeof(gf_internal_t) + sizeof(struct gf_wgen_table_w8_data) +
876 sizeof(uint8_t)*(1 << w)*(1<<w)*2 + 64;
877 } else if (w < 15) {
878 return sizeof(gf_internal_t) + sizeof(struct gf_wgen_table_w16_data) +
879 sizeof(uint16_t)*(1 << w)*(1<<w)*2 + 64;
880 }
881 return 0;
882 case GF_MULT_LOG_TABLE:
883 if (w <= 8) {
884 return sizeof(gf_internal_t) + sizeof(struct gf_wgen_log_w8_data) +
885 sizeof(uint8_t)*(1 << w)*3;
886 } else if (w <= 16) {
887 return sizeof(gf_internal_t) + sizeof(struct gf_wgen_log_w16_data) +
888 sizeof(uint16_t)*(1 << w)*3;
889 } else if (w <= 27) {
890 return sizeof(gf_internal_t) + sizeof(struct gf_wgen_log_w32_data) +
891 sizeof(uint32_t)*(1 << w)*3;
892 } else
893 return 0;
894 default:
895 return 0;
896 }
897 }
898
899 void
900 gf_wgen_cauchy_region(gf_t *gf, void *src, void *dest, gf_val_32_t val, int bytes, int xor)
901 {
902 gf_internal_t *h;
903 gf_region_data rd;
904 int written;
905 int rs, i, j;
906
907 gf_set_region_data(&rd, gf, src, dest, bytes, val, xor, -1);
908
909 if (val == 0) { gf_multby_zero(dest, bytes, xor); return; }
910 if (val == 1) { gf_multby_one(src, dest, bytes, xor); return; }
911
912 h = (gf_internal_t *) gf->scratch;
913 rs = bytes / (h->w);
914
915 written = (xor) ? 0xffffffff : 0;
916 for (i = 0; i < h->w; i++) {
917 for (j = 0; j < h->w; j++) {
918 if (val & (1 << j)) {
919 gf_multby_one(src, ((uint8_t *)dest) + j*rs, rs, (written & (1 << j)));
920 written |= (1 << j);
921 }
922 }
923 src = (uint8_t *)src + rs;
924 val = gf->multiply.w32(gf, val, 2);
925 }
926 }
927
928 int gf_wgen_init(gf_t *gf)
929 {
930 gf_internal_t *h;
931
932 h = (gf_internal_t *) gf->scratch;
933 if (h->prim_poly == 0) {
934 switch (h->w) {
935 case 1: h->prim_poly = 1; break;
936 case 2: h->prim_poly = 7; break;
937 case 3: h->prim_poly = 013; break;
938 case 4: h->prim_poly = 023; break;
939 case 5: h->prim_poly = 045; break;
940 case 6: h->prim_poly = 0103; break;
941 case 7: h->prim_poly = 0211; break;
942 case 8: h->prim_poly = 0435; break;
943 case 9: h->prim_poly = 01021; break;
944 case 10: h->prim_poly = 02011; break;
945 case 11: h->prim_poly = 04005; break;
946 case 12: h->prim_poly = 010123; break;
947 case 13: h->prim_poly = 020033; break;
948 case 14: h->prim_poly = 042103; break;
949 case 15: h->prim_poly = 0100003; break;
950 case 16: h->prim_poly = 0210013; break;
951 case 17: h->prim_poly = 0400011; break;
952 case 18: h->prim_poly = 01000201; break;
953 case 19: h->prim_poly = 02000047; break;
954 case 20: h->prim_poly = 04000011; break;
955 case 21: h->prim_poly = 010000005; break;
956 case 22: h->prim_poly = 020000003; break;
957 case 23: h->prim_poly = 040000041; break;
958 case 24: h->prim_poly = 0100000207; break;
959 case 25: h->prim_poly = 0200000011; break;
960 case 26: h->prim_poly = 0400000107; break;
961 case 27: h->prim_poly = 01000000047; break;
962 case 28: h->prim_poly = 02000000011; break;
963 case 29: h->prim_poly = 04000000005; break;
964 case 30: h->prim_poly = 010040000007; break;
965 case 31: h->prim_poly = 020000000011; break;
966 case 32: h->prim_poly = 00020000007; break;
967 default: fprintf(stderr, "gf_wgen_init: w not defined yet\n"); exit(1);
968 }
969 } else {
970 if (h->w == 32) {
971 h->prim_poly &= 0xffffffff;
972 } else {
973 h->prim_poly |= (1 << h->w);
974 if (h->prim_poly & ~((1ULL<<(h->w+1))-1)) return 0;
975 }
976 }
977
978 SET_FUNCTION(gf,multiply,w32,NULL)
979 SET_FUNCTION(gf,divide,w32,NULL)
980 SET_FUNCTION(gf,inverse,w32,NULL)
981 SET_FUNCTION(gf,multiply_region,w32,gf_wgen_cauchy_region)
982 SET_FUNCTION(gf,extract_word,w32,gf_wgen_extract_word)
983
984 switch(h->mult_type) {
985 case GF_MULT_DEFAULT:
986 if (h->w <= 8) {
987 if (gf_wgen_table_init(gf) == 0) return 0;
988 } else if (h->w <= 16) {
989 if (gf_wgen_log_init(gf) == 0) return 0;
990 } else {
991 if (gf_wgen_bytwo_p_init(gf) == 0) return 0;
992 }
993 break;
994 case GF_MULT_SHIFT: if (gf_wgen_shift_init(gf) == 0) return 0; break;
995 case GF_MULT_BYTWO_b: if (gf_wgen_bytwo_b_init(gf) == 0) return 0; break;
996 case GF_MULT_BYTWO_p: if (gf_wgen_bytwo_p_init(gf) == 0) return 0; break;
997 case GF_MULT_GROUP: if (gf_wgen_group_init(gf) == 0) return 0; break;
998 case GF_MULT_TABLE: if (gf_wgen_table_init(gf) == 0) return 0; break;
999 case GF_MULT_LOG_TABLE: if (gf_wgen_log_init(gf) == 0) return 0; break;
1000 default: return 0;
1001 }
1002 if (h->divide_type == GF_DIVIDE_EUCLID) {
1003 SET_FUNCTION(gf,divide,w32,gf_wgen_divide_from_inverse)
1004 SET_FUNCTION(gf,inverse,w32,gf_wgen_euclid)
1005 } else if (h->divide_type == GF_DIVIDE_MATRIX) {
1006 SET_FUNCTION(gf,divide,w32,gf_wgen_divide_from_inverse)
1007 SET_FUNCTION(gf,inverse,w32,gf_wgen_matrix)
1008 }
1009
1010 if (gf->inverse.w32== NULL && gf->divide.w32 == NULL) SET_FUNCTION(gf,inverse,w32,gf_wgen_euclid)
1011
1012 if (gf->inverse.w32 != NULL && gf->divide.w32 == NULL) {
1013 SET_FUNCTION(gf,divide,w32,gf_wgen_divide_from_inverse)
1014 }
1015 if (gf->inverse.w32 == NULL && gf->divide.w32 != NULL) {
1016 SET_FUNCTION(gf,inverse,w32,gf_wgen_inverse_from_divide)
1017 }
1018 return 1;
1019 }
1020