Lines Matching refs:a
124 #define mp_iszero(a) (((a)->used == 0) ? MP_YES : MP_NO) argument
125 #define mp_iseven(a) (((a)->used > 0 && (((a)->dp[0] & 1) == 0)) ? MP_YES : MP_NO) argument
126 #define mp_isodd(a) (((a)->used > 0 && (((a)->dp[0] & 1) == 1)) ? MP_YES : MP_NO) argument
130 #define s_mp_mul(a, b, c) s_mp_mul_digs(a, b, c, (a)->used + (b)->used + 1) argument
132 static int s_mp_mul_digs (mp_int * a, mp_int * b, mp_int * c, int digs);
133 static int s_mp_sqr(mp_int * a, mp_int * b);
134 static int s_mp_mul_high_digs(mp_int * a, mp_int * b, mp_int * c, int digs);
136 static int fast_s_mp_mul_digs (mp_int * a, mp_int * b, mp_int * c, int digs);
144 static int mp_lshd(mp_int * a, int b);
145 static void mp_set(mp_int * a, mp_digit b);
146 static void mp_clamp(mp_int * a);
147 static void mp_exch(mp_int * a, mp_int * b);
148 static void mp_rshd(mp_int * a, int b);
149 static void mp_zero(mp_int * a);
150 static int mp_mod_2d(mp_int * a, int b, mp_int * c);
151 static int mp_div_2d(mp_int * a, int b, mp_int * c, mp_int * d);
152 static int mp_init_copy(mp_int * a, mp_int * b);
153 static int mp_mul_2d(mp_int * a, int b, mp_int * c);
155 static int mp_div_2(mp_int * a, mp_int * b);
156 static int mp_invmod(mp_int * a, mp_int * b, mp_int * c);
157 static int mp_invmod_slow(mp_int * a, mp_int * b, mp_int * c);
159 static int mp_copy(mp_int * a, mp_int * b);
160 static int mp_count_bits(mp_int * a);
161 static int mp_div(mp_int * a, mp_int * b, mp_int * c, mp_int * d);
162 static int mp_mod(mp_int * a, mp_int * b, mp_int * c);
163 static int mp_grow(mp_int * a, int size);
164 static int mp_cmp_mag(mp_int * a, mp_int * b);
166 static int mp_abs(mp_int * a, mp_int * b);
168 static int mp_sqr(mp_int * a, mp_int * b);
169 static int mp_reduce_2k_l(mp_int *a, mp_int *n, mp_int *d);
170 static int mp_reduce_2k_setup_l(mp_int *a, mp_int *d);
171 static int mp_2expt(mp_int * a, int b);
172 static int mp_reduce_setup(mp_int * a, mp_int * b);
174 static int mp_init_size(mp_int * a, int size);
179 static int fast_s_mp_sqr (mp_int * a, mp_int * b);
182 static int mp_mul_d (mp_int * a, mp_digit b, mp_int * c);
211 s_mp_add (mp_int * a, mp_int * b, mp_int * c) in s_mp_add() argument
219 if (a->used > b->used) { in s_mp_add()
221 max = a->used; in s_mp_add()
222 x = a; in s_mp_add()
224 min = a->used; in s_mp_add()
247 tmpa = a->dp; in s_mp_add()
300 s_mp_sub (mp_int * a, mp_int * b, mp_int * c) in s_mp_sub() argument
306 max = a->used; in s_mp_sub()
322 tmpa = a->dp; in s_mp_sub()
368 mp_init (mp_int * a) in mp_init() argument
373 a->dp = OPT_CAST(mp_digit) XMALLOC (sizeof (mp_digit) * MP_PREC); in mp_init()
374 if (a->dp == NULL) { in mp_init()
380 a->dp[i] = 0; in mp_init()
385 a->used = 0; in mp_init()
386 a->alloc = MP_PREC; in mp_init()
387 a->sign = MP_ZPOS; in mp_init()
395 mp_clear (mp_int * a) in mp_clear() argument
400 if (a->dp != NULL) { in mp_clear()
402 for (i = 0; i < a->used; i++) { in mp_clear()
403 a->dp[i] = 0; in mp_clear()
407 XFREE(a->dp); in mp_clear()
410 a->dp = NULL; in mp_clear()
411 a->alloc = a->used = 0; in mp_clear()
412 a->sign = MP_ZPOS; in mp_clear()
419 mp_add (mp_int * a, mp_int * b, mp_int * c) in mp_add() argument
424 sa = a->sign; in mp_add()
432 res = s_mp_add (a, b, c); in mp_add()
438 if (mp_cmp_mag (a, b) == MP_LT) { in mp_add()
440 res = s_mp_sub (b, a, c); in mp_add()
443 res = s_mp_sub (a, b, c); in mp_add()
452 mp_sub (mp_int * a, mp_int * b, mp_int * c) in mp_sub() argument
456 sa = a->sign; in mp_sub()
465 res = s_mp_add (a, b, c); in mp_sub()
471 if (mp_cmp_mag (a, b) != MP_LT) { in mp_sub()
475 res = s_mp_sub (a, b, c); in mp_sub()
481 res = s_mp_sub (b, a, c); in mp_sub()
490 mp_mul (mp_int * a, mp_int * b, mp_int * c) in mp_mul() argument
493 neg = (a->sign == b->sign) ? MP_ZPOS : MP_NEG; in mp_mul()
497 if (MIN (a->used, b->used) >= TOOM_MUL_CUTOFF) { in mp_mul()
498 res = mp_toom_mul(a, b, c); in mp_mul()
503 if (MIN (a->used, b->used) >= KARATSUBA_MUL_CUTOFF) { in mp_mul()
504 res = mp_karatsuba_mul (a, b, c); in mp_mul()
515 int digs = a->used + b->used + 1; in mp_mul()
518 MIN(a->used, b->used) <= in mp_mul()
520 res = fast_s_mp_mul_digs (a, b, c, digs); in mp_mul()
524 res = s_mp_mul (a, b, c); /* uses s_mp_mul_digs */ in mp_mul()
538 mp_mulmod (mp_int * a, mp_int * b, mp_int * c, mp_int * d) in mp_mulmod() argument
547 if ((res = mp_mul (a, b, &t)) != MP_OKAY) { in mp_mulmod()
559 mp_mod (mp_int * a, mp_int * b, mp_int * c) in mp_mod() argument
568 if ((res = mp_div (a, b, NULL, &t)) != MP_OKAY) { in mp_mod()
683 mp_cmp (mp_int * a, mp_int * b) in mp_cmp() argument
686 if (a->sign != b->sign) { in mp_cmp()
687 if (a->sign == MP_NEG) { in mp_cmp()
695 if (a->sign == MP_NEG) { in mp_cmp()
697 return mp_cmp_mag(b, a); in mp_cmp()
699 return mp_cmp_mag(a, b); in mp_cmp()
706 mp_cmp_d(mp_int * a, mp_digit b) in mp_cmp_d() argument
709 if (a->sign == MP_NEG) { in mp_cmp_d()
714 if (a->used > 1) { in mp_cmp_d()
719 if (a->dp[0] > b) { in mp_cmp_d()
721 } else if (a->dp[0] < b) { in mp_cmp_d()
732 mp_invmod (mp_int * a, mp_int * b, mp_int * c) in mp_invmod() argument
742 return fast_mp_invmod (a, b, c); in mp_invmod()
747 return mp_invmod_slow(a, b, c); in mp_invmod()
762 mp_unsigned_bin_size (mp_int * a) in mp_unsigned_bin_size() argument
764 int size = mp_count_bits (a); in mp_unsigned_bin_size()
772 mp_invmod_slow (mp_int * a, mp_int * b, mp_int * c) in mp_invmod_slow() argument
789 if ((res = mp_mod(a, b, &x)) != MP_OKAY) { in mp_invmod_slow()
929 mp_cmp_mag (mp_int * a, mp_int * b) in mp_cmp_mag() argument
935 if (a->used > b->used) { in mp_cmp_mag()
939 if (a->used < b->used) { in mp_cmp_mag()
944 tmpa = a->dp + (a->used - 1); in mp_cmp_mag()
947 tmpb = b->dp + (a->used - 1); in mp_cmp_mag()
950 for (n = 0; n < a->used; ++n, --tmpa, --tmpb) { in mp_cmp_mag()
965 mp_read_unsigned_bin (mp_int * a, const unsigned char *b, int c) in mp_read_unsigned_bin() argument
970 if (a->alloc < 2) { in mp_read_unsigned_bin()
971 if ((res = mp_grow(a, 2)) != MP_OKAY) { in mp_read_unsigned_bin()
977 mp_zero (a); in mp_read_unsigned_bin()
981 if ((res = mp_mul_2d (a, 8, a)) != MP_OKAY) { in mp_read_unsigned_bin()
986 a->dp[0] |= *b++; in mp_read_unsigned_bin()
987 a->used += 1; in mp_read_unsigned_bin()
989 a->dp[0] = (*b & MP_MASK); in mp_read_unsigned_bin()
990 a->dp[1] |= ((*b++ >> 7U) & 1); in mp_read_unsigned_bin()
991 a->used += 2; in mp_read_unsigned_bin()
994 mp_clamp (a); in mp_read_unsigned_bin()
1001 mp_to_unsigned_bin (mp_int * a, unsigned char *b) in mp_to_unsigned_bin() argument
1006 if ((res = mp_init_copy (&t, a)) != MP_OKAY) { in mp_to_unsigned_bin()
1030 mp_div_2d (mp_int * a, int b, mp_int * c, mp_int * d) in mp_div_2d() argument
1039 res = mp_copy (a, c); in mp_div_2d()
1052 if ((res = mp_mod_2d (a, b, &t)) != MP_OKAY) { in mp_div_2d()
1059 if ((res = mp_copy (a, c)) != MP_OKAY) { in mp_div_2d()
1107 mp_init_copy (mp_int * a, mp_int * b) in mp_init_copy() argument
1111 if ((res = mp_init (a)) != MP_OKAY) { in mp_init_copy()
1114 return mp_copy (b, a); in mp_init_copy()
1120 mp_zero (mp_int * a) in mp_zero() argument
1125 a->sign = MP_ZPOS; in mp_zero()
1126 a->used = 0; in mp_zero()
1128 tmp = a->dp; in mp_zero()
1129 for (n = 0; n < a->alloc; n++) { in mp_zero()
1137 mp_copy (mp_int * a, mp_int * b) in mp_copy() argument
1142 if (a == b) { in mp_copy()
1147 if (b->alloc < a->used) { in mp_copy()
1148 if ((res = mp_grow (b, a->used)) != MP_OKAY) { in mp_copy()
1160 tmpa = a->dp; in mp_copy()
1166 for (n = 0; n < a->used; n++) { in mp_copy()
1177 b->used = a->used; in mp_copy()
1178 b->sign = a->sign; in mp_copy()
1185 mp_rshd (mp_int * a, int b) in mp_rshd() argument
1195 if (a->used <= b) { in mp_rshd()
1196 mp_zero (a); in mp_rshd()
1206 bottom = a->dp; in mp_rshd()
1209 top = a->dp + b; in mp_rshd()
1221 for (x = 0; x < (a->used - b); x++) { in mp_rshd()
1226 for (; x < a->used; x++) { in mp_rshd()
1232 a->used -= b; in mp_rshd()
1240 mp_exch (mp_int * a, mp_int * b) in mp_exch() argument
1244 t = *a; in mp_exch()
1245 *a = *b; in mp_exch()
1258 mp_clamp (mp_int * a) in mp_clamp() argument
1263 while (a->used > 0 && a->dp[a->used - 1] == 0) { in mp_clamp()
1264 --(a->used); in mp_clamp()
1268 if (a->used == 0) { in mp_clamp()
1269 a->sign = MP_ZPOS; in mp_clamp()
1276 mp_grow (mp_int * a, int size) in mp_grow() argument
1282 if (a->alloc < size) { in mp_grow()
1292 tmp = OPT_CAST(mp_digit) XREALLOC (a->dp, sizeof (mp_digit) * size); in mp_grow()
1299 a->dp = tmp; in mp_grow()
1302 i = a->alloc; in mp_grow()
1303 a->alloc = size; in mp_grow()
1304 for (; i < a->alloc; i++) { in mp_grow()
1305 a->dp[i] = 0; in mp_grow()
1318 mp_abs (mp_int * a, mp_int * b) in mp_abs() argument
1323 if (a != b) { in mp_abs()
1324 if ((res = mp_copy (a, b)) != MP_OKAY) { in mp_abs()
1339 mp_set (mp_int * a, mp_digit b) in mp_set() argument
1341 mp_zero (a); in mp_set()
1342 a->dp[0] = b & MP_MASK; in mp_set()
1343 a->used = (a->dp[0] != 0) ? 1 : 0; in mp_set()
1350 mp_div_2(mp_int * a, mp_int * b) in mp_div_2() argument
1355 if (b->alloc < a->used) { in mp_div_2()
1356 if ((res = mp_grow (b, a->used)) != MP_OKAY) { in mp_div_2()
1362 b->used = a->used; in mp_div_2()
1367 tmpa = a->dp + b->used - 1; in mp_div_2()
1391 b->sign = a->sign; in mp_div_2()
1400 mp_mul_2d (mp_int * a, int b, mp_int * c) in mp_mul_2d() argument
1406 if (a != c) { in mp_mul_2d()
1407 if ((res = mp_copy (a, c)) != MP_OKAY) { in mp_mul_2d()
1522 mp_lshd (mp_int * a, int b) in mp_lshd() argument
1532 if (a->alloc < a->used + b) { in mp_lshd()
1533 if ((res = mp_grow (a, a->used + b)) != MP_OKAY) { in mp_lshd()
1542 a->used += b; in mp_lshd()
1545 top = a->dp + a->used - 1; in mp_lshd()
1548 bottom = a->dp + a->used - 1 - b; in mp_lshd()
1554 for (x = a->used - 1; x >= b; x--) { in mp_lshd()
1559 top = a->dp; in mp_lshd()
1570 mp_count_bits (mp_int * a) in mp_count_bits() argument
1576 if (a->used == 0) { in mp_count_bits()
1581 r = (a->used - 1) * DIGIT_BIT; in mp_count_bits()
1584 q = a->dp[a->used - 1]; in mp_count_bits()
1595 mp_mod_2d (mp_int * a, int b, mp_int * c) in mp_mod_2d() argument
1606 if (b >= (int) (a->used * DIGIT_BIT)) { in mp_mod_2d()
1607 res = mp_copy (a, c); in mp_mod_2d()
1612 if ((res = mp_copy (a, c)) != MP_OKAY) { in mp_mod_2d()
1632 mp_div(mp_int * a, mp_int * b, mp_int * c, mp_int * d) in mp_div() argument
1643 if (mp_cmp_mag (a, b) == MP_LT) { in mp_div()
1645 res = mp_copy (a, d); in mp_div()
1662 n = mp_count_bits(a) - mp_count_bits(b); in mp_div()
1663 if (((res = mp_abs(a, &ta)) != MP_OKAY) || in mp_div()
1684 n = a->sign; in mp_div()
1685 n2 = (a->sign == b->sign ? MP_ZPOS : MP_NEG); in mp_div()
1715 mp_div (mp_int * a, mp_int * b, mp_int * c, mp_int * d) in mp_div() argument
1726 if (mp_cmp_mag (a, b) == MP_LT) { in mp_div()
1728 res = mp_copy (a, d); in mp_div()
1738 if ((res = mp_init_size (&q, a->used + 2)) != MP_OKAY) { in mp_div()
1741 q.used = a->used + 2; in mp_div()
1751 if ((res = mp_init_copy (&x, a)) != MP_OKAY) { in mp_div()
1760 neg = (a->sign == b->sign) ? MP_ZPOS : MP_NEG; in mp_div()
1875 x.sign = x.used == 0 ? MP_ZPOS : a->sign; in mp_div()
2137 mp_sqr (mp_int * a, mp_int * b) in mp_sqr() argument
2143 if (a->used >= TOOM_SQR_CUTOFF) { in mp_sqr()
2144 res = mp_toom_sqr(a, b); in mp_sqr()
2149 if (a->used >= KARATSUBA_SQR_CUTOFF) { in mp_sqr()
2150 res = mp_karatsuba_sqr (a, b); in mp_sqr()
2156 if ((a->used * 2 + 1) < MP_WARRAY && in mp_sqr()
2157 a->used < in mp_sqr()
2159 res = fast_s_mp_sqr (a, b); in mp_sqr()
2163 res = s_mp_sqr (a, b); in mp_sqr()
2179 mp_reduce_2k_l(mp_int *a, mp_int *n, mp_int *d) in mp_reduce_2k_l() argument
2191 if ((res = mp_div_2d(a, p, &q, a)) != MP_OKAY) { in mp_reduce_2k_l()
2201 if ((res = s_mp_add(a, &q, a)) != MP_OKAY) { in mp_reduce_2k_l()
2205 if (mp_cmp_mag(a, n) != MP_LT) { in mp_reduce_2k_l()
2206 s_mp_sub(a, n, a); in mp_reduce_2k_l()
2218 mp_reduce_2k_setup_l(mp_int *a, mp_int *d) in mp_reduce_2k_setup_l() argument
2227 if ((res = mp_2expt(&tmp, mp_count_bits(a))) != MP_OKAY) { in mp_reduce_2k_setup_l()
2231 if ((res = s_mp_sub(&tmp, a, d)) != MP_OKAY) { in mp_reduce_2k_setup_l()
2247 mp_2expt (mp_int * a, int b) in mp_2expt() argument
2252 mp_zero (a); in mp_2expt()
2255 if ((res = mp_grow (a, b / DIGIT_BIT + 1)) != MP_OKAY) { in mp_2expt()
2260 a->used = b / DIGIT_BIT + 1; in mp_2expt()
2263 a->dp[b / DIGIT_BIT] = ((mp_digit)1) << (b % DIGIT_BIT); in mp_2expt()
2273 mp_reduce_setup (mp_int * a, mp_int * b) in mp_reduce_setup() argument
2277 if ((res = mp_2expt (a, b->used * 2 * DIGIT_BIT)) != MP_OKAY) { in mp_reduce_setup()
2280 return mp_div (a, b, a, NULL); in mp_reduce_setup()
2373 s_mp_mul_digs (mp_int * a, mp_int * b, mp_int * c, int digs) in s_mp_mul_digs() argument
2383 MIN (a->used, b->used) < in s_mp_mul_digs()
2385 return fast_s_mp_mul_digs (a, b, c, digs); in s_mp_mul_digs()
2394 pa = a->used; in s_mp_mul_digs()
2404 tmpx = a->dp[ix]; in s_mp_mul_digs()
2456 fast_s_mp_mul_digs (mp_int * a, mp_int * b, mp_int * c, int digs) in fast_s_mp_mul_digs() argument
2470 pa = MIN(digs, a->used + b->used); in fast_s_mp_mul_digs()
2484 tmpx = a->dp + tx; in fast_s_mp_mul_digs()
2490 iy = MIN(a->used-tx, ty+1); in fast_s_mp_mul_digs()
2529 mp_init_size (mp_int * a, int size) in mp_init_size() argument
2537 a->dp = OPT_CAST(mp_digit) XMALLOC (sizeof (mp_digit) * size); in mp_init_size()
2538 if (a->dp == NULL) { in mp_init_size()
2543 a->used = 0; in mp_init_size()
2544 a->alloc = size; in mp_init_size()
2545 a->sign = MP_ZPOS; in mp_init_size()
2549 a->dp[x] = 0; in mp_init_size()
2558 s_mp_sqr (mp_int * a, mp_int * b) in s_mp_sqr() argument
2565 pa = a->used; in s_mp_sqr()
2577 ((mp_word)a->dp[ix])*((mp_word)a->dp[ix]); in s_mp_sqr()
2586 tmpx = a->dp[ix]; in s_mp_sqr()
2593 r = ((mp_word)tmpx) * ((mp_word)a->dp[iy]); in s_mp_sqr()
2625 s_mp_mul_high_digs (mp_int * a, mp_int * b, mp_int * c, int digs) in s_mp_mul_high_digs() argument
2635 if (((a->used + b->used + 1) < MP_WARRAY) in s_mp_mul_high_digs()
2636 && MIN (a->used, b->used) < (1 << ((CHAR_BIT * sizeof (mp_word)) - (2 * DIGIT_BIT)))) { in s_mp_mul_high_digs()
2637 return fast_s_mp_mul_high_digs (a, b, c, digs); in s_mp_mul_high_digs()
2641 if ((res = mp_init_size (&t, a->used + b->used + 1)) != MP_OKAY) { in s_mp_mul_high_digs()
2644 t.used = a->used + b->used + 1; in s_mp_mul_high_digs()
2646 pa = a->used; in s_mp_mul_high_digs()
2653 tmpx = a->dp[ix]; in s_mp_mul_high_digs()
2881 mp_mul_2(mp_int * a, mp_int * b) in mp_mul_2() argument
2886 if (b->alloc < a->used + 1) { in mp_mul_2()
2887 if ((res = mp_grow (b, a->used + 1)) != MP_OKAY) { in mp_mul_2()
2893 b->used = a->used; in mp_mul_2()
2899 tmpa = a->dp; in mp_mul_2()
2906 for (x = 0; x < a->used; x++) { in mp_mul_2()
2937 b->sign = a->sign; in mp_mul_2()
2951 mp_montgomery_calc_normalization (mp_int * a, mp_int * b) in mp_montgomery_calc_normalization() argument
2959 if ((res = mp_2expt (a, (b->used - 1) * DIGIT_BIT + bits - 1)) != MP_OKAY) { in mp_montgomery_calc_normalization()
2963 mp_set(a, 1); in mp_montgomery_calc_normalization()
2970 if ((res = mp_mul_2 (a, a)) != MP_OKAY) { in mp_montgomery_calc_normalization()
2973 if (mp_cmp_mag (a, b) != MP_LT) { in mp_montgomery_calc_normalization()
2974 if ((res = s_mp_sub (a, b, a)) != MP_OKAY) { in mp_montgomery_calc_normalization()
3294 fast_s_mp_sqr (mp_int * a, mp_int * b) in fast_s_mp_sqr() argument
3301 pa = a->used + a->used; in fast_s_mp_sqr()
3319 ty = MIN(a->used-1, ix); in fast_s_mp_sqr()
3323 tmpx = a->dp + tx; in fast_s_mp_sqr()
3324 tmpy = a->dp + ty; in fast_s_mp_sqr()
3329 iy = MIN(a->used-tx, ty+1); in fast_s_mp_sqr()
3347 _W += ((mp_word)a->dp[ix>>1])*((mp_word)a->dp[ix>>1]); in fast_s_mp_sqr()
3359 b->used = a->used+a->used; in fast_s_mp_sqr()
3382 mp_mul_d (mp_int * a, mp_digit b, mp_int * c) in mp_mul_d() argument
3389 if (c->alloc < a->used + 1) { in mp_mul_d()
3390 if ((res = mp_grow (c, a->used + 1)) != MP_OKAY) { in mp_mul_d()
3399 c->sign = a->sign; in mp_mul_d()
3402 tmpa = a->dp; in mp_mul_d()
3411 for (ix = 0; ix < a->used; ix++) { in mp_mul_d()
3432 c->used = a->used + 1; in mp_mul_d()