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