ceph/src/erasure-code/jerasure/gf-complete/src/gf_wgen.c

   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
 422   if (h->mult_type == GF_MULT_DEFAULT) {
 423     g_s = 2;
 424     g_r = 8;
 425   } else {
 426     g_s = h->arg1;
 427     g_r = h->arg2;
 428   }
 429   gd = (struct gf_wgen_group_data *) h->private;
 430   gd->shift = &(gd->memory);
 431   gd->reduce = gd->shift + (1 << g_s);
 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;
 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
 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 }