imath.c File Reference

#include "postgres.h"
#include "px.h"
#include "imath.h"

Include dependency graph for imath.c:

Define Documentation

#define ADD_WILL_OVERFLOW	(	W,
		V		)	((MP_WORD_MAX - (V)) < (W))

Definition at line 162 of file imath.c.

Referenced by s_usqr().

#define assert ( TEST ) Assert(TEST)

Definition at line 37 of file imath.c.

Referenced by addrange(), allocarc(), altdissect(), bracket(), brenext(), caltdissect(), carcsort(), cbracket(), cbrdissect(), ccondissect(), cdissect(), cfind(), cfindloop(), cleanup(), clearcvec(), cloneouts(), cmtreefree(), colorcomplement(), combine(), compact(), condissect(), copyins(), copyouts(), crevdissect(), delsub(), deltraverse(), destroystate(), dissect(), 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(), parse(), parsebranch(), parseqatom(), pg_regcomp(), pg_regexec(), pickss(), pull(), pullback(), push(), pushfwd(), s_alloc(), s_embar(), s_qsub(), s_realloc(), s_udiv(), s_usqr(), s_usub(), s_val2ch(), scanplain(), setcolor(), shortest(), skip(), specialcolors(), subblock(), subcolor(), subrange(), subre(), subset(), uncolorchain(), unempty(), word(), wordchrs(), and zapmem().

#define CHECK ( TEST ) assert(TEST)

#define CLAMP ( Z )

Value:

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().

#define CMPZ ( Z ) (((Z)->used==1&&(Z)->digits[0]==0)?0:((Z)->sign==MP_NEG)?-1:1)

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	)

Value:

do{mp_size i__=(S)*sizeof(mp_digit);mp_digit *p__=(P),*q__=(Q);\
memcpy(q__,p__,i__);}while(0)

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))

Definition at line 161 of file imath.c.

Referenced by s_usqr().

#define LOWER_HALF ( W ) ((mp_digit)(W))

Definition at line 160 of file imath.c.

Referenced by s_dadd(), s_dbmul(), s_dmul(), s_ksqr(), s_qsub(), s_uadd(), s_umul(), s_usqr(), and s_usub().

#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().

#define MP_VALUE_DIGITS ( V ) ((sizeof(V)+(sizeof(mp_digit)-1))/sizeof(mp_digit))

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 REV	(	T,
		A,
		N	)	do{T u_=(A),v_=u_+(N)-1;while(u_<v_){T xch=u_;u_++=v_;v_--=xch;}}while(0)

Definition at line 125 of file imath.c.

Referenced by s_tobin(), and s_udiv().

#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 SWAP	(	T,
		A,
		B	)	do{T t_=(A);A=(B);B=t_;}while(0)

Definition at line 140 of file imath.c.

Referenced by s_kmul(), and s_uadd().

#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 TRACEABLE_CLAMP 0

Definition at line 38 of file imath.c.

#define TRACEABLE_FREE 0

Definition at line 39 of file imath.c.

#define UMUL	(	X,
		Y,
		Z	)

Value:

do{mp_size ua_=MP_USED(X),ub_=MP_USED(Y);mp_size o_=ua_+ub_;\
ZERO(MP_DIGITS(Z),o_);\
(void) s_kmul(MP_DIGITS(X),MP_DIGITS(Y),MP_DIGITS(Z),ua_,ub_);\
MP_USED(Z)=o_;CLAMP(Z);}while(0)

Definition at line 149 of file imath.c.

Referenced by s_embar(), and s_reduce().

#define UPPER_HALF ( W ) ((mp_word)((W) >> MP_DIGIT_BIT))

Definition at line 159 of file imath.c.

Referenced by s_dadd(), s_dbmul(), s_dmul(), s_ksqr(), s_qsub(), s_uadd(), s_umul(), s_usqr(), and s_usub().

#define USQR	(	X,
		Z		)

Value:

do{mp_size ua_=MP_USED(X),o_=ua_+ua_;ZERO(MP_DIGITS(Z),o_);\
(void) s_ksqr(MP_DIGITS(X),MP_DIGITS(Z),ua_);MP_USED(Z)=o_;CLAMP(Z);}while(0)

Definition at line 155 of file imath.c.

Referenced by s_embar().

#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(), permute(), s_2expt(), s_kmul(), s_ksqr(), s_qmul(), and s_udiv().

Function Documentation

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.

02259 {
02260     int         ix;
02261 
02262     if (res > 0)
02263         return s_unknown_err;
02264 
02265     res = -res;
02266     for (ix = 0; ix < res && s_error_msg[ix] != NULL; ++ix)
02267         ;
02268 
02269     if (s_error_msg[ix] != NULL)
02270         return s_error_msg[ix];
02271     else
02272         return s_unknown_err;
02273 }

mp_size mp_get_default_precision ( void )

Definition at line 319 of file imath.c.

References default_precision.

00320 {
00321     return default_precision;
00322 }

mp_size mp_get_multiply_threshold ( void )

Definition at line 341 of file imath.c.

References multiply_threshold.

00342 {
00343     return multiply_threshold;
00344 }

mp_result mp_int_abs	(	mp_int	a,
		mp_int	c
	)

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().

00570 {
00571     mp_result   res;
00572 
00573     CHECK(a != NULL && c != NULL);
00574 
00575     if ((res = mp_int_copy(a, c)) != MP_OK)
00576         return res;
00577 
00578     MP_SIGN(c) = MP_ZPOS;
00579     return MP_OK;
00580 }

mp_result mp_int_add	(	mp_int	a,
		mp_int	b,
		mp_int	c
	)

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().

00608 {
00609     mp_size     ua,
00610                 ub,
00611                 uc,
00612                 max;
00613 
00614     CHECK(a != NULL && b != NULL && c != NULL);
00615 
00616     ua = MP_USED(a);
00617     ub = MP_USED(b);
00618     uc = MP_USED(c);
00619     max = MAX(ua, ub);
00620 
00621     if (MP_SIGN(a) == MP_SIGN(b))
00622     {
00623         /* Same sign -- add magnitudes, preserve sign of addends */
00624         mp_digit    carry;
00625 
00626         if (!s_pad(c, max))
00627             return MP_MEMORY;
00628 
00629         carry = s_uadd(MP_DIGITS(a), MP_DIGITS(b), MP_DIGITS(c), ua, ub);
00630         uc = max;
00631 
00632         if (carry)
00633         {
00634             if (!s_pad(c, max + 1))
00635                 return MP_MEMORY;
00636 
00637             c->digits[max] = carry;
00638             ++uc;
00639         }
00640 
00641         MP_USED(c) = uc;
00642         MP_SIGN(c) = MP_SIGN(a);
00643 
00644     }
00645     else
00646     {
00647         /* Different signs -- subtract magnitudes, preserve sign of greater */
00648         mp_int      x,
00649                     y;
00650         int         cmp = s_ucmp(a, b); /* magnitude comparision, sign ignored */
00651 
00652         /* Set x to max(a, b), y to min(a, b) to simplify later code */
00653         if (cmp >= 0)
00654         {
00655             x = a;
00656             y = b;
00657         }
00658         else
00659         {
00660             x = b;
00661             y = a;
00662         }
00663 
00664         if (!s_pad(c, MP_USED(x)))
00665             return MP_MEMORY;
00666 
00667         /* Subtract smaller from larger */
00668         s_usub(MP_DIGITS(x), MP_DIGITS(y), MP_DIGITS(c), MP_USED(x), MP_USED(y));
00669         MP_USED(c) = MP_USED(x);
00670         CLAMP(c);
00671 
00672         /* Give result the sign of the larger */
00673         MP_SIGN(c) = MP_SIGN(x);
00674     }
00675 
00676     return MP_OK;
00677 }

mp_result mp_int_add_value	(	mp_int	a,
		int	value,
		mp_int	c
	)

Definition at line 684 of file imath.c.

References mp_int_add(), MP_VALUE_DIGITS, and s_fake().

00685 {
00686     mpz_t       vtmp;
00687     mp_digit    vbuf[MP_VALUE_DIGITS(value)];
00688 
00689     s_fake(&vtmp, value, vbuf);
00690 
00691     return mp_int_add(a, &vtmp, c);
00692 }

mp_int mp_int_alloc ( void )

Definition at line 371 of file imath.c.

References mpz::alloc, assert, mpz::digits, NULL, px_alloc, mpz::sign, and mpz::used.

Referenced by mp_new().

00372 {
00373     mp_int      out = px_alloc(sizeof(mpz_t));
00374 
00375     assert(out != NULL);
00376     out->digits = NULL;
00377     out->used = 0;
00378     out->alloc = 0;
00379     out->sign = 0;
00380 
00381     return out;
00382 }

mp_result mp_int_binary_len ( mp_int z )

Definition at line 2169 of file imath.c.

References mp_int_count_bits(), and mp_int_unsigned_len().

02170 {
02171     mp_result   res = mp_int_count_bits(z);
02172     int         bytes = mp_int_unsigned_len(z);
02173 
02174     if (res <= 0)
02175         return res;
02176 
02177     bytes = (res + (CHAR_BIT - 1)) / CHAR_BIT;
02178 
02179     /*
02180      * If the highest-order bit falls exactly on a byte boundary, we need to
02181      * pad with an extra byte so that the sign will be read correctly when
02182      * reading it back in.
02183      */
02184     if (bytes * CHAR_BIT == res)
02185         ++bytes;
02186 
02187     return bytes;
02188 }

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().

00479 {
00480     if (z == NULL)
00481         return;
00482 
00483     if (MP_DIGITS(z) != NULL)
00484     {
00485         s_free(MP_DIGITS(z));
00486         MP_DIGITS(z) = NULL;
00487     }
00488 }

int mp_int_compare	(	mp_int	a,
		mp_int	b
	)

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().

01242 {
01243     mp_sign     sa;
01244 
01245     CHECK(a != NULL && b != NULL);
01246 
01247     sa = MP_SIGN(a);
01248     if (sa == MP_SIGN(b))
01249     {
01250         int         cmp = s_ucmp(a, b);
01251 
01252         /*
01253          * If they're both zero or positive, the normal comparison applies; if
01254          * both negative, the sense is reversed.
01255          */
01256         if (sa == MP_ZPOS)
01257             return cmp;
01258         else
01259             return -cmp;
01260 
01261     }
01262     else
01263     {
01264         if (sa == MP_ZPOS)
01265             return 1;
01266         else
01267             return -1;
01268     }
01269 }

int mp_int_compare_unsigned	(	mp_int	a,
		mp_int	b
	)

Definition at line 1276 of file imath.c.

References NRCHECK, NULL, and s_ucmp().

Referenced by mp_int_sqrt().

01277 {
01278     NRCHECK(a != NULL && b != NULL);
01279 
01280     return s_ucmp(a, b);
01281 }

int mp_int_compare_value	(	mp_int	z,
		int	value
	)

Definition at line 1305 of file imath.c.

References CHECK, cmp(), MP_NEG, MP_SIGN, MP_ZPOS, NULL, and s_vcmp().

Referenced by mp_int_invmod(), and mp_int_to_int().

01306 {
01307     mp_sign     vsign = (value < 0) ? MP_NEG : MP_ZPOS;
01308     int         cmp;
01309 
01310     CHECK(z != NULL);
01311 
01312     if (vsign == MP_SIGN(z))
01313     {
01314         cmp = s_vcmp(z, value);
01315 
01316         if (vsign == MP_ZPOS)
01317             return cmp;
01318         else
01319             return -cmp;
01320     }
01321     else
01322     {
01323         if (value < 0)
01324             return 1;
01325         else
01326             return -1;
01327     }
01328 }

int mp_int_compare_zero ( mp_int z )

Definition at line 1288 of file imath.c.

References mpz::digits, MP_SIGN, MP_USED, MP_ZPOS, NRCHECK, and NULL.

Referenced by mp_int_mul().

01289 {
01290     NRCHECK(z != NULL);
01291 
01292     if (MP_USED(z) == 1 && z->digits[0] == 0)
01293         return 0;
01294     else if (MP_SIGN(z) == MP_ZPOS)
01295         return 1;
01296     else
01297         return -1;
01298 }

mp_result mp_int_copy	(	mp_int	a,
		mp_int	c
	)

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().

00511 {
00512     CHECK(a != NULL && c != NULL);
00513 
00514     if (a != c)
00515     {
00516         mp_size     ua = MP_USED(a);
00517         mp_digit   *da,
00518                    *dc;
00519 
00520         if (!s_pad(c, ua))
00521             return MP_MEMORY;
00522 
00523         da = MP_DIGITS(a);
00524         dc = MP_DIGITS(c);
00525         COPY(da, dc, ua);
00526 
00527         MP_USED(c) = ua;
00528         MP_SIGN(c) = MP_SIGN(a);
00529     }
00530 
00531     return MP_OK;
00532 }

mp_result mp_int_count_bits ( mp_int z )

Definition at line 2072 of file imath.c.

References CHECK, mpz::digits, MP_DIGIT_BIT, 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().

02073 {
02074     mp_size     nbits = 0,
02075                 uz;
02076     mp_digit    d;
02077 
02078     CHECK(z != NULL);
02079 
02080     uz = MP_USED(z);
02081     if (uz == 1 && z->digits[0] == 0)
02082         return 1;
02083 
02084     --uz;
02085     nbits = uz * MP_DIGIT_BIT;
02086     d = z->digits[uz];
02087 
02088     while (d != 0)
02089     {
02090         d >>= 1;
02091         ++nbits;
02092     }
02093 
02094     return nbits;
02095 }

mp_result mp_int_div	(	mp_int	a,
		mp_int	b,
		mp_int	q,
		mp_int	r
	)

Definition at line 954 of file imath.c.

References CHECK, cmp(), 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().

00955 {
00956     int         cmp,
00957                 last = 0,
00958                 lg;
00959     mp_result   res = MP_OK;
00960     mpz_t       temp[2];
00961     mp_int      qout,
00962                 rout;
00963     mp_sign     sa = MP_SIGN(a),
00964                 sb = MP_SIGN(b);
00965 
00966     CHECK(a != NULL && b != NULL && q != r);
00967 
00968     if (CMPZ(b) == 0)
00969         return MP_UNDEF;
00970     else if ((cmp = s_ucmp(a, b)) < 0)
00971     {
00972         /*
00973          * If |a| < |b|, no division is required: q = 0, r = a
00974          */
00975         if (r && (res = mp_int_copy(a, r)) != MP_OK)
00976             return res;
00977 
00978         if (q)
00979             mp_int_zero(q);
00980 
00981         return MP_OK;
00982     }
00983     else if (cmp == 0)
00984     {
00985         /*
00986          * If |a| = |b|, no division is required: q = 1 or -1, r = 0
00987          */
00988         if (r)
00989             mp_int_zero(r);
00990 
00991         if (q)
00992         {
00993             mp_int_zero(q);
00994             q->digits[0] = 1;
00995 
00996             if (sa != sb)
00997                 MP_SIGN(q) = MP_NEG;
00998         }
00999 
01000         return MP_OK;
01001     }
01002 
01003     /*
01004      * When |a| > |b|, real division is required.  We need someplace to store
01005      * quotient and remainder, but q and r are allowed to be NULL or to
01006      * overlap with the inputs.
01007      */
01008     if ((lg = s_isp2(b)) < 0)
01009     {
01010         if (q && b != q && (res = mp_int_copy(a, q)) == MP_OK)
01011         {
01012             qout = q;
01013         }
01014         else
01015         {
01016             qout = TEMP(last);
01017             SETUP(mp_int_init_copy(TEMP(last), a), last);
01018         }
01019 
01020         if (r && a != r && (res = mp_int_copy(b, r)) == MP_OK)
01021         {
01022             rout = r;
01023         }
01024         else
01025         {
01026             rout = TEMP(last);
01027             SETUP(mp_int_init_copy(TEMP(last), b), last);
01028         }
01029 
01030         if ((res = s_udiv(qout, rout)) != MP_OK)
01031             goto CLEANUP;
01032     }
01033     else
01034     {
01035         if (q && (res = mp_int_copy(a, q)) != MP_OK)
01036             goto CLEANUP;
01037         if (r && (res = mp_int_copy(a, r)) != MP_OK)
01038             goto CLEANUP;
01039 
01040         if (q)
01041             s_qdiv(q, (mp_size) lg);
01042         qout = q;
01043         if (r)
01044             s_qmod(r, (mp_size) lg);
01045         rout = r;
01046     }
01047 
01048     /* Recompute signs for output */
01049     if (rout)
01050     {
01051         MP_SIGN(rout) = sa;
01052         if (CMPZ(rout) == 0)
01053             MP_SIGN(rout) = MP_ZPOS;
01054     }
01055     if (qout)
01056     {
01057         MP_SIGN(qout) = (sa == sb) ? MP_ZPOS : MP_NEG;
01058         if (CMPZ(qout) == 0)
01059             MP_SIGN(qout) = MP_ZPOS;
01060     }
01061 
01062     if (q && (res = mp_int_copy(qout, q)) != MP_OK)
01063         goto CLEANUP;
01064     if (r && (res = mp_int_copy(rout, r)) != MP_OK)
01065         goto CLEANUP;
01066 
01067 CLEANUP:
01068     while (--last >= 0)
01069         mp_int_clear(TEMP(last));
01070 
01071     return res;
01072 }

mp_result mp_int_div_pow2	(	mp_int	a,
		int	p2,
		mp_int	q,
		mp_int	r
	)

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().

01146 {
01147     mp_result   res = MP_OK;
01148 
01149     CHECK(a != NULL && p2 >= 0 && q != r);
01150 
01151     if (q != NULL && (res = mp_int_copy(a, q)) == MP_OK)
01152         s_qdiv(q, (mp_size) p2);
01153 
01154     if (res == MP_OK && r != NULL && (res = mp_int_copy(a, r)) == MP_OK)
01155         s_qmod(r, (mp_size) p2);
01156 
01157     return res;
01158 }

mp_result mp_int_div_value	(	mp_int	a,
		int	value,
		mp_int	q,
		int *	r
	)

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().

01119 {
01120     mpz_t       vtmp,
01121                 rtmp;
01122     mp_digit    vbuf[MP_VALUE_DIGITS(value)];
01123     mp_result   res;
01124 
01125     if ((res = mp_int_init(&rtmp)) != MP_OK)
01126         return res;
01127     s_fake(&vtmp, value, vbuf);
01128 
01129     if ((res = mp_int_div(a, &vtmp, q, &rtmp)) != MP_OK)
01130         goto CLEANUP;
01131 
01132     if (r)
01133         (void) mp_int_to_int(&rtmp, r); /* can't fail */
01134 
01135 CLEANUP:
01136     mp_int_clear(&rtmp);
01137     return res;
01138 }

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.

01781 {
01782     int         rem = 0;
01783 
01784     if (mp_int_div_value(a, v, NULL, &rem) != MP_OK)
01785         return 0;
01786 
01787     return rem == 0;
01788 }

mp_result mp_int_egcd	(	mp_int	a,
		mp_int	b,
		mp_int	c,
		mp_int	x,
		mp_int	y
	)

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().

01632 {
01633     int         k,
01634                 last = 0,
01635                 ca,
01636                 cb;
01637     mpz_t       temp[8];
01638     mp_result   res;
01639 
01640     CHECK(a != NULL && b != NULL && c != NULL &&
01641           (x != NULL || y != NULL));
01642 
01643     ca = CMPZ(a);
01644     cb = CMPZ(b);
01645     if (ca == 0 && cb == 0)
01646         return MP_UNDEF;
01647     else if (ca == 0)
01648     {
01649         if ((res = mp_int_abs(b, c)) != MP_OK)
01650             return res;
01651         mp_int_zero(x);
01652         (void) mp_int_set_value(y, 1);
01653         return MP_OK;
01654     }
01655     else if (cb == 0)
01656     {
01657         if ((res = mp_int_abs(a, c)) != MP_OK)
01658             return res;
01659         (void) mp_int_set_value(x, 1);
01660         mp_int_zero(y);
01661         return MP_OK;
01662     }
01663 
01664     /*
01665      * Initialize temporaries: A:0, B:1, C:2, D:3, u:4, v:5, ou:6, ov:7
01666      */
01667     for (last = 0; last < 4; ++last)
01668     {
01669         if ((res = mp_int_init(TEMP(last))) != MP_OK)
01670             goto CLEANUP;
01671     }
01672     TEMP(0)->digits[0] = 1;
01673     TEMP(3)->digits[0] = 1;
01674 
01675     SETUP(mp_int_init_copy(TEMP(4), a), last);
01676     SETUP(mp_int_init_copy(TEMP(5), b), last);
01677 
01678     /* We will work with absolute values here */
01679     MP_SIGN(TEMP(4)) = MP_ZPOS;
01680     MP_SIGN(TEMP(5)) = MP_ZPOS;
01681 
01682     {                           /* Divide out common factors of 2 from u and v */
01683         int         div2_u = s_dp2k(TEMP(4)),
01684                     div2_v = s_dp2k(TEMP(5));
01685 
01686         k = MIN(div2_u, div2_v);
01687         s_qdiv(TEMP(4), k);
01688         s_qdiv(TEMP(5), k);
01689     }
01690 
01691     SETUP(mp_int_init_copy(TEMP(6), TEMP(4)), last);
01692     SETUP(mp_int_init_copy(TEMP(7), TEMP(5)), last);
01693 
01694     for (;;)
01695     {
01696         while (mp_int_is_even(TEMP(4)))
01697         {
01698             s_qdiv(TEMP(4), 1);
01699 
01700             if (mp_int_is_odd(TEMP(0)) || mp_int_is_odd(TEMP(1)))
01701             {
01702                 if ((res = mp_int_add(TEMP(0), TEMP(7), TEMP(0))) != MP_OK)
01703                     goto CLEANUP;
01704                 if ((res = mp_int_sub(TEMP(1), TEMP(6), TEMP(1))) != MP_OK)
01705                     goto CLEANUP;
01706             }
01707 
01708             s_qdiv(TEMP(0), 1);
01709             s_qdiv(TEMP(1), 1);
01710         }
01711 
01712         while (mp_int_is_even(TEMP(5)))
01713         {
01714             s_qdiv(TEMP(5), 1);
01715 
01716             if (mp_int_is_odd(TEMP(2)) || mp_int_is_odd(TEMP(3)))
01717             {
01718                 if ((res = mp_int_add(TEMP(2), TEMP(7), TEMP(2))) != MP_OK)
01719                     goto CLEANUP;
01720                 if ((res = mp_int_sub(TEMP(3), TEMP(6), TEMP(3))) != MP_OK)
01721                     goto CLEANUP;
01722             }
01723 
01724             s_qdiv(TEMP(2), 1);
01725             s_qdiv(TEMP(3), 1);
01726         }
01727 
01728         if (mp_int_compare(TEMP(4), TEMP(5)) >= 0)
01729         {
01730             if ((res = mp_int_sub(TEMP(4), TEMP(5), TEMP(4))) != MP_OK)
01731                 goto CLEANUP;
01732             if ((res = mp_int_sub(TEMP(0), TEMP(2), TEMP(0))) != MP_OK)
01733                 goto CLEANUP;
01734             if ((res = mp_int_sub(TEMP(1), TEMP(3), TEMP(1))) != MP_OK)
01735                 goto CLEANUP;
01736         }
01737         else
01738         {
01739             if ((res = mp_int_sub(TEMP(5), TEMP(4), TEMP(5))) != MP_OK)
01740                 goto CLEANUP;
01741             if ((res = mp_int_sub(TEMP(2), TEMP(0), TEMP(2))) != MP_OK)
01742                 goto CLEANUP;
01743             if ((res = mp_int_sub(TEMP(3), TEMP(1), TEMP(3))) != MP_OK)
01744                 goto CLEANUP;
01745         }
01746 
01747         if (CMPZ(TEMP(4)) == 0)
01748         {
01749             if (x && (res = mp_int_copy(TEMP(2), x)) != MP_OK)
01750                 goto CLEANUP;
01751             if (y && (res = mp_int_copy(TEMP(3), y)) != MP_OK)
01752                 goto CLEANUP;
01753             if (c)
01754             {
01755                 if (!s_qmul(TEMP(5), k))
01756                 {
01757                     res = MP_MEMORY;
01758                     goto CLEANUP;
01759                 }
01760 
01761                 res = mp_int_copy(TEMP(5), c);
01762             }
01763 
01764             break;
01765         }
01766     }
01767 
01768 CLEANUP:
01769     while (--last >= 0)
01770         mp_int_clear(TEMP(last));
01771 
01772     return res;
01773 }

mp_result mp_int_expt	(	mp_int	a,
		int	b,
		mp_int	c
	)

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.

01166 {
01167     mpz_t       t;
01168     mp_result   res;
01169     unsigned int v = abs(b);
01170 
01171     CHECK(b >= 0 && c != NULL);
01172 
01173     if ((res = mp_int_init_copy(&t, a)) != MP_OK)
01174         return res;
01175 
01176     (void) mp_int_set_value(c, 1);
01177     while (v != 0)
01178     {
01179         if (v & 1)
01180         {
01181             if ((res = mp_int_mul(c, &t, c)) != MP_OK)
01182                 goto CLEANUP;
01183         }
01184 
01185         v >>= 1;
01186         if (v == 0)
01187             break;
01188 
01189         if ((res = mp_int_sqr(&t, &t)) != MP_OK)
01190             goto CLEANUP;
01191     }
01192 
01193 CLEANUP:
01194     mp_int_clear(&t);
01195     return res;
01196 }

mp_result mp_int_expt_value	(	int	a,
		int	b,
		mp_int	c
	)

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.

01204 {
01205     mpz_t       t;
01206     mp_result   res;
01207     unsigned int v = abs(b);
01208 
01209     CHECK(b >= 0 && c != NULL);
01210 
01211     if ((res = mp_int_init_value(&t, a)) != MP_OK)
01212         return res;
01213 
01214     (void) mp_int_set_value(c, 1);
01215     while (v != 0)
01216     {
01217         if (v & 1)
01218         {
01219             if ((res = mp_int_mul(c, &t, c)) != MP_OK)
01220                 goto CLEANUP;
01221         }
01222 
01223         v >>= 1;
01224         if (v == 0)
01225             break;
01226 
01227         if ((res = mp_int_sqr(&t, &t)) != MP_OK)
01228             goto CLEANUP;
01229     }
01230 
01231 CLEANUP:
01232     mp_int_clear(&t);
01233     return res;
01234 }

mp_result mp_int_exptmod	(	mp_int	a,
		mp_int	b,
		mp_int	m,
		mp_int	c
	)

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().

01336 {
01337     mp_result   res;
01338     mp_size     um;
01339     mpz_t       temp[3];
01340     mp_int      s;
01341     int         last = 0;
01342 
01343     CHECK(a != NULL && b != NULL && c != NULL && m != NULL);
01344 
01345     /* Zero moduli and negative exponents are not considered. */
01346     if (CMPZ(m) == 0)
01347         return MP_UNDEF;
01348     if (CMPZ(b) < 0)
01349         return MP_RANGE;
01350 
01351     um = MP_USED(m);
01352     SETUP(mp_int_init_size(TEMP(0), 2 * um), last);
01353     SETUP(mp_int_init_size(TEMP(1), 2 * um), last);
01354 
01355     if (c == b || c == m)
01356     {
01357         SETUP(mp_int_init_size(TEMP(2), 2 * um), last);
01358         s = TEMP(2);
01359     }
01360     else
01361     {
01362         s = c;
01363     }
01364 
01365     if ((res = mp_int_mod(a, m, TEMP(0))) != MP_OK)
01366         goto CLEANUP;
01367 
01368     if ((res = s_brmu(TEMP(1), m)) != MP_OK)
01369         goto CLEANUP;
01370 
01371     if ((res = s_embar(TEMP(0), b, m, TEMP(1), s)) != MP_OK)
01372         goto CLEANUP;
01373 
01374     res = mp_int_copy(s, c);
01375 
01376 CLEANUP:
01377     while (--last >= 0)
01378         mp_int_clear(TEMP(last));
01379 
01380     return res;
01381 }

mp_result mp_int_exptmod_bvalue	(	int	value,
		mp_int	b,
		mp_int	m,
		mp_int	c
	)

Definition at line 1403 of file imath.c.

References mp_int_exptmod(), MP_VALUE_DIGITS, and s_fake().

01405 {
01406     mpz_t       vtmp;
01407     mp_digit    vbuf[MP_VALUE_DIGITS(value)];
01408 
01409     s_fake(&vtmp, value, vbuf);
01410 
01411     return mp_int_exptmod(&vtmp, b, m, c);
01412 }

mp_result mp_int_exptmod_evalue	(	mp_int	a,
		int	value,
		mp_int	m,
		mp_int	c
	)

Definition at line 1388 of file imath.c.

References mp_int_exptmod(), MP_VALUE_DIGITS, and s_fake().

01389 {
01390     mpz_t       vtmp;
01391     mp_digit    vbuf[MP_VALUE_DIGITS(value)];
01392 
01393     s_fake(&vtmp, value, vbuf);
01394 
01395     return mp_int_exptmod(a, &vtmp, m, c);
01396 }

mp_result mp_int_exptmod_known	(	mp_int	a,
		mp_int	b,
		mp_int	m,
		mp_int	mu,
		mp_int	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.

01420 {
01421     mp_result   res;
01422     mp_size     um;
01423     mpz_t       temp[2];
01424     mp_int      s;
01425     int         last = 0;
01426 
01427     CHECK(a && b && m && c);
01428 
01429     /* Zero moduli and negative exponents are not considered. */
01430     if (CMPZ(m) == 0)
01431         return MP_UNDEF;
01432     if (CMPZ(b) < 0)
01433         return MP_RANGE;
01434 
01435     um = MP_USED(m);
01436     SETUP(mp_int_init_size(TEMP(0), 2 * um), last);
01437 
01438     if (c == b || c == m)
01439     {
01440         SETUP(mp_int_init_size(TEMP(1), 2 * um), last);
01441         s = TEMP(1);
01442     }
01443     else
01444     {
01445         s = c;
01446     }
01447 
01448     if ((res = mp_int_mod(a, m, TEMP(0))) != MP_OK)
01449         goto CLEANUP;
01450 
01451     if ((res = s_embar(TEMP(0), b, m, mu, s)) != MP_OK)
01452         goto CLEANUP;
01453 
01454     res = mp_int_copy(s, c);
01455 
01456 CLEANUP:
01457     while (--last >= 0)
01458         mp_int_clear(TEMP(last));
01459 
01460     return res;
01461 }

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().

00496 {
00497     NRCHECK(z != NULL);
00498 
00499     if (z->digits != NULL)
00500         mp_int_clear(z);
00501 
00502     px_free(z);
00503 }

mp_result mp_int_gcd	(	mp_int	a,
		mp_int	b,
		mp_int	c
	)

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().

01536 {
01537     int         ca,
01538                 cb,
01539                 k = 0;
01540     mpz_t       u,
01541                 v,
01542                 t;
01543     mp_result   res;
01544 
01545     CHECK(a != NULL && b != NULL && c != NULL);
01546 
01547     ca = CMPZ(a);
01548     cb = CMPZ(b);
01549     if (ca == 0 && cb == 0)
01550         return MP_UNDEF;
01551     else if (ca == 0)
01552         return mp_int_abs(b, c);
01553     else if (cb == 0)
01554         return mp_int_abs(a, c);
01555 
01556     if ((res = mp_int_init(&t)) != MP_OK)
01557         return res;
01558     if ((res = mp_int_init_copy(&u, a)) != MP_OK)
01559         goto U;
01560     if ((res = mp_int_init_copy(&v, b)) != MP_OK)
01561         goto V;
01562 
01563     MP_SIGN(&u) = MP_ZPOS;
01564     MP_SIGN(&v) = MP_ZPOS;
01565 
01566     {                           /* Divide out common factors of 2 from u and v */
01567         int         div2_u = s_dp2k(&u),
01568                     div2_v = s_dp2k(&v);
01569 
01570         k = MIN(div2_u, div2_v);
01571         s_qdiv(&u, (mp_size) k);
01572         s_qdiv(&v, (mp_size) k);
01573     }
01574 
01575     if (mp_int_is_odd(&u))
01576     {
01577         if ((res = mp_int_neg(&v, &t)) != MP_OK)
01578             goto CLEANUP;
01579     }
01580     else
01581     {
01582         if ((res = mp_int_copy(&u, &t)) != MP_OK)
01583             goto CLEANUP;
01584     }
01585 
01586     for (;;)
01587     {
01588         s_qdiv(&t, s_dp2k(&t));
01589 
01590         if (CMPZ(&t) > 0)
01591         {
01592             if ((res = mp_int_copy(&t, &u)) != MP_OK)
01593                 goto CLEANUP;
01594         }
01595         else
01596         {
01597             if ((res = mp_int_neg(&t, &v)) != MP_OK)
01598                 goto CLEANUP;
01599         }
01600 
01601         if ((res = mp_int_sub(&u, &v, &t)) != MP_OK)
01602             goto CLEANUP;
01603 
01604         if (CMPZ(&t) == 0)
01605             break;
01606     }
01607 
01608     if ((res = mp_int_abs(&u, c)) != MP_OK)
01609         goto CLEANUP;
01610     if (!s_qmul(c, (mp_size) k))
01611         res = MP_MEMORY;
01612 
01613 CLEANUP:
01614     mp_int_clear(&v);
01615 V: mp_int_clear(&u);
01616 U: mp_int_clear(&t);
01617 
01618     return res;
01619 }

mp_result mp_int_init ( mp_int z )

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().

00362 {
00363     return mp_int_init_size(z, default_precision);
00364 }

mp_result mp_int_init_copy	(	mp_int	z,
		mp_int	old
	)

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().

00413 {
00414     mp_result   res;
00415     mp_size     uold,
00416                 target;
00417 
00418     CHECK(z != NULL && old != NULL);
00419 
00420     uold = MP_USED(old);
00421     target = MAX(uold, default_precision);
00422 
00423     if ((res = mp_int_init_size(z, target)) != MP_OK)
00424         return res;
00425 
00426     MP_USED(z) = uold;
00427     MP_SIGN(z) = MP_SIGN(old);
00428     COPY(MP_DIGITS(old), MP_DIGITS(z), uold);
00429 
00430     return MP_OK;
00431 }

mp_result mp_int_init_size	(	mp_int	z,
		mp_size	prec
	)

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().

00390 {
00391     CHECK(z != NULL);
00392 
00393     prec = (mp_size) ROUND_PREC(prec);
00394     prec = MAX(prec, default_precision);
00395 
00396     if ((MP_DIGITS(z) = s_alloc(prec)) == NULL)
00397         return MP_MEMORY;
00398 
00399     z->digits[0] = 0;
00400     MP_USED(z) = 1;
00401     MP_ALLOC(z) = prec;
00402     MP_SIGN(z) = MP_ZPOS;
00403 
00404     return MP_OK;
00405 }

mp_result mp_int_init_value	(	mp_int	z,
		int	value
	)

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().

00439 {
00440     mp_result   res;
00441 
00442     CHECK(z != NULL);
00443 
00444     if ((res = mp_int_init(z)) != MP_OK)
00445         return res;
00446 
00447     return mp_int_set_value(z, value);
00448 }

mp_result mp_int_invmod	(	mp_int	a,
		mp_int	m,
		mp_int	c
	)

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().

01481 {
01482     mp_result   res;
01483     mp_sign     sa;
01484     int         last = 0;
01485     mpz_t       temp[2];
01486 
01487     CHECK(a != NULL && m != NULL && c != NULL);
01488 
01489     if (CMPZ(a) == 0 || CMPZ(m) <= 0)
01490         return MP_RANGE;
01491 
01492     sa = MP_SIGN(a);            /* need this for the result later */
01493 
01494     for (last = 0; last < 2; ++last)
01495         if ((res = mp_int_init(TEMP(last))) != MP_OK)
01496             goto CLEANUP;
01497 
01498     if ((res = mp_int_egcd(a, m, TEMP(0), TEMP(1), NULL)) != MP_OK)
01499         goto CLEANUP;
01500 
01501     if (mp_int_compare_value(TEMP(0), 1) != 0)
01502     {
01503         res = MP_UNDEF;
01504         goto CLEANUP;
01505     }
01506 
01507     /* It is first necessary to constrain the value to the proper range */
01508     if ((res = mp_int_mod(TEMP(1), m, TEMP(1))) != MP_OK)
01509         goto CLEANUP;
01510 
01511     /*
01512      * Now, if 'a' was originally negative, the value we have is actually the
01513      * magnitude of the negative representative; to get the positive value we
01514      * have to subtract from the modulus.  Otherwise, the value is okay as it
01515      * stands.
01516      */
01517     if (sa == MP_NEG)
01518         res = mp_int_sub(m, TEMP(1), c);
01519     else
01520         res = mp_int_copy(TEMP(1), c);
01521 
01522 CLEANUP:
01523     while (--last >= 0)
01524         mp_int_clear(TEMP(last));
01525 
01526     return res;
01527 }

int mp_int_is_pow2 ( mp_int z )

Definition at line 1795 of file imath.c.

References CHECK, NULL, and s_isp2().

01796 {
01797     CHECK(z != NULL);
01798 
01799     return s_isp2(z);
01800 }

mp_result mp_int_mod	(	mp_int	a,
		mp_int	m,
		mp_int	c
	)

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().

01080 {
01081     mp_result   res;
01082     mpz_t       tmp;
01083     mp_int      out;
01084 
01085     if (m == c)
01086     {
01087         if ((res = mp_int_init(&tmp)) != MP_OK)
01088             return res;
01089 
01090         out = &tmp;
01091     }
01092     else
01093     {
01094         out = c;
01095     }
01096 
01097     if ((res = mp_int_div(a, m, NULL, out)) != MP_OK)
01098         goto CLEANUP;
01099 
01100     if (CMPZ(out) < 0)
01101         res = mp_int_add(out, m, c);
01102     else
01103         res = mp_int_copy(out, c);
01104 
01105 CLEANUP:
01106     if (out != c)
01107         mp_int_clear(&tmp);
01108 
01109     return res;
01110 }

mp_result mp_int_mul	(	mp_int	a,
		mp_int	b,
		mp_int	c
	)

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().

00795 {
00796     mp_digit   *out;
00797     mp_size     osize,
00798                 ua,
00799                 ub,
00800                 p = 0;
00801     mp_sign     osign;
00802 
00803     CHECK(a != NULL && b != NULL && c != NULL);
00804 
00805     /* If either input is zero, we can shortcut multiplication */
00806     if (mp_int_compare_zero(a) == 0 || mp_int_compare_zero(b) == 0)
00807     {
00808         mp_int_zero(c);
00809         return MP_OK;
00810     }
00811 
00812     /* Output is positive if inputs have same sign, otherwise negative */
00813     osign = (MP_SIGN(a) == MP_SIGN(b)) ? MP_ZPOS : MP_NEG;
00814 
00815     /*
00816      * If the output is not equal to any of the inputs, we'll write the
00817      * results there directly; otherwise, allocate a temporary space.
00818      */
00819     ua = MP_USED(a);
00820     ub = MP_USED(b);
00821     osize = ua + ub;
00822 
00823     if (c == a || c == b)
00824     {
00825         p = ROUND_PREC(osize);
00826         p = MAX(p, default_precision);
00827 
00828         if ((out = s_alloc(p)) == NULL)
00829             return MP_MEMORY;
00830     }
00831     else
00832     {
00833         if (!s_pad(c, osize))
00834             return MP_MEMORY;
00835 
00836         out = MP_DIGITS(c);
00837     }
00838     ZERO(out, osize);
00839 
00840     if (!s_kmul(MP_DIGITS(a), MP_DIGITS(b), out, ua, ub))
00841         return MP_MEMORY;
00842 
00843     /*
00844      * If we allocated a new buffer, get rid of whatever memory c was already
00845      * using, and fix up its fields to reflect that.
00846      */
00847     if (out != MP_DIGITS(c))
00848     {
00849         s_free(MP_DIGITS(c));
00850         MP_DIGITS(c) = out;
00851         MP_ALLOC(c) = p;
00852     }
00853 
00854     MP_USED(c) = osize;         /* might not be true, but we'll fix it ... */
00855     CLAMP(c);                   /* ... right here */
00856     MP_SIGN(c) = osign;
00857 
00858     return MP_OK;
00859 }

mp_result mp_int_mul_pow2	(	mp_int	a,
		int	p2,
		mp_int	c
	)

Definition at line 881 of file imath.c.

References CHECK, mp_int_copy(), MP_MEMORY, MP_OK, NULL, and s_qmul().

00882 {
00883     mp_result   res;
00884 
00885     CHECK(a != NULL && c != NULL && p2 >= 0);
00886 
00887     if ((res = mp_int_copy(a, c)) != MP_OK)
00888         return res;
00889 
00890     if (s_qmul(c, (mp_size) p2))
00891         return MP_OK;
00892     else
00893         return MP_MEMORY;
00894 }

mp_result mp_int_mul_value	(	mp_int	a,
		int	value,
		mp_int	c
	)

Definition at line 866 of file imath.c.

References mp_int_mul(), MP_VALUE_DIGITS, and s_fake().

00867 {
00868     mpz_t       vtmp;
00869     mp_digit    vbuf[MP_VALUE_DIGITS(value)];
00870 
00871     s_fake(&vtmp, value, vbuf);
00872 
00873     return mp_int_mul(a, &vtmp, c);
00874 }

mp_result mp_int_neg	(	mp_int	a,
		mp_int	c
	)

Definition at line 587 of file imath.c.

References CHECK, CMPZ, mp_int_copy(), MP_OK, MP_SIGN, and NULL.

Referenced by mp_int_gcd().

00588 {
00589     mp_result   res;
00590 
00591     CHECK(a != NULL && c != NULL);
00592 
00593     if ((res = mp_int_copy(a, c)) != MP_OK)
00594         return res;
00595 
00596     if (CMPZ(c) != 0)
00597         MP_SIGN(c) = 1 - MP_SIGN(a);
00598 
00599     return MP_OK;
00600 }

mp_result mp_int_read_binary	(	mp_int	z,
		unsigned char *	buf,
		int	len
	)

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().

02125 {
02126     mp_size     need,
02127                 i;
02128     unsigned char *tmp;
02129     mp_digit   *dz;
02130 
02131     CHECK(z != NULL && buf != NULL && len > 0);
02132 
02133     /* Figure out how many digits are needed to represent this value */
02134     need = ((len * CHAR_BIT) + (MP_DIGIT_BIT - 1)) / MP_DIGIT_BIT;
02135     if (!s_pad(z, need))
02136         return MP_MEMORY;
02137 
02138     mp_int_zero(z);
02139 
02140     /*
02141      * If the high-order bit is set, take the 2's complement before reading
02142      * the value (it will be restored afterward)
02143      */
02144     if (buf[0] >> (CHAR_BIT - 1))
02145     {
02146         MP_SIGN(z) = MP_NEG;
02147         s_2comp(buf, len);
02148     }
02149 
02150     dz = MP_DIGITS(z);
02151     for (tmp = buf, i = len; i > 0; --i, ++tmp)
02152     {
02153         s_qmul(z, (mp_size) CHAR_BIT);
02154         *dz |= *tmp;
02155     }
02156 
02157     /* Restore 2's complement if we took it before */
02158     if (MP_SIGN(z) == MP_NEG)
02159         s_2comp(buf, len);
02160 
02161     return MP_OK;
02162 }

mp_result mp_int_read_cstring	(	mp_int	z,
		mp_size	radix,
		const char *	str,
		char **	end
	)

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().

02004 {
02005     int         ch;
02006 
02007     CHECK(z != NULL && str != NULL);
02008 
02009     if (radix < MP_MIN_RADIX || radix > MP_MAX_RADIX)
02010         return MP_RANGE;
02011 
02012     /* Skip leading whitespace */
02013     while (isspace((unsigned char) *str))
02014         ++str;
02015 
02016     /* Handle leading sign tag (+/-, positive default) */
02017     switch (*str)
02018     {
02019         case '-':
02020             MP_SIGN(z) = MP_NEG;
02021             ++str;
02022             break;
02023         case '+':
02024             ++str;              /* fallthrough */
02025         default:
02026             MP_SIGN(z) = MP_ZPOS;
02027             break;
02028     }
02029 
02030     /* Skip leading zeroes */
02031     while ((ch = s_ch2val(*str, radix)) == 0)
02032         ++str;
02033 
02034     /* Make sure there is enough space for the value */
02035     if (!s_pad(z, s_inlen(strlen(str), radix)))
02036         return MP_MEMORY;
02037 
02038     MP_USED(z) = 1;
02039     z->digits[0] = 0;
02040 
02041     while (*str != '\0' && ((ch = s_ch2val(*str, radix)) >= 0))
02042     {
02043         s_dmul(z, (mp_digit) radix);
02044         s_dadd(z, (mp_digit) ch);
02045         ++str;
02046     }
02047 
02048     CLAMP(z);
02049 
02050     /* Override sign for zero, even if negative specified. */
02051     if (CMPZ(z) == 0)
02052         MP_SIGN(z) = MP_ZPOS;
02053 
02054     if (end != NULL)
02055         *end = (char *) str;
02056 
02057     /*
02058      * Return a truncation error if the string has unprocessed characters
02059      * remaining, so the caller can tell if the whole string was done
02060      */
02061     if (*str != '\0')
02062         return MP_TRUNC;
02063     else
02064         return MP_OK;
02065 }

mp_result mp_int_read_string	(	mp_int	z,
		mp_size	radix,
		const char *	str
	)

Definition at line 1992 of file imath.c.

References mp_int_read_cstring(), and NULL.

01993 {
01994     return mp_int_read_cstring(z, radix, str, NULL);
01995 
01996 }

mp_result mp_int_read_unsigned	(	mp_int	z,
		unsigned char *	buf,
		int	len
	)

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().

02210 {
02211     mp_size     need,
02212                 i;
02213     unsigned char *tmp;
02214     mp_digit   *dz;
02215 
02216     CHECK(z != NULL && buf != NULL && len > 0);
02217 
02218     /* Figure out how many digits are needed to represent this value */
02219     need = ((len * CHAR_BIT) + (MP_DIGIT_BIT - 1)) / MP_DIGIT_BIT;
02220     if (!s_pad(z, need))
02221         return MP_MEMORY;
02222 
02223     mp_int_zero(z);
02224 
02225     dz = MP_DIGITS(z);
02226     for (tmp = buf, i = len; i > 0; --i, ++tmp)
02227     {
02228         (void) s_qmul(z, CHAR_BIT);
02229         *dz |= *tmp;
02230     }
02231 
02232     return MP_OK;
02233 }

mp_result mp_int_redux_const	(	mp_int	m,
		mp_int	c
	)

Definition at line 1468 of file imath.c.

References CHECK, NULL, and s_brmu().

01469 {
01470     CHECK(m != NULL && c != NULL && m != c);
01471 
01472     return s_brmu(c, m);
01473 }

mp_result mp_int_set_value	(	mp_int	z,
		int	value
	)

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().

00456 {
00457     mp_size     ndig;
00458 
00459     CHECK(z != NULL);
00460 
00461     /* How many digits to copy */
00462     ndig = (mp_size) MP_VALUE_DIGITS(value);
00463 
00464     if (!s_pad(z, ndig))
00465         return MP_MEMORY;
00466 
00467     MP_USED(z) = (mp_size) s_vpack(value, MP_DIGITS(z));
00468     MP_SIGN(z) = (value < 0) ? MP_NEG : MP_ZPOS;
00469 
00470     return MP_OK;
00471 }

mp_result mp_int_sqr	(	mp_int	a,
		mp_int	c
	)

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().

00902 {
00903     mp_digit   *out;
00904     mp_size     osize,
00905                 p = 0;
00906 
00907     CHECK(a != NULL && c != NULL);
00908 
00909     /* Get a temporary buffer big enough to hold the result */
00910     osize = (mp_size) 2 *MP_USED(a);
00911 
00912     if (a == c)
00913     {
00914         p = ROUND_PREC(osize);
00915         p = MAX(p, default_precision);
00916 
00917         if ((out = s_alloc(p)) == NULL)
00918             return MP_MEMORY;
00919     }
00920     else
00921     {
00922         if (!s_pad(c, osize))
00923             return MP_MEMORY;
00924 
00925         out = MP_DIGITS(c);
00926     }
00927     ZERO(out, osize);
00928 
00929     s_ksqr(MP_DIGITS(a), out, MP_USED(a));
00930 
00931     /*
00932      * Get rid of whatever memory c was already using, and fix up its fields
00933      * to reflect the new digit array it's using
00934      */
00935     if (out != MP_DIGITS(c))
00936     {
00937         s_free(MP_DIGITS(c));
00938         MP_DIGITS(c) = out;
00939         MP_ALLOC(c) = p;
00940     }
00941 
00942     MP_USED(c) = osize;         /* might not be true, but we'll fix it ... */
00943     CLAMP(c);                   /* ... right here */
00944     MP_SIGN(c) = MP_ZPOS;
00945 
00946     return MP_OK;
00947 }

mp_result mp_int_sqrt	(	mp_int	a,
		mp_int	c
	)

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.

01808 {
01809     mp_result   res = MP_OK;
01810     mpz_t       temp[2];
01811     int         last = 0;
01812 
01813     CHECK(a != NULL && c != NULL);
01814 
01815     /* The square root of a negative value does not exist in the integers. */
01816     if (MP_SIGN(a) == MP_NEG)
01817         return MP_UNDEF;
01818 
01819     SETUP(mp_int_init_copy(TEMP(last), a), last);
01820     SETUP(mp_int_init(TEMP(last)), last);
01821 
01822     for (;;)
01823     {
01824         if ((res = mp_int_sqr(TEMP(0), TEMP(1))) != MP_OK)
01825             goto CLEANUP;
01826 
01827         if (mp_int_compare_unsigned(a, TEMP(1)) == 0)
01828             break;
01829 
01830         if ((res = mp_int_copy(a, TEMP(1))) != MP_OK)
01831             goto CLEANUP;
01832         if ((res = mp_int_div(TEMP(1), TEMP(0), TEMP(1), NULL)) != MP_OK)
01833             goto CLEANUP;
01834         if ((res = mp_int_add(TEMP(0), TEMP(1), TEMP(1))) != MP_OK)
01835             goto CLEANUP;
01836         if ((res = mp_int_div_pow2(TEMP(1), 1, TEMP(1), NULL)) != MP_OK)
01837             goto CLEANUP;
01838 
01839         if (mp_int_compare_unsigned(TEMP(0), TEMP(1)) == 0)
01840             break;
01841         if ((res = mp_int_sub_value(TEMP(0), 1, TEMP(0))) != MP_OK)
01842             goto CLEANUP;
01843         if (mp_int_compare_unsigned(TEMP(0), TEMP(1)) == 0)
01844             break;
01845 
01846         if ((res = mp_int_copy(TEMP(1), TEMP(0))) != MP_OK)
01847             goto CLEANUP;
01848     }
01849 
01850     res = mp_int_copy(TEMP(0), c);
01851 
01852 CLEANUP:
01853     while (--last >= 0)
01854         mp_int_clear(TEMP(last));
01855 
01856     return res;
01857 }

mp_result mp_int_string_len	(	mp_int	z,
		mp_size	radix
	)

Definition at line 1968 of file imath.c.

References CHECK, MP_MAX_RADIX, MP_NEG, MP_RANGE, MP_SIGN, NULL, and s_outlen().

01969 {
01970     int         len;
01971 
01972     CHECK(z != NULL);
01973 
01974     if (radix < MP_MIN_RADIX || radix > MP_MAX_RADIX)
01975         return MP_RANGE;
01976 
01977     len = s_outlen(z, radix) + 1;       /* for terminator */
01978 
01979     /* Allow for sign marker on negatives */
01980     if (MP_SIGN(z) == MP_NEG)
01981         len += 1;
01982 
01983     return len;
01984 }

mp_result mp_int_sub	(	mp_int	a,
		mp_int	b,
		mp_int	c
	)

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().

00700 {
00701     mp_size     ua,
00702                 ub,
00703                 uc,
00704                 max;
00705 
00706     CHECK(a != NULL && b != NULL && c != NULL);
00707 
00708     ua = MP_USED(a);
00709     ub = MP_USED(b);
00710     uc = MP_USED(c);
00711     max = MAX(ua, ub);
00712 
00713     if (MP_SIGN(a) != MP_SIGN(b))
00714     {
00715         /* Different signs -- add magnitudes and keep sign of a */
00716         mp_digit    carry;
00717 
00718         if (!s_pad(c, max))
00719             return MP_MEMORY;
00720 
00721         carry = s_uadd(MP_DIGITS(a), MP_DIGITS(b), MP_DIGITS(c), ua, ub);
00722         uc = max;
00723 
00724         if (carry)
00725         {
00726             if (!s_pad(c, max + 1))
00727                 return MP_MEMORY;
00728 
00729             c->digits[max] = carry;
00730             ++uc;
00731         }
00732 
00733         MP_USED(c) = uc;
00734         MP_SIGN(c) = MP_SIGN(a);
00735 
00736     }
00737     else
00738     {
00739         /* Same signs -- subtract magnitudes */
00740         mp_int      x,
00741                     y;
00742         mp_sign     osign;
00743         int         cmp = s_ucmp(a, b);
00744 
00745         if (!s_pad(c, max))
00746             return MP_MEMORY;
00747 
00748         if (cmp >= 0)
00749         {
00750             x = a;
00751             y = b;
00752             osign = MP_ZPOS;
00753         }
00754         else
00755         {
00756             x = b;
00757             y = a;
00758             osign = MP_NEG;
00759         }
00760 
00761         if (MP_SIGN(a) == MP_NEG && cmp != 0)
00762             osign = 1 - osign;
00763 
00764         s_usub(MP_DIGITS(x), MP_DIGITS(y), MP_DIGITS(c), MP_USED(x), MP_USED(y));
00765         MP_USED(c) = MP_USED(x);
00766         CLAMP(c);
00767 
00768         MP_SIGN(c) = osign;
00769     }
00770 
00771     return MP_OK;
00772 }

mp_result mp_int_sub_value	(	mp_int	a,
		int	value,
		mp_int	c
	)

Definition at line 779 of file imath.c.

References mp_int_sub(), MP_VALUE_DIGITS, and s_fake().

Referenced by mp_int_sqrt().

00780 {
00781     mpz_t       vtmp;
00782     mp_digit    vbuf[MP_VALUE_DIGITS(value)];
00783 
00784     s_fake(&vtmp, value, vbuf);
00785 
00786     return mp_int_sub(a, &vtmp, c);
00787 }

void mp_int_swap	(	mp_int	a,
		mp_int	c
	)

Definition at line 539 of file imath.c.

00540 {
00541     if (a != c)
00542     {
00543         mpz_t       tmp = *a;
00544 
00545         *a = *c;
00546         *c = tmp;
00547     }
00548 }

mp_result mp_int_to_binary	(	mp_int	z,
		unsigned char *	buf,
		int	limit
	)

Definition at line 2102 of file imath.c.

References CHECK, MP_NEG, MP_SIGN, NULL, s_2comp(), and s_tobin().

02103 {
02104     static const int PAD_FOR_2C = 1;
02105 
02106     mp_result   res;
02107     int         limpos = limit;
02108 
02109     CHECK(z != NULL && buf != NULL);
02110 
02111     res = s_tobin(z, buf, &limpos, PAD_FOR_2C);
02112 
02113     if (MP_SIGN(z) == MP_NEG)
02114         s_2comp(buf, limpos);
02115 
02116     return res;
02117 }

mp_result mp_int_to_int	(	mp_int	z,
		int *	out
	)

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().

01865 {
01866     unsigned int uv = 0;
01867     mp_size     uz;
01868     mp_digit   *dz;
01869     mp_sign     sz;
01870 
01871     CHECK(z != NULL);
01872 
01873     /* Make sure the value is representable as an int */
01874     sz = MP_SIGN(z);
01875     if ((sz == MP_ZPOS && mp_int_compare_value(z, INT_MAX) > 0) ||
01876         mp_int_compare_value(z, INT_MIN) < 0)
01877         return MP_RANGE;
01878 
01879     uz = MP_USED(z);
01880     dz = MP_DIGITS(z) + uz - 1;
01881 
01882     while (uz > 0)
01883     {
01884         uv <<= MP_DIGIT_BIT / 2;
01885         uv = (uv << (MP_DIGIT_BIT / 2)) | *dz--;
01886         --uz;
01887     }
01888 
01889     if (out)
01890         *out = (sz == MP_NEG) ? -(int) uv : (int) uv;
01891 
01892     return MP_OK;
01893 }

mp_result mp_int_to_string	(	mp_int	z,
		mp_size	radix,
		char *	str,
		int	limit
	)

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().

01902 {
01903     mp_result   res;
01904     int         cmp = 0;
01905 
01906     CHECK(z != NULL && str != NULL && limit >= 2);
01907 
01908     if (radix < MP_MIN_RADIX || radix > MP_MAX_RADIX)
01909         return MP_RANGE;
01910 
01911     if (CMPZ(z) == 0)
01912     {
01913         *str++ = s_val2ch(0, mp_flags & MP_CAP_DIGITS);
01914     }
01915     else
01916     {
01917         mpz_t       tmp;
01918         char       *h,
01919                    *t;
01920 
01921         if ((res = mp_int_init_copy(&tmp, z)) != MP_OK)
01922             return res;
01923 
01924         if (MP_SIGN(z) == MP_NEG)
01925         {
01926             *str++ = '-';
01927             --limit;
01928         }
01929         h = str;
01930 
01931         /* Generate digits in reverse order until finished or limit reached */
01932         for ( /* */ ; limit > 0; --limit)
01933         {
01934             mp_digit    d;
01935 
01936             if ((cmp = CMPZ(&tmp)) == 0)
01937                 break;
01938 
01939             d = s_ddiv(&tmp, (mp_digit) radix);
01940             *str++ = s_val2ch(d, mp_flags & MP_CAP_DIGITS);
01941         }
01942         t = str - 1;
01943 
01944         /* Put digits back in correct output order */
01945         while (h < t)
01946         {
01947             char        tc = *h;
01948 
01949             *h++ = *t;
01950             *t-- = tc;
01951         }
01952 
01953         mp_int_clear(&tmp);
01954     }
01955 
01956     *str = '\0';
01957     if (cmp == 0)
01958         return MP_OK;
01959     else
01960         return MP_TRUNC;
01961 }

mp_result mp_int_to_unsigned	(	mp_int	z,
		unsigned char *	buf,
		int	limit
	)

Definition at line 2195 of file imath.c.

References CHECK, NULL, and s_tobin().

Referenced by bn_to_mpi().

02196 {
02197     static const int NO_PADDING = 0;
02198 
02199     CHECK(z != NULL && buf != NULL);
02200 
02201     return s_tobin(z, buf, &limit, NO_PADDING);
02202 }

mp_result mp_int_unsigned_len ( mp_int z )

Definition at line 2240 of file imath.c.

References mp_int_count_bits().

Referenced by mp_int_binary_len().

02241 {
02242     mp_result   res = mp_int_count_bits(z);
02243     int         bytes;
02244 
02245     if (res <= 0)
02246         return res;
02247 
02248     bytes = (res + (CHAR_BIT - 1)) / CHAR_BIT;
02249 
02250     return bytes;
02251 }

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().

00556 {
00557     NRCHECK(z != NULL);
00558 
00559     z->digits[0] = 0;
00560     MP_USED(z) = 1;
00561     MP_SIGN(z) = MP_ZPOS;
00562 }

void mp_set_default_precision ( mp_size s )

Definition at line 329 of file imath.c.

References default_precision, NRCHECK, and ROUND_PREC.

00330 {
00331     NRCHECK(s > 0);
00332 
00333     default_precision = (mp_size) ROUND_PREC(s);
00334 }

void mp_set_multiply_threshold ( mp_size s )

Definition at line 351 of file imath.c.

References multiply_threshold.

00352 {
00353     multiply_threshold = s;
00354 }

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().

03574 {
03575     int         i;
03576     unsigned short s = 1;
03577 
03578     for (i = len - 1; i >= 0; --i)
03579     {
03580         unsigned char c = ~buf[i];
03581 
03582         s = c + s;
03583         c = s & UCHAR_MAX;
03584         s >>= CHAR_BIT;
03585 
03586         buf[i] = c;
03587     }
03588 
03589     /* last carry out is ignored */
03590 }

static int s_2expt	(	mp_int	z,
		int	k
	)			`[static]`

Definition at line 3172 of file imath.c.

References MP_DIGIT_BIT, MP_DIGITS, MP_USED, s_pad(), and ZERO.

Referenced by s_brmu().

03173 {
03174     mp_size     ndig,
03175                 rest;
03176     mp_digit   *dz;
03177 
03178     ndig = (k + MP_DIGIT_BIT) / MP_DIGIT_BIT;
03179     rest = k % MP_DIGIT_BIT;
03180 
03181     if (!s_pad(z, ndig))
03182         return 0;
03183 
03184     dz = MP_DIGITS(z);
03185     ZERO(dz, ndig);
03186     *(dz + ndig - 1) = (1 << rest);
03187     MP_USED(z) = ndig;
03188 
03189     return 1;
03190 }

static mp_digit * s_alloc ( mp_size num ) [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().

02284 {
02285     mp_digit   *out = px_alloc(num * sizeof(mp_digit));
02286 
02287     assert(out != NULL);        /* for debugging */
02288 
02289     return out;
02290 }

static mp_result s_brmu	(	mp_int	z,
		mp_int	m
	)			`[static]`

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().

03224 {
03225     mp_size     um = MP_USED(m) * 2;
03226 
03227     if (!s_pad(z, um))
03228         return MP_MEMORY;
03229 
03230     s_2expt(z, MP_DIGIT_BIT * um);
03231     return mp_int_div(z, m, z, NULL);
03232 }

static int s_cdig	(	mp_digit *	da,
		mp_digit *	db,
		mp_size	len
	)			`[static]`

Definition at line 2378 of file imath.c.

Referenced by s_ucmp(), and s_vcmp().

02379 {
02380     mp_digit   *dat = da + len - 1,
02381                *dbt = db + len - 1;
02382 
02383     for ( /* */ ; len != 0; --len, --dat, --dbt)
02384     {
02385         if (*dat > *dbt)
02386             return 1;
02387         else if (*dat < *dbt)
02388             return -1;
02389     }
02390 
02391     return 0;
02392 }

static int s_ch2val	(	char	c,
		int	r
	)			`[static]`

Definition at line 3532 of file imath.c.

Referenced by mp_int_read_cstring().

03533 {
03534     int         out;
03535 
03536     if (isdigit((unsigned char) c))
03537         out = c - '0';
03538     else if (r > 10 && isalpha((unsigned char) c))
03539         out = toupper((unsigned char) c) - 'A' + 10;
03540     else
03541         return -1;
03542 
03543     return (out >= r) ? -1 : out;
03544 }

static void s_dadd	(	mp_int	a,
		mp_digit	b
	)			`[static]`

Definition at line 2805 of file imath.c.

References LOWER_HALF, MP_DIGITS, MP_USED, and UPPER_HALF.

Referenced by mp_int_read_cstring().

02806 {
02807     mp_word     w = 0;
02808     mp_digit   *da = MP_DIGITS(a);
02809     mp_size     ua = MP_USED(a);
02810 
02811     w = (mp_word) *da + b;
02812     *da++ = LOWER_HALF(w);
02813     w = UPPER_HALF(w);
02814 
02815     for (ua -= 1; ua > 0; --ua, ++da)
02816     {
02817         w = (mp_word) *da + w;
02818 
02819         *da = LOWER_HALF(w);
02820         w = UPPER_HALF(w);
02821     }
02822 
02823     if (w)
02824     {
02825         *da = (mp_digit) w;
02826         MP_USED(a) += 1;
02827     }
02828 }

static void s_dbmul	(	mp_digit *	da,
		mp_digit	b,
		mp_digit *	dc,
		mp_size	size_a
	)			`[static]`

Definition at line 2861 of file imath.c.

References LOWER_HALF, and UPPER_HALF.

Referenced by s_udiv().

02862 {
02863     mp_word     w = 0;
02864 
02865     while (size_a > 0)
02866     {
02867         w = (mp_word) *da++ * (mp_word) b + w;
02868 
02869         *dc++ = LOWER_HALF(w);
02870         w = UPPER_HALF(w);
02871         --size_a;
02872     }
02873 
02874     if (w)
02875         *dc = LOWER_HALF(w);
02876 }

static mp_digit s_ddiv	(	mp_int	a,
		mp_digit	b
	)			`[static]`

Definition at line 2883 of file imath.c.

References CLAMP, MP_DIGIT_BIT, MP_DIGITS, and MP_USED.

Referenced by mp_int_to_string().

02884 {
02885     mp_word     w = 0,
02886                 qdigit;
02887     mp_size     ua = MP_USED(a);
02888     mp_digit   *da = MP_DIGITS(a) + ua - 1;
02889 
02890     for ( /* */ ; ua > 0; --ua, --da)
02891     {
02892         w = (w << MP_DIGIT_BIT) | *da;
02893 
02894         if (w >= b)
02895         {
02896             qdigit = w / b;
02897             w = w % b;
02898         }
02899         else
02900         {
02901             qdigit = 0;
02902         }
02903 
02904         *da = (mp_digit) qdigit;
02905     }
02906 
02907     CLAMP(a);
02908     return (mp_digit) w;
02909 }

static void s_dmul	(	mp_int	a,
		mp_digit	b
	)			`[static]`

Definition at line 2835 of file imath.c.

References LOWER_HALF, MP_DIGITS, MP_USED, and UPPER_HALF.

Referenced by mp_int_read_cstring().

02836 {
02837     mp_word     w = 0;
02838     mp_digit   *da = MP_DIGITS(a);
02839     mp_size     ua = MP_USED(a);
02840 
02841     while (ua > 0)
02842     {
02843         w = (mp_word) *da * b + w;
02844         *da++ = LOWER_HALF(w);
02845         w = UPPER_HALF(w);
02846         --ua;
02847     }
02848 
02849     if (w)
02850     {
02851         *da = (mp_digit) w;
02852         MP_USED(a) += 1;
02853     }
02854 }

static int s_dp2k ( mp_int z ) [static]

Definition at line 3110 of file imath.c.

References MP_DIGIT_BIT, MP_DIGITS, and MP_USED.

Referenced by mp_int_egcd(), and mp_int_gcd().

03111 {
03112     int         k = 0;
03113     mp_digit   *dp = MP_DIGITS(z),
03114                 d;
03115 
03116     if (MP_USED(z) == 1 && *dp == 0)
03117         return 1;
03118 
03119     while (*dp == 0)
03120     {
03121         k += MP_DIGIT_BIT;
03122         ++dp;
03123     }
03124 
03125     d = *dp;
03126     while ((d & 1) == 0)
03127     {
03128         d >>= 1;
03129         ++k;
03130     }
03131 
03132     return k;
03133 }

static mp_result s_embar	(	mp_int	a,
		mp_int	b,
		mp_int	m,
		mp_int	mu,
		mp_int	c
	)			`[static]`

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().

03296 {
03297     mp_digit   *db,
03298                *dbt,
03299                 umu,
03300                 d;
03301     mpz_t       temp[3];
03302     mp_result   res;
03303     int         last = 0;
03304 
03305     umu = MP_USED(mu);
03306     db = MP_DIGITS(b);
03307     dbt = db + MP_USED(b) - 1;
03308 
03309     while (last < 3)
03310         SETUP(mp_int_init_size(TEMP(last), 2 * umu), last);
03311 
03312     (void) mp_int_set_value(c, 1);
03313 
03314     /* Take care of low-order digits */
03315     while (db < dbt)
03316     {
03317         int         i;
03318 
03319         for (d = *db, i = MP_DIGIT_BIT; i > 0; --i, d >>= 1)
03320         {
03321             if (d & 1)
03322             {
03323                 /* The use of a second temporary avoids allocation */
03324                 UMUL(c, a, TEMP(0));
03325                 if (!s_reduce(TEMP(0), m, mu, TEMP(1), TEMP(2)))
03326                 {
03327                     res = MP_MEMORY;
03328                     goto CLEANUP;
03329                 }
03330                 mp_int_copy(TEMP(0), c);
03331             }
03332 
03333 
03334             USQR(a, TEMP(0));
03335             assert(MP_SIGN(TEMP(0)) == MP_ZPOS);
03336             if (!s_reduce(TEMP(0), m, mu, TEMP(1), TEMP(2)))
03337             {
03338                 res = MP_MEMORY;
03339                 goto CLEANUP;
03340             }
03341             assert(MP_SIGN(TEMP(0)) == MP_ZPOS);
03342             mp_int_copy(TEMP(0), a);
03343 
03344 
03345         }
03346 
03347         ++db;
03348     }
03349 
03350     /* Take care of highest-order digit */
03351     d = *dbt;
03352     for (;;)
03353     {
03354         if (d & 1)
03355         {
03356             UMUL(c, a, TEMP(0));
03357             if (!s_reduce(TEMP(0), m, mu, TEMP(1), TEMP(2)))
03358             {
03359                 res = MP_MEMORY;
03360                 goto CLEANUP;
03361             }
03362             mp_int_copy(TEMP(0), c);
03363         }
03364 
03365         d >>= 1;
03366         if (!d)
03367             break;
03368 
03369         USQR(a, TEMP(0));
03370         if (!s_reduce(TEMP(0), m, mu, TEMP(1), TEMP(2)))
03371         {
03372             res = MP_MEMORY;
03373             goto CLEANUP;
03374         }
03375         (void) mp_int_copy(TEMP(0), a);
03376     }
03377 
03378 CLEANUP:
03379     while (--last >= 0)
03380         mp_int_clear(TEMP(last));
03381 
03382     return res;
03383 }

static void s_fake	(	mp_int	z,
		int	value,
		mp_digit	vbuf[]
	)			`[static]`

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().

02364 {
02365     mp_size     uv = (mp_size) s_vpack(value, vbuf);
02366 
02367     z->used = uv;
02368     z->alloc = MP_VALUE_DIGITS(value);
02369     z->sign = (value < 0) ? MP_NEG : MP_ZPOS;
02370     z->digits = vbuf;
02371 }

static mp_size s_inlen	(	int	len,
		mp_size	r
	)			`[static]`

Definition at line 3519 of file imath.c.

References MP_DIGIT_BIT, and s_log2.

Referenced by mp_int_read_cstring().

03520 {
03521     double      raw = (double) len / s_log2[r];
03522     mp_size     bits = (mp_size) (raw + 0.5);
03523 
03524     return (mp_size) ((bits + (MP_DIGIT_BIT - 1)) / MP_DIGIT_BIT);
03525 }

static int s_isp2 ( mp_int z ) [static]

Definition at line 3140 of file imath.c.

References MP_DIGIT_BIT, MP_DIGITS, and MP_USED.

Referenced by mp_int_div(), and mp_int_is_pow2().

03141 {
03142     mp_size     uz = MP_USED(z),
03143                 k = 0;
03144     mp_digit   *dz = MP_DIGITS(z),
03145                 d;
03146 
03147     while (uz > 1)
03148     {
03149         if (*dz++ != 0)
03150             return -1;
03151         k += MP_DIGIT_BIT;
03152         --uz;
03153     }
03154 
03155     d = *dz;
03156     while (d > 1)
03157     {
03158         if (d & 1)
03159             return -1;
03160         ++k;
03161         d >>= 1;
03162     }
03163 
03164     return (int) k;
03165 }

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, NULL, s_alloc(), s_free, s_uadd(), s_umul(), s_usub(), SWAP, and ZERO.

Referenced by mp_int_mul(), and s_ksqr().

02542 {
02543     mp_size     bot_size;
02544 
02545     /* Make sure b is the smaller of the two input values */
02546     if (size_b > size_a)
02547     {
02548         SWAP(mp_digit *, da, db);
02549         SWAP(mp_size, size_a, size_b);
02550     }
02551 
02552     /*
02553      * Insure that the bottom is the larger half in an odd-length split; the
02554      * code below relies on this being true.
02555      */
02556     bot_size = (size_a + 1) / 2;
02557 
02558     /*
02559      * If the values are big enough to bother with recursion, use the
02560      * Karatsuba algorithm to compute the product; otherwise use the normal
02561      * multiplication algorithm
02562      */
02563     if (multiply_threshold &&
02564         size_a >= multiply_threshold &&
02565         size_b > bot_size)
02566     {
02567 
02568         mp_digit   *t1,
02569                    *t2,
02570                    *t3,
02571                     carry;
02572 
02573         mp_digit   *a_top = da + bot_size;
02574         mp_digit   *b_top = db + bot_size;
02575 
02576         mp_size     at_size = size_a - bot_size;
02577         mp_size     bt_size = size_b - bot_size;
02578         mp_size     buf_size = 2 * bot_size;
02579 
02580         /*
02581          * Do a single allocation for all three temporary buffers needed; each
02582          * buffer must be big enough to hold the product of two bottom halves,
02583          * and one buffer needs space for the completed product; twice the
02584          * space is plenty.
02585          */
02586         if ((t1 = s_alloc(4 * buf_size)) == NULL)
02587             return 0;
02588         t2 = t1 + buf_size;
02589         t3 = t2 + buf_size;
02590         ZERO(t1, 4 * buf_size);
02591 
02592         /*
02593          * t1 and t2 are initially used as temporaries to compute the inner
02594          * product (a1 + a0)(b1 + b0) = a1b1 + a1b0 + a0b1 + a0b0
02595          */
02596         carry = s_uadd(da, a_top, t1, bot_size, at_size);       /* t1 = a1 + a0 */
02597         t1[bot_size] = carry;
02598 
02599         carry = s_uadd(db, b_top, t2, bot_size, bt_size);       /* t2 = b1 + b0 */
02600         t2[bot_size] = carry;
02601 
02602         (void) s_kmul(t1, t2, t3, bot_size + 1, bot_size + 1);  /* t3 = t1 * t2 */
02603 
02604         /*
02605          * Now we'll get t1 = a0b0 and t2 = a1b1, and subtract them out so
02606          * that we're left with only the pieces we want:  t3 = a1b0 + a0b1
02607          */
02608         ZERO(t1, bot_size + 1);
02609         ZERO(t2, bot_size + 1);
02610         (void) s_kmul(da, db, t1, bot_size, bot_size);  /* t1 = a0 * b0 */
02611         (void) s_kmul(a_top, b_top, t2, at_size, bt_size);      /* t2 = a1 * b1 */
02612 
02613         /* Subtract out t1 and t2 to get the inner product */
02614         s_usub(t3, t1, t3, buf_size + 2, buf_size);
02615         s_usub(t3, t2, t3, buf_size + 2, buf_size);
02616 
02617         /* Assemble the output value */
02618         COPY(t1, dc, buf_size);
02619         (void) s_uadd(t3, dc + bot_size, dc + bot_size,
02620                       buf_size + 1, buf_size + 1);
02621 
02622         (void) s_uadd(t2, dc + 2 * bot_size, dc + 2 * bot_size,
02623                       buf_size, buf_size);
02624 
02625         s_free(t1);             /* note t2 and t3 are just internal pointers
02626                                  * to t1 */
02627     }
02628     else
02629     {
02630         s_umul(da, db, dc, size_a, size_b);
02631     }
02632 
02633     return 1;
02634 }

static int s_ksqr	(	mp_digit *	da,
		mp_digit *	dc,
		mp_size	size_a
	)			`[static]`

Definition at line 2674 of file imath.c.

References COPY, i, LOWER_HALF, multiply_threshold, NULL, px_free, s_alloc(), s_kmul(), s_uadd(), s_usqr(), UPPER_HALF, and ZERO.

Referenced by mp_int_sqr().

02675 {
02676     if (multiply_threshold && size_a > multiply_threshold)
02677     {
02678         mp_size     bot_size = (size_a + 1) / 2;
02679         mp_digit   *a_top = da + bot_size;
02680         mp_digit   *t1,
02681                    *t2,
02682                    *t3;
02683         mp_size     at_size = size_a - bot_size;
02684         mp_size     buf_size = 2 * bot_size;
02685 
02686         if ((t1 = s_alloc(4 * buf_size)) == NULL)
02687             return 0;
02688         t2 = t1 + buf_size;
02689         t3 = t2 + buf_size;
02690         ZERO(t1, 4 * buf_size);
02691 
02692         (void) s_ksqr(da, t1, bot_size);        /* t1 = a0 ^ 2 */
02693         (void) s_ksqr(a_top, t2, at_size);      /* t2 = a1 ^ 2 */
02694 
02695         (void) s_kmul(da, a_top, t3, bot_size, at_size);        /* t3 = a0 * a1 */
02696 
02697         /* Quick multiply t3 by 2, shifting left (can't overflow) */
02698         {
02699             int         i,
02700                         top = bot_size + at_size;
02701             mp_word     w,
02702                         save = 0;
02703 
02704             for (i = 0; i < top; ++i)
02705             {
02706                 w = t3[i];
02707                 w = (w << 1) | save;
02708                 t3[i] = LOWER_HALF(w);
02709                 save = UPPER_HALF(w);
02710             }
02711             t3[i] = LOWER_HALF(save);
02712         }
02713 
02714         /* Assemble the output value */
02715         COPY(t1, dc, 2 * bot_size);
02716         (void) s_uadd(t3, dc + bot_size, dc + bot_size,
02717                       buf_size + 1, buf_size + 1);
02718 
02719         (void) s_uadd(t2, dc + 2 * bot_size, dc + 2 * bot_size,
02720                       buf_size, buf_size);
02721 
02722         px_free(t1);            /* note that t2 and t2 are internal pointers
02723                                  * only */
02724 
02725     }
02726     else
02727     {
02728         s_usqr(da, dc, size_a);
02729     }
02730 
02731     return 1;
02732 }

static int s_norm	(	mp_int	a,
		mp_int	b
	)			`[static]`

Definition at line 3197 of file imath.c.

References mpz::digits, MP_DIGIT_BIT, MP_USED, and s_qmul().

Referenced by s_udiv().

03198 {
03199     mp_digit    d = b->digits[MP_USED(b) - 1];
03200     int         k = 0;
03201 
03202     while (d < (mp_digit) ((mp_digit) 1 << (MP_DIGIT_BIT - 1)))
03203     {                           /* d < (MP_RADIX / 2) */
03204         d <<= 1;
03205         ++k;
03206     }
03207 
03208     /* These multiplications can't fail */
03209     if (k != 0)
03210     {
03211         (void) s_qmul(a, (mp_size) k);
03212         (void) s_qmul(b, (mp_size) k);
03213     }
03214 
03215     return k;
03216 }

static int s_outlen	(	mp_int	z,
		mp_size	r
	)			`[static]`

Definition at line 3503 of file imath.c.

References mp_int_count_bits(), and s_log2.

Referenced by mp_int_string_len().

03504 {
03505     mp_result   bits;
03506     double      raw;
03507 
03508     bits = mp_int_count_bits(z);
03509     raw = (double) bits *s_log2[r];
03510 
03511     return (int) (raw + 0.999999);
03512 }

static int s_pad	(	mp_int	z,
		mp_size	min
	)			`[static]`

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(), px_find_combo(), s_2expt(), s_brmu(), s_qmul(), and s_qsub().

02324 {
02325     if (MP_ALLOC(z) < min)
02326     {
02327         mp_size     nsize = ROUND_PREC(min);
02328         mp_digit   *tmp = s_realloc(MP_DIGITS(z), nsize);
02329 
02330         if (tmp == NULL)
02331             return 0;
02332 
02333         MP_DIGITS(z) = tmp;
02334         MP_ALLOC(z) = nsize;
02335     }
02336 
02337     return 1;
02338 }

static void s_qdiv	(	mp_int	z,
		mp_size	p2
	)			`[static]`

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().

02917 {
02918     mp_size     ndig = p2 / MP_DIGIT_BIT,
02919                 nbits = p2 % MP_DIGIT_BIT;
02920     mp_size     uz = MP_USED(z);
02921 
02922     if (ndig)
02923     {
02924         mp_size     mark;
02925         mp_digit   *to,
02926                    *from;
02927 
02928         if (ndig >= uz)
02929         {
02930             mp_int_zero(z);
02931             return;
02932         }
02933 
02934         to = MP_DIGITS(z);
02935         from = to + ndig;
02936 
02937         for (mark = ndig; mark < uz; ++mark)
02938             *to++ = *from++;
02939 
02940         MP_USED(z) = uz - ndig;
02941     }
02942 
02943     if (nbits)
02944     {
02945         mp_digit    d = 0,
02946                    *dz,
02947                     save;
02948         mp_size     up = MP_DIGIT_BIT - nbits;
02949 
02950         uz = MP_USED(z);
02951         dz = MP_DIGITS(z) + uz - 1;
02952 
02953         for ( /* */ ; uz > 0; --uz, --dz)
02954         {
02955             save = *dz;
02956 
02957             *dz = (*dz >> nbits) | (d << up);
02958             d = save;
02959         }
02960 
02961         CLAMP(z);
02962     }
02963 
02964     if (MP_USED(z) == 1 && z->digits[0] == 0)
02965         MP_SIGN(z) = MP_ZPOS;
02966 }

static void s_qmod	(	mp_int	z,
		mp_size	p2
	)			`[static]`

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().

02974 {
02975     mp_size     start = p2 / MP_DIGIT_BIT + 1,
02976                 rest = p2 % MP_DIGIT_BIT;
02977     mp_size     uz = MP_USED(z);
02978     mp_digit    mask = (1 << rest) - 1;
02979 
02980     if (start <= uz)
02981     {
02982         MP_USED(z) = start;
02983         z->digits[start - 1] &= mask;
02984         CLAMP(z);
02985     }
02986 }

static int s_qmul	(	mp_int	z,
		mp_size	p2
	)			`[static]`

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().

02994 {
02995     mp_size     uz,
02996                 need,
02997                 rest,
02998                 extra,
02999                 i;
03000     mp_digit   *from,
03001                *to,
03002                 d;
03003 
03004     if (p2 == 0)
03005         return 1;
03006 
03007     uz = MP_USED(z);
03008     need = p2 / MP_DIGIT_BIT;
03009     rest = p2 % MP_DIGIT_BIT;
03010 
03011     /*
03012      * Figure out if we need an extra digit at the top end; this occurs if the
03013      * topmost `rest' bits of the high-order digit of z are not zero, meaning
03014      * they will be shifted off the end if not preserved
03015      */
03016     extra = 0;
03017     if (rest != 0)
03018     {
03019         mp_digit   *dz = MP_DIGITS(z) + uz - 1;
03020 
03021         if ((*dz >> (MP_DIGIT_BIT - rest)) != 0)
03022             extra = 1;
03023     }
03024 
03025     if (!s_pad(z, uz + need + extra))
03026         return 0;
03027 
03028     /*
03029      * If we need to shift by whole digits, do that in one pass, then to back
03030      * and shift by partial digits.
03031      */
03032     if (need > 0)
03033     {
03034         from = MP_DIGITS(z) + uz - 1;
03035         to = from + need;
03036 
03037         for (i = 0; i < uz; ++i)
03038             *to-- = *from--;
03039 
03040         ZERO(MP_DIGITS(z), need);
03041         uz += need;
03042     }
03043 
03044     if (rest)
03045     {
03046         d = 0;
03047         for (i = need, from = MP_DIGITS(z) + need; i < uz; ++i, ++from)
03048         {
03049             mp_digit    save = *from;
03050 
03051             *from = (*from << rest) | (d >> (MP_DIGIT_BIT - rest));
03052             d = save;
03053         }
03054 
03055         d >>= (MP_DIGIT_BIT - rest);
03056         if (d != 0)
03057         {
03058             *from = d;
03059             uz += extra;
03060         }
03061     }
03062 
03063     MP_USED(z) = uz;
03064     CLAMP(z);
03065 
03066     return 1;
03067 }

static int s_qsub	(	mp_int	z,
		mp_size	p2
	)			`[static]`

Definition at line 3075 of file imath.c.

References assert, CLAMP, LOWER_HALF, MP_DIGIT_BIT, MP_DIGIT_MAX, MP_DIGITS, MP_SIGN, MP_ZPOS, s_pad(), and UPPER_HALF.

Referenced by s_reduce().

03076 {
03077     mp_digit    hi = (1 << (p2 % MP_DIGIT_BIT)),
03078                *zp;
03079     mp_size     tdig = (p2 / MP_DIGIT_BIT),
03080                 pos;
03081     mp_word     w = 0;
03082 
03083     if (!s_pad(z, tdig + 1))
03084         return 0;
03085 
03086     for (pos = 0, zp = MP_DIGITS(z); pos < tdig; ++pos, ++zp)
03087     {
03088         w = ((mp_word) MP_DIGIT_MAX + 1) - w - (mp_word) *zp;
03089 
03090         *zp = LOWER_HALF(w);
03091         w = UPPER_HALF(w) ? 0 : 1;
03092     }
03093 
03094     w = ((mp_word) MP_DIGIT_MAX + 1 + hi) - w - (mp_word) *zp;
03095     *zp = LOWER_HALF(w);
03096 
03097     assert(UPPER_HALF(w) != 0); /* no borrow out should be possible */
03098 
03099     MP_SIGN(z) = MP_ZPOS;
03100     CLAMP(z);
03101 
03102     return 1;
03103 }

static mp_digit* s_realloc	(	mp_digit *	old,
		mp_size	num
	)			`[static]`

Definition at line 2297 of file imath.c.

References assert, NULL, and px_realloc.

Referenced by s_pad().

02298 {
02299     mp_digit   *new = px_realloc(old, num * sizeof(mp_digit));
02300 
02301     assert(new != NULL);        /* for debugging */
02302 
02303     return new;
02304 }

static int s_reduce	(	mp_int	x,
		mp_int	m,
		mp_int	mu,
		mp_int	q1,
		mp_int	q2
	)			`[static]`

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().

03240 {
03241     mp_size     um = MP_USED(m),
03242                 umb_p1,
03243                 umb_m1;
03244 
03245     umb_p1 = (um + 1) * MP_DIGIT_BIT;
03246     umb_m1 = (um - 1) * MP_DIGIT_BIT;
03247 
03248     if (mp_int_copy(x, q1) != MP_OK)
03249         return 0;
03250 
03251     /* Compute q2 = floor((floor(x / b^(k-1)) * mu) / b^(k+1)) */
03252     s_qdiv(q1, umb_m1);
03253     UMUL(q1, mu, q2);
03254     s_qdiv(q2, umb_p1);
03255 
03256     /* Set x = x mod b^(k+1) */
03257     s_qmod(x, umb_p1);
03258 
03259     /*
03260      * Now, q is a guess for the quotient a / m. Compute x - q * m mod
03261      * b^(k+1), replacing x.  This may be off by a factor of 2m, but no more
03262      * than that.
03263      */
03264     UMUL(q2, m, q1);
03265     s_qmod(q1, umb_p1);
03266     (void) mp_int_sub(x, q1, x);    /* can't fail */
03267 
03268     /*
03269      * The result may be < 0; if it is, add b^(k+1) to pin it in the proper
03270      * range.
03271      */
03272     if ((CMPZ(x) < 0) && !s_qsub(x, umb_p1))
03273         return 0;
03274 
03275     /*
03276      * If x > m, we need to back it off until it is in range. This will be
03277      * required at most twice.
03278      */
03279     if (mp_int_compare(x, m) >= 0)
03280         (void) mp_int_sub(x, m, x);
03281     if (mp_int_compare(x, m) >= 0)
03282         (void) mp_int_sub(x, m, x);
03283 
03284     /* At this point, x has been properly reduced. */
03285     return 1;
03286 }

static mp_result s_tobin	(	mp_int	z,
		unsigned char *	buf,
		int *	limpos,
		int	pad
	)			`[static]`

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().

03598 {
03599     mp_size     uz;
03600     mp_digit   *dz;
03601     int         pos = 0,
03602                 limit = *limpos;
03603 
03604     uz = MP_USED(z);
03605     dz = MP_DIGITS(z);
03606     while (uz > 0 && pos < limit)
03607     {
03608         mp_digit    d = *dz++;
03609         int         i;
03610 
03611         for (i = sizeof(mp_digit); i > 0 && pos < limit; --i)
03612         {
03613             buf[pos++] = (unsigned char) d;
03614             d >>= CHAR_BIT;
03615 
03616             /* Don't write leading zeroes */
03617             if (d == 0 && uz == 1)
03618                 i = 0;          /* exit loop without signaling truncation */
03619         }
03620 
03621         /* Detect truncation (loop exited with pos >= limit) */
03622         if (i > 0)
03623             break;
03624 
03625         --uz;
03626     }
03627 
03628     if (pad != 0 && (buf[pos - 1] >> (CHAR_BIT - 1)))
03629     {
03630         if (pos < limit)
03631             buf[pos++] = 0;
03632         else
03633             uz = 1;
03634     }
03635 
03636     /* Digits are in reverse order, fix that */
03637     REV(unsigned char, buf, pos);
03638 
03639     /* Return the number of bytes actually written */
03640     *limpos = pos;
03641 
03642     return (uz == 0) ? MP_OK : MP_TRUNC;
03643 }

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().

02465 {
02466     mp_size     pos;
02467     mp_word     w = 0;
02468 
02469     /* Insure that da is the longer of the two to simplify later code */
02470     if (size_b > size_a)
02471     {
02472         SWAP(mp_digit *, da, db);
02473         SWAP(mp_size, size_a, size_b);
02474     }
02475 
02476     /* Add corresponding digits until the shorter number runs out */
02477     for (pos = 0; pos < size_b; ++pos, ++da, ++db, ++dc)
02478     {
02479         w = w + (mp_word) *da + (mp_word) *db;
02480         *dc = LOWER_HALF(w);
02481         w = UPPER_HALF(w);
02482     }
02483 
02484     /* Propagate carries as far as necessary */
02485     for ( /* */ ; pos < size_a; ++pos, ++da, ++dc)
02486     {
02487         w = w + *da;
02488 
02489         *dc = LOWER_HALF(w);
02490         w = UPPER_HALF(w);
02491     }
02492 
02493     /* Return carry out */
02494     return (mp_digit) w;
02495 }

static int s_ucmp	(	mp_int	a,
		mp_int	b
	)			`[static]`

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().

02425 {
02426     mp_size     ua = MP_USED(a),
02427                 ub = MP_USED(b);
02428 
02429     if (ua > ub)
02430         return 1;
02431     else if (ub > ua)
02432         return -1;
02433     else
02434         return s_cdig(MP_DIGITS(a), MP_DIGITS(b), ua);
02435 }

static mp_result s_udiv	(	mp_int	a,
		mp_int	b
	)			`[static]`

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().

03394 {
03395     mpz_t       q,
03396                 r,
03397                 t;
03398     mp_size     ua,
03399                 ub,
03400                 qpos = 0;
03401     mp_digit   *da,
03402                 btop;
03403     mp_result   res = MP_OK;
03404     int         k,
03405                 skip = 0;
03406 
03407     /* Force signs to positive */
03408     MP_SIGN(a) = MP_ZPOS;
03409     MP_SIGN(b) = MP_ZPOS;
03410 
03411     /* Normalize, per Knuth */
03412     k = s_norm(a, b);
03413 
03414     ua = MP_USED(a);
03415     ub = MP_USED(b);
03416     btop = b->digits[ub - 1];
03417     if ((res = mp_int_init_size(&q, ua)) != MP_OK)
03418         return res;
03419     if ((res = mp_int_init_size(&t, ua + 1)) != MP_OK)
03420         goto CLEANUP;
03421 
03422     da = MP_DIGITS(a);
03423     r.digits = da + ua - 1;     /* The contents of r are shared with a */
03424     r.used = 1;
03425     r.sign = MP_ZPOS;
03426     r.alloc = MP_ALLOC(a);
03427     ZERO(t.digits, t.alloc);
03428 
03429     /* Solve for quotient digits, store in q.digits in reverse order */
03430     while (r.digits >= da)
03431     {
03432         assert(qpos <= q.alloc);
03433 
03434         if (s_ucmp(b, &r) > 0)
03435         {
03436             r.digits -= 1;
03437             r.used += 1;
03438 
03439             if (++skip > 1)
03440                 q.digits[qpos++] = 0;
03441 
03442             CLAMP(&r);
03443         }
03444         else
03445         {
03446             mp_word     pfx = r.digits[r.used - 1];
03447             mp_word     qdigit;
03448 
03449             if (r.used > 1 && (pfx < btop || r.digits[r.used - 2] == 0))
03450             {
03451                 pfx <<= MP_DIGIT_BIT / 2;
03452                 pfx <<= MP_DIGIT_BIT / 2;
03453                 pfx |= r.digits[r.used - 2];
03454             }
03455 
03456             qdigit = pfx / btop;
03457             if (qdigit > MP_DIGIT_MAX)
03458                 qdigit = 1;
03459 
03460             s_dbmul(MP_DIGITS(b), (mp_digit) qdigit, t.digits, ub);
03461             t.used = ub + 1;
03462             CLAMP(&t);
03463             while (s_ucmp(&t, &r) > 0)
03464             {
03465                 --qdigit;
03466                 (void) mp_int_sub(&t, b, &t);   /* cannot fail */
03467             }
03468 
03469             s_usub(r.digits, t.digits, r.digits, r.used, t.used);
03470             CLAMP(&r);
03471 
03472             q.digits[qpos++] = (mp_digit) qdigit;
03473             ZERO(t.digits, t.used);
03474             skip = 0;
03475         }
03476     }
03477 
03478     /* Put quotient digits in the correct order, and discard extra zeroes */
03479     q.used = qpos;
03480     REV(mp_digit, q.digits, qpos);
03481     CLAMP(&q);
03482 
03483     /* Denormalize the remainder */
03484     CLAMP(a);
03485     if (k != 0)
03486         s_qdiv(a, k);
03487 
03488     mp_int_copy(a, b);          /* ok:  0 <= r < b */
03489     mp_int_copy(&q, a);         /* ok:  q <= a     */
03490 
03491     mp_int_clear(&t);
03492 CLEANUP:
03493     mp_int_clear(&q);
03494     return res;
03495 }


Defines
#define	assert(TEST) Assert(TEST)
#define	TRACEABLE_CLAMP 0
#define	TRACEABLE_FREE 0
#define	MP_CAP_DIGITS 1
#define	CHECK(TEST) assert(TEST)
#define	NRCHECK(TEST) assert(TEST)
#define	MP_VALUE_DIGITS(V) ((sizeof(V)+(sizeof(mp_digit)-1))/sizeof(mp_digit))
#define	ROUND_PREC(P) ((mp_size)(2*(((P)+1)/2)))
#define	ZERO(P, S) do{mp_size i__=(S)sizeof(mp_digit);mp_digit p__=(P);memset(p__,0,i__);}while(0)
#define	COPY(P, Q, S)
#define	REV(T, A, N) do{T u_=(A),v_=u_+(N)-1;while(u_<v_){T xch=u_;u_++=v_;v_--=xch;}}while(0)
#define	CLAMP(Z)
#define	MIN(A, B) ((B)<(A)?(B):(A))
#define	MAX(A, B) ((B)>(A)?(B):(A))
#define	SWAP(T, A, B) do{T t_=(A);A=(B);B=t_;}while(0)
#define	TEMP(K) (temp + (K))
#define	SETUP(E, C) do{if((res = (E)) != MP_OK) goto CLEANUP; ++(C);}while(0)
#define	CMPZ(Z) (((Z)->used==1&&(Z)->digits[0]==0)?0:((Z)->sign==MP_NEG)?-1:1)
#define	UMUL(X, Y, Z)
#define	USQR(X, Z)
#define	UPPER_HALF(W) ((mp_word)((W) >> MP_DIGIT_BIT))
#define	LOWER_HALF(W) ((mp_digit)(W))
#define	HIGH_BIT_SET(W) ((W) >> (MP_WORD_BIT - 1))
#define	ADD_WILL_OVERFLOW(W, V) ((MP_WORD_MAX - (V)) < (W))
#define	s_free(P) px_free(P)
Functions
static mp_digit *	s_alloc (mp_size num)
static int	s_pad (mp_int z, mp_size min)
static void	s_fake (mp_int z, int value, mp_digit vbuf[])
static int	s_cdig (mp_digit da, mp_digit db, mp_size len)
static int	s_vpack (int v, mp_digit t[])
static int	s_ucmp (mp_int a, mp_int b)
static int	s_vcmp (mp_int a, int v)
static mp_digit	s_uadd (mp_digit da, mp_digit db, mp_digit *dc, mp_size size_a, mp_size size_b)
static void	s_usub (mp_digit da, mp_digit db, mp_digit *dc, mp_size size_a, mp_size size_b)
static int	s_kmul (mp_digit da, mp_digit db, mp_digit *dc, mp_size size_a, mp_size size_b)
static void	s_umul (mp_digit da, mp_digit db, mp_digit *dc, mp_size size_a, mp_size size_b)
static int	s_ksqr (mp_digit da, mp_digit dc, mp_size size_a)
static void	s_usqr (mp_digit da, mp_digit dc, mp_size size_a)
static void	s_dadd (mp_int a, mp_digit b)
static void	s_dmul (mp_int a, mp_digit b)
static void	s_dbmul (mp_digit da, mp_digit b, mp_digit dc, mp_size size_a)
static mp_digit	s_ddiv (mp_int a, mp_digit b)
static void	s_qdiv (mp_int z, mp_size p2)
static void	s_qmod (mp_int z, mp_size p2)
static int	s_qmul (mp_int z, mp_size p2)
static int	s_qsub (mp_int z, mp_size p2)
static int	s_dp2k (mp_int z)
static int	s_isp2 (mp_int z)
static int	s_2expt (mp_int z, int k)
static int	s_norm (mp_int a, mp_int b)
static mp_result	s_brmu (mp_int z, mp_int m)
static int	s_reduce (mp_int x, mp_int m, mp_int mu, mp_int q1, mp_int q2)
static mp_result	s_embar (mp_int a, mp_int b, mp_int m, mp_int mu, mp_int c)
static mp_result	s_udiv (mp_int a, mp_int b)
static int	s_outlen (mp_int z, mp_size r)
static mp_size	s_inlen (int len, mp_size r)
static int	s_ch2val (char c, int r)
static char	s_val2ch (int v, int caps)
static void	s_2comp (unsigned char *buf, int len)
static mp_result	s_tobin (mp_int z, unsigned char buf, int limpos, int pad)
mp_size	mp_get_default_precision (void)
void	mp_set_default_precision (mp_size s)
mp_size	mp_get_multiply_threshold (void)
void	mp_set_multiply_threshold (mp_size s)
mp_result	mp_int_init (mp_int z)
mp_int	mp_int_alloc (void)
mp_result	mp_int_init_size (mp_int z, mp_size prec)
mp_result	mp_int_init_copy (mp_int z, mp_int old)
mp_result	mp_int_init_value (mp_int z, int value)
mp_result	mp_int_set_value (mp_int z, int value)
void	mp_int_clear (mp_int z)
void	mp_int_free (mp_int z)
mp_result	mp_int_copy (mp_int a, mp_int c)
void	mp_int_swap (mp_int a, mp_int c)
void	mp_int_zero (mp_int z)
mp_result	mp_int_abs (mp_int a, mp_int c)
mp_result	mp_int_neg (mp_int a, mp_int c)
mp_result	mp_int_add (mp_int a, mp_int b, mp_int c)
mp_result	mp_int_add_value (mp_int a, int value, mp_int c)
mp_result	mp_int_sub (mp_int a, mp_int b, mp_int c)
mp_result	mp_int_sub_value (mp_int a, int value, mp_int c)
mp_result	mp_int_mul (mp_int a, mp_int b, mp_int c)
mp_result	mp_int_mul_value (mp_int a, int value, mp_int c)
mp_result	mp_int_mul_pow2 (mp_int a, int p2, mp_int c)
mp_result	mp_int_sqr (mp_int a, mp_int c)
mp_result	mp_int_div (mp_int a, mp_int b, mp_int q, mp_int r)
mp_result	mp_int_mod (mp_int a, mp_int m, mp_int c)
mp_result	mp_int_div_value (mp_int a, int value, mp_int q, int *r)
mp_result	mp_int_div_pow2 (mp_int a, int p2, mp_int q, mp_int r)
mp_result	mp_int_expt (mp_int a, int b, mp_int c)
mp_result	mp_int_expt_value (int a, int b, mp_int c)
int	mp_int_compare (mp_int a, mp_int b)
int	mp_int_compare_unsigned (mp_int a, mp_int b)
int	mp_int_compare_zero (mp_int z)
int	mp_int_compare_value (mp_int z, int value)
mp_result	mp_int_exptmod (mp_int a, mp_int b, mp_int m, mp_int c)
mp_result	mp_int_exptmod_evalue (mp_int a, int value, mp_int m, mp_int c)
mp_result	mp_int_exptmod_bvalue (int value, mp_int b, mp_int m, mp_int c)
mp_result	mp_int_exptmod_known (mp_int a, mp_int b, mp_int m, mp_int mu, mp_int c)
mp_result	mp_int_redux_const (mp_int m, mp_int c)
mp_result	mp_int_invmod (mp_int a, mp_int m, mp_int c)
mp_result	mp_int_gcd (mp_int a, mp_int b, mp_int c)
mp_result	mp_int_egcd (mp_int a, mp_int b, mp_int c, mp_int x, mp_int y)
int	mp_int_divisible_value (mp_int a, int v)
int	mp_int_is_pow2 (mp_int z)
mp_result	mp_int_sqrt (mp_int a, mp_int c)
mp_result	mp_int_to_int (mp_int z, int *out)
mp_result	mp_int_to_string (mp_int z, mp_size radix, char *str, int limit)
mp_result	mp_int_string_len (mp_int z, mp_size radix)
mp_result	mp_int_read_string (mp_int z, mp_size radix, const char *str)
mp_result	mp_int_read_cstring (mp_int z, mp_size radix, const char str, char *end)
mp_result	mp_int_count_bits (mp_int z)
mp_result	mp_int_to_binary (mp_int z, unsigned char *buf, int limit)
mp_result	mp_int_read_binary (mp_int z, unsigned char *buf, int len)
mp_result	mp_int_binary_len (mp_int z)
mp_result	mp_int_to_unsigned (mp_int z, unsigned char *buf, int limit)
mp_result	mp_int_read_unsigned (mp_int z, unsigned char *buf, int len)
mp_result	mp_int_unsigned_len (mp_int z)
const char *	mp_error_string (mp_result res)
static mp_digit *	s_realloc (mp_digit *old, mp_size num)
Variables
const mp_result	MP_OK = 0
const mp_result	MP_FALSE = 0
const mp_result	MP_TRUE = -1
const mp_result	MP_MEMORY = -2
const mp_result	MP_RANGE = -3
const mp_result	MP_UNDEF = -4
const mp_result	MP_TRUNC = -5
const mp_result	MP_BADARG = -6
const mp_sign	MP_NEG = 1
const mp_sign	MP_ZPOS = 0
static const char *	s_unknown_err = "unknown result code"
static const char *	s_error_msg []
static const double	s_log2 []
static mp_size	default_precision = 64
static mp_size	multiply_threshold = 32
static mp_word	mp_flags = MP_CAP_DIGITS

Header And Logo

imath.c File Reference

Defines

Functions

Variables

Define Documentation

Function Documentation