Header And Logo

PostgreSQL
| The world's most advanced open source database.

imath.c File Reference

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

Include dependency graph for imath.c:

Go to the source code of this file.

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


Define Documentation

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

Definition at line 162 of file imath.c.

Referenced by s_usqr().

#define assert ( TEST   )     Assert(TEST)

#define CHECK ( TEST   )     assert(TEST)

#define CLAMP (  ) 

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)->used==1&&(Z)->digits[0]==0)?0:((Z)->sign==MP_NEG)?-1:1)

#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) >> (MP_WORD_BIT - 1))

Definition at line 161 of file imath.c.

Referenced by s_usqr().

#define LOWER_HALF (  )     ((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)>(A)?(B):(A))

#define MIN ( A,
 )     ((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 (  )     ((sizeof(V)+(sizeof(mp_digit)-1))/sizeof(mp_digit))

#define NRCHECK ( TEST   )     assert(TEST)

#define REV ( T,
A,
 )     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 (  )     ((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 (  )     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,
 )     do{if((res = (E)) != MP_OK) goto CLEANUP; ++(C);}while(0)

#define SWAP ( T,
A,
 )     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 (  )     (temp + (K))

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

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

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  ) 

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 }