imath.c File Reference

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

Include dependency graph for imath.c:

Go to the source code of this file.

Macros
#define	assert(TEST)   Assert(TEST)
#define	MP_VALUE_DIGITS(V)   ((sizeof(V) + (sizeof(mp_digit) - 1)) / sizeof(mp_digit))
#define	SWAP(T, A, B)
#define	DECLARE_TEMP(N)
#define	CLEANUP_TEMP()
#define	TEMP(K)   (temp_.value + (K))
#define	REQUIRE(E)

Functions
static mp_size	s_round_prec (mp_size P)
static void	ZERO (mp_digit *P, mp_size S)
static void	COPY (mp_digit *P, mp_digit *Q, mp_size S)
static void	REV (unsigned char *A, int N)
static void	CLAMP (mp_int z_)
static int	MIN (int A, int B)
static mp_size	MAX (mp_size A, mp_size B)
static int	CMPZ (mp_int Z)
static mp_word	UPPER_HALF (mp_word W)
static mp_digit	LOWER_HALF (mp_word W)
static bool	HIGH_BIT_SET (mp_word W)
static bool	ADD_WILL_OVERFLOW (mp_word W, mp_word V)
void	mp_int_default_precision (mp_size size)
void	mp_int_multiply_threshold (mp_size thresh)
static mp_digit *	s_alloc (mp_size num)
static void	s_free (void *ptr)
static bool	s_pad (mp_int z, mp_size min)
static mp_result	GROW (mp_int Z, mp_size N)
static void	s_fake (mp_int z, mp_small value, mp_digit vbuf[])
static void	s_ufake (mp_int z, mp_usmall value, mp_digit vbuf[])
static int	s_cdig (mp_digit *da, mp_digit *db, mp_size len)
static int	s_uvpack (mp_usmall v, mp_digit t[])
static int	s_ucmp (mp_int a, mp_int b)
static int	s_vcmp (mp_int a, mp_small v)
static int	s_uvcmp (mp_int a, mp_usmall uv)
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, mp_small 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_knuth (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)
static void	UMUL (mp_int X, mp_int Y, mp_int Z)
static void	USQR (mp_int X, mp_int Z)
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, mp_small value)
mp_result	mp_int_init_uvalue (mp_int z, mp_usmall uvalue)
mp_result	mp_int_set_value (mp_int z, mp_small value)
mp_result	mp_int_set_uvalue (mp_int z, mp_usmall uvalue)
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, mp_small 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, mp_small 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, mp_small value, mp_int c)
mp_result	mp_int_mul_pow2 (mp_int a, mp_small 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, mp_small value, mp_int q, mp_small *r)
mp_result	mp_int_div_pow2 (mp_int a, mp_small p2, mp_int q, mp_int r)
mp_result	mp_int_expt (mp_int a, mp_small b, mp_int c)
mp_result	mp_int_expt_value (mp_small a, mp_small b, mp_int c)
mp_result	mp_int_expt_full (mp_int a, mp_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, mp_small value)
int	mp_int_compare_uvalue (mp_int z, mp_usmall uv)
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, mp_small value, mp_int m, mp_int c)
mp_result	mp_int_exptmod_bvalue (mp_small 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)
mp_result	mp_int_lcm (mp_int a, mp_int b, mp_int c)
bool	mp_int_divisible_value (mp_int a, mp_small v)
int	mp_int_is_pow2 (mp_int z)
mp_result	mp_int_root (mp_int a, mp_small b, mp_int c)
mp_result	mp_int_to_int (mp_int z, mp_small *out)
mp_result	mp_int_to_uint (mp_int z, mp_usmall *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 osize, mp_size nsize)

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_result	MP_MINERR = -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 = 8
static mp_size	multiply_threshold = 32

Macro Definition Documentation

assert

#define assert

(

TEST

)

Assert(TEST)

Definition at line 73 of file imath.c.

Referenced by addchr(), addrange(), bracket(), breakconstraintloop(), brenext(), caltdissect(), cbracket(), cbrdissect(), cclass_column_index(), ccondissect(), cdissect(), cfind(), cfindloop(), changearcsource(), changearctarget(), check_in_colors_match(), check_out_colors_match(), checkmatchall(), checkmatchall_recurse(), citerdissect(), cleanup(), clearcvec(), cloneouts(), clonesuccessorstates(), colorchain(), colorcomplement(), combine(), compact(), copyins(), copyouts(), createarc(), crevcondissect(), creviterdissect(), delsub(), deltraverse(), dumpnfa(), duptraverse(), eclass(), element(), find(), findconstraintloop(), fixconstraintloops(), fixempties(), freearc(), freecnfa(), freecolor(), freelacons(), freestate(), generate_unaccent_rules::get_plain_letter(), generate_unaccent_rules::get_plain_letters(), getladfa(), getvacant(), IncreaseBuffer(), inet_cidr_pton_ipv4(), inet_net_pton_ipv4(), initialize(), lacon(), lexescape(), lexstart(), longest(), makesearch(), markst(), matchuntil(), mergeins(), miss(), moresubs(), moveins(), moveouts(), mp_int_abs(), mp_int_add(), mp_int_compare(), mp_int_compare_unsigned(), mp_int_compare_uvalue(), mp_int_compare_value(), mp_int_compare_zero(), mp_int_copy(), mp_int_count_bits(), mp_int_default_precision(), mp_int_div(), mp_int_div_pow2(), mp_int_egcd(), mp_int_expt(), mp_int_expt_full(), mp_int_expt_value(), mp_int_exptmod(), mp_int_exptmod_known(), mp_int_free(), mp_int_gcd(), mp_int_init_copy(), mp_int_init_size(), mp_int_invmod(), mp_int_is_pow2(), mp_int_lcm(), mp_int_mul(), mp_int_mul_pow2(), mp_int_multiply_threshold(), mp_int_neg(), mp_int_read_binary(), mp_int_read_cstring(), mp_int_read_unsigned(), mp_int_redux_const(), mp_int_root(), mp_int_sqr(), mp_int_string_len(), mp_int_sub(), mp_int_to_binary(), mp_int_to_int(), mp_int_to_string(), mp_int_to_uint(), mp_int_to_unsigned(), mp_int_zero(), newarc(), newcolor(), newdfa(), NewMetaString(), newstate(), newsub(), next(), nfanode(), nfatree(), nonword(), numst(), okcolors(), optimizebracket(), parse(), generate_unaccent_rules::parse_cldr_latin_ascii_transliterator(), parsebranch(), parseqatom(), pg_reg_colorisbegin(), pg_reg_colorisend(), pg_reg_getcharacters(), pg_reg_getcolor(), pg_reg_getfinalstate(), pg_reg_getinitialstate(), pg_reg_getnumcharacters(), pg_reg_getnumcolors(), pg_reg_getnumoutarcs(), pg_reg_getnumstates(), pg_reg_getoutarcs(), pg_regcomp(), pg_regexec(), pg_regprefix(), processlacon(), pull(), pullback(), push(), pushfwd(), removecaptures(), s_alloc(), s_embar(), s_kmul(), s_ksqr(), s_outlen(), s_qsub(), s_realloc(), s_udiv_knuth(), s_usqr(), s_usub(), s_val2ch(), scanplain(), shortest(), skip(), sortins(), sortouts(), specialcolors(), store_match(), subcolor(), subcolorhi(), subcoloronechr(), subcoloronerange(), subre(), subset(), uncolorchain(), and word().

CLEANUP_TEMP

#define CLEANUP_TEMP

(

)

Value:

CLEANUP:                                \
  do {                                    \
    for (int i = 0; i < temp_.len; i++) { \
      mp_int_clear(TEMP(i));              \
    }                                     \
    if (temp_.err != MP_OK) {             \
      return temp_.err;                   \
    }                                     \
  } while (0)

Definition at line 222 of file imath.c.

Referenced by mp_int_div(), mp_int_div_value(), mp_int_egcd(), mp_int_expt(), mp_int_expt_full(), mp_int_expt_value(), mp_int_exptmod(), mp_int_exptmod_known(), mp_int_gcd(), mp_int_invmod(), mp_int_lcm(), mp_int_mod(), mp_int_root(), s_embar(), and s_udiv_knuth().

DECLARE_TEMP

#define DECLARE_TEMP

(

N

)

Value:

struct {                                \
    mpz_t value[(N)];                     \
    int len;                              \
    mp_result err;                        \
  } temp_ = {                             \
      .len = (N),                         \
      .err = MP_OK,                       \
  };                                      \
  do {                                    \
    for (int i = 0; i < temp_.len; i++) { \
      mp_int_init(TEMP(i));               \
    }                                     \
  } while (0)

Definition at line 206 of file imath.c.

Referenced by mp_int_div(), mp_int_div_value(), mp_int_egcd(), mp_int_expt(), mp_int_expt_full(), mp_int_expt_value(), mp_int_exptmod(), mp_int_exptmod_known(), mp_int_gcd(), mp_int_invmod(), mp_int_lcm(), mp_int_mod(), mp_int_root(), s_embar(), and s_udiv_knuth().

MP_VALUE_DIGITS

#define MP_VALUE_DIGITS

(

V

)

((sizeof(V) + (sizeof(mp_digit) - 1)) / sizeof(mp_digit))

Definition at line 119 of file imath.c.

Referenced by mp_int_add_value(), mp_int_div_value(), mp_int_exptmod_bvalue(), mp_int_exptmod_evalue(), mp_int_init_uvalue(), mp_int_init_value(), mp_int_mul_value(), mp_int_set_uvalue(), mp_int_set_value(), mp_int_sub_value(), s_ufake(), and s_uvcmp().

REQUIRE

#define REQUIRE

(

E

)

Value:

do {                                    \
    temp_.err = (E);                      \
    if (temp_.err != MP_OK) goto CLEANUP; \
  } while (0)

Definition at line 240 of file imath.c.

Referenced by mp_int_div(), mp_int_div_value(), mp_int_egcd(), mp_int_expt(), mp_int_expt_full(), mp_int_expt_value(), mp_int_exptmod(), mp_int_exptmod_known(), mp_int_gcd(), mp_int_invmod(), mp_int_lcm(), mp_int_mod(), mp_int_root(), s_embar(), and s_udiv_knuth().

SWAP

#define SWAP	(		T,
			A,
			B
	)

Value:

do {                \
    T t_ = (A);       \
    A = (B);          \
    B = t_;           \
  } while (0)

Definition at line 194 of file imath.c.

Referenced by s_kmul(), and s_uadd().

TEMP

#define TEMP

(

K

)

(temp_.value + (K))

Definition at line 234 of file imath.c.

Referenced by mp_int_div(), mp_int_div_value(), mp_int_egcd(), mp_int_expt(), mp_int_expt_full(), mp_int_expt_value(), mp_int_exptmod(), mp_int_exptmod_known(), mp_int_gcd(), mp_int_invmod(), mp_int_lcm(), mp_int_mod(), mp_int_root(), s_embar(), and s_udiv_knuth().

Function Documentation

ADD_WILL_OVERFLOW()

static bool ADD_WILL_OVERFLOW ( mp_word  W, mp_word  V  )

inlinestatic

Definition at line 275 of file imath.c.

References MP_WORD_MAX.

Referenced by s_usqr().

{
    return ((MP_WORD_MAX - V) < W);
}

CLAMP()

static void CLAMP ( mp_int  z_ )

inlinestatic

Definition at line 168 of file imath.c.

References MP_DIGITS(), MP_USED(), and mpz_t::used.

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(), s_udiv_knuth(), UMUL(), and USQR().

{
    mp_size     uz_ = MP_USED(z_);
    mp_digit   *dz_ = MP_DIGITS(z_) + uz_ - 1;

    while (uz_ > 1 && (*dz_-- == 0))
        --uz_;
    z_->used = uz_;
}

CMPZ()

static int CMPZ ( mp_int  Z )

inlinestatic

Definition at line 248 of file imath.c.

References mpz_t::digits, MP_NEG, mpz_t::sign, and mpz_t::used.

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

{
    if (Z->used == 1 && Z->digits[0] == 0)
        return 0;
    return (Z->sign == MP_NEG) ? -1 : 1;
}

COPY()

static void COPY ( mp_digit *  P, mp_digit *  Q, mp_size  S  )

inlinestatic

Definition at line 141 of file imath.c.

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

{
    mp_size     i__ = S * sizeof(mp_digit);
    mp_digit   *p__ = P;
    mp_digit   *q__ = Q;

    memcpy(q__, p__, i__);
}

GROW()

static mp_result GROW ( mp_int  Z, mp_size  N  )

inlinestatic

Definition at line 313 of file imath.c.

References buf, MP_MEMORY, MP_OK, s_2comp(), s_2expt(), s_brmu(), s_cdig(), s_ch2val(), s_dadd(), s_dbmul(), s_ddiv(), s_dmul(), s_dp2k(), s_embar(), s_fake(), s_inlen(), s_isp2(), s_kmul(), s_ksqr(), s_norm(), s_outlen(), s_pad(), s_qdiv(), s_qmod(), s_qmul(), s_qsub(), s_reduce(), s_tobin(), s_uadd(), s_ucmp(), s_udiv_knuth(), s_ufake(), s_umul(), s_usqr(), s_usub(), s_uvcmp(), s_uvpack(), s_val2ch(), s_vcmp(), and value.

Referenced by mp_int_exptmod(), mp_int_exptmod_known(), s_embar(), and s_udiv_knuth().

{
    return s_pad(Z, N) ? MP_OK : MP_MEMORY;
}

HIGH_BIT_SET()

static bool HIGH_BIT_SET ( mp_word  W )

inlinestatic

Definition at line 268 of file imath.c.

References MP_WORD_BIT.

Referenced by s_usqr().

{
    return (W >> (MP_WORD_BIT - 1)) != 0;
}

LOWER_HALF()

static mp_digit LOWER_HALF ( mp_word  W )

inlinestatic

Definition at line 261 of file imath.c.

References W.

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

{
    return (mp_digit) (W);
}

MAX()

static mp_size MAX ( mp_size  A, mp_size  B  )

inlinestatic

Definition at line 187 of file imath.c.

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

{
    return (B > A ? B : A);
}

MIN()

static int MIN ( int  A, int  B  )

inlinestatic

Definition at line 182 of file imath.c.

Referenced by mp_int_egcd(), and mp_int_gcd().

{
    return (B < A ? B : A);
}

mp_error_string()

const char* mp_error_string

(

mp_result

res

)

Returns a pointer to a brief, human-readable, zero-terminated string describing res. The returned string is statically allocated and must not be freed by the caller.

Definition at line 2184 of file imath.c.

References fill(), s_error_msg, and s_unknown_err.

Referenced by mp_int_sqrt().

{
    if (res > 0)
        return s_unknown_err;

    res = -res;
    int         ix;

    for (ix = 0; ix < res && s_error_msg[ix] != NULL; ++ix)
        ;

    if (s_error_msg[ix] != NULL)
    {
        return s_error_msg[ix];
    }
    else
    {
        return s_unknown_err;
    }
}

mp_int_abs()

mp_result mp_int_abs	(	mp_int	a,
		mp_int	c
	)

Sets c to the absolute value of a.

Definition at line 663 of file imath.c.

References assert, mp_int_copy(), MP_OK, MP_ZPOS, and mpz_t::sign.

Referenced by mp_int_egcd(), mp_int_gcd(), and mp_int_is_even().

{
    assert(a != NULL && c != NULL);

    mp_result   res;

    if ((res = mp_int_copy(a, c)) != MP_OK)
        return res;

    c->sign = MP_ZPOS;
    return MP_OK;
}

mp_int_add()

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

Sets c to the sum of a and b.

Definition at line 693 of file imath.c.

References assert, CLAMP(), cmp(), mpz_t::digits, MAX(), MP_DIGITS(), mp_int_zero(), MP_MEMORY, MP_OK, MP_SIGN(), MP_USED(), s_pad(), s_uadd(), s_ucmp(), s_usub(), mpz_t::sign, and mpz_t::used.

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

{
    assert(a != NULL && b != NULL && c != NULL);

    mp_size     ua = MP_USED(a);
    mp_size     ub = MP_USED(b);
    mp_size     max = MAX(ua, ub);

    if (MP_SIGN(a) == MP_SIGN(b))
    {
        /* Same sign -- add magnitudes, preserve sign of addends */
        if (!s_pad(c, max))
            return MP_MEMORY;

        mp_digit    carry = s_uadd(MP_DIGITS(a), MP_DIGITS(b), MP_DIGITS(c), ua, ub);
        mp_size     uc = max;

        if (carry)
        {
            if (!s_pad(c, max + 1))
                return MP_MEMORY;

            c->digits[max] = carry;
            ++uc;
        }

        c->used = uc;
        c->sign = a->sign;

    }
    else
    {
        /* Different signs -- subtract magnitudes, preserve sign of greater */
        int         cmp = s_ucmp(a, b); /* magnitude comparision, sign ignored */

        /*
         * Set x to max(a, b), y to min(a, b) to simplify later code. A
         * special case yields zero for equal magnitudes.
         */
        mp_int      x,
                    y;

        if (cmp == 0)
        {
            mp_int_zero(c);
            return MP_OK;
        }
        else if (cmp < 0)
        {
            x = b;
            y = a;
        }
        else
        {
            x = a;
            y = b;
        }

        if (!s_pad(c, MP_USED(x)))
            return MP_MEMORY;

        /* Subtract smaller from larger */
        s_usub(MP_DIGITS(x), MP_DIGITS(y), MP_DIGITS(c), MP_USED(x), MP_USED(y));
        c->used = x->used;
        CLAMP(c);

        /* Give result the sign of the larger */
        c->sign = x->sign;
    }

    return MP_OK;
}

mp_int_add_value()

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

Sets c to the sum of a and value.

Definition at line 767 of file imath.c.

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

Referenced by mp_int_is_even().

{
    mpz_t       vtmp;
    mp_digit    vbuf[MP_VALUE_DIGITS(value)];

    s_fake(&vtmp, value, vbuf);

    return mp_int_add(a, &vtmp, c);
}

mp_int_alloc()

mp_int mp_int_alloc

(

void

)

Allocates a fresh zero-valued mpz_t on the heap, returning NULL in case of error. The only possible error is out-of-memory.

Definition at line 479 of file imath.c.

References mp_int_init(), and palloc().

Referenced by mp_int_is_even(), and mp_new().

{
    mp_int      out = palloc(sizeof(mpz_t));

    if (out != NULL)
        mp_int_init(out);

    return out;
}

mp_int_binary_len()

mp_result mp_int_binary_len

(

mp_int

z

)

Returns the number of bytes to represent z in 2's complement binary.

Definition at line 2116 of file imath.c.

References generate_unaccent_rules::bytes(), mp_int_count_bits(), and mp_int_unsigned_len().

Referenced by mp_int_sqrt().

{
    mp_result   res = mp_int_count_bits(z);

    if (res <= 0)
        return res;

    int         bytes = mp_int_unsigned_len(z);

    /*
     * If the highest-order bit falls exactly on a byte boundary, we need to
     * pad with an extra byte so that the sign will be read correctly when
     * reading it back in.
     */
    if (bytes * CHAR_BIT == res)
        ++bytes;

    return bytes;
}

mp_int_clear()

void mp_int_clear

(

mp_int

z

)

Releases the storage used by z.

Definition at line 587 of file imath.c.

References mpz_t::digits, MP_DIGITS(), s_free(), and mpz_t::single.

Referenced by mp_int_free(), mp_int_is_even(), and mp_int_to_string().

{
    if (z == NULL)
        return;

    if (MP_DIGITS(z) != NULL)
    {
        if (MP_DIGITS(z) != &(z->single))
            s_free(MP_DIGITS(z));

        z->digits = NULL;
    }
}

mp_int_compare()

int mp_int_compare	(	mp_int	a,
		mp_int	b
	)

Returns the comparator of a and b.

Definition at line 1274 of file imath.c.

References assert, cmp(), MP_SIGN(), MP_ZPOS, and s_ucmp().

Referenced by mp_int_egcd(), mp_int_mod_value(), and s_reduce().

{
    assert(a != NULL && b != NULL);

    mp_sign     sa = MP_SIGN(a);

    if (sa == MP_SIGN(b))
    {
        int         cmp = s_ucmp(a, b);

        /*
         * If they're both zero or positive, the normal comparison applies; if
         * both negative, the sense is reversed.
         */
        if (sa == MP_ZPOS)
        {
            return cmp;
        }
        else
        {
            return -cmp;
        }
    }
    else if (sa == MP_ZPOS)
    {
        return 1;
    }
    else
    {
        return -1;
    }
}

mp_int_compare_unsigned()

int mp_int_compare_unsigned	(	mp_int	a,
		mp_int	b
	)

Returns the comparator of the magnitudes of a and b, disregarding their signs. Neither a nor b is modified by the comparison.

Definition at line 1308 of file imath.c.

References assert, and s_ucmp().

Referenced by mp_int_mod_value(), and mp_int_root().

{
    assert(a != NULL && b != NULL);

    return s_ucmp(a, b);
}

mp_int_compare_uvalue()

int mp_int_compare_uvalue	(	mp_int	z,
		mp_usmall	uv
	)

Returns the comparator of z and the unsigned value uv.

Definition at line 1354 of file imath.c.

References assert, MP_NEG, MP_SIGN(), and s_uvcmp().

Referenced by mp_int_mod_value(), and mp_int_to_uint().

{
    assert(z != NULL);

    if (MP_SIGN(z) == MP_NEG)
    {
        return -1;
    }
    else
    {
        return s_uvcmp(z, uv);
    }
}

mp_int_compare_value()

int mp_int_compare_value	(	mp_int	z,
		mp_small	v
	)

Returns the comparator of z and the signed value v.

Definition at line 1335 of file imath.c.

References assert, cmp(), MP_NEG, MP_SIGN(), MP_ZPOS, and s_vcmp().

Referenced by mp_int_invmod(), mp_int_mod_value(), and mp_int_to_int().

{
    assert(z != NULL);

    mp_sign     vsign = (value < 0) ? MP_NEG : MP_ZPOS;

    if (vsign == MP_SIGN(z))
    {
        int         cmp = s_vcmp(z, value);

        return (vsign == MP_ZPOS) ? cmp : -cmp;
    }
    else
    {
        return (value < 0) ? 1 : -1;
    }
}

mp_int_compare_zero()

int mp_int_compare_zero

(

mp_int

z

)

Returns the comparator of z and zero.

Definition at line 1316 of file imath.c.

References assert, mpz_t::digits, MP_SIGN(), MP_USED(), and MP_ZPOS.

Referenced by mp_int_mod_value(), and mp_int_mul().

{
    assert(z != NULL);

    if (MP_USED(z) == 1 && z->digits[0] == 0)
    {
        return 0;
    }
    else if (MP_SIGN(z) == MP_ZPOS)
    {
        return 1;
    }
    else
    {
        return -1;
    }
}

mp_int_copy()

mp_result mp_int_copy	(	mp_int	a,
		mp_int	c
	)

Replaces the value of c with a copy of the value of a. No new memory is allocated unless a has more significant digits than c has allocated.

Definition at line 611 of file imath.c.

References assert, COPY(), MP_DIGITS(), MP_MEMORY, MP_OK, MP_USED(), s_pad(), mpz_t::sign, and mpz_t::used.

Referenced by mp_int_abs(), mp_int_div(), mp_int_div_pow2(), mp_int_egcd(), mp_int_expt(), mp_int_expt_full(), mp_int_exptmod(), mp_int_exptmod_known(), mp_int_gcd(), mp_int_invmod(), mp_int_is_even(), mp_int_lcm(), mp_int_mod(), mp_int_mul_pow2(), mp_int_neg(), mp_int_root(), mp_int_set_uvalue(), mp_int_set_value(), s_embar(), s_reduce(), and s_udiv_knuth().

{
    assert(a != NULL && c != NULL);

    if (a != c)
    {
        mp_size     ua = MP_USED(a);
        mp_digit   *da,
                   *dc;

        if (!s_pad(c, ua))
            return MP_MEMORY;

        da = MP_DIGITS(a);
        dc = MP_DIGITS(c);
        COPY(da, dc, ua);

        c->used = ua;
        c->sign = a->sign;
    }

    return MP_OK;
}

mp_int_count_bits()

mp_result mp_int_count_bits

(

mp_int

z

)

Returns the number of significant bits in z.

Definition at line 2038 of file imath.c.

References assert, mpz_t::digits, MP_DIGIT_BIT, and MP_USED().

Referenced by bn_to_mpi(), mp_int_binary_len(), mp_int_sqrt(), mp_int_unsigned_len(), mpi_to_bn(), pgp_elgamal_encrypt(), and s_outlen().

{
    assert(z != NULL);

    mp_size     uz = MP_USED(z);

    if (uz == 1 && z->digits[0] == 0)
        return 1;

    --uz;
    mp_size     nbits = uz * MP_DIGIT_BIT;
    mp_digit    d = z->digits[uz];

    while (d != 0)
    {
        d >>= 1;
        ++nbits;
    }

    return nbits;
}

mp_int_default_precision()

void mp_int_default_precision

(

mp_size

ndigits

)

Sets the default number of digits allocated to an mp_int constructed by mp_int_init_size() with prec == 0. Allocations are rounded up to multiples of this value. MP_DEFAULT_PREC is the default value. Requires ndigits > 0.

Definition at line 284 of file imath.c.

References assert, and default_precision.

{
    assert(size > 0);
    default_precision = size;
}

mp_int_div()

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

Sets q and r to the quotent and remainder of a / b. Division by powers of 2 is detected and handled efficiently. The remainder is pinned to 0 <= r < b.

Either of q or r may be NULL, but not both, and q and r may not point to the same value.

Definition at line 1002 of file imath.c.

References assert, CLEANUP_TEMP, cmp(), CMPZ(), DECLARE_TEMP, mpz_t::digits, mp_int_copy(), mp_int_zero(), MP_NEG, MP_OK, MP_SIGN(), MP_UNDEF, MP_ZPOS, REQUIRE, s_isp2(), s_qdiv(), s_qmod(), s_ucmp(), s_udiv_knuth(), mpz_t::sign, and TEMP.

Referenced by mp_int_div_value(), mp_int_is_even(), mp_int_lcm(), mp_int_mod(), mp_int_root(), and s_brmu().

{
    assert(a != NULL && b != NULL && q != r);

    int         cmp;
    mp_result   res = MP_OK;
    mp_int      qout,
                rout;
    mp_sign     sa = MP_SIGN(a);
    mp_sign     sb = MP_SIGN(b);

    if (CMPZ(b) == 0)
    {
        return MP_UNDEF;
    }
    else if ((cmp = s_ucmp(a, b)) < 0)
    {
        /*
         * If |a| < |b|, no division is required: q = 0, r = a
         */
        if (r && (res = mp_int_copy(a, r)) != MP_OK)
            return res;

        if (q)
            mp_int_zero(q);

        return MP_OK;
    }
    else if (cmp == 0)
    {
        /*
         * If |a| = |b|, no division is required: q = 1 or -1, r = 0
         */
        if (r)
            mp_int_zero(r);

        if (q)
        {
            mp_int_zero(q);
            q->digits[0] = 1;

            if (sa != sb)
                q->sign = MP_NEG;
        }

        return MP_OK;
    }

    /*
     * When |a| > |b|, real division is required.  We need someplace to store
     * quotient and remainder, but q and r are allowed to be NULL or to
     * overlap with the inputs.
     */
    DECLARE_TEMP(2);
    int         lg;

    if ((lg = s_isp2(b)) < 0)
    {
        if (q && b != q)
        {
            REQUIRE(mp_int_copy(a, q));
            qout = q;
        }
        else
        {
            REQUIRE(mp_int_copy(a, TEMP(0)));
            qout = TEMP(0);
        }

        if (r && a != r)
        {
            REQUIRE(mp_int_copy(b, r));
            rout = r;
        }
        else
        {
            REQUIRE(mp_int_copy(b, TEMP(1)));
            rout = TEMP(1);
        }

        REQUIRE(s_udiv_knuth(qout, rout));
    }
    else
    {
        if (q)
            REQUIRE(mp_int_copy(a, q));
        if (r)
            REQUIRE(mp_int_copy(a, r));

        if (q)
            s_qdiv(q, (mp_size) lg);
        qout = q;
        if (r)
            s_qmod(r, (mp_size) lg);
        rout = r;
    }

    /* Recompute signs for output */
    if (rout)
    {
        rout->sign = sa;
        if (CMPZ(rout) == 0)
            rout->sign = MP_ZPOS;
    }
    if (qout)
    {
        qout->sign = (sa == sb) ? MP_ZPOS : MP_NEG;
        if (CMPZ(qout) == 0)
            qout->sign = MP_ZPOS;
    }

    if (q)
        REQUIRE(mp_int_copy(qout, q));
    if (r)
        REQUIRE(mp_int_copy(rout, r));
    CLEANUP_TEMP();
    return res;
}

mp_int_div_pow2()

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

Sets q and r to the quotient and remainder of a / 2^p2. This is a special case for division by powers of two that is more efficient than using ordinary division. Note that mp_int_div() will automatically handle this case, this function is for cases where you have only the exponent.

Definition at line 1159 of file imath.c.

References assert, mp_int_copy(), MP_OK, s_qdiv(), and s_qmod().

Referenced by mp_int_is_even().

{
    assert(a != NULL && p2 >= 0 && q != r);

    mp_result   res = MP_OK;

    if (q != NULL && (res = mp_int_copy(a, q)) == MP_OK)
    {
        s_qdiv(q, (mp_size) p2);
    }

    if (res == MP_OK && r != NULL && (res = mp_int_copy(a, r)) == MP_OK)
    {
        s_qmod(r, (mp_size) p2);
    }

    return res;
}

mp_int_div_value()

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

Sets q and *r to the quotent and remainder of a / value. Division by powers of 2 is detected and handled efficiently. The remainder is pinned to 0 <= *r < b. Either of q or r may be NULL.

Definition at line 1141 of file imath.c.

References CLEANUP_TEMP, DECLARE_TEMP, mp_int_div(), mp_int_to_int(), MP_OK, MP_VALUE_DIGITS, REQUIRE, s_fake(), and TEMP.

Referenced by mp_int_divisible_value(), mp_int_is_even(), and mp_int_mod_value().

{
    mpz_t       vtmp;
    mp_digit    vbuf[MP_VALUE_DIGITS(value)];

    s_fake(&vtmp, value, vbuf);

    DECLARE_TEMP(1);
    REQUIRE(mp_int_div(a, &vtmp, q, TEMP(0)));

    if (r)
        (void) mp_int_to_int(TEMP(0), r);   /* can't fail */

    CLEANUP_TEMP();
    return MP_OK;
}

mp_int_divisible_value()

bool mp_int_divisible_value	(	mp_int	a,
		mp_small	v
	)

Reports whether a is divisible by v.

Definition at line 1738 of file imath.c.

References mp_int_div_value(), and MP_OK.

Referenced by mp_int_mod_value().

{
    mp_small    rem = 0;

    if (mp_int_div_value(a, v, NULL, &rem) != MP_OK)
    {
        return false;
    }
    return rem == 0;
}

mp_int_egcd()

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

Sets c to the greatest common divisor of a and b, and sets x and y to values satisfying Bezout's identity gcd(a, b) = ax + by.

It returns MP_UNDEF if the GCD is undefined, such as for example if a and b are both zero.

Definition at line 1593 of file imath.c.

References assert, CLEANUP_TEMP, CMPZ(), DECLARE_TEMP, MIN(), mp_int_abs(), mp_int_add(), mp_int_compare(), mp_int_copy(), mp_int_is_even(), mp_int_is_odd(), mp_int_set_value(), mp_int_sub(), mp_int_zero(), MP_MEMORY, MP_OK, MP_UNDEF, MP_ZPOS, REQUIRE, s_dp2k(), s_qdiv(), s_qmul(), and TEMP.

Referenced by mp_int_invmod(), and mp_int_mod_value().

{
    assert(a != NULL && b != NULL && c != NULL && (x != NULL || y != NULL));

    mp_result   res = MP_OK;
    int         ca = CMPZ(a);
    int         cb = CMPZ(b);

    if (ca == 0 && cb == 0)
    {
        return MP_UNDEF;
    }
    else if (ca == 0)
    {
        if ((res = mp_int_abs(b, c)) != MP_OK)
            return res;
        mp_int_zero(x);
        (void) mp_int_set_value(y, 1);
        return MP_OK;
    }
    else if (cb == 0)
    {
        if ((res = mp_int_abs(a, c)) != MP_OK)
            return res;
        (void) mp_int_set_value(x, 1);
        mp_int_zero(y);
        return MP_OK;
    }

    /*
     * Initialize temporaries: A:0, B:1, C:2, D:3, u:4, v:5, ou:6, ov:7
     */
    DECLARE_TEMP(8);
    REQUIRE(mp_int_set_value(TEMP(0), 1));
    REQUIRE(mp_int_set_value(TEMP(3), 1));
    REQUIRE(mp_int_copy(a, TEMP(4)));
    REQUIRE(mp_int_copy(b, TEMP(5)));

    /* We will work with absolute values here */
    TEMP(4)->sign = MP_ZPOS;
    TEMP(5)->sign = MP_ZPOS;

    int         k = 0;

    {                           /* Divide out common factors of 2 from u and v */
        int         div2_u = s_dp2k(TEMP(4)),
                    div2_v = s_dp2k(TEMP(5));

        k = MIN(div2_u, div2_v);
        s_qdiv(TEMP(4), k);
        s_qdiv(TEMP(5), k);
    }

    REQUIRE(mp_int_copy(TEMP(4), TEMP(6)));
    REQUIRE(mp_int_copy(TEMP(5), TEMP(7)));

    for (;;)
    {
        while (mp_int_is_even(TEMP(4)))
        {
            s_qdiv(TEMP(4), 1);

            if (mp_int_is_odd(TEMP(0)) || mp_int_is_odd(TEMP(1)))
            {
                REQUIRE(mp_int_add(TEMP(0), TEMP(7), TEMP(0)));
                REQUIRE(mp_int_sub(TEMP(1), TEMP(6), TEMP(1)));
            }

            s_qdiv(TEMP(0), 1);
            s_qdiv(TEMP(1), 1);
        }

        while (mp_int_is_even(TEMP(5)))
        {
            s_qdiv(TEMP(5), 1);

            if (mp_int_is_odd(TEMP(2)) || mp_int_is_odd(TEMP(3)))
            {
                REQUIRE(mp_int_add(TEMP(2), TEMP(7), TEMP(2)));
                REQUIRE(mp_int_sub(TEMP(3), TEMP(6), TEMP(3)));
            }

            s_qdiv(TEMP(2), 1);
            s_qdiv(TEMP(3), 1);
        }

        if (mp_int_compare(TEMP(4), TEMP(5)) >= 0)
        {
            REQUIRE(mp_int_sub(TEMP(4), TEMP(5), TEMP(4)));
            REQUIRE(mp_int_sub(TEMP(0), TEMP(2), TEMP(0)));
            REQUIRE(mp_int_sub(TEMP(1), TEMP(3), TEMP(1)));
        }
        else
        {
            REQUIRE(mp_int_sub(TEMP(5), TEMP(4), TEMP(5)));
            REQUIRE(mp_int_sub(TEMP(2), TEMP(0), TEMP(2)));
            REQUIRE(mp_int_sub(TEMP(3), TEMP(1), TEMP(3)));
        }

        if (CMPZ(TEMP(4)) == 0)
        {
            if (x)
                REQUIRE(mp_int_copy(TEMP(2), x));
            if (y)
                REQUIRE(mp_int_copy(TEMP(3), y));
            if (c)
            {
                if (!s_qmul(TEMP(5), k))
                {
                    REQUIRE(MP_MEMORY);
                }
                REQUIRE(mp_int_copy(TEMP(5), c));
            }

            break;
        }
    }

    CLEANUP_TEMP();
    return MP_OK;
}

mp_int_expt()

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

Sets c to the value of a raised to the b power. It returns MP_RANGE if b < 0.

Definition at line 1179 of file imath.c.

References assert, CLEANUP_TEMP, DECLARE_TEMP, mp_int_copy(), mp_int_mul(), mp_int_set_value(), mp_int_sqr(), MP_OK, MP_RANGE, REQUIRE, and TEMP.

Referenced by mp_int_is_even(), and mp_int_root().

{
    assert(c != NULL);
    if (b < 0)
        return MP_RANGE;

    DECLARE_TEMP(1);
    REQUIRE(mp_int_copy(a, TEMP(0)));

    (void) mp_int_set_value(c, 1);
    unsigned int v = labs(b);

    while (v != 0)
    {
        if (v & 1)
        {
            REQUIRE(mp_int_mul(c, TEMP(0), c));
        }

        v >>= 1;
        if (v == 0)
            break;

        REQUIRE(mp_int_sqr(TEMP(0), TEMP(0)));
    }

    CLEANUP_TEMP();
    return MP_OK;
}

mp_int_expt_full()

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

Sets c to the value of a raised to the b power. It returns MP_RANGE) if b < 0.

Definition at line 1241 of file imath.c.

References assert, CLEANUP_TEMP, DECLARE_TEMP, mpz_t::digits, MP_DIGIT_BIT, mp_int_copy(), mp_int_mul(), mp_int_set_value(), mp_int_sqr(), MP_NEG, MP_OK, MP_RANGE, MP_SIGN(), MP_USED(), REQUIRE, and TEMP.

Referenced by mp_int_is_even().

{
    assert(a != NULL && b != NULL && c != NULL);
    if (MP_SIGN(b) == MP_NEG)
        return MP_RANGE;

    DECLARE_TEMP(1);
    REQUIRE(mp_int_copy(a, TEMP(0)));

    (void) mp_int_set_value(c, 1);
    for (unsigned ix = 0; ix < MP_USED(b); ++ix)
    {
        mp_digit    d = b->digits[ix];

        for (unsigned jx = 0; jx < MP_DIGIT_BIT; ++jx)
        {
            if (d & 1)
            {
                REQUIRE(mp_int_mul(c, TEMP(0), c));
            }

            d >>= 1;
            if (d == 0 && ix + 1 == MP_USED(b))
                break;
            REQUIRE(mp_int_sqr(TEMP(0), TEMP(0)));
        }
    }

    CLEANUP_TEMP();
    return MP_OK;
}

mp_int_expt_value()

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

Sets c to the value of a raised to the b power. It returns MP_RANGE if b < 0.

Definition at line 1210 of file imath.c.

References assert, CLEANUP_TEMP, DECLARE_TEMP, mp_int_mul(), mp_int_set_value(), mp_int_sqr(), MP_OK, MP_RANGE, REQUIRE, and TEMP.

Referenced by mp_int_is_even().

{
    assert(c != NULL);
    if (b < 0)
        return MP_RANGE;

    DECLARE_TEMP(1);
    REQUIRE(mp_int_set_value(TEMP(0), a));

    (void) mp_int_set_value(c, 1);
    unsigned int v = labs(b);

    while (v != 0)
    {
        if (v & 1)
        {
            REQUIRE(mp_int_mul(c, TEMP(0), c));
        }

        v >>= 1;
        if (v == 0)
            break;

        REQUIRE(mp_int_sqr(TEMP(0), TEMP(0)));
    }

    CLEANUP_TEMP();
    return MP_OK;
}

mp_int_exptmod()

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

Sets c to the value of a raised to the b power, reduced modulo m. It returns MP_RANGE if b < 0 or MP_UNDEF if m == 0.

Definition at line 1369 of file imath.c.

References assert, CLEANUP_TEMP, CMPZ(), DECLARE_TEMP, GROW(), mp_int_copy(), mp_int_mod(), MP_OK, MP_RANGE, MP_UNDEF, MP_USED(), REQUIRE, s_brmu(), s_embar(), and TEMP.

Referenced by mp_int_exptmod_bvalue(), mp_int_exptmod_evalue(), mp_int_mod_value(), pgp_elgamal_decrypt(), pgp_elgamal_encrypt(), pgp_rsa_decrypt(), and pgp_rsa_encrypt().

{
    assert(a != NULL && b != NULL && c != NULL && m != NULL);

    /* Zero moduli and negative exponents are not considered. */
    if (CMPZ(m) == 0)
        return MP_UNDEF;
    if (CMPZ(b) < 0)
        return MP_RANGE;

    mp_size     um = MP_USED(m);

    DECLARE_TEMP(3);
    REQUIRE(GROW(TEMP(0), 2 * um));
    REQUIRE(GROW(TEMP(1), 2 * um));

    mp_int      s;

    if (c == b || c == m)
    {
        REQUIRE(GROW(TEMP(2), 2 * um));
        s = TEMP(2);
    }
    else
    {
        s = c;
    }

    REQUIRE(mp_int_mod(a, m, TEMP(0)));
    REQUIRE(s_brmu(TEMP(1), m));
    REQUIRE(s_embar(TEMP(0), b, m, TEMP(1), s));
    REQUIRE(mp_int_copy(s, c));

    CLEANUP_TEMP();
    return MP_OK;
}

mp_int_exptmod_bvalue()

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

Sets c to the value of value raised to the b power, modulo m. It returns MP_RANGE if b < 0 or MP_UNDEF if m == 0.

Definition at line 1418 of file imath.c.

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

Referenced by mp_int_mod_value().

{
    mpz_t       vtmp;
    mp_digit    vbuf[MP_VALUE_DIGITS(value)];

    s_fake(&vtmp, value, vbuf);

    return mp_int_exptmod(&vtmp, b, m, c);
}

mp_int_exptmod_evalue()

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

Sets c to the value of a raised to the value power, modulo m. It returns MP_RANGE if value < 0 or MP_UNDEF if m == 0.

Definition at line 1407 of file imath.c.

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

Referenced by mp_int_mod_value().

{
    mpz_t       vtmp;
    mp_digit    vbuf[MP_VALUE_DIGITS(value)];

    s_fake(&vtmp, value, vbuf);

    return mp_int_exptmod(a, &vtmp, m, c);
}

mp_int_exptmod_known()

mp_result mp_int_exptmod_known	(	mp_int	a,
		mp_int	b,
		mp_int	m,
		mp_int	mu,
		mp_int	c
	)

Sets c to the value of a raised to the b power, reduced modulo m, given a precomputed reduction constant mu defined for Barrett's modular reduction algorithm.

It returns MP_RANGE if b < 0 or MP_UNDEF if m == 0.

Definition at line 1429 of file imath.c.

References assert, CLEANUP_TEMP, CMPZ(), DECLARE_TEMP, GROW(), mp_int_copy(), mp_int_mod(), MP_OK, MP_RANGE, MP_UNDEF, MP_USED(), REQUIRE, s_embar(), and TEMP.

Referenced by mp_int_mod_value().

{
    assert(a && b && m && c);

    /* Zero moduli and negative exponents are not considered. */
    if (CMPZ(m) == 0)
        return MP_UNDEF;
    if (CMPZ(b) < 0)
        return MP_RANGE;

    DECLARE_TEMP(2);
    mp_size     um = MP_USED(m);

    REQUIRE(GROW(TEMP(0), 2 * um));

    mp_int      s;

    if (c == b || c == m)
    {
        REQUIRE(GROW(TEMP(1), 2 * um));
        s = TEMP(1);
    }
    else
    {
        s = c;
    }

    REQUIRE(mp_int_mod(a, m, TEMP(0)));
    REQUIRE(s_embar(TEMP(0), b, m, mu, s));
    REQUIRE(mp_int_copy(s, c));

    CLEANUP_TEMP();
    return MP_OK;
}

mp_int_free()

void mp_int_free

(

mp_int

z

)

Releases the storage used by z and also z itself. This should only be used for z allocated by mp_int_alloc().

Definition at line 602 of file imath.c.

References assert, mp_int_clear(), and pfree().

Referenced by mp_clear_free(), and mp_int_is_even().

{
    assert(z != NULL);

    mp_int_clear(z);
    pfree(z);                   /* note: NOT s_free() */
}

mp_int_gcd()

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

Sets c to the greatest common divisor of a and b.

It returns MP_UNDEF if the GCD is undefined, such as for example if a and b are both zero.

Definition at line 1514 of file imath.c.

References assert, CLEANUP_TEMP, CMPZ(), DECLARE_TEMP, MIN(), mp_int_abs(), mp_int_copy(), mp_int_is_odd(), mp_int_neg(), mp_int_sub(), MP_MEMORY, MP_OK, MP_UNDEF, MP_ZPOS, REQUIRE, s_dp2k(), s_qdiv(), s_qmul(), and TEMP.

Referenced by mp_int_lcm(), and mp_int_mod_value().

{
    assert(a != NULL && b != NULL && c != NULL);

    int         ca = CMPZ(a);
    int         cb = CMPZ(b);

    if (ca == 0 && cb == 0)
    {
        return MP_UNDEF;
    }
    else if (ca == 0)
    {
        return mp_int_abs(b, c);
    }
    else if (cb == 0)
    {
        return mp_int_abs(a, c);
    }

    DECLARE_TEMP(3);
    REQUIRE(mp_int_copy(a, TEMP(0)));
    REQUIRE(mp_int_copy(b, TEMP(1)));

    TEMP(0)->sign = MP_ZPOS;
    TEMP(1)->sign = MP_ZPOS;

    int         k = 0;

    {                           /* Divide out common factors of 2 from u and v */
        int         div2_u = s_dp2k(TEMP(0));
        int         div2_v = s_dp2k(TEMP(1));

        k = MIN(div2_u, div2_v);
        s_qdiv(TEMP(0), (mp_size) k);
        s_qdiv(TEMP(1), (mp_size) k);
    }

    if (mp_int_is_odd(TEMP(0)))
    {
        REQUIRE(mp_int_neg(TEMP(1), TEMP(2)));
    }
    else
    {
        REQUIRE(mp_int_copy(TEMP(0), TEMP(2)));
    }

    for (;;)
    {
        s_qdiv(TEMP(2), s_dp2k(TEMP(2)));

        if (CMPZ(TEMP(2)) > 0)
        {
            REQUIRE(mp_int_copy(TEMP(2), TEMP(0)));
        }
        else
        {
            REQUIRE(mp_int_neg(TEMP(2), TEMP(1)));
        }

        REQUIRE(mp_int_sub(TEMP(0), TEMP(1), TEMP(2)));

        if (CMPZ(TEMP(2)) == 0)
            break;
    }

    REQUIRE(mp_int_abs(TEMP(0), c));
    if (!s_qmul(c, (mp_size) k))
        REQUIRE(MP_MEMORY);

    CLEANUP_TEMP();
    return MP_OK;
}

mp_int_init()

mp_result mp_int_init

(

mp_int

z

)

Initializes z with 1-digit precision and sets it to zero. This function cannot fail unless z == NULL.

Definition at line 464 of file imath.c.

References mpz_t::alloc, mpz_t::digits, MP_BADARG, MP_OK, MP_ZPOS, mpz_t::sign, mpz_t::single, and mpz_t::used.

Referenced by mp_int_alloc(), mp_int_init_copy(), mp_int_init_size(), and mp_int_is_even().

{
    if (z == NULL)
        return MP_BADARG;

    z->single = 0;
    z->digits = &(z->single);
    z->alloc = 1;
    z->used = 1;
    z->sign = MP_ZPOS;

    return MP_OK;
}

mp_int_init_copy()

mp_result mp_int_init_copy	(	mp_int	z,
		mp_int	old
	)

Initializes z to be a copy of an already-initialized value in old. The new copy does not share storage with the original.

Definition at line 520 of file imath.c.

References assert, COPY(), default_precision, MAX(), MP_DIGITS(), mp_int_init(), mp_int_init_size(), MP_OK, MP_USED(), mpz_t::sign, and mpz_t::used.

Referenced by mp_int_init_uvalue(), mp_int_init_value(), mp_int_is_even(), and mp_int_to_string().

{
    assert(z != NULL && old != NULL);

    mp_size     uold = MP_USED(old);

    if (uold == 1)
    {
        mp_int_init(z);
    }
    else
    {
        mp_size     target = MAX(uold, default_precision);
        mp_result   res = mp_int_init_size(z, target);

        if (res != MP_OK)
            return res;
    }

    z->used = uold;
    z->sign = old->sign;
    COPY(MP_DIGITS(old), MP_DIGITS(z), uold);

    return MP_OK;
}

mp_int_init_size()

mp_result mp_int_init_size	(	mp_int	z,
		mp_size	prec
	)

Initializes z with at least prec digits of storage, and sets it to zero. If prec is zero, the default precision is used. In either case the size is rounded up to the nearest multiple of the word size.

Definition at line 490 of file imath.c.

References mpz_t::alloc, assert, default_precision, mpz_t::digits, MP_DIGITS(), mp_int_init(), MP_MEMORY, MP_OK, MP_ZPOS, s_alloc(), s_round_prec(), mpz_t::sign, and mpz_t::used.

Referenced by mp_int_init_copy(), mp_int_is_even(), and mp_new().

{
    assert(z != NULL);

    if (prec == 0)
    {
        prec = default_precision;
    }
    else if (prec == 1)
    {
        return mp_int_init(z);
    }
    else
    {
        prec = s_round_prec(prec);
    }

    z->digits = s_alloc(prec);
    if (MP_DIGITS(z) == NULL)
        return MP_MEMORY;

    z->digits[0] = 0;
    z->used = 1;
    z->alloc = prec;
    z->sign = MP_ZPOS;

    return MP_OK;
}

mp_int_init_uvalue()

mp_result mp_int_init_uvalue	(	mp_int	z,
		mp_usmall	uvalue
	)

Initializes z to the specified unsigned value at default precision.

Definition at line 557 of file imath.c.

References mp_int_init_copy(), MP_VALUE_DIGITS, and s_ufake().

Referenced by mp_int_is_even().

{
    mpz_t       vtmp;
    mp_digit    vbuf[MP_VALUE_DIGITS(uvalue)];

    s_ufake(&vtmp, uvalue, vbuf);
    return mp_int_init_copy(z, &vtmp);
}

mp_int_init_value()

mp_result mp_int_init_value	(	mp_int	z,
		mp_small	value
	)

Initializes z to the specified signed value at default precision.

Definition at line 547 of file imath.c.

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

Referenced by mp_int_is_even().

{
    mpz_t       vtmp;
    mp_digit    vbuf[MP_VALUE_DIGITS(value)];

    s_fake(&vtmp, value, vbuf);
    return mp_int_init_copy(z, &vtmp);
}

mp_int_invmod()

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

Sets c to the multiplicative inverse of a modulo m, if it exists. The least non-negative representative of the congruence class is computed.

It returns MP_UNDEF if the inverse does not exist, or MP_RANGE if a == 0 or m <= 0.

Definition at line 1474 of file imath.c.

References assert, CLEANUP_TEMP, CMPZ(), DECLARE_TEMP, mp_int_compare_value(), mp_int_copy(), mp_int_egcd(), mp_int_mod(), mp_int_sub(), MP_NEG, MP_OK, MP_RANGE, MP_SIGN(), MP_UNDEF, REQUIRE, and TEMP.

Referenced by mp_int_mod_value(), and pgp_elgamal_decrypt().

{
    assert(a != NULL && m != NULL && c != NULL);

    if (CMPZ(a) == 0 || CMPZ(m) <= 0)
        return MP_RANGE;

    DECLARE_TEMP(2);

    REQUIRE(mp_int_egcd(a, m, TEMP(0), TEMP(1), NULL));

    if (mp_int_compare_value(TEMP(0), 1) != 0)
    {
        REQUIRE(MP_UNDEF);
    }

    /* It is first necessary to constrain the value to the proper range */
    REQUIRE(mp_int_mod(TEMP(1), m, TEMP(1)));

    /*
     * Now, if 'a' was originally negative, the value we have is actually the
     * magnitude of the negative representative; to get the positive value we
     * have to subtract from the modulus.  Otherwise, the value is okay as it
     * stands.
     */
    if (MP_SIGN(a) == MP_NEG)
    {
        REQUIRE(mp_int_sub(m, TEMP(1), c));
    }
    else
    {
        REQUIRE(mp_int_copy(TEMP(1), c));
    }

    CLEANUP_TEMP();
    return MP_OK;
}

mp_int_is_pow2()

int mp_int_is_pow2

(

mp_int

z

)

Returns k >= 0 such that z is 2^k, if such a k exists. If no such k exists, the function returns -1.

Definition at line 1750 of file imath.c.

References assert, and s_isp2().

Referenced by mp_int_mod_value().

{
    assert(z != NULL);

    return s_isp2(z);
}

mp_int_lcm()

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

Sets c to the least common multiple of a and b.

It returns MP_UNDEF if the LCM is undefined, such as for example if a and b are both zero.

Definition at line 1716 of file imath.c.

References assert, CLEANUP_TEMP, DECLARE_TEMP, mp_int_copy(), mp_int_div(), mp_int_gcd(), mp_int_mul(), MP_OK, REQUIRE, and TEMP.

Referenced by mp_int_mod_value().

{
    assert(a != NULL && b != NULL && c != NULL);

    /*
     * Since a * b = gcd(a, b) * lcm(a, b), we can compute lcm(a, b) = (a /
     * gcd(a, b)) * b.
     *
     * This formulation insures everything works even if the input variables
     * share space.
     */
    DECLARE_TEMP(1);
    REQUIRE(mp_int_gcd(a, b, TEMP(0)));
    REQUIRE(mp_int_div(a, TEMP(0), TEMP(0), NULL));
    REQUIRE(mp_int_mul(TEMP(0), b, TEMP(0)));
    REQUIRE(mp_int_copy(TEMP(0), c));

    CLEANUP_TEMP();
    return MP_OK;
}

mp_int_mod()

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

Sets c to the remainder of a / m. The remainder is pinned to 0 <= c < m.

Definition at line 1122 of file imath.c.

References CLEANUP_TEMP, CMPZ(), DECLARE_TEMP, mp_int_add(), mp_int_copy(), mp_int_div(), MP_OK, REQUIRE, and TEMP.

Referenced by mp_int_exptmod(), mp_int_exptmod_known(), mp_int_invmod(), mp_int_is_even(), and mp_modmul().

{
    DECLARE_TEMP(1);
    mp_int      out = (m == c) ? TEMP(0) : c;

    REQUIRE(mp_int_div(a, m, NULL, out));
    if (CMPZ(out) < 0)
    {
        REQUIRE(mp_int_add(out, m, c));
    }
    else
    {
        REQUIRE(mp_int_copy(out, c));
    }
    CLEANUP_TEMP();
    return MP_OK;
}

mp_int_mul()

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

Sets c to the product of a and b.

Definition at line 857 of file imath.c.

References assert, CLAMP(), default_precision, MAX(), MP_DIGITS(), mp_int_compare_zero(), mp_int_zero(), MP_MEMORY, MP_NEG, MP_OK, MP_SIGN(), MP_USED(), MP_ZPOS, s_alloc(), s_free(), s_kmul(), s_pad(), s_round_prec(), mpz_t::sign, mpz_t::used, and ZERO().

Referenced by mp_int_expt(), mp_int_expt_full(), mp_int_expt_value(), mp_int_is_even(), mp_int_lcm(), mp_int_mul_value(), and mp_modmul().

{
    assert(a != NULL && b != NULL && c != NULL);

    /* If either input is zero, we can shortcut multiplication */
    if (mp_int_compare_zero(a) == 0 || mp_int_compare_zero(b) == 0)
    {
        mp_int_zero(c);
        return MP_OK;
    }

    /* Output is positive if inputs have same sign, otherwise negative */
    mp_sign     osign = (MP_SIGN(a) == MP_SIGN(b)) ? MP_ZPOS : MP_NEG;

    /*
     * If the output is not identical to any of the inputs, we'll write the
     * results directly; otherwise, allocate a temporary space.
     */
    mp_size     ua = MP_USED(a);
    mp_size     ub = MP_USED(b);
    mp_size     osize = MAX(ua, ub);

    osize = 4 * ((osize + 1) / 2);

    mp_digit   *out;
    mp_size     p = 0;

    if (c == a || c == b)
    {
        p = MAX(s_round_prec(osize), default_precision);

        if ((out = s_alloc(p)) == NULL)
            return MP_MEMORY;
    }
    else
    {
        if (!s_pad(c, osize))
            return MP_MEMORY;

        out = MP_DIGITS(c);
    }
    ZERO(out, osize);

    if (!s_kmul(MP_DIGITS(a), MP_DIGITS(b), out, ua, ub))
        return MP_MEMORY;

    /*
     * If we allocated a new buffer, get rid of whatever memory c was already
     * using, and fix up its fields to reflect that.
     */
    if (out != MP_DIGITS(c))
    {
        if ((void *) MP_DIGITS(c) != (void *) c)
            s_free(MP_DIGITS(c));
        c->digits = out;
        c->alloc = p;
    }

    c->used = osize;            /* might not be true, but we'll fix it ... */
    CLAMP(c);                   /* ... right here */
    c->sign = osign;

    return MP_OK;
}

mp_int_mul_pow2()

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

Sets c to the product of a and 2^p2. Requires p2 >= 0.

Definition at line 934 of file imath.c.

References assert, mp_int_copy(), MP_MEMORY, MP_OK, and s_qmul().

Referenced by mp_int_is_even().

{
    assert(a != NULL && c != NULL && p2 >= 0);

    mp_result   res = mp_int_copy(a, c);

    if (res != MP_OK)
        return res;

    if (s_qmul(c, (mp_size) p2))
    {
        return MP_OK;
    }
    else
    {
        return MP_MEMORY;
    }
}

mp_int_mul_value()

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

Sets c to the product of a and value.

Definition at line 923 of file imath.c.

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

Referenced by mp_int_is_even(), and mp_int_root().

{
    mpz_t       vtmp;
    mp_digit    vbuf[MP_VALUE_DIGITS(value)];

    s_fake(&vtmp, value, vbuf);

    return mp_int_mul(a, &vtmp, c);
}

mp_int_multiply_threshold()

void mp_int_multiply_threshold

(

mp_size

ndigits

)

Sets the number of digits below which multiplication will use the standard quadratic "schoolbook" multiplcation algorithm rather than Karatsuba-Ofman. Requires ndigits >= sizeof(mp_word).

Definition at line 294 of file imath.c.

References assert, multiply_threshold, s_alloc(), s_free(), and s_pad().

{
    assert(thresh >= sizeof(mp_word));
    multiply_threshold = thresh;
}

mp_int_neg()

mp_result mp_int_neg	(	mp_int	a,
		mp_int	c
	)

Sets c to the additive inverse (negation) of a.

Definition at line 677 of file imath.c.

References assert, CMPZ(), mp_int_copy(), MP_OK, MP_SIGN(), and mpz_t::sign.

Referenced by mp_int_gcd(), mp_int_is_even(), and mp_int_root().

{
    assert(a != NULL && c != NULL);

    mp_result   res;

    if ((res = mp_int_copy(a, c)) != MP_OK)
        return res;

    if (CMPZ(c) != 0)
        c->sign = 1 - MP_SIGN(a);

    return MP_OK;
}

mp_int_read_binary()

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

Reads a 2's complement binary value from buf into z, where len is the length of the buffer. The contents of buf may be overwritten during processing, although they will be restored when the function returns.

Definition at line 2077 of file imath.c.

References assert, buf, i, MP_DIGIT_BIT, MP_DIGITS(), mp_int_zero(), MP_MEMORY, MP_NEG, MP_OK, MP_SIGN(), s_2comp(), s_pad(), s_qmul(), and mpz_t::sign.

Referenced by mp_int_sqrt().

{
    assert(z != NULL && buf != NULL && len > 0);

    /* Figure out how many digits are needed to represent this value */
    mp_size     need = ((len * CHAR_BIT) + (MP_DIGIT_BIT - 1)) / MP_DIGIT_BIT;

    if (!s_pad(z, need))
        return MP_MEMORY;

    mp_int_zero(z);

    /*
     * If the high-order bit is set, take the 2's complement before reading
     * the value (it will be restored afterward)
     */
    if (buf[0] >> (CHAR_BIT - 1))
    {
        z->sign = MP_NEG;
        s_2comp(buf, len);
    }

    mp_digit   *dz = MP_DIGITS(z);
    unsigned char *tmp = buf;

    for (int i = len; i > 0; --i, ++tmp)
    {
        s_qmul(z, (mp_size) CHAR_BIT);
        *dz |= *tmp;
    }

    /* Restore 2's complement if we took it before */
    if (MP_SIGN(z) == MP_NEG)
        s_2comp(buf, len);

    return MP_OK;
}

mp_int_read_cstring()

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

Reads a string of ASCII digits in the specified radix from the zero terminated str provided into z. For values of radix > 10, the letters A..Z or a..z are accepted. Letters are interpreted without respect to case.

Leading whitespace is ignored, and a leading + or - is interpreted as a sign flag. Processing stops when a NUL or any other character out of range for a digit in the given radix is encountered.

If the whole string was consumed, MP_OK is returned; otherwise MP_TRUNC. is returned. If end is not NULL, *end is set to point to the first unconsumed byte of the input string (the NUL byte if the whole string was consumed). This emulates the behavior of the standard C strtol() function.

Requires MP_MIN_RADIX <= radix <= MP_MAX_RADIX.

Definition at line 1970 of file imath.c.

References assert, CLAMP(), CMPZ(), mpz_t::digits, MP_MAX_RADIX, MP_MEMORY, MP_MIN_RADIX, MP_NEG, MP_OK, MP_TRUNC, MP_ZPOS, s_ch2val(), s_dadd(), s_dmul(), s_inlen(), s_pad(), mpz_t::sign, generate_unaccent_rules::str, unconstify, and mpz_t::used.

Referenced by mp_int_read_string(), and mp_int_sqrt().

{
    assert(z != NULL && str != NULL);
    assert(radix >= MP_MIN_RADIX && radix <= MP_MAX_RADIX);

    /* Skip leading whitespace */
    while (isspace((unsigned char) *str))
        ++str;

    /* Handle leading sign tag (+/-, positive default) */
    switch (*str)
    {
        case '-':
            z->sign = MP_NEG;
            ++str;
            break;
        case '+':
            ++str;              /* fallthrough */
        default:
            z->sign = MP_ZPOS;
            break;
    }

    /* Skip leading zeroes */
    int         ch;

    while ((ch = s_ch2val(*str, radix)) == 0)
        ++str;

    /* Make sure there is enough space for the value */
    if (!s_pad(z, s_inlen(strlen(str), radix)))
        return MP_MEMORY;

    z->used = 1;
    z->digits[0] = 0;

    while (*str != '\0' && ((ch = s_ch2val(*str, radix)) >= 0))
    {
        s_dmul(z, (mp_digit) radix);
        s_dadd(z, (mp_digit) ch);
        ++str;
    }

    CLAMP(z);

    /* Override sign for zero, even if negative specified. */
    if (CMPZ(z) == 0)
        z->sign = MP_ZPOS;

    if (end != NULL)
        *end = unconstify(char *, str);

    /*
     * Return a truncation error if the string has unprocessed characters
     * remaining, so the caller can tell if the whole string was done
     */
    if (*str != '\0')
    {
        return MP_TRUNC;
    }
    else
    {
        return MP_OK;
    }
}

mp_int_read_string()

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

Reads a string of ASCII digits in the specified radix from the zero terminated str provided into z. For values of radix > 10, the letters A..Z or a..z are accepted. Letters are interpreted without respect to case.

Leading whitespace is ignored, and a leading + or - is interpreted as a sign flag. Processing stops when a NUL or any other character out of range for a digit in the given radix is encountered.

If the whole string was consumed, MP_OK is returned; otherwise MP_TRUNC. is returned.

Requires MP_MIN_RADIX <= radix <= MP_MAX_RADIX.

Definition at line 1964 of file imath.c.

References mp_int_read_cstring().

Referenced by mp_int_sqrt().

{
    return mp_int_read_cstring(z, radix, str, NULL);
}

mp_int_read_unsigned()

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

Reads an unsigned binary value from buf into z, where len is the length of the buffer. The contents of buf are not modified during processing.

Definition at line 2147 of file imath.c.

References assert, buf, i, MP_DIGIT_BIT, MP_DIGITS(), mp_int_zero(), MP_MEMORY, MP_OK, s_pad(), and s_qmul().

Referenced by mp_int_sqrt(), mp_px_rand(), and mpi_to_bn().

{
    assert(z != NULL && buf != NULL && len > 0);

    /* Figure out how many digits are needed to represent this value */
    mp_size     need = ((len * CHAR_BIT) + (MP_DIGIT_BIT - 1)) / MP_DIGIT_BIT;

    if (!s_pad(z, need))
        return MP_MEMORY;

    mp_int_zero(z);

    unsigned char *tmp = buf;

    for (int i = len; i > 0; --i, ++tmp)
    {
        (void) s_qmul(z, CHAR_BIT);
        *MP_DIGITS(z) |= *tmp;
    }

    return MP_OK;
}

mp_int_redux_const()

mp_result mp_int_redux_const	(	mp_int	m,
		mp_int	c
	)

Sets c to the reduction constant for Barrett reduction by modulus m. Requires that c and m point to distinct locations.

Definition at line 1466 of file imath.c.

References assert, and s_brmu().

Referenced by mp_int_mod_value().

{
    assert(m != NULL && c != NULL && m != c);

    return s_brmu(c, m);
}

mp_int_root()

mp_result mp_int_root	(	mp_int	a,
		mp_small	b,
		mp_int	c
	)

Sets c to the greatest integer not less than the bth root of a, using Newton's root-finding algorithm. It returns MP_UNDEF if a < 0 and b is even.

Definition at line 1762 of file imath.c.

References assert, CLEANUP_TEMP, DECLARE_TEMP, mp_int_compare_unsigned(), mp_int_copy(), mp_int_div(), mp_int_expt(), mp_int_mul_value(), mp_int_neg(), mp_int_sub(), mp_int_sub_value(), MP_NEG, MP_OK, MP_SIGN(), MP_UNDEF, MP_ZPOS, REQUIRE, and TEMP.

Referenced by mp_int_mod_value(), and mp_int_sqrt().

{
    assert(a != NULL && c != NULL && b > 0);

    if (b == 1)
    {
        return mp_int_copy(a, c);
    }
    bool        flips = false;

    if (MP_SIGN(a) == MP_NEG)
    {
        if (b % 2 == 0)
        {
            return MP_UNDEF;    /* root does not exist for negative a with
                                 * even b */
        }
        else
        {
            flips = true;
        }
    }

    DECLARE_TEMP(5);
    REQUIRE(mp_int_copy(a, TEMP(0)));
    REQUIRE(mp_int_copy(a, TEMP(1)));
    TEMP(0)->sign = MP_ZPOS;
    TEMP(1)->sign = MP_ZPOS;

    for (;;)
    {
        REQUIRE(mp_int_expt(TEMP(1), b, TEMP(2)));

        if (mp_int_compare_unsigned(TEMP(2), TEMP(0)) <= 0)
            break;

        REQUIRE(mp_int_sub(TEMP(2), TEMP(0), TEMP(2)));
        REQUIRE(mp_int_expt(TEMP(1), b - 1, TEMP(3)));
        REQUIRE(mp_int_mul_value(TEMP(3), b, TEMP(3)));
        REQUIRE(mp_int_div(TEMP(2), TEMP(3), TEMP(4), NULL));
        REQUIRE(mp_int_sub(TEMP(1), TEMP(4), TEMP(4)));

        if (mp_int_compare_unsigned(TEMP(1), TEMP(4)) == 0)
        {
            REQUIRE(mp_int_sub_value(TEMP(4), 1, TEMP(4)));
        }
        REQUIRE(mp_int_copy(TEMP(4), TEMP(1)));
    }

    REQUIRE(mp_int_copy(TEMP(1), c));

    /* If the original value of a was negative, flip the output sign. */
    if (flips)
        (void) mp_int_neg(c, c);    /* cannot fail */

    CLEANUP_TEMP();
    return MP_OK;
}

mp_int_set_uvalue()

mp_result mp_int_set_uvalue	(	mp_int	z,
		mp_usmall	uvalue
	)

Sets z to the value of the specified unsigned value.

Definition at line 577 of file imath.c.

References mp_int_copy(), MP_VALUE_DIGITS, and s_ufake().

Referenced by mp_int_is_even().

{
    mpz_t       vtmp;
    mp_digit    vbuf[MP_VALUE_DIGITS(uvalue)];

    s_ufake(&vtmp, uvalue, vbuf);
    return mp_int_copy(&vtmp, z);
}

mp_int_set_value()

mp_result mp_int_set_value	(	mp_int	z,
		mp_small	value
	)

Sets z to the value of the specified signed value.

Definition at line 567 of file imath.c.

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

Referenced by mp_int_egcd(), mp_int_expt(), mp_int_expt_full(), mp_int_expt_value(), mp_int_is_even(), s_embar(), and s_udiv_knuth().

{
    mpz_t       vtmp;
    mp_digit    vbuf[MP_VALUE_DIGITS(value)];

    s_fake(&vtmp, value, vbuf);
    return mp_int_copy(&vtmp, z);
}

mp_int_sqr()

mp_result mp_int_sqr	(	mp_int	a,
		mp_int	c
	)

Sets c to the square of a.

Definition at line 954 of file imath.c.

References assert, CLAMP(), default_precision, MAX(), MP_DIGITS(), MP_MEMORY, MP_OK, MP_USED(), MP_ZPOS, s_alloc(), s_free(), s_ksqr(), s_pad(), s_round_prec(), mpz_t::sign, mpz_t::used, and ZERO().

Referenced by mp_int_expt(), mp_int_expt_full(), mp_int_expt_value(), and mp_int_is_even().

{
    assert(a != NULL && c != NULL);

    /* Get a temporary buffer big enough to hold the result */
    mp_size     osize = (mp_size) 4 * ((MP_USED(a) + 1) / 2);
    mp_size     p = 0;
    mp_digit   *out;

    if (a == c)
    {
        p = s_round_prec(osize);
        p = MAX(p, default_precision);

        if ((out = s_alloc(p)) == NULL)
            return MP_MEMORY;
    }
    else
    {
        if (!s_pad(c, osize))
            return MP_MEMORY;

        out = MP_DIGITS(c);
    }
    ZERO(out, osize);

    s_ksqr(MP_DIGITS(a), out, MP_USED(a));

    /*
     * Get rid of whatever memory c was already using, and fix up its fields
     * to reflect the new digit array it's using
     */
    if (out != MP_DIGITS(c))
    {
        if ((void *) MP_DIGITS(c) != (void *) c)
            s_free(MP_DIGITS(c));
        c->digits = out;
        c->alloc = p;
    }

    c->used = osize;            /* might not be true, but we'll fix it ... */
    CLAMP(c);                   /* ... right here */
    c->sign = MP_ZPOS;

    return MP_OK;
}

mp_int_string_len()

mp_result mp_int_string_len	(	mp_int	z,
		mp_size	radix
	)

Reports the minimum number of characters required to represent z as a zero-terminated string in the given radix. Requires MP_MIN_RADIX <= radix <= MP_MAX_RADIX.

Definition at line 1948 of file imath.c.

References assert, MP_MAX_RADIX, MP_MIN_RADIX, MP_NEG, MP_SIGN(), and s_outlen().

Referenced by mp_int_sqrt().

{
    assert(z != NULL);
    assert(radix >= MP_MIN_RADIX && radix <= MP_MAX_RADIX);

    int         len = s_outlen(z, radix) + 1;   /* for terminator */

    /* Allow for sign marker on negatives */
    if (MP_SIGN(z) == MP_NEG)
        len += 1;

    return len;
}

mp_int_sub()

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

Sets c to the difference of a less b.

Definition at line 778 of file imath.c.

References assert, CLAMP(), cmp(), mpz_t::digits, MAX(), MP_DIGITS(), MP_MEMORY, MP_NEG, MP_OK, MP_SIGN(), MP_USED(), MP_ZPOS, s_pad(), s_uadd(), s_ucmp(), s_usub(), mpz_t::sign, and mpz_t::used.

Referenced by mp_int_egcd(), mp_int_gcd(), mp_int_invmod(), mp_int_is_even(), mp_int_root(), mp_int_sub_value(), and s_reduce().

{
    assert(a != NULL && b != NULL && c != NULL);

    mp_size     ua = MP_USED(a);
    mp_size     ub = MP_USED(b);
    mp_size     max = MAX(ua, ub);

    if (MP_SIGN(a) != MP_SIGN(b))
    {
        /* Different signs -- add magnitudes and keep sign of a */
        if (!s_pad(c, max))
            return MP_MEMORY;

        mp_digit    carry = s_uadd(MP_DIGITS(a), MP_DIGITS(b), MP_DIGITS(c), ua, ub);
        mp_size     uc = max;

        if (carry)
        {
            if (!s_pad(c, max + 1))
                return MP_MEMORY;

            c->digits[max] = carry;
            ++uc;
        }

        c->used = uc;
        c->sign = a->sign;

    }
    else
    {
        /* Same signs -- subtract magnitudes */
        if (!s_pad(c, max))
            return MP_MEMORY;
        mp_int      x,
                    y;
        mp_sign     osign;

        int         cmp = s_ucmp(a, b);

        if (cmp >= 0)
        {
            x = a;
            y = b;
            osign = MP_ZPOS;
        }
        else
        {
            x = b;
            y = a;
            osign = MP_NEG;
        }

        if (MP_SIGN(a) == MP_NEG && cmp != 0)
            osign = 1 - osign;

        s_usub(MP_DIGITS(x), MP_DIGITS(y), MP_DIGITS(c), MP_USED(x), MP_USED(y));
        c->used = x->used;
        CLAMP(c);

        c->sign = osign;
    }

    return MP_OK;
}

mp_int_sub_value()

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

Sets c to the difference of a less value.

Definition at line 846 of file imath.c.

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

Referenced by mp_int_is_even(), and mp_int_root().

{
    mpz_t       vtmp;
    mp_digit    vbuf[MP_VALUE_DIGITS(value)];

    s_fake(&vtmp, value, vbuf);

    return mp_int_sub(a, &vtmp, c);
}

mp_int_swap()

void mp_int_swap	(	mp_int	a,
		mp_int	c
	)

Swaps the values and storage between a and c.

Definition at line 636 of file imath.c.

References mpz_t::digits, MP_DIGITS(), and mpz_t::single.

Referenced by mp_int_is_even().

{
    if (a != c)
    {
        mpz_t       tmp = *a;

        *a = *c;
        *c = tmp;

        if (MP_DIGITS(a) == &(c->single))
            a->digits = &(a->single);
        if (MP_DIGITS(c) == &(a->single))
            c->digits = &(c->single);
    }
}

mp_int_to_binary()

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

Converts z to 2's complement binary, writing at most limit bytes into the given buf. Returns MP_TRUNC if the buffer limit was too small to contain the whole value. If this occurs, the contents of buf will be effectively garbage, as the function uses the buffer as scratch space.

The binary representation of z is in base-256 with digits ordered from most significant to least significant (network byte ordering). The high-order bit of the first byte is set for negative values, clear for non-negative values.

As a result, non-negative values will be padded with a leading zero byte if the high-order byte of the base-256 magnitude is set. This extra byte is accounted for by the mp_int_binary_len() function.

Definition at line 2061 of file imath.c.

References assert, MP_NEG, MP_SIGN(), s_2comp(), and s_tobin().

Referenced by mp_int_sqrt().

{
    static const int PAD_FOR_2C = 1;

    assert(z != NULL && buf != NULL);

    int         limpos = limit;
    mp_result   res = s_tobin(z, buf, &limpos, PAD_FOR_2C);

    if (MP_SIGN(z) == MP_NEG)
        s_2comp(buf, limpos);

    return res;
}

mp_int_to_int()

mp_result mp_int_to_int	(	mp_int	z,
		mp_small *	out
	)

Returns MP_OK if z is representable as mp_small, else MP_RANGE. If out is not NULL, *out is set to the value of z when MP_OK.

Definition at line 1822 of file imath.c.

References assert, MP_DIGIT_BIT, MP_DIGITS(), mp_int_compare_value(), MP_NEG, MP_OK, MP_RANGE, MP_SIGN(), MP_SMALL_MAX, MP_SMALL_MIN, MP_USED(), and MP_ZPOS.

Referenced by mp_int_div_value(), and mp_int_sqrt().

{
    assert(z != NULL);

    /* Make sure the value is representable as a small integer */
    mp_sign     sz = MP_SIGN(z);

    if ((sz == MP_ZPOS && mp_int_compare_value(z, MP_SMALL_MAX) > 0) ||
        mp_int_compare_value(z, MP_SMALL_MIN) < 0)
    {
        return MP_RANGE;
    }

    mp_usmall   uz = MP_USED(z);
    mp_digit   *dz = MP_DIGITS(z) + uz - 1;
    mp_small    uv = 0;

    while (uz > 0)
    {
        uv <<= MP_DIGIT_BIT / 2;
        uv = (uv << (MP_DIGIT_BIT / 2)) | *dz--;
        --uz;
    }

    if (out)
        *out = (mp_small) ((sz == MP_NEG) ? -uv : uv);

    return MP_OK;
}

mp_int_to_string()

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

Converts z to a zero-terminated string of characters in the specified radix, writing at most limit characters to str including the terminating NUL value. A leading - is used to indicate a negative value.

Returns MP_TRUNC if limit was to small to write all of z. Requires MP_MIN_RADIX <= radix <= MP_MAX_RADIX.

Definition at line 1883 of file imath.c.

References assert, cmp(), CMPZ(), mp_int_clear(), mp_int_init_copy(), MP_MAX_RADIX, MP_MIN_RADIX, MP_NEG, MP_OK, MP_SIGN(), MP_TRUNC, s_ddiv(), s_val2ch(), and generate_unaccent_rules::str.

Referenced by mp_int_sqrt().

{
    assert(z != NULL && str != NULL && limit >= 2);
    assert(radix >= MP_MIN_RADIX && radix <= MP_MAX_RADIX);

    int         cmp = 0;

    if (CMPZ(z) == 0)
    {
        *str++ = s_val2ch(0, 1);
    }
    else
    {
        mp_result   res;
        mpz_t       tmp;
        char       *h,
                   *t;

        if ((res = mp_int_init_copy(&tmp, z)) != MP_OK)
            return res;

        if (MP_SIGN(z) == MP_NEG)
        {
            *str++ = '-';
            --limit;
        }
        h = str;

        /* Generate digits in reverse order until finished or limit reached */
        for ( /* */ ; limit > 0; --limit)
        {
            mp_digit    d;

            if ((cmp = CMPZ(&tmp)) == 0)
                break;

            d = s_ddiv(&tmp, (mp_digit) radix);
            *str++ = s_val2ch(d, 1);
        }
        t = str - 1;

        /* Put digits back in correct output order */
        while (h < t)
        {
            char        tc = *h;

            *h++ = *t;
            *t-- = tc;
        }

        mp_int_clear(&tmp);
    }

    *str = '\0';
    if (cmp == 0)
    {
        return MP_OK;
    }
    else
    {
        return MP_TRUNC;
    }
}

mp_int_to_uint()

mp_result mp_int_to_uint	(	mp_int	z,
		mp_usmall *	out
	)

Returns MP_OK if z is representable as mp_usmall, or MP_RANGE. If out is not NULL, *out is set to the value of z when MP_OK.

Definition at line 1853 of file imath.c.

References assert, MP_DIGIT_BIT, MP_DIGITS(), mp_int_compare_uvalue(), MP_NEG, MP_OK, MP_RANGE, MP_SIGN(), MP_USED(), and MP_USMALL_MAX.

Referenced by mp_int_sqrt().

{
    assert(z != NULL);

    /* Make sure the value is representable as an unsigned small integer */
    mp_size     sz = MP_SIGN(z);

    if (sz == MP_NEG || mp_int_compare_uvalue(z, MP_USMALL_MAX) > 0)
    {
        return MP_RANGE;
    }

    mp_size     uz = MP_USED(z);
    mp_digit   *dz = MP_DIGITS(z) + uz - 1;
    mp_usmall   uv = 0;

    while (uz > 0)
    {
        uv <<= MP_DIGIT_BIT / 2;
        uv = (uv << (MP_DIGIT_BIT / 2)) | *dz--;
        --uz;
    }

    if (out)
        *out = uv;

    return MP_OK;
}

mp_int_to_unsigned()

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

Converts the magnitude of z to unsigned binary, writing at most limit bytes into the given buf. The sign of z is ignored, but z is not modified. Returns MP_TRUNC if the buffer limit was too small to contain the whole value. If this occurs, the contents of buf will be effectively garbage, as the function uses the buffer as scratch space during conversion.

The binary representation of z is in base-256 with digits ordered from most significant to least significant (network byte ordering).

Definition at line 2137 of file imath.c.

References assert, and s_tobin().

Referenced by bn_to_mpi(), and mp_int_sqrt().

{
    static const int NO_PADDING = 0;

    assert(z != NULL && buf != NULL);

    return s_tobin(z, buf, &limit, NO_PADDING);
}

mp_int_unsigned_len()

mp_result mp_int_unsigned_len

(

mp_int

z

)

Returns the number of bytes required to represent z as an unsigned binary value in base 256.

Definition at line 2171 of file imath.c.

References generate_unaccent_rules::bytes(), and mp_int_count_bits().

Referenced by mp_int_binary_len(), and mp_int_sqrt().

{
    mp_result   res = mp_int_count_bits(z);

    if (res <= 0)
        return res;

    int         bytes = (res + (CHAR_BIT - 1)) / CHAR_BIT;

    return bytes;
}

mp_int_zero()

void mp_int_zero

(

mp_int

z

)

Sets z to zero. The allocated storage of z is not changed.

Definition at line 653 of file imath.c.

References assert, mpz_t::digits, MP_ZPOS, mpz_t::sign, and mpz_t::used.

Referenced by mp_int_add(), mp_int_div(), mp_int_egcd(), mp_int_is_even(), mp_int_mul(), mp_int_read_binary(), mp_int_read_unsigned(), and s_qdiv().

{
    assert(z != NULL);

    z->digits[0] = 0;
    z->used = 1;
    z->sign = MP_ZPOS;
}

REV()

static void REV ( unsigned char *  A, int  N  )

inlinestatic

Definition at line 152 of file imath.c.

Referenced by s_tobin().

{
    unsigned char *u_ = A;
    unsigned char *v_ = u_ + N - 1;

    while (u_ < v_)
    {
        unsigned char xch = *u_;

        *u_++ = *v_;
        *v_-- = xch;
    }
}

s_2comp()

static void s_2comp ( unsigned char *  buf, int  len  )

static

Definition at line 3519 of file imath.c.

References i.

Referenced by GROW(), mp_int_read_binary(), and mp_int_to_binary().

{
    unsigned short s = 1;

    for (int i = len - 1; i >= 0; --i)
    {
        unsigned char c = ~buf[i];

        s = c + s;
        c = s & UCHAR_MAX;
        s >>= CHAR_BIT;

        buf[i] = c;
    }

    /* last carry out is ignored */
}

s_2expt()

static int s_2expt ( mp_int  z, mp_small  k  )

static

Definition at line 3038 of file imath.c.

References MP_DIGIT_BIT, MP_DIGITS(), s_pad(), mpz_t::used, and ZERO().

Referenced by GROW(), and s_brmu().

{
    mp_size     ndig,
                rest;
    mp_digit   *dz;

    ndig = (k + MP_DIGIT_BIT) / MP_DIGIT_BIT;
    rest = k % MP_DIGIT_BIT;

    if (!s_pad(z, ndig))
        return 0;

    dz = MP_DIGITS(z);
    ZERO(dz, ndig);
    *(dz + ndig - 1) = (1u << rest);
    z->used = ndig;

    return 1;
}

s_alloc()

static mp_digit * s_alloc ( mp_size  num )

static

Definition at line 2213 of file imath.c.

References assert, fill(), and palloc().

Referenced by mp_int_init_size(), mp_int_mul(), mp_int_multiply_threshold(), mp_int_sqr(), s_kmul(), s_ksqr(), s_pad(), and s_realloc().

{
    mp_digit   *out = palloc(num * sizeof(mp_digit));

    assert(out != NULL);

#if IMATH_DEBUG
    for (mp_size ix = 0; ix < num; ++ix)
        out[ix] = fill;
#endif
    return out;
}

s_brmu()

static mp_result s_brmu ( mp_int  z, mp_int  m  )

static

Definition at line 3081 of file imath.c.

References MP_DIGIT_BIT, mp_int_div(), MP_MEMORY, MP_USED(), s_2expt(), and s_pad().

Referenced by GROW(), mp_int_exptmod(), and mp_int_redux_const().

{
    mp_size     um = MP_USED(m) * 2;

    if (!s_pad(z, um))
        return MP_MEMORY;

    s_2expt(z, MP_DIGIT_BIT * um);
    return mp_int_div(z, m, z, NULL);
}

s_cdig()

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

static

Definition at line 2301 of file imath.c.

Referenced by GROW(), and s_ucmp().

{
    mp_digit   *dat = da + len - 1,
               *dbt = db + len - 1;

    for ( /* */ ; len != 0; --len, --dat, --dbt)
    {
        if (*dat > *dbt)
        {
            return 1;
        }
        else if (*dat < *dbt)
        {
            return -1;
        }
    }

    return 0;
}

s_ch2val()

static int s_ch2val ( char  c, int  r  )

static

Definition at line 3474 of file imath.c.

Referenced by GROW(), and mp_int_read_cstring().

{
    int         out;

    /*
     * In some locales, isalpha() accepts characters outside the range A-Z,
     * producing out<0 or out>=36.  The "out >= r" check will always catch
     * out>=36.  Though nothing explicitly catches out<0, our caller reacts
     * the same way to every negative return value.
     */
    if (isdigit((unsigned char) c))
        out = c - '0';
    else if (r > 10 && isalpha((unsigned char) c))
        out = toupper((unsigned char) c) - 'A' + 10;
    else
        return -1;

    return (out >= r) ? -1 : out;
}

s_dadd()

static void s_dadd ( mp_int  a, mp_digit  b  )

static

Definition at line 2707 of file imath.c.

References LOWER_HALF(), MP_DIGITS(), MP_USED(), UPPER_HALF(), and mpz_t::used.

Referenced by GROW(), and mp_int_read_cstring().

{
    mp_word     w = 0;
    mp_digit   *da = MP_DIGITS(a);
    mp_size     ua = MP_USED(a);

    w = (mp_word) *da + b;
    *da++ = LOWER_HALF(w);
    w = UPPER_HALF(w);

    for (ua -= 1; ua > 0; --ua, ++da)
    {
        w = (mp_word) *da + w;

        *da = LOWER_HALF(w);
        w = UPPER_HALF(w);
    }

    if (w)
    {
        *da = (mp_digit) w;
        a->used += 1;
    }
}

s_dbmul()

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

static

Definition at line 2755 of file imath.c.

References LOWER_HALF(), and UPPER_HALF().

Referenced by GROW(), and s_udiv_knuth().

{
    mp_word     w = 0;

    while (size_a > 0)
    {
        w = (mp_word) *da++ * (mp_word) b + w;

        *dc++ = LOWER_HALF(w);
        w = UPPER_HALF(w);
        --size_a;
    }

    if (w)
        *dc = LOWER_HALF(w);
}

s_ddiv()

static mp_digit s_ddiv ( mp_int  a, mp_digit  b  )

static

Definition at line 2773 of file imath.c.

References CLAMP(), MP_DIGIT_BIT, MP_DIGITS(), and MP_USED().

Referenced by GROW(), mp_int_to_string(), and s_udiv_knuth().

{
    mp_word     w = 0,
                qdigit;
    mp_size     ua = MP_USED(a);
    mp_digit   *da = MP_DIGITS(a) + ua - 1;

    for ( /* */ ; ua > 0; --ua, --da)
    {
        w = (w << MP_DIGIT_BIT) | *da;

        if (w >= b)
        {
            qdigit = w / b;
            w = w % b;
        }
        else
        {
            qdigit = 0;
        }

        *da = (mp_digit) qdigit;
    }

    CLAMP(a);
    return (mp_digit) w;
}

s_dmul()

static void s_dmul ( mp_int  a, mp_digit  b  )

static

Definition at line 2733 of file imath.c.

References LOWER_HALF(), MP_DIGITS(), MP_USED(), UPPER_HALF(), and mpz_t::used.

Referenced by GROW(), and mp_int_read_cstring().

{
    mp_word     w = 0;
    mp_digit   *da = MP_DIGITS(a);
    mp_size     ua = MP_USED(a);

    while (ua > 0)
    {
        w = (mp_word) *da * b + w;
        *da++ = LOWER_HALF(w);
        w = UPPER_HALF(w);
        --ua;
    }

    if (w)
    {
        *da = (mp_digit) w;
        a->used += 1;
    }
}

s_dp2k()

static int s_dp2k ( mp_int  z )

static

Definition at line 2984 of file imath.c.

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

Referenced by GROW(), mp_int_egcd(), and mp_int_gcd().

{
    int         k = 0;
    mp_digit   *dp = MP_DIGITS(z),
                d;

    if (MP_USED(z) == 1 && *dp == 0)
        return 1;

    while (*dp == 0)
    {
        k += MP_DIGIT_BIT;
        ++dp;
    }

    d = *dp;
    while ((d & 1) == 0)
    {
        d >>= 1;
        ++k;
    }

    return k;
}

s_embar()

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

static

Definition at line 3149 of file imath.c.

References assert, CLEANUP_TEMP, DECLARE_TEMP, digits, GROW(), i, MP_DIGIT_BIT, MP_DIGITS(), mp_int_copy(), mp_int_set_value(), MP_MEMORY, MP_OK, MP_SIGN(), MP_USED(), MP_ZPOS, REQUIRE, s_reduce(), TEMP, UMUL(), USQR(), and ZERO().

Referenced by GROW(), mp_int_exptmod(), and mp_int_exptmod_known().

{
    mp_digit    umu = MP_USED(mu);
    mp_digit   *db = MP_DIGITS(b);
    mp_digit   *dbt = db + MP_USED(b) - 1;

    DECLARE_TEMP(3);
    REQUIRE(GROW(TEMP(0), 4 * umu));
    REQUIRE(GROW(TEMP(1), 4 * umu));
    REQUIRE(GROW(TEMP(2), 4 * umu));
    ZERO(TEMP(0)->digits, TEMP(0)->alloc);
    ZERO(TEMP(1)->digits, TEMP(1)->alloc);
    ZERO(TEMP(2)->digits, TEMP(2)->alloc);

    (void) mp_int_set_value(c, 1);

    /* Take care of low-order digits */
    while (db < dbt)
    {
        mp_digit    d = *db;

        for (int i = MP_DIGIT_BIT; i > 0; --i, d >>= 1)
        {
            if (d & 1)
            {
                /* The use of a second temporary avoids allocation */
                UMUL(c, a, TEMP(0));
                if (!s_reduce(TEMP(0), m, mu, TEMP(1), TEMP(2)))
                {
                    REQUIRE(MP_MEMORY);
                }
                mp_int_copy(TEMP(0), c);
            }

            USQR(a, TEMP(0));
            assert(MP_SIGN(TEMP(0)) == MP_ZPOS);
            if (!s_reduce(TEMP(0), m, mu, TEMP(1), TEMP(2)))
            {
                REQUIRE(MP_MEMORY);
            }
            assert(MP_SIGN(TEMP(0)) == MP_ZPOS);
            mp_int_copy(TEMP(0), a);
        }

        ++db;
    }

    /* Take care of highest-order digit */
    mp_digit    d = *dbt;

    for (;;)
    {
        if (d & 1)
        {
            UMUL(c, a, TEMP(0));
            if (!s_reduce(TEMP(0), m, mu, TEMP(1), TEMP(2)))
            {
                REQUIRE(MP_MEMORY);
            }
            mp_int_copy(TEMP(0), c);
        }

        d >>= 1;
        if (!d)
            break;

        USQR(a, TEMP(0));
        if (!s_reduce(TEMP(0), m, mu, TEMP(1), TEMP(2)))
        {
            REQUIRE(MP_MEMORY);
        }
        (void) mp_int_copy(TEMP(0), a);
    }

    CLEANUP_TEMP();
    return MP_OK;
}

s_fake()

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

static

Definition at line 2280 of file imath.c.

References MP_NEG, s_ufake(), mpz_t::sign, and value.

Referenced by GROW(), mp_int_add_value(), mp_int_div_value(), mp_int_exptmod_bvalue(), mp_int_exptmod_evalue(), mp_int_init_value(), mp_int_mul_value(), mp_int_set_value(), and mp_int_sub_value().

{
    mp_usmall   uv = (mp_usmall) (value < 0) ? -value : value;

    s_ufake(z, uv, vbuf);
    if (value < 0)
        z->sign = MP_NEG;
}

s_free()

static void s_free ( void *  ptr )

static

Definition at line 2247 of file imath.c.

References pfree().

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

{
    pfree(ptr);
}

s_inlen()

static mp_size s_inlen ( int  len, mp_size  r  )

static

Definition at line 3465 of file imath.c.

References MP_DIGIT_BIT, and s_log2.

Referenced by GROW(), and mp_int_read_cstring().

{
    double      raw = (double) len / s_log2[r];
    mp_size     bits = (mp_size) (raw + 0.5);

    return (mp_size) ((bits + (MP_DIGIT_BIT - 1)) / MP_DIGIT_BIT) + 1;
}

s_isp2()

static int s_isp2 ( mp_int  z )

static

Definition at line 3010 of file imath.c.

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

Referenced by GROW(), mp_int_div(), and mp_int_is_pow2().

{
    mp_size     uz = MP_USED(z),
                k = 0;
    mp_digit   *dz = MP_DIGITS(z),
                d;

    while (uz > 1)
    {
        if (*dz++ != 0)
            return -1;
        k += MP_DIGIT_BIT;
        --uz;
    }

    d = *dz;
    while (d > 1)
    {
        if (d & 1)
            return -1;
        ++k;
        d >>= 1;
    }

    return (int) k;
}

s_kmul()

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 2458 of file imath.c.

References assert, COPY(), multiply_threshold, s_alloc(), s_free(), s_uadd(), s_umul(), s_usub(), SWAP, and ZERO().

Referenced by GROW(), mp_int_mul(), s_ksqr(), and UMUL().

{
    mp_size     bot_size;

    /* Make sure b is the smaller of the two input values */
    if (size_b > size_a)
    {
        SWAP(mp_digit *, da, db);
        SWAP(mp_size, size_a, size_b);
    }

    /*
     * Insure that the bottom is the larger half in an odd-length split; the
     * code below relies on this being true.
     */
    bot_size = (size_a + 1) / 2;

    /*
     * If the values are big enough to bother with recursion, use the
     * Karatsuba algorithm to compute the product; otherwise use the normal
     * multiplication algorithm
     */
    if (multiply_threshold && size_a >= multiply_threshold && size_b > bot_size)
    {
        mp_digit   *t1,
                   *t2,
                   *t3,
                    carry;

        mp_digit   *a_top = da + bot_size;
        mp_digit   *b_top = db + bot_size;

        mp_size     at_size = size_a - bot_size;
        mp_size     bt_size = size_b - bot_size;
        mp_size     buf_size = 2 * bot_size;

        /*
         * Do a single allocation for all three temporary buffers needed; each
         * buffer must be big enough to hold the product of two bottom halves,
         * and one buffer needs space for the completed product; twice the
         * space is plenty.
         */
        if ((t1 = s_alloc(4 * buf_size)) == NULL)
            return 0;
        t2 = t1 + buf_size;
        t3 = t2 + buf_size;
        ZERO(t1, 4 * buf_size);

        /*
         * t1 and t2 are initially used as temporaries to compute the inner
         * product (a1 + a0)(b1 + b0) = a1b1 + a1b0 + a0b1 + a0b0
         */
        carry = s_uadd(da, a_top, t1, bot_size, at_size);   /* t1 = a1 + a0 */
        t1[bot_size] = carry;

        carry = s_uadd(db, b_top, t2, bot_size, bt_size);   /* t2 = b1 + b0 */
        t2[bot_size] = carry;

        (void) s_kmul(t1, t2, t3, bot_size + 1, bot_size + 1);  /* t3 = t1 * t2 */

        /*
         * Now we'll get t1 = a0b0 and t2 = a1b1, and subtract them out so
         * that we're left with only the pieces we want:  t3 = a1b0 + a0b1
         */
        ZERO(t1, buf_size);
        ZERO(t2, buf_size);
        (void) s_kmul(da, db, t1, bot_size, bot_size);  /* t1 = a0 * b0 */
        (void) s_kmul(a_top, b_top, t2, at_size, bt_size);  /* t2 = a1 * b1 */

        /* Subtract out t1 and t2 to get the inner product */
        s_usub(t3, t1, t3, buf_size + 2, buf_size);
        s_usub(t3, t2, t3, buf_size + 2, buf_size);

        /* Assemble the output value */
        COPY(t1, dc, buf_size);
        carry = s_uadd(t3, dc + bot_size, dc + bot_size, buf_size + 1, buf_size);
        assert(carry == 0);

        carry =
            s_uadd(t2, dc + 2 * bot_size, dc + 2 * bot_size, buf_size, buf_size);
        assert(carry == 0);

        s_free(t1);             /* note t2 and t3 are just internal pointers
                                 * to t1 */
    }
    else
    {
        s_umul(da, db, dc, size_a, size_b);
    }

    return 1;
}

s_ksqr()

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

static

Definition at line 2582 of file imath.c.

References assert, COPY(), i, LOWER_HALF(), multiply_threshold, PG_USED_FOR_ASSERTS_ONLY, s_alloc(), s_free(), s_kmul(), s_uadd(), s_usqr(), UPPER_HALF(), and ZERO().

Referenced by GROW(), mp_int_sqr(), and USQR().

{
    if (multiply_threshold && size_a > multiply_threshold)
    {
        mp_size     bot_size = (size_a + 1) / 2;
        mp_digit   *a_top = da + bot_size;
        mp_digit   *t1,
                   *t2,
                   *t3,
                    carry PG_USED_FOR_ASSERTS_ONLY;
        mp_size     at_size = size_a - bot_size;
        mp_size     buf_size = 2 * bot_size;

        if ((t1 = s_alloc(4 * buf_size)) == NULL)
            return 0;
        t2 = t1 + buf_size;
        t3 = t2 + buf_size;
        ZERO(t1, 4 * buf_size);

        (void) s_ksqr(da, t1, bot_size);    /* t1 = a0 ^ 2 */
        (void) s_ksqr(a_top, t2, at_size);  /* t2 = a1 ^ 2 */

        (void) s_kmul(da, a_top, t3, bot_size, at_size);    /* t3 = a0 * a1 */

        /* Quick multiply t3 by 2, shifting left (can't overflow) */
        {
            int         i,
                        top = bot_size + at_size;
            mp_word     w,
                        save = 0;

            for (i = 0; i < top; ++i)
            {
                w = t3[i];
                w = (w << 1) | save;
                t3[i] = LOWER_HALF(w);
                save = UPPER_HALF(w);
            }
            t3[i] = LOWER_HALF(save);
        }

        /* Assemble the output value */
        COPY(t1, dc, 2 * bot_size);
        carry = s_uadd(t3, dc + bot_size, dc + bot_size, buf_size + 1, buf_size);
        assert(carry == 0);

        carry =
            s_uadd(t2, dc + 2 * bot_size, dc + 2 * bot_size, buf_size, buf_size);
        assert(carry == 0);

        s_free(t1);             /* note that t2 and t2 are internal pointers
                                 * only */

    }
    else
    {
        s_usqr(da, dc, size_a);
    }

    return 1;
}

s_norm()

static int s_norm ( mp_int  a, mp_int  b  )

static

Definition at line 3059 of file imath.c.

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

Referenced by GROW(), and s_udiv_knuth().

{
    mp_digit    d = b->digits[MP_USED(b) - 1];
    int         k = 0;

    while (d < (1u << (mp_digit) (MP_DIGIT_BIT - 1)))
    {                           /* d < (MP_RADIX / 2) */
        d <<= 1;
        ++k;
    }

    /* These multiplications can't fail */
    if (k != 0)
    {
        (void) s_qmul(a, (mp_size) k);
        (void) s_qmul(b, (mp_size) k);
    }

    return k;
}

s_outlen()

static int s_outlen ( mp_int  z, mp_size  r  )

static

Definition at line 3454 of file imath.c.

References assert, mp_int_count_bits(), MP_MAX_RADIX, MP_MIN_RADIX, and s_log2.

Referenced by GROW(), and mp_int_string_len().

{
    assert(r >= MP_MIN_RADIX && r <= MP_MAX_RADIX);

    mp_result   bits = mp_int_count_bits(z);
    double      raw = (double) bits * s_log2[r];

    return (int) (raw + 0.999999);
}

s_pad()

static bool s_pad ( mp_int  z, mp_size  min  )

static

Definition at line 2253 of file imath.c.

References mpz_t::alloc, mpz_t::digits, MP_ALLOC(), MP_DIGITS(), s_alloc(), s_realloc(), s_round_prec(), and mpz_t::single.

Referenced by GROW(), mp_int_add(), mp_int_copy(), mp_int_mul(), mp_int_multiply_threshold(), mp_int_read_binary(), mp_int_read_cstring(), mp_int_read_unsigned(), mp_int_sqr(), mp_int_sub(), px_find_combo(), s_2expt(), s_brmu(), s_qmul(), s_qsub(), and s_udiv_knuth().

{
    if (MP_ALLOC(z) < min)
    {
        mp_size     nsize = s_round_prec(min);
        mp_digit   *tmp;

        if (z->digits == &(z->single))
        {
            if ((tmp = s_alloc(nsize)) == NULL)
                return false;
            tmp[0] = z->single;
        }
        else if ((tmp = s_realloc(MP_DIGITS(z), MP_ALLOC(z), nsize)) == NULL)
        {
            return false;
        }

        z->digits = tmp;
        z->alloc = nsize;
    }

    return true;
}

s_qdiv()

static void s_qdiv ( mp_int  z, mp_size  p2  )

static

Definition at line 2802 of file imath.c.

References CLAMP(), mpz_t::digits, MP_DIGIT_BIT, MP_DIGITS(), mp_int_zero(), MP_USED(), MP_ZPOS, mpz_t::sign, and mpz_t::used.

Referenced by GROW(), mp_int_div(), mp_int_div_pow2(), mp_int_egcd(), mp_int_gcd(), s_reduce(), and s_udiv_knuth().

{
    mp_size     ndig = p2 / MP_DIGIT_BIT,
                nbits = p2 % MP_DIGIT_BIT;
    mp_size     uz = MP_USED(z);

    if (ndig)
    {
        mp_size     mark;
        mp_digit   *to,
                   *from;

        if (ndig >= uz)
        {
            mp_int_zero(z);
            return;
        }

        to = MP_DIGITS(z);
        from = to + ndig;

        for (mark = ndig; mark < uz; ++mark)
        {
            *to++ = *from++;
        }

        z->used = uz - ndig;
    }

    if (nbits)
    {
        mp_digit    d = 0,
                   *dz,
                    save;
        mp_size     up = MP_DIGIT_BIT - nbits;

        uz = MP_USED(z);
        dz = MP_DIGITS(z) + uz - 1;

        for ( /* */ ; uz > 0; --uz, --dz)
        {
            save = *dz;

            *dz = (*dz >> nbits) | (d << up);
            d = save;
        }

        CLAMP(z);
    }

    if (MP_USED(z) == 1 && z->digits[0] == 0)
        z->sign = MP_ZPOS;
}

s_qmod()

static void s_qmod ( mp_int  z, mp_size  p2  )

static

Definition at line 2857 of file imath.c.

References CLAMP(), mpz_t::digits, MP_DIGIT_BIT, MP_USED(), and mpz_t::used.

Referenced by GROW(), mp_int_div(), mp_int_div_pow2(), and s_reduce().

{
    mp_size     start = p2 / MP_DIGIT_BIT + 1,
                rest = p2 % MP_DIGIT_BIT;
    mp_size     uz = MP_USED(z);
    mp_digit    mask = (1u << rest) - 1;

    if (start <= uz)
    {
        z->used = start;
        z->digits[start - 1] &= mask;
        CLAMP(z);
    }
}

s_qmul()

static int s_qmul ( mp_int  z, mp_size  p2  )

static

Definition at line 2873 of file imath.c.

References CLAMP(), i, MP_DIGIT_BIT, MP_DIGITS(), MP_USED(), s_pad(), mpz_t::used, and ZERO().

Referenced by GROW(), mp_int_egcd(), mp_int_gcd(), mp_int_mul_pow2(), mp_int_read_binary(), mp_int_read_unsigned(), and s_norm().

{
    mp_size     uz,
                need,
                rest,
                extra,
                i;
    mp_digit   *from,
               *to,
                d;

    if (p2 == 0)
        return 1;

    uz = MP_USED(z);
    need = p2 / MP_DIGIT_BIT;
    rest = p2 % MP_DIGIT_BIT;

    /*
     * Figure out if we need an extra digit at the top end; this occurs if the
     * topmost `rest' bits of the high-order digit of z are not zero, meaning
     * they will be shifted off the end if not preserved
     */
    extra = 0;
    if (rest != 0)
    {
        mp_digit   *dz = MP_DIGITS(z) + uz - 1;

        if ((*dz >> (MP_DIGIT_BIT - rest)) != 0)
            extra = 1;
    }

    if (!s_pad(z, uz + need + extra))
        return 0;

    /*
     * If we need to shift by whole digits, do that in one pass, then to back
     * and shift by partial digits.
     */
    if (need > 0)
    {
        from = MP_DIGITS(z) + uz - 1;
        to = from + need;

        for (i = 0; i < uz; ++i)
            *to-- = *from--;

        ZERO(MP_DIGITS(z), need);
        uz += need;
    }

    if (rest)
    {
        d = 0;
        for (i = need, from = MP_DIGITS(z) + need; i < uz; ++i, ++from)
        {
            mp_digit    save = *from;

            *from = (*from << rest) | (d >> (MP_DIGIT_BIT - rest));
            d = save;
        }

        d >>= (MP_DIGIT_BIT - rest);
        if (d != 0)
        {
            *from = d;
            uz += extra;
        }
    }

    z->used = uz;
    CLAMP(z);

    return 1;
}

s_qsub()

static int s_qsub ( mp_int  z, mp_size  p2  )

static

Definition at line 2953 of file imath.c.

References assert, CLAMP(), LOWER_HALF(), MP_DIGIT_BIT, MP_DIGIT_MAX, MP_DIGITS(), MP_ZPOS, s_pad(), mpz_t::sign, and UPPER_HALF().

Referenced by GROW(), and s_reduce().

{
    mp_digit    hi = (1u << (p2 % MP_DIGIT_BIT)),
               *zp;
    mp_size     tdig = (p2 / MP_DIGIT_BIT),
                pos;
    mp_word     w = 0;

    if (!s_pad(z, tdig + 1))
        return 0;

    for (pos = 0, zp = MP_DIGITS(z); pos < tdig; ++pos, ++zp)
    {
        w = ((mp_word) MP_DIGIT_MAX + 1) - w - (mp_word) *zp;

        *zp = LOWER_HALF(w);
        w = UPPER_HALF(w) ? 0 : 1;
    }

    w = ((mp_word) MP_DIGIT_MAX + 1 + hi) - w - (mp_word) *zp;
    *zp = LOWER_HALF(w);

    assert(UPPER_HALF(w) != 0); /* no borrow out should be possible */

    z->sign = MP_ZPOS;
    CLAMP(z);

    return 1;
}

s_realloc()

static mp_digit* s_realloc ( mp_digit *  old, mp_size  osize, mp_size  nsize  )

static

Definition at line 2227 of file imath.c.

References assert, fill(), repalloc(), and s_alloc().

Referenced by s_pad().

{
#if IMATH_DEBUG
    mp_digit   *new = s_alloc(nsize);

    assert(new != NULL);

    for (mp_size ix = 0; ix < nsize; ++ix)
        new[ix] = fill;
    memcpy(new, old, osize * sizeof(mp_digit));
#else
    mp_digit   *new = repalloc(old, nsize * sizeof(mp_digit));

    assert(new != NULL);
#endif

    return new;
}

s_reduce()

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

static

Definition at line 3093 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 GROW(), and s_embar().

{
    mp_size     um = MP_USED(m),
                umb_p1,
                umb_m1;

    umb_p1 = (um + 1) * MP_DIGIT_BIT;
    umb_m1 = (um - 1) * MP_DIGIT_BIT;

    if (mp_int_copy(x, q1) != MP_OK)
        return 0;

    /* Compute q2 = floor((floor(x / b^(k-1)) * mu) / b^(k+1)) */
    s_qdiv(q1, umb_m1);
    UMUL(q1, mu, q2);
    s_qdiv(q2, umb_p1);

    /* Set x = x mod b^(k+1) */
    s_qmod(x, umb_p1);

    /*
     * Now, q is a guess for the quotient a / m. Compute x - q * m mod
     * b^(k+1), replacing x.  This may be off by a factor of 2m, but no more
     * than that.
     */
    UMUL(q2, m, q1);
    s_qmod(q1, umb_p1);
    (void) mp_int_sub(x, q1, x);    /* can't fail */

    /*
     * The result may be < 0; if it is, add b^(k+1) to pin it in the proper
     * range.
     */
    if ((CMPZ(x) < 0) && !s_qsub(x, umb_p1))
        return 0;

    /*
     * If x > m, we need to back it off until it is in range.  This will be
     * required at most twice.
     */
    if (mp_int_compare(x, m) >= 0)
    {
        (void) mp_int_sub(x, m, x);
        if (mp_int_compare(x, m) >= 0)
        {
            (void) mp_int_sub(x, m, x);
        }
    }

    /* At this point, x has been properly reduced. */
    return 1;
}

s_round_prec()

static mp_size s_round_prec ( mp_size  P )

inlinestatic

Definition at line 124 of file imath.c.

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

{
    return 2 * ((P + 1) / 2);
}

s_tobin()

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

static

Definition at line 3538 of file imath.c.

References i, MP_DIGITS(), MP_OK, MP_TRUNC, MP_USED(), and REV().

Referenced by GROW(), mp_int_to_binary(), and mp_int_to_unsigned().

{
    int         pos = 0,
                limit = *limpos;
    mp_size     uz = MP_USED(z);
    mp_digit   *dz = MP_DIGITS(z);

    while (uz > 0 && pos < limit)
    {
        mp_digit    d = *dz++;
        int         i;

        for (i = sizeof(mp_digit); i > 0 && pos < limit; --i)
        {
            buf[pos++] = (unsigned char) d;
            d >>= CHAR_BIT;

            /* Don't write leading zeroes */
            if (d == 0 && uz == 1)
                i = 0;          /* exit loop without signaling truncation */
        }

        /* Detect truncation (loop exited with pos >= limit) */
        if (i > 0)
            break;

        --uz;
    }

    if (pad != 0 && (buf[pos - 1] >> (CHAR_BIT - 1)))
    {
        if (pos < limit)
        {
            buf[pos++] = 0;
        }
        else
        {
            uz = 1;
        }
    }

    /* Digits are in reverse order, fix that */
    REV(buf, pos);

    /* Return the number of bytes actually written */
    *limpos = pos;

    return (uz == 0) ? MP_OK : MP_TRUNC;
}

s_uadd()

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 2387 of file imath.c.

References LOWER_HALF(), SWAP, and UPPER_HALF().

Referenced by GROW(), mp_int_add(), mp_int_sub(), s_kmul(), and s_ksqr().

{
    mp_size     pos;
    mp_word     w = 0;

    /* Insure that da is the longer of the two to simplify later code */
    if (size_b > size_a)
    {
        SWAP(mp_digit *, da, db);
        SWAP(mp_size, size_a, size_b);
    }

    /* Add corresponding digits until the shorter number runs out */
    for (pos = 0; pos < size_b; ++pos, ++da, ++db, ++dc)
    {
        w = w + (mp_word) *da + (mp_word) *db;
        *dc = LOWER_HALF(w);
        w = UPPER_HALF(w);
    }

    /* Propagate carries as far as necessary */
    for ( /* */ ; pos < size_a; ++pos, ++da, ++dc)
    {
        w = w + *da;

        *dc = LOWER_HALF(w);
        w = UPPER_HALF(w);
    }

    /* Return carry out */
    return (mp_digit) w;
}

s_ucmp()

static int s_ucmp ( mp_int  a, mp_int  b  )

static

Definition at line 2342 of file imath.c.

References MP_DIGITS(), MP_USED(), and s_cdig().

Referenced by GROW(), mp_int_add(), mp_int_compare(), mp_int_compare_unsigned(), mp_int_div(), mp_int_sub(), s_udiv_knuth(), and s_uvcmp().

{
    mp_size     ua = MP_USED(a),
                ub = MP_USED(b);

    if (ua > ub)
    {
        return 1;
    }
    else if (ub > ua)
    {
        return -1;
    }
    else
    {
        return s_cdig(MP_DIGITS(a), MP_DIGITS(b), ua);
    }
}

s_udiv_knuth()

static mp_result s_udiv_knuth ( mp_int  a, mp_int  b  )

static

Definition at line 3248 of file imath.c.

References mpz_t::alloc, assert, CLAMP(), CLEANUP_TEMP, DECLARE_TEMP, mpz_t::digits, digits, GROW(), MP_ALLOC(), MP_DIGIT_BIT, MP_DIGIT_MAX, MP_DIGITS(), mp_int_copy(), mp_int_set_value(), MP_MEMORY, MP_OK, MP_USED(), MP_ZPOS, REQUIRE, s_dbmul(), s_ddiv(), s_norm(), s_pad(), s_qdiv(), s_ucmp(), s_usub(), mpz_t::sign, TEMP, mpz_t::used, and ZERO().

Referenced by GROW(), and mp_int_div().

{
    /* Force signs to positive */
    u->sign = MP_ZPOS;
    v->sign = MP_ZPOS;

    /* Use simple division algorithm when v is only one digit long */
    if (MP_USED(v) == 1)
    {
        mp_digit    d,
                    rem;

        d = v->digits[0];
        rem = s_ddiv(u, d);
        mp_int_set_value(v, rem);
        return MP_OK;
    }

    /*
     * Algorithm D
     *
     * The n and m variables are defined as used by Knuth. u is an n digit
     * number with digits u_{n-1}..u_0. v is an n+m digit number with digits
     * from v_{m+n-1}..v_0. We require that n > 1 and m >= 0
     */
    mp_size     n = MP_USED(v);
    mp_size     m = MP_USED(u) - n;

    assert(n > 1);
    /* assert(m >= 0) follows because m is unsigned. */

    /*
     * D1: Normalize. The normalization step provides the necessary condition
     * for Theorem B, which states that the quotient estimate for q_j, call it
     * qhat
     *
     * qhat = u_{j+n}u_{j+n-1} / v_{n-1}
     *
     * is bounded by
     *
     * qhat - 2 <= q_j <= qhat.
     *
     * That is, qhat is always greater than the actual quotient digit q, and
     * it is never more than two larger than the actual quotient digit.
     */
    int         k = s_norm(u, v);

    /*
     * Extend size of u by one if needed.
     *
     * The algorithm begins with a value of u that has one more digit of
     * input. The normalization step sets u_{m+n}..u_0 = 2^k * u_{m+n-1}..u_0.
     * If the multiplication did not increase the number of digits of u, we
     * need to add a leading zero here.
     */
    if (k == 0 || MP_USED(u) != m + n + 1)
    {
        if (!s_pad(u, m + n + 1))
            return MP_MEMORY;
        u->digits[m + n] = 0;
        u->used = m + n + 1;
    }

    /*
     * Add a leading 0 to v.
     *
     * The multiplication in step D4 multiplies qhat * 0v_{n-1}..v_0.  We need
     * to add the leading zero to v here to ensure that the multiplication
     * will produce the full n+1 digit result.
     */
    if (!s_pad(v, n + 1))
        return MP_MEMORY;
    v->digits[n] = 0;

    /*
     * Initialize temporary variables q and t. q allocates space for m+1
     * digits to store the quotient digits t allocates space for n+1 digits to
     * hold the result of q_j*v
     */
    DECLARE_TEMP(2);
    REQUIRE(GROW(TEMP(0), m + 1));
    REQUIRE(GROW(TEMP(1), n + 1));

    /* D2: Initialize j */
    int         j = m;
    mpz_t       r;

    r.digits = MP_DIGITS(u) + j;    /* The contents of r are shared with u */
    r.used = n + 1;
    r.sign = MP_ZPOS;
    r.alloc = MP_ALLOC(u);
    ZERO(TEMP(1)->digits, TEMP(1)->alloc);

    /* Calculate the m+1 digits of the quotient result */
    for (; j >= 0; j--)
    {
        /* D3: Calculate q' */
        /* r->digits is aligned to position j of the number u */
        mp_word     pfx,
                    qhat;

        pfx = r.digits[n];
        pfx <<= MP_DIGIT_BIT / 2;
        pfx <<= MP_DIGIT_BIT / 2;
        pfx |= r.digits[n - 1]; /* pfx = u_{j+n}{j+n-1} */

        qhat = pfx / v->digits[n - 1];

        /*
         * Check to see if qhat > b, and decrease qhat if so. Theorem B
         * guarantess that qhat is at most 2 larger than the actual value, so
         * it is possible that qhat is greater than the maximum value that
         * will fit in a digit
         */
        if (qhat > MP_DIGIT_MAX)
            qhat = MP_DIGIT_MAX;

        /*
         * D4,D5,D6: Multiply qhat * v and test for a correct value of q
         *
         * We proceed a bit different than the way described by Knuth. This
         * way is simpler but less efficent. Instead of doing the multiply and
         * subtract then checking for underflow, we first do the multiply of
         * qhat * v and see if it is larger than the current remainder r. If
         * it is larger, we decrease qhat by one and try again. We may need to
         * decrease qhat one more time before we get a value that is smaller
         * than r.
         *
         * This way is less efficent than Knuth becuase we do more multiplies,
         * but we do not need to worry about underflow this way.
         */
        /* t = qhat * v */
        s_dbmul(MP_DIGITS(v), (mp_digit) qhat, TEMP(1)->digits, n + 1);
        TEMP(1)->used = n + 1;
        CLAMP(TEMP(1));

        /* Clamp r for the comparison. Comparisons do not like leading zeros. */
        CLAMP(&r);
        if (s_ucmp(TEMP(1), &r) > 0)
        {                       /* would the remainder be negative? */
            qhat -= 1;          /* try a smaller q */
            s_dbmul(MP_DIGITS(v), (mp_digit) qhat, TEMP(1)->digits, n + 1);
            TEMP(1)->used = n + 1;
            CLAMP(TEMP(1));