imath.c File Reference

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

Include dependency graph for imath.c:

Define Documentation

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

Definition at line 162 of file imath.c.

Referenced by s_usqr().

#define assert ( TEST ) Assert(TEST)

Definition at line 37 of file imath.c.

Referenced by addrange(), allocarc(), altdissect(), bracket(), brenext(), caltdissect(), carcsort(), cbracket(), cbrdissect(), ccondissect(), cdissect(), cfind(), cfindloop(), cleanup(), clearcvec(), cloneouts(), cmtreefree(), colorcomplement(), combine(), compact(), condissect(), copyins(), copyouts(), crevdissect(), delsub(), deltraverse(), destroystate(), dissect(), duptraverse(), eclass(), element(), find(), fixempties(), freearc(), freecnfa(), freecolor(), freelacons(), freestate(), getvacant(), IncreaseBuffer(), inet_cidr_pton_ipv4(), inet_net_pton_ipv4(), initialize(), lacon(), lexescape(), lexnest(), lexstart(), makesearch(), markst(), miss(), moresubs(), moveins(), moveouts(), mp_int_alloc(), newarc(), newcolor(), newdfa(), NewMetaString(), newstate(), newsub(), next(), nfanode(), nfatree(), nonword(), numst(), okcolors(), parse(), parsebranch(), parseqatom(), pg_regcomp(), pg_regexec(), pickss(), pull(), pullback(), push(), pushfwd(), s_alloc(), s_embar(), s_qsub(), s_realloc(), s_udiv(), s_usqr(), s_usub(), s_val2ch(), scanplain(), setcolor(), shortest(), skip(), specialcolors(), subblock(), subcolor(), subrange(), subre(), subset(), uncolorchain(), unempty(), word(), wordchrs(), and zapmem().

#define CHECK ( TEST ) assert(TEST)

#define CLAMP ( Z )

Value:

do{mp_int z_=(Z);mp_size uz_=MP_USED(z_);mp_digit *dz_=MP_DIGITS(z_)+uz_-1;\
while(uz_ > 1 && (*dz_-- == 0)) --uz_;MP_USED(z_)=uz_;}while(0)

Definition at line 131 of file imath.c.

Referenced by mp_int_add(), mp_int_mul(), mp_int_read_cstring(), mp_int_sqr(), mp_int_sub(), s_ddiv(), s_qdiv(), s_qmod(), s_qmul(), s_qsub(), and s_udiv().

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

Definition at line 146 of file imath.c.

Referenced by mp_int_div(), mp_int_egcd(), mp_int_exptmod(), mp_int_exptmod_known(), mp_int_gcd(), mp_int_invmod(), mp_int_mod(), mp_int_neg(), mp_int_read_cstring(), mp_int_to_string(), and s_reduce().

#define COPY	(	P,
		Q,
		S	)

Value:

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

Definition at line 120 of file imath.c.

Referenced by mp_int_copy(), mp_int_init_copy(), s_kmul(), and s_ksqr().

#define HIGH_BIT_SET ( W ) ((W) >> (MP_WORD_BIT - 1))

Definition at line 161 of file imath.c.

Referenced by s_usqr().

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

Definition at line 160 of file imath.c.

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

#define MAX	(	A,
		B		)	((B)>(A)?(B):(A))

Definition at line 139 of file imath.c.

Referenced by mp_int_add(), mp_int_init_copy(), mp_int_init_size(), mp_int_mul(), mp_int_sqr(), and mp_int_sub().

#define MIN	(	A,
		B		)	((B)<(A)?(B):(A))

Definition at line 138 of file imath.c.

Referenced by mp_int_egcd(), and mp_int_gcd().

#define MP_CAP_DIGITS 1

Definition at line 70 of file imath.c.

Referenced by mp_int_to_string().

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

Definition at line 109 of file imath.c.

Referenced by mp_int_add_value(), mp_int_div_value(), mp_int_exptmod_bvalue(), mp_int_exptmod_evalue(), mp_int_mul_value(), mp_int_set_value(), mp_int_sub_value(), s_fake(), and s_vcmp().

#define NRCHECK ( TEST ) assert(TEST)

Definition at line 75 of file imath.c.

Referenced by mp_int_compare_unsigned(), mp_int_compare_zero(), mp_int_free(), mp_int_zero(), and mp_set_default_precision().

#define REV	(	T,
		A,
		N	)	do{T u_=(A),v_=u_+(N)-1;while(u_<v_){T xch=u_;u_++=v_;v_--=xch;}}while(0)

Definition at line 125 of file imath.c.

Referenced by s_tobin(), and s_udiv().

#define ROUND_PREC ( P ) ((mp_size)(2*(((P)+1)/2)))

Definition at line 113 of file imath.c.

Referenced by mp_int_init_size(), mp_int_mul(), mp_int_sqr(), mp_set_default_precision(), and s_pad().

#define s_free ( P ) px_free(P)

Definition at line 182 of file imath.c.

Referenced by mp_int_clear(), mp_int_mul(), mp_int_sqr(), and s_kmul().

#define SETUP	(	E,
		C		)	do{if((res = (E)) != MP_OK) goto CLEANUP; ++(C);}while(0)

Definition at line 143 of file imath.c.

Referenced by mp_int_div(), mp_int_egcd(), mp_int_exptmod(), mp_int_exptmod_known(), mp_int_sqrt(), and s_embar().

#define SWAP	(	T,
		A,
		B	)	do{T t_=(A);A=(B);B=t_;}while(0)

Definition at line 140 of file imath.c.

Referenced by s_kmul(), and s_uadd().

#define TEMP ( K ) (temp + (K))

Definition at line 142 of file imath.c.

Referenced by mp_int_div(), mp_int_egcd(), mp_int_exptmod(), mp_int_exptmod_known(), mp_int_invmod(), mp_int_sqrt(), and s_embar().

#define TRACEABLE_CLAMP 0

Definition at line 38 of file imath.c.

#define TRACEABLE_FREE 0

Definition at line 39 of file imath.c.

#define UMUL	(	X,
		Y,
		Z	)

Value:

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

Definition at line 149 of file imath.c.

Referenced by s_embar(), and s_reduce().

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

Definition at line 159 of file imath.c.

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

#define USQR	(	X,
		Z		)

Value:

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

Definition at line 155 of file imath.c.

Referenced by s_embar().

#define ZERO	(	P,
		S		)	do{mp_size i__=(S)sizeof(mp_digit);mp_digit p__=(P);memset(p__,0,i__);}while(0)

Definition at line 116 of file imath.c.

Referenced by mp_int_mul(), mp_int_sqr(), permute(), s_2expt(), s_kmul(), s_ksqr(), s_qmul(), and s_udiv().

Function Documentation

const char* mp_error_string ( mp_result res )

Definition at line 2258 of file imath.c.

References NULL, s_error_msg, and s_unknown_err.

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

mp_size mp_get_default_precision ( void )

Definition at line 319 of file imath.c.

References default_precision.

00320 {
00321     return default_precision;
00322 }

mp_size mp_get_multiply_threshold ( void )

Definition at line 341 of file imath.c.

References multiply_threshold.

00342 {
00343     return multiply_threshold;
00344 }

mp_result mp_int_abs	(	mp_int	a,
		mp_int	c
	)

Definition at line 569 of file imath.c.

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

Referenced by mp_int_egcd(), and mp_int_gcd().

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

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

Definition at line 607 of file imath.c.

References CHECK, CLAMP, cmp(), mpz::digits, MAX, MP_DIGITS, MP_MEMORY, MP_OK, MP_SIGN, MP_USED, NULL, s_pad(), s_uadd(), s_ucmp(), and s_usub().

Referenced by mp_int_add_value(), mp_int_egcd(), mp_int_mod(), and mp_int_sqrt().

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

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

Definition at line 684 of file imath.c.

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

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

mp_int mp_int_alloc ( void )

Definition at line 371 of file imath.c.

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

Referenced by mp_new().

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

mp_result mp_int_binary_len ( mp_int z )

Definition at line 2169 of file imath.c.

References mp_int_count_bits(), and mp_int_unsigned_len().

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

void mp_int_clear ( mp_int z )

Definition at line 478 of file imath.c.

References MP_DIGITS, NULL, and s_free.

Referenced by mp_int_div(), mp_int_div_value(), mp_int_egcd(), mp_int_expt(), mp_int_expt_value(), mp_int_exptmod(), mp_int_exptmod_known(), mp_int_free(), mp_int_gcd(), mp_int_invmod(), mp_int_mod(), mp_int_sqrt(), mp_int_to_string(), s_embar(), and s_udiv().

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

int mp_int_compare	(	mp_int	a,
		mp_int	b
	)

Definition at line 1241 of file imath.c.

References CHECK, cmp(), MP_SIGN, MP_ZPOS, NULL, and s_ucmp().

Referenced by mp_int_egcd(), and s_reduce().

01242 {
01243     mp_sign     sa;
01244 
01245     CHECK(a != NULL && b != NULL);
01246 
01247     sa = MP_SIGN(a);
01248     if (sa == MP_SIGN(b))
01249     {
01250         int         cmp = s_ucmp(a, b);
01251 
01252         /*
01253          * If they're both zero or positive, the normal comparison applies; if
01254          * both negative, the sense is reversed.
01255


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

Header And Logo

imath.c File Reference

Defines

Functions

Variables

Define Documentation

Function Documentation