diff options
Diffstat (limited to 'src/c/gf-complete/src/gf_wgen.c')
| -rw-r--r-- | src/c/gf-complete/src/gf_wgen.c | 1019 |
1 files changed, 1019 insertions, 0 deletions
diff --git a/src/c/gf-complete/src/gf_wgen.c b/src/c/gf-complete/src/gf_wgen.c new file mode 100644 index 0000000..c6a830e --- /dev/null +++ b/src/c/gf-complete/src/gf_wgen.c @@ -0,0 +1,1019 @@ +/* + * GF-Complete: A Comprehensive Open Source Library for Galois Field Arithmetic + * James S. Plank, Ethan L. Miller, Kevin M. Greenan, + * Benjamin A. Arnold, John A. Burnum, Adam W. Disney, Allen C. McBride. + * + * gf_wgen.c + * + * Routines for Galois fields for general w < 32. For specific w, + like 4, 8, 16, 32, 64 and 128, see the other files. + */ + +#include "gf_int.h" +#include <stdio.h> +#include <stdlib.h> + +struct gf_wgen_table_w8_data { + uint8_t *mult; + uint8_t *div; + uint8_t base; +}; + +struct gf_wgen_table_w16_data { + uint16_t *mult; + uint16_t *div; + uint16_t base; +}; + +struct gf_wgen_log_w8_data { + uint8_t *log; + uint8_t *anti; + uint8_t *danti; + uint8_t base; +}; + +struct gf_wgen_log_w16_data { + uint16_t *log; + uint16_t *anti; + uint16_t *danti; + uint16_t base; +}; + +struct gf_wgen_log_w32_data { + uint32_t *log; + uint32_t *anti; + uint32_t *danti; + uint32_t base; +}; + +struct gf_wgen_group_data { + uint32_t *reduce; + uint32_t *shift; + uint32_t mask; + uint64_t rmask; + int tshift; + uint32_t memory; +}; + +static +inline +gf_val_32_t gf_wgen_inverse_from_divide (gf_t *gf, gf_val_32_t a) +{ + return gf->divide.w32(gf, 1, a); +} + +static +inline +gf_val_32_t gf_wgen_divide_from_inverse (gf_t *gf, gf_val_32_t a, gf_val_32_t b) +{ + b = gf->inverse.w32(gf, b); + return gf->multiply.w32(gf, a, b); +} + +static +inline +gf_val_32_t gf_wgen_euclid (gf_t *gf, gf_val_32_t b) +{ + + gf_val_32_t e_i, e_im1, e_ip1; + gf_val_32_t d_i, d_im1, d_ip1; + gf_val_32_t y_i, y_im1, y_ip1; + gf_val_32_t c_i; + + if (b == 0) return -1; + e_im1 = ((gf_internal_t *) (gf->scratch))->prim_poly; + e_i = b; + d_im1 = ((gf_internal_t *) (gf->scratch))->w; + for (d_i = d_im1; ((1 << d_i) & e_i) == 0; d_i--) ; + y_i = 1; + y_im1 = 0; + + while (e_i != 1) { + + e_ip1 = e_im1; + d_ip1 = d_im1; + c_i = 0; + + while (d_ip1 >= d_i) { + c_i ^= (1 << (d_ip1 - d_i)); + e_ip1 ^= (e_i << (d_ip1 - d_i)); + if (e_ip1 == 0) return 0; + while ((e_ip1 & (1 << d_ip1)) == 0) d_ip1--; + } + + y_ip1 = y_im1 ^ gf->multiply.w32(gf, c_i, y_i); + y_im1 = y_i; + y_i = y_ip1; + + e_im1 = e_i; + d_im1 = d_i; + e_i = e_ip1; + d_i = d_ip1; + } + + return y_i; +} + +gf_val_32_t gf_wgen_extract_word(gf_t *gf, void *start, int bytes, int index) +{ + uint8_t *ptr; + uint32_t rv; + int rs; + int byte, bit, i; + gf_internal_t *h; + + h = (gf_internal_t *) gf->scratch; + rs = bytes / h->w; + byte = index/8; + bit = index%8; + + ptr = (uint8_t *) start; + ptr += bytes; + ptr -= rs; + ptr += byte; + + rv = 0; + for (i = 0; i < h->w; i++) { + rv <<= 1; + if ((*ptr) & (1 << bit)) rv |= 1; + ptr -= rs; + } + + return rv; +} + +static +inline +gf_val_32_t gf_wgen_matrix (gf_t *gf, gf_val_32_t b) +{ + return gf_bitmatrix_inverse(b, ((gf_internal_t *) (gf->scratch))->w, + ((gf_internal_t *) (gf->scratch))->prim_poly); +} + +static +inline +uint32_t +gf_wgen_shift_multiply (gf_t *gf, uint32_t a32, uint32_t b32) +{ + uint64_t product, i, pp, a, b, one; + gf_internal_t *h; + + a = a32; + b = b32; + h = (gf_internal_t *) gf->scratch; + one = 1; + pp = h->prim_poly | (one << h->w); + + product = 0; + + for (i = 0; i < h->w; i++) { + if (a & (one << i)) product ^= (b << i); + } + for (i = h->w*2-1; i >= h->w; i--) { + if (product & (one << i)) product ^= (pp << (i-h->w)); + } + return product; +} + +static +int gf_wgen_shift_init(gf_t *gf) +{ + gf->multiply.w32 = gf_wgen_shift_multiply; + gf->inverse.w32 = gf_wgen_euclid; + return 1; +} + +static +gf_val_32_t +gf_wgen_bytwo_b_multiply (gf_t *gf, gf_val_32_t a, gf_val_32_t b) +{ + uint32_t prod, pp, bmask; + gf_internal_t *h; + + h = (gf_internal_t *) gf->scratch; + pp = h->prim_poly; + + prod = 0; + bmask = (1 << (h->w-1)); + + while (1) { + if (a & 1) prod ^= b; + a >>= 1; + if (a == 0) return prod; + if (b & bmask) { + b = ((b << 1) ^ pp); + } else { + b <<= 1; + } + } +} + +static +int gf_wgen_bytwo_b_init(gf_t *gf) +{ + gf->multiply.w32 = gf_wgen_bytwo_b_multiply; + gf->inverse.w32 = gf_wgen_euclid; + return 1; +} + +static +inline +gf_val_32_t +gf_wgen_bytwo_p_multiply (gf_t *gf, gf_val_32_t a, gf_val_32_t b) +{ + uint32_t prod, pp, pmask, amask; + gf_internal_t *h; + + h = (gf_internal_t *) gf->scratch; + pp = h->prim_poly; + + prod = 0; + pmask = (1 << ((h->w)-1)); /*Ben: Had an operator precedence warning here*/ + amask = pmask; + + while (amask != 0) { + if (prod & pmask) { + prod = ((prod << 1) ^ pp); + } else { + prod <<= 1; + } + if (a & amask) prod ^= b; + amask >>= 1; + } + return prod; +} + + +static +int gf_wgen_bytwo_p_init(gf_t *gf) +{ + gf->multiply.w32 = gf_wgen_bytwo_p_multiply; + gf->inverse.w32 = gf_wgen_euclid; + return 1; +} + +static +void +gf_wgen_group_set_shift_tables(uint32_t *shift, uint32_t val, gf_internal_t *h) +{ + int i; + uint32_t j; + int g_s; + + if (h->mult_type == GF_MULT_DEFAULT) { + g_s = 2; + } else { + g_s = h->arg1; + } + + shift[0] = 0; + + for (i = 1; i < (1 << g_s); i <<= 1) { + for (j = 0; j < i; j++) shift[i|j] = shift[j]^val; + if (val & (1 << (h->w-1))) { + val <<= 1; + val ^= h->prim_poly; + } else { + val <<= 1; + } + } +} + +static +inline +gf_val_32_t +gf_wgen_group_s_equals_r_multiply(gf_t *gf, gf_val_32_t a, gf_val_32_t b) +{ + int leftover, rs; + uint32_t p, l, ind, a32; + int bits_left; + int g_s; + int w; + + struct gf_wgen_group_data *gd; + gf_internal_t *h = (gf_internal_t *) gf->scratch; + g_s = h->arg1; + w = h->w; + + gd = (struct gf_wgen_group_data *) h->private; + gf_wgen_group_set_shift_tables(gd->shift, b, h); + + leftover = w % g_s; + if (leftover == 0) leftover = g_s; + + rs = w - leftover; + a32 = a; + ind = a32 >> rs; + a32 <<= leftover; + a32 &= gd->mask; + p = gd->shift[ind]; + + bits_left = rs; + rs = w - g_s; + + while (bits_left > 0) { + bits_left -= g_s; + ind = a32 >> rs; + a32 <<= g_s; + a32 &= gd->mask; + l = p >> rs; + p = (gd->shift[ind] ^ gd->reduce[l] ^ (p << g_s)) & gd->mask; + } + return p; +} + +char *bits(uint32_t v) +{ + char *rv; + int i, j; + + rv = malloc(30); + j = 0; + for (i = 27; i >= 0; i--) { + rv[j] = '0' + ((v & (1 << i)) ? 1 : 0); + j++; + } + rv[j] = '\0'; + return rv; +} +char *bits_56(uint64_t v) +{ + char *rv; + int i, j; + uint64_t one; + + one = 1; + + rv = malloc(60); + j = 0; + for (i = 55; i >= 0; i--) { + rv[j] = '0' + ((v & (one << i)) ? 1 : 0); + j++; + } + rv[j] = '\0'; + return rv; +} + +static +inline +gf_val_32_t +gf_wgen_group_multiply(gf_t *gf, gf_val_32_t a, gf_val_32_t b) +{ + int i; + int leftover; + uint64_t p, l, r; + uint32_t a32, ind; + int g_s, g_r; + struct gf_wgen_group_data *gd; + int w; + + gf_internal_t *h = (gf_internal_t *) gf->scratch; + if (h->mult_type == GF_MULT_DEFAULT) { + g_s = 2; + g_r = 8; + } else { + g_s = h->arg1; + g_r = h->arg2; + } + w = h->w; + gd = (struct gf_wgen_group_data *) h->private; + gf_wgen_group_set_shift_tables(gd->shift, b, h); + + leftover = w % g_s; + if (leftover == 0) leftover = g_s; + + a32 = a; + ind = a32 >> (w - leftover); + p = gd->shift[ind]; + p <<= g_s; + a32 <<= leftover; + a32 &= gd->mask; + + i = (w - leftover); + while (i > g_s) { + ind = a32 >> (w-g_s); + p ^= gd->shift[ind]; + a32 <<= g_s; + a32 &= gd->mask; + p <<= g_s; + i -= g_s; + } + + ind = a32 >> (h->w-g_s); + p ^= gd->shift[ind]; + + for (i = gd->tshift ; i >= 0; i -= g_r) { + l = p & (gd->rmask << i); + r = gd->reduce[l >> (i+w)]; + r <<= (i); + p ^= r; + } + return p & gd->mask; +} + +static +int gf_wgen_group_init(gf_t *gf) +{ + uint32_t i, j, p, index; + struct gf_wgen_group_data *gd; + gf_internal_t *h = (gf_internal_t *) gf->scratch; + int g_s, g_r; + + if (h->mult_type == GF_MULT_DEFAULT) { + g_s = 2; + g_r = 8; + } else { + g_s = h->arg1; + g_r = h->arg2; + } + gd = (struct gf_wgen_group_data *) h->private; + gd->shift = &(gd->memory); + gd->reduce = gd->shift + (1 << g_s); + gd->mask = (h->w != 31) ? ((1 << h->w)-1) : 0x7fffffff; + + gd->rmask = (1 << g_r) - 1; + gd->rmask <<= h->w; + + gd->tshift = h->w % g_s; + if (gd->tshift == 0) gd->tshift = g_s; + gd->tshift = (h->w - gd->tshift); + gd->tshift = ((gd->tshift-1)/g_r) * g_r; + + gd->reduce[0] = 0; + for (i = 0; i < (1 << g_r); i++) { + p = 0; + index = 0; + for (j = 0; j < g_r; j++) { + if (i & (1 << j)) { + p ^= (h->prim_poly << j); + index ^= (h->prim_poly >> (h->w-j)); + } + } + gd->reduce[index] = (p & gd->mask); + } + + if (g_s == g_r) { + gf->multiply.w32 = gf_wgen_group_s_equals_r_multiply; + } else { + gf->multiply.w32 = gf_wgen_group_multiply; + } + gf->divide.w32 = NULL; + gf->divide.w32 = NULL; + return 1; +} + + +static +gf_val_32_t +gf_wgen_table_8_multiply(gf_t *gf, gf_val_32_t a, gf_val_32_t b) +{ + gf_internal_t *h; + struct gf_wgen_table_w8_data *std; + + h = (gf_internal_t *) gf->scratch; + std = (struct gf_wgen_table_w8_data *) h->private; + + return (std->mult[(a<<h->w)+b]); +} + +static +gf_val_32_t +gf_wgen_table_8_divide(gf_t *gf, gf_val_32_t a, gf_val_32_t b) +{ + gf_internal_t *h; + struct gf_wgen_table_w8_data *std; + + h = (gf_internal_t *) gf->scratch; + std = (struct gf_wgen_table_w8_data *) h->private; + + return (std->div[(a<<h->w)+b]); +} + +static +int gf_wgen_table_8_init(gf_t *gf) +{ + gf_internal_t *h; + int w; + struct gf_wgen_table_w8_data *std; + uint32_t a, b, p; + + h = (gf_internal_t *) gf->scratch; + w = h->w; + std = (struct gf_wgen_table_w8_data *) h->private; + + std->mult = &(std->base); + std->div = std->mult + ((1<<h->w)*(1<<h->w)); + + for (a = 0; a < (1 << w); a++) { + std->mult[a] = 0; + std->mult[a<<w] = 0; + std->div[a] = 0; + std->div[a<<w] = 0; + } + + for (a = 1; a < (1 << w); a++) { + for (b = 1; b < (1 << w); b++) { + p = gf_wgen_shift_multiply(gf, a, b); + std->mult[(a<<w)|b] = p; + std->div[(p<<w)|a] = b; + } + } + + gf->multiply.w32 = gf_wgen_table_8_multiply; + gf->divide.w32 = gf_wgen_table_8_divide; + return 1; +} + +static +gf_val_32_t +gf_wgen_table_16_multiply(gf_t *gf, gf_val_32_t a, gf_val_32_t b) +{ + gf_internal_t *h; + struct gf_wgen_table_w16_data *std; + + h = (gf_internal_t *) gf->scratch; + std = (struct gf_wgen_table_w16_data *) h->private; + + return (std->mult[(a<<h->w)+b]); +} + +static +gf_val_32_t +gf_wgen_table_16_divide(gf_t *gf, gf_val_32_t a, gf_val_32_t b) +{ + gf_internal_t *h; + struct gf_wgen_table_w16_data *std; + + h = (gf_internal_t *) gf->scratch; + std = (struct gf_wgen_table_w16_data *) h->private; + + return (std->div[(a<<h->w)+b]); +} + +static +int gf_wgen_table_16_init(gf_t *gf) +{ + gf_internal_t *h; + int w; + struct gf_wgen_table_w16_data *std; + uint32_t a, b, p; + + h = (gf_internal_t *) gf->scratch; + w = h->w; + std = (struct gf_wgen_table_w16_data *) h->private; + + std->mult = &(std->base); + std->div = std->mult + ((1<<h->w)*(1<<h->w)); + + for (a = 0; a < (1 << w); a++) { + std->mult[a] = 0; + std->mult[a<<w] = 0; + std->div[a] = 0; + std->div[a<<w] = 0; + } + + for (a = 1; a < (1 << w); a++) { + for (b = 1; b < (1 << w); b++) { + p = gf_wgen_shift_multiply(gf, a, b); + std->mult[(a<<w)|b] = p; + std->div[(p<<w)|a] = b; + } + } + + gf->multiply.w32 = gf_wgen_table_16_multiply; + gf->divide.w32 = gf_wgen_table_16_divide; + return 1; +} + +static +int gf_wgen_table_init(gf_t *gf) +{ + gf_internal_t *h; + + h = (gf_internal_t *) gf->scratch; + if (h->w <= 8) return gf_wgen_table_8_init(gf); + if (h->w <= 14) return gf_wgen_table_16_init(gf); + + /* Returning zero to make the compiler happy, but this won't get + executed, because it is tested in _scratch_space. */ + + return 0; +} + +static +gf_val_32_t +gf_wgen_log_8_multiply(gf_t *gf, gf_val_32_t a, gf_val_32_t b) +{ + gf_internal_t *h; + struct gf_wgen_log_w8_data *std; + + h = (gf_internal_t *) gf->scratch; + std = (struct gf_wgen_log_w8_data *) h->private; + + if (a == 0 || b == 0) return 0; + return (std->anti[std->log[a]+std->log[b]]); +} + +static +gf_val_32_t +gf_wgen_log_8_divide(gf_t *gf, gf_val_32_t a, gf_val_32_t b) +{ + gf_internal_t *h; + struct gf_wgen_log_w8_data *std; + int index; + + h = (gf_internal_t *) gf->scratch; + std = (struct gf_wgen_log_w8_data *) h->private; + + if (a == 0 || b == 0) return 0; + index = std->log[a]; + index -= std->log[b]; + + return (std->danti[index]); +} + +static +int gf_wgen_log_8_init(gf_t *gf) +{ + gf_internal_t *h; + struct gf_wgen_log_w8_data *std; + int w; + uint32_t a, i; + int check = 0; + + h = (gf_internal_t *) gf->scratch; + w = h->w; + std = (struct gf_wgen_log_w8_data *) h->private; + + std->log = &(std->base); + std->anti = std->log + (1<<h->w); + std->danti = std->anti + (1<<h->w)-1; + + for (i = 0; i < (1 << w); i++) + std->log[i] = 0; + + a = 1; + for(i=0; i < (1<<w)-1; i++) + { + if (std->log[a] != 0) check = 1; + std->log[a] = i; + std->anti[i] = a; + std->danti[i] = a; + a <<= 1; + if(a & (1<<w)) + a ^= h->prim_poly; + //a &= ((1 << w)-1); + } + + if (check != 0) { + _gf_errno = GF_E_LOGPOLY; + return 0; + } + + gf->multiply.w32 = gf_wgen_log_8_multiply; + gf->divide.w32 = gf_wgen_log_8_divide; + return 1; +} + +static +gf_val_32_t +gf_wgen_log_16_multiply(gf_t *gf, gf_val_32_t a, gf_val_32_t b) +{ + gf_internal_t *h; + struct gf_wgen_log_w16_data *std; + + h = (gf_internal_t *) gf->scratch; + std = (struct gf_wgen_log_w16_data *) h->private; + + if (a == 0 || b == 0) return 0; + return (std->anti[std->log[a]+std->log[b]]); +} + +static +gf_val_32_t +gf_wgen_log_16_divide(gf_t *gf, gf_val_32_t a, gf_val_32_t b) +{ + gf_internal_t *h; + struct gf_wgen_log_w16_data *std; + int index; + + h = (gf_internal_t *) gf->scratch; + std = (struct gf_wgen_log_w16_data *) h->private; + + if (a == 0 || b == 0) return 0; + index = std->log[a]; + index -= std->log[b]; + + return (std->danti[index]); +} + +static +int gf_wgen_log_16_init(gf_t *gf) +{ + gf_internal_t *h; + struct gf_wgen_log_w16_data *std; + int w; + uint32_t a, i; + int check = 0; + + h = (gf_internal_t *) gf->scratch; + w = h->w; + std = (struct gf_wgen_log_w16_data *) h->private; + + std->log = &(std->base); + std->anti = std->log + (1<<h->w); + std->danti = std->anti + (1<<h->w)-1; + + for (i = 0; i < (1 << w); i++) + std->log[i] = 0; + + a = 1; + for(i=0; i < (1<<w)-1; i++) + { + if (std->log[a] != 0) check = 1; + std->log[a] = i; + std->anti[i] = a; + std->danti[i] = a; + a <<= 1; + if(a & (1<<w)) + a ^= h->prim_poly; + //a &= ((1 << w)-1); + } + + if (check) { + if (h->mult_type != GF_MULT_LOG_TABLE) return gf_wgen_shift_init(gf); + _gf_errno = GF_E_LOGPOLY; + return 0; + } + + gf->multiply.w32 = gf_wgen_log_16_multiply; + gf->divide.w32 = gf_wgen_log_16_divide; + return 1; +} + +static +gf_val_32_t +gf_wgen_log_32_multiply(gf_t *gf, gf_val_32_t a, gf_val_32_t b) +{ + gf_internal_t *h; + struct gf_wgen_log_w32_data *std; + + h = (gf_internal_t *) gf->scratch; + std = (struct gf_wgen_log_w32_data *) h->private; + + if (a == 0 || b == 0) return 0; + return (std->anti[std->log[a]+std->log[b]]); +} + +static +gf_val_32_t +gf_wgen_log_32_divide(gf_t *gf, gf_val_32_t a, gf_val_32_t b) +{ + gf_internal_t *h; + struct gf_wgen_log_w32_data *std; + int index; + + h = (gf_internal_t *) gf->scratch; + std = (struct gf_wgen_log_w32_data *) h->private; + + if (a == 0 || b == 0) return 0; + index = std->log[a]; + index -= std->log[b]; + + return (std->danti[index]); +} + +static +int gf_wgen_log_32_init(gf_t *gf) +{ + gf_internal_t *h; + struct gf_wgen_log_w32_data *std; + int w; + uint32_t a, i; + int check = 0; + + h = (gf_internal_t *) gf->scratch; + w = h->w; + std = (struct gf_wgen_log_w32_data *) h->private; + + std->log = &(std->base); + std->anti = std->log + (1<<h->w); + std->danti = std->anti + (1<<h->w)-1; + + for (i = 0; i < (1 << w); i++) + std->log[i] = 0; + + a = 1; + for(i=0; i < (1<<w)-1; i++) + { + if (std->log[a] != 0) check = 1; + std->log[a] = i; + std->anti[i] = a; + std->danti[i] = a; + a <<= 1; + if(a & (1<<w)) + a ^= h->prim_poly; + //a &= ((1 << w)-1); + } + + if (check != 0) { + _gf_errno = GF_E_LOGPOLY; + return 0; + } + + gf->multiply.w32 = gf_wgen_log_32_multiply; + gf->divide.w32 = gf_wgen_log_32_divide; + return 1; +} + +static +int gf_wgen_log_init(gf_t *gf) +{ + gf_internal_t *h; + + h = (gf_internal_t *) gf->scratch; + if (h->w <= 8) return gf_wgen_log_8_init(gf); + if (h->w <= 16) return gf_wgen_log_16_init(gf); + if (h->w <= 32) return gf_wgen_log_32_init(gf); + + /* Returning zero to make the compiler happy, but this won't get + executed, because it is tested in _scratch_space. */ + + return 0; +} + +int gf_wgen_scratch_size(int w, int mult_type, int region_type, int divide_type, int arg1, int arg2) +{ + + switch(mult_type) + { + case GF_MULT_DEFAULT: + if (w <= 8) { + return sizeof(gf_internal_t) + sizeof(struct gf_wgen_table_w8_data) + + sizeof(uint8_t)*(1 << w)*(1<<w)*2 + 64; + } else if (w <= 16) { + return sizeof(gf_internal_t) + sizeof(struct gf_wgen_log_w16_data) + + sizeof(uint16_t)*(1 << w)*3; + } else { + return sizeof(gf_internal_t) + sizeof(struct gf_wgen_group_data) + + sizeof(uint32_t) * (1 << 2) + + sizeof(uint32_t) * (1 << 8) + 64; + } + case GF_MULT_SHIFT: + case GF_MULT_BYTWO_b: + case GF_MULT_BYTWO_p: + return sizeof(gf_internal_t); + break; + case GF_MULT_GROUP: + return sizeof(gf_internal_t) + sizeof(struct gf_wgen_group_data) + + sizeof(uint32_t) * (1 << arg1) + + sizeof(uint32_t) * (1 << arg2) + 64; + break; + + case GF_MULT_TABLE: + if (w <= 8) { + return sizeof(gf_internal_t) + sizeof(struct gf_wgen_table_w8_data) + + sizeof(uint8_t)*(1 << w)*(1<<w)*2 + 64; + } else if (w < 15) { + return sizeof(gf_internal_t) + sizeof(struct gf_wgen_table_w16_data) + + sizeof(uint16_t)*(1 << w)*(1<<w)*2 + 64; + } + return 0; + case GF_MULT_LOG_TABLE: + if (w <= 8) { + return sizeof(gf_internal_t) + sizeof(struct gf_wgen_log_w8_data) + + sizeof(uint8_t)*(1 << w)*3; + } else if (w <= 16) { + return sizeof(gf_internal_t) + sizeof(struct gf_wgen_log_w16_data) + + sizeof(uint16_t)*(1 << w)*3; + } else if (w <= 27) { + return sizeof(gf_internal_t) + sizeof(struct gf_wgen_log_w32_data) + + sizeof(uint32_t)*(1 << w)*3; + } else + return 0; + default: + return 0; + } +} + +void +gf_wgen_cauchy_region(gf_t *gf, void *src, void *dest, gf_val_32_t val, int bytes, int xor) +{ + gf_internal_t *h; + gf_region_data rd; + int written; + int rs, i, j; + + gf_set_region_data(&rd, gf, src, dest, bytes, val, xor, -1); + + if (val == 0) { gf_multby_zero(dest, bytes, xor); return; } + if (val == 1) { gf_multby_one(src, dest, bytes, xor); return; } + + h = (gf_internal_t *) gf->scratch; + rs = bytes / (h->w); + + written = (xor) ? 0xffffffff : 0; + for (i = 0; i < h->w; i++) { + for (j = 0; j < h->w; j++) { + if (val & (1 << j)) { + gf_multby_one(src, ((uint8_t *)dest) + j*rs, rs, (written & (1 << j))); + written |= (1 << j); + } + } + src = (uint8_t *)src + rs; + val = gf->multiply.w32(gf, val, 2); + } +} + +int gf_wgen_init(gf_t *gf) +{ + gf_internal_t *h; + + h = (gf_internal_t *) gf->scratch; + if (h->prim_poly == 0) { + switch (h->w) { + case 1: h->prim_poly = 1; break; + case 2: h->prim_poly = 7; break; + case 3: h->prim_poly = 013; break; + case 4: h->prim_poly = 023; break; + case 5: h->prim_poly = 045; break; + case 6: h->prim_poly = 0103; break; + case 7: h->prim_poly = 0211; break; + case 8: h->prim_poly = 0435; break; + case 9: h->prim_poly = 01021; break; + case 10: h->prim_poly = 02011; break; + case 11: h->prim_poly = 04005; break; + case 12: h->prim_poly = 010123; break; + case 13: h->prim_poly = 020033; break; + case 14: h->prim_poly = 042103; break; + case 15: h->prim_poly = 0100003; break; + case 16: h->prim_poly = 0210013; break; + case 17: h->prim_poly = 0400011; break; + case 18: h->prim_poly = 01000201; break; + case 19: h->prim_poly = 02000047; break; + case 20: h->prim_poly = 04000011; break; + case 21: h->prim_poly = 010000005; break; + case 22: h->prim_poly = 020000003; break; + case 23: h->prim_poly = 040000041; break; + case 24: h->prim_poly = 0100000207; break; + case 25: h->prim_poly = 0200000011; break; + case 26: h->prim_poly = 0400000107; break; + case 27: h->prim_poly = 01000000047; break; + case 28: h->prim_poly = 02000000011; break; + case 29: h->prim_poly = 04000000005; break; + case 30: h->prim_poly = 010040000007; break; + case 31: h->prim_poly = 020000000011; break; + case 32: h->prim_poly = 00020000007; break; + default: fprintf(stderr, "gf_wgen_init: w not defined yet\n"); exit(1); + } + } else { + if (h->w == 32) { + h->prim_poly &= 0xffffffff; + } else { + h->prim_poly |= (1 << h->w); + if (h->prim_poly & ~((1ULL<<(h->w+1))-1)) return 0; + } + } + + gf->multiply.w32 = NULL; + gf->divide.w32 = NULL; + gf->inverse.w32 = NULL; + gf->multiply_region.w32 = gf_wgen_cauchy_region; + gf->extract_word.w32 = gf_wgen_extract_word; + + switch(h->mult_type) { + case GF_MULT_DEFAULT: + if (h->w <= 8) { + if (gf_wgen_table_init(gf) == 0) return 0; + } else if (h->w <= 16) { + if (gf_wgen_log_init(gf) == 0) return 0; + } else { + if (gf_wgen_bytwo_p_init(gf) == 0) return 0; + } + break; + case GF_MULT_SHIFT: if (gf_wgen_shift_init(gf) == 0) return 0; break; + case GF_MULT_BYTWO_b: if (gf_wgen_bytwo_b_init(gf) == 0) return 0; break; + case GF_MULT_BYTWO_p: if (gf_wgen_bytwo_p_init(gf) == 0) return 0; break; + case GF_MULT_GROUP: if (gf_wgen_group_init(gf) == 0) return 0; break; + case GF_MULT_TABLE: if (gf_wgen_table_init(gf) == 0) return 0; break; + case GF_MULT_LOG_TABLE: if (gf_wgen_log_init(gf) == 0) return 0; break; + default: return 0; + } + if (h->divide_type == GF_DIVIDE_EUCLID) { + gf->divide.w32 = gf_wgen_divide_from_inverse; + gf->inverse.w32 = gf_wgen_euclid; + } else if (h->divide_type == GF_DIVIDE_MATRIX) { + gf->divide.w32 = gf_wgen_divide_from_inverse; + gf->inverse.w32 = gf_wgen_matrix; + } + + if (gf->inverse.w32== NULL && gf->divide.w32 == NULL) gf->inverse.w32 = gf_wgen_euclid; + + if (gf->inverse.w32 != NULL && gf->divide.w32 == NULL) { + gf->divide.w32 = gf_wgen_divide_from_inverse; + } + if (gf->inverse.w32 == NULL && gf->divide.w32 != NULL) { + gf->inverse.w32 = gf_wgen_inverse_from_divide; + } + return 1; +} |