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