Header And Logo
|
#include "postgres.h"#include "px.h"#include "imath.h"
Go to the source code of this file.
| #define ADD_WILL_OVERFLOW | ( | W, | ||
| V | ||||
| ) | ((MP_WORD_MAX - (V)) < (W)) |
| #define assert | ( | TEST | ) | Assert(TEST) |
Definition at line 37 of file imath.c.
Referenced by addchr(), addrange(), allocarc(), bracket(), brenext(), caltdissect(), carcsort(), cbracket(), cbrdissect(), ccondissect(), cdissect(), cfind(), cfindloop(), citerdissect(), cleanup(), clearcvec(), cloneouts(), cmtreefree(), colorcomplement(), combine(), compact(), copyins(), copyouts(), crevcondissect(), creviterdissect(), delsub(), deltraverse(), destroystate(), duptraverse(), eclass(), element(), find(), fixempties(), freearc(), freecnfa(), freecolor(), freelacons(), freestate(), getvacant(), IncreaseBuffer(), inet_cidr_pton_ipv4(), inet_net_pton_ipv4(), initialize(), lacon(), lexescape(), lexnest(), lexstart(), makesearch(), markst(), miss(), moresubs(), moveins(), moveouts(), mp_int_alloc(), newarc(), newcolor(), newdfa(), NewMetaString(), newstate(), newsub(), next(), nfanode(), nfatree(), nonword(), numst(), okcolors(), old_8_3_create_sequence_script(), parse(), parsebranch(), parseqatom(), pg_reg_colorisbegin(), pg_reg_colorisend(), pg_reg_getcharacters(), pg_reg_getfinalstate(), pg_reg_getinitialstate(), pg_reg_getnumcharacters(), pg_reg_getnumcolors(), pg_reg_getnumoutarcs(), pg_reg_getnumstates(), pg_reg_getoutarcs(), pg_regcomp(), pg_regexec(), pg_regprefix(), pickss(), pull(), pullback(), push(), pushfwd(), replaceempty(), s_alloc(), s_embar(), s_qsub(), s_realloc(), s_udiv(), s_usqr(), s_usub(), s_val2ch(), scanplain(), set_locale_and_encoding(), setcolor(), shortest(), skip(), specialcolors(), store_match(), subblock(), subcolor(), subrange(), subre(), subset(), uncolorchain(), word(), wordchrs(), and zaptreesubs().
| #define CHECK | ( | TEST | ) | assert(TEST) |
Definition at line 74 of file imath.c.
Referenced by mp_int_abs(), mp_int_add(), mp_int_compare(), mp_int_compare_value(), mp_int_copy(), mp_int_count_bits(), mp_int_div(), mp_int_div_pow2(), mp_int_egcd(), mp_int_expt(), mp_int_expt_value(), mp_int_exptmod(), mp_int_exptmod_known(), mp_int_gcd(), mp_int_init_copy(), mp_int_init_size(), mp_int_init_value(), mp_int_invmod(), mp_int_is_pow2(), mp_int_mul(), mp_int_mul_pow2(), mp_int_neg(), mp_int_read_binary(), mp_int_read_cstring(), mp_int_read_unsigned(), mp_int_redux_const(), mp_int_set_value(), mp_int_sqr(), mp_int_sqrt(), mp_int_string_len(), mp_int_sub(), mp_int_to_binary(), mp_int_to_int(), mp_int_to_string(), and mp_int_to_unsigned().
| #define CLAMP | ( | Z | ) |
do{mp_int z_=(Z);mp_size uz_=MP_USED(z_);mp_digit *dz_=MP_DIGITS(z_)+uz_-1;\ while(uz_ > 1 && (*dz_-- == 0)) --uz_;MP_USED(z_)=uz_;}while(0)
Definition at line 131 of file imath.c.
Referenced by mp_int_add(), mp_int_mul(), mp_int_read_cstring(), mp_int_sqr(), mp_int_sub(), s_ddiv(), s_qdiv(), s_qmod(), s_qmul(), s_qsub(), and s_udiv().
Definition at line 146 of file imath.c.
Referenced by mp_int_div(), mp_int_egcd(), mp_int_exptmod(), mp_int_exptmod_known(), mp_int_gcd(), mp_int_invmod(), mp_int_mod(), mp_int_neg(), mp_int_read_cstring(), mp_int_to_string(), and s_reduce().
| #define COPY | ( | P, | ||
| Q, | ||||
| S | ||||
| ) |
Definition at line 120 of file imath.c.
Referenced by mp_int_copy(), mp_int_init_copy(), s_kmul(), and s_ksqr().
| #define HIGH_BIT_SET | ( | W | ) | ((W) >> (MP_WORD_BIT - 1)) |
| #define LOWER_HALF | ( | W | ) | ((mp_digit)(W)) |
| #define MAX | ( | A, | ||
| B | ||||
| ) | ((B)>(A)?(B):(A)) |
Definition at line 139 of file imath.c.
Referenced by mp_int_add(), mp_int_init_copy(), mp_int_init_size(), mp_int_mul(), mp_int_sqr(), and mp_int_sub().
| #define MIN | ( | A, | ||
| B | ||||
| ) | ((B)<(A)?(B):(A)) |
Definition at line 138 of file imath.c.
Referenced by mp_int_egcd(), and mp_int_gcd().
| #define MP_CAP_DIGITS 1 |
Definition at line 70 of file imath.c.
Referenced by mp_int_to_string().
Definition at line 109 of file imath.c.
Referenced by mp_int_add_value(), mp_int_div_value(), mp_int_exptmod_bvalue(), mp_int_exptmod_evalue(), mp_int_mul_value(), mp_int_set_value(), mp_int_sub_value(), s_fake(), and s_vcmp().
| #define NRCHECK | ( | TEST | ) | assert(TEST) |
Definition at line 75 of file imath.c.
Referenced by mp_int_compare_unsigned(), mp_int_compare_zero(), mp_int_free(), mp_int_zero(), and mp_set_default_precision().
| #define ROUND_PREC | ( | P | ) | ((mp_size)(2*(((P)+1)/2))) |
Definition at line 113 of file imath.c.
Referenced by mp_int_init_size(), mp_int_mul(), mp_int_sqr(), mp_set_default_precision(), and s_pad().
| #define s_free | ( | P | ) | px_free(P) |
Definition at line 182 of file imath.c.
Referenced by mp_int_clear(), mp_int_mul(), mp_int_sqr(), and s_kmul().
| #define SETUP | ( | E, | ||
| C | ||||
| ) | do{if((res = (E)) != MP_OK) goto CLEANUP; ++(C);}while(0) |
Definition at line 143 of file imath.c.
Referenced by mp_int_div(), mp_int_egcd(), mp_int_exptmod(), mp_int_exptmod_known(), mp_int_sqrt(), and s_embar().
| #define TEMP | ( | K | ) | (temp + (K)) |
Definition at line 142 of file imath.c.
Referenced by mp_int_div(), mp_int_egcd(), mp_int_exptmod(), mp_int_exptmod_known(), mp_int_invmod(), mp_int_sqrt(), and s_embar().
| #define UMUL | ( | X, | ||
| Y, | ||||
| Z | ||||
| ) |
| #define UPPER_HALF | ( | W | ) | ((mp_word)((W) >> MP_DIGIT_BIT)) |
| #define USQR | ( | X, | ||
| Z | ||||
| ) |
| #define ZERO | ( | P, | ||
| S | ||||
| ) | do{mp_size i__=(S)*sizeof(mp_digit);mp_digit *p__=(P);memset(p__,0,i__);}while(0) |
Definition at line 116 of file imath.c.
Referenced by mp_int_mul(), mp_int_sqr(), s_2expt(), s_kmul(), s_ksqr(), s_qmul(), and s_udiv().
| const char* mp_error_string | ( | mp_result | res | ) |
Definition at line 2258 of file imath.c.
References NULL, s_error_msg, and s_unknown_err.
{
int ix;
if (res > 0)
return s_unknown_err;
res = -res;
for (ix = 0; ix < res && s_error_msg[ix] != NULL; ++ix)
;
if (s_error_msg[ix] != NULL)
return s_error_msg[ix];
else
return s_unknown_err;
}
| mp_size mp_get_default_precision | ( | void | ) |
| mp_size mp_get_multiply_threshold | ( | void | ) |
Definition at line 341 of file imath.c.
References multiply_threshold.
{
return multiply_threshold;
}
Definition at line 569 of file imath.c.
References CHECK, mp_int_copy(), MP_OK, MP_SIGN, MP_ZPOS, and NULL.
Referenced by mp_int_egcd(), and mp_int_gcd().
Definition at line 607 of file imath.c.
References CHECK, CLAMP, cmp(), mpz::digits, MAX, MP_DIGITS, MP_MEMORY, MP_OK, MP_SIGN, MP_USED, NULL, s_pad(), s_uadd(), s_ucmp(), and s_usub().
Referenced by mp_int_add_value(), mp_int_egcd(), mp_int_mod(), and mp_int_sqrt().
{
mp_size ua,
ub,
uc,
max;
CHECK(a != NULL && b != NULL && c != NULL);
ua = MP_USED(a);
ub = MP_USED(b);
uc = MP_USED(c);
max = MAX(ua, ub);
if (MP_SIGN(a) == MP_SIGN(b))
{
/* Same sign -- add magnitudes, preserve sign of addends */
mp_digit carry;
if (!s_pad(c, max))
return MP_MEMORY;
carry = s_uadd(MP_DIGITS(a), MP_DIGITS(b), MP_DIGITS(c), ua, ub);
uc = max;
if (carry)
{
if (!s_pad(c, max + 1))
return MP_MEMORY;
c->digits[max] = carry;
++uc;
}
MP_USED(c) = uc;
MP_SIGN(c) = MP_SIGN(a);
}
else
{
/* Different signs -- subtract magnitudes, preserve sign of greater */
mp_int x,
y;
int cmp = s_ucmp(a, b); /* magnitude comparison, sign ignored */
/* Set x to max(a, b), y to min(a, b) to simplify later code */
if (cmp >= 0)
{
x = a;
y = b;
}
else
{
x = b;
y = a;
}
if (!s_pad(c, MP_USED(x)))
return MP_MEMORY;
/* Subtract smaller from larger */
s_usub(MP_DIGITS(x), MP_DIGITS(y), MP_DIGITS(c), MP_USED(x), MP_USED(y));
MP_USED(c) = MP_USED(x);
CLAMP(c);
/* Give result the sign of the larger */
MP_SIGN(c) = MP_SIGN(x);
}
return MP_OK;
}
Definition at line 684 of file imath.c.
References mp_int_add(), MP_VALUE_DIGITS, and s_fake().
{
mpz_t vtmp;
mp_digit vbuf[MP_VALUE_DIGITS(value)];
s_fake(&vtmp, value, vbuf);
return mp_int_add(a, &vtmp, c);
}
| mp_int mp_int_alloc | ( | void | ) |
Definition at line 2169 of file imath.c.
References mp_int_count_bits(), and mp_int_unsigned_len().
{
mp_result res = mp_int_count_bits(z);
int bytes = mp_int_unsigned_len(z);
if (res <= 0)
return res;
bytes = (res + (CHAR_BIT - 1)) / CHAR_BIT;
/*
* If the highest-order bit falls exactly on a byte boundary, we need to
* pad with an extra byte so that the sign will be read correctly when
* reading it back in.
*/
if (bytes * CHAR_BIT == res)
++bytes;
return bytes;
}
| void mp_int_clear | ( | mp_int | z | ) |
Definition at line 478 of file imath.c.
References MP_DIGITS, NULL, and s_free.
Referenced by mp_int_div(), mp_int_div_value(), mp_int_egcd(), mp_int_expt(), mp_int_expt_value(), mp_int_exptmod(), mp_int_exptmod_known(), mp_int_free(), mp_int_gcd(), mp_int_invmod(), mp_int_mod(), mp_int_sqrt(), mp_int_to_string(), s_embar(), and s_udiv().
Definition at line 1241 of file imath.c.
References CHECK, cmp(), MP_SIGN, MP_ZPOS, NULL, and s_ucmp().
Referenced by mp_int_egcd(), and s_reduce().
{
mp_sign sa;
CHECK(a != NULL && b != NULL);
sa = MP_SIGN(a);
if (sa == MP_SIGN(b))
{
int cmp = s_ucmp(a, b);
/*
* If they're both zero or positive, the normal comparison applies; if
* both negative, the sense is reversed.
*/
if (sa == MP_ZPOS)
return cmp;
else
return -cmp;
}
else
{
if (sa == MP_ZPOS)
return 1;
else
return -1;
}
}
| int mp_int_compare_value | ( | mp_int | z, | |
| int | value | |||
| ) |
Definition at line 1305 of file imath.c.
References CHECK, MP_NEG, MP_SIGN, MP_ZPOS, NULL, and s_vcmp().
Referenced by mp_int_invmod(), and mp_int_to_int().
| int mp_int_compare_zero | ( | mp_int | z | ) |
Definition at line 510 of file imath.c.
References CHECK, COPY, MP_DIGITS, MP_MEMORY, MP_OK, MP_SIGN, MP_USED, NULL, and s_pad().
Referenced by mp_int_abs(), mp_int_div(), mp_int_div_pow2(), mp_int_egcd(), mp_int_exptmod(), mp_int_exptmod_known(), mp_int_gcd(), mp_int_invmod(), mp_int_mod(), mp_int_mul_pow2(), mp_int_neg(), mp_int_sqrt(), s_embar(), s_reduce(), and s_udiv().
Definition at line 2072 of file imath.c.
References CHECK, mpz::digits, MP_USED, and NULL.
Referenced by bn_to_mpi(), mp_int_binary_len(), mp_int_unsigned_len(), mpi_to_bn(), pgp_elgamal_encrypt(), and s_outlen().
Definition at line 954 of file imath.c.
References CHECK, CMPZ, mpz::digits, mp_int_clear(), mp_int_copy(), mp_int_init_copy(), mp_int_zero(), MP_NEG, MP_OK, MP_SIGN, MP_UNDEF, MP_ZPOS, NULL, s_isp2(), s_qdiv(), s_qmod(), s_ucmp(), s_udiv(), SETUP, and TEMP.
Referenced by mp_int_div_value(), mp_int_mod(), mp_int_sqrt(), and s_brmu().
{
int cmp,
last = 0,
lg;
mp_result res = MP_OK;
mpz_t temp[2];
mp_int qout,
rout;
mp_sign sa = MP_SIGN(a),
sb = MP_SIGN(b);
CHECK(a != NULL && b != NULL && q != r);
if (CMPZ(b) == 0)
return MP_UNDEF;
else if ((cmp = s_ucmp(a, b)) < 0)
{
/*
* If |a| < |b|, no division is required: q = 0, r = a
*/
if (r && (res = mp_int_copy(a, r)) != MP_OK)
return res;
if (q)
mp_int_zero(q);
return MP_OK;
}
else if (cmp == 0)
{
/*
* If |a| = |b|, no division is required: q = 1 or -1, r = 0
*/
if (r)
mp_int_zero(r);
if (q)
{
mp_int_zero(q);
q->digits[0] = 1;
if (sa != sb)
MP_SIGN(q) = MP_NEG;
}
return MP_OK;
}
/*
* When |a| > |b|, real division is required. We need someplace to store
* quotient and remainder, but q and r are allowed to be NULL or to
* overlap with the inputs.
*/
if ((lg = s_isp2(b)) < 0)
{
if (q && b != q && (res = mp_int_copy(a, q)) == MP_OK)
{
qout = q;
}
else
{
qout = TEMP(last);
SETUP(mp_int_init_copy(TEMP(last), a), last);
}
if (r && a != r && (res = mp_int_copy(b, r)) == MP_OK)
{
rout = r;
}
else
{
rout = TEMP(last);
SETUP(mp_int_init_copy(TEMP(last), b), last);
}
if ((res = s_udiv(qout, rout)) != MP_OK)
goto CLEANUP;
}
else
{
if (q && (res = mp_int_copy(a, q)) != MP_OK)
goto CLEANUP;
if (r && (res = mp_int_copy(a, r)) != MP_OK)
goto CLEANUP;
if (q)
s_qdiv(q, (mp_size) lg);
qout = q;
if (r)
s_qmod(r, (mp_size) lg);
rout = r;
}
/* Recompute signs for output */
if (rout)
{
MP_SIGN(rout) = sa;
if (CMPZ(rout) == 0)
MP_SIGN(rout) = MP_ZPOS;
}
if (qout)
{
MP_SIGN(qout) = (sa == sb) ? MP_ZPOS : MP_NEG;
if (CMPZ(qout) == 0)
MP_SIGN(qout) = MP_ZPOS;
}
if (q && (res = mp_int_copy(qout, q)) != MP_OK)
goto CLEANUP;
if (r && (res = mp_int_copy(rout, r)) != MP_OK)
goto CLEANUP;
CLEANUP:
while (--last >= 0)
mp_int_clear(TEMP(last));
return res;
}
Definition at line 1145 of file imath.c.
References CHECK, mp_int_copy(), MP_OK, NULL, s_qdiv(), and s_qmod().
Referenced by mp_int_sqrt().
Definition at line 1118 of file imath.c.
References mp_int_clear(), mp_int_div(), mp_int_init(), mp_int_to_int(), MP_OK, MP_VALUE_DIGITS, and s_fake().
Referenced by mp_int_divisible_value().
{
mpz_t vtmp,
rtmp;
mp_digit vbuf[MP_VALUE_DIGITS(value)];
mp_result res;
if ((res = mp_int_init(&rtmp)) != MP_OK)
return res;
s_fake(&vtmp, value, vbuf);
if ((res = mp_int_div(a, &vtmp, q, &rtmp)) != MP_OK)
goto CLEANUP;
if (r)
(void) mp_int_to_int(&rtmp, r); /* can't fail */
CLEANUP:
mp_int_clear(&rtmp);
return res;
}
| int mp_int_divisible_value | ( | mp_int | a, | |
| int | v | |||
| ) |
Definition at line 1780 of file imath.c.
References mp_int_div_value(), MP_OK, and NULL.
{
int rem = 0;
if (mp_int_div_value(a, v, NULL, &rem) != MP_OK)
return 0;
return rem == 0;
}
Definition at line 1630 of file imath.c.
References CHECK, CMPZ, MIN, mp_int_abs(), mp_int_add(), mp_int_clear(), mp_int_compare(), mp_int_copy(), mp_int_init(), mp_int_init_copy(), mp_int_is_even, mp_int_is_odd, mp_int_set_value(), mp_int_sub(), mp_int_zero(), MP_MEMORY, MP_OK, MP_SIGN, MP_UNDEF, MP_ZPOS, NULL, s_dp2k(), s_qdiv(), s_qmul(), SETUP, and TEMP.
Referenced by mp_int_invmod().
{
int k,
last = 0,
ca,
cb;
mpz_t temp[8];
mp_result res;
CHECK(a != NULL && b != NULL && c != NULL &&
(x != NULL || y != NULL));
ca = CMPZ(a);
cb = CMPZ(b);
if (ca == 0 && cb == 0)
return MP_UNDEF;
else if (ca == 0)
{
if ((res = mp_int_abs(b, c)) != MP_OK)
return res;
mp_int_zero(x);
(void) mp_int_set_value(y, 1);
return MP_OK;
}
else if (cb == 0)
{
if ((res = mp_int_abs(a, c)) != MP_OK)
return res;
(void) mp_int_set_value(x, 1);
mp_int_zero(y);
return MP_OK;
}
/*
* Initialize temporaries: A:0, B:1, C:2, D:3, u:4, v:5, ou:6, ov:7
*/
for (last = 0; last < 4; ++last)
{
if ((res = mp_int_init(TEMP(last))) != MP_OK)
goto CLEANUP;
}
TEMP(0)->digits[0] = 1;
TEMP(3)->digits[0] = 1;
SETUP(mp_int_init_copy(TEMP(4), a), last);
SETUP(mp_int_init_copy(TEMP(5), b), last);
/* We will work with absolute values here */
MP_SIGN(TEMP(4)) = MP_ZPOS;
MP_SIGN(TEMP(5)) = MP_ZPOS;
{ /* Divide out common factors of 2 from u and v */
int div2_u = s_dp2k(TEMP(4)),
div2_v = s_dp2k(TEMP(5));
k = MIN(div2_u, div2_v);
s_qdiv(TEMP(4), k);
s_qdiv(TEMP(5), k);
}
SETUP(mp_int_init_copy(TEMP(6), TEMP(4)), last);
SETUP(mp_int_init_copy(TEMP(7), TEMP(5)), last);
for (;;)
{
while (mp_int_is_even(TEMP(4)))
{
s_qdiv(TEMP(4), 1);
if (mp_int_is_odd(TEMP(0)) || mp_int_is_odd(TEMP(1)))
{
if ((res = mp_int_add(TEMP(0), TEMP(7), TEMP(0))) != MP_OK)
goto CLEANUP;
if ((res = mp_int_sub(TEMP(1), TEMP(6), TEMP(1))) != MP_OK)
goto CLEANUP;
}
s_qdiv(TEMP(0), 1);
s_qdiv(TEMP(1), 1);
}
while (mp_int_is_even(TEMP(5)))
{
s_qdiv(TEMP(5), 1);
if (mp_int_is_odd(TEMP(2)) || mp_int_is_odd(TEMP(3)))
{
if ((res = mp_int_add(TEMP(2), TEMP(7), TEMP(2))) != MP_OK)
goto CLEANUP;
if ((res = mp_int_sub(TEMP(3), TEMP(6), TEMP(3))) != MP_OK)
goto CLEANUP;
}
s_qdiv(TEMP(2), 1);
s_qdiv(TEMP(3), 1);
}
if (mp_int_compare(TEMP(4), TEMP(5)) >= 0)
{
if ((res = mp_int_sub(TEMP(4), TEMP(5), TEMP(4))) != MP_OK)
goto CLEANUP;
if ((res = mp_int_sub(TEMP(0), TEMP(2), TEMP(0))) != MP_OK)
goto CLEANUP;
if ((res = mp_int_sub(TEMP(1), TEMP(3), TEMP(1))) != MP_OK)
goto CLEANUP;
}
else
{
if ((res = mp_int_sub(TEMP(5), TEMP(4), TEMP(5))) != MP_OK)
goto CLEANUP;
if ((res = mp_int_sub(TEMP(2), TEMP(0), TEMP(2))) != MP_OK)
goto CLEANUP;
if ((res = mp_int_sub(TEMP(3), TEMP(1), TEMP(3))) != MP_OK)
goto CLEANUP;
}
if (CMPZ(TEMP(4)) == 0)
{
if (x && (res = mp_int_copy(TEMP(2), x)) != MP_OK)
goto CLEANUP;
if (y && (res = mp_int_copy(TEMP(3), y)) != MP_OK)
goto CLEANUP;
if (c)
{
if (!s_qmul(TEMP(5), k))
{
res = MP_MEMORY;
goto CLEANUP;
}
res = mp_int_copy(TEMP(5), c);
}
break;
}
}
CLEANUP:
while (--last >= 0)
mp_int_clear(TEMP(last));
return res;
}
Definition at line 1165 of file imath.c.
References CHECK, mp_int_clear(), mp_int_init_copy(), mp_int_mul(), mp_int_set_value(), mp_int_sqr(), MP_OK, and NULL.
{
mpz_t t;
mp_result res;
unsigned int v = abs(b);
CHECK(b >= 0 && c != NULL);
if ((res = mp_int_init_copy(&t, a)) != MP_OK)
return res;
(void) mp_int_set_value(c, 1);
while (v != 0)
{
if (v & 1)
{
if ((res = mp_int_mul(c, &t, c)) != MP_OK)
goto CLEANUP;
}
v >>= 1;
if (v == 0)
break;
if ((res = mp_int_sqr(&t, &t)) != MP_OK)
goto CLEANUP;
}
CLEANUP:
mp_int_clear(&t);
return res;
}
Definition at line 1203 of file imath.c.
References CHECK, mp_int_clear(), mp_int_init_value(), mp_int_mul(), mp_int_set_value(), mp_int_sqr(), MP_OK, and NULL.
{
mpz_t t;
mp_result res;
unsigned int v = abs(b);
CHECK(b >= 0 && c != NULL);
if ((res = mp_int_init_value(&t, a)) != MP_OK)
return res;
(void) mp_int_set_value(c, 1);
while (v != 0)
{
if (v & 1)
{
if ((res = mp_int_mul(c, &t, c)) != MP_OK)
goto CLEANUP;
}
v >>= 1;
if (v == 0)
break;
if ((res = mp_int_sqr(&t, &t)) != MP_OK)
goto CLEANUP;
}
CLEANUP:
mp_int_clear(&t);
return res;
}
Definition at line 1335 of file imath.c.
References CHECK, CMPZ, mp_int_clear(), mp_int_copy(), mp_int_init_size(), mp_int_mod(), MP_OK, MP_RANGE, MP_UNDEF, MP_USED, NULL, s_brmu(), s_embar(), SETUP, and TEMP.
Referenced by mp_int_exptmod_bvalue(), mp_int_exptmod_evalue(), pgp_elgamal_decrypt(), pgp_elgamal_encrypt(), pgp_rsa_decrypt(), and pgp_rsa_encrypt().
{
mp_result res;
mp_size um;
mpz_t temp[3];
mp_int s;
int last = 0;
CHECK(a != NULL && b != NULL && c != NULL && m != NULL);
/* Zero moduli and negative exponents are not considered. */
if (CMPZ(m) == 0)
return MP_UNDEF;
if (CMPZ(b) < 0)
return MP_RANGE;
um = MP_USED(m);
SETUP(mp_int_init_size(TEMP(0), 2 * um), last);
SETUP(mp_int_init_size(TEMP(1), 2 * um), last);
if (c == b || c == m)
{
SETUP(mp_int_init_size(TEMP(2), 2 * um), last);
s = TEMP(2);
}
else
{
s = c;
}
if ((res = mp_int_mod(a, m, TEMP(0))) != MP_OK)
goto CLEANUP;
if ((res = s_brmu(TEMP(1), m)) != MP_OK)
goto CLEANUP;
if ((res = s_embar(TEMP(0), b, m, TEMP(1), s)) != MP_OK)
goto CLEANUP;
res = mp_int_copy(s, c);
CLEANUP:
while (--last >= 0)
mp_int_clear(TEMP(last));
return res;
}
Definition at line 1403 of file imath.c.
References mp_int_exptmod(), MP_VALUE_DIGITS, and s_fake().
{
mpz_t vtmp;
mp_digit vbuf[MP_VALUE_DIGITS(value)];
s_fake(&vtmp, value, vbuf);
return mp_int_exptmod(&vtmp, b, m, c);
}
Definition at line 1388 of file imath.c.
References mp_int_exptmod(), MP_VALUE_DIGITS, and s_fake().
{
mpz_t vtmp;
mp_digit vbuf[MP_VALUE_DIGITS(value)];
s_fake(&vtmp, value, vbuf);
return mp_int_exptmod(a, &vtmp, m, c);
}
Definition at line 1419 of file imath.c.
References CHECK, CMPZ, mp_int_clear(), mp_int_copy(), mp_int_init_size(), mp_int_mod(), MP_OK, MP_RANGE, MP_UNDEF, MP_USED, s_embar(), SETUP, and TEMP.
{
mp_result res;
mp_size um;
mpz_t temp[2];
mp_int s;
int last = 0;
CHECK(a && b && m && c);
/* Zero moduli and negative exponents are not considered. */
if (CMPZ(m) == 0)
return MP_UNDEF;
if (CMPZ(b) < 0)
return MP_RANGE;
um = MP_USED(m);
SETUP(mp_int_init_size(TEMP(0), 2 * um), last);
if (c == b || c == m)
{
SETUP(mp_int_init_size(TEMP(1), 2 * um), last);
s = TEMP(1);
}
else
{
s = c;
}
if ((res = mp_int_mod(a, m, TEMP(0))) != MP_OK)
goto CLEANUP;
if ((res = s_embar(TEMP(0), b, m, mu, s)) != MP_OK)
goto CLEANUP;
res = mp_int_copy(s, c);
CLEANUP:
while (--last >= 0)
mp_int_clear(TEMP(last));
return res;
}
| void mp_int_free | ( | mp_int | z | ) |
Definition at line 495 of file imath.c.
References mpz::digits, mp_int_clear(), NRCHECK, NULL, and px_free.
Referenced by mp_clear_free().
Definition at line 1535 of file imath.c.
References CHECK, CMPZ, MIN, mp_int_abs(), mp_int_clear(), mp_int_copy(), mp_int_init(), mp_int_init_copy(), mp_int_is_odd, mp_int_neg(), mp_int_sub(), MP_MEMORY, MP_OK, MP_SIGN, MP_UNDEF, MP_ZPOS, NULL, s_dp2k(), s_qdiv(), and s_qmul().
{
int ca,
cb,
k = 0;
mpz_t u,
v,
t;
mp_result res;
CHECK(a != NULL && b != NULL && c != NULL);
ca = CMPZ(a);
cb = CMPZ(b);
if (ca == 0 && cb == 0)
return MP_UNDEF;
else if (ca == 0)
return mp_int_abs(b, c);
else if (cb == 0)
return mp_int_abs(a, c);
if ((res = mp_int_init(&t)) != MP_OK)
return res;
if ((res = mp_int_init_copy(&u, a)) != MP_OK)
goto U;
if ((res = mp_int_init_copy(&v, b)) != MP_OK)
goto V;
MP_SIGN(&u) = MP_ZPOS;
MP_SIGN(&v) = MP_ZPOS;
{ /* Divide out common factors of 2 from u and v */
int div2_u = s_dp2k(&u),
div2_v = s_dp2k(&v);
k = MIN(div2_u, div2_v);
s_qdiv(&u, (mp_size) k);
s_qdiv(&v, (mp_size) k);
}
if (mp_int_is_odd(&u))
{
if ((res = mp_int_neg(&v, &t)) != MP_OK)
goto CLEANUP;
}
else
{
if ((res = mp_int_copy(&u, &t)) != MP_OK)
goto CLEANUP;
}
for (;;)
{
s_qdiv(&t, s_dp2k(&t));
if (CMPZ(&t) > 0)
{
if ((res = mp_int_copy(&t, &u)) != MP_OK)
goto CLEANUP;
}
else
{
if ((res = mp_int_neg(&t, &v)) != MP_OK)
goto CLEANUP;
}
if ((res = mp_int_sub(&u, &v, &t)) != MP_OK)
goto CLEANUP;
if (CMPZ(&t) == 0)
break;
}
if ((res = mp_int_abs(&u, c)) != MP_OK)
goto CLEANUP;
if (!s_qmul(c, (mp_size) k))
res = MP_MEMORY;
CLEANUP:
mp_int_clear(&v);
V: mp_int_clear(&u);
U: mp_int_clear(&t);
return res;
}
Definition at line 361 of file imath.c.
References default_precision, and mp_int_init_size().
Referenced by mp_int_div_value(), mp_int_egcd(), mp_int_gcd(), mp_int_init_value(), mp_int_invmod(), mp_int_mod(), and mp_int_sqrt().
{
return mp_int_init_size(z, default_precision);
}
Definition at line 412 of file imath.c.
References CHECK, COPY, default_precision, MAX, MP_DIGITS, mp_int_init_size(), MP_OK, MP_SIGN, MP_USED, and NULL.
Referenced by mp_int_div(), mp_int_egcd(), mp_int_expt(), mp_int_gcd(), mp_int_sqrt(), and mp_int_to_string().
Definition at line 389 of file imath.c.
References CHECK, default_precision, mpz::digits, MAX, MP_ALLOC, MP_DIGITS, MP_MEMORY, MP_OK, MP_SIGN, MP_USED, MP_ZPOS, NULL, ROUND_PREC, and s_alloc().
Referenced by mp_int_exptmod(), mp_int_exptmod_known(), mp_int_init(), mp_int_init_copy(), mp_new(), s_embar(), and s_udiv().
Definition at line 438 of file imath.c.
References CHECK, mp_int_init(), mp_int_set_value(), MP_OK, and NULL.
Referenced by mp_int_expt_value().
{
mp_result res;
CHECK(z != NULL);
if ((res = mp_int_init(z)) != MP_OK)
return res;
return mp_int_set_value(z, value);
}
Definition at line 1480 of file imath.c.
References CHECK, CMPZ, mp_int_clear(), mp_int_compare_value(), mp_int_copy(), mp_int_egcd(), mp_int_init(), mp_int_mod(), mp_int_sub(), MP_NEG, MP_OK, MP_RANGE, MP_SIGN, MP_UNDEF, NULL, and TEMP.
Referenced by pgp_elgamal_decrypt().
{
mp_result res;
mp_sign sa;
int last = 0;
mpz_t temp[2];
CHECK(a != NULL && m != NULL && c != NULL);
if (CMPZ(a) == 0 || CMPZ(m) <= 0)
return MP_RANGE;
sa = MP_SIGN(a); /* need this for the result later */
for (last = 0; last < 2; ++last)
if ((res = mp_int_init(TEMP(last))) != MP_OK)
goto CLEANUP;
if ((res = mp_int_egcd(a, m, TEMP(0), TEMP(1), NULL)) != MP_OK)
goto CLEANUP;
if (mp_int_compare_value(TEMP(0), 1) != 0)
{
res = MP_UNDEF;
goto CLEANUP;
}
/* It is first necessary to constrain the value to the proper range */
if ((res = mp_int_mod(TEMP(1), m, TEMP(1))) != MP_OK)
goto CLEANUP;
/*
* Now, if 'a' was originally negative, the value we have is actually the
* magnitude of the negative representative; to get the positive value we
* have to subtract from the modulus. Otherwise, the value is okay as it
* stands.
*/
if (sa == MP_NEG)
res = mp_int_sub(m, TEMP(1), c);
else
res = mp_int_copy(TEMP(1), c);
CLEANUP:
while (--last >= 0)
mp_int_clear(TEMP(last));
return res;
}
| int mp_int_is_pow2 | ( | mp_int | z | ) |
Definition at line 1079 of file imath.c.
References CMPZ, mp_int_add(), mp_int_clear(), mp_int_copy(), mp_int_div(), mp_int_init(), MP_OK, and NULL.
Referenced by mp_int_exptmod(), mp_int_exptmod_known(), mp_int_invmod(), and mp_modmul().
{
mp_result res;
mpz_t tmp;
mp_int out;
if (m == c)
{
if ((res = mp_int_init(&tmp)) != MP_OK)
return res;
out = &tmp;
}
else
{
out = c;
}
if ((res = mp_int_div(a, m, NULL, out)) != MP_OK)
goto CLEANUP;
if (CMPZ(out) < 0)
res = mp_int_add(out, m, c);
else
res = mp_int_copy(out, c);
CLEANUP:
if (out != c)
mp_int_clear(&tmp);
return res;
}
Definition at line 794 of file imath.c.
References CHECK, CLAMP, default_precision, MAX, MP_ALLOC, MP_DIGITS, mp_int_compare_zero(), mp_int_zero(), MP_MEMORY, MP_NEG, MP_OK, MP_SIGN, MP_USED, MP_ZPOS, NULL, ROUND_PREC, s_alloc(), s_free, s_kmul(), s_pad(), and ZERO.
Referenced by mp_int_expt(), mp_int_expt_value(), mp_int_mul_value(), and mp_modmul().
{
mp_digit *out;
mp_size osize,
ua,
ub,
p = 0;
mp_sign osign;
CHECK(a != NULL && b != NULL && c != NULL);
/* If either input is zero, we can shortcut multiplication */
if (mp_int_compare_zero(a) == 0 || mp_int_compare_zero(b) == 0)
{
mp_int_zero(c);
return MP_OK;
}
/* Output is positive if inputs have same sign, otherwise negative */
osign = (MP_SIGN(a) == MP_SIGN(b)) ? MP_ZPOS : MP_NEG;
/*
* If the output is not equal to any of the inputs, we'll write the
* results there directly; otherwise, allocate a temporary space.
*/
ua = MP_USED(a);
ub = MP_USED(b);
osize = ua + ub;
if (c == a || c == b)
{
p = ROUND_PREC(osize);
p = MAX(p, default_precision);
if ((out = s_alloc(p)) == NULL)
return MP_MEMORY;
}
else
{
if (!s_pad(c, osize))
return MP_MEMORY;
out = MP_DIGITS(c);
}
ZERO(out, osize);
if (!s_kmul(MP_DIGITS(a), MP_DIGITS(b), out, ua, ub))
return MP_MEMORY;
/*
* If we allocated a new buffer, get rid of whatever memory c was already
* using, and fix up its fields to reflect that.
*/
if (out != MP_DIGITS(c))
{
s_free(MP_DIGITS(c));
MP_DIGITS(c) = out;
MP_ALLOC(c) = p;
}
MP_USED(c) = osize; /* might not be true, but we'll fix it ... */
CLAMP(c); /* ... right here */
MP_SIGN(c) = osign;
return MP_OK;
}
Definition at line 866 of file imath.c.
References mp_int_mul(), MP_VALUE_DIGITS, and s_fake().
{
mpz_t vtmp;
mp_digit vbuf[MP_VALUE_DIGITS(value)];
s_fake(&vtmp, value, vbuf);
return mp_int_mul(a, &vtmp, c);
}
Definition at line 2124 of file imath.c.
References CHECK, i, MP_DIGIT_BIT, MP_DIGITS, mp_int_zero(), MP_MEMORY, MP_NEG, MP_OK, MP_SIGN, NULL, s_2comp(), s_pad(), and s_qmul().
{
mp_size need,
i;
unsigned char *tmp;
mp_digit *dz;
CHECK(z != NULL && buf != NULL && len > 0);
/* Figure out how many digits are needed to represent this value */
need = ((len * CHAR_BIT) + (MP_DIGIT_BIT - 1)) / MP_DIGIT_BIT;
if (!s_pad(z, need))
return MP_MEMORY;
mp_int_zero(z);
/*
* If the high-order bit is set, take the 2's complement before reading
* the value (it will be restored afterward)
*/
if (buf[0] >> (CHAR_BIT - 1))
{
MP_SIGN(z) = MP_NEG;
s_2comp(buf, len);
}
dz = MP_DIGITS(z);
for (tmp = buf, i = len; i > 0; --i, ++tmp)
{
s_qmul(z, (mp_size) CHAR_BIT);
*dz |= *tmp;
}
/* Restore 2's complement if we took it before */
if (MP_SIGN(z) == MP_NEG)
s_2comp(buf, len);
return MP_OK;
}
Definition at line 2003 of file imath.c.
References CHECK, CLAMP, CMPZ, mpz::digits, MP_MAX_RADIX, MP_MEMORY, MP_NEG, MP_OK, MP_RANGE, MP_SIGN, MP_TRUNC, MP_USED, MP_ZPOS, NULL, s_ch2val(), s_dadd(), s_dmul(), s_inlen(), and s_pad().
Referenced by mp_int_read_string().
{
int ch;
CHECK(z != NULL && str != NULL);
if (radix < MP_MIN_RADIX || radix > MP_MAX_RADIX)
return MP_RANGE;
/* Skip leading whitespace */
while (isspace((unsigned char) *str))
++str;
/* Handle leading sign tag (+/-, positive default) */
switch (*str)
{
case '-':
MP_SIGN(z) = MP_NEG;
++str;
break;
case '+':
++str; /* fallthrough */
default:
MP_SIGN(z) = MP_ZPOS;
break;
}
/* Skip leading zeroes */
while ((ch = s_ch2val(*str, radix)) == 0)
++str;
/* Make sure there is enough space for the value */
if (!s_pad(z, s_inlen(strlen(str), radix)))
return MP_MEMORY;
MP_USED(z) = 1;
z->digits[0] = 0;
while (*str != '\0' && ((ch = s_ch2val(*str, radix)) >= 0))
{
s_dmul(z, (mp_digit) radix);
s_dadd(z, (mp_digit) ch);
++str;
}
CLAMP(z);
/* Override sign for zero, even if negative specified. */
if (CMPZ(z) == 0)
MP_SIGN(z) = MP_ZPOS;
if (end != NULL)
*end = (char *) str;
/*
* Return a truncation error if the string has unprocessed characters
* remaining, so the caller can tell if the whole string was done
*/
if (*str != '\0')
return MP_TRUNC;
else
return MP_OK;
}
Definition at line 1992 of file imath.c.
References mp_int_read_cstring(), and NULL.
{
return mp_int_read_cstring(z, radix, str, NULL);
}
Definition at line 2209 of file imath.c.
References CHECK, i, MP_DIGIT_BIT, MP_DIGITS, mp_int_zero(), MP_MEMORY, MP_OK, NULL, s_pad(), and s_qmul().
Referenced by mp_px_rand(), and mpi_to_bn().
{
mp_size need,
i;
unsigned char *tmp;
mp_digit *dz;
CHECK(z != NULL && buf != NULL && len > 0);
/* Figure out how many digits are needed to represent this value */
need = ((len * CHAR_BIT) + (MP_DIGIT_BIT - 1)) / MP_DIGIT_BIT;
if (!s_pad(z, need))
return MP_MEMORY;
mp_int_zero(z);
dz = MP_DIGITS(z);
for (tmp = buf, i = len; i > 0; --i, ++tmp)
{
(void) s_qmul(z, CHAR_BIT);
*dz |= *tmp;
}
return MP_OK;
}
Definition at line 455 of file imath.c.
References CHECK, MP_DIGITS, MP_MEMORY, MP_NEG, MP_OK, MP_SIGN, MP_USED, MP_VALUE_DIGITS, MP_ZPOS, NULL, s_pad(), and s_vpack().
Referenced by mp_int_egcd(), mp_int_expt(), mp_int_expt_value(), mp_int_init_value(), and s_embar().
Definition at line 901 of file imath.c.
References CHECK, CLAMP, default_precision, MAX, MP_ALLOC, MP_DIGITS, MP_MEMORY, MP_OK, MP_SIGN, MP_USED, MP_ZPOS, NULL, ROUND_PREC, s_alloc(), s_free, s_ksqr(), s_pad(), and ZERO.
Referenced by mp_int_expt(), mp_int_expt_value(), and mp_int_sqrt().
{
mp_digit *out;
mp_size osize,
p = 0;
CHECK(a != NULL && c != NULL);
/* Get a temporary buffer big enough to hold the result */
osize = (mp_size) 2 *MP_USED(a);
if (a == c)
{
p = ROUND_PREC(osize);
p = MAX(p, default_precision);
if ((out = s_alloc(p)) == NULL)
return MP_MEMORY;
}
else
{
if (!s_pad(c, osize))
return MP_MEMORY;
out = MP_DIGITS(c);
}
ZERO(out, osize);
s_ksqr(MP_DIGITS(a), out, MP_USED(a));
/*
* Get rid of whatever memory c was already using, and fix up its fields
* to reflect the new digit array it's using
*/
if (out != MP_DIGITS(c))
{
s_free(MP_DIGITS(c));
MP_DIGITS(c) = out;
MP_ALLOC(c) = p;
}
MP_USED(c) = osize; /* might not be true, but we'll fix it ... */
CLAMP(c); /* ... right here */
MP_SIGN(c) = MP_ZPOS;
return MP_OK;
}
Definition at line 1807 of file imath.c.
References CHECK, mp_int_add(), mp_int_clear(), mp_int_compare_unsigned(), mp_int_copy(), mp_int_div(), mp_int_div_pow2(), mp_int_init(), mp_int_init_copy(), mp_int_sqr(), mp_int_sub_value(), MP_NEG, MP_OK, MP_SIGN, MP_UNDEF, NULL, SETUP, and TEMP.
{
mp_result res = MP_OK;
mpz_t temp[2];
int last = 0;
CHECK(a != NULL && c != NULL);
/* The square root of a negative value does not exist in the integers. */
if (MP_SIGN(a) == MP_NEG)
return MP_UNDEF;
SETUP(mp_int_init_copy(TEMP(last), a), last);
SETUP(mp_int_init(TEMP(last)), last);
for (;;)
{
if ((res = mp_int_sqr(TEMP(0), TEMP(1))) != MP_OK)
goto CLEANUP;
if (mp_int_compare_unsigned(a, TEMP(1)) == 0)
break;
if ((res = mp_int_copy(a, TEMP(1))) != MP_OK)
goto CLEANUP;
if ((res = mp_int_div(TEMP(1), TEMP(0), TEMP(1), NULL)) != MP_OK)
goto CLEANUP;
if ((res = mp_int_add(TEMP(0), TEMP(1), TEMP(1))) != MP_OK)
goto CLEANUP;
if ((res = mp_int_div_pow2(TEMP(1), 1, TEMP(1), NULL)) != MP_OK)
goto CLEANUP;
if (mp_int_compare_unsigned(TEMP(0), TEMP(1)) == 0)
break;
if ((res = mp_int_sub_value(TEMP(0), 1, TEMP(0))) != MP_OK)
goto CLEANUP;
if (mp_int_compare_unsigned(TEMP(0), TEMP(1)) == 0)
break;
if ((res = mp_int_copy(TEMP(1), TEMP(0))) != MP_OK)
goto CLEANUP;
}
res = mp_int_copy(TEMP(0), c);
CLEANUP:
while (--last >= 0)
mp_int_clear(TEMP(last));
return res;
}
Definition at line 1968 of file imath.c.
References CHECK, MP_MAX_RADIX, MP_NEG, MP_RANGE, MP_SIGN, NULL, and s_outlen().
Definition at line 699 of file imath.c.
References CHECK, CLAMP, cmp(), mpz::digits, MAX, MP_DIGITS, MP_MEMORY, MP_NEG, MP_OK, MP_SIGN, MP_USED, MP_ZPOS, NULL, s_pad(), s_uadd(), s_ucmp(), and s_usub().
Referenced by mp_int_egcd(), mp_int_gcd(), mp_int_invmod(), mp_int_sub_value(), s_reduce(), and s_udiv().
{
mp_size ua,
ub,
uc,
max;
CHECK(a != NULL && b != NULL && c != NULL);
ua = MP_USED(a);
ub = MP_USED(b);
uc = MP_USED(c);
max = MAX(ua, ub);
if (MP_SIGN(a) != MP_SIGN(b))
{
/* Different signs -- add magnitudes and keep sign of a */
mp_digit carry;
if (!s_pad(c, max))
return MP_MEMORY;
carry = s_uadd(MP_DIGITS(a), MP_DIGITS(b), MP_DIGITS(c), ua, ub);
uc = max;
if (carry)
{
if (!s_pad(c, max + 1))
return MP_MEMORY;
c->digits[max] = carry;
++uc;
}
MP_USED(c) = uc;
MP_SIGN(c) = MP_SIGN(a);
}
else
{
/* Same signs -- subtract magnitudes */
mp_int x,
y;
mp_sign osign;
int cmp = s_ucmp(a, b);
if (!s_pad(c, max))
return MP_MEMORY;
if (cmp >= 0)
{
x = a;
y = b;
osign = MP_ZPOS;
}
else
{
x = b;
y = a;
osign = MP_NEG;
}
if (MP_SIGN(a) == MP_NEG && cmp != 0)
osign = 1 - osign;
s_usub(MP_DIGITS(x), MP_DIGITS(y), MP_DIGITS(c), MP_USED(x), MP_USED(y));
MP_USED(c) = MP_USED(x);
CLAMP(c);
MP_SIGN(c) = osign;
}
return MP_OK;
}
Definition at line 779 of file imath.c.
References mp_int_sub(), MP_VALUE_DIGITS, and s_fake().
Referenced by mp_int_sqrt().
{
mpz_t vtmp;
mp_digit vbuf[MP_VALUE_DIGITS(value)];
s_fake(&vtmp, value, vbuf);
return mp_int_sub(a, &vtmp, c);
}
Definition at line 1864 of file imath.c.
References CHECK, MP_DIGIT_BIT, MP_DIGITS, mp_int_compare_value(), MP_NEG, MP_OK, MP_RANGE, MP_SIGN, MP_USED, MP_ZPOS, and NULL.
Referenced by mp_int_div_value().
{
unsigned int uv = 0;
mp_size uz;
mp_digit *dz;
mp_sign sz;
CHECK(z != NULL);
/* Make sure the value is representable as an int */
sz = MP_SIGN(z);
if ((sz == MP_ZPOS && mp_int_compare_value(z, INT_MAX) > 0) ||
mp_int_compare_value(z, INT_MIN) < 0)
return MP_RANGE;
uz = MP_USED(z);
dz = MP_DIGITS(z) + uz - 1;
while (uz > 0)
{
uv <<= MP_DIGIT_BIT / 2;
uv = (uv << (MP_DIGIT_BIT / 2)) | *dz--;
--uz;
}
if (out)
*out = (sz == MP_NEG) ? -(int) uv : (int) uv;
return MP_OK;
}
Definition at line 1900 of file imath.c.
References CHECK, cmp(), CMPZ, MP_CAP_DIGITS, mp_flags, mp_int_clear(), mp_int_init_copy(), MP_MAX_RADIX, MP_NEG, MP_OK, MP_RANGE, MP_SIGN, MP_TRUNC, NULL, s_ddiv(), and s_val2ch().
{
mp_result res;
int cmp = 0;
CHECK(z != NULL && str != NULL && limit >= 2);
if (radix < MP_MIN_RADIX || radix > MP_MAX_RADIX)
return MP_RANGE;
if (CMPZ(z) == 0)
{
*str++ = s_val2ch(0, mp_flags & MP_CAP_DIGITS);
}
else
{
mpz_t tmp;
char *h,
*t;
if ((res = mp_int_init_copy(&tmp, z)) != MP_OK)
return res;
if (MP_SIGN(z) == MP_NEG)
{
*str++ = '-';
--limit;
}
h = str;
/* Generate digits in reverse order until finished or limit reached */
for ( /* */ ; limit > 0; --limit)
{
mp_digit d;
if ((cmp = CMPZ(&tmp)) == 0)
break;
d = s_ddiv(&tmp, (mp_digit) radix);
*str++ = s_val2ch(d, mp_flags & MP_CAP_DIGITS);
}
t = str - 1;
/* Put digits back in correct output order */
while (h < t)
{
char tc = *h;
*h++ = *t;
*t-- = tc;
}
mp_int_clear(&tmp);
}
*str = '\0';
if (cmp == 0)
return MP_OK;
else
return MP_TRUNC;
}
Definition at line 2240 of file imath.c.
References mp_int_count_bits().
Referenced by mp_int_binary_len().
{
mp_result res = mp_int_count_bits(z);
int bytes;
if (res <= 0)
return res;
bytes = (res + (CHAR_BIT - 1)) / CHAR_BIT;
return bytes;
}
| void mp_int_zero | ( | mp_int | z | ) |
Definition at line 555 of file imath.c.
References mpz::digits, MP_SIGN, MP_USED, MP_ZPOS, NRCHECK, and NULL.
Referenced by mp_int_div(), mp_int_egcd(), mp_int_mul(), mp_int_read_binary(), mp_int_read_unsigned(), and s_qdiv().
| void mp_set_default_precision | ( | mp_size | s | ) |
Definition at line 329 of file imath.c.
References default_precision, NRCHECK, and ROUND_PREC.
{
NRCHECK(s > 0);
default_precision = (mp_size) ROUND_PREC(s);
}
| void mp_set_multiply_threshold | ( | mp_size | s | ) |
| static void s_2comp | ( | unsigned char * | buf, | |
| int | len | |||
| ) | [static] |
Definition at line 3573 of file imath.c.
References i.
Referenced by mp_int_read_binary(), and mp_int_to_binary().
| static int s_2expt | ( | mp_int | z, | |
| int | k | |||
| ) | [static] |
Definition at line 2283 of file imath.c.
References assert, NULL, and px_alloc.
Referenced by mp_int_init_size(), mp_int_mul(), mp_int_sqr(), s_kmul(), and s_ksqr().
Definition at line 3223 of file imath.c.
References MP_DIGIT_BIT, mp_int_div(), MP_MEMORY, MP_USED, NULL, s_2expt(), and s_pad().
Referenced by mp_int_exptmod(), and mp_int_redux_const().
{
mp_size um = MP_USED(m) * 2;
if (!s_pad(z, um))
return MP_MEMORY;
s_2expt(z, MP_DIGIT_BIT * um);
return mp_int_div(z, m, z, NULL);
}
| static int s_ch2val | ( | char | c, | |
| int | r | |||
| ) | [static] |
Definition at line 3532 of file imath.c.
Referenced by mp_int_read_cstring().
{
int out;
if (isdigit((unsigned char) c))
out = c - '0';
else if (r > 10 && isalpha((unsigned char) c))
out = toupper((unsigned char) c) - 'A' + 10;
else
return -1;
return (out >= r) ? -1 : out;
}
Definition at line 2805 of file imath.c.
References LOWER_HALF, MP_DIGITS, MP_USED, and UPPER_HALF.
Referenced by mp_int_read_cstring().
{
mp_word w = 0;
mp_digit *da = MP_DIGITS(a);
mp_size ua = MP_USED(a);
w = (mp_word) *da + b;
*da++ = LOWER_HALF(w);
w = UPPER_HALF(w);
for (ua -= 1; ua > 0; --ua, ++da)
{
w = (mp_word) *da + w;
*da = LOWER_HALF(w);
w = UPPER_HALF(w);
}
if (w)
{
*da = (mp_digit) w;
MP_USED(a) += 1;
}
}
Definition at line 2861 of file imath.c.
References LOWER_HALF, and UPPER_HALF.
Referenced by s_udiv().
{
mp_word w = 0;
while (size_a > 0)
{
w = (mp_word) *da++ * (mp_word) b + w;
*dc++ = LOWER_HALF(w);
w = UPPER_HALF(w);
--size_a;
}
if (w)
*dc = LOWER_HALF(w);
}
Definition at line 2835 of file imath.c.
References LOWER_HALF, MP_DIGITS, MP_USED, and UPPER_HALF.
Referenced by mp_int_read_cstring().
{
mp_word w = 0;
mp_digit *da = MP_DIGITS(a);
mp_size ua = MP_USED(a);
while (ua > 0)
{
w = (mp_word) *da * b + w;
*da++ = LOWER_HALF(w);
w = UPPER_HALF(w);
--ua;
}
if (w)
{
*da = (mp_digit) w;
MP_USED(a) += 1;
}
}
| static int s_dp2k | ( | mp_int | z | ) | [static] |
Definition at line 3110 of file imath.c.
References MP_DIGITS, and MP_USED.
Referenced by mp_int_egcd(), and mp_int_gcd().
Definition at line 3295 of file imath.c.
References assert, i, MP_DIGIT_BIT, MP_DIGITS, mp_int_clear(), mp_int_copy(), mp_int_init_size(), mp_int_set_value(), MP_MEMORY, MP_SIGN, MP_USED, MP_ZPOS, s_reduce(), SETUP, TEMP, UMUL, and USQR.
Referenced by mp_int_exptmod(), and mp_int_exptmod_known().
{
mp_digit *db,
*dbt,
umu,
d;
mpz_t temp[3];
mp_result res;
int last = 0;
umu = MP_USED(mu);
db = MP_DIGITS(b);
dbt = db + MP_USED(b) - 1;
while (last < 3)
SETUP(mp_int_init_size(TEMP(last), 2 * umu), last);
(void) mp_int_set_value(c, 1);
/* Take care of low-order digits */
while (db < dbt)
{
int i;
for (d = *db, i = MP_DIGIT_BIT; i > 0; --i, d >>= 1)
{
if (d & 1)
{
/* The use of a second temporary avoids allocation */
UMUL(c, a, TEMP(0));
if (!s_reduce(TEMP(0), m, mu, TEMP(1), TEMP(2)))
{
res = MP_MEMORY;
goto CLEANUP;
}
mp_int_copy(TEMP(0), c);
}
USQR(a, TEMP(0));
assert(MP_SIGN(TEMP(0)) == MP_ZPOS);
if (!s_reduce(TEMP(0), m, mu, TEMP(1), TEMP(2)))
{
res = MP_MEMORY;
goto CLEANUP;
}
assert(MP_SIGN(TEMP(0)) == MP_ZPOS);
mp_int_copy(TEMP(0), a);
}
++db;
}
/* Take care of highest-order digit */
d = *dbt;
for (;;)
{
if (d & 1)
{
UMUL(c, a, TEMP(0));
if (!s_reduce(TEMP(0), m, mu, TEMP(1), TEMP(2)))
{
res = MP_MEMORY;
goto CLEANUP;
}
mp_int_copy(TEMP(0), c);
}
d >>= 1;
if (!d)
break;
USQR(a, TEMP(0));
if (!s_reduce(TEMP(0), m, mu, TEMP(1), TEMP(2)))
{
res = MP_MEMORY;
goto CLEANUP;
}
(void) mp_int_copy(TEMP(0), a);
}
CLEANUP:
while (--last >= 0)
mp_int_clear(TEMP(last));
return res;
}
Definition at line 2363 of file imath.c.
References mpz::alloc, mpz::digits, MP_NEG, MP_VALUE_DIGITS, MP_ZPOS, s_vpack(), mpz::sign, and mpz::used.
Referenced by mp_int_add_value(), mp_int_div_value(), mp_int_exptmod_bvalue(), mp_int_exptmod_evalue(), mp_int_mul_value(), and mp_int_sub_value().
Definition at line 3519 of file imath.c.
References MP_DIGIT_BIT, and s_log2.
Referenced by mp_int_read_cstring().
{
double raw = (double) len / s_log2[r];
mp_size bits = (mp_size) (raw + 0.5);
return (mp_size) ((bits + (MP_DIGIT_BIT - 1)) / MP_DIGIT_BIT);
}
| static int s_isp2 | ( | mp_int | z | ) | [static] |
Definition at line 3140 of file imath.c.
References MP_DIGITS, and MP_USED.
Referenced by mp_int_div(), and mp_int_is_pow2().
| static int s_kmul | ( | mp_digit * | da, | |
| mp_digit * | db, | |||
| mp_digit * | dc, | |||
| mp_size | size_a, | |||
| mp_size | size_b | |||
| ) | [static] |
Definition at line 2540 of file imath.c.
References COPY, multiply_threshold, s_alloc(), s_free, s_uadd(), s_umul(), s_usub(), SWAP, and ZERO.
Referenced by mp_int_mul(), and s_ksqr().
{
mp_size bot_size;
/* Make sure b is the smaller of the two input values */
if (size_b > size_a)
{
SWAP(mp_digit *, da, db);
SWAP(mp_size, size_a, size_b);
}
/*
* Insure that the bottom is the larger half in an odd-length split; the
* code below relies on this being true.
*/
bot_size = (size_a + 1) / 2;
/*
* If the values are big enough to bother with recursion, use the
* Karatsuba algorithm to compute the product; otherwise use the normal
* multiplication algorithm
*/
if (multiply_threshold &&
size_a >= multiply_threshold &&
size_b > bot_size)
{
mp_digit *t1,
*t2,
*t3,
carry;
mp_digit *a_top = da + bot_size;
mp_digit *b_top = db + bot_size;
mp_size at_size = size_a - bot_size;
mp_size bt_size = size_b - bot_size;
mp_size buf_size = 2 * bot_size;
/*
* Do a single allocation for all three temporary buffers needed; each
* buffer must be big enough to hold the product of two bottom halves,
* and one buffer needs space for the completed product; twice the
* space is plenty.
*/
if ((t1 = s_alloc(4 * buf_size)) == NULL)
return 0;
t2 = t1 + buf_size;
t3 = t2 + buf_size;
ZERO(t1, 4 * buf_size);
/*
* t1 and t2 are initially used as temporaries to compute the inner
* product (a1 + a0)(b1 + b0) = a1b1 + a1b0 + a0b1 + a0b0
*/
carry = s_uadd(da, a_top, t1, bot_size, at_size); /* t1 = a1 + a0 */
t1[bot_size] = carry;
carry = s_uadd(db, b_top, t2, bot_size, bt_size); /* t2 = b1 + b0 */
t2[bot_size] = carry;
(void) s_kmul(t1, t2, t3, bot_size + 1, bot_size + 1); /* t3 = t1 * t2 */
/*
* Now we'll get t1 = a0b0 and t2 = a1b1, and subtract them out so
* that we're left with only the pieces we want: t3 = a1b0 + a0b1
*/
ZERO(t1, bot_size + 1);
ZERO(t2, bot_size + 1);
(void) s_kmul(da, db, t1, bot_size, bot_size); /* t1 = a0 * b0 */
(void) s_kmul(a_top, b_top, t2, at_size, bt_size); /* t2 = a1 * b1 */
/* Subtract out t1 and t2 to get the inner product */
s_usub(t3, t1, t3, buf_size + 2, buf_size);
s_usub(t3, t2, t3, buf_size + 2, buf_size);
/* Assemble the output value */
COPY(t1, dc, buf_size);
(void) s_uadd(t3, dc + bot_size, dc + bot_size,
buf_size + 1, buf_size + 1);
(void) s_uadd(t2, dc + 2 * bot_size, dc + 2 * bot_size,
buf_size, buf_size);
s_free(t1); /* note t2 and t3 are just internal pointers
* to t1 */
}
else
{
s_umul(da, db, dc, size_a, size_b);
}
return 1;
}
Definition at line 2674 of file imath.c.
References COPY, i, LOWER_HALF, multiply_threshold, px_free, s_alloc(), s_kmul(), s_uadd(), s_usqr(), UPPER_HALF, and ZERO.
Referenced by mp_int_sqr().
{
if (multiply_threshold && size_a > multiply_threshold)
{
mp_size bot_size = (size_a + 1) / 2;
mp_digit *a_top = da + bot_size;
mp_digit *t1,
*t2,
*t3;
mp_size at_size = size_a - bot_size;
mp_size buf_size = 2 * bot_size;
if ((t1 = s_alloc(4 * buf_size)) == NULL)
return 0;
t2 = t1 + buf_size;
t3 = t2 + buf_size;
ZERO(t1, 4 * buf_size);
(void) s_ksqr(da, t1, bot_size); /* t1 = a0 ^ 2 */
(void) s_ksqr(a_top, t2, at_size); /* t2 = a1 ^ 2 */
(void) s_kmul(da, a_top, t3, bot_size, at_size); /* t3 = a0 * a1 */
/* Quick multiply t3 by 2, shifting left (can't overflow) */
{
int i,
top = bot_size + at_size;
mp_word w,
save = 0;
for (i = 0; i < top; ++i)
{
w = t3[i];
w = (w << 1) | save;
t3[i] = LOWER_HALF(w);
save = UPPER_HALF(w);
}
t3[i] = LOWER_HALF(save);
}
/* Assemble the output value */
COPY(t1, dc, 2 * bot_size);
(void) s_uadd(t3, dc + bot_size, dc + bot_size,
buf_size + 1, buf_size + 1);
(void) s_uadd(t2, dc + 2 * bot_size, dc + 2 * bot_size,
buf_size, buf_size);
px_free(t1); /* note that t2 and t2 are internal pointers
* only */
}
else
{
s_usqr(da, dc, size_a);
}
return 1;
}
Definition at line 3197 of file imath.c.
References mpz::digits, MP_DIGIT_BIT, MP_USED, and s_qmul().
Referenced by s_udiv().
Definition at line 3503 of file imath.c.
References mp_int_count_bits(), and s_log2.
Referenced by mp_int_string_len().
{
mp_result bits;
double raw;
bits = mp_int_count_bits(z);
raw = (double) bits *s_log2[r];
return (int) (raw + 0.999999);
}
Definition at line 2323 of file imath.c.
References MP_ALLOC, MP_DIGITS, NULL, ROUND_PREC, and s_realloc().
Referenced by mp_int_add(), mp_int_copy(), mp_int_mul(), mp_int_read_binary(), mp_int_read_cstring(), mp_int_read_unsigned(), mp_int_set_value(), mp_int_sqr(), mp_int_sub(), s_2expt(), s_brmu(), s_qmul(), and s_qsub().
Definition at line 2916 of file imath.c.
References CLAMP, mpz::digits, MP_DIGIT_BIT, MP_DIGITS, mp_int_zero(), MP_SIGN, MP_USED, and MP_ZPOS.
Referenced by mp_int_div(), mp_int_div_pow2(), mp_int_egcd(), mp_int_gcd(), s_reduce(), and s_udiv().
{
mp_size ndig = p2 / MP_DIGIT_BIT,
nbits = p2 % MP_DIGIT_BIT;
mp_size uz = MP_USED(z);
if (ndig)
{
mp_size mark;
mp_digit *to,
*from;
if (ndig >= uz)
{
mp_int_zero(z);
return;
}
to = MP_DIGITS(z);
from = to + ndig;
for (mark = ndig; mark < uz; ++mark)
*to++ = *from++;
MP_USED(z) = uz - ndig;
}
if (nbits)
{
mp_digit d = 0,
*dz,
save;
mp_size up = MP_DIGIT_BIT - nbits;
uz = MP_USED(z);
dz = MP_DIGITS(z) + uz - 1;
for ( /* */ ; uz > 0; --uz, --dz)
{
save = *dz;
*dz = (*dz >> nbits) | (d << up);
d = save;
}
CLAMP(z);
}
if (MP_USED(z) == 1 && z->digits[0] == 0)
MP_SIGN(z) = MP_ZPOS;
}
Definition at line 2973 of file imath.c.
References CLAMP, mpz::digits, MP_DIGIT_BIT, and MP_USED.
Referenced by mp_int_div(), mp_int_div_pow2(), and s_reduce().
Definition at line 2993 of file imath.c.
References CLAMP, i, MP_DIGIT_BIT, MP_DIGITS, MP_USED, s_pad(), and ZERO.
Referenced by mp_int_egcd(), mp_int_gcd(), mp_int_mul_pow2(), mp_int_read_binary(), mp_int_read_unsigned(), and s_norm().
{
mp_size uz,
need,
rest,
extra,
i;
mp_digit *from,
*to,
d;
if (p2 == 0)
return 1;
uz = MP_USED(z);
need = p2 / MP_DIGIT_BIT;
rest = p2 % MP_DIGIT_BIT;
/*
* Figure out if we need an extra digit at the top end; this occurs if the
* topmost `rest' bits of the high-order digit of z are not zero, meaning
* they will be shifted off the end if not preserved
*/
extra = 0;
if (rest != 0)
{
mp_digit *dz = MP_DIGITS(z) + uz - 1;
if ((*dz >> (MP_DIGIT_BIT - rest)) != 0)
extra = 1;
}
if (!s_pad(z, uz + need + extra))
return 0;
/*
* If we need to shift by whole digits, do that in one pass, then to back
* and shift by partial digits.
*/
if (need > 0)
{
from = MP_DIGITS(z) + uz - 1;
to = from + need;
for (i = 0; i < uz; ++i)
*to-- = *from--;
ZERO(MP_DIGITS(z), need);
uz += need;
}
if (rest)
{
d = 0;
for (i = need, from = MP_DIGITS(z) + need; i < uz; ++i, ++from)
{
mp_digit save = *from;
*from = (*from << rest) | (d >> (MP_DIGIT_BIT - rest));
d = save;
}
d >>= (MP_DIGIT_BIT - rest);
if (d != 0)
{
*from = d;
uz += extra;
}
}
MP_USED(z) = uz;
CLAMP(z);
return 1;
}
Definition at line 3075 of file imath.c.
References assert, CLAMP, LOWER_HALF, MP_DIGIT_MAX, MP_DIGITS, MP_SIGN, MP_ZPOS, s_pad(), and UPPER_HALF.
Referenced by s_reduce().
{
mp_digit hi = (1 << (p2 % MP_DIGIT_BIT)),
*zp;
mp_size tdig = (p2 / MP_DIGIT_BIT),
pos;
mp_word w = 0;
if (!s_pad(z, tdig + 1))
return 0;
for (pos = 0, zp = MP_DIGITS(z); pos < tdig; ++pos, ++zp)
{
w = ((mp_word) MP_DIGIT_MAX + 1) - w - (mp_word) *zp;
*zp = LOWER_HALF(w);
w = UPPER_HALF(w) ? 0 : 1;
}
w = ((mp_word) MP_DIGIT_MAX + 1 + hi) - w - (mp_word) *zp;
*zp = LOWER_HALF(w);
assert(UPPER_HALF(w) != 0); /* no borrow out should be possible */
MP_SIGN(z) = MP_ZPOS;
CLAMP(z);
return 1;
}
Definition at line 3239 of file imath.c.
References CMPZ, MP_DIGIT_BIT, mp_int_compare(), mp_int_copy(), mp_int_sub(), MP_OK, MP_USED, s_qdiv(), s_qmod(), s_qsub(), and UMUL.
Referenced by s_embar().
{
mp_size um = MP_USED(m),
umb_p1,
umb_m1;
umb_p1 = (um + 1) * MP_DIGIT_BIT;
umb_m1 = (um - 1) * MP_DIGIT_BIT;
if (mp_int_copy(x, q1) != MP_OK)
return 0;
/* Compute q2 = floor((floor(x / b^(k-1)) * mu) / b^(k+1)) */
s_qdiv(q1, umb_m1);
UMUL(q1, mu, q2);
s_qdiv(q2, umb_p1);
/* Set x = x mod b^(k+1) */
s_qmod(x, umb_p1);
/*
* Now, q is a guess for the quotient a / m. Compute x - q * m mod
* b^(k+1), replacing x. This may be off by a factor of 2m, but no more
* than that.
*/
UMUL(q2, m, q1);
s_qmod(q1, umb_p1);
(void) mp_int_sub(x, q1, x); /* can't fail */
/*
* The result may be < 0; if it is, add b^(k+1) to pin it in the proper
* range.
*/
if ((CMPZ(x) < 0) && !s_qsub(x, umb_p1))
return 0;
/*
* If x > m, we need to back it off until it is in range. This will be
* required at most twice.
*/
if (mp_int_compare(x, m) >= 0)
(void) mp_int_sub(x, m, x);
if (mp_int_compare(x, m) >= 0)
(void) mp_int_sub(x, m, x);
/* At this point, x has been properly reduced. */
return 1;
}
Definition at line 3597 of file imath.c.
References i, MP_DIGITS, MP_OK, MP_TRUNC, MP_USED, and REV.
Referenced by mp_int_to_binary(), and mp_int_to_unsigned().
{
mp_size uz;
mp_digit *dz;
int pos = 0,
limit = *limpos;
uz = MP_USED(z);
dz = MP_DIGITS(z);
while (uz > 0 && pos < limit)
{
mp_digit d = *dz++;
int i;
for (i = sizeof(mp_digit); i > 0 && pos < limit; --i)
{
buf[pos++] = (unsigned char) d;
d >>= CHAR_BIT;
/* Don't write leading zeroes */
if (d == 0 && uz == 1)
i = 0; /* exit loop without signaling truncation */
}
/* Detect truncation (loop exited with pos >= limit) */
if (i > 0)
break;
--uz;
}
if (pad != 0 && (buf[pos - 1] >> (CHAR_BIT - 1)))
{
if (pos < limit)
buf[pos++] = 0;
else
uz = 1;
}
/* Digits are in reverse order, fix that */
REV(unsigned char, buf, pos);
/* Return the number of bytes actually written */
*limpos = pos;
return (uz == 0) ? MP_OK : MP_TRUNC;
}
| static mp_digit s_uadd | ( | mp_digit * | da, | |
| mp_digit * | db, | |||
| mp_digit * | dc, | |||
| mp_size | size_a, | |||
| mp_size | size_b | |||
| ) | [static] |
Definition at line 2463 of file imath.c.
References LOWER_HALF, SWAP, and UPPER_HALF.
Referenced by mp_int_add(), mp_int_sub(), s_kmul(), and s_ksqr().
{
mp_size pos;
mp_word w = 0;
/* Insure that da is the longer of the two to simplify later code */
if (size_b > size_a)
{
SWAP(mp_digit *, da, db);
SWAP(mp_size, size_a, size_b);
}
/* Add corresponding digits until the shorter number runs out */
for (pos = 0; pos < size_b; ++pos, ++da, ++db, ++dc)
{
w = w + (mp_word) *da + (mp_word) *db;
*dc = LOWER_HALF(w);
w = UPPER_HALF(w);
}
/* Propagate carries as far as necessary */
for ( /* */ ; pos < size_a; ++pos, ++da, ++dc)
{
w = w + *da;
*dc = LOWER_HALF(w);
w = UPPER_HALF(w);
}
/* Return carry out */
return (mp_digit) w;
}
Definition at line 2424 of file imath.c.
References MP_DIGITS, MP_USED, and s_cdig().
Referenced by mp_int_add(), mp_int_compare(), mp_int_compare_unsigned(), mp_int_div(), mp_int_sub(), and s_udiv().
Definition at line 3393 of file imath.c.
References mpz::alloc, assert, CLAMP, mpz::digits, MP_ALLOC, MP_DIGIT_BIT, MP_DIGIT_MAX, MP_DIGITS, mp_int_clear(), mp_int_copy(), mp_int_init_size(), mp_int_sub(), MP_OK, MP_SIGN, MP_USED, MP_ZPOS, REV, s_dbmul(), s_norm(), s_qdiv(), s_ucmp(), s_usub(), mpz::sign, skip(), mpz::used, and ZERO.
Referenced by mp_int_div().
{
mpz_t q,
r,
t;
mp_size ua,
ub,
qpos = 0;
mp_digit *da,
btop;
mp_result res = MP_OK;
int k,
skip = 0;
/* Force signs to positive */
MP_SIGN(a) = MP_ZPOS;
MP_SIGN(b) = MP_ZPOS;
/* Normalize, per Knuth */
k = s_norm(a, b);
ua = MP_USED(a);
ub = MP_USED(b);
btop = b->digits[ub - 1];
if ((res = mp_int_init_size(&q, ua)) != MP_OK)
return res;
if ((res = mp_int_init_size(&t, ua + 1)) != MP_OK)
goto CLEANUP;
da = MP_DIGITS(a);
r.digits = da + ua - 1; /* The contents of r are shared with a */
r.used = 1;
r.sign = MP_ZPOS;
r.alloc = MP_ALLOC(a);
ZERO(t.digits, t.alloc);
/* Solve for quotient digits, store in q.digits in reverse order */
while (r.digits >= da)
{
assert(qpos <= q.alloc);
if (s_ucmp(b, &r) > 0)
{
r.digits -= 1;
r.used += 1;
if (++skip > 1)
q.digits[qpos++] = 0;
CLAMP(&r);
}
else
{
mp_word pfx = r.digits[r.used - 1];
mp_word qdigit;
if (r.used > 1 && (pfx < btop || r.digits[r.used - 2] == 0))
{
pfx <<= MP_DIGIT_BIT / 2;
pfx <<= MP_DIGIT_BIT / 2;
pfx |= r.digits[r.used - 2];
}
qdigit = pfx / btop;
if (qdigit > MP_DIGIT_MAX)
qdigit = 1;
s_dbmul(MP_DIGITS(b), (mp_digit) qdigit, t.digits, ub);
t.used = ub + 1;
CLAMP(&t);
while (s_ucmp(&t, &r) > 0)
{
--qdigit;
(void) mp_int_sub(&t, b, &t); /* cannot fail */
}
s_usub(r.digits, t.digits, r.digits, r.used, t.used);
CLAMP(&r);
q.digits[qpos++] = (mp_digit) qdigit;
ZERO(t.digits, t.used);
skip = 0;
}
}
/* Put quotient digits in the correct order, and discard extra zeroes */
q.used = qpos;
REV(mp_digit, q.digits, qpos);
CLAMP(&q);
/* Denormalize the remainder */
CLAMP(a);
if (k != 0)
s_qdiv(a, k);
mp_int_copy(a, b); /* ok: 0 <= r < b */
mp_int_copy(&q, a); /* ok: q <= a */
mp_int_clear(&t);
CLEANUP:
mp_int_clear(&q);
return res;
}
| static void s_umul | ( | mp_digit * | da, | |
| mp_digit * | db, | |||
| mp_digit * | dc, | |||
| mp_size | size_a, | |||
| mp_size | size_b | |||
| ) | [static] |
Definition at line 2641 of file imath.c.
References LOWER_HALF, and UPPER_HALF.
Referenced by s_kmul().
{
mp_size a,
b;
mp_word w;
for (a = 0; a < size_a; ++a, ++dc, ++da)
{
mp_digit *dct = dc;
mp_digit *dbt = db;
if (*da == 0)
continue;
w = 0;
for (b = 0; b < size_b; ++b, ++dbt, ++dct)
{
w = (mp_word) *da * (mp_word) *dbt + w + (mp_word) *dct;
*dct = LOWER_HALF(w);
w = UPPER_HALF(w);
}
*dct = (mp_digit) w;
}
}
Definition at line 2739 of file imath.c.
References ADD_WILL_OVERFLOW, assert, HIGH_BIT_SET, i, LOWER_HALF, and UPPER_HALF.
Referenced by s_ksqr().
{
mp_size i,
j;
mp_word w;
for (i = 0; i < size_a; ++i, dc += 2, ++da)
{
mp_digit *dct = dc,
*dat = da;
if (*da == 0)
continue;
/* Take care of the first digit, no rollover */
w = (mp_word) *dat * (mp_word) *dat + (mp_word) *dct;
*dct = LOWER_HALF(w);
w = UPPER_HALF(w);
++dat;
++dct;
for (j = i + 1; j < size_a; ++j, ++dat, ++dct)
{
mp_word t = (mp_word) *da * (mp_word) *dat;
mp_word u = w + (mp_word) *dct,
ov = 0;
/* Check if doubling t will overflow a word */
if (HIGH_BIT_SET(t))
ov = 1;
w = t + t;
/* Check if adding u to w will overflow a word */
if (ADD_WILL_OVERFLOW(w, u))
ov = 1;
w += u;
*dct = LOWER_HALF(w);
w = UPPER_HALF(w);
if (ov)
{
w += MP_DIGIT_MAX; /* MP_RADIX */
++w;
}
}
w = w + *dct;
*dct = (mp_digit) w;
while ((w = UPPER_HALF(w)) != 0)
{
++dct;
w = w + *dct;
*dct = LOWER_HALF(w);
}
assert(w == 0);
}
}
| static void s_usub | ( | mp_digit * | da, | |
| mp_digit * | db, | |||
| mp_digit * | dc, | |||
| mp_size | size_a, | |||
| mp_size | size_b | |||
| ) | [static] |
Definition at line 2502 of file imath.c.
References assert, LOWER_HALF, MP_DIGIT_MAX, and UPPER_HALF.
Referenced by mp_int_add(), mp_int_sub(), s_kmul(), and s_udiv().
{
mp_size pos;
mp_word w = 0;
/* We assume that |a| >= |b| so this should definitely hold */
assert(size_a >= size_b);
/* Subtract corresponding digits and propagate borrow */
for (pos = 0; pos < size_b; ++pos, ++da, ++db, ++dc)
{
w = ((mp_word) MP_DIGIT_MAX + 1 + /* MP_RADIX */
(mp_word) *da) - w - (mp_word) *db;
*dc = LOWER_HALF(w);
w = (UPPER_HALF(w) == 0);
}
/* Finish the subtraction for remaining upper digits of da */
for ( /* */ ; pos < size_a; ++pos, ++da, ++dc)
{
w = ((mp_word) MP_DIGIT_MAX + 1 + /* MP_RADIX */
(mp_word) *da) - w;
*dc = LOWER_HALF(w);
w = (UPPER_HALF(w) == 0);
}
/* If there is a borrow out at the end, it violates the precondition */
assert(w == 0);
}
| static char s_val2ch | ( | int | v, | |
| int | caps | |||
| ) | [static] |
Definition at line 3551 of file imath.c.
References assert.
Referenced by mp_int_to_string().
{
assert(v >= 0);
if (v < 10)
return v + '0';
else
{
char out = (v - 10) + 'a';
if (caps)
return toupper((unsigned char) out);
else
return out;
}
}
| static int s_vcmp | ( | mp_int | a, | |
| int | v | |||
| ) | [static] |
Definition at line 2442 of file imath.c.
References MP_DIGITS, MP_USED, MP_VALUE_DIGITS, s_cdig(), and s_vpack().
Referenced by mp_int_compare_value().
| static int s_vpack | ( | int | v, | |
| mp_digit | t[] | |||
| ) | [static] |
Definition at line 2399 of file imath.c.
References MP_DIGIT_BIT.
Referenced by mp_int_set_value(), s_fake(), and s_vcmp().
{
unsigned int uv = (unsigned int) ((v < 0) ? -v : v);
int ndig = 0;
if (uv == 0)
t[ndig++] = 0;
else
{
while (uv != 0)
{
t[ndig++] = (mp_digit) uv;
uv >>= MP_DIGIT_BIT / 2;
uv >>= MP_DIGIT_BIT / 2;
}
}
return ndig;
}
mp_size default_precision = 64 [static] |
Definition at line 167 of file imath.c.
Referenced by mp_get_default_precision(), mp_int_init(), mp_int_init_copy(), mp_int_init_size(), mp_int_mul(), mp_int_sqr(), and mp_set_default_precision().
Definition at line 173 of file imath.c.
Referenced by mp_int_to_string().
Definition at line 46 of file imath.c.
Referenced by mp_int_add(), mp_int_copy(), mp_int_egcd(), mp_int_gcd(), mp_int_init_size(), mp_int_mul(), mp_int_mul_pow2(), mp_int_read_binary(), mp_int_read_cstring(), mp_int_read_unsigned(), mp_int_set_value(), mp_int_sqr(), mp_int_sub(), s_brmu(), and s_embar().
Definition at line 52 of file imath.c.
Referenced by mp_int_compare_value(), mp_int_div(), mp_int_invmod(), mp_int_mul(), mp_int_read_binary(), mp_int_read_cstring(), mp_int_set_value(), mp_int_sqrt(), mp_int_string_len(), mp_int_sub(), mp_int_to_binary(), mp_int_to_int(), mp_int_to_string(), and s_fake().
Definition at line 43 of file imath.c.
Referenced by mp_int_abs(), mp_int_add(), mp_int_copy(), mp_int_div(), mp_int_div_pow2(), mp_int_div_value(), mp_int_divisible_value(), mp_int_egcd(), mp_int_expt(), mp_int_expt_value(), mp_int_exptmod(), mp_int_exptmod_known(), mp_int_gcd(), mp_int_init_copy(), mp_int_init_size(), mp_int_init_value(), mp_int_invmod(), mp_int_mod(), mp_int_mul(), mp_int_mul_pow2(), mp_int_neg(), mp_int_read_binary(), mp_int_read_cstring(), mp_int_read_unsigned(), mp_int_set_value(), mp_int_sqr(), mp_int_sqrt(), mp_int_sub(), mp_int_to_int(), mp_int_to_string(), s_reduce(), s_tobin(), and s_udiv().
Definition at line 47 of file imath.c.
Referenced by mp_int_exptmod(), mp_int_exptmod_known(), mp_int_invmod(), mp_int_read_cstring(), mp_int_string_len(), mp_int_to_int(), and mp_int_to_string().
Definition at line 49 of file imath.c.
Referenced by mp_int_read_cstring(), mp_int_to_string(), and s_tobin().
Definition at line 48 of file imath.c.
Referenced by mp_int_div(), mp_int_egcd(), mp_int_exptmod(), mp_int_exptmod_known(), mp_int_gcd(), mp_int_invmod(), and mp_int_sqrt().
Definition at line 53 of file imath.c.
Referenced by mp_int_abs(), mp_int_compare(), mp_int_compare_value(), mp_int_compare_zero(), mp_int_div(), mp_int_egcd(), mp_int_gcd(), mp_int_init_size(), mp_int_mul(), mp_int_read_cstring(), mp_int_set_value(), mp_int_sqr(), mp_int_sub(), mp_int_to_int(), mp_int_zero(), s_embar(), s_fake(), s_qdiv(), s_qsub(), and s_udiv().
mp_size multiply_threshold = 32 [static] |
Definition at line 170 of file imath.c.
Referenced by mp_get_multiply_threshold(), mp_set_multiply_threshold(), s_kmul(), and s_ksqr().
const char* s_error_msg[] [static] |
{
"error code 0",
"boolean true",
"out of memory",
"argument out of range",
"result undefined",
"output truncated",
"invalid null argument",
NULL
}
Definition at line 56 of file imath.c.
Referenced by mp_error_string().
const double s_log2[] [static] |
{
0.000000000, 0.000000000, 1.000000000, 0.630929754,
0.500000000, 0.430676558, 0.386852807, 0.356207187,
0.333333333, 0.315464877, 0.301029996, 0.289064826,
0.278942946, 0.270238154, 0.262649535, 0.255958025,
0.250000000, 0.244650542, 0.239812467, 0.235408913,
0.231378213, 0.227670249, 0.224243824, 0.221064729,
0.218104292, 0.215338279, 0.212746054, 0.210309918,
0.208014598, 0.205846832, 0.203795047, 0.201849087,
0.200000000, 0.198239863, 0.196561632, 0.194959022,
0.193426404, 0.191958720, 0.190551412, 0.189200360,
0.187901825, 0.186652411, 0.185449023, 0.184288833,
0.183169251, 0.182087900, 0.181042597, 0.180031327,
0.179052232, 0.178103594, 0.177183820, 0.176291434,
0.175425064, 0.174583430, 0.173765343, 0.172969690,
0.172195434, 0.171441601, 0.170707280, 0.169991616,
0.169293808, 0.168613099, 0.167948779, 0.167300179,
0.166666667
}
Definition at line 85 of file imath.c.
Referenced by s_inlen(), and s_outlen().
const char* s_unknown_err = "unknown result code" [static] |
Definition at line 55 of file imath.c.
Referenced by mp_error_string().
1.7.1