Back to index

lightning-sunbird  0.9+nobinonly
mp_gf2m.c
Go to the documentation of this file.
00001 /*
00002  * ***** BEGIN LICENSE BLOCK *****
00003  * Version: MPL 1.1/GPL 2.0/LGPL 2.1
00004  *
00005  * The contents of this file are subject to the Mozilla Public License Version
00006  * 1.1 (the "License"); you may not use this file except in compliance with
00007  * the License. You may obtain a copy of the License at
00008  * http://www.mozilla.org/MPL/
00009  *
00010  * Software distributed under the License is distributed on an "AS IS" basis,
00011  * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
00012  * for the specific language governing rights and limitations under the
00013  * License.
00014  *
00015  * The Original Code is the Multi-precision Binary Polynomial Arithmetic Library.
00016  *
00017  * The Initial Developer of the Original Code is
00018  * Sun Microsystems, Inc.
00019  * Portions created by the Initial Developer are Copyright (C) 2003
00020  * the Initial Developer. All Rights Reserved.
00021  *
00022  * Contributor(s):
00023  *   Sheueling Chang Shantz <sheueling.chang@sun.com> and
00024  *   Douglas Stebila <douglas@stebila.ca> of Sun Laboratories.
00025  *
00026  * Alternatively, the contents of this file may be used under the terms of
00027  * either the GNU General Public License Version 2 or later (the "GPL"), or
00028  * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
00029  * in which case the provisions of the GPL or the LGPL are applicable instead
00030  * of those above. If you wish to allow use of your version of this file only
00031  * under the terms of either the GPL or the LGPL, and not to allow others to
00032  * use your version of this file under the terms of the MPL, indicate your
00033  * decision by deleting the provisions above and replace them with the notice
00034  * and other provisions required by the GPL or the LGPL. If you do not delete
00035  * the provisions above, a recipient may use your version of this file under
00036  * the terms of any one of the MPL, the GPL or the LGPL.
00037  *
00038  * ***** END LICENSE BLOCK ***** */
00039 
00040 #include "mp_gf2m.h"
00041 #include "mp_gf2m-priv.h"
00042 #include "mplogic.h"
00043 #include "mpi-priv.h"
00044 
00045 const mp_digit mp_gf2m_sqr_tb[16] =
00046 {
00047       0,     1,     4,     5,    16,    17,    20,    21,
00048      64,    65,    68,    69,    80,    81,    84,    85
00049 };
00050 
00051 /* Multiply two binary polynomials mp_digits a, b.
00052  * Result is a polynomial with degree < 2 * MP_DIGIT_BITS - 1.
00053  * Output in two mp_digits rh, rl.
00054  */
00055 #if MP_DIGIT_BITS == 32
00056 void 
00057 s_bmul_1x1(mp_digit *rh, mp_digit *rl, const mp_digit a, const mp_digit b)
00058 {
00059     register mp_digit h, l, s;
00060     mp_digit tab[8], top2b = a >> 30; 
00061     register mp_digit a1, a2, a4;
00062 
00063     a1 = a & (0x3FFFFFFF); a2 = a1 << 1; a4 = a2 << 1;
00064 
00065     tab[0] =  0; tab[1] = a1;    tab[2] = a2;    tab[3] = a1^a2;
00066     tab[4] = a4; tab[5] = a1^a4; tab[6] = a2^a4; tab[7] = a1^a2^a4;
00067 
00068     s = tab[b       & 0x7]; l  = s;
00069     s = tab[b >>  3 & 0x7]; l ^= s <<  3; h  = s >> 29;
00070     s = tab[b >>  6 & 0x7]; l ^= s <<  6; h ^= s >> 26;
00071     s = tab[b >>  9 & 0x7]; l ^= s <<  9; h ^= s >> 23;
00072     s = tab[b >> 12 & 0x7]; l ^= s << 12; h ^= s >> 20;
00073     s = tab[b >> 15 & 0x7]; l ^= s << 15; h ^= s >> 17;
00074     s = tab[b >> 18 & 0x7]; l ^= s << 18; h ^= s >> 14;
00075     s = tab[b >> 21 & 0x7]; l ^= s << 21; h ^= s >> 11;
00076     s = tab[b >> 24 & 0x7]; l ^= s << 24; h ^= s >>  8;
00077     s = tab[b >> 27 & 0x7]; l ^= s << 27; h ^= s >>  5;
00078     s = tab[b >> 30      ]; l ^= s << 30; h ^= s >>  2;
00079 
00080     /* compensate for the top two bits of a */
00081 
00082     if (top2b & 01) { l ^= b << 30; h ^= b >> 2; } 
00083     if (top2b & 02) { l ^= b << 31; h ^= b >> 1; } 
00084 
00085     *rh = h; *rl = l;
00086 } 
00087 #else
00088 void 
00089 s_bmul_1x1(mp_digit *rh, mp_digit *rl, const mp_digit a, const mp_digit b)
00090 {
00091     register mp_digit h, l, s;
00092     mp_digit tab[16], top3b = a >> 61;
00093     register mp_digit a1, a2, a4, a8;
00094 
00095     a1 = a & (0x1FFFFFFFFFFFFFFFULL); a2 = a1 << 1; 
00096     a4 = a2 << 1; a8 = a4 << 1;
00097     tab[ 0] = 0;     tab[ 1] = a1;       tab[ 2] = a2;       tab[ 3] = a1^a2;
00098     tab[ 4] = a4;    tab[ 5] = a1^a4;    tab[ 6] = a2^a4;    tab[ 7] = a1^a2^a4;
00099     tab[ 8] = a8;    tab[ 9] = a1^a8;    tab[10] = a2^a8;    tab[11] = a1^a2^a8;
00100     tab[12] = a4^a8; tab[13] = a1^a4^a8; tab[14] = a2^a4^a8; tab[15] = a1^a2^a4^a8;
00101 
00102     s = tab[b       & 0xF]; l  = s;
00103     s = tab[b >>  4 & 0xF]; l ^= s <<  4; h  = s >> 60;
00104     s = tab[b >>  8 & 0xF]; l ^= s <<  8; h ^= s >> 56;
00105     s = tab[b >> 12 & 0xF]; l ^= s << 12; h ^= s >> 52;
00106     s = tab[b >> 16 & 0xF]; l ^= s << 16; h ^= s >> 48;
00107     s = tab[b >> 20 & 0xF]; l ^= s << 20; h ^= s >> 44;
00108     s = tab[b >> 24 & 0xF]; l ^= s << 24; h ^= s >> 40;
00109     s = tab[b >> 28 & 0xF]; l ^= s << 28; h ^= s >> 36;
00110     s = tab[b >> 32 & 0xF]; l ^= s << 32; h ^= s >> 32;
00111     s = tab[b >> 36 & 0xF]; l ^= s << 36; h ^= s >> 28;
00112     s = tab[b >> 40 & 0xF]; l ^= s << 40; h ^= s >> 24;
00113     s = tab[b >> 44 & 0xF]; l ^= s << 44; h ^= s >> 20;
00114     s = tab[b >> 48 & 0xF]; l ^= s << 48; h ^= s >> 16;
00115     s = tab[b >> 52 & 0xF]; l ^= s << 52; h ^= s >> 12;
00116     s = tab[b >> 56 & 0xF]; l ^= s << 56; h ^= s >>  8;
00117     s = tab[b >> 60      ]; l ^= s << 60; h ^= s >>  4;
00118 
00119     /* compensate for the top three bits of a */
00120 
00121     if (top3b & 01) { l ^= b << 61; h ^= b >> 3; } 
00122     if (top3b & 02) { l ^= b << 62; h ^= b >> 2; } 
00123     if (top3b & 04) { l ^= b << 63; h ^= b >> 1; } 
00124 
00125     *rh = h; *rl = l;
00126 } 
00127 #endif
00128 
00129 /* Compute xor-multiply of two binary polynomials  (a1, a0) x (b1, b0)  
00130  * result is a binary polynomial in 4 mp_digits r[4].
00131  * The caller MUST ensure that r has the right amount of space allocated.
00132  */
00133 void 
00134 s_bmul_2x2(mp_digit *r, const mp_digit a1, const mp_digit a0, const mp_digit b1,
00135            const mp_digit b0)
00136 {
00137     mp_digit m1, m0;
00138     /* r[3] = h1, r[2] = h0; r[1] = l1; r[0] = l0 */
00139     s_bmul_1x1(r+3, r+2, a1, b1);
00140     s_bmul_1x1(r+1, r, a0, b0);
00141     s_bmul_1x1(&m1, &m0, a0 ^ a1, b0 ^ b1);
00142     /* Correction on m1 ^= l1 ^ h1; m0 ^= l0 ^ h0; */
00143     r[2] ^= m1 ^ r[1] ^ r[3];  /* h0 ^= m1 ^ l1 ^ h1; */
00144     r[1]  = r[3] ^ r[2] ^ r[0] ^ m1 ^ m0;  /* l1 ^= l0 ^ h0 ^ m0; */
00145 }
00146 
00147 /* Compute xor-multiply of two binary polynomials  (a2, a1, a0) x (b2, b1, b0)  
00148  * result is a binary polynomial in 6 mp_digits r[6].
00149  * The caller MUST ensure that r has the right amount of space allocated.
00150  */
00151 void 
00152 s_bmul_3x3(mp_digit *r, const mp_digit a2, const mp_digit a1, const mp_digit a0, 
00153        const mp_digit b2, const mp_digit b1, const mp_digit b0)
00154 {
00155        mp_digit zm[4];
00156 
00157        s_bmul_1x1(r+5, r+4, a2, b2);         /* fill top 2 words */
00158        s_bmul_2x2(zm, a1, a2^a0, b1, b2^b0); /* fill middle 4 words */
00159        s_bmul_2x2(r, a1, a0, b1, b0);        /* fill bottom 4 words */
00160 
00161        zm[3] ^= r[3];
00162        zm[2] ^= r[2]; 
00163        zm[1] ^= r[1] ^ r[5];
00164        zm[0] ^= r[0] ^ r[4];
00165 
00166        r[5]  ^= zm[3];
00167        r[4]  ^= zm[2];
00168        r[3]  ^= zm[1];
00169        r[2]  ^= zm[0];
00170 }
00171 
00172 /* Compute xor-multiply of two binary polynomials  (a3, a2, a1, a0) x (b3, b2, b1, b0)  
00173  * result is a binary polynomial in 8 mp_digits r[8].
00174  * The caller MUST ensure that r has the right amount of space allocated.
00175  */
00176 void s_bmul_4x4(mp_digit *r, const mp_digit a3, const mp_digit a2, const mp_digit a1, 
00177        const mp_digit a0, const mp_digit b3, const mp_digit b2, const mp_digit b1, 
00178        const mp_digit b0)
00179 {
00180        mp_digit zm[4];
00181 
00182        s_bmul_2x2(r+4, a3, a2, b3, b2);            /* fill top 4 words */
00183        s_bmul_2x2(zm, a3^a1, a2^a0, b3^b1, b2^b0); /* fill middle 4 words */
00184        s_bmul_2x2(r, a1, a0, b1, b0);              /* fill bottom 4 words */
00185 
00186        zm[3] ^= r[3] ^ r[7]; 
00187        zm[2] ^= r[2] ^ r[6]; 
00188        zm[1] ^= r[1] ^ r[5]; 
00189        zm[0] ^= r[0] ^ r[4]; 
00190 
00191        r[5]  ^= zm[3];    
00192        r[4]  ^= zm[2];
00193        r[3]  ^= zm[1];    
00194        r[2]  ^= zm[0];
00195 }
00196 
00197 /* Compute addition of two binary polynomials a and b,
00198  * store result in c; c could be a or b, a and b could be equal; 
00199  * c is the bitwise XOR of a and b.
00200  */
00201 mp_err
00202 mp_badd(const mp_int *a, const mp_int *b, mp_int *c)
00203 {
00204     mp_digit *pa, *pb, *pc;
00205     mp_size ix;
00206     mp_size used_pa, used_pb;
00207     mp_err res = MP_OKAY;
00208 
00209     /* Add all digits up to the precision of b.  If b had more
00210      * precision than a initially, swap a, b first
00211      */
00212     if (MP_USED(a) >= MP_USED(b)) {
00213         pa = MP_DIGITS(a);
00214         pb = MP_DIGITS(b);
00215         used_pa = MP_USED(a);
00216         used_pb = MP_USED(b);
00217     } else {
00218         pa = MP_DIGITS(b);
00219         pb = MP_DIGITS(a);
00220         used_pa = MP_USED(b);
00221         used_pb = MP_USED(a);
00222     }
00223 
00224     /* Make sure c has enough precision for the output value */
00225     MP_CHECKOK( s_mp_pad(c, used_pa) );
00226 
00227     /* Do word-by-word xor */
00228     pc = MP_DIGITS(c);
00229     for (ix = 0; ix < used_pb; ix++) {
00230         (*pc++) = (*pa++) ^ (*pb++);
00231     }
00232 
00233     /* Finish the rest of digits until we're actually done */
00234     for (; ix < used_pa; ++ix) {
00235         *pc++ = *pa++;
00236     }
00237 
00238     MP_USED(c) = used_pa;
00239     MP_SIGN(c) = ZPOS;
00240     s_mp_clamp(c);
00241 
00242 CLEANUP:
00243     return res;
00244 } 
00245 
00246 #define s_mp_div2(a) MP_CHECKOK( mpl_rsh((a), (a), 1) );
00247 
00248 /* Compute binary polynomial multiply d = a * b */
00249 static void 
00250 s_bmul_d(const mp_digit *a, mp_size a_len, mp_digit b, mp_digit *d)
00251 {
00252     mp_digit a_i, a0b0, a1b1, carry = 0;
00253     while (a_len--) {
00254         a_i = *a++;
00255         s_bmul_1x1(&a1b1, &a0b0, a_i, b);
00256         *d++ = a0b0 ^ carry;
00257         carry = a1b1;
00258     }
00259     *d = carry;
00260 }
00261 
00262 /* Compute binary polynomial xor multiply accumulate d ^= a * b */
00263 static void 
00264 s_bmul_d_add(const mp_digit *a, mp_size a_len, mp_digit b, mp_digit *d)
00265 {
00266     mp_digit a_i, a0b0, a1b1, carry = 0;
00267     while (a_len--) {
00268         a_i = *a++;
00269         s_bmul_1x1(&a1b1, &a0b0, a_i, b);
00270         *d++ ^= a0b0 ^ carry;
00271         carry = a1b1;
00272     }
00273     *d ^= carry;
00274 }
00275 
00276 /* Compute binary polynomial xor multiply c = a * b.  
00277  * All parameters may be identical.
00278  */
00279 mp_err 
00280 mp_bmul(const mp_int *a, const mp_int *b, mp_int *c)
00281 {
00282     mp_digit *pb, b_i;
00283     mp_int tmp;
00284     mp_size ib, a_used, b_used;
00285     mp_err res = MP_OKAY;
00286 
00287     MP_DIGITS(&tmp) = 0;
00288 
00289     ARGCHK(a != NULL && b != NULL && c != NULL, MP_BADARG);
00290 
00291     if (a == c) {
00292         MP_CHECKOK( mp_init_copy(&tmp, a) );
00293         if (a == b)
00294             b = &tmp;
00295         a = &tmp;
00296     } else if (b == c) {
00297         MP_CHECKOK( mp_init_copy(&tmp, b) );
00298         b = &tmp;
00299     }
00300 
00301     if (MP_USED(a) < MP_USED(b)) {
00302         const mp_int *xch = b;      /* switch a and b if b longer */
00303         b = a;
00304         a = xch;
00305     }
00306 
00307     MP_USED(c) = 1; MP_DIGIT(c, 0) = 0;
00308     MP_CHECKOK( s_mp_pad(c, USED(a) + USED(b)) );
00309 
00310     pb = MP_DIGITS(b);
00311     s_bmul_d(MP_DIGITS(a), MP_USED(a), *pb++, MP_DIGITS(c));
00312 
00313     /* Outer loop:  Digits of b */
00314     a_used = MP_USED(a);
00315     b_used = MP_USED(b);
00316        MP_USED(c) = a_used + b_used;
00317     for (ib = 1; ib < b_used; ib++) {
00318         b_i = *pb++;
00319 
00320         /* Inner product:  Digits of a */
00321         if (b_i)
00322             s_bmul_d_add(MP_DIGITS(a), a_used, b_i, MP_DIGITS(c) + ib);
00323         else
00324             MP_DIGIT(c, ib + a_used) = b_i;
00325     }
00326 
00327     s_mp_clamp(c);
00328 
00329     SIGN(c) = ZPOS;
00330 
00331 CLEANUP:
00332     mp_clear(&tmp);
00333     return res;
00334 }
00335 
00336 
00337 /* Compute modular reduction of a and store result in r.  
00338  * r could be a. 
00339  * For modular arithmetic, the irreducible polynomial f(t) is represented 
00340  * as an array of int[], where f(t) is of the form: 
00341  *     f(t) = t^p[0] + t^p[1] + ... + t^p[k]
00342  * where m = p[0] > p[1] > ... > p[k] = 0.
00343  */
00344 mp_err
00345 mp_bmod(const mp_int *a, const unsigned int p[], mp_int *r)
00346 {
00347     int j, k;
00348     int n, dN, d0, d1;
00349     mp_digit zz, *z, tmp;
00350     mp_size used;
00351     mp_err res = MP_OKAY;
00352 
00353     /* The algorithm does the reduction in place in r, 
00354      * if a != r, copy a into r first so reduction can be done in r
00355      */
00356     if (a != r) {
00357         MP_CHECKOK( mp_copy(a, r) );
00358     }
00359     z = MP_DIGITS(r);
00360 
00361     /* start reduction */
00362     dN = p[0] / MP_DIGIT_BITS;
00363     used = MP_USED(r);
00364 
00365     for (j = used - 1; j > dN;) {
00366 
00367         zz = z[j];
00368         if (zz == 0) {
00369             j--; continue;
00370         }
00371         z[j] = 0;
00372 
00373         for (k = 1; p[k] > 0; k++) {
00374             /* reducing component t^p[k] */
00375             n = p[0] - p[k];
00376             d0 = n % MP_DIGIT_BITS;  
00377             d1 = MP_DIGIT_BITS - d0;
00378             n /= MP_DIGIT_BITS;
00379             z[j-n] ^= (zz>>d0);
00380             if (d0) 
00381                 z[j-n-1] ^= (zz<<d1);
00382         }
00383 
00384         /* reducing component t^0 */
00385         n = dN;  
00386         d0 = p[0] % MP_DIGIT_BITS;
00387         d1 = MP_DIGIT_BITS - d0;
00388         z[j-n] ^= (zz >> d0);
00389         if (d0) 
00390             z[j-n-1] ^= (zz << d1);
00391 
00392     }
00393 
00394     /* final round of reduction */
00395     while (j == dN) {
00396 
00397         d0 = p[0] % MP_DIGIT_BITS;
00398         zz = z[dN] >> d0;  
00399         if (zz == 0) break;
00400         d1 = MP_DIGIT_BITS - d0;
00401 
00402         /* clear up the top d1 bits */
00403         if (d0) z[dN] = (z[dN] << d1) >> d1; 
00404         *z ^= zz; /* reduction t^0 component */
00405 
00406         for (k = 1; p[k] > 0; k++) {
00407             /* reducing component t^p[k]*/
00408             n = p[k] / MP_DIGIT_BITS;
00409             d0 = p[k] % MP_DIGIT_BITS;
00410             d1 = MP_DIGIT_BITS - d0;
00411             z[n] ^= (zz << d0);
00412             tmp = zz >> d1;
00413             if (d0 && tmp)
00414                 z[n+1] ^= tmp;
00415         }
00416     }
00417 
00418     s_mp_clamp(r);
00419 CLEANUP:
00420     return res;
00421 }
00422 
00423 /* Compute the product of two polynomials a and b, reduce modulo p, 
00424  * Store the result in r.  r could be a or b; a could be b.
00425  */
00426 mp_err 
00427 mp_bmulmod(const mp_int *a, const mp_int *b, const unsigned int p[], mp_int *r)
00428 {
00429     mp_err res;
00430     
00431     if (a == b) return mp_bsqrmod(a, p, r);
00432     if ((res = mp_bmul(a, b, r) ) != MP_OKAY)
00433        return res;
00434     return mp_bmod(r, p, r);
00435 }
00436 
00437 /* Compute binary polynomial squaring c = a*a mod p .  
00438  * Parameter r and a can be identical.
00439  */
00440 
00441 mp_err 
00442 mp_bsqrmod(const mp_int *a, const unsigned int p[], mp_int *r)
00443 {
00444     mp_digit *pa, *pr, a_i;
00445     mp_int tmp;
00446     mp_size ia, a_used;
00447     mp_err res;
00448 
00449     ARGCHK(a != NULL && r != NULL, MP_BADARG);
00450     MP_DIGITS(&tmp) = 0;
00451 
00452     if (a == r) {
00453         MP_CHECKOK( mp_init_copy(&tmp, a) );
00454         a = &tmp;
00455     }
00456 
00457     MP_USED(r) = 1; MP_DIGIT(r, 0) = 0;
00458     MP_CHECKOK( s_mp_pad(r, 2*USED(a)) );
00459 
00460     pa = MP_DIGITS(a);
00461     pr = MP_DIGITS(r);
00462     a_used = MP_USED(a);
00463        MP_USED(r) = 2 * a_used;
00464 
00465     for (ia = 0; ia < a_used; ia++) {
00466         a_i = *pa++;
00467         *pr++ = gf2m_SQR0(a_i);
00468         *pr++ = gf2m_SQR1(a_i);
00469     }
00470 
00471     MP_CHECKOK( mp_bmod(r, p, r) );
00472     s_mp_clamp(r);
00473     SIGN(r) = ZPOS;
00474 
00475 CLEANUP:
00476     mp_clear(&tmp);
00477     return res;
00478 }
00479 
00480 /* Compute binary polynomial y/x mod p, y divided by x, reduce modulo p.
00481  * Store the result in r. r could be x or y, and x could equal y.
00482  * Uses algorithm Modular_Division_GF(2^m) from 
00483  *     Chang-Shantz, S.  "From Euclid's GCD to Montgomery Multiplication to 
00484  *     the Great Divide".
00485  */
00486 int 
00487 mp_bdivmod(const mp_int *y, const mp_int *x, const mp_int *pp, 
00488     const unsigned int p[], mp_int *r)
00489 {
00490     mp_int aa, bb, uu;
00491     mp_int *a, *b, *u, *v;
00492     mp_err res = MP_OKAY;
00493 
00494     MP_DIGITS(&aa) = 0;
00495     MP_DIGITS(&bb) = 0;
00496     MP_DIGITS(&uu) = 0;
00497 
00498     MP_CHECKOK( mp_init_copy(&aa, x) );
00499     MP_CHECKOK( mp_init_copy(&uu, y) );
00500     MP_CHECKOK( mp_init_copy(&bb, pp) );
00501     MP_CHECKOK( s_mp_pad(r, USED(pp)) );
00502     MP_USED(r) = 1; MP_DIGIT(r, 0) = 0;
00503 
00504     a = &aa; b= &bb; u=&uu; v=r;
00505     /* reduce x and y mod p */
00506     MP_CHECKOK( mp_bmod(a, p, a) );
00507     MP_CHECKOK( mp_bmod(u, p, u) );
00508 
00509     while (!mp_isodd(a)) {
00510         s_mp_div2(a);
00511         if (mp_isodd(u)) {
00512             MP_CHECKOK( mp_badd(u, pp, u) );
00513         }
00514         s_mp_div2(u);
00515     }
00516 
00517     do {
00518         if (mp_cmp_mag(b, a) > 0) {
00519             MP_CHECKOK( mp_badd(b, a, b) );
00520             MP_CHECKOK( mp_badd(v, u, v) );
00521             do {
00522                 s_mp_div2(b);
00523                 if (mp_isodd(v)) {
00524                     MP_CHECKOK( mp_badd(v, pp, v) );
00525                 }
00526                 s_mp_div2(v);
00527             } while (!mp_isodd(b));
00528         }
00529         else if ((MP_DIGIT(a,0) == 1) && (MP_USED(a) == 1))
00530             break;
00531         else {
00532             MP_CHECKOK( mp_badd(a, b, a) );
00533             MP_CHECKOK( mp_badd(u, v, u) );
00534             do {
00535                 s_mp_div2(a);
00536                 if (mp_isodd(u)) {
00537                     MP_CHECKOK( mp_badd(u, pp, u) );
00538                 }
00539                 s_mp_div2(u);
00540             } while (!mp_isodd(a));
00541         }
00542     } while (1);
00543 
00544     MP_CHECKOK( mp_copy(u, r) );
00545 
00546 CLEANUP:
00547     mp_clear(&aa);
00548     mp_clear(&bb);
00549     mp_clear(&uu);
00550     return res;
00551 
00552 }
00553 
00554 /* Convert the bit-string representation of a polynomial a into an array
00555  * of integers corresponding to the bits with non-zero coefficient.
00556  * Up to max elements of the array will be filled.  Return value is total
00557  * number of coefficients that would be extracted if array was large enough.
00558  */
00559 int
00560 mp_bpoly2arr(const mp_int *a, unsigned int p[], int max)
00561 {
00562     int i, j, k;
00563     mp_digit top_bit, mask;
00564 
00565     top_bit = 1;
00566     top_bit <<= MP_DIGIT_BIT - 1;
00567 
00568     for (k = 0; k < max; k++) p[k] = 0;
00569     k = 0;
00570 
00571     for (i = MP_USED(a) - 1; i >= 0; i--) {
00572         mask = top_bit;
00573         for (j = MP_DIGIT_BIT - 1; j >= 0; j--) {
00574             if (MP_DIGITS(a)[i] & mask) {
00575                 if (k < max) p[k] = MP_DIGIT_BIT * i + j;
00576                 k++;
00577             }
00578             mask >>= 1;
00579         }
00580     }
00581 
00582     return k;
00583 }
00584 
00585 /* Convert the coefficient array representation of a polynomial to a 
00586  * bit-string.  The array must be terminated by 0.
00587  */
00588 mp_err
00589 mp_barr2poly(const unsigned int p[], mp_int *a)
00590 {
00591 
00592     mp_err res = MP_OKAY;
00593     int i;
00594 
00595     mp_zero(a);
00596     for (i = 0; p[i] > 0; i++) {
00597        MP_CHECKOK( mpl_set_bit(a, p[i], 1) );
00598     }
00599     MP_CHECKOK( mpl_set_bit(a, 0, 1) );
00600        
00601 CLEANUP:
00602     return res;
00603 }