imath.h File Reference

#include <limits.h>

Include dependency graph for imath.h:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Data Structures
struct	mpz_t

Macros
#define	MP_DIGIT_MAX   (PG_UINT32_MAX * UINT64CONST(1))
#define	MP_WORD_MAX   (PG_UINT64_MAX)
#define	MP_DIGIT_BIT   (sizeof(mp_digit) * CHAR_BIT)
#define	MP_WORD_BIT   (sizeof(mp_word) * CHAR_BIT)
#define	MP_SMALL_MIN   LONG_MIN
#define	MP_SMALL_MAX   LONG_MAX
#define	MP_USMALL_MAX   ULONG_MAX
#define	MP_MIN_RADIX   2
#define	MP_MAX_RADIX   36

Typedefs
typedef unsigned char	mp_sign
typedef unsigned int	mp_size
typedef int	mp_result
typedef long	mp_small
typedef unsigned long	mp_usmall
typedef uint32	mp_digit
typedef uint64	mp_word
typedef struct mpz_t *	mp_int

Functions
static mp_digit *	MP_DIGITS (mp_int Z)
static mp_size	MP_ALLOC (mp_int Z)
static mp_size	MP_USED (mp_int Z)
static mp_sign	MP_SIGN (mp_int Z)
void	mp_int_default_precision (mp_size ndigits)
void	mp_int_multiply_threshold (mp_size ndigits)
static bool	mp_int_is_odd (mp_int z)
static bool	mp_int_is_even (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_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_mod (mp_int a, mp_int m, mp_int c)
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)
static mp_result	mp_int_mod_value (mp_int a, mp_small value, mp_small *r)
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 v)
int	mp_int_compare_uvalue (mp_int z, mp_usmall uv)
bool	mp_int_divisible_value (mp_int a, mp_small v)
int	mp_int_is_pow2 (mp_int z)
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)
mp_result	mp_int_root (mp_int a, mp_small b, mp_int c)
static mp_result	mp_int_sqrt (mp_int a, 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)

Variables
const mp_result	MP_OK
const mp_result	MP_FALSE
const mp_result	MP_TRUE
const mp_result	MP_MEMORY
const mp_result	MP_RANGE
const mp_result	MP_UNDEF
const mp_result	MP_TRUNC
const mp_result	MP_BADARG
const mp_result	MP_MINERR
const mp_sign	MP_NEG
const mp_sign	MP_ZPOS

Macro Definition Documentation

MP_DIGIT_BIT

#define MP_DIGIT_BIT   (sizeof(mp_digit) * CHAR_BIT)

Definition at line 94 of file imath.h.

Referenced by mp_int_count_bits(), mp_int_expt_full(), mp_int_read_binary(), mp_int_read_unsigned(), mp_int_to_int(), mp_int_to_uint(), s_2expt(), s_brmu(), s_ddiv(), s_dp2k(), s_embar(), s_inlen(), s_isp2(), s_norm(), s_qdiv(), s_qmod(), s_qmul(), s_qsub(), s_reduce(), s_udiv_knuth(), s_uvpack(), and UPPER_HALF().

MP_DIGIT_MAX

#define MP_DIGIT_MAX   (PG_UINT32_MAX * UINT64CONST(1))

Definition at line 48 of file imath.h.

Referenced by s_qsub(), s_udiv_knuth(), s_usqr(), and s_usub().

MP_MAX_RADIX

#define MP_MAX_RADIX   36

Definition at line 101 of file imath.h.

Referenced by mp_int_read_cstring(), mp_int_string_len(), mp_int_to_string(), and s_outlen().

MP_MIN_RADIX

#define MP_MIN_RADIX   2

Definition at line 100 of file imath.h.

Referenced by mp_int_read_cstring(), mp_int_string_len(), mp_int_to_string(), and s_outlen().

MP_SMALL_MAX

#define MP_SMALL_MAX   LONG_MAX

Definition at line 97 of file imath.h.

Referenced by mp_int_to_int().

MP_SMALL_MIN

#define MP_SMALL_MIN   LONG_MIN

Definition at line 96 of file imath.h.

Referenced by mp_int_to_int().

MP_USMALL_MAX

#define MP_USMALL_MAX   ULONG_MAX

Definition at line 98 of file imath.h.

Referenced by mp_int_to_uint().

MP_WORD_BIT

#define MP_WORD_BIT   (sizeof(mp_word) * CHAR_BIT)

Definition at line 95 of file imath.h.

Referenced by HIGH_BIT_SET().

MP_WORD_MAX

#define MP_WORD_MAX   (PG_UINT64_MAX)

Definition at line 49 of file imath.h.

Referenced by ADD_WILL_OVERFLOW().

Typedef Documentation

mp_digit

typedef uint32 mp_digit

Definition at line 46 of file imath.h.

mp_int

typedef struct mpz_t * mp_int

mp_result

typedef int mp_result

Definition at line 34 of file imath.h.

mp_sign

typedef unsigned char mp_sign

Definition at line 32 of file imath.h.

mp_size

typedef unsigned int mp_size

Definition at line 33 of file imath.h.

mp_small

typedef long mp_small

Definition at line 35 of file imath.h.

mp_usmall

typedef unsigned long mp_usmall

Definition at line 36 of file imath.h.

mp_word

typedef uint64 mp_word

Definition at line 47 of file imath.h.

Function Documentation

MP_ALLOC()

static mp_size MP_ALLOC ( mp_int  Z )

inlinestatic

Definition at line 69 of file imath.h.

References mpz_t::alloc.

Referenced by s_pad(), and s_udiv_knuth().

{
    return Z->alloc;
}

MP_DIGITS()

static mp_digit* MP_DIGITS ( mp_int  Z )

inlinestatic

Definition at line 64 of file imath.h.

References mpz_t::digits.

Referenced by CLAMP(), mp_int_add(), mp_int_clear(), mp_int_copy(), mp_int_init_copy(), mp_int_init_size(), mp_int_mul(), mp_int_read_binary(), mp_int_read_unsigned(), mp_int_sqr(), mp_int_sub(), mp_int_swap(), mp_int_to_int(), mp_int_to_uint(), s_2expt(), s_dadd(), s_ddiv(), s_dmul(), s_dp2k(), s_embar(), s_isp2(), s_pad(), s_qdiv(), s_qmul(), s_qsub(), s_tobin(), s_ucmp(), s_udiv_knuth(), UMUL(), and USQR().

{
    return Z->digits;
}

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

static bool mp_int_is_even ( mp_int  z )

inlinestatic

Reports whether z is even, having remainder 0 when divided by 2.

Definition at line 129 of file imath.h.

References mpz_t::digits, mp_int_abs(), mp_int_add(), mp_int_add_value(), mp_int_alloc(), mp_int_clear(), mp_int_copy(), mp_int_div(), mp_int_div_pow2(), mp_int_div_value(), mp_int_expt(), mp_int_expt_full(), mp_int_expt_value(), mp_int_free(), mp_int_init(), mp_int_init_copy(), mp_int_init_size(), mp_int_init_uvalue(), mp_int_init_value(), mp_int_mod(), mp_int_mul(), mp_int_mul_pow2(), mp_int_mul_value(), mp_int_neg(), mp_int_set_uvalue(), mp_int_set_value(), mp_int_sqr(), mp_int_sub(), mp_int_sub_value(), mp_int_swap(), mp_int_zero(), and value.

Referenced by mp_int_egcd().

{
    return (z->digits[0] & 1) == 0;
}

mp_int_is_odd()

static bool mp_int_is_odd ( mp_int  z )

inlinestatic

Reports whether z is odd, having remainder 1 when divided by 2.

Definition at line 122 of file imath.h.

References mpz_t::digits.

Referenced by mp_int_egcd(), and mp_int_gcd().

{
    return (z->digits[0] & 1) != 0;
}

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

static mp_result mp_int_mod_value ( mp_int  a, mp_small  value, mp_small *  r  )

inlinestatic

Sets *r to the remainder of a / value. The remainder is pinned to 0 <= r < value.

Definition at line 249 of file imath.h.

References mp_int_compare(), mp_int_compare_unsigned(), mp_int_compare_uvalue(), mp_int_compare_value(), mp_int_compare_zero(), mp_int_div_value(), mp_int_divisible_value(), mp_int_egcd(), mp_int_exptmod(), mp_int_exptmod_bvalue(), mp_int_exptmod_evalue(), mp_int_exptmod_known(), mp_int_gcd(), mp_int_invmod(), mp_int_is_pow2(), mp_int_lcm(), mp_int_redux_const(), mp_int_root(), and value.

{
    return mp_int_div_value(a, value, 0, r);
}

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

static mp_result mp_int_sqrt ( mp_int  a, mp_int  c  )

inlinestatic

Sets c to the greatest integer not less than the square root of a. This is a special case of mp_int_root().

Definition at line 335 of file imath.h.

References buf, mp_error_string(), mp_int_binary_len(), mp_int_count_bits(), mp_int_read_binary(), mp_int_read_cstring(), mp_int_read_string(), mp_int_read_unsigned(), mp_int_root(), mp_int_string_len(), mp_int_to_binary(), mp_int_to_int(), mp_int_to_string(), mp_int_to_uint(), mp_int_to_unsigned(), mp_int_unsigned_len(), and generate_unaccent_rules::str.

{
    return mp_int_root(a, 2, c);
}

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;
}

MP_SIGN()

static mp_sign MP_SIGN ( mp_int  Z )

inlinestatic

Definition at line 79 of file imath.h.

References MP_BADARG, MP_FALSE, MP_MEMORY, MP_MINERR, MP_OK, MP_RANGE, MP_TRUE, MP_TRUNC, MP_UNDEF, and mpz_t::sign.

Referenced by mp_int_add(), mp_int_compare(), mp_int_compare_uvalue(), mp_int_compare_value(), mp_int_compare_zero(), mp_int_div(), mp_int_expt_full(), mp_int_invmod(), mp_int_mul(), mp_int_neg(), mp_int_read_binary(), mp_int_root(), mp_int_string_len(), mp_int_sub(), mp_int_to_binary(), mp_int_to_int(), mp_int_to_string(), mp_int_to_uint(), and s_embar().

{
    return Z->sign;
}

MP_USED()

static mp_size MP_USED ( mp_int  Z )

inlinestatic

Definition at line 74 of file imath.h.

References mpz_t::used.

Referenced by CLAMP(), mp_int_add(), mp_int_compare_zero(), mp_int_copy(), mp_int_count_bits(), mp_int_expt_full(), mp_int_exptmod(), mp_int_exptmod_known(), mp_int_init_copy(), mp_int_mul(), mp_int_sqr(), mp_int_sub(), mp_int_to_int(), mp_int_to_uint(), s_brmu(), s_dadd(), s_ddiv(), s_dmul(), s_dp2k(), s_embar(), s_isp2(), s_norm(), s_qdiv(), s_qmod(), s_qmul(), s_reduce(), s_tobin(), s_ucmp(), s_udiv_knuth(), UMUL(), and USQR().

{
    return Z->used;
}

Variable Documentation

MP_BADARG

const mp_result MP_BADARG

Definition at line 82 of file imath.c.

Referenced by mp_int_init(), and MP_SIGN().

MP_FALSE

const mp_result MP_FALSE

Definition at line 76 of file imath.c.

Referenced by MP_SIGN().

MP_MEMORY

const mp_result MP_MEMORY

Definition at line 78 of file imath.c.

Referenced by GROW(), mp_int_add(), mp_int_copy(), mp_int_egcd(), mp_int_gcd(), mp_int_init_size(), mp_int_mul(), mp_int_mul_pow2(), mp_int_read_binary(), mp_int_read_cstring(), mp_int_read_unsigned(), mp_int_sqr(), mp_int_sub(), MP_SIGN(), s_brmu(), s_embar(), and s_udiv_knuth().

MP_MINERR

const mp_result MP_MINERR

Definition at line 83 of file imath.c.

Referenced by MP_SIGN().

MP_NEG

const mp_sign MP_NEG

A sign indicating a (strictly) negative value.

Definition at line 85 of file imath.c.

Referenced by CMPZ(), mp_int_compare_uvalue(), mp_int_compare_value(), mp_int_div(), mp_int_expt_full(), mp_int_invmod(), mp_int_mul(), mp_int_read_binary(), mp_int_read_cstring(), mp_int_root(), mp_int_string_len(), mp_int_sub(), mp_int_to_binary(), mp_int_to_int(), mp_int_to_string(), mp_int_to_uint(), and s_fake().

MP_OK

const mp_result MP_OK

Definition at line 75 of file imath.c.

Referenced by GROW(), mp_int_abs(), mp_int_add(), mp_int_copy(), mp_int_div(), mp_int_div_pow2(), mp_int_div_value(), mp_int_divisible_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_init(), mp_int_init_copy(), mp_int_init_size(), mp_int_invmod(), mp_int_lcm(), mp_int_mod(), mp_int_mul(), mp_int_mul_pow2(), mp_int_neg(), mp_int_read_binary(), mp_int_read_cstring(), mp_int_read_unsigned(), mp_int_root(), mp_int_sqr(), mp_int_sub(), mp_int_to_int(), mp_int_to_string(), mp_int_to_uint(), MP_SIGN(), s_embar(), s_reduce(), s_tobin(), and s_udiv_knuth().

MP_RANGE

const mp_result MP_RANGE

Definition at line 79 of file imath.c.

Referenced by mp_int_expt(), mp_int_expt_full(), mp_int_expt_value(), mp_int_exptmod(), mp_int_exptmod_known(), mp_int_invmod(), mp_int_to_int(), mp_int_to_uint(), and MP_SIGN().

MP_TRUE

const mp_result MP_TRUE

Definition at line 77 of file imath.c.

Referenced by MP_SIGN().

MP_TRUNC

const mp_result MP_TRUNC

Definition at line 81 of file imath.c.

Referenced by mp_int_read_cstring(), mp_int_to_string(), MP_SIGN(), and s_tobin().

MP_UNDEF

const mp_result MP_UNDEF

Definition at line 80 of file imath.c.

Referenced by mp_int_div(), mp_int_egcd(), mp_int_exptmod(), mp_int_exptmod_known(), mp_int_gcd(), mp_int_invmod(), mp_int_root(), and MP_SIGN().

MP_ZPOS

const mp_sign MP_ZPOS

A sign indicating a zero or positive value.

Definition at line 86 of file imath.c.

Referenced by mp_int_abs(), mp_int_compare(), mp_int_compare_value(), mp_int_compare_zero(), mp_int_div(), mp_int_egcd(), mp_int_gcd(), mp_int_init(), mp_int_init_size(), mp_int_mul(), mp_int_read_cstring(), mp_int_root(), mp_int_sqr(), mp_int_sub(), mp_int_to_int(), mp_int_zero(), s_embar(), s_qdiv(), s_qsub(), s_udiv_knuth(), and s_ufake().