usr/src/common/mpi/mp_gf2m.c

   1 /*
   2  * ***** BEGIN LICENSE BLOCK *****
   3  * Version: MPL 1.1/GPL 2.0/LGPL 2.1
   4  *
   5  * The contents of this file are subject to the Mozilla Public License Version
   6  * 1.1 (the "License"); you may not use this file except in compliance with
   7  * the License. You may obtain a copy of the License at
   8  * http://www.mozilla.org/MPL/
   9  *
  10  * Software distributed under the License is distributed on an "AS IS" basis,
  11  * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
  12  * for the specific language governing rights and limitations under the
  13  * License.
  14  *
  15  * The Original Code is the Multi-precision Binary Polynomial Arithmetic Library.
  16  *
  17  * The Initial Developer of the Original Code is
  18  * Sun Microsystems, Inc.
  19  * Portions created by the Initial Developer are Copyright (C) 2003
  20  * the Initial Developer. All Rights Reserved.
  21  *
  22  * Contributor(s):
  23  *   Sheueling Chang Shantz <sheueling.chang@sun.com> and
  24  *   Douglas Stebila <douglas@stebila.ca> of Sun Laboratories.
  25  *
  26  * Alternatively, the contents of this file may be used under the terms of
  27  * either the GNU General Public License Version 2 or later (the "GPL"), or
  28  * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
  29  * in which case the provisions of the GPL or the LGPL are applicable instead
  30  * of those above. If you wish to allow use of your version of this file only
  31  * under the terms of either the GPL or the LGPL, and not to allow others to
  32  * use your version of this file under the terms of the MPL, indicate your
  33  * decision by deleting the provisions above and replace them with the notice
  34  * and other provisions required by the GPL or the LGPL. If you do not delete
  35  * the provisions above, a recipient may use your version of this file under
  36  * the terms of any one of the MPL, the GPL or the LGPL.
  37  *
  38  * ***** END LICENSE BLOCK ***** */
  39 /*
  40  * Copyright 2007 Sun Microsystems, Inc.  All rights reserved.
  41  * Use is subject to license terms.
  42  *
  43  * Sun elects to use this software under the MPL license.
  44  */
  45
  46 #pragma ident   "%Z%%M% %I%     %E% SMI"
  47
  48 #include "mp_gf2m.h"
  49 #include "mp_gf2m-priv.h"
  50 #include "mplogic.h"
  51 #include "mpi-priv.h"
  52
  53 const mp_digit mp_gf2m_sqr_tb[16] =
  54 {
  55       0,     1,     4,     5,    16,    17,    20,    21,
  56      64,    65,    68,    69,    80,    81,    84,    85
  57 };
  58
  59 /* Multiply two binary polynomials mp_digits a, b.
  60  * Result is a polynomial with degree < 2 * MP_DIGIT_BITS - 1.
  61  * Output in two mp_digits rh, rl.
  62  */
  63 #if MP_DIGIT_BITS == 32
  64 void
  65 s_bmul_1x1(mp_digit *rh, mp_digit *rl, const mp_digit a, const mp_digit b)
  66 {
  67     register mp_digit h, l, s;
  68     mp_digit tab[8], top2b = a >> 30;
  69     register mp_digit a1, a2, a4;
  70
  71     a1 = a & (0x3FFFFFFF); a2 = a1 << 1; a4 = a2 << 1;
  72
  73     tab[0] =  0; tab[1] = a1;    tab[2] = a2;    tab[3] = a1^a2;
  74     tab[4] = a4; tab[5] = a1^a4; tab[6] = a2^a4; tab[7] = a1^a2^a4;
  75
  76     s = tab[b       & 0x7]; l  = s;
  77     s = tab[b >>  3 & 0x7]; l ^= s <<  3; h  = s >> 29;
  78     s = tab[b >>  6 & 0x7]; l ^= s <<  6; h ^= s >> 26;
  79     s = tab[b >>  9 & 0x7]; l ^= s <<  9; h ^= s >> 23;
  80     s = tab[b >> 12 & 0x7]; l ^= s << 12; h ^= s >> 20;
  81     s = tab[b >> 15 & 0x7]; l ^= s << 15; h ^= s >> 17;
  82     s = tab[b >> 18 & 0x7]; l ^= s << 18; h ^= s >> 14;
  83     s = tab[b >> 21 & 0x7]; l ^= s << 21; h ^= s >> 11;
  84     s = tab[b >> 24 & 0x7]; l ^= s << 24; h ^= s >>  8;
  85     s = tab[b >> 27 & 0x7]; l ^= s << 27; h ^= s >>  5;
  86     s = tab[b >> 30      ]; l ^= s << 30; h ^= s >>  2;
  87
  88     /* compensate for the top two bits of a */
  89
  90     if (top2b & 01) { l ^= b << 30; h ^= b >> 2; }
  91     if (top2b & 02) { l ^= b << 31; h ^= b >> 1; }
  92
  93     *rh = h; *rl = l;
  94 }
  95 #else
  96 void
  97 s_bmul_1x1(mp_digit *rh, mp_digit *rl, const mp_digit a, const mp_digit b)
  98 {
  99     register mp_digit h, l, s;
 100     mp_digit tab[16], top3b = a >> 61;
 101     register mp_digit a1, a2, a4, a8;
 102
 103     a1 = a & (0x1FFFFFFFFFFFFFFFULL); a2 = a1 << 1;
 104     a4 = a2 << 1; a8 = a4 << 1;
 105     tab[ 0] = 0;     tab[ 1] = a1;       tab[ 2] = a2;       tab[ 3] = a1^a2;
 106     tab[ 4] = a4;    tab[ 5] = a1^a4;    tab[ 6] = a2^a4;    tab[ 7] = a1^a2^a4;
 107     tab[ 8] = a8;    tab[ 9] = a1^a8;    tab[10] = a2^a8;    tab[11] = a1^a2^a8;
 108     tab[12] = a4^a8; tab[13] = a1^a4^a8; tab[14] = a2^a4^a8; tab[15] = a1^a2^a4^a8;
 109
 110     s = tab[b       & 0xF]; l  = s;
 111     s = tab[b >>  4 & 0xF]; l ^= s <<  4; h  = s >> 60;
 112     s = tab[b >>  8 & 0xF]; l ^= s <<  8; h ^= s >> 56;
 113     s = tab[b >> 12 & 0xF]; l ^= s << 12; h ^= s >> 52;
 114     s = tab[b >> 16 & 0xF]; l ^= s << 16; h ^= s >> 48;
 115     s = tab[b >> 20 & 0xF]; l ^= s << 20; h ^= s >> 44;
 116     s = tab[b >> 24 & 0xF]; l ^= s << 24; h ^= s >> 40;
 117     s = tab[b >> 28 & 0xF]; l ^= s << 28; h ^= s >> 36;
 118     s = tab[b >> 32 & 0xF]; l ^= s << 32; h ^= s >> 32;
 119     s = tab[b >> 36 & 0xF]; l ^= s << 36; h ^= s >> 28;
 120     s = tab[b >> 40 & 0xF]; l ^= s << 40; h ^= s >> 24;
 121     s = tab[b >> 44 & 0xF]; l ^= s << 44; h ^= s >> 20;
 122     s = tab[b >> 48 & 0xF]; l ^= s << 48; h ^= s >> 16;
 123     s = tab[b >> 52 & 0xF]; l ^= s << 52; h ^= s >> 12;
 124     s = tab[b >> 56 & 0xF]; l ^= s << 56; h ^= s >>  8;
 125     s = tab[b >> 60      ]; l ^= s << 60; h ^= s >>  4;
 126
 127     /* compensate for the top three bits of a */
 128
 129     if (top3b & 01) { l ^= b << 61; h ^= b >> 3; }
 130     if (top3b & 02) { l ^= b << 62; h ^= b >> 2; }
 131     if (top3b & 04) { l ^= b << 63; h ^= b >> 1; }
 132
 133     *rh = h; *rl = l;
 134 }
 135 #endif
 136
 137 /* Compute xor-multiply of two binary polynomials  (a1, a0) x (b1, b0)
 138  * result is a binary polynomial in 4 mp_digits r[4].
 139  * The caller MUST ensure that r has the right amount of space allocated.
 140  */
 141 void
 142 s_bmul_2x2(mp_digit *r, const mp_digit a1, const mp_digit a0, const mp_digit b1,
 143            const mp_digit b0)
 144 {
 145     mp_digit m1, m0;
 146     /* r[3] = h1, r[2] = h0; r[1] = l1; r[0] = l0 */
 147     s_bmul_1x1(r+3, r+2, a1, b1);
 148     s_bmul_1x1(r+1, r, a0, b0);
 149     s_bmul_1x1(&m1, &m0, a0 ^ a1, b0 ^ b1);
 150     /* Correction on m1 ^= l1 ^ h1; m0 ^= l0 ^ h0; */
 151     r[2] ^= m1 ^ r[1] ^ r[3];  /* h0 ^= m1 ^ l1 ^ h1; */
 152     r[1]  = r[3] ^ r[2] ^ r[0] ^ m1 ^ m0;  /* l1 ^= l0 ^ h0 ^ m0; */
 153 }
 154
 155 /* Compute xor-multiply of two binary polynomials  (a2, a1, a0) x (b2, b1, b0)
 156  * result is a binary polynomial in 6 mp_digits r[6].
 157  * The caller MUST ensure that r has the right amount of space allocated.
 158  */
 159 void
 160 s_bmul_3x3(mp_digit *r, const mp_digit a2, const mp_digit a1, const mp_digit a0,
 161         const mp_digit b2, const mp_digit b1, const mp_digit b0)
 162 {
 163         mp_digit zm[4];
 164
 165         s_bmul_1x1(r+5, r+4, a2, b2);         /* fill top 2 words */
 166         s_bmul_2x2(zm, a1, a2^a0, b1, b2^b0); /* fill middle 4 words */
 167         s_bmul_2x2(r, a1, a0, b1, b0);        /* fill bottom 4 words */
 168
 169         zm[3] ^= r[3];
 170         zm[2] ^= r[2];
 171         zm[1] ^= r[1] ^ r[5];
 172         zm[0] ^= r[0] ^ r[4];
 173
 174         r[5]  ^= zm[3];
 175         r[4]  ^= zm[2];
 176         r[3]  ^= zm[1];
 177         r[2]  ^= zm[0];
 178 }
 179
 180 /* Compute xor-multiply of two binary polynomials  (a3, a2, a1, a0) x (b3, b2, b1, b0)
 181  * result is a binary polynomial in 8 mp_digits r[8].
 182  * The caller MUST ensure that r has the right amount of space allocated.
 183  */
 184 void s_bmul_4x4(mp_digit *r, const mp_digit a3, const mp_digit a2, const mp_digit a1,
 185         const mp_digit a0, const mp_digit b3, const mp_digit b2, const mp_digit b1,
 186         const mp_digit b0)
 187 {
 188         mp_digit zm[4];
 189
 190         s_bmul_2x2(r+4, a3, a2, b3, b2);            /* fill top 4 words */
 191         s_bmul_2x2(zm, a3^a1, a2^a0, b3^b1, b2^b0); /* fill middle 4 words */
 192         s_bmul_2x2(r, a1, a0, b1, b0);              /* fill bottom 4 words */
 193
 194         zm[3] ^= r[3] ^ r[7];
 195         zm[2] ^= r[2] ^ r[6];
 196         zm[1] ^= r[1] ^ r[5];
 197         zm[0] ^= r[0] ^ r[4];
 198
 199         r[5]  ^= zm[3];
 200         r[4]  ^= zm[2];
 201         r[3]  ^= zm[1];
 202         r[2]  ^= zm[0];
 203 }
 204
 205 /* Compute addition of two binary polynomials a and b,
 206  * store result in c; c could be a or b, a and b could be equal;
 207  * c is the bitwise XOR of a and b.
 208  */
 209 mp_err
 210 mp_badd(const mp_int *a, const mp_int *b, mp_int *c)
 211 {
 212     mp_digit *pa, *pb, *pc;
 213     mp_size ix;
 214     mp_size used_pa, used_pb;
 215     mp_err res = MP_OKAY;
 216
 217     /* Add all digits up to the precision of b.  If b had more
 218      * precision than a initially, swap a, b first
 219      */
 220     if (MP_USED(a) >= MP_USED(b)) {
 221         pa = MP_DIGITS(a);
 222         pb = MP_DIGITS(b);
 223         used_pa = MP_USED(a);
 224         used_pb = MP_USED(b);
 225     } else {
 226         pa = MP_DIGITS(b);
 227         pb = MP_DIGITS(a);
 228         used_pa = MP_USED(b);
 229         used_pb = MP_USED(a);
 230     }
 231
 232     /* Make sure c has enough precision for the output value */
 233     MP_CHECKOK( s_mp_pad(c, used_pa) );
 234
 235     /* Do word-by-word xor */
 236     pc = MP_DIGITS(c);
 237     for (ix = 0; ix < used_pb; ix++) {
 238         (*pc++) = (*pa++) ^ (*pb++);
 239     }
 240
 241     /* Finish the rest of digits until we're actually done */
 242     for (; ix < used_pa; ++ix) {
 243         *pc++ = *pa++;
 244     }
 245
 246     MP_USED(c) = used_pa;
 247     MP_SIGN(c) = ZPOS;
 248     s_mp_clamp(c);
 249
 250 CLEANUP:
 251     return res;
 252 }
 253
 254 #define s_mp_div2(a) MP_CHECKOK( mpl_rsh((a), (a), 1) );
 255
 256 /* Compute binary polynomial multiply d = a * b */
 257 static void
 258 s_bmul_d(const mp_digit *a, mp_size a_len, mp_digit b, mp_digit *d)
 259 {
 260     mp_digit a_i, a0b0, a1b1, carry = 0;
 261     while (a_len--) {
 262         a_i = *a++;
 263         s_bmul_1x1(&a1b1, &a0b0, a_i, b);
 264         *d++ = a0b0 ^ carry;
 265         carry = a1b1;
 266     }
 267     *d = carry;
 268 }
 269
 270 /* Compute binary polynomial xor multiply accumulate d ^= a * b */
 271 static void
 272 s_bmul_d_add(const mp_digit *a, mp_size a_len, mp_digit b, mp_digit *d)
 273 {
 274     mp_digit a_i, a0b0, a1b1, carry = 0;
 275     while (a_len--) {
 276         a_i = *a++;
 277         s_bmul_1x1(&a1b1, &a0b0, a_i, b);
 278         *d++ ^= a0b0 ^ carry;
 279         carry = a1b1;
 280     }
 281     *d ^= carry;
 282 }
 283
 284 /* Compute binary polynomial xor multiply c = a * b.
 285  * All parameters may be identical.
 286  */
 287 mp_err
 288 mp_bmul(const mp_int *a, const mp_int *b, mp_int *c)
 289 {
 290     mp_digit *pb, b_i;
 291     mp_int tmp;
 292     mp_size ib, a_used, b_used;
 293     mp_err res = MP_OKAY;
 294
 295     MP_DIGITS(&tmp) = 0;
 296
 297     ARGCHK(a != NULL && b != NULL && c != NULL, MP_BADARG);
 298
 299     if (a == c) {
 300         MP_CHECKOK( mp_init_copy(&tmp, a) );
 301         if (a == b)
 302             b = &tmp;
 303         a = &tmp;
 304     } else if (b == c) {
 305         MP_CHECKOK( mp_init_copy(&tmp, b) );
 306         b = &tmp;
 307     }
 308
 309     if (MP_USED(a) < MP_USED(b)) {
 310         const mp_int *xch = b;      /* switch a and b if b longer */
 311         b = a;
 312         a = xch;
 313     }
 314
 315     MP_USED(c) = 1; MP_DIGIT(c, 0) = 0;
 316     MP_CHECKOK( s_mp_pad(c, USED(a) + USED(b)) );
 317
 318     pb = MP_DIGITS(b);
 319     s_bmul_d(MP_DIGITS(a), MP_USED(a), *pb++, MP_DIGITS(c));
 320
 321     /* Outer loop:  Digits of b */
 322     a_used = MP_USED(a);
 323     b_used = MP_USED(b);
 324         MP_USED(c) = a_used + b_used;
 325     for (ib = 1; ib < b_used; ib++) {
 326         b_i = *pb++;
 327
 328         /* Inner product:  Digits of a */
 329         if (b_i)
 330             s_bmul_d_add(MP_DIGITS(a), a_used, b_i, MP_DIGITS(c) + ib);
 331         else
 332             MP_DIGIT(c, ib + a_used) = b_i;
 333     }
 334
 335     s_mp_clamp(c);
 336
 337     SIGN(c) = ZPOS;
 338
 339 CLEANUP:
 340     mp_clear(&tmp);
 341     return res;
 342 }
 343
 344
 345 /* Compute modular reduction of a and store result in r.
 346  * r could be a.
 347  * For modular arithmetic, the irreducible polynomial f(t) is represented
 348  * as an array of int[], where f(t) is of the form:
 349  *     f(t) = t^p[0] + t^p[1] + ... + t^p[k]
 350  * where m = p[0] > p[1] > ... > p[k] = 0.
 351  */
 352 mp_err
 353 mp_bmod(const mp_int *a, const unsigned int p[], mp_int *r)
 354 {
 355     int j, k;
 356     int n, dN, d0, d1;
 357     mp_digit zz, *z, tmp;
 358     mp_size used;
 359     mp_err res = MP_OKAY;
 360
 361     /* The algorithm does the reduction in place in r,
 362      * if a != r, copy a into r first so reduction can be done in r
 363      */
 364     if (a != r) {
 365         MP_CHECKOK( mp_copy(a, r) );
 366     }
 367     z = MP_DIGITS(r);
 368
 369     /* start reduction */
 370     dN = p[0] / MP_DIGIT_BITS;
 371     used = MP_USED(r);
 372
 373     for (j = used - 1; j > dN;) {
 374
 375         zz = z[j];
 376         if (zz == 0) {
 377             j--; continue;
 378         }
 379         z[j] = 0;
 380
 381         for (k = 1; p[k] > 0; k++) {
 382             /* reducing component t^p[k] */
 383             n = p[0] - p[k];
 384             d0 = n % MP_DIGIT_BITS;
 385             d1 = MP_DIGIT_BITS - d0;
 386             n /= MP_DIGIT_BITS;
 387             z[j-n] ^= (zz>>d0);
 388             if (d0)
 389                 z[j-n-1] ^= (zz<<d1);
 390         }
 391
 392         /* reducing component t^0 */
 393         n = dN;
 394         d0 = p[0] % MP_DIGIT_BITS;
 395         d1 = MP_DIGIT_BITS - d0;
 396         z[j-n] ^= (zz >> d0);
 397         if (d0)
 398             z[j-n-1] ^= (zz << d1);
 399
 400     }
 401
 402     /* final round of reduction */
 403     while (j == dN) {
 404
 405         d0 = p[0] % MP_DIGIT_BITS;
 406         zz = z[dN] >> d0;
 407         if (zz == 0) break;
 408         d1 = MP_DIGIT_BITS - d0;
 409
 410         /* clear up the top d1 bits */
 411         if (d0) z[dN] = (z[dN] << d1) >> d1;
 412         *z ^= zz; /* reduction t^0 component */
 413
 414         for (k = 1; p[k] > 0; k++) {
 415             /* reducing component t^p[k]*/
 416             n = p[k] / MP_DIGIT_BITS;
 417             d0 = p[k] % MP_DIGIT_BITS;
 418             d1 = MP_DIGIT_BITS - d0;
 419             z[n] ^= (zz << d0);
 420             tmp = zz >> d1;
 421             if (d0 && tmp)
 422                 z[n+1] ^= tmp;
 423         }
 424     }
 425
 426     s_mp_clamp(r);
 427 CLEANUP:
 428     return res;
 429 }
 430
 431 /* Compute the product of two polynomials a and b, reduce modulo p,
 432  * Store the result in r.  r could be a or b; a could be b.
 433  */
 434 mp_err
 435 mp_bmulmod(const mp_int *a, const mp_int *b, const unsigned int p[], mp_int *r)
 436 {
 437     mp_err res;
 438
 439     if (a == b) return mp_bsqrmod(a, p, r);
 440     if ((res = mp_bmul(a, b, r) ) != MP_OKAY)
 441         return res;
 442     return mp_bmod(r, p, r);
 443 }
 444
 445 /* Compute binary polynomial squaring c = a*a mod p .
 446  * Parameter r and a can be identical.
 447  */
 448
 449 mp_err
 450 mp_bsqrmod(const mp_int *a, const unsigned int p[], mp_int *r)
 451 {
 452     mp_digit *pa, *pr, a_i;
 453     mp_int tmp;
 454     mp_size ia, a_used;
 455     mp_err res;
 456
 457     ARGCHK(a != NULL && r != NULL, MP_BADARG);
 458     MP_DIGITS(&tmp) = 0;
 459
 460     if (a == r) {
 461         MP_CHECKOK( mp_init_copy(&tmp, a) );
 462         a = &tmp;
 463     }
 464
 465     MP_USED(r) = 1; MP_DIGIT(r, 0) = 0;
 466     MP_CHECKOK( s_mp_pad(r, 2*USED(a)) );
 467
 468     pa = MP_DIGITS(a);
 469     pr = MP_DIGITS(r);
 470     a_used = MP_USED(a);
 471         MP_USED(r) = 2 * a_used;
 472
 473     for (ia = 0; ia < a_used; ia++) {
 474         a_i = *pa++;
 475         *pr++ = gf2m_SQR0(a_i);
 476         *pr++ = gf2m_SQR1(a_i);
 477     }
 478
 479     MP_CHECKOK( mp_bmod(r, p, r) );
 480     s_mp_clamp(r);
 481     SIGN(r) = ZPOS;
 482
 483 CLEANUP:
 484     mp_clear(&tmp);
 485     return res;
 486 }
 487
 488 /* Compute binary polynomial y/x mod p, y divided by x, reduce modulo p.
 489  * Store the result in r. r could be x or y, and x could equal y.
 490  * Uses algorithm Modular_Division_GF(2^m) from
 491  *     Chang-Shantz, S.  "From Euclid's GCD to Montgomery Multiplication to
 492  *     the Great Divide".
 493  */
 494 int
 495 mp_bdivmod(const mp_int *y, const mp_int *x, const mp_int *pp,
 496     const unsigned int p[], mp_int *r)
 497 {
 498     mp_int aa, bb, uu;
 499     mp_int *a, *b, *u, *v;
 500     mp_err res = MP_OKAY;
 501
 502     MP_DIGITS(&aa) = 0;
 503     MP_DIGITS(&bb) = 0;
 504     MP_DIGITS(&uu) = 0;
 505
 506     MP_CHECKOK( mp_init_copy(&aa, x) );
 507     MP_CHECKOK( mp_init_copy(&uu, y) );
 508     MP_CHECKOK( mp_init_copy(&bb, pp) );
 509     MP_CHECKOK( s_mp_pad(r, USED(pp)) );
 510     MP_USED(r) = 1; MP_DIGIT(r, 0) = 0;
 511
 512     a = &aa; b= &bb; u=&uu; v=r;
 513     /* reduce x and y mod p */
 514     MP_CHECKOK( mp_bmod(a, p, a) );
 515     MP_CHECKOK( mp_bmod(u, p, u) );
 516
 517     while (!mp_isodd(a)) {
 518         s_mp_div2(a);
 519         if (mp_isodd(u)) {
 520             MP_CHECKOK( mp_badd(u, pp, u) );
 521         }
 522         s_mp_div2(u);
 523     }
 524
 525     do {
 526         if (mp_cmp_mag(b, a) > 0) {
 527             MP_CHECKOK( mp_badd(b, a, b) );
 528             MP_CHECKOK( mp_badd(v, u, v) );
 529             do {
 530                 s_mp_div2(b);
 531                 if (mp_isodd(v)) {
 532                     MP_CHECKOK( mp_badd(v, pp, v) );
 533                 }
 534                 s_mp_div2(v);
 535             } while (!mp_isodd(b));
 536         }
 537         else if ((MP_DIGIT(a,0) == 1) && (MP_USED(a) == 1))
 538             break;
 539         else {
 540             MP_CHECKOK( mp_badd(a, b, a) );
 541             MP_CHECKOK( mp_badd(u, v, u) );
 542             do {
 543                 s_mp_div2(a);
 544                 if (mp_isodd(u)) {
 545                     MP_CHECKOK( mp_badd(u, pp, u) );
 546                 }
 547                 s_mp_div2(u);
 548             } while (!mp_isodd(a));
 549         }
 550     } while (1);
 551
 552     MP_CHECKOK( mp_copy(u, r) );
 553
 554 CLEANUP:
 555     /* XXX this appears to be a memory leak in the NSS code */
 556     mp_clear(&aa);
 557     mp_clear(&bb);
 558     mp_clear(&uu);
 559     return res;
 560
 561 }
 562
 563 /* Convert the bit-string representation of a polynomial a into an array
 564  * of integers corresponding to the bits with non-zero coefficient.
 565  * Up to max elements of the array will be filled.  Return value is total
 566  * number of coefficients that would be extracted if array was large enough.
 567  */
 568 int
 569 mp_bpoly2arr(const mp_int *a, unsigned int p[], int max)
 570 {
 571     int i, j, k;
 572     mp_digit top_bit, mask;
 573
 574     top_bit = 1;
 575     top_bit <<= MP_DIGIT_BIT - 1;
 576
 577     for (k = 0; k < max; k++) p[k] = 0;
 578     k = 0;
 579
 580     for (i = MP_USED(a) - 1; i >= 0; i--) {
 581         mask = top_bit;
 582         for (j = MP_DIGIT_BIT - 1; j >= 0; j--) {
 583             if (MP_DIGITS(a)[i] & mask) {
 584                 if (k < max) p[k] = MP_DIGIT_BIT * i + j;
 585                 k++;
 586             }
 587             mask >>= 1;
 588         }
 589     }
 590
 591     return k;
 592 }
 593
 594 /* Convert the coefficient array representation of a polynomial to a
 595  * bit-string.  The array must be terminated by 0.
 596  */
 597 mp_err
 598 mp_barr2poly(const unsigned int p[], mp_int *a)
 599 {
 600
 601     mp_err res = MP_OKAY;
 602     int i;
 603
 604     mp_zero(a);
 605     for (i = 0; p[i] > 0; i++) {
 606         MP_CHECKOK( mpl_set_bit(a, p[i], 1) );
 607     }
 608     MP_CHECKOK( mpl_set_bit(a, 0, 1) );
 609
 610 CLEANUP:
 611     return res;
 612 }