00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021 #include <stdio.h>
00022 #include <stdlib.h>
00023 #include <string.h>
00024
00025 #include "gf.h"
00026 #include "poly.h"
00027
00028
00030
00031
00032 poly_t poly_alloc(int d) {
00033 poly_t p;
00034
00035 p = (poly_t) malloc(sizeof (struct polynome));
00036 p->deg = -1;
00037 p->size = d + 1;
00038 p->coeff = (gf_t *) calloc(p->size, sizeof (gf_t));
00039 return p;
00040 }
00041
00042
00043 poly_t poly_alloc_from_string(int d, const unsigned char * s) {
00044 poly_t p;
00045
00046 p = (poly_t) malloc(sizeof (struct polynome));
00047 p->deg = -1;
00048 p->size = d + 1;
00049 p->coeff = (gf_t *) s;
00050 return p;
00051 }
00052
00053 poly_t poly_copy(poly_t p) {
00054 poly_t q;
00055
00056 q = (poly_t) malloc(sizeof (struct polynome));
00057 q->deg = p->deg;
00058 q->size = p->size;
00059 q->coeff = (gf_t *) calloc(q->size, sizeof (gf_t));
00060 memcpy(q->coeff, p->coeff, p->size * sizeof (gf_t));
00061 return q;
00062 }
00063
00064 void poly_free(poly_t p) {
00065 free(p->coeff);
00066 free(p);
00067 }
00068
00069 void poly_set_to_zero(poly_t p) {
00070 memset(p->coeff, 0, p->size * sizeof (gf_t));
00071 p->deg = -1;
00072 }
00073
00074 int poly_calcule_deg(poly_t p) {
00075 int d = p->size - 1;
00076 while ((d >= 0) && (p->coeff[d] == gf_zero()))
00077 --d;
00078 p->deg = d;
00079 return d;
00080 }
00081
00082
00083 void poly_set(poly_t p, poly_t q) {
00084 int d = p->size - q->size;
00085 if (d < 0) {
00086 memcpy(p->coeff, q->coeff, p->size * sizeof (gf_t));
00087 poly_calcule_deg(p);
00088 }
00089 else {
00090 memcpy(p->coeff, q->coeff, q->size * sizeof (gf_t));
00091 memset(p->coeff + q->size, 0, d * sizeof (gf_t));
00092 p->deg = q->deg;
00093 }
00094 }
00095
00096 gf_t poly_eval_aux(gf_t * coeff, gf_t a, int d) {
00097 gf_t b;
00098
00099 b = coeff[d--];
00100 for (; d >= 0; --d)
00101 if (b != gf_zero())
00102 b = gf_add(gf_mul(b, a), coeff[d]);
00103 else
00104 b = coeff[d];
00105 return b;
00106 }
00107
00108 poly_t poly_mul(poly_t p, poly_t q) {
00109 int i,j,dp,dq;
00110 poly_t r;
00111
00112 poly_calcule_deg(p);
00113 poly_calcule_deg(q);
00114 dp = poly_deg(p);
00115 dq = poly_deg(q);
00116 r=poly_alloc(dp+dq);
00117 for (i = 0; i <= dp; ++i)
00118 for (j = 0; j <= dq; ++j)
00119 poly_addto_coeff(r,i+j,gf_mul(poly_coeff(p,i),poly_coeff(q,j)));
00120 poly_calcule_deg(r);
00121
00122 return(r);
00123 }
00124
00125 gf_t poly_eval(poly_t p, gf_t a) {
00126 return poly_eval_aux(p->coeff, a, poly_deg(p));
00127 }
00128
00129
00130 void poly_rem(poly_t p, poly_t g) {
00131 int i, j, d;
00132 gf_t a, b;
00133
00134 d = poly_deg(p) - poly_deg(g);
00135 if (d >= 0) {
00136 a = gf_inv(poly_tete(g));
00137 for (i = poly_deg(p); d >= 0; --i, --d) {
00138 if (poly_coeff(p, i) != gf_zero()) {
00139 b = gf_mul_fast(a, poly_coeff(p, i));
00140 for (j = 0; j < poly_deg(g); ++j)
00141 poly_addto_coeff(p, j + d, gf_mul_fast(b, poly_coeff(g, j)));
00142 poly_set_coeff(p, i, gf_zero());
00143 }
00144 }
00145 poly_set_deg(p, poly_deg(g) - 1);
00146 while ((poly_deg(p) >= 0) && (poly_coeff(p, poly_deg(p)) == gf_zero()))
00147 poly_set_deg(p, poly_deg(p) - 1);
00148 }
00149 }
00150
00151 void poly_sqmod_init(poly_t g, poly_t * sq) {
00152 int i, d;
00153
00154 d = poly_deg(g);
00155
00156 for (i = 0; i < d / 2; ++i) {
00157
00158 poly_set_to_zero(sq[i]);
00159 poly_set_deg(sq[i], 2 * i);
00160 poly_set_coeff(sq[i], 2 * i, gf_unit());
00161 }
00162
00163 for (; i < d; ++i) {
00164
00165 memset(sq[i]->coeff, 0, 2 * sizeof (gf_t));
00166 memcpy(sq[i]->coeff + 2, sq[i - 1]->coeff, d * sizeof (gf_t));
00167 poly_set_deg(sq[i], poly_deg(sq[i - 1]) + 2);
00168 poly_rem(sq[i], g);
00169 }
00170 }
00171
00172
00173
00174
00175
00176 void poly_sqmod(poly_t res, poly_t p, poly_t * sq, int d) {
00177 int i, j;
00178 gf_t a;
00179
00180 poly_set_to_zero(res);
00181
00182
00183 for (i = 0; i < d / 2; ++i)
00184 poly_set_coeff(res, i * 2, gf_square(poly_coeff(p, i)));
00185
00186
00187 for (; i < d; ++i) {
00188 if (poly_coeff(p, i) != gf_zero()) {
00189 a = gf_square(poly_coeff(p, i));
00190 for (j = 0; j < d; ++j)
00191 poly_addto_coeff(res, j, gf_mul_fast(a, poly_coeff(sq[i], j)));
00192 }
00193 }
00194
00195
00196 poly_set_deg(res, d - 1);
00197 while ((poly_deg(res) >= 0) && (poly_coeff(res, poly_deg(res)) == gf_zero()))
00198 poly_set_deg(res, poly_deg(res) - 1);
00199 }
00200
00201
00202 poly_t poly_gcd_aux(poly_t p1, poly_t p2) {
00203 if (poly_deg(p2) == -1)
00204 return p1;
00205 else {
00206 poly_rem(p1, p2);
00207 return poly_gcd_aux(p2, p1);
00208 }
00209 }
00210
00211 poly_t poly_gcd(poly_t p1, poly_t p2) {
00212 poly_t a, b, c;
00213
00214 a = poly_copy(p1);
00215 b = poly_copy(p2);
00216 if (poly_deg(a) < poly_deg(b))
00217 c = poly_copy(poly_gcd_aux(b, a));
00218 else
00219 c = poly_copy(poly_gcd_aux(a, b));
00220 poly_free(a);
00221 poly_free(b);
00222 return c;
00223 }
00224
00225 poly_t poly_quo(poly_t p, poly_t d) {
00226 int i, j, dd, dp;
00227 gf_t a, b;
00228 poly_t quo, rem;
00229
00230 dd = poly_calcule_deg(d);
00231 dp = poly_calcule_deg(p);
00232 rem = poly_copy(p);
00233 quo = poly_alloc(dp - dd);
00234 poly_set_deg(quo, dp - dd);
00235 a = gf_inv(poly_coeff(d, dd));
00236 for (i = dp; i >= dd; --i) {
00237 b = gf_mul_fast(a, poly_coeff(rem, i));
00238 poly_set_coeff(quo, i - dd, b);
00239 if (b != gf_zero()) {
00240 poly_set_coeff(rem, i, gf_zero());
00241 for (j = i - 1; j >= i - dd; --j)
00242 poly_addto_coeff(rem, j, gf_mul_fast(b, poly_coeff(d, dd - i + j)));
00243 }
00244 }
00245 poly_free(rem);
00246
00247 return quo;
00248 }
00249
00250
00251 int poly_degppf(poly_t g) {
00252 int i, d, res;
00253 poly_t *u, p, r, s;
00254
00255 d = poly_deg(g);
00256 u = malloc(d * sizeof (poly_t *));
00257 for (i = 0; i < d; ++i)
00258 u[i] = poly_alloc(d + 1);
00259 poly_sqmod_init(g, u);
00260
00261 p = poly_alloc(d - 1);
00262 poly_set_deg(p, 1);
00263 poly_set_coeff(p, 1, gf_unit());
00264 r = poly_alloc(d - 1);
00265 res = d;
00266 for (i = 1; i <= (d / 2) * gf_extd(); ++i) {
00267 poly_sqmod(r, p, u, d);
00268
00269 if ((i % gf_extd()) == 0) {
00270 poly_addto_coeff(r, 1, gf_unit());
00271 poly_calcule_deg(r);
00272 s = poly_gcd(g, r);
00273 if (poly_deg(s) > 0) {
00274 poly_free(s);
00275 res = i / gf_extd();
00276 break;
00277 }
00278 poly_free(s);
00279 poly_addto_coeff(r, 1, gf_unit());
00280 poly_calcule_deg(r);
00281 }
00282
00283 s = p;
00284 p = r;
00285 r = s;
00286 }
00287
00288 poly_free(p);
00289 poly_free(r);
00290 for (i = 0; i < d; ++i) {
00291 poly_free(u[i]);
00292 }
00293 free(u);
00294
00295 return res;
00296 }
00297
00298
00299 void poly_eeaux(poly_t * u, poly_t * v, poly_t p, poly_t g, int t) {
00300 int i, j, dr, du, delta;
00301 gf_t a;
00302 poly_t aux, r0, r1, u0, u1;
00303
00304
00305
00306 dr = poly_deg(g);
00307
00308 r0 = poly_alloc(dr);
00309 r1 = poly_alloc(dr - 1);
00310 u0 = poly_alloc(dr - 1);
00311 u1 = poly_alloc(dr - 1);
00312 poly_set(r0, g);
00313 poly_set(r1, p);
00314 poly_set_to_zero(u0);
00315 poly_set_to_zero(u1);
00316 poly_set_coeff(u1, 0, gf_unit());
00317 poly_set_deg(u1, 0);
00318
00319
00320
00321
00322
00323
00324
00325 du = 0;
00326 dr = poly_deg(r1);
00327 delta = poly_deg(r0) - dr;
00328
00329 while (dr >= t) {
00330 for (j = delta; j >= 0; --j) {
00331 a = gf_div(poly_coeff(r0, dr + j), poly_coeff(r1, dr));
00332 if (a != gf_zero()) {
00333
00334 for (i = 0; i <= du; ++i){
00335 poly_addto_coeff(u0, i + j, gf_mul_fast(a, poly_coeff(u1, i)));
00336 }
00337
00338 for (i = 0; i <= dr; ++i)
00339 poly_addto_coeff(r0, i + j, gf_mul_fast(a, poly_coeff(r1, i)));
00340 }
00341 }
00342
00343 aux = r0; r0 = r1; r1 = aux;
00344 aux = u0; u0 = u1; u1 = aux;
00345
00346 du = du + delta;
00347 delta = 1;
00348 while (poly_coeff(r1, dr - delta) == gf_zero())
00349 delta++;
00350 dr -= delta;
00351 }
00352
00353 poly_set_deg(u1, du);
00354 poly_set_deg(r1, dr);
00355
00356 *u=u1;
00357 *v=r1;
00358
00359 poly_free(r0);
00360 poly_free(u0);
00361 }
00362
00363
00364
00365 poly_t poly_randgen_irred(int t, int (*u8rnd)()) {
00366 int i;
00367 poly_t g;
00368
00369 g = poly_alloc(t);
00370 poly_set_deg(g, t);
00371 poly_set_coeff(g, t, gf_unit());
00372
00373 i = 0;
00374 do
00375 for (i = 0; i < t; ++i)
00376 poly_set_coeff(g, i, gf_rand(u8rnd));
00377 while (poly_degppf(g) < t);
00378
00379 return g;
00380 }
00381
00382
00383
00384
00385 void poly_shiftmod(poly_t p, poly_t g) {
00386 int i, t;
00387 gf_t a;
00388
00389 t = poly_deg(g);
00390 a = gf_div(p->coeff[t-1], g->coeff[t]);
00391 for (i = t - 1; i > 0; --i)
00392 p->coeff[i] = gf_add(p->coeff[i - 1], gf_mul(a, g->coeff[i]));
00393 p->coeff[0] = gf_mul(a, g->coeff[0]);
00394 }
00395
00396 poly_t * poly_sqrtmod_init(poly_t g) {
00397 int i, t;
00398 poly_t * sqrt, aux, p, q, * sq_aux;
00399
00400 t = poly_deg(g);
00401
00402 sq_aux = malloc(t * sizeof (poly_t));
00403 for (i = 0; i < t; ++i)
00404 sq_aux[i] = poly_alloc(t + 1);
00405 poly_sqmod_init(g, sq_aux);
00406
00407 q = poly_alloc(t - 1);
00408 p = poly_alloc(t - 1);
00409 poly_set_deg(p, 1);
00410
00411 poly_set_coeff(p, 1, gf_unit());
00412
00413 for (i = 0; i < t * gf_extd() - 1; ++i) {
00414
00415 poly_sqmod(q, p, sq_aux, t);
00416
00417 aux = q; q = p; p = aux;
00418 }
00419
00420
00421 sqrt = malloc(t * sizeof (poly_t));
00422 for (i = 0; i < t; ++i)
00423 sqrt[i] = poly_alloc(t - 1);
00424
00425 poly_set(sqrt[1], p);
00426 poly_calcule_deg(sqrt[1]);
00427 for(i = 3; i < t; i += 2) {
00428 poly_set(sqrt[i], sqrt[i - 2]);
00429 poly_shiftmod(sqrt[i], g);
00430 poly_calcule_deg(sqrt[i]);
00431 }
00432
00433 for (i = 0; i < t; i += 2) {
00434 poly_set_to_zero(sqrt[i]);
00435 sqrt[i]->coeff[i / 2] = gf_unit();
00436 sqrt[i]->deg = i / 2;
00437 }
00438
00439 for (i = 0; i < t; ++i)
00440 poly_free(sq_aux[i]);
00441 free(sq_aux);
00442 poly_free(p);
00443 poly_free(q);
00444
00445 return sqrt;
00446 }
00447
00448 poly_t * poly_syndrome_init(poly_t generator, gf_t *support, int n)
00449 {
00450 int i,j,t;
00451 gf_t a;
00452 poly_t * F;
00453
00454 F = malloc(n * sizeof (poly_t));
00455 t = poly_deg(generator);
00456
00457
00458
00459
00460 for(j=0;j<n;j++)
00461 {
00462 F[j] = poly_alloc(t-1);
00463 poly_set_coeff(F[j],t-1,gf_unit());
00464 for(i=t-2;i>=0;i--)
00465 {
00466 poly_set_coeff(F[j],i,gf_add(poly_coeff(generator,i+1),
00467 gf_mul(support[j],poly_coeff(F[j],i+1))));
00468 }
00469 a = gf_add(poly_coeff(generator,0),gf_mul(support[j],poly_coeff(F[j],0)));
00470 for(i=0;i<t;i++)
00471 {
00472 poly_set_coeff(F[j],i, gf_div(poly_coeff(F[j],i),a));
00473 }
00474 }
00475
00476 return F;
00477 }