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