userapps/opensource/sshd/libtommath/etclib/poly.c

   1 /* LibTomMath, multiple-precision integer library -- Tom St Denis
   2  *
   3  * LibTomMath is library that provides for multiple-precision
   4  * integer arithmetic as well as number theoretic functionality.
   5  *
   6  * This file "poly.c" provides GF(p^k) functionality on top of the
   7  * libtommath library.
   8  *
   9  * The library is designed directly after the MPI library by
  10  * Michael Fromberger but has been written from scratch with
  11  * additional optimizations in place.
  12  *
  13  * The library is free for all purposes without any express
  14  * guarantee it works.
  15  *
  16  * Tom St Denis, tomstdenis@iahu.ca, http://libtommath.iahu.ca
  17  */
  18 #include "poly.h"
  19
  20 #undef MIN
  21 #define MIN(x,y) ((x)<(y)?(x):(y))
  22 #undef MAX
  23 #define MAX(x,y) ((x)>(y)?(x):(y))
  24
  25 static void s_free(mp_poly *a)
  26 {
  27    int k;
  28    for (k = 0; k < a->alloc; k++) {
  29        mp_clear(&(a->co[k]));
  30    }
  31 }
  32
  33 static int s_setup(mp_poly *a, int low, int high)
  34 {
  35    int res, k, j;
  36    for (k = low; k < high; k++) {
  37        if ((res = mp_init(&(a->co[k]))) != MP_OKAY) {
  38           for (j = low; j < k; j++) {
  39              mp_clear(&(a->co[j]));
  40           }
  41           return MP_MEM;
  42        }
  43    }
  44    return MP_OKAY;
  45 }
  46
  47 int mp_poly_init(mp_poly *a, mp_int *cha)
  48 {
  49    return mp_poly_init_size(a, cha, MP_POLY_PREC);
  50 }
  51
  52 /* init a poly of a given (size) degree */
  53 int mp_poly_init_size(mp_poly *a, mp_int *cha, int size)
  54 {
  55    int res;
  56
  57    /* allocate array of mp_ints for coefficients */
  58    a->co = malloc(size * sizeof(mp_int));
  59    if (a->co == NULL) {
  60       return MP_MEM;
  61    }
  62    a->used  = 0;
  63    a->alloc = size;
  64
  65    /* now init the range */
  66    if ((res = s_setup(a, 0, size)) != MP_OKAY) {
  67       free(a->co);
  68       return res;
  69    }
  70
  71    /* copy characteristic */
  72    if ((res = mp_init_copy(&(a->cha), cha)) != MP_OKAY) {
  73       s_free(a);
  74       free(a->co);
  75       return res;
  76    }
  77
  78    /* return ok at this point */
  79    return MP_OKAY;
  80 }
  81
  82 /* grow the size of a poly */
  83 static int mp_poly_grow(mp_poly *a, int size)
  84 {
  85   int res;
  86
  87   if (size > a->alloc) {
  88      /* resize the array of coefficients */
  89      a->co = realloc(a->co, sizeof(mp_int) * size);
  90      if (a->co == NULL) {
  91         return MP_MEM;
  92      }
  93
  94      /* now setup the coefficients */
  95      if ((res = s_setup(a, a->alloc, a->alloc + size)) != MP_OKAY) {
  96         return res;
  97      }
  98
  99      a->alloc += size;
 100   }
 101   return MP_OKAY;
 102 }
 103
 104 /* copy, b = a */
 105 int mp_poly_copy(mp_poly *a, mp_poly *b)
 106 {
 107    int res, k;
 108
 109    /* resize b */
 110    if ((res = mp_poly_grow(b, a->used)) != MP_OKAY) {
 111       return res;
 112    }
 113
 114    /* now copy the used part */
 115    b->used = a->used;
 116
 117    /* now the cha */
 118    if ((res = mp_copy(&(a->cha), &(b->cha))) != MP_OKAY) {
 119       return res;
 120    }
 121
 122    /* now all the coefficients */
 123    for (k = 0; k < b->used; k++) {
 124        if ((res = mp_copy(&(a->co[k]), &(b->co[k]))) != MP_OKAY) {
 125           return res;
 126        }
 127    }
 128
 129    /* now zero the top */
 130    for (k = b->used; k < b->alloc; k++) {
 131        mp_zero(&(b->co[k]));
 132    }
 133
 134    return MP_OKAY;
 135 }
 136
 137 /* init from a copy, a = b */
 138 int mp_poly_init_copy(mp_poly *a, mp_poly *b)
 139 {
 140    int res;
 141
 142    if ((res = mp_poly_init(a, &(b->cha))) != MP_OKAY) {
 143       return res;
 144    }
 145    return mp_poly_copy(b, a);
 146 }
 147
 148 /* free a poly from ram */
 149 void mp_poly_clear(mp_poly *a)
 150 {
 151    s_free(a);
 152    mp_clear(&(a->cha));
 153    free(a->co);
 154
 155    a->co = NULL;
 156    a->used = a->alloc = 0;
 157 }
 158
 159 /* exchange two polys */
 160 void mp_poly_exch(mp_poly *a, mp_poly *b)
 161 {
 162    mp_poly t;
 163    t = *a; *a = *b; *b = t;
 164 }
 165
 166 /* clamp the # of used digits */
 167 static void mp_poly_clamp(mp_poly *a)
 168 {
 169    while (a->used > 0 && mp_cmp_d(&(a->co[a->used]), 0) == MP_EQ) --(a->used);
 170 }
 171
 172 /* add two polynomials, c(x) = a(x) + b(x) */
 173 int mp_poly_add(mp_poly *a, mp_poly *b, mp_poly *c)
 174 {
 175    mp_poly t, *x, *y;
 176    int res, k;
 177
 178    /* ensure char's are the same */
 179    if (mp_cmp(&(a->cha), &(b->cha)) != MP_EQ) {
 180       return MP_VAL;
 181    }
 182
 183    /* now figure out the sizes such that x is the
 184       largest degree poly and y is less or equal in degree
 185     */
 186    if (a->used > b->used) {
 187       x = a;
 188       y = b;
 189    } else {
 190       x = b;
 191       y = a;
 192    }
 193
 194    /* now init the result to be a copy of the largest */
 195    if ((res = mp_poly_init_copy(&t, x)) != MP_OKAY) {
 196       return res;
 197    }
 198
 199    /* now add the coeffcients of the smaller one */
 200    for (k = 0; k < y->used; k++) {
 201        if ((res = mp_addmod(&(a->co[k]), &(b->co[k]), &(a->cha), &(t.co[k]))) != MP_OKAY) {
 202           goto __T;
 203        }
 204    }
 205
 206    mp_poly_clamp(&t);
 207    mp_poly_exch(&t, c);
 208    res = MP_OKAY;
 209
 210 __T:  mp_poly_clear(&t);
 211    return res;
 212 }
 213
 214 /* subtracts two polynomials, c(x) = a(x) - b(x) */
 215 int mp_poly_sub(mp_poly *a, mp_poly *b, mp_poly *c)
 216 {
 217    mp_poly t, *x, *y;
 218    int res, k;
 219
 220    /* ensure char's are the same */
 221    if (mp_cmp(&(a->cha), &(b->cha)) != MP_EQ) {
 222       return MP_VAL;
 223    }
 224
 225    /* now figure out the sizes such that x is the
 226       largest degree poly and y is less or equal in degree
 227     */
 228    if (a->used > b->used) {
 229       x = a;
 230       y = b;
 231    } else {
 232       x = b;
 233       y = a;
 234    }
 235
 236    /* now init the result to be a copy of the largest */
 237    if ((res = mp_poly_init_copy(&t, x)) != MP_OKAY) {
 238       return res;
 239    }
 240
 241    /* now add the coeffcients of the smaller one */
 242    for (k = 0; k < y->used; k++) {
 243        if ((res = mp_submod(&(a->co[k]), &(b->co[k]), &(a->cha), &(t.co[k]))) != MP_OKAY) {
 244           goto __T;
 245        }
 246    }
 247
 248    mp_poly_clamp(&t);
 249    mp_poly_exch(&t, c);
 250    res = MP_OKAY;
 251
 252 __T:  mp_poly_clear(&t);
 253    return res;
 254 }
 255
 256 /* multiplies two polynomials, c(x) = a(x) * b(x) */
 257 int mp_poly_mul(mp_poly *a, mp_poly *b, mp_poly *c)
 258 {
 259    mp_poly t;
 260    mp_int  tt;
 261    int res, pa, pb, ix, iy;
 262
 263    /* ensure char's are the same */
 264    if (mp_cmp(&(a->cha), &(b->cha)) != MP_EQ) {
 265       return MP_VAL;
 266    }
 267
 268    /* degrees of a and b */
 269    pa = a->used;
 270    pb = b->used;
 271
 272    /* now init the temp polynomial to be of degree pa+pb */
 273    if ((res = mp_poly_init_size(&t, &(a->cha), pa+pb)) != MP_OKAY) {
 274       return res;
 275    }
 276
 277    /* now init our temp int */
 278    if ((res = mp_init(&tt)) != MP_OKAY) {
 279       goto __T;
 280    }
 281
 282    /* now loop through all the digits */
 283    for (ix = 0; ix < pa; ix++) {
 284        for (iy = 0; iy < pb; iy++) {
 285           if ((res = mp_mul(&(a->co[ix]), &(b->co[iy]), &tt)) != MP_OKAY) {
 286              goto __TT;
 287           }
 288           if ((res = mp_addmod(&tt, &(t.co[ix+iy]), &(a->cha), &(t.co[ix+iy]))) != MP_OKAY) {
 289              goto __TT;
 290           }
 291        }
 292    }
 293
 294    mp_poly_clamp(&t);
 295    mp_poly_exch(&t, c);
 296    res = MP_OKAY;
 297
 298 __TT: mp_clear(&tt);
 299 __T:  mp_poly_clear(&t);
 300    return res;
 301 }
 302