#include "imath.h"
#include <assert.h>
#include <ctype.h>
#include <stdlib.h>
#include <string.h>

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

#define	SWAP(T, A, B)

#define	DECLARE_TEMP(N)

#define	CLEANUP_TEMP()

#define	TEMP(K) (temp_.value + (K))

#define	REQUIRE(E)

Functions
static mp_size	s_round_prec (mp_size P)

static void	ZERO (mp_digit *P, mp_size S)

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

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

static void	CLAMP (mp_int z_)

static int	MIN (int A, int B)

static mp_size	MAX (mp_size A, mp_size B)

static int	CMPZ (mp_int Z)

static mp_word	UPPER_HALF (mp_word W)

static mp_digit	LOWER_HALF (mp_word W)

static bool	HIGH_BIT_SET (mp_word W)

static bool	ADD_WILL_OVERFLOW (mp_word W, mp_word V)

void	mp_int_default_precision (mp_size size)
	Sets the default number of digits allocated to an `mp_int` constructed by `mp_int_init_size()` with `prec == 0`.

void	mp_int_multiply_threshold (mp_size thresh)
	Sets the number of digits below which multiplication will use the standard quadratic "schoolbook" multiplication algorithm rather than Karatsuba-Ofman.

static mp_digit *	s_alloc (mp_size num)

static void	s_free (void *ptr)

static bool	s_pad (mp_int z, mp_size min)

static mp_result	GROW (mp_int Z, mp_size N)

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

static void	s_ufake (mp_int z, mp_usmall value, mp_digit vbuf[])

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

static int	s_uvpack (mp_usmall v, mp_digit t[])

static int	s_ucmp (mp_int a, mp_int b)

static int	s_vcmp (mp_int a, mp_small v)

static int	s_uvcmp (mp_int a, mp_usmall uv)

static mp_digit	s_uadd (mp_digit da, mp_digit db, mp_digit *dc, mp_size size_a, mp_size size_b)

static void	s_usub (mp_digit da, mp_digit db, mp_digit *dc, mp_size size_a, mp_size size_b)

static int	s_kmul (mp_digit da, mp_digit db, mp_digit *dc, mp_size size_a, mp_size size_b)

static void	s_umul (mp_digit da, mp_digit db, mp_digit *dc, mp_size size_a, mp_size size_b)

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

static void	s_usqr (mp_digit da, mp_digit dc, mp_size size_a)

static void	s_dadd (mp_int a, mp_digit b)

static void	s_dmul (mp_int a, mp_digit b)

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

static mp_digit	s_ddiv (mp_int a, mp_digit b)

static void	s_qdiv (mp_int z, mp_size p2)

static void	s_qmod (mp_int z, mp_size p2)

static int	s_qmul (mp_int z, mp_size p2)

static int	s_qsub (mp_int z, mp_size p2)

static int	s_dp2k (mp_int z)

static int	s_isp2 (mp_int z)

static int	s_2expt (mp_int z, mp_small k)

static int	s_norm (mp_int a, mp_int b)

static mp_result	s_brmu (mp_int z, mp_int m)

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

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

static mp_result	s_udiv_knuth (mp_int a, mp_int b)

static int	s_outlen (mp_int z, mp_size r)

static mp_size	s_inlen (int len, mp_size r)

static int	s_ch2val (char c, int r)

static char	s_val2ch (int v, int caps)

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

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

static void	UMUL (mp_int X, mp_int Y, mp_int Z)

static void	USQR (mp_int X, mp_int Z)

mp_result	mp_int_init (mp_int z)
	Initializes `z` with 1-digit precision and sets it to zero.

mp_int	mp_int_alloc (void)
	Allocates a fresh zero-valued `mpz_t` on the heap, returning NULL in case of error.

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.

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`.

mp_result	mp_int_init_value (mp_int z, mp_small value)
	Initializes `z` to the specified signed `value` at default precision.

mp_result	mp_int_init_uvalue (mp_int z, mp_usmall uvalue)
	Initializes `z` to the specified unsigned `value` at default precision.

mp_result	mp_int_set_value (mp_int z, mp_small value)
	Sets `z` to the value of the specified signed `value`.

mp_result	mp_int_set_uvalue (mp_int z, mp_usmall uvalue)
	Sets `z` to the value of the specified unsigned `value`.

void	mp_int_clear (mp_int z)
	Releases the storage used by `z`.

void	mp_int_free (mp_int z)
	Releases the storage used by `z` and also `z` itself.

mp_result	mp_int_copy (mp_int a, mp_int c)
	Replaces the value of `c` with a copy of the value of `a`.

void	mp_int_swap (mp_int a, mp_int c)
	Swaps the values and storage between `a` and `c`.

void	mp_int_zero (mp_int z)
	Sets `z` to zero.

mp_result	mp_int_abs (mp_int a, mp_int c)
	Sets `c` to the absolute value of `a`.

mp_result	mp_int_neg (mp_int a, mp_int c)
	Sets `c` to the additive inverse (negation) of `a`.

mp_result	mp_int_add (mp_int a, mp_int b, mp_int c)
	Sets `c` to the sum of `a` and `b`.

mp_result	mp_int_add_value (mp_int a, mp_small value, mp_int c)
	Sets `c` to the sum of `a` and `value`.

mp_result	mp_int_sub (mp_int a, mp_int b, mp_int c)
	Sets `c` to the difference of `a` less `b`.

mp_result	mp_int_sub_value (mp_int a, mp_small value, mp_int c)
	Sets `c` to the difference of `a` less `value`.

mp_result	mp_int_mul (mp_int a, mp_int b, mp_int c)
	Sets `c` to the product of `a` and `b`.

mp_result	mp_int_mul_value (mp_int a, mp_small value, mp_int c)
	Sets `c` to the product of `a` and `value`.

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`.

mp_result	mp_int_sqr (mp_int a, mp_int c)
	Sets `c` to the square of `a`.

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`.

mp_result	mp_int_mod (mp_int a, mp_int m, mp_int c)
	Sets `c` to the remainder of `a / m`.

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`.

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`.

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.

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.

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.

int	mp_int_compare (mp_int a, mp_int b)
	Returns the comparator of `a` and `b`.

int	mp_int_compare_unsigned (mp_int a, mp_int b)
	Returns the comparator of the magnitudes of `a` and `b`, disregarding their signs.

int	mp_int_compare_zero (mp_int z)
	Returns the comparator of `z` and zero.

int	mp_int_compare_value (mp_int z, mp_small value)
	Returns the comparator of `z` and the signed value `v`.

int	mp_int_compare_uvalue (mp_int z, mp_usmall uv)
	Returns the comparator of `z` and the unsigned value `uv`.

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`.

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`.

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`.

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.

mp_result	mp_int_redux_const (mp_int m, mp_int c)
	Sets `c` to the reduction constant for Barrett reduction by modulus `m`.

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.

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`.

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`.

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`.

bool	mp_int_divisible_value (mp_int a, mp_small v)
	Reports whether `a` is divisible by `v`.

int	mp_int_is_pow2 (mp_int z)
	Returns `k >= 0` such that `z` is `2^k`, if such a `k` exists.

mp_result	mp_int_root (mp_int a, mp_small b, mp_int c)
	Sets `c` to the greatest integer not less than the `b`th root of `a`, using Newton's root-finding algorithm.

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`.

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`.

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.

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`.

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`.

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`.

mp_result	mp_int_count_bits (mp_int z)
	Returns the number of significant bits in `z`.

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`.

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.

mp_result	mp_int_binary_len (mp_int z)
	Returns the number of bytes to represent `z` in 2's complement binary.

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`.

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.

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.

const char *	mp_error_string (mp_result res)
	Returns a pointer to a brief, human-readable, zero-terminated string describing `res`.

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

Variables
const mp_result	MP_OK = 0

const mp_result	MP_FALSE = 0

const mp_result	MP_TRUE = -1

const mp_result	MP_MEMORY = -2

const mp_result	MP_RANGE = -3

const mp_result	MP_UNDEF = -4

const mp_result	MP_TRUNC = -5

const mp_result	MP_BADARG = -6

const mp_result	MP_MINERR = -6

const mp_sign	MP_NEG = 1
	A sign indicating a (strictly) negative value.

const mp_sign	MP_ZPOS = 0
	A sign indicating a zero or positive value.

static const char *	s_unknown_err = "unknown result code"

static const char *	s_error_msg []

static const double	s_log2 []

static mp_size	default_precision = 8

static mp_size	multiply_threshold = 32

Macro Definition Documentation

◆ CLEANUP_TEMP

#define CLEANUP_TEMP ( )

Value:

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

Definition at line 152 of file imath/imath.c.

◆ DECLARE_TEMP

#define DECLARE_TEMP ( N )

Value:

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

Definition at line 136 of file imath/imath.c.

◆ MP_VALUE_DIGITS

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

Definition at line 78 of file imath/imath.c.

◆ REQUIRE

#define REQUIRE ( E )

Value:

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

Definition at line 170 of file imath/imath.c.

◆ SWAP

#define SWAP	(	T,
		A,
		B
	)

Value:

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

Definition at line 124 of file imath/imath.c.

◆ TEMP

#define TEMP ( K ) (temp_.value + (K))

Definition at line 164 of file imath/imath.c.

Function Documentation

◆ ADD_WILL_OVERFLOW()

static bool ADD_WILL_OVERFLOW	(	mp_word	W,
		mp_word	V
	)

inlinestatic

Definition at line 191 of file imath/imath.c.

References MP_WORD_MAX.

Referenced by s_usqr().

◆ CLAMP()

static void CLAMP ( mp_int z_ )

inlinestatic

Definition at line 111 of file imath/imath.c.

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

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

◆ CMPZ()

static int CMPZ ( mp_int Z )

inlinestatic

Definition at line 177 of file imath/imath.c.

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

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

◆ COPY()

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

inlinestatic

Definition at line 92 of file imath/imath.c.

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

◆ GROW()

static mp_result GROW	(	mp_int	Z,
		mp_size	N
	)

inlinestatic

Definition at line 223 of file imath/imath.c.

References MP_MEMORY, MP_OK, N(), and s_pad().

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

◆ HIGH_BIT_SET()

static bool HIGH_BIT_SET ( mp_word W )

inlinestatic

Definition at line 186 of file imath/imath.c.

References MP_WORD_BIT.

Referenced by s_usqr().

◆ LOWER_HALF()

static mp_digit LOWER_HALF ( mp_word W )

inlinestatic

Definition at line 183 of file imath/imath.c.

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

◆ MAX()

static mp_size MAX	(	mp_size	A,
		mp_size	B
	)

inlinestatic

Definition at line 120 of file imath/imath.c.

References A(), and B().

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

◆ MIN()

static int MIN	(	int	A,
		int	B
	)

inlinestatic

Definition at line 119 of file imath/imath.c.

References A(), and B().

Referenced by mp_int_egcd(), and mp_int_gcd().

◆ 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 1668 of file imath/imath.c.

References res, s_error_msg, and 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 516 of file imath/imath.c.

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

◆ 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 537 of file imath/imath.c.

References a(), assert, b(), carry(), 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.

◆ 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 594 of file imath/imath.c.

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

◆ 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 378 of file imath/imath.c.

References mp_int_init.

◆ 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 1620 of file imath/imath.c.

References mp_int_count_bits, mp_int_unsigned_len, and res.

◆ mp_int_clear()

void mp_int_clear ( mp_int z )

Releases the storage used by z.

Definition at line 459 of file imath/imath.c.

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

◆ mp_int_compare()

int mp_int_compare	(	mp_int	a,
		mp_int	b
	)

Returns the comparator of a and b.

Definition at line 975 of file imath/imath.c.

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

◆ 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 996 of file imath/imath.c.

References a(), assert, b(), and s_ucmp().

◆ 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 1027 of file imath/imath.c.

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

◆ mp_int_compare_value()

int mp_int_compare_value	(	mp_int	z,
		mp_small	value
	)

Returns the comparator of z and the signed value v.

Definition at line 1014 of file imath/imath.c.

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

◆ mp_int_compare_zero()

int mp_int_compare_zero ( mp_int z )

Returns the comparator of z and zero.

Definition at line 1002 of file imath/imath.c.

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

◆ 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 476 of file imath/imath.c.

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

◆ mp_int_count_bits()

mp_result mp_int_count_bits ( mp_int z )

Returns the number of significant bits in z.

Definition at line 1560 of file imath/imath.c.

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

◆ 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 198 of file imath/imath.c.

References assert, default_precision, and 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 774 of file imath/imath.c.

References a(), assert, b(), 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, res, s_isp2(), s_qdiv(), s_qmod(), s_ucmp(), s_udiv_knuth(), mpz_t::sign, and TEMP.

◆ 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 886 of file imath/imath.c.

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

◆ 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 872 of file imath/imath.c.

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

◆ 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 1327 of file imath/imath.c.

References a(), mp_int_div_value, and MP_OK.

◆ 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 1211 of file imath/imath.c.

References a(), assert, b(), 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, res, s_dp2k(), s_qdiv(), s_qmul(), and TEMP.

◆ 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 901 of file imath/imath.c.

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

◆ 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 949 of file imath/imath.c.

References a(), assert, b(), CLEANUP_TEMP, DECLARE_TEMP, 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.

◆ 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 925 of file imath/imath.c.

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

◆ 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 1037 of file imath/imath.c.

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

◆ 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 1075 of file imath/imath.c.

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

◆ 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 1066 of file imath/imath.c.

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

◆ 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 1084 of file imath/imath.c.

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

◆ 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 469 of file imath/imath.c.

References assert, and mp_int_clear.

◆ 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 1150 of file imath/imath.c.

References a(), assert, b(), 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.

◆ 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 366 of file imath/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.

◆ 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 408 of file imath/imath.c.

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

◆ 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 386 of file imath/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.

◆ 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 435 of file imath/imath.c.

References mp_int_init_copy, MP_VALUE_DIGITS, and s_ufake().

◆ 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 427 of file imath/imath.c.

References mp_int_init_copy, MP_VALUE_DIGITS, and s_fake().

◆ 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 1118 of file imath/imath.c.

References a(), assert, CLEANUP_TEMP, CMPZ(), DECLARE_TEMP, m, 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.

◆ 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 1336 of file imath/imath.c.

References assert, and s_isp2().

◆ 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 1308 of file imath/imath.c.

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

◆ 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 859 of file imath/imath.c.

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

◆ 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 665 of file imath/imath.c.

References a(), assert, b(), 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, p, s_alloc(), s_free(), s_kmul(), s_pad(), s_round_prec(), mpz_t::sign, mpz_t::used, and ZERO.

◆ 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 724 of file imath/imath.c.

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

◆ 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 715 of file imath/imath.c.

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

◆ 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" multiplication algorithm rather than Karatsuba-Ofman.

Requires ndigits >= sizeof(mp_word).

Definition at line 206 of file imath/imath.c.

References assert, and multiply_threshold.

Referenced by main().

◆ 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 526 of file imath/imath.c.

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

◆ 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 1591 of file imath/imath.c.

References assert, 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.

◆ 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 1507 of file imath/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, str, and mpz_t::used.

◆ 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 1503 of file imath/imath.c.

References mp_int_read_cstring, and str.

◆ 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 1642 of file imath/imath.c.

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

◆ 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 1112 of file imath/imath.c.

References assert, m, and s_brmu().

◆ 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 1346 of file imath/imath.c.

References a(), assert, b(), 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.

◆ 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 451 of file imath/imath.c.

References mp_int_copy, MP_VALUE_DIGITS, and s_ufake().

◆ 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 443 of file imath/imath.c.

References mp_int_copy, MP_VALUE_DIGITS, and s_fake().

◆ mp_int_sqr()

mp_result mp_int_sqr	(	mp_int	a,
		mp_int	c
	)

Sets c to the square of a.

Definition at line 737 of file imath/imath.c.

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

◆ 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 1490 of file imath/imath.c.

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

◆ 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 603 of file imath/imath.c.

References a(), assert, b(), carry(), 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.

◆ 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 656 of file imath/imath.c.

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

◆ 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 496 of file imath/imath.c.

References a(), mpz_t::digits, MP_DIGITS(), and mpz_t::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 1578 of file imath/imath.c.

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

◆ 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 1393 of file imath/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.

◆ 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 1441 of file imath/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, res, s_ddiv(), s_val2ch(), str, and t.

◆ 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 1417 of file imath/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.

◆ 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 1634 of file imath/imath.c.

References assert, and s_tobin().

◆ 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 1660 of file imath/imath.c.

References mp_int_count_bits, and res.

◆ 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 508 of file imath/imath.c.

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

◆ REV()

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

inlinestatic

Definition at line 100 of file imath/imath.c.

References A(), and N().

Referenced by s_tobin().

◆ s_2comp()

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

static

Definition at line 2724 of file imath/imath.c.

Referenced by mp_int_read_binary(), and mp_int_to_binary().

◆ s_2expt()

static int s_2expt	(	mp_int	z,
		mp_small	k
	)

static

Definition at line 2327 of file imath/imath.c.

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

Referenced by s_brmu().

◆ s_alloc()

static mp_digit * s_alloc ( mp_size num )

static

Definition at line 1690 of file imath/imath.c.

References assert.

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

◆ s_brmu()

static mp_result s_brmu	(	mp_int	z,
		mp_int	m
	)

static

Definition at line 2362 of file imath/imath.c.

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

Referenced by mp_int_exptmod(), and mp_int_redux_const().

◆ s_cdig()

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

static

Definition at line 1752 of file imath/imath.c.

Referenced by s_ucmp().

◆ s_ch2val()

static int s_ch2val	(	char	c,
		int	r
	)

static

Definition at line 2689 of file imath/imath.c.

Referenced by mp_int_read_cstring().

◆ s_dadd()

static void s_dadd	(	mp_int	a,
		mp_digit	b
	)

static

Definition at line 2071 of file imath/imath.c.

References a(), b(), LOWER_HALF(), MP_DIGITS(), MP_USED(), and UPPER_HALF().

Referenced by mp_int_read_cstring().

◆ s_dbmul()

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

static

Definition at line 2111 of file imath/imath.c.

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

Referenced by s_udiv_knuth().

◆ s_ddiv()

static mp_digit s_ddiv	(	mp_int	a,
		mp_digit	b
	)

static

Definition at line 2125 of file imath/imath.c.

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

Referenced by mp_int_to_string(), and s_udiv_knuth().

◆ s_dmul()

static void s_dmul	(	mp_int	a,
		mp_digit	b
	)

static

Definition at line 2093 of file imath/imath.c.

References a(), b(), LOWER_HALF(), MP_DIGITS(), MP_USED(), and UPPER_HALF().

Referenced by mp_int_read_cstring().

◆ s_dp2k()

static int s_dp2k ( mp_int z )

static

Definition at line 2287 of file imath/imath.c.

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

Referenced by mp_int_egcd(), and mp_int_gcd().

◆ s_embar()

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

static

Definition at line 2414 of file imath/imath.c.

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

Referenced by mp_int_exptmod(), and mp_int_exptmod_known().

◆ s_fake()

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

static

Definition at line 1737 of file imath/imath.c.

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

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

◆ s_free()

static void s_free ( void * ptr )

static

Definition at line 1715 of file imath/imath.c.

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

◆ s_inlen()

static mp_size s_inlen	(	int	len,
		mp_size	r
	)

static

Definition at line 2682 of file imath/imath.c.

References MP_DIGIT_BIT, and s_log2.

Referenced by mp_int_read_cstring().

◆ s_isp2()

static int s_isp2 ( mp_int z )

static

Definition at line 2307 of file imath/imath.c.

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

Referenced by mp_int_div(), and mp_int_is_pow2().

◆ s_kmul()

static int s_kmul	(	mp_digit *	da,
		mp_digit *	db,
		mp_digit *	dc,
		mp_size	size_a,
		mp_size	size_b
	)

static

Definition at line 1869 of file imath/imath.c.

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

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

◆ s_ksqr()

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

static

Definition at line 1971 of file imath/imath.c.

References assert, carry(), COPY(), LOWER_HALF(), multiply_threshold, s_alloc(), s_free(), s_kmul(), s_ksqr(), s_uadd(), s_usqr(), t1, t2, UPPER_HALF(), and ZERO.

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

◆ s_norm()

static int s_norm	(	mp_int	a,
		mp_int	b
	)

static

Definition at line 2344 of file imath/imath.c.

References a(), b(), MP_DIGIT_BIT, MP_USED(), and s_qmul().

Referenced by s_udiv_knuth().

◆ s_outlen()

static int s_outlen	(	mp_int	z,
		mp_size	r
	)

static

Definition at line 2673 of file imath/imath.c.

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

Referenced by mp_int_string_len().

◆ s_pad()

static bool s_pad	(	mp_int	z,
		mp_size	min
	)

static

Definition at line 1717 of file imath/imath.c.

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

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

◆ s_qdiv()

static void s_qdiv	(	mp_int	z,
		mp_size	p2
	)

static

Definition at line 2147 of file imath/imath.c.

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

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

◆ s_qmod()

static void s_qmod	(	mp_int	z,
		mp_size	p2
	)

static

Definition at line 2190 of file imath/imath.c.

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

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

◆ s_qmul()

static int s_qmul	(	mp_int	z,
		mp_size	p2
	)

static

Definition at line 2202 of file imath/imath.c.

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

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

◆ s_qsub()

static int s_qsub	(	mp_int	z,
		mp_size	p2
	)

static

Definition at line 2262 of file imath/imath.c.

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

Referenced by s_reduce().

◆ s_realloc()

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

static

Definition at line 1700 of file imath/imath.c.

References assert, and s_alloc().

Referenced by s_pad().

◆ s_reduce()

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

static

Definition at line 2371 of file imath/imath.c.

References CMPZ(), m, MP_DIGIT_BIT, mp_int_compare, mp_int_copy, mp_int_sub, MP_OK, MP_USED(), s_qdiv(), s_qmod(), s_qsub(), and UMUL().

Referenced by s_embar().

◆ s_round_prec()

static mp_size s_round_prec ( mp_size P )

inlinestatic

Definition at line 82 of file imath/imath.c.

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

◆ s_tobin()

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

static

Definition at line 2740 of file imath/imath.c.

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

Referenced by mp_int_to_binary(), and mp_int_to_unsigned().

◆ s_uadd()

static mp_digit s_uadd	(	mp_digit *	da,
		mp_digit *	db,
		mp_digit *	dc,
		mp_size	size_a,
		mp_size	size_b
	)

static

Definition at line 1807 of file imath/imath.c.

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

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

◆ s_ucmp()

static int s_ucmp	(	mp_int	a,
		mp_int	b
	)

static

Definition at line 1782 of file imath/imath.c.

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

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

◆ s_udiv_knuth()

static mp_result s_udiv_knuth	(	mp_int	a,
		mp_int	b
	)

static

Definition at line 2500 of file imath/imath.c.

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

Referenced by mp_int_div().

◆ s_ufake()

static void s_ufake	(	mp_int	z,
		mp_usmall	value,
		mp_digit	vbuf[]
	)

static

Definition at line 1743 of file imath/imath.c.

References mpz_t::alloc, mpz_t::digits, MP_VALUE_DIGITS, MP_ZPOS, s_uvpack(), mpz_t::sign, and mpz_t::used.

Referenced by mp_int_init_uvalue(), mp_int_set_uvalue(), s_fake(), and s_uvcmp().

◆ s_umul()

static void s_umul	(	mp_digit *	da,
		mp_digit *	db,
		mp_digit *	dc,
		mp_size	size_a,
		mp_size	size_b
	)

static

Definition at line 1948 of file imath/imath.c.

References a(), b(), LOWER_HALF(), and UPPER_HALF().

Referenced by s_kmul().

◆ s_usqr()

static void s_usqr	(	mp_digit *	da,
		mp_digit *	dc,
		mp_size	size_a
	)

static

Definition at line 2021 of file imath/imath.c.

References ADD_WILL_OVERFLOW(), assert, HIGH_BIT_SET(), LOWER_HALF(), MP_DIGIT_MAX, t, and UPPER_HALF().

Referenced by s_ksqr().

◆ s_usub()

static void s_usub	(	mp_digit *	da,
		mp_digit *	db,
		mp_digit *	dc,
		mp_size	size_a,
		mp_size	size_b
	)

static

Definition at line 1837 of file imath/imath.c.

References assert, LOWER_HALF(), MP_DIGIT_MAX, pos(), and UPPER_HALF().

Referenced by mp_int_add(), mp_int_sub(), s_kmul(), and s_udiv_knuth().

◆ s_uvcmp()

static int s_uvcmp	(	mp_int	a,
		mp_usmall	uv
	)

static

Definition at line 1799 of file imath/imath.c.

References a(), MP_VALUE_DIGITS, s_ucmp(), and s_ufake().

Referenced by mp_int_compare_uvalue(), and s_vcmp().

◆ s_uvpack()

static int s_uvpack	(	mp_usmall	v,
		mp_digit	t[]
	)

static

Definition at line 1766 of file imath/imath.c.

References MP_DIGIT_BIT, and t.

Referenced by s_ufake().

◆ s_val2ch()

static char s_val2ch	(	int	v,
		int	caps
	)

static

Definition at line 2708 of file imath/imath.c.

References assert.

Referenced by mp_int_to_string().

◆ s_vcmp()

static int s_vcmp	(	mp_int	a,
		mp_small	v
	)

static

Definition at line 1794 of file imath/imath.c.

References a(), and s_uvcmp().

Referenced by mp_int_compare_value().

◆ UMUL()

static void UMUL	(	mp_int	X,
		mp_int	Y,
		mp_int	Z
	)

inlinestatic

Definition at line 346 of file imath/imath.c.

References CLAMP(), MP_DIGITS(), MP_USED(), s_kmul(), mpz_t::used, X(), Y(), and ZERO.

Referenced by s_embar(), and s_reduce().

◆ UPPER_HALF()

static mp_word UPPER_HALF ( mp_word W )

inlinestatic

Definition at line 182 of file imath/imath.c.

References MP_DIGIT_BIT.

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

◆ USQR()

static void USQR	(	mp_int	X,
		mp_int	Z
	)

inlinestatic

Definition at line 357 of file imath/imath.c.

References CLAMP(), MP_DIGITS(), MP_USED(), s_ksqr(), mpz_t::used, X(), and ZERO.

Referenced by s_embar().

◆ ZERO()

static void ZERO	(	mp_digit *	P,
		mp_size	S
	)

inlinestatic

Definition at line 85 of file imath/imath.c.

Variable Documentation

◆ default_precision

mp_size default_precision = 8

static

Definition at line 196 of file imath/imath.c.

Referenced by mp_int_default_precision(), mp_int_init_copy(), mp_int_init_size(), mp_int_mul(), and mp_int_sqr().

◆ MP_BADARG

const mp_result MP_BADARG = -6

Definition at line 41 of file imath/imath.c.

Referenced by mp_int_init().

◆ MP_FALSE

const mp_result MP_FALSE = 0

Definition at line 35 of file imath/imath.c.

◆ MP_MEMORY

const mp_result MP_MEMORY = -2

Definition at line 37 of file imath/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(), s_brmu(), s_embar(), and s_udiv_knuth().

◆ MP_MINERR

const mp_result MP_MINERR = -6

Definition at line 42 of file imath/imath.c.

◆ MP_NEG

const mp_sign MP_NEG = 1

A sign indicating a (strictly) negative value.

Definition at line 44 of file imath/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

◆ MP_RANGE

const mp_result MP_RANGE = -3

Definition at line 38 of file imath/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(), and mp_int_to_uint().

◆ MP_TRUE

const mp_result MP_TRUE = -1

Definition at line 36 of file imath/imath.c.

◆ MP_TRUNC

const mp_result MP_TRUNC = -5

Definition at line 40 of file imath/imath.c.

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

◆ MP_UNDEF

const mp_result MP_UNDEF = -4

Definition at line 39 of file imath/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_root().

◆ MP_ZPOS

const mp_sign MP_ZPOS = 0

A sign indicating a zero or positive value.

Definition at line 45 of file imath/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().

◆ multiply_threshold

mp_size multiply_threshold = 32

static

Definition at line 204 of file imath/imath.c.

Referenced by mp_int_multiply_threshold(), s_kmul(), and s_ksqr().

◆ s_error_msg

const char* s_error_msg[]

static

Initial value:

= {"error code 0",     "boolean true",
                                    "out of memory",    "argument out of range",
                                    "result undefined", "output truncated",
                                    "invalid argument", NULL}

Definition at line 48 of file imath/imath.c.

Referenced by mp_error_string().

◆ s_log2

const double s_log2[]

static

Initial value:

= {
000000000, 0.000000000, 1.000000000, 0.630929754, 
500000000, 0.430676558, 0.386852807, 0.356207187, 
333333333, 0.315464877, 0.301029996, 0.289064826, 
278942946, 0.270238154, 0.262649535, 0.255958025, 
250000000, 0.244650542, 0.239812467, 0.235408913, 
231378213, 0.227670249, 0.224243824, 0.221064729, 
218104292, 0.215338279, 0.212746054, 0.210309918, 
208014598, 0.205846832, 0.203795047, 0.201849087, 
200000000, 0.198239863, 0.196561632, 0.194959022, 
193426404,                                        
}

Definition at line 64 of file imath/imath.c.

Referenced by s_inlen(), and s_outlen().

◆ s_unknown_err

const char* s_unknown_err = "unknown result code"

static

Definition at line 47 of file imath/imath.c.

Referenced by mp_error_string().

Macros

Functions

Variables

Macro Definition Documentation

◆ CLEANUP_TEMP

◆ DECLARE_TEMP

◆ MP_VALUE_DIGITS

◆ REQUIRE

◆ SWAP

◆ TEMP

Function Documentation

◆ ADD_WILL_OVERFLOW()

◆ CLAMP()

◆ CMPZ()

◆ COPY()

◆ GROW()

◆ HIGH_BIT_SET()

◆ LOWER_HALF()

◆ MAX()

◆ MIN()

◆ mp_error_string()

◆ mp_int_abs()

◆ mp_int_add()

◆ mp_int_add_value()

◆ mp_int_alloc()

◆ mp_int_binary_len()

◆ mp_int_clear()

◆ mp_int_compare()

◆ mp_int_compare_unsigned()

◆ mp_int_compare_uvalue()

◆ mp_int_compare_value()

◆ mp_int_compare_zero()

◆ mp_int_copy()

◆ mp_int_count_bits()

◆ mp_int_default_precision()

◆ mp_int_div()

◆ mp_int_div_pow2()

◆ mp_int_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_bvalue()

◆ mp_int_exptmod_evalue()

◆ mp_int_exptmod_known()

◆ mp_int_free()

◆ mp_int_gcd()

◆ mp_int_init()

◆ mp_int_init_copy()

◆ mp_int_init_size()

◆ mp_int_init_uvalue()

◆ mp_int_init_value()

◆ mp_int_invmod()

◆ mp_int_is_pow2()

◆ mp_int_lcm()

◆ mp_int_mod()

◆ mp_int_mul()

◆ mp_int_mul_pow2()

◆ mp_int_mul_value()

◆ mp_int_multiply_threshold()

◆ mp_int_neg()

◆ mp_int_read_binary()

◆ mp_int_read_cstring()

◆ mp_int_read_string()

◆ mp_int_read_unsigned()

◆ mp_int_redux_const()

◆ mp_int_root()

◆ mp_int_set_uvalue()

◆ mp_int_set_value()

◆ mp_int_sqr()

◆ mp_int_string_len()

◆ mp_int_sub()

◆ mp_int_sub_value()

◆ mp_int_swap()

◆ mp_int_to_binary()

◆ mp_int_to_int()

◆ mp_int_to_string()

◆ mp_int_to_uint()