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

Macros
#define	USE_LONG_LONG
#define	MP_DIGIT_MAX   0xFFFFFFFFULL
#define	MP_WORD_MAX   0xFFFFFFFFFFFFFFFFULL
#define	MP_DIGITS(Z)   ((Z)->digits)
#define	MP_ALLOC(Z)   ((Z)->alloc)
#define	MP_USED(Z)   ((Z)->used)
#define	MP_SIGN(Z)   ((Z)->sign)
#define	MP_DIGIT_BIT   (sizeof(mp_digit) * CHAR_BIT)
#define	MP_WORD_BIT   (sizeof(mp_word) * CHAR_BIT)
#define	MP_MIN_RADIX   2
#define	MP_MAX_RADIX   36
#define	mp_int_is_odd(Z)   ((Z)->digits[0] & 1)
#define	mp_int_is_even(Z)   !((Z)->digits[0] & 1)
#define	mp_int_mod_value(A, V, R)   mp_int_div_value((A), (V), 0, (R))

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

Functions
mp_size	mp_get_default_precision (void)
void	mp_set_default_precision (mp_size s)
mp_size	mp_get_multiply_threshold (void)
void	mp_set_multiply_threshold (mp_size s)
mp_result	mp_int_init (mp_int z)
mp_int	mp_int_alloc (void)
mp_result	mp_int_init_size (mp_int z, mp_size prec)
mp_result	mp_int_init_copy (mp_int z, mp_int old)
mp_result	mp_int_init_value (mp_int z, int value)
mp_result	mp_int_set_value (mp_int z, int value)
void	mp_int_clear (mp_int z)
void	mp_int_free (mp_int z)
mp_result	mp_int_copy (mp_int a, mp_int c)
void	mp_int_swap (mp_int a, mp_int c)
void	mp_int_zero (mp_int z)
mp_result	mp_int_abs (mp_int a, mp_int c)
mp_result	mp_int_neg (mp_int a, mp_int c)
mp_result	mp_int_add (mp_int a, mp_int b, mp_int c)
mp_result	mp_int_add_value (mp_int a, int value, mp_int c)
mp_result	mp_int_sub (mp_int a, mp_int b, mp_int c)
mp_result	mp_int_sub_value (mp_int a, int value, mp_int c)
mp_result	mp_int_mul (mp_int a, mp_int b, mp_int c)
mp_result	mp_int_mul_value (mp_int a, int value, mp_int c)
mp_result	mp_int_mul_pow2 (mp_int a, int p2, mp_int c)
mp_result	mp_int_sqr (mp_int a, mp_int c)
mp_result	mp_int_div (mp_int a, mp_int b, mp_int q, mp_int r)
mp_result	mp_int_div_value (mp_int a, int value, mp_int q, int *r)
mp_result	mp_int_div_pow2 (mp_int a, int p2, mp_int q, mp_int r)
mp_result	mp_int_mod (mp_int a, mp_int m, mp_int c)
mp_result	mp_int_expt (mp_int a, int b, mp_int c)
mp_result	mp_int_expt_value (int a, int b, mp_int c)
int	mp_int_compare (mp_int a, mp_int b)
int	mp_int_compare_unsigned (mp_int a, mp_int b)
int	mp_int_compare_zero (mp_int z)
int	mp_int_compare_value (mp_int z, int value)
int	mp_int_divisible_value (mp_int a, int 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, int value, mp_int m, mp_int c)
mp_result	mp_int_exptmod_bvalue (int value, mp_int b, mp_int m, mp_int c)
mp_result	mp_int_exptmod_known (mp_int a, mp_int b, mp_int m, mp_int mu, mp_int c)
mp_result	mp_int_redux_const (mp_int m, mp_int c)
mp_result	mp_int_invmod (mp_int a, mp_int m, mp_int c)
mp_result	mp_int_gcd (mp_int a, mp_int b, mp_int c)
mp_result	mp_int_egcd (mp_int a, mp_int b, mp_int c, mp_int x, mp_int y)
mp_result	mp_int_sqrt (mp_int a, mp_int c)
mp_result	mp_int_to_int (mp_int z, int *out)
mp_result	mp_int_to_string (mp_int z, mp_size radix, char *str, int limit)
mp_result	mp_int_string_len (mp_int z, mp_size radix)
mp_result	mp_int_read_string (mp_int z, mp_size radix, const char *str)
mp_result	mp_int_read_cstring (mp_int z, mp_size radix, const char *str, char **end)
mp_result	mp_int_count_bits (mp_int z)
mp_result	mp_int_to_binary (mp_int z, unsigned char *buf, int limit)
mp_result	mp_int_read_binary (mp_int z, unsigned char *buf, int len)
mp_result	mp_int_binary_len (mp_int z)
mp_result	mp_int_to_unsigned (mp_int z, unsigned char *buf, int limit)
mp_result	mp_int_read_unsigned (mp_int z, unsigned char *buf, int len)
mp_result	mp_int_unsigned_len (mp_int z)
const char *	mp_error_string (mp_result res)

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_sign	MP_NEG
const mp_sign	MP_ZPOS

Macro Definition Documentation

#define MP_ALLOC

(

Z

)

((Z)->alloc)

Definition at line 68 of file imath.h.

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

#define MP_DIGIT_BIT   (sizeof(mp_digit) * CHAR_BIT)

Definition at line 81 of file imath.h.

Referenced by mp_int_count_bits(), mp_int_read_binary(), mp_int_read_unsigned(), mp_int_to_int(), 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(), and s_vpack().

#define MP_DIGIT_MAX   0xFFFFFFFFULL

Definition at line 47 of file imath.h.

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

#define MP_DIGITS

(

Z

)

((Z)->digits)

Definition at line 67 of file imath.h.

Referenced by 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_set_value(), mp_int_sqr(), mp_int_sub(), mp_int_to_int(), 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(), and s_vcmp().

#define mp_int_is_even

(

Z

)

!((Z)->digits[0] & 1)

Definition at line 91 of file imath.h.

Referenced by mp_int_egcd().

#define mp_int_is_odd

(

Z

)

((Z)->digits[0] & 1)

Definition at line 90 of file imath.h.

Referenced by mp_int_egcd(), and mp_int_gcd().

#define mp_int_mod_value	(		A,
			V,
			R
	)		mp_int_div_value((A), (V), 0, (R))

Definition at line 129 of file imath.h.

#define MP_MAX_RADIX   36

Definition at line 85 of file imath.h.

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

#define MP_MIN_RADIX   2

Definition at line 84 of file imath.h.

#define MP_SIGN

(

Z

)

((Z)->sign)

Definition at line 70 of file imath.h.

Referenced by mp_int_abs(), mp_int_add(), mp_int_compare(), mp_int_compare_value(), mp_int_compare_zero(), mp_int_copy(), mp_int_div(), mp_int_egcd(), mp_int_gcd(), mp_int_init_copy(), mp_int_init_size(), mp_int_invmod(), mp_int_mul(), mp_int_neg(), mp_int_read_binary(), mp_int_read_cstring(), mp_int_set_value(), mp_int_sqr(), mp_int_sqrt(), mp_int_string_len(), mp_int_sub(), mp_int_to_binary(), mp_int_to_int(), mp_int_to_string(), mp_int_zero(), s_embar(), s_qdiv(), s_qsub(), and s_udiv().

#define MP_USED

(

Z

)

((Z)->used)

Definition at line 69 of file imath.h.

Referenced by mp_int_add(), mp_int_compare_zero(), mp_int_copy(), mp_int_count_bits(), mp_int_exptmod(), mp_int_exptmod_known(), mp_int_init_copy(), mp_int_init_size(), mp_int_mul(), mp_int_read_cstring(), mp_int_set_value(), mp_int_sqr(), mp_int_sub(), mp_int_to_int(), mp_int_zero(), s_2expt(), 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(), and s_vcmp().

#define MP_WORD_BIT   (sizeof(mp_word) * CHAR_BIT)

Definition at line 82 of file imath.h.

#define MP_WORD_MAX   0xFFFFFFFFFFFFFFFFULL

Definition at line 48 of file imath.h.

#define USE_LONG_LONG

Definition at line 35 of file imath.h.

Typedef Documentation

typedef uint32 mp_digit

Definition at line 44 of file imath.h.

typedef struct mpz * mp_int

typedef int mp_result

Definition at line 41 of file imath.h.

typedef unsigned char mp_sign

Definition at line 39 of file imath.h.

typedef unsigned int mp_size

Definition at line 40 of file imath.h.

typedef uint64 mp_word

Definition at line 45 of file imath.h.

typedef struct mpz mpz_t

Function Documentation

const char* mp_error_string

(

mp_result

res

)

Definition at line 2259 of file imath.c.

References NULL, s_error_msg, and s_unknown_err.

{
    int         ix;

    if (res > 0)
        return s_unknown_err;

    res = -res;
    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_size mp_get_default_precision

(

void

)

Definition at line 319 of file imath.c.

References default_precision.

{
    return default_precision;
}

mp_size mp_get_multiply_threshold

(

void

)

Definition at line 341 of file imath.c.

References multiply_threshold.

{
    return multiply_threshold;
}

mp_result mp_int_abs	(	mp_int	a,
		mp_int	c
	)

Definition at line 569 of file imath.c.

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

Referenced by mp_int_egcd(), and mp_int_gcd().

{
    mp_result   res;

    CHECK(a != NULL && c != NULL);

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

    MP_SIGN(c) = MP_ZPOS;
    return MP_OK;
}

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

Definition at line 607 of file imath.c.

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

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

{
    mp_size     ua,
                ub,
                uc,
                max;

    CHECK(a != NULL && b != NULL && c != NULL);

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

    if (MP_SIGN(a) == MP_SIGN(b))
    {
        /* Same sign -- add magnitudes, preserve sign of addends */
        mp_digit    carry;

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

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

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

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

        MP_USED(c) = uc;
        MP_SIGN(c) = MP_SIGN(a);

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

        /* Set x to max(a, b), y to min(a, b) to simplify later code */
        if (cmp >= 0)
        {
            x = a;
            y = b;
        }
        else
        {
            x = b;
            y = a;
        }

        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));
        MP_USED(c) = MP_USED(x);
        CLAMP(c);

        /* Give result the sign of the larger */
        MP_SIGN(c) = MP_SIGN(x);
    }

    return MP_OK;
}

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

Definition at line 684 of file imath.c.

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

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

    s_fake(&vtmp, value, vbuf);

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

mp_int mp_int_alloc

(

void

)

Definition at line 371 of file imath.c.

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

Referenced by mp_new().

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

    assert(out != NULL);
    out->digits = NULL;
    out->used = 0;
    out->alloc = 0;
    out->sign = 0;

    return out;
}

mp_result mp_int_binary_len

(

mp_int

z

)

Definition at line 2170 of file imath.c.

References mp_int_count_bits(), and mp_int_unsigned_len().

{
    mp_result   res = mp_int_count_bits(z);
    int         bytes = mp_int_unsigned_len(z);

    if (res <= 0)
        return res;

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

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

void mp_int_clear

(

mp_int

z

)

Definition at line 478 of file imath.c.

References MP_DIGITS, NULL, and s_free.

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

{
    if (z == NULL)
        return;

    if (MP_DIGITS(z) != NULL)
    {
        s_free(MP_DIGITS(z));
        MP_DIGITS(z) = NULL;
    }
}

int mp_int_compare	(	mp_int	a,
		mp_int	b
	)

Definition at line 1242 of file imath.c.

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

Referenced by mp_int_egcd(), and s_reduce().

{
    mp_sign     sa;

    CHECK(a != NULL && b != NULL);

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

int mp_int_compare_unsigned	(	mp_int	a,
		mp_int	b
	)

Definition at line 1277 of file imath.c.

References NRCHECK, NULL, and s_ucmp().

Referenced by mp_int_sqrt().

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

    return s_ucmp(a, b);
}

int mp_int_compare_value	(	mp_int	z,
		int	value
	)

Definition at line 1306 of file imath.c.

References CHECK, cmp(), MP_NEG, MP_SIGN, MP_ZPOS, NULL, and s_vcmp().

Referenced by mp_int_invmod(), and mp_int_to_int().

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

    CHECK(z != NULL);

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

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

int mp_int_compare_zero

(

mp_int

z

)

Definition at line 1289 of file imath.c.

References mpz::digits, MP_SIGN, MP_USED, MP_ZPOS, NRCHECK, and NULL.

Referenced by mp_int_mul().

{
    NRCHECK(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_result mp_int_copy	(	mp_int	a,
		mp_int	c
	)

Definition at line 510 of file imath.c.

References CHECK, COPY, MP_DIGITS, MP_MEMORY, MP_OK, MP_SIGN, MP_USED, NULL, and s_pad().

Referenced by mp_int_abs(), mp_int_div(), mp_int_div_pow2(), mp_int_egcd(), mp_int_exptmod(), mp_int_exptmod_known(), mp_int_gcd(), mp_int_invmod(), mp_int_mod(), mp_int_mul_pow2(), mp_int_neg(), mp_int_sqrt(), s_embar(), s_reduce(), and s_udiv().

{
    CHECK(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);

        MP_USED(c) = ua;
        MP_SIGN(c) = MP_SIGN(a);
    }

    return MP_OK;
}

mp_result mp_int_count_bits

(

mp_int

z

)

Definition at line 2073 of file imath.c.

References CHECK, mpz::digits, MP_DIGIT_BIT, MP_USED, and NULL.

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

{
    mp_size     nbits = 0,
                uz;
    mp_digit    d;

    CHECK(z != NULL);

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

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

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

    return nbits;
}

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

Definition at line 955 of file imath.c.

References CHECK, cmp(), CMPZ, mpz::digits, mp_int_clear(), mp_int_copy(), mp_int_init_copy(), mp_int_zero(), MP_NEG, MP_OK, MP_SIGN, MP_UNDEF, MP_ZPOS, NULL, s_isp2(), s_qdiv(), s_qmod(), s_ucmp(), s_udiv(), SETUP, and TEMP.

Referenced by mp_int_div_value(), mp_int_mod(), mp_int_sqrt(), and s_brmu().

{
    int         cmp,
                last = 0,
                lg;
    mp_result   res = MP_OK;
    mpz_t       temp[2];
    mp_int      qout,
                rout;
    mp_sign     sa = MP_SIGN(a),
                sb = MP_SIGN(b);

    CHECK(a != NULL && b != NULL && q != r);

    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)
                MP_SIGN(q) = 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.
     */
    if ((lg = s_isp2(b)) < 0)
    {
        if (q && b != q && (res = mp_int_copy(a, q)) == MP_OK)
        {
            qout = q;
        }
        else
        {
            qout = TEMP(last);
            SETUP(mp_int_init_copy(TEMP(last), a), last);
        }

        if (r && a != r && (res = mp_int_copy(b, r)) == MP_OK)
        {
            rout = r;
        }
        else
        {
            rout = TEMP(last);
            SETUP(mp_int_init_copy(TEMP(last), b), last);
        }

        if ((res = s_udiv(qout, rout)) != MP_OK)
            goto CLEANUP;
    }
    else
    {
        if (q && (res = mp_int_copy(a, q)) != MP_OK)
            goto CLEANUP;
        if (r && (res = mp_int_copy(a, r)) != MP_OK)
            goto CLEANUP;

        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)
    {
        MP_SIGN(rout) = sa;
        if (CMPZ(rout) == 0)
            MP_SIGN(rout) = MP_ZPOS;
    }
    if (qout)
    {
        MP_SIGN(qout) = (sa == sb) ? MP_ZPOS : MP_NEG;
        if (CMPZ(qout) == 0)
            MP_SIGN(qout) = MP_ZPOS;
    }

    if (q && (res = mp_int_copy(qout, q)) != MP_OK)
        goto CLEANUP;
    if (r && (res = mp_int_copy(rout, r)) != MP_OK)
        goto CLEANUP;

CLEANUP:
    while (--last >= 0)
        mp_int_clear(TEMP(last));

    return res;
}

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

Definition at line 1146 of file imath.c.

References CHECK, mp_int_copy(), MP_OK, NULL, s_qdiv(), and s_qmod().

Referenced by mp_int_sqrt().

{
    mp_result   res = MP_OK;

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

    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_result mp_int_div_value	(	mp_int	a,
		int	value,
		mp_int	q,
		int *	r
	)

Definition at line 1119 of file imath.c.

References mp_int_clear(), mp_int_div(), mp_int_init(), mp_int_to_int(), MP_OK, MP_VALUE_DIGITS, and s_fake().

Referenced by mp_int_divisible_value().

{
    mpz_t       vtmp,
                rtmp;
    mp_digit    vbuf[MP_VALUE_DIGITS(value)];
    mp_result   res;

    if ((res = mp_int_init(&rtmp)) != MP_OK)
        return res;
    s_fake(&vtmp, value, vbuf);

    if ((res = mp_int_div(a, &vtmp, q, &rtmp)) != MP_OK)
        goto CLEANUP;

    if (r)
        (void) mp_int_to_int(&rtmp, r); /* can't fail */

CLEANUP:
    mp_int_clear(&rtmp);
    return res;
}

int mp_int_divisible_value	(	mp_int	a,
		int	v
	)

Definition at line 1781 of file imath.c.

References mp_int_div_value(), MP_OK, and NULL.

{
    int         rem = 0;

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

    return rem == 0;
}

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

Definition at line 1631 of file imath.c.

References CHECK, CMPZ, MIN, mp_int_abs(), mp_int_add(), mp_int_clear(), mp_int_compare(), mp_int_copy(), mp_int_init(), mp_int_init_copy(), mp_int_is_even, mp_int_is_odd, mp_int_set_value(), mp_int_sub(), mp_int_zero(), MP_MEMORY, MP_OK, MP_SIGN, MP_UNDEF, MP_ZPOS, NULL, s_dp2k(), s_qdiv(), s_qmul(), SETUP, and TEMP.

Referenced by mp_int_invmod().

{
    int         k,
                last = 0,
                ca,
                cb;
    mpz_t       temp[8];
    mp_result   res;

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

    ca = CMPZ(a);
    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
     */
    for (last = 0; last < 4; ++last)
    {
        if ((res = mp_int_init(TEMP(last))) != MP_OK)
            goto CLEANUP;
    }
    TEMP(0)->digits[0] = 1;
    TEMP(3)->digits[0] = 1;

    SETUP(mp_int_init_copy(TEMP(4), a), last);
    SETUP(mp_int_init_copy(TEMP(5), b), last);

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

    {                           /* 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);
    }

    SETUP(mp_int_init_copy(TEMP(6), TEMP(4)), last);
    SETUP(mp_int_init_copy(TEMP(7), TEMP(5)), last);

    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)))
            {
                if ((res = mp_int_add(TEMP(0), TEMP(7), TEMP(0))) != MP_OK)
                    goto CLEANUP;
                if ((res = mp_int_sub(TEMP(1), TEMP(6), TEMP(1))) != MP_OK)
                    goto CLEANUP;
            }

            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)))
            {
                if ((res = mp_int_add(TEMP(2), TEMP(7), TEMP(2))) != MP_OK)
                    goto CLEANUP;
                if ((res = mp_int_sub(TEMP(3), TEMP(6), TEMP(3))) != MP_OK)
                    goto CLEANUP;
            }

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

        if (mp_int_compare(TEMP(4), TEMP(5)) >= 0)
        {
            if ((res = mp_int_sub(TEMP(4), TEMP(5), TEMP(4))) != MP_OK)
                goto CLEANUP;
            if ((res = mp_int_sub(TEMP(0), TEMP(2), TEMP(0))) != MP_OK)
                goto CLEANUP;
            if ((res = mp_int_sub(TEMP(1), TEMP(3), TEMP(1))) != MP_OK)
                goto CLEANUP;
        }
        else
        {
            if ((res = mp_int_sub(TEMP(5), TEMP(4), TEMP(5))) != MP_OK)
                goto CLEANUP;
            if ((res = mp_int_sub(TEMP(2), TEMP(0), TEMP(2))) != MP_OK)
                goto CLEANUP;
            if ((res = mp_int_sub(TEMP(3), TEMP(1), TEMP(3))) != MP_OK)
                goto CLEANUP;
        }

        if (CMPZ(TEMP(4)) == 0)
        {
            if (x && (res = mp_int_copy(TEMP(2), x)) != MP_OK)
                goto CLEANUP;
            if (y && (res = mp_int_copy(TEMP(3), y)) != MP_OK)
                goto CLEANUP;
            if (c)
            {
                if (!s_qmul(TEMP(5), k))
                {
                    res = MP_MEMORY;
                    goto CLEANUP;
                }

                res = mp_int_copy(TEMP(5), c);
            }

            break;
        }
    }

CLEANUP:
    while (--last >= 0)
        mp_int_clear(TEMP(last));

    return res;
}

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

Definition at line 1166 of file imath.c.

References CHECK, mp_int_clear(), mp_int_init_copy(), mp_int_mul(), mp_int_set_value(), mp_int_sqr(), MP_OK, and NULL.

{
    mpz_t       t;
    mp_result   res;
    unsigned int v = abs(b);

    CHECK(b >= 0 && c != NULL);

    if ((res = mp_int_init_copy(&t, a)) != MP_OK)
        return res;

    (void) mp_int_set_value(c, 1);
    while (v != 0)
    {
        if (v & 1)
        {
            if ((res = mp_int_mul(c, &t, c)) != MP_OK)
                goto CLEANUP;
        }

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

        if ((res = mp_int_sqr(&t, &t)) != MP_OK)
            goto CLEANUP;
    }

CLEANUP:
    mp_int_clear(&t);
    return res;
}

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

Definition at line 1204 of file imath.c.

References CHECK, mp_int_clear(), mp_int_init_value(), mp_int_mul(), mp_int_set_value(), mp_int_sqr(), MP_OK, and NULL.

{
    mpz_t       t;
    mp_result   res;
    unsigned int v = abs(b);

    CHECK(b >= 0 && c != NULL);

    if ((res = mp_int_init_value(&t, a)) != MP_OK)
        return res;

    (void) mp_int_set_value(c, 1);
    while (v != 0)
    {
        if (v & 1)
        {
            if ((res = mp_int_mul(c, &t, c)) != MP_OK)
                goto CLEANUP;
        }

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

        if ((res = mp_int_sqr(&t, &t)) != MP_OK)
            goto CLEANUP;
    }

CLEANUP:
    mp_int_clear(&t);
    return res;
}

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

Definition at line 1336 of file imath.c.

References CHECK, CMPZ, mp_int_clear(), mp_int_copy(), mp_int_init_size(), mp_int_mod(), MP_OK, MP_RANGE, MP_UNDEF, MP_USED, NULL, s_brmu(), s_embar(), SETUP, and TEMP.

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

{
    mp_result   res;
    mp_size     um;
    mpz_t       temp[3];
    mp_int      s;
    int         last = 0;

    CHECK(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;

    um = MP_USED(m);
    SETUP(mp_int_init_size(TEMP(0), 2 * um), last);
    SETUP(mp_int_init_size(TEMP(1), 2 * um), last);

    if (c == b || c == m)
    {
        SETUP(mp_int_init_size(TEMP(2), 2 * um), last);
        s = TEMP(2);
    }
    else
    {
        s = c;
    }

    if ((res = mp_int_mod(a, m, TEMP(0))) != MP_OK)
        goto CLEANUP;

    if ((res = s_brmu(TEMP(1), m)) != MP_OK)
        goto CLEANUP;

    if ((res = s_embar(TEMP(0), b, m, TEMP(1), s)) != MP_OK)
        goto CLEANUP;

    res = mp_int_copy(s, c);

CLEANUP:
    while (--last >= 0)
        mp_int_clear(TEMP(last));

    return res;
}

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

Definition at line 1404 of file imath.c.

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

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

    s_fake(&vtmp, value, vbuf);

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

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

Definition at line 1389 of file imath.c.

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

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

    s_fake(&vtmp, value, vbuf);

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

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

Definition at line 1420 of file imath.c.

References CHECK, CMPZ, mp_int_clear(), mp_int_copy(), mp_int_init_size(), mp_int_mod(), MP_OK, MP_RANGE, MP_UNDEF, MP_USED, s_embar(), SETUP, and TEMP.

{
    mp_result   res;
    mp_size     um;
    mpz_t       temp[2];
    mp_int      s;
    int         last = 0;

    CHECK(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;

    um = MP_USED(m);
    SETUP(mp_int_init_size(TEMP(0), 2 * um), last);

    if (c == b || c == m)
    {
        SETUP(mp_int_init_size(TEMP(1), 2 * um), last);
        s = TEMP(1);
    }
    else
    {
        s = c;
    }

    if ((res = mp_int_mod(a, m, TEMP(0))) != MP_OK)
        goto CLEANUP;

    if ((res = s_embar(TEMP(0), b, m, mu, s)) != MP_OK)
        goto CLEANUP;

    res = mp_int_copy(s, c);

CLEANUP:
    while (--last >= 0)
        mp_int_clear(TEMP(last));

    return res;
}

void mp_int_free

(

mp_int

z

)

Definition at line 495 of file imath.c.

References mpz::digits, mp_int_clear(), NRCHECK, NULL, and px_free.

Referenced by mp_clear_free().

{
    NRCHECK(z != NULL);

    if (z->digits != NULL)
        mp_int_clear(z);

    px_free(z);
}

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

Definition at line 1536 of file imath.c.

References CHECK, CMPZ, MIN, mp_int_abs(), mp_int_clear(), mp_int_copy(), mp_int_init(), mp_int_init_copy(), mp_int_is_odd, mp_int_neg(), mp_int_sub(), MP_MEMORY, MP_OK, MP_SIGN, MP_UNDEF, MP_ZPOS, NULL, s_dp2k(), s_qdiv(), and s_qmul().

{
    int         ca,
                cb,
                k = 0;
    mpz_t       u,
                v,
                t;
    mp_result   res;

    CHECK(a != NULL && b != NULL && c != NULL);

    ca = CMPZ(a);
    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);

    if ((res = mp_int_init(&t)) != MP_OK)
        return res;
    if ((res = mp_int_init_copy(&u, a)) != MP_OK)
        goto U;
    if ((res = mp_int_init_copy(&v, b)) != MP_OK)
        goto V;

    MP_SIGN(&u) = MP_ZPOS;
    MP_SIGN(&v) = MP_ZPOS;

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

        k = MIN(div2_u, div2_v);
        s_qdiv(&u, (mp_size) k);
        s_qdiv(&v, (mp_size) k);
    }

    if (mp_int_is_odd(&u))
    {
        if ((res = mp_int_neg(&v, &t)) != MP_OK)
            goto CLEANUP;
    }
    else
    {
        if ((res = mp_int_copy(&u, &t)) != MP_OK)
            goto CLEANUP;
    }

    for (;;)
    {
        s_qdiv(&t, s_dp2k(&t));

        if (CMPZ(&t) > 0)
        {
            if ((res = mp_int_copy(&t, &u)) != MP_OK)
                goto CLEANUP;
        }
        else
        {
            if ((res = mp_int_neg(&t, &v)) != MP_OK)
                goto CLEANUP;
        }

        if ((res = mp_int_sub(&u, &v, &t)) != MP_OK)
            goto CLEANUP;

        if (CMPZ(&t) == 0)
            break;
    }

    if ((res = mp_int_abs(&u, c)) != MP_OK)
        goto CLEANUP;
    if (!s_qmul(c, (mp_size) k))
        res = MP_MEMORY;

CLEANUP:
    mp_int_clear(&v);
V:  mp_int_clear(&u);
U:  mp_int_clear(&t);

    return res;
}

mp_result mp_int_init

(

mp_int

z

)

Definition at line 361 of file imath.c.

References default_precision, and mp_int_init_size().

Referenced by mp_int_div_value(), mp_int_egcd(), mp_int_gcd(), mp_int_init_value(), mp_int_invmod(), mp_int_mod(), and mp_int_sqrt().

{
    return mp_int_init_size(z, default_precision);
}

mp_result mp_int_init_copy	(	mp_int	z,
		mp_int	old
	)

Definition at line 412 of file imath.c.

References CHECK, COPY, default_precision, MAX, MP_DIGITS, mp_int_init_size(), MP_OK, MP_SIGN, MP_USED, and NULL.

Referenced by mp_int_div(), mp_int_egcd(), mp_int_expt(), mp_int_gcd(), mp_int_sqrt(), and mp_int_to_string().

{
    mp_result   res;
    mp_size     uold,
                target;

    CHECK(z != NULL && old != NULL);

    uold = MP_USED(old);
    target = MAX(uold, default_precision);

    if ((res = mp_int_init_size(z, target)) != MP_OK)
        return res;

    MP_USED(z) = uold;
    MP_SIGN(z) = MP_SIGN(old);
    COPY(MP_DIGITS(old), MP_DIGITS(z), uold);

    return MP_OK;
}

mp_result mp_int_init_size	(	mp_int	z,
		mp_size	prec
	)

Definition at line 389 of file imath.c.

References CHECK, default_precision, mpz::digits, MAX, MP_ALLOC, MP_DIGITS, MP_MEMORY, MP_OK, MP_SIGN, MP_USED, MP_ZPOS, NULL, ROUND_PREC, and s_alloc().

Referenced by mp_int_exptmod(), mp_int_exptmod_known(), mp_int_init(), mp_int_init_copy(), mp_new(), s_embar(), and s_udiv().

{
    CHECK(z != NULL);

    prec = (mp_size) ROUND_PREC(prec);
    prec = MAX(prec, default_precision);

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

    z->digits[0] = 0;
    MP_USED(z) = 1;
    MP_ALLOC(z) = prec;
    MP_SIGN(z) = MP_ZPOS;

    return MP_OK;
}

mp_result mp_int_init_value	(	mp_int	z,
		int	value
	)

Definition at line 438 of file imath.c.

References CHECK, mp_int_init(), mp_int_set_value(), MP_OK, and NULL.

Referenced by mp_int_expt_value().

{
    mp_result   res;

    CHECK(z != NULL);

    if ((res = mp_int_init(z)) != MP_OK)
        return res;

    return mp_int_set_value(z, value);
}

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

Definition at line 1481 of file imath.c.

References CHECK, CMPZ, mp_int_clear(), mp_int_compare_value(), mp_int_copy(), mp_int_egcd(), mp_int_init(), mp_int_mod(), mp_int_sub(), MP_NEG, MP_OK, MP_RANGE, MP_SIGN, MP_UNDEF, NULL, and TEMP.

Referenced by pgp_elgamal_decrypt().

{
    mp_result   res;
    mp_sign     sa;
    int         last = 0;
    mpz_t       temp[2];

    CHECK(a != NULL && m != NULL && c != NULL);

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

    sa = MP_SIGN(a);            /* need this for the result later */

    for (last = 0; last < 2; ++last)
        if ((res = mp_int_init(TEMP(last))) != MP_OK)
            goto CLEANUP;

    if ((res = mp_int_egcd(a, m, TEMP(0), TEMP(1), NULL)) != MP_OK)
        goto CLEANUP;

    if (mp_int_compare_value(TEMP(0), 1) != 0)
    {
        res = MP_UNDEF;
        goto CLEANUP;
    }

    /* It is first necessary to constrain the value to the proper range */
    if ((res = mp_int_mod(TEMP(1), m, TEMP(1))) != MP_OK)
        goto CLEANUP;

    /*
     * 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 (sa == MP_NEG)
        res = mp_int_sub(m, TEMP(1), c);
    else
        res = mp_int_copy(TEMP(1), c);

CLEANUP:
    while (--last >= 0)
        mp_int_clear(TEMP(last));

    return res;
}

int mp_int_is_pow2

(

mp_int

z

)

Definition at line 1796 of file imath.c.

References CHECK, NULL, and s_isp2().

{
    CHECK(z != NULL);

    return s_isp2(z);
}

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

Definition at line 1080 of file imath.c.

References CMPZ, mp_int_add(), mp_int_clear(), mp_int_copy(), mp_int_div(), mp_int_init(), MP_OK, and NULL.

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

{
    mp_result   res;
    mpz_t       tmp;
    mp_int      out;

    if (m == c)
    {
        if ((res = mp_int_init(&tmp)) != MP_OK)
            return res;

        out = &tmp;
    }
    else
    {
        out = c;
    }

    if ((res = mp_int_div(a, m, NULL, out)) != MP_OK)
        goto CLEANUP;

    if (CMPZ(out) < 0)
        res = mp_int_add(out, m, c);
    else
        res = mp_int_copy(out, c);

CLEANUP:
    if (out != c)
        mp_int_clear(&tmp);

    return res;
}

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

Definition at line 794 of file imath.c.

References CHECK, CLAMP, default_precision, MAX, MP_ALLOC, MP_DIGITS, mp_int_compare_zero(), mp_int_zero(), MP_MEMORY, MP_NEG, MP_OK, MP_SIGN, MP_USED, MP_ZPOS, NULL, ROUND_PREC, s_alloc(), s_free, s_kmul(), s_pad(), and ZERO.

Referenced by mp_int_expt(), mp_int_expt_value(), mp_int_mul_value(), and mp_modmul().

{
    mp_digit   *out;
    mp_size     osize,
                ua,
                ub,
                p = 0;
    mp_sign     osign;

    CHECK(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 */
    osign = (MP_SIGN(a) == MP_SIGN(b)) ? MP_ZPOS : MP_NEG;

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

    if (c == a || c == b)
    {
        p = 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);

    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))
    {
        s_free(MP_DIGITS(c));
        MP_DIGITS(c) = out;
        MP_ALLOC(c) = p;
    }

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

    return MP_OK;
}

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

Definition at line 882 of file imath.c.

References CHECK, mp_int_copy(), MP_MEMORY, MP_OK, NULL, and s_qmul().

{
    mp_result   res;

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

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

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

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

Definition at line 867 of file imath.c.

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

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

    s_fake(&vtmp, value, vbuf);

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

mp_result mp_int_neg	(	mp_int	a,
		mp_int	c
	)

Definition at line 587 of file imath.c.

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

Referenced by mp_int_gcd().

{
    mp_result   res;

    CHECK(a != NULL && c != NULL);

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

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

    return MP_OK;
}

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

Definition at line 2125 of file imath.c.

References CHECK, i, MP_DIGIT_BIT, MP_DIGITS, mp_int_zero(), MP_MEMORY, MP_NEG, MP_OK, MP_SIGN, NULL, s_2comp(), s_pad(), and s_qmul().

{
    mp_size     need,
                i;
    unsigned char *tmp;
    mp_digit   *dz;

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

    /* Figure out how many digits are needed to represent this value */
    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))
    {
        MP_SIGN(z) = MP_NEG;
        s_2comp(buf, len);
    }

    dz = MP_DIGITS(z);
    for (tmp = buf, 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_result mp_int_read_cstring	(	mp_int	z,
		mp_size	radix,
		const char *	str,
		char **	end
	)

Definition at line 2004 of file imath.c.

References CHECK, CLAMP, CMPZ, mpz::digits, MP_MAX_RADIX, MP_MEMORY, MP_NEG, MP_OK, MP_RANGE, MP_SIGN, MP_TRUNC, MP_USED, MP_ZPOS, NULL, s_ch2val(), s_dadd(), s_dmul(), s_inlen(), and s_pad().

Referenced by mp_int_read_string().

{
    int         ch;

    CHECK(z != NULL && str != NULL);

    if (radix < MP_MIN_RADIX || radix > MP_MAX_RADIX)
        return MP_RANGE;

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

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

    /* Skip leading zeroes */
    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;

    MP_USED(z) = 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)
        MP_SIGN(z) = MP_ZPOS;

    if (end != NULL)
        *end = (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_result mp_int_read_string	(	mp_int	z,
		mp_size	radix,
		const char *	str
	)

Definition at line 1993 of file imath.c.

References mp_int_read_cstring(), and NULL.

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

}

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

Definition at line 2210 of file imath.c.

References CHECK, i, MP_DIGIT_BIT, MP_DIGITS, mp_int_zero(), MP_MEMORY, MP_OK, NULL, s_pad(), and s_qmul().

Referenced by mp_px_rand(), and mpi_to_bn().

{
    mp_size     need,
                i;
    unsigned char *tmp;
    mp_digit   *dz;

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

    /* Figure out how many digits are needed to represent this value */
    need = ((len * CHAR_BIT) + (MP_DIGIT_BIT - 1)) / MP_DIGIT_BIT;
    if (!s_pad(z, need))
        return MP_MEMORY;

    mp_int_zero(z);

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

    return MP_OK;
}

mp_result mp_int_redux_const	(	mp_int	m,
		mp_int	c
	)

Definition at line 1469 of file imath.c.

References CHECK, NULL, and s_brmu().

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

    return s_brmu(c, m);
}

mp_result mp_int_set_value	(	mp_int	z,
		int	value
	)

Definition at line 455 of file imath.c.

References CHECK, MP_DIGITS, MP_MEMORY, MP_NEG, MP_OK, MP_SIGN, MP_USED, MP_VALUE_DIGITS, MP_ZPOS, NULL, s_pad(), and s_vpack().

Referenced by mp_int_egcd(), mp_int_expt(), mp_int_expt_value(), mp_int_init_value(), and s_embar().

{
    mp_size     ndig;

    CHECK(z != NULL);

    /* How many digits to copy */
    ndig = (mp_size) MP_VALUE_DIGITS(value);

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

    MP_USED(z) = (mp_size) s_vpack(value, MP_DIGITS(z));
    MP_SIGN(z) = (value < 0) ? MP_NEG : MP_ZPOS;

    return MP_OK;
}

mp_result mp_int_sqr	(	mp_int	a,
		mp_int	c
	)

Definition at line 902 of file imath.c.

References CHECK, CLAMP, default_precision, MAX, MP_ALLOC, MP_DIGITS, MP_MEMORY, MP_OK, MP_SIGN, MP_USED, MP_ZPOS, NULL, ROUND_PREC, s_alloc(), s_free, s_ksqr(), s_pad(), and ZERO.

Referenced by mp_int_expt(), mp_int_expt_value(), and mp_int_sqrt().

{
    mp_digit   *out;
    mp_size     osize,
                p = 0;

    CHECK(a != NULL && c != NULL);

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

    if (a == c)
    {
        p = 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))
    {
        s_free(MP_DIGITS(c));
        MP_DIGITS(c) = out;
        MP_ALLOC(c) = p;
    }

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

    return MP_OK;
}

mp_result mp_int_sqrt	(	mp_int	a,
		mp_int	c
	)

Definition at line 1808 of file imath.c.

References CHECK, mp_int_add(), mp_int_clear(), mp_int_compare_unsigned(), mp_int_copy(), mp_int_div(), mp_int_div_pow2(), mp_int_init(), mp_int_init_copy(), mp_int_sqr(), mp_int_sub_value(), MP_NEG, MP_OK, MP_SIGN, MP_UNDEF, NULL, SETUP, and TEMP.

{
    mp_result   res = MP_OK;
    mpz_t       temp[2];
    int         last = 0;

    CHECK(a != NULL && c != NULL);

    /* The square root of a negative value does not exist in the integers. */
    if (MP_SIGN(a) == MP_NEG)
        return MP_UNDEF;

    SETUP(mp_int_init_copy(TEMP(last), a), last);
    SETUP(mp_int_init(TEMP(last)), last);

    for (;;)
    {
        if ((res = mp_int_sqr(TEMP(0), TEMP(1))) != MP_OK)
            goto CLEANUP;

        if (mp_int_compare_unsigned(a, TEMP(1)) == 0)
            break;

        if ((res = mp_int_copy(a, TEMP(1))) != MP_OK)
            goto CLEANUP;
        if ((res = mp_int_div(TEMP(1), TEMP(0), TEMP(1), NULL)) != MP_OK)
            goto CLEANUP;
        if ((res = mp_int_add(TEMP(0), TEMP(1), TEMP(1))) != MP_OK)
            goto CLEANUP;
        if ((res = mp_int_div_pow2(TEMP(1), 1, TEMP(1), NULL)) != MP_OK)
            goto CLEANUP;

        if (mp_int_compare_unsigned(TEMP(0), TEMP(1)) == 0)
            break;
        if ((res = mp_int_sub_value(TEMP(0), 1, TEMP(0))) != MP_OK)
            goto CLEANUP;
        if (mp_int_compare_unsigned(TEMP(0), TEMP(1)) == 0)
            break;

        if ((res = mp_int_copy(TEMP(1), TEMP(0))) != MP_OK)
            goto CLEANUP;
    }

    res = mp_int_copy(TEMP(0), c);

CLEANUP:
    while (--last >= 0)
        mp_int_clear(TEMP(last));

    return res;
}

mp_result mp_int_string_len	(	mp_int	z,
		mp_size	radix
	)

Definition at line 1969 of file imath.c.

References CHECK, MP_MAX_RADIX, MP_NEG, MP_RANGE, MP_SIGN, NULL, and s_outlen().

{
    int         len;

    CHECK(z != NULL);

    if (radix < MP_MIN_RADIX || radix > MP_MAX_RADIX)
        return MP_RANGE;

    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_result mp_int_sub	(	mp_int	a,
		mp_int	b,
		mp_int	c
	)

Definition at line 699 of file imath.c.

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

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

{
    mp_size     ua,
                ub,
                uc,
                max;

    CHECK(a != NULL && b != NULL && c != NULL);

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

    if (MP_SIGN(a) != MP_SIGN(b))
    {
        /* Different signs -- add magnitudes and keep sign of a */
        mp_digit    carry;

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

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

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

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

        MP_USED(c) = uc;
        MP_SIGN(c) = MP_SIGN(a);

    }
    else
    {
        /* Same signs -- subtract magnitudes */
        mp_int      x,
                    y;
        mp_sign     osign;
        int         cmp = s_ucmp(a, b);

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

        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));
        MP_USED(c) = MP_USED(x);
        CLAMP(c);

        MP_SIGN(c) = osign;
    }

    return MP_OK;
}

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

Definition at line 779 of file imath.c.

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

Referenced by mp_int_sqrt().

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

    s_fake(&vtmp, value, vbuf);

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

void mp_int_swap	(	mp_int	a,
		mp_int	c
	)

Definition at line 539 of file imath.c.

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

        *a = *c;
        *c = tmp;
    }
}

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

Definition at line 2103 of file imath.c.

References CHECK, MP_NEG, MP_SIGN, NULL, s_2comp(), and s_tobin().

{
    static const int PAD_FOR_2C = 1;

    mp_result   res;
    int         limpos = limit;

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

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

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

    return res;
}

mp_result mp_int_to_int	(	mp_int	z,
		int *	out
	)

Definition at line 1865 of file imath.c.

References CHECK, MP_DIGIT_BIT, MP_DIGITS, mp_int_compare_value(), MP_NEG, MP_OK, MP_RANGE, MP_SIGN, MP_USED, MP_ZPOS, and NULL.

Referenced by mp_int_div_value().

{
    unsigned int uv = 0;
    mp_size     uz;
    mp_digit   *dz;
    mp_sign     sz;

    CHECK(z != NULL);

    /* Make sure the value is representable as an int */
    sz = MP_SIGN(z);
    if ((sz == MP_ZPOS && mp_int_compare_value(z, INT_MAX) > 0) ||
        mp_int_compare_value(z, INT_MIN) < 0)
        return MP_RANGE;

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

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

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

    return MP_OK;
}

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

Definition at line 1901 of file imath.c.

References CHECK, cmp(), CMPZ, MP_CAP_DIGITS, mp_flags, mp_int_clear(), mp_int_init_copy(), MP_MAX_RADIX, MP_NEG, MP_OK, MP_RANGE, MP_SIGN, MP_TRUNC, NULL, s_ddiv(), and s_val2ch().

{
    mp_result   res;
    int         cmp = 0;

    CHECK(z != NULL && str != NULL && limit >= 2);

    if (radix < MP_MIN_RADIX || radix > MP_MAX_RADIX)
        return MP_RANGE;

    if (CMPZ(z) == 0)
    {
        *str++ = s_val2ch(0, mp_flags & MP_CAP_DIGITS);
    }
    else
    {
        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, mp_flags & MP_CAP_DIGITS);
        }
        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_result mp_int_to_unsigned	(	mp_int	z,
		unsigned char *	buf,
		int	limit
	)

Definition at line 2196 of file imath.c.

References CHECK, NULL, and s_tobin().

Referenced by bn_to_mpi().

{
    static const int NO_PADDING = 0;

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

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

mp_result mp_int_unsigned_len

(

mp_int

z

)

Definition at line 2241 of file imath.c.

References mp_int_count_bits().

Referenced by mp_int_binary_len().

{
    mp_result   res = mp_int_count_bits(z);
    int         bytes;

    if (res <= 0)
        return res;

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

    return bytes;
}

void mp_int_zero

(

mp_int

z

)

Definition at line 555 of file imath.c.

References mpz::digits, MP_SIGN, MP_USED, MP_ZPOS, NRCHECK, and NULL.

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

{
    NRCHECK(z != NULL);

    z->digits[0] = 0;
    MP_USED(z) = 1;
    MP_SIGN(z) = MP_ZPOS;
}

void mp_set_default_precision

(

mp_size

s

)

Definition at line 329 of file imath.c.

References default_precision, NRCHECK, and ROUND_PREC.

{
    NRCHECK(s > 0);

    default_precision = (mp_size) ROUND_PREC(s);
}

void mp_set_multiply_threshold

(

mp_size

s

)

Definition at line 351 of file imath.c.

References multiply_threshold.

{
    multiply_threshold = s;
}

Variable Documentation

const mp_result MP_BADARG

Definition at line 50 of file imath.c.

const mp_result MP_FALSE

Definition at line 44 of file imath.c.

const mp_result MP_MEMORY

Definition at line 46 of file imath.c.

Referenced by 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_set_value(), mp_int_sqr(), mp_int_sub(), s_brmu(), and s_embar().

const mp_sign MP_NEG

Definition at line 52 of file imath.c.

Referenced by mp_int_compare_value(), mp_int_div(), mp_int_invmod(), mp_int_mul(), mp_int_read_binary(), mp_int_read_cstring(), mp_int_set_value(), mp_int_sqrt(), mp_int_string_len(), mp_int_sub(), mp_int_to_binary(), mp_int_to_int(), mp_int_to_string(), and s_fake().

const mp_result MP_OK

Definition at line 43 of file imath.c.

Referenced by 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_value(), mp_int_exptmod(), mp_int_exptmod_known(), mp_int_gcd(), mp_int_init_copy(), mp_int_init_size(), mp_int_init_value(), mp_int_invmod(), 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_set_value(), mp_int_sqr(), mp_int_sqrt(), mp_int_sub(), mp_int_to_int(), mp_int_to_string(), s_reduce(), s_tobin(), and s_udiv().

const mp_result MP_RANGE

Definition at line 47 of file imath.c.

Referenced by mp_int_exptmod(), mp_int_exptmod_known(), mp_int_invmod(), mp_int_read_cstring(), mp_int_string_len(), mp_int_to_int(), and mp_int_to_string().

const mp_result MP_TRUE

Definition at line 45 of file imath.c.

const mp_result MP_TRUNC

Definition at line 49 of file imath.c.

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

const mp_result MP_UNDEF

Definition at line 48 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(), and mp_int_sqrt().

const mp_sign MP_ZPOS

Definition at line 53 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_size(), mp_int_mul(), mp_int_read_cstring(), mp_int_set_value(), mp_int_sqr(), mp_int_sub(), mp_int_to_int(), mp_int_zero(), s_embar(), s_fake(), s_qdiv(), s_qsub(), and s_udiv().