1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/security/nss/lib/freebl/mpi/mp_gf2m.c Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,579 @@
1.4 +/* This Source Code Form is subject to the terms of the Mozilla Public
1.5 + * License, v. 2.0. If a copy of the MPL was not distributed with this
1.6 + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
1.7 +
1.8 +#include "mp_gf2m.h"
1.9 +#include "mp_gf2m-priv.h"
1.10 +#include "mplogic.h"
1.11 +#include "mpi-priv.h"
1.12 +
1.13 +const mp_digit mp_gf2m_sqr_tb[16] =
1.14 +{
1.15 + 0, 1, 4, 5, 16, 17, 20, 21,
1.16 + 64, 65, 68, 69, 80, 81, 84, 85
1.17 +};
1.18 +
1.19 +/* Multiply two binary polynomials mp_digits a, b.
1.20 + * Result is a polynomial with degree < 2 * MP_DIGIT_BITS - 1.
1.21 + * Output in two mp_digits rh, rl.
1.22 + */
1.23 +#if MP_DIGIT_BITS == 32
1.24 +void
1.25 +s_bmul_1x1(mp_digit *rh, mp_digit *rl, const mp_digit a, const mp_digit b)
1.26 +{
1.27 + register mp_digit h, l, s;
1.28 + mp_digit tab[8], top2b = a >> 30;
1.29 + register mp_digit a1, a2, a4;
1.30 +
1.31 + a1 = a & (0x3FFFFFFF); a2 = a1 << 1; a4 = a2 << 1;
1.32 +
1.33 + tab[0] = 0; tab[1] = a1; tab[2] = a2; tab[3] = a1^a2;
1.34 + tab[4] = a4; tab[5] = a1^a4; tab[6] = a2^a4; tab[7] = a1^a2^a4;
1.35 +
1.36 + s = tab[b & 0x7]; l = s;
1.37 + s = tab[b >> 3 & 0x7]; l ^= s << 3; h = s >> 29;
1.38 + s = tab[b >> 6 & 0x7]; l ^= s << 6; h ^= s >> 26;
1.39 + s = tab[b >> 9 & 0x7]; l ^= s << 9; h ^= s >> 23;
1.40 + s = tab[b >> 12 & 0x7]; l ^= s << 12; h ^= s >> 20;
1.41 + s = tab[b >> 15 & 0x7]; l ^= s << 15; h ^= s >> 17;
1.42 + s = tab[b >> 18 & 0x7]; l ^= s << 18; h ^= s >> 14;
1.43 + s = tab[b >> 21 & 0x7]; l ^= s << 21; h ^= s >> 11;
1.44 + s = tab[b >> 24 & 0x7]; l ^= s << 24; h ^= s >> 8;
1.45 + s = tab[b >> 27 & 0x7]; l ^= s << 27; h ^= s >> 5;
1.46 + s = tab[b >> 30 ]; l ^= s << 30; h ^= s >> 2;
1.47 +
1.48 + /* compensate for the top two bits of a */
1.49 +
1.50 + if (top2b & 01) { l ^= b << 30; h ^= b >> 2; }
1.51 + if (top2b & 02) { l ^= b << 31; h ^= b >> 1; }
1.52 +
1.53 + *rh = h; *rl = l;
1.54 +}
1.55 +#else
1.56 +void
1.57 +s_bmul_1x1(mp_digit *rh, mp_digit *rl, const mp_digit a, const mp_digit b)
1.58 +{
1.59 + register mp_digit h, l, s;
1.60 + mp_digit tab[16], top3b = a >> 61;
1.61 + register mp_digit a1, a2, a4, a8;
1.62 +
1.63 + a1 = a & (0x1FFFFFFFFFFFFFFFULL); a2 = a1 << 1;
1.64 + a4 = a2 << 1; a8 = a4 << 1;
1.65 + tab[ 0] = 0; tab[ 1] = a1; tab[ 2] = a2; tab[ 3] = a1^a2;
1.66 + tab[ 4] = a4; tab[ 5] = a1^a4; tab[ 6] = a2^a4; tab[ 7] = a1^a2^a4;
1.67 + tab[ 8] = a8; tab[ 9] = a1^a8; tab[10] = a2^a8; tab[11] = a1^a2^a8;
1.68 + tab[12] = a4^a8; tab[13] = a1^a4^a8; tab[14] = a2^a4^a8; tab[15] = a1^a2^a4^a8;
1.69 +
1.70 + s = tab[b & 0xF]; l = s;
1.71 + s = tab[b >> 4 & 0xF]; l ^= s << 4; h = s >> 60;
1.72 + s = tab[b >> 8 & 0xF]; l ^= s << 8; h ^= s >> 56;
1.73 + s = tab[b >> 12 & 0xF]; l ^= s << 12; h ^= s >> 52;
1.74 + s = tab[b >> 16 & 0xF]; l ^= s << 16; h ^= s >> 48;
1.75 + s = tab[b >> 20 & 0xF]; l ^= s << 20; h ^= s >> 44;
1.76 + s = tab[b >> 24 & 0xF]; l ^= s << 24; h ^= s >> 40;
1.77 + s = tab[b >> 28 & 0xF]; l ^= s << 28; h ^= s >> 36;
1.78 + s = tab[b >> 32 & 0xF]; l ^= s << 32; h ^= s >> 32;
1.79 + s = tab[b >> 36 & 0xF]; l ^= s << 36; h ^= s >> 28;
1.80 + s = tab[b >> 40 & 0xF]; l ^= s << 40; h ^= s >> 24;
1.81 + s = tab[b >> 44 & 0xF]; l ^= s << 44; h ^= s >> 20;
1.82 + s = tab[b >> 48 & 0xF]; l ^= s << 48; h ^= s >> 16;
1.83 + s = tab[b >> 52 & 0xF]; l ^= s << 52; h ^= s >> 12;
1.84 + s = tab[b >> 56 & 0xF]; l ^= s << 56; h ^= s >> 8;
1.85 + s = tab[b >> 60 ]; l ^= s << 60; h ^= s >> 4;
1.86 +
1.87 + /* compensate for the top three bits of a */
1.88 +
1.89 + if (top3b & 01) { l ^= b << 61; h ^= b >> 3; }
1.90 + if (top3b & 02) { l ^= b << 62; h ^= b >> 2; }
1.91 + if (top3b & 04) { l ^= b << 63; h ^= b >> 1; }
1.92 +
1.93 + *rh = h; *rl = l;
1.94 +}
1.95 +#endif
1.96 +
1.97 +/* Compute xor-multiply of two binary polynomials (a1, a0) x (b1, b0)
1.98 + * result is a binary polynomial in 4 mp_digits r[4].
1.99 + * The caller MUST ensure that r has the right amount of space allocated.
1.100 + */
1.101 +void
1.102 +s_bmul_2x2(mp_digit *r, const mp_digit a1, const mp_digit a0, const mp_digit b1,
1.103 + const mp_digit b0)
1.104 +{
1.105 + mp_digit m1, m0;
1.106 + /* r[3] = h1, r[2] = h0; r[1] = l1; r[0] = l0 */
1.107 + s_bmul_1x1(r+3, r+2, a1, b1);
1.108 + s_bmul_1x1(r+1, r, a0, b0);
1.109 + s_bmul_1x1(&m1, &m0, a0 ^ a1, b0 ^ b1);
1.110 + /* Correction on m1 ^= l1 ^ h1; m0 ^= l0 ^ h0; */
1.111 + r[2] ^= m1 ^ r[1] ^ r[3]; /* h0 ^= m1 ^ l1 ^ h1; */
1.112 + r[1] = r[3] ^ r[2] ^ r[0] ^ m1 ^ m0; /* l1 ^= l0 ^ h0 ^ m0; */
1.113 +}
1.114 +
1.115 +/* Compute xor-multiply of two binary polynomials (a2, a1, a0) x (b2, b1, b0)
1.116 + * result is a binary polynomial in 6 mp_digits r[6].
1.117 + * The caller MUST ensure that r has the right amount of space allocated.
1.118 + */
1.119 +void
1.120 +s_bmul_3x3(mp_digit *r, const mp_digit a2, const mp_digit a1, const mp_digit a0,
1.121 + const mp_digit b2, const mp_digit b1, const mp_digit b0)
1.122 +{
1.123 + mp_digit zm[4];
1.124 +
1.125 + s_bmul_1x1(r+5, r+4, a2, b2); /* fill top 2 words */
1.126 + s_bmul_2x2(zm, a1, a2^a0, b1, b2^b0); /* fill middle 4 words */
1.127 + s_bmul_2x2(r, a1, a0, b1, b0); /* fill bottom 4 words */
1.128 +
1.129 + zm[3] ^= r[3];
1.130 + zm[2] ^= r[2];
1.131 + zm[1] ^= r[1] ^ r[5];
1.132 + zm[0] ^= r[0] ^ r[4];
1.133 +
1.134 + r[5] ^= zm[3];
1.135 + r[4] ^= zm[2];
1.136 + r[3] ^= zm[1];
1.137 + r[2] ^= zm[0];
1.138 +}
1.139 +
1.140 +/* Compute xor-multiply of two binary polynomials (a3, a2, a1, a0) x (b3, b2, b1, b0)
1.141 + * result is a binary polynomial in 8 mp_digits r[8].
1.142 + * The caller MUST ensure that r has the right amount of space allocated.
1.143 + */
1.144 +void s_bmul_4x4(mp_digit *r, const mp_digit a3, const mp_digit a2, const mp_digit a1,
1.145 + const mp_digit a0, const mp_digit b3, const mp_digit b2, const mp_digit b1,
1.146 + const mp_digit b0)
1.147 +{
1.148 + mp_digit zm[4];
1.149 +
1.150 + s_bmul_2x2(r+4, a3, a2, b3, b2); /* fill top 4 words */
1.151 + s_bmul_2x2(zm, a3^a1, a2^a0, b3^b1, b2^b0); /* fill middle 4 words */
1.152 + s_bmul_2x2(r, a1, a0, b1, b0); /* fill bottom 4 words */
1.153 +
1.154 + zm[3] ^= r[3] ^ r[7];
1.155 + zm[2] ^= r[2] ^ r[6];
1.156 + zm[1] ^= r[1] ^ r[5];
1.157 + zm[0] ^= r[0] ^ r[4];
1.158 +
1.159 + r[5] ^= zm[3];
1.160 + r[4] ^= zm[2];
1.161 + r[3] ^= zm[1];
1.162 + r[2] ^= zm[0];
1.163 +}
1.164 +
1.165 +/* Compute addition of two binary polynomials a and b,
1.166 + * store result in c; c could be a or b, a and b could be equal;
1.167 + * c is the bitwise XOR of a and b.
1.168 + */
1.169 +mp_err
1.170 +mp_badd(const mp_int *a, const mp_int *b, mp_int *c)
1.171 +{
1.172 + mp_digit *pa, *pb, *pc;
1.173 + mp_size ix;
1.174 + mp_size used_pa, used_pb;
1.175 + mp_err res = MP_OKAY;
1.176 +
1.177 + /* Add all digits up to the precision of b. If b had more
1.178 + * precision than a initially, swap a, b first
1.179 + */
1.180 + if (MP_USED(a) >= MP_USED(b)) {
1.181 + pa = MP_DIGITS(a);
1.182 + pb = MP_DIGITS(b);
1.183 + used_pa = MP_USED(a);
1.184 + used_pb = MP_USED(b);
1.185 + } else {
1.186 + pa = MP_DIGITS(b);
1.187 + pb = MP_DIGITS(a);
1.188 + used_pa = MP_USED(b);
1.189 + used_pb = MP_USED(a);
1.190 + }
1.191 +
1.192 + /* Make sure c has enough precision for the output value */
1.193 + MP_CHECKOK( s_mp_pad(c, used_pa) );
1.194 +
1.195 + /* Do word-by-word xor */
1.196 + pc = MP_DIGITS(c);
1.197 + for (ix = 0; ix < used_pb; ix++) {
1.198 + (*pc++) = (*pa++) ^ (*pb++);
1.199 + }
1.200 +
1.201 + /* Finish the rest of digits until we're actually done */
1.202 + for (; ix < used_pa; ++ix) {
1.203 + *pc++ = *pa++;
1.204 + }
1.205 +
1.206 + MP_USED(c) = used_pa;
1.207 + MP_SIGN(c) = ZPOS;
1.208 + s_mp_clamp(c);
1.209 +
1.210 +CLEANUP:
1.211 + return res;
1.212 +}
1.213 +
1.214 +#define s_mp_div2(a) MP_CHECKOK( mpl_rsh((a), (a), 1) );
1.215 +
1.216 +/* Compute binary polynomial multiply d = a * b */
1.217 +static void
1.218 +s_bmul_d(const mp_digit *a, mp_size a_len, mp_digit b, mp_digit *d)
1.219 +{
1.220 + mp_digit a_i, a0b0, a1b1, carry = 0;
1.221 + while (a_len--) {
1.222 + a_i = *a++;
1.223 + s_bmul_1x1(&a1b1, &a0b0, a_i, b);
1.224 + *d++ = a0b0 ^ carry;
1.225 + carry = a1b1;
1.226 + }
1.227 + *d = carry;
1.228 +}
1.229 +
1.230 +/* Compute binary polynomial xor multiply accumulate d ^= a * b */
1.231 +static void
1.232 +s_bmul_d_add(const mp_digit *a, mp_size a_len, mp_digit b, mp_digit *d)
1.233 +{
1.234 + mp_digit a_i, a0b0, a1b1, carry = 0;
1.235 + while (a_len--) {
1.236 + a_i = *a++;
1.237 + s_bmul_1x1(&a1b1, &a0b0, a_i, b);
1.238 + *d++ ^= a0b0 ^ carry;
1.239 + carry = a1b1;
1.240 + }
1.241 + *d ^= carry;
1.242 +}
1.243 +
1.244 +/* Compute binary polynomial xor multiply c = a * b.
1.245 + * All parameters may be identical.
1.246 + */
1.247 +mp_err
1.248 +mp_bmul(const mp_int *a, const mp_int *b, mp_int *c)
1.249 +{
1.250 + mp_digit *pb, b_i;
1.251 + mp_int tmp;
1.252 + mp_size ib, a_used, b_used;
1.253 + mp_err res = MP_OKAY;
1.254 +
1.255 + MP_DIGITS(&tmp) = 0;
1.256 +
1.257 + ARGCHK(a != NULL && b != NULL && c != NULL, MP_BADARG);
1.258 +
1.259 + if (a == c) {
1.260 + MP_CHECKOK( mp_init_copy(&tmp, a) );
1.261 + if (a == b)
1.262 + b = &tmp;
1.263 + a = &tmp;
1.264 + } else if (b == c) {
1.265 + MP_CHECKOK( mp_init_copy(&tmp, b) );
1.266 + b = &tmp;
1.267 + }
1.268 +
1.269 + if (MP_USED(a) < MP_USED(b)) {
1.270 + const mp_int *xch = b; /* switch a and b if b longer */
1.271 + b = a;
1.272 + a = xch;
1.273 + }
1.274 +
1.275 + MP_USED(c) = 1; MP_DIGIT(c, 0) = 0;
1.276 + MP_CHECKOK( s_mp_pad(c, USED(a) + USED(b)) );
1.277 +
1.278 + pb = MP_DIGITS(b);
1.279 + s_bmul_d(MP_DIGITS(a), MP_USED(a), *pb++, MP_DIGITS(c));
1.280 +
1.281 + /* Outer loop: Digits of b */
1.282 + a_used = MP_USED(a);
1.283 + b_used = MP_USED(b);
1.284 + MP_USED(c) = a_used + b_used;
1.285 + for (ib = 1; ib < b_used; ib++) {
1.286 + b_i = *pb++;
1.287 +
1.288 + /* Inner product: Digits of a */
1.289 + if (b_i)
1.290 + s_bmul_d_add(MP_DIGITS(a), a_used, b_i, MP_DIGITS(c) + ib);
1.291 + else
1.292 + MP_DIGIT(c, ib + a_used) = b_i;
1.293 + }
1.294 +
1.295 + s_mp_clamp(c);
1.296 +
1.297 + SIGN(c) = ZPOS;
1.298 +
1.299 +CLEANUP:
1.300 + mp_clear(&tmp);
1.301 + return res;
1.302 +}
1.303 +
1.304 +
1.305 +/* Compute modular reduction of a and store result in r.
1.306 + * r could be a.
1.307 + * For modular arithmetic, the irreducible polynomial f(t) is represented
1.308 + * as an array of int[], where f(t) is of the form:
1.309 + * f(t) = t^p[0] + t^p[1] + ... + t^p[k]
1.310 + * where m = p[0] > p[1] > ... > p[k] = 0.
1.311 + */
1.312 +mp_err
1.313 +mp_bmod(const mp_int *a, const unsigned int p[], mp_int *r)
1.314 +{
1.315 + int j, k;
1.316 + int n, dN, d0, d1;
1.317 + mp_digit zz, *z, tmp;
1.318 + mp_size used;
1.319 + mp_err res = MP_OKAY;
1.320 +
1.321 + /* The algorithm does the reduction in place in r,
1.322 + * if a != r, copy a into r first so reduction can be done in r
1.323 + */
1.324 + if (a != r) {
1.325 + MP_CHECKOK( mp_copy(a, r) );
1.326 + }
1.327 + z = MP_DIGITS(r);
1.328 +
1.329 + /* start reduction */
1.330 + /*dN = p[0] / MP_DIGIT_BITS; */
1.331 + dN = p[0] >> MP_DIGIT_BITS_LOG_2;
1.332 + used = MP_USED(r);
1.333 +
1.334 + for (j = used - 1; j > dN;) {
1.335 +
1.336 + zz = z[j];
1.337 + if (zz == 0) {
1.338 + j--; continue;
1.339 + }
1.340 + z[j] = 0;
1.341 +
1.342 + for (k = 1; p[k] > 0; k++) {
1.343 + /* reducing component t^p[k] */
1.344 + n = p[0] - p[k];
1.345 + /*d0 = n % MP_DIGIT_BITS; */
1.346 + d0 = n & MP_DIGIT_BITS_MASK;
1.347 + d1 = MP_DIGIT_BITS - d0;
1.348 + /*n /= MP_DIGIT_BITS; */
1.349 + n >>= MP_DIGIT_BITS_LOG_2;
1.350 + z[j-n] ^= (zz>>d0);
1.351 + if (d0)
1.352 + z[j-n-1] ^= (zz<<d1);
1.353 + }
1.354 +
1.355 + /* reducing component t^0 */
1.356 + n = dN;
1.357 + /*d0 = p[0] % MP_DIGIT_BITS;*/
1.358 + d0 = p[0] & MP_DIGIT_BITS_MASK;
1.359 + d1 = MP_DIGIT_BITS - d0;
1.360 + z[j-n] ^= (zz >> d0);
1.361 + if (d0)
1.362 + z[j-n-1] ^= (zz << d1);
1.363 +
1.364 + }
1.365 +
1.366 + /* final round of reduction */
1.367 + while (j == dN) {
1.368 +
1.369 + /* d0 = p[0] % MP_DIGIT_BITS; */
1.370 + d0 = p[0] & MP_DIGIT_BITS_MASK;
1.371 + zz = z[dN] >> d0;
1.372 + if (zz == 0) break;
1.373 + d1 = MP_DIGIT_BITS - d0;
1.374 +
1.375 + /* clear up the top d1 bits */
1.376 + if (d0) {
1.377 + z[dN] = (z[dN] << d1) >> d1;
1.378 + } else {
1.379 + z[dN] = 0;
1.380 + }
1.381 + *z ^= zz; /* reduction t^0 component */
1.382 +
1.383 + for (k = 1; p[k] > 0; k++) {
1.384 + /* reducing component t^p[k]*/
1.385 + /* n = p[k] / MP_DIGIT_BITS; */
1.386 + n = p[k] >> MP_DIGIT_BITS_LOG_2;
1.387 + /* d0 = p[k] % MP_DIGIT_BITS; */
1.388 + d0 = p[k] & MP_DIGIT_BITS_MASK;
1.389 + d1 = MP_DIGIT_BITS - d0;
1.390 + z[n] ^= (zz << d0);
1.391 + tmp = zz >> d1;
1.392 + if (d0 && tmp)
1.393 + z[n+1] ^= tmp;
1.394 + }
1.395 + }
1.396 +
1.397 + s_mp_clamp(r);
1.398 +CLEANUP:
1.399 + return res;
1.400 +}
1.401 +
1.402 +/* Compute the product of two polynomials a and b, reduce modulo p,
1.403 + * Store the result in r. r could be a or b; a could be b.
1.404 + */
1.405 +mp_err
1.406 +mp_bmulmod(const mp_int *a, const mp_int *b, const unsigned int p[], mp_int *r)
1.407 +{
1.408 + mp_err res;
1.409 +
1.410 + if (a == b) return mp_bsqrmod(a, p, r);
1.411 + if ((res = mp_bmul(a, b, r) ) != MP_OKAY)
1.412 + return res;
1.413 + return mp_bmod(r, p, r);
1.414 +}
1.415 +
1.416 +/* Compute binary polynomial squaring c = a*a mod p .
1.417 + * Parameter r and a can be identical.
1.418 + */
1.419 +
1.420 +mp_err
1.421 +mp_bsqrmod(const mp_int *a, const unsigned int p[], mp_int *r)
1.422 +{
1.423 + mp_digit *pa, *pr, a_i;
1.424 + mp_int tmp;
1.425 + mp_size ia, a_used;
1.426 + mp_err res;
1.427 +
1.428 + ARGCHK(a != NULL && r != NULL, MP_BADARG);
1.429 + MP_DIGITS(&tmp) = 0;
1.430 +
1.431 + if (a == r) {
1.432 + MP_CHECKOK( mp_init_copy(&tmp, a) );
1.433 + a = &tmp;
1.434 + }
1.435 +
1.436 + MP_USED(r) = 1; MP_DIGIT(r, 0) = 0;
1.437 + MP_CHECKOK( s_mp_pad(r, 2*USED(a)) );
1.438 +
1.439 + pa = MP_DIGITS(a);
1.440 + pr = MP_DIGITS(r);
1.441 + a_used = MP_USED(a);
1.442 + MP_USED(r) = 2 * a_used;
1.443 +
1.444 + for (ia = 0; ia < a_used; ia++) {
1.445 + a_i = *pa++;
1.446 + *pr++ = gf2m_SQR0(a_i);
1.447 + *pr++ = gf2m_SQR1(a_i);
1.448 + }
1.449 +
1.450 + MP_CHECKOK( mp_bmod(r, p, r) );
1.451 + s_mp_clamp(r);
1.452 + SIGN(r) = ZPOS;
1.453 +
1.454 +CLEANUP:
1.455 + mp_clear(&tmp);
1.456 + return res;
1.457 +}
1.458 +
1.459 +/* Compute binary polynomial y/x mod p, y divided by x, reduce modulo p.
1.460 + * Store the result in r. r could be x or y, and x could equal y.
1.461 + * Uses algorithm Modular_Division_GF(2^m) from
1.462 + * Chang-Shantz, S. "From Euclid's GCD to Montgomery Multiplication to
1.463 + * the Great Divide".
1.464 + */
1.465 +int
1.466 +mp_bdivmod(const mp_int *y, const mp_int *x, const mp_int *pp,
1.467 + const unsigned int p[], mp_int *r)
1.468 +{
1.469 + mp_int aa, bb, uu;
1.470 + mp_int *a, *b, *u, *v;
1.471 + mp_err res = MP_OKAY;
1.472 +
1.473 + MP_DIGITS(&aa) = 0;
1.474 + MP_DIGITS(&bb) = 0;
1.475 + MP_DIGITS(&uu) = 0;
1.476 +
1.477 + MP_CHECKOK( mp_init_copy(&aa, x) );
1.478 + MP_CHECKOK( mp_init_copy(&uu, y) );
1.479 + MP_CHECKOK( mp_init_copy(&bb, pp) );
1.480 + MP_CHECKOK( s_mp_pad(r, USED(pp)) );
1.481 + MP_USED(r) = 1; MP_DIGIT(r, 0) = 0;
1.482 +
1.483 + a = &aa; b= &bb; u=&uu; v=r;
1.484 + /* reduce x and y mod p */
1.485 + MP_CHECKOK( mp_bmod(a, p, a) );
1.486 + MP_CHECKOK( mp_bmod(u, p, u) );
1.487 +
1.488 + while (!mp_isodd(a)) {
1.489 + s_mp_div2(a);
1.490 + if (mp_isodd(u)) {
1.491 + MP_CHECKOK( mp_badd(u, pp, u) );
1.492 + }
1.493 + s_mp_div2(u);
1.494 + }
1.495 +
1.496 + do {
1.497 + if (mp_cmp_mag(b, a) > 0) {
1.498 + MP_CHECKOK( mp_badd(b, a, b) );
1.499 + MP_CHECKOK( mp_badd(v, u, v) );
1.500 + do {
1.501 + s_mp_div2(b);
1.502 + if (mp_isodd(v)) {
1.503 + MP_CHECKOK( mp_badd(v, pp, v) );
1.504 + }
1.505 + s_mp_div2(v);
1.506 + } while (!mp_isodd(b));
1.507 + }
1.508 + else if ((MP_DIGIT(a,0) == 1) && (MP_USED(a) == 1))
1.509 + break;
1.510 + else {
1.511 + MP_CHECKOK( mp_badd(a, b, a) );
1.512 + MP_CHECKOK( mp_badd(u, v, u) );
1.513 + do {
1.514 + s_mp_div2(a);
1.515 + if (mp_isodd(u)) {
1.516 + MP_CHECKOK( mp_badd(u, pp, u) );
1.517 + }
1.518 + s_mp_div2(u);
1.519 + } while (!mp_isodd(a));
1.520 + }
1.521 + } while (1);
1.522 +
1.523 + MP_CHECKOK( mp_copy(u, r) );
1.524 +
1.525 +CLEANUP:
1.526 + mp_clear(&aa);
1.527 + mp_clear(&bb);
1.528 + mp_clear(&uu);
1.529 + return res;
1.530 +
1.531 +}
1.532 +
1.533 +/* Convert the bit-string representation of a polynomial a into an array
1.534 + * of integers corresponding to the bits with non-zero coefficient.
1.535 + * Up to max elements of the array will be filled. Return value is total
1.536 + * number of coefficients that would be extracted if array was large enough.
1.537 + */
1.538 +int
1.539 +mp_bpoly2arr(const mp_int *a, unsigned int p[], int max)
1.540 +{
1.541 + int i, j, k;
1.542 + mp_digit top_bit, mask;
1.543 +
1.544 + top_bit = 1;
1.545 + top_bit <<= MP_DIGIT_BIT - 1;
1.546 +
1.547 + for (k = 0; k < max; k++) p[k] = 0;
1.548 + k = 0;
1.549 +
1.550 + for (i = MP_USED(a) - 1; i >= 0; i--) {
1.551 + mask = top_bit;
1.552 + for (j = MP_DIGIT_BIT - 1; j >= 0; j--) {
1.553 + if (MP_DIGITS(a)[i] & mask) {
1.554 + if (k < max) p[k] = MP_DIGIT_BIT * i + j;
1.555 + k++;
1.556 + }
1.557 + mask >>= 1;
1.558 + }
1.559 + }
1.560 +
1.561 + return k;
1.562 +}
1.563 +
1.564 +/* Convert the coefficient array representation of a polynomial to a
1.565 + * bit-string. The array must be terminated by 0.
1.566 + */
1.567 +mp_err
1.568 +mp_barr2poly(const unsigned int p[], mp_int *a)
1.569 +{
1.570 +
1.571 + mp_err res = MP_OKAY;
1.572 + int i;
1.573 +
1.574 + mp_zero(a);
1.575 + for (i = 0; p[i] > 0; i++) {
1.576 + MP_CHECKOK( mpl_set_bit(a, p[i], 1) );
1.577 + }
1.578 + MP_CHECKOK( mpl_set_bit(a, 0, 1) );
1.579 +
1.580 +CLEANUP:
1.581 + return res;
1.582 +}
