PostgreSQL Source Code  git master
imath.c File Reference
#include "postgres.h"
#include "imath.h"
#include "px.h"
Include dependency graph for imath.c:

Go to the source code of this file.

Macros

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

Functions

static mp_size s_round_prec (mp_size P)
 
static void ZERO (mp_digit *P, mp_size S)
 
static void COPY (mp_digit *P, mp_digit *Q, mp_size S)
 
static void REV (unsigned char *A, int N)
 
static void CLAMP (mp_int z_)
 
static int MIN (int A, int B)
 
static mp_size MAX (mp_size A, mp_size B)
 
static int CMPZ (mp_int Z)
 
static mp_word UPPER_HALF (mp_word W)
 
static mp_digit LOWER_HALF (mp_word W)
 
static bool HIGH_BIT_SET (mp_word W)
 
static bool ADD_WILL_OVERFLOW (mp_word W, mp_word V)
 
void mp_int_default_precision (mp_size size)
 
void mp_int_multiply_threshold (mp_size thresh)
 
static mp_digits_alloc (mp_size num)
 
static void s_free (void *ptr)
 
static bool s_pad (mp_int z, mp_size min)
 
static mp_result GROW (mp_int Z, mp_size N)
 
static void s_fake (mp_int z, mp_small value, mp_digit vbuf[])
 
static void s_ufake (mp_int z, mp_usmall value, mp_digit vbuf[])
 
static int s_cdig (mp_digit *da, mp_digit *db, mp_size len)
 
static int s_uvpack (mp_usmall v, mp_digit t[])
 
static int s_ucmp (mp_int a, mp_int b)
 
static int s_vcmp (mp_int a, mp_small v)
 
static int s_uvcmp (mp_int a, mp_usmall uv)
 
static mp_digit s_uadd (mp_digit *da, mp_digit *db, mp_digit *dc, mp_size size_a, mp_size size_b)
 
static void s_usub (mp_digit *da, mp_digit *db, mp_digit *dc, mp_size size_a, mp_size size_b)
 
static int s_kmul (mp_digit *da, mp_digit *db, mp_digit *dc, mp_size size_a, mp_size size_b)
 
static void s_umul (mp_digit *da, mp_digit *db, mp_digit *dc, mp_size size_a, mp_size size_b)
 
static int s_ksqr (mp_digit *da, mp_digit *dc, mp_size size_a)
 
static void s_usqr (mp_digit *da, mp_digit *dc, mp_size size_a)
 
static void s_dadd (mp_int a, mp_digit b)
 
static void s_dmul (mp_int a, mp_digit b)
 
static void s_dbmul (mp_digit *da, mp_digit b, mp_digit *dc, mp_size size_a)
 
static mp_digit s_ddiv (mp_int a, mp_digit b)
 
static void s_qdiv (mp_int z, mp_size p2)
 
static void s_qmod (mp_int z, mp_size p2)
 
static int s_qmul (mp_int z, mp_size p2)
 
static int s_qsub (mp_int z, mp_size p2)
 
static int s_dp2k (mp_int z)
 
static int s_isp2 (mp_int z)
 
static int s_2expt (mp_int z, mp_small k)
 
static int s_norm (mp_int a, mp_int b)
 
static mp_result s_brmu (mp_int z, mp_int m)
 
static int s_reduce (mp_int x, mp_int m, mp_int mu, mp_int q1, mp_int q2)
 
static mp_result s_embar (mp_int a, mp_int b, mp_int m, mp_int mu, mp_int c)
 
static mp_result s_udiv_knuth (mp_int a, mp_int b)
 
static int s_outlen (mp_int z, mp_size r)
 
static mp_size s_inlen (int len, mp_size r)
 
static int s_ch2val (char c, int r)
 
static char s_val2ch (int v, int caps)
 
static void s_2comp (unsigned char *buf, int len)
 
static mp_result s_tobin (mp_int z, unsigned char *buf, int *limpos, int pad)
 
static void UMUL (mp_int X, mp_int Y, mp_int Z)
 
static void USQR (mp_int X, mp_int Z)
 
mp_result mp_int_init (mp_int z)
 
mp_int mp_int_alloc (void)
 
mp_result mp_int_init_size (mp_int z, mp_size prec)
 
mp_result mp_int_init_copy (mp_int z, mp_int old)
 
mp_result mp_int_init_value (mp_int z, mp_small value)
 
mp_result mp_int_init_uvalue (mp_int z, mp_usmall uvalue)
 
mp_result mp_int_set_value (mp_int z, mp_small value)
 
mp_result mp_int_set_uvalue (mp_int z, mp_usmall uvalue)
 
void mp_int_clear (mp_int z)
 
void mp_int_free (mp_int z)
 
mp_result mp_int_copy (mp_int a, mp_int c)
 
void mp_int_swap (mp_int a, mp_int c)
 
void mp_int_zero (mp_int z)
 
mp_result mp_int_abs (mp_int a, mp_int c)
 
mp_result mp_int_neg (mp_int a, mp_int c)
 
mp_result mp_int_add (mp_int a, mp_int b, mp_int c)
 
mp_result mp_int_add_value (mp_int a, mp_small value, mp_int c)
 
mp_result mp_int_sub (mp_int a, mp_int b, mp_int c)
 
mp_result mp_int_sub_value (mp_int a, mp_small value, mp_int c)
 
mp_result mp_int_mul (mp_int a, mp_int b, mp_int c)
 
mp_result mp_int_mul_value (mp_int a, mp_small value, mp_int c)
 
mp_result mp_int_mul_pow2 (mp_int a, mp_small p2, mp_int c)
 
mp_result mp_int_sqr (mp_int a, mp_int c)
 
mp_result mp_int_div (mp_int a, mp_int b, mp_int q, mp_int r)
 
mp_result mp_int_mod (mp_int a, mp_int m, mp_int c)
 
mp_result mp_int_div_value (mp_int a, mp_small value, mp_int q, mp_small *r)
 
mp_result mp_int_div_pow2 (mp_int a, mp_small p2, mp_int q, mp_int r)
 
mp_result mp_int_expt (mp_int a, mp_small b, mp_int c)
 
mp_result mp_int_expt_value (mp_small a, mp_small b, mp_int c)
 
mp_result mp_int_expt_full (mp_int a, mp_int b, mp_int c)
 
int mp_int_compare (mp_int a, mp_int b)
 
int mp_int_compare_unsigned (mp_int a, mp_int b)
 
int mp_int_compare_zero (mp_int z)
 
int mp_int_compare_value (mp_int z, mp_small value)
 
int mp_int_compare_uvalue (mp_int z, mp_usmall uv)
 
mp_result mp_int_exptmod (mp_int a, mp_int b, mp_int m, mp_int c)
 
mp_result mp_int_exptmod_evalue (mp_int a, mp_small value, mp_int m, mp_int c)
 
mp_result mp_int_exptmod_bvalue (mp_small value, mp_int b, mp_int m, mp_int c)
 
mp_result mp_int_exptmod_known (mp_int a, mp_int b, mp_int m, mp_int mu, mp_int c)
 
mp_result mp_int_redux_const (mp_int m, mp_int c)
 
mp_result mp_int_invmod (mp_int a, mp_int m, mp_int c)
 
mp_result mp_int_gcd (mp_int a, mp_int b, mp_int c)
 
mp_result mp_int_egcd (mp_int a, mp_int b, mp_int c, mp_int x, mp_int y)
 
mp_result mp_int_lcm (mp_int a, mp_int b, mp_int c)
 
bool mp_int_divisible_value (mp_int a, mp_small v)
 
int mp_int_is_pow2 (mp_int z)
 
mp_result mp_int_root (mp_int a, mp_small b, mp_int c)
 
mp_result mp_int_to_int (mp_int z, mp_small *out)
 
mp_result mp_int_to_uint (mp_int z, mp_usmall *out)
 
mp_result mp_int_to_string (mp_int z, mp_size radix, char *str, int limit)
 
mp_result mp_int_string_len (mp_int z, mp_size radix)
 
mp_result mp_int_read_string (mp_int z, mp_size radix, const char *str)
 
mp_result mp_int_read_cstring (mp_int z, mp_size radix, const char *str, char **end)
 
mp_result mp_int_count_bits (mp_int z)
 
mp_result mp_int_to_binary (mp_int z, unsigned char *buf, int limit)
 
mp_result mp_int_read_binary (mp_int z, unsigned char *buf, int len)
 
mp_result mp_int_binary_len (mp_int z)
 
mp_result mp_int_to_unsigned (mp_int z, unsigned char *buf, int limit)
 
mp_result mp_int_read_unsigned (mp_int z, unsigned char *buf, int len)
 
mp_result mp_int_unsigned_len (mp_int z)
 
const char * mp_error_string (mp_result res)
 
static mp_digits_realloc (mp_digit *old, mp_size osize, mp_size nsize)
 

Variables

const mp_result MP_OK = 0
 
const mp_result MP_FALSE = 0
 
const mp_result MP_TRUE = -1
 
const mp_result MP_MEMORY = -2
 
const mp_result MP_RANGE = -3
 
const mp_result MP_UNDEF = -4
 
const mp_result MP_TRUNC = -5
 
const mp_result MP_BADARG = -6
 
const mp_result MP_MINERR = -6
 
const mp_sign MP_NEG = 1
 
const mp_sign MP_ZPOS = 0
 
static const char * s_unknown_err = "unknown result code"
 
static const char * s_error_msg []
 
static const double s_log2 []
 
static mp_size default_precision = 8
 
static mp_size multiply_threshold = 32
 

Macro Definition Documentation

◆ assert

#define assert (   TEST)    Assert(TEST)

Definition at line 73 of file imath.c.

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

◆ 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)
#define TEMP(K)
Definition: imath.c:234
const mp_result MP_OK
Definition: imath.c:75
int i

Definition at line 222 of file imath.c.

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

◆ DECLARE_TEMP

#define DECLARE_TEMP (   N)
Value:
struct { \
mpz_t value[(N)]; \
int len; \
mp_result err; \
} temp_ = { \
.len = (N), \
.err = MP_OK, \
}; \
do { \
for (int i = 0; i < temp_.len; i++) { \
mp_int_init(TEMP(i)); \
} \
} while (0)
static struct @145 value
#define TEMP(K)
Definition: imath.c:234
const mp_result MP_OK
Definition: imath.c:75
int i

Definition at line 206 of file imath.c.

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

◆ MP_VALUE_DIGITS

◆ REQUIRE

#define REQUIRE (   E)
Value:
do { \
temp_.err = (E); \
if (temp_.err != MP_OK) goto CLEANUP; \
} while (0)
const mp_result MP_OK
Definition: imath.c:75

Definition at line 240 of file imath.c.

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

◆ SWAP

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

Definition at line 194 of file imath.c.

Referenced by s_kmul(), and s_uadd().

◆ TEMP

Function Documentation

◆ ADD_WILL_OVERFLOW()

static bool ADD_WILL_OVERFLOW ( mp_word  W,
mp_word  V 
)
inlinestatic

Definition at line 275 of file imath.c.

References MP_WORD_MAX.

Referenced by s_usqr().

276 {
277  return ((MP_WORD_MAX - V) < W);
278 }
#define MP_WORD_MAX
Definition: imath.h:49
#define W(n)
Definition: sha1.c:60

◆ CLAMP()

static void CLAMP ( mp_int  z_)
inlinestatic

Definition at line 168 of file imath.c.

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

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

169 {
170  mp_size uz_ = MP_USED(z_);
171  mp_digit *dz_ = MP_DIGITS(z_) + uz_ - 1;
172 
173  while (uz_ > 1 && (*dz_-- == 0))
174  --uz_;
175  z_->used = uz_;
176 }
static mp_size MP_USED(mp_int Z)
Definition: imath.h:74
mp_size used
Definition: imath.h:57
unsigned int mp_size
Definition: imath.h:33
static mp_digit * MP_DIGITS(mp_int Z)
Definition: imath.h:64
uint32 mp_digit
Definition: imath.h:46

◆ CMPZ()

static int CMPZ ( mp_int  Z)
inlinestatic

Definition at line 248 of file imath.c.

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

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

249 {
250  if (Z->used == 1 && Z->digits[0] == 0)
251  return 0;
252  return (Z->sign == MP_NEG) ? -1 : 1;
253 }
mp_digit * digits
Definition: imath.h:55
const mp_sign MP_NEG
Definition: imath.c:85
mp_sign sign
Definition: imath.h:58
mp_size used
Definition: imath.h:57

◆ COPY()

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

Definition at line 141 of file imath.c.

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

142 {
143  mp_size i__ = S * sizeof(mp_digit);
144  mp_digit *p__ = P;
145  mp_digit *q__ = Q;
146 
147  memcpy(q__, p__, i__);
148 }
#define S(n, x)
Definition: sha1.c:55
unsigned int mp_size
Definition: imath.h:33
uint32 mp_digit
Definition: imath.h:46

◆ GROW()

static mp_result GROW ( mp_int  Z,
mp_size  N 
)
inlinestatic

Definition at line 313 of file imath.c.

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

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

314 {
315  return s_pad(Z, N) ? MP_OK : MP_MEMORY;
316 }
const mp_result MP_OK
Definition: imath.c:75
static bool s_pad(mp_int z, mp_size min)
Definition: imath.c:2253
const mp_result MP_MEMORY
Definition: imath.c:78

◆ HIGH_BIT_SET()

static bool HIGH_BIT_SET ( mp_word  W)
inlinestatic

Definition at line 268 of file imath.c.

References MP_WORD_BIT.

Referenced by s_usqr().

269 {
270  return (W >> (MP_WORD_BIT - 1)) != 0;
271 }
#define W(n)
Definition: sha1.c:60
#define MP_WORD_BIT
Definition: imath.h:95

◆ LOWER_HALF()

static mp_digit LOWER_HALF ( mp_word  W)
inlinestatic

Definition at line 261 of file imath.c.

References W.

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

262 {
263  return (mp_digit) (W);
264 }
#define W(n)
Definition: sha1.c:60
uint32 mp_digit
Definition: imath.h:46

◆ MAX()

static mp_size MAX ( mp_size  A,
mp_size  B 
)
inlinestatic

Definition at line 187 of file imath.c.

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

188 {
189  return (B > A ? B : A);
190 }

◆ MIN()

static int MIN ( int  A,
int  B 
)
inlinestatic

Definition at line 182 of file imath.c.

Referenced by mp_int_egcd(), and mp_int_gcd().

183 {
184  return (B < A ? B : A);
185 }

◆ mp_error_string()

const char* mp_error_string ( mp_result  res)

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

Definition at line 2184 of file imath.c.

References fill(), s_error_msg, and s_unknown_err.

Referenced by mp_int_sqrt().

2185 {
2186  if (res > 0)
2187  return s_unknown_err;
2188 
2189  res = -res;
2190  int ix;
2191 
2192  for (ix = 0; ix < res && s_error_msg[ix] != NULL; ++ix)
2193  ;
2194 
2195  if (s_error_msg[ix] != NULL)
2196  {
2197  return s_error_msg[ix];
2198  }
2199  else
2200  {
2201  return s_unknown_err;
2202  }
2203 }
static const char * s_error_msg[]
Definition: imath.c:89
static const char * s_unknown_err
Definition: imath.c:88

◆ mp_int_abs()

mp_result mp_int_abs ( mp_int  a,
mp_int  c 
)

Sets c to the absolute value of a.

Definition at line 663 of file imath.c.

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

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

664 {
665  assert(a != NULL && c != NULL);
666 
667  mp_result res;
668 
669  if ((res = mp_int_copy(a, c)) != MP_OK)
670  return res;
671 
672  c->sign = MP_ZPOS;
673  return MP_OK;
674 }
mp_result mp_int_copy(mp_int a, mp_int c)
Definition: imath.c:611
const mp_sign MP_ZPOS
Definition: imath.c:86
#define assert(TEST)
Definition: imath.c:73
const mp_result MP_OK
Definition: imath.c:75
mp_sign sign
Definition: imath.h:58
int mp_result
Definition: imath.h:34

◆ mp_int_add()

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

Sets c to the sum of a and b.

Definition at line 693 of file imath.c.

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

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

694 {
695  assert(a != NULL && b != NULL && c != NULL);
696 
697  mp_size ua = MP_USED(a);
698  mp_size ub = MP_USED(b);
699  mp_size max = MAX(ua, ub);
700 
701  if (MP_SIGN(a) == MP_SIGN(b))
702  {
703  /* Same sign -- add magnitudes, preserve sign of addends */
704  if (!s_pad(c, max))
705  return MP_MEMORY;
706 
707  mp_digit carry = s_uadd(MP_DIGITS(a), MP_DIGITS(b), MP_DIGITS(c), ua, ub);
708  mp_size uc = max;
709 
710  if (carry)
711  {
712  if (!s_pad(c, max + 1))
713  return MP_MEMORY;
714 
715  c->digits[max] = carry;
716  ++uc;
717  }
718 
719  c->used = uc;
720  c->sign = a->sign;
721 
722  }
723  else
724  {
725  /* Different signs -- subtract magnitudes, preserve sign of greater */
726  int cmp = s_ucmp(a, b); /* magnitude comparision, sign ignored */
727 
728  /*
729  * Set x to max(a, b), y to min(a, b) to simplify later code. A
730  * special case yields zero for equal magnitudes.
731  */
732  mp_int x,
733  y;
734 
735  if (cmp == 0)
736  {
737  mp_int_zero(c);
738  return MP_OK;
739  }
740  else if (cmp < 0)
741  {
742  x = b;
743  y = a;
744  }
745  else
746  {
747  x = a;
748  y = b;
749  }
750 
751  if (!s_pad(c, MP_USED(x)))
752  return MP_MEMORY;
753 
754  /* Subtract smaller from larger */
755  s_usub(MP_DIGITS(x), MP_DIGITS(y), MP_DIGITS(c), MP_USED(x), MP_USED(y));
756  c->used = x->used;
757  CLAMP(c);
758 
759  /* Give result the sign of the larger */
760  c->sign = x->sign;
761  }
762 
763  return MP_OK;
764 }
static mp_size MP_USED(mp_int Z)
Definition: imath.h:74
mp_digit * digits
Definition: imath.h:55
static mp_sign MP_SIGN(mp_int Z)
Definition: imath.h:79
Definition: imath.h:52
static mp_size MAX(mp_size A, mp_size B)
Definition: imath.c:187
#define assert(TEST)
Definition: imath.c:73
void mp_int_zero(mp_int z)
Definition: imath.c:653
static mp_digit s_uadd(mp_digit *da, mp_digit *db, mp_digit *dc, mp_size size_a, mp_size size_b)
Definition: imath.c:2387
static void CLAMP(mp_int z_)
Definition: imath.c:168
const mp_result MP_OK
Definition: imath.c:75
mp_sign sign
Definition: imath.h:58
static void s_usub(mp_digit *da, mp_digit *db, mp_digit *dc, mp_size size_a, mp_size size_b)
Definition: imath.c:2422
static bool s_pad(mp_int z, mp_size min)
Definition: imath.c:2253
mp_size used
Definition: imath.h:57
static int s_ucmp(mp_int a, mp_int b)
Definition: imath.c:2342
unsigned int mp_size
Definition: imath.h:33
static mp_digit * MP_DIGITS(mp_int Z)
Definition: imath.h:64
const mp_result MP_MEMORY
Definition: imath.c:78
uint32 mp_digit
Definition: imath.h:46
static int cmp(const chr *x, const chr *y, size_t len)
Definition: regc_locale.c:742

◆ mp_int_add_value()

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

Sets c to the sum of a and value.

Definition at line 767 of file imath.c.

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

Referenced by mp_int_is_even().

768 {
769  mpz_t vtmp;
771 
772  s_fake(&vtmp, value, vbuf);
773 
774  return mp_int_add(a, &vtmp, c);
775 }
static void s_fake(mp_int z, mp_small value, mp_digit vbuf[])
Definition: imath.c:2280
Definition: imath.h:52
static struct @145 value
#define MP_VALUE_DIGITS(V)
Definition: imath.c:119
mp_result mp_int_add(mp_int a, mp_int b, mp_int c)
Definition: imath.c:693
uint32 mp_digit
Definition: imath.h:46

◆ mp_int_alloc()

mp_int mp_int_alloc ( void  )

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

Definition at line 479 of file imath.c.

References mp_int_init(), and px_alloc.

Referenced by mp_int_is_even(), and mp_new().

480 {
481  mp_int out = px_alloc(sizeof(mpz_t));
482 
483  if (out != NULL)
484  mp_int_init(out);
485 
486  return out;
487 }
Definition: imath.h:52
mp_result mp_int_init(mp_int z)
Definition: imath.c:464
#define px_alloc(s)
Definition: px.h:44

◆ mp_int_binary_len()

mp_result mp_int_binary_len ( mp_int  z)

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

Definition at line 2116 of file imath.c.

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

Referenced by mp_int_sqrt().

2117 {
2118  mp_result res = mp_int_count_bits(z);
2119 
2120  if (res <= 0)
2121  return res;
2122 
2123  int bytes = mp_int_unsigned_len(z);
2124 
2125  /*
2126  * If the highest-order bit falls exactly on a byte boundary, we need to
2127  * pad with an extra byte so that the sign will be read correctly when
2128  * reading it back in.
2129  */
2130  if (bytes * CHAR_BIT == res)
2131  ++bytes;
2132 
2133  return bytes;
2134 }
def bytes(source, encoding='ascii', errors='strict')
mp_result mp_int_count_bits(mp_int z)
Definition: imath.c:2038
mp_result mp_int_unsigned_len(mp_int z)
Definition: imath.c:2171
int mp_result
Definition: imath.h:34

◆ mp_int_clear()

void mp_int_clear ( mp_int  z)

Releases the storage used by z.

Definition at line 587 of file imath.c.

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

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

588 {
589  if (z == NULL)
590  return;
591 
592  if (MP_DIGITS(z) != NULL)
593  {
594  if (MP_DIGITS(z) != &(z->single))
595  s_free(MP_DIGITS(z));
596 
597  z->digits = NULL;
598  }
599 }
mp_digit * digits
Definition: imath.h:55
mp_digit single
Definition: imath.h:54
static mp_digit * MP_DIGITS(mp_int Z)
Definition: imath.h:64
static void s_free(void *ptr)
Definition: imath.c:2247

◆ mp_int_compare()

int mp_int_compare ( mp_int  a,
mp_int  b 
)

Returns the comparator of a and b.

Definition at line 1274 of file imath.c.

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

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

1275 {
1276  assert(a != NULL && b != NULL);
1277 
1278  mp_sign sa = MP_SIGN(a);
1279 
1280  if (sa == MP_SIGN(b))
1281  {
1282  int cmp = s_ucmp(a, b);
1283 
1284  /*
1285  * If they're both zero or positive, the normal comparison applies; if
1286  * both negative, the sense is reversed.
1287  */
1288  if (sa == MP_ZPOS)
1289  {
1290  return cmp;
1291  }
1292  else
1293  {
1294  return -cmp;
1295  }
1296  }
1297  else if (sa == MP_ZPOS)
1298  {
1299  return 1;
1300  }
1301  else
1302  {
1303  return -1;
1304  }
1305 }
static mp_sign MP_SIGN(mp_int Z)
Definition: imath.h:79
const mp_sign MP_ZPOS
Definition: imath.c:86
#define assert(TEST)
Definition: imath.c:73
unsigned char mp_sign
Definition: imath.h:32
static int s_ucmp(mp_int a, mp_int b)
Definition: imath.c:2342
static int cmp(const chr *x, const chr *y, size_t len)
Definition: regc_locale.c:742

◆ mp_int_compare_unsigned()

int mp_int_compare_unsigned ( mp_int  a,
mp_int  b 
)

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

Definition at line 1308 of file imath.c.

References assert, and s_ucmp().

Referenced by mp_int_mod_value(), and mp_int_root().

1309 {
1310  assert(a != NULL && b != NULL);
1311 
1312  return s_ucmp(a, b);
1313 }
#define assert(TEST)
Definition: imath.c:73
static int s_ucmp(mp_int a, mp_int b)
Definition: imath.c:2342

◆ mp_int_compare_uvalue()

int mp_int_compare_uvalue ( mp_int  z,
mp_usmall  uv 
)

Returns the comparator of z and the unsigned value uv.

Definition at line 1354 of file imath.c.

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

Referenced by mp_int_mod_value(), and mp_int_to_uint().

1355 {
1356  assert(z != NULL);
1357 
1358  if (MP_SIGN(z) == MP_NEG)
1359  {
1360  return -1;
1361  }
1362  else
1363  {
1364  return s_uvcmp(z, uv);
1365  }
1366 }
static int s_uvcmp(mp_int a, mp_usmall uv)
Definition: imath.c:2377
const mp_sign MP_NEG
Definition: imath.c:85
static mp_sign MP_SIGN(mp_int Z)
Definition: imath.h:79
#define assert(TEST)
Definition: imath.c:73

◆ mp_int_compare_value()

int mp_int_compare_value ( mp_int  z,
mp_small  v 
)

Returns the comparator of z and the signed value v.

Definition at line 1335 of file imath.c.

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

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

1336 {
1337  assert(z != NULL);
1338 
1339  mp_sign vsign = (value < 0) ? MP_NEG : MP_ZPOS;
1340 
1341  if (vsign == MP_SIGN(z))
1342  {
1343  int cmp = s_vcmp(z, value);
1344 
1345  return (vsign == MP_ZPOS) ? cmp : -cmp;
1346  }
1347  else
1348  {
1349  return (value < 0) ? 1 : -1;
1350  }
1351 }
const mp_sign MP_NEG
Definition: imath.c:85
static mp_sign MP_SIGN(mp_int Z)
Definition: imath.h:79
static struct @145 value
static int s_vcmp(mp_int a, mp_small v)
Definition: imath.c:2362
const mp_sign MP_ZPOS
Definition: imath.c:86
#define assert(TEST)
Definition: imath.c:73
unsigned char mp_sign
Definition: imath.h:32
static int cmp(const chr *x, const chr *y, size_t len)
Definition: regc_locale.c:742

◆ mp_int_compare_zero()

int mp_int_compare_zero ( mp_int  z)

Returns the comparator of z and zero.

Definition at line 1316 of file imath.c.

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

Referenced by mp_int_mod_value(), and mp_int_mul().

1317 {
1318  assert(z != NULL);
1319 
1320  if (MP_USED(z) == 1 && z->digits[0] == 0)
1321  {
1322  return 0;
1323  }
1324  else if (MP_SIGN(z) == MP_ZPOS)
1325  {
1326  return 1;
1327  }
1328  else
1329  {
1330  return -1;
1331  }
1332 }
static mp_size MP_USED(mp_int Z)
Definition: imath.h:74
mp_digit * digits
Definition: imath.h:55
static mp_sign MP_SIGN(mp_int Z)
Definition: imath.h:79
const mp_sign MP_ZPOS
Definition: imath.c:86
#define assert(TEST)
Definition: imath.c:73

◆ mp_int_copy()

mp_result mp_int_copy ( mp_int  a,
mp_int  c 
)

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

Definition at line 611 of file imath.c.

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

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

612 {
613  assert(a != NULL && c != NULL);
614 
615  if (a != c)
616  {
617  mp_size ua = MP_USED(a);
618  mp_digit *da,
619  *dc;
620 
621  if (!s_pad(c, ua))
622  return MP_MEMORY;
623 
624  da = MP_DIGITS(a);
625  dc = MP_DIGITS(c);
626  COPY(da, dc, ua);
627 
628  c->used = ua;
629  c->sign = a->sign;
630  }
631 
632  return MP_OK;
633 }
static mp_size MP_USED(mp_int Z)
Definition: imath.h:74
static void COPY(mp_digit *P, mp_digit *Q, mp_size S)
Definition: imath.c:141
#define assert(TEST)
Definition: imath.c:73
const mp_result MP_OK
Definition: imath.c:75
mp_sign sign
Definition: imath.h:58
static bool s_pad(mp_int z, mp_size min)
Definition: imath.c:2253
mp_size used
Definition: imath.h:57
unsigned int mp_size
Definition: imath.h:33
static mp_digit * MP_DIGITS(mp_int Z)
Definition: imath.h:64
const mp_result MP_MEMORY
Definition: imath.c:78
uint32 mp_digit
Definition: imath.h:46

◆ mp_int_count_bits()

mp_result mp_int_count_bits ( mp_int  z)

Returns the number of significant bits in z.

Definition at line 2038 of file imath.c.

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

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

2039 {
2040  assert(z != NULL);
2041 
2042  mp_size uz = MP_USED(z);
2043 
2044  if (uz == 1 && z->digits[0] == 0)
2045  return 1;
2046 
2047  --uz;
2048  mp_size nbits = uz * MP_DIGIT_BIT;
2049  mp_digit d = z->digits[uz];
2050 
2051  while (d != 0)
2052  {
2053  d >>= 1;
2054  ++nbits;
2055  }
2056 
2057  return nbits;
2058 }
static mp_size MP_USED(mp_int Z)
Definition: imath.h:74
mp_digit * digits
Definition: imath.h:55
#define MP_DIGIT_BIT
Definition: imath.h:94
#define assert(TEST)
Definition: imath.c:73
unsigned int mp_size
Definition: imath.h:33
uint32 mp_digit
Definition: imath.h:46

◆ mp_int_default_precision()

void mp_int_default_precision ( mp_size  ndigits)

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

Definition at line 284 of file imath.c.

References assert, and default_precision.

285 {
286  assert(size > 0);
287  default_precision = size;
288 }
static mp_size default_precision
Definition: imath.c:281
#define assert(TEST)
Definition: imath.c:73

◆ mp_int_div()

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

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

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

Definition at line 1002 of file imath.c.

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

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

1003 {
1004  assert(a != NULL && b != NULL && q != r);
1005 
1006  int cmp;
1007  mp_result res = MP_OK;
1008  mp_int qout,
1009  rout;
1010  mp_sign sa = MP_SIGN(a);
1011  mp_sign sb = MP_SIGN(b);
1012 
1013  if (CMPZ(b) == 0)
1014  {
1015  return MP_UNDEF;
1016  }
1017  else if ((cmp = s_ucmp(a, b)) < 0)
1018  {
1019  /*
1020  * If |a| < |b|, no division is required: q = 0, r = a
1021  */
1022  if (r && (res = mp_int_copy(a, r)) != MP_OK)
1023  return res;
1024 
1025  if (q)
1026  mp_int_zero(q);
1027 
1028  return MP_OK;
1029  }
1030  else if (cmp == 0)
1031  {
1032  /*
1033  * If |a| = |b|, no division is required: q = 1 or -1, r = 0
1034  */
1035  if (r)
1036  mp_int_zero(r);
1037 
1038  if (q)
1039  {
1040  mp_int_zero(q);
1041  q->digits[0] = 1;
1042 
1043  if (sa != sb)
1044  q->sign = MP_NEG;
1045  }
1046 
1047  return MP_OK;
1048  }
1049 
1050  /*
1051  * When |a| > |b|, real division is required. We need someplace to store
1052  * quotient and remainder, but q and r are allowed to be NULL or to
1053  * overlap with the inputs.
1054  */
1055  DECLARE_TEMP(2);
1056  int lg;
1057 
1058  if ((lg = s_isp2(b)) < 0)
1059  {
1060  if (q && b != q)
1061  {
1062  REQUIRE(mp_int_copy(a, q));
1063  qout = q;
1064  }
1065  else
1066  {
1067  REQUIRE(mp_int_copy(a, TEMP(0)));
1068  qout = TEMP(0);
1069  }
1070 
1071  if (r && a != r)
1072  {
1073  REQUIRE(mp_int_copy(b, r));
1074  rout = r;
1075  }
1076  else
1077  {
1078  REQUIRE(mp_int_copy(b, TEMP(1)));
1079  rout = TEMP(1);
1080  }
1081 
1082  REQUIRE(s_udiv_knuth(qout, rout));
1083  }
1084  else
1085  {
1086  if (q)
1087  REQUIRE(mp_int_copy(a, q));
1088  if (r)
1089  REQUIRE(mp_int_copy(a, r));
1090 
1091  if (q)
1092  s_qdiv(q, (mp_size) lg);
1093  qout = q;
1094  if (r)
1095  s_qmod(r, (mp_size) lg);
1096  rout = r;
1097  }
1098 
1099  /* Recompute signs for output */
1100  if (rout)
1101  {
1102  rout->sign = sa;
1103  if (CMPZ(rout) == 0)
1104  rout->sign = MP_ZPOS;
1105  }
1106  if (qout)
1107  {
1108  qout->sign = (sa == sb) ? MP_ZPOS : MP_NEG;
1109  if (CMPZ(qout) == 0)
1110  qout->sign = MP_ZPOS;
1111  }
1112 
1113  if (q)
1114  REQUIRE(mp_int_copy(qout, q));
1115  if (r)
1116  REQUIRE(mp_int_copy(rout, r));
1117  CLEANUP_TEMP();
1118  return res;
1119 }
#define DECLARE_TEMP(N)
Definition: imath.c:206
mp_digit * digits
Definition: imath.h:55
const mp_sign MP_NEG
Definition: imath.c:85
static mp_sign MP_SIGN(mp_int Z)
Definition: imath.h:79
static int CMPZ(mp_int Z)
Definition: imath.c:248
static void s_qmod(mp_int z, mp_size p2)
Definition: imath.c:2857
mp_result mp_int_copy(mp_int a, mp_int c)
Definition: imath.c:611
Definition: imath.h:52
const mp_sign MP_ZPOS
Definition: imath.c:86
#define CLEANUP_TEMP()
Definition: imath.c:222
#define REQUIRE(E)
Definition: imath.c:240
#define assert(TEST)
Definition: imath.c:73
void mp_int_zero(mp_int z)
Definition: imath.c:653
#define TEMP(K)
Definition: imath.c:234
static int s_isp2(mp_int z)
Definition: imath.c:3010
const mp_result MP_OK
Definition: imath.c:75
const mp_result MP_UNDEF
Definition: imath.c:80
static void s_qdiv(mp_int z, mp_size p2)
Definition: imath.c:2802
mp_sign sign
Definition: imath.h:58
unsigned char mp_sign
Definition: imath.h:32
static int s_ucmp(mp_int a, mp_int b)
Definition: imath.c:2342
int mp_result
Definition: imath.h:34
unsigned int mp_size
Definition: imath.h:33
static mp_result s_udiv_knuth(mp_int a, mp_int b)
Definition: imath.c:3248
static int cmp(const chr *x, const chr *y, size_t len)
Definition: regc_locale.c:742

◆ mp_int_div_pow2()

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

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

Definition at line 1159 of file imath.c.

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

Referenced by mp_int_is_even().

1160 {
1161  assert(a != NULL && p2 >= 0 && q != r);
1162 
1163  mp_result res = MP_OK;
1164 
1165  if (q != NULL && (res = mp_int_copy(a, q)) == MP_OK)
1166  {
1167  s_qdiv(q, (mp_size) p2);
1168  }
1169 
1170  if (res == MP_OK && r != NULL && (res = mp_int_copy(a, r)) == MP_OK)
1171  {
1172  s_qmod(r, (mp_size) p2);
1173  }
1174 
1175  return res;
1176 }
static void s_qmod(mp_int z, mp_size p2)
Definition: imath.c:2857
mp_result mp_int_copy(mp_int a, mp_int c)
Definition: imath.c:611
#define assert(TEST)
Definition: imath.c:73
const mp_result MP_OK
Definition: imath.c:75
static void s_qdiv(mp_int z, mp_size p2)
Definition: imath.c:2802
int mp_result
Definition: imath.h:34
unsigned int mp_size
Definition: imath.h:33

◆ mp_int_div_value()

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

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

Definition at line 1141 of file imath.c.

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

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

1142 {
1143  mpz_t vtmp;
1145 
1146  s_fake(&vtmp, value, vbuf);
1147 
1148  DECLARE_TEMP(1);
1149  REQUIRE(mp_int_div(a, &vtmp, q, TEMP(0)));
1150 
1151  if (r)
1152  (void) mp_int_to_int(TEMP(0), r); /* can't fail */
1153 
1154  CLEANUP_TEMP();
1155  return MP_OK;
1156 }
#define DECLARE_TEMP(N)
Definition: imath.c:206
static void s_fake(mp_int z, mp_small value, mp_digit vbuf[])
Definition: imath.c:2280
Definition: imath.h:52
static struct @145 value
#define MP_VALUE_DIGITS(V)
Definition: imath.c:119
#define CLEANUP_TEMP()
Definition: imath.c:222
#define REQUIRE(E)
Definition: imath.c:240
mp_result mp_int_div(mp_int a, mp_int b, mp_int q, mp_int r)
Definition: imath.c:1002
#define TEMP(K)
Definition: imath.c:234
const mp_result MP_OK
Definition: imath.c:75
uint32 mp_digit
Definition: imath.h:46
mp_result mp_int_to_int(mp_int z, mp_small *out)
Definition: imath.c:1822

◆ mp_int_divisible_value()

bool mp_int_divisible_value ( mp_int  a,
mp_small  v 
)

Reports whether a is divisible by v.

Definition at line 1738 of file imath.c.

References mp_int_div_value(), and MP_OK.

Referenced by mp_int_mod_value().

1739 {
1740  mp_small rem = 0;
1741 
1742  if (mp_int_div_value(a, v, NULL, &rem) != MP_OK)
1743  {
1744  return false;
1745  }
1746  return rem == 0;
1747 }
long mp_small
Definition: imath.h:35
mp_result mp_int_div_value(mp_int a, mp_small value, mp_int q, mp_small *r)
Definition: imath.c:1141
const mp_result MP_OK
Definition: imath.c:75

◆ mp_int_egcd()

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

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

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

Definition at line 1593 of file imath.c.

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

Referenced by mp_int_invmod(), and mp_int_mod_value().

1594 {
1595  assert(a != NULL && b != NULL && c != NULL && (x != NULL || y != NULL));
1596 
1597  mp_result res = MP_OK;
1598  int ca = CMPZ(a);
1599  int cb = CMPZ(b);
1600 
1601  if (ca == 0 && cb == 0)
1602  {
1603  return MP_UNDEF;
1604  }
1605  else if (ca == 0)
1606  {
1607  if ((res = mp_int_abs(b, c)) != MP_OK)
1608  return res;
1609  mp_int_zero(x);
1610  (void) mp_int_set_value(y, 1);
1611  return MP_OK;
1612  }
1613  else if (cb == 0)
1614  {
1615  if ((res = mp_int_abs(a, c)) != MP_OK)
1616  return res;
1617  (void) mp_int_set_value(x, 1);
1618  mp_int_zero(y);
1619  return MP_OK;
1620  }
1621 
1622  /*
1623  * Initialize temporaries: A:0, B:1, C:2, D:3, u:4, v:5, ou:6, ov:7
1624  */
1625  DECLARE_TEMP(8);
1626  REQUIRE(mp_int_set_value(TEMP(0), 1));
1627  REQUIRE(mp_int_set_value(TEMP(3), 1));
1628  REQUIRE(mp_int_copy(a, TEMP(4)));
1629  REQUIRE(mp_int_copy(b, TEMP(5)));
1630 
1631  /* We will work with absolute values here */
1632  TEMP(4)->sign = MP_ZPOS;
1633  TEMP(5)->sign = MP_ZPOS;
1634 
1635  int k = 0;
1636 
1637  { /* Divide out common factors of 2 from u and v */
1638  int div2_u = s_dp2k(TEMP(4)),
1639  div2_v = s_dp2k(TEMP(5));
1640 
1641  k = MIN(div2_u, div2_v);
1642  s_qdiv(TEMP(4), k);
1643  s_qdiv(TEMP(5), k);
1644  }
1645 
1646  REQUIRE(mp_int_copy(TEMP(4), TEMP(6)));
1647  REQUIRE(mp_int_copy(TEMP(5), TEMP(7)));
1648 
1649  for (;;)
1650  {
1651  while (mp_int_is_even(TEMP(4)))
1652  {
1653  s_qdiv(TEMP(4), 1);
1654 
1655  if (mp_int_is_odd(TEMP(0)) || mp_int_is_odd(TEMP(1)))
1656  {
1657  REQUIRE(mp_int_add(TEMP(0), TEMP(7), TEMP(0)));
1658  REQUIRE(mp_int_sub(TEMP(1), TEMP(6), TEMP(1)));
1659  }
1660 
1661  s_qdiv(TEMP(0), 1);
1662  s_qdiv(TEMP(1), 1);
1663  }
1664 
1665  while (mp_int_is_even(TEMP(5)))
1666  {
1667  s_qdiv(TEMP(5), 1);
1668 
1669  if (mp_int_is_odd(TEMP(2)) || mp_int_is_odd(TEMP(3)))
1670  {
1671  REQUIRE(mp_int_add(TEMP(2), TEMP(7), TEMP(2)));
1672  REQUIRE(mp_int_sub(TEMP(3), TEMP(6), TEMP(3)));
1673  }
1674 
1675  s_qdiv(TEMP(2), 1);
1676  s_qdiv(TEMP(3), 1);
1677  }
1678 
1679  if (mp_int_compare(TEMP(4), TEMP(5)) >= 0)
1680  {
1681  REQUIRE(mp_int_sub(TEMP(4), TEMP(5), TEMP(4)));
1682  REQUIRE(mp_int_sub(TEMP(0), TEMP(2), TEMP(0)));
1683  REQUIRE(mp_int_sub(TEMP(1), TEMP(3), TEMP(1)));
1684  }
1685  else
1686  {
1687  REQUIRE(mp_int_sub(TEMP(5), TEMP(4), TEMP(5)));
1688  REQUIRE(mp_int_sub(TEMP(2), TEMP(0), TEMP(2)));
1689  REQUIRE(mp_int_sub(TEMP(3), TEMP(1), TEMP(3)));
1690  }
1691 
1692  if (CMPZ(TEMP(4)) == 0)
1693  {
1694  if (x)
1695  REQUIRE(mp_int_copy(TEMP(2), x));
1696  if (y)
1697  REQUIRE(mp_int_copy(TEMP(3), y));
1698  if (c)
1699  {
1700  if (!s_qmul(TEMP(5), k))
1701  {
1702  REQUIRE(MP_MEMORY);
1703  }
1704  REQUIRE(mp_int_copy(TEMP(5), c));
1705  }
1706 
1707  break;
1708  }
1709  }
1710 
1711  CLEANUP_TEMP();
1712  return MP_OK;
1713 }
static int s_dp2k(mp_int z)
Definition: imath.c:2984
#define DECLARE_TEMP(N)
Definition: imath.c:206
static int s_qmul(mp_int z, mp_size p2)
Definition: imath.c:2873
static int CMPZ(mp_int Z)
Definition: imath.c:248
mp_result mp_int_copy(mp_int a, mp_int c)
Definition: imath.c:611
const mp_sign MP_ZPOS
Definition: imath.c:86
mp_result mp_int_sub(mp_int a, mp_int b, mp_int c)
Definition: imath.c:778
static bool mp_int_is_odd(mp_int z)
Definition: imath.h:122
#define CLEANUP_TEMP()
Definition: imath.c:222
mp_result mp_int_add(mp_int a, mp_int b, mp_int c)
Definition: imath.c:693
#define REQUIRE(E)
Definition: imath.c:240
#define assert(TEST)
Definition: imath.c:73
void mp_int_zero(mp_int z)
Definition: imath.c:653
#define TEMP(K)
Definition: imath.c:234
const mp_result MP_OK
Definition: imath.c:75
const mp_result MP_UNDEF
Definition: imath.c:80
static void s_qdiv(mp_int z, mp_size p2)
Definition: imath.c:2802
static bool mp_int_is_even(mp_int z)
Definition: imath.h:129
mp_result mp_int_abs(mp_int a, mp_int c)
Definition: imath.c:663
mp_result mp_int_set_value(mp_int z, mp_small value)
Definition: imath.c:567
int mp_result
Definition: imath.h:34
const mp_result MP_MEMORY
Definition: imath.c:78
static int MIN(int A, int B)
Definition: imath.c:182
int mp_int_compare(mp_int a, mp_int b)
Definition: imath.c:1274

◆ mp_int_expt()

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

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

Definition at line 1179 of file imath.c.

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

Referenced by mp_int_is_even(), and mp_int_root().

1180 {
1181  assert(c != NULL);
1182  if (b < 0)
1183  return MP_RANGE;
1184 
1185  DECLARE_TEMP(1);
1186  REQUIRE(mp_int_copy(a, TEMP(0)));
1187 
1188  (void) mp_int_set_value(c, 1);
1189  unsigned int v = labs(b);
1190 
1191  while (v != 0)
1192  {
1193  if (v & 1)
1194  {
1195  REQUIRE(mp_int_mul(c, TEMP(0), c));
1196  }
1197 
1198  v >>= 1;
1199  if (v == 0)
1200  break;
1201 
1202  REQUIRE(mp_int_sqr(TEMP(0), TEMP(0)));
1203  }
1204 
1205  CLEANUP_TEMP();
1206  return MP_OK;
1207 }
mp_result mp_int_mul(mp_int a, mp_int b, mp_int c)
Definition: imath.c:857
#define DECLARE_TEMP(N)
Definition: imath.c:206
mp_result mp_int_copy(mp_int a, mp_int c)
Definition: imath.c:611
const mp_result MP_RANGE
Definition: imath.c:79
#define CLEANUP_TEMP()
Definition: imath.c:222
#define REQUIRE(E)
Definition: imath.c:240
#define assert(TEST)
Definition: imath.c:73
#define TEMP(K)
Definition: imath.c:234
const mp_result MP_OK
Definition: imath.c:75
mp_result mp_int_sqr(mp_int a, mp_int c)
Definition: imath.c:954
mp_result mp_int_set_value(mp_int z, mp_small value)
Definition: imath.c:567

◆ mp_int_expt_full()

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

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

Definition at line 1241 of file imath.c.

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

Referenced by mp_int_is_even().

1242 {
1243  assert(a != NULL && b != NULL && c != NULL);
1244  if (MP_SIGN(b) == MP_NEG)
1245  return MP_RANGE;
1246 
1247  DECLARE_TEMP(1);
1248  REQUIRE(mp_int_copy(a, TEMP(0)));
1249 
1250  (void) mp_int_set_value(c, 1);
1251  for (unsigned ix = 0; ix < MP_USED(b); ++ix)
1252  {
1253  mp_digit d = b->digits[ix];
1254 
1255  for (unsigned jx = 0; jx < MP_DIGIT_BIT; ++jx)
1256  {
1257  if (d & 1)
1258  {
1259  REQUIRE(mp_int_mul(c, TEMP(0), c));
1260  }
1261 
1262  d >>= 1;
1263  if (d == 0 && ix + 1 == MP_USED(b))
1264  break;
1265  REQUIRE(mp_int_sqr(TEMP(0), TEMP(0)));
1266  }
1267  }
1268 
1269  CLEANUP_TEMP();
1270  return MP_OK;
1271 }
mp_result mp_int_mul(mp_int a, mp_int b, mp_int c)
Definition: imath.c:857
#define DECLARE_TEMP(N)
Definition: imath.c:206
static mp_size MP_USED(mp_int Z)
Definition: imath.h:74
mp_digit * digits
Definition: imath.h:55
const mp_sign MP_NEG
Definition: imath.c:85
static mp_sign MP_SIGN(mp_int Z)
Definition: imath.h:79
#define MP_DIGIT_BIT
Definition: imath.h:94
mp_result mp_int_copy(mp_int a, mp_int c)
Definition: imath.c:611
const mp_result MP_RANGE
Definition: imath.c:79
#define CLEANUP_TEMP()
Definition: imath.c:222
#define REQUIRE(E)
Definition: imath.c:240
#define assert(TEST)
Definition: imath.c:73
#define TEMP(K)
Definition: imath.c:234
const mp_result MP_OK
Definition: imath.c:75
mp_result mp_int_sqr(mp_int a, mp_int c)
Definition: imath.c:954
mp_result mp_int_set_value(mp_int z, mp_small value)
Definition: imath.c:567
uint32 mp_digit
Definition: imath.h:46

◆ mp_int_expt_value()

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

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

Definition at line 1210 of file imath.c.

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

Referenced by mp_int_is_even().

1211 {
1212  assert(c != NULL);
1213  if (b < 0)
1214  return MP_RANGE;
1215 
1216  DECLARE_TEMP(1);
1217  REQUIRE(mp_int_set_value(TEMP(0), a));
1218 
1219  (void) mp_int_set_value(c, 1);
1220  unsigned int v = labs(b);
1221 
1222  while (v != 0)
1223  {
1224  if (v & 1)
1225  {
1226  REQUIRE(mp_int_mul(c, TEMP(0), c));
1227  }
1228 
1229  v >>= 1;
1230  if (v == 0)
1231  break;
1232 
1233  REQUIRE(mp_int_sqr(TEMP(0), TEMP(0)));
1234  }
1235 
1236  CLEANUP_TEMP();
1237  return MP_OK;
1238 }
mp_result mp_int_mul(mp_int a, mp_int b, mp_int c)
Definition: imath.c:857
#define DECLARE_TEMP(N)
Definition: imath.c:206
const mp_result MP_RANGE
Definition: imath.c:79
#define CLEANUP_TEMP()
Definition: imath.c:222
#define REQUIRE(E)
Definition: imath.c:240
#define assert(TEST)
Definition: imath.c:73
#define TEMP(K)
Definition: imath.c:234
const mp_result MP_OK
Definition: imath.c:75
mp_result mp_int_sqr(mp_int a, mp_int c)
Definition: imath.c:954
mp_result mp_int_set_value(mp_int z, mp_small value)
Definition: imath.c:567

◆ mp_int_exptmod()

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

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

Definition at line 1369 of file imath.c.

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

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

1370 {
1371  assert(a != NULL && b != NULL && c != NULL && m != NULL);
1372 
1373  /* Zero moduli and negative exponents are not considered. */
1374  if (CMPZ(m) == 0)
1375  return MP_UNDEF;
1376  if (CMPZ(b) < 0)
1377  return MP_RANGE;
1378 
1379  mp_size um = MP_USED(m);
1380 
1381  DECLARE_TEMP(3);
1382  REQUIRE(GROW(TEMP(0), 2 * um));
1383  REQUIRE(GROW(TEMP(1), 2 * um));
1384 
1385  mp_int s;
1386 
1387  if (c == b || c == m)
1388  {
1389  REQUIRE(GROW(TEMP(2), 2 * um));
1390  s = TEMP(2);
1391  }
1392  else
1393  {
1394  s = c;
1395  }
1396 
1397  REQUIRE(mp_int_mod(a, m, TEMP(0)));
1398  REQUIRE(s_brmu(TEMP(1), m));
1399  REQUIRE(s_embar(TEMP(0), b, m, TEMP(1), s));
1400  REQUIRE(mp_int_copy(s, c));
1401 
1402  CLEANUP_TEMP();
1403  return MP_OK;
1404 }
#define DECLARE_TEMP(N)
Definition: imath.c:206
static mp_size MP_USED(mp_int Z)
Definition: imath.h:74
static int CMPZ(mp_int Z)
Definition: imath.c:248
mp_result mp_int_copy(mp_int a, mp_int c)
Definition: imath.c:611
Definition: imath.h:52
mp_result mp_int_mod(mp_int a, mp_int m, mp_int c)
Definition: imath.c:1122
const mp_result MP_RANGE
Definition: imath.c:79
static mp_result s_embar(mp_int a, mp_int b, mp_int m, mp_int mu, mp_int c)
Definition: imath.c:3149
#define CLEANUP_TEMP()
Definition: imath.c:222
char * c
#define REQUIRE(E)
Definition: imath.c:240
#define assert(TEST)
Definition: imath.c:73
#define TEMP(K)
Definition: imath.c:234
const mp_result MP_OK
Definition: imath.c:75
const mp_result MP_UNDEF
Definition: imath.c:80
static mp_result s_brmu(mp_int z, mp_int m)
Definition: imath.c:3081
static mp_result GROW(mp_int Z, mp_size N)
Definition: imath.c:313
unsigned int mp_size
Definition: imath.h:33

◆ mp_int_exptmod_bvalue()

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

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

Definition at line 1418 of file imath.c.

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

Referenced by mp_int_mod_value().

1419 {
1420  mpz_t vtmp;
1422 
1423  s_fake(&vtmp, value, vbuf);
1424 
1425  return mp_int_exptmod(&vtmp, b, m, c);
1426 }
static void s_fake(mp_int z, mp_small value, mp_digit vbuf[])
Definition: imath.c:2280
Definition: imath.h:52
static struct @145 value
#define MP_VALUE_DIGITS(V)
Definition: imath.c:119
mp_result mp_int_exptmod(mp_int a, mp_int b, mp_int m, mp_int c)
Definition: imath.c:1369
uint32 mp_digit
Definition: imath.h:46

◆ mp_int_exptmod_evalue()

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

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

Definition at line 1407 of file imath.c.

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

Referenced by mp_int_mod_value().

1408 {
1409  mpz_t vtmp;
1411 
1412  s_fake(&vtmp, value, vbuf);
1413 
1414  return mp_int_exptmod(a, &vtmp, m, c);
1415 }
static void s_fake(mp_int z, mp_small value, mp_digit vbuf[])
Definition: imath.c:2280
Definition: imath.h:52
static struct @145 value
#define MP_VALUE_DIGITS(V)
Definition: imath.c:119
mp_result mp_int_exptmod(mp_int a, mp_int b, mp_int m, mp_int c)
Definition: imath.c:1369
uint32 mp_digit
Definition: imath.h:46

◆ mp_int_exptmod_known()

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

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

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

Definition at line 1429 of file imath.c.

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

Referenced by mp_int_mod_value().

1431 {
1432  assert(a && b && m && c);
1433 
1434  /* Zero moduli and negative exponents are not considered. */
1435  if (CMPZ(m) == 0)
1436  return MP_UNDEF;
1437  if (CMPZ(b) < 0)
1438  return MP_RANGE;
1439 
1440  DECLARE_TEMP(2);
1441  mp_size um = MP_USED(m);
1442 
1443  REQUIRE(GROW(TEMP(0), 2 * um));
1444 
1445  mp_int s;
1446 
1447  if (c == b || c == m)
1448  {
1449  REQUIRE(GROW(TEMP(1), 2 * um));
1450  s = TEMP(1);
1451  }
1452  else
1453  {
1454  s = c;
1455  }
1456 
1457  REQUIRE(mp_int_mod(a, m, TEMP(0)));
1458  REQUIRE(s_embar(TEMP(0), b, m, mu, s));
1459  REQUIRE(mp_int_copy(s, c));
1460 
1461  CLEANUP_TEMP();
1462  return MP_OK;
1463 }
#define DECLARE_TEMP(N)
Definition: imath.c:206
static mp_size MP_USED(mp_int Z)
Definition: imath.h:74
static int CMPZ(mp_int Z)
Definition: imath.c:248
mp_result mp_int_copy(mp_int a, mp_int c)
Definition: imath.c:611
Definition: imath.h:52
mp_result mp_int_mod(mp_int a, mp_int m, mp_int c)
Definition: imath.c:1122
const mp_result MP_RANGE
Definition: imath.c:79
static mp_result s_embar(mp_int a, mp_int b, mp_int m, mp_int mu, mp_int c)
Definition: imath.c:3149
#define CLEANUP_TEMP()
Definition: imath.c:222
char * c
#define REQUIRE(E)
Definition: imath.c:240
#define assert(TEST)
Definition: imath.c:73
#define TEMP(K)
Definition: imath.c:234
const mp_result MP_OK
Definition: imath.c:75
const mp_result MP_UNDEF
Definition: imath.c:80
static mp_result GROW(mp_int Z, mp_size N)
Definition: imath.c:313
unsigned int mp_size
Definition: imath.h:33

◆ mp_int_free()

void mp_int_free ( mp_int  z)

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

Definition at line 602 of file imath.c.

References assert, mp_int_clear(), and px_free.

Referenced by mp_clear_free(), and mp_int_is_even().

603 {
604  assert(z != NULL);
605 
606  mp_int_clear(z);
607  px_free(z); /* note: NOT s_free() */
608 }
#define px_free(p)
Definition: px.h:46
#define assert(TEST)
Definition: imath.c:73
void mp_int_clear(mp_int z)
Definition: imath.c:587

◆ mp_int_gcd()

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

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

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

Definition at line 1514 of file imath.c.

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

Referenced by mp_int_lcm(), and mp_int_mod_value().

1515 {
1516  assert(a != NULL && b != NULL && c != NULL);
1517 
1518  int ca = CMPZ(a);
1519  int cb = CMPZ(b);
1520 
1521  if (ca == 0 && cb == 0)
1522  {
1523  return MP_UNDEF;
1524  }
1525  else if (ca == 0)
1526  {
1527  return mp_int_abs(b, c);
1528  }
1529  else if (cb == 0)
1530  {
1531  return mp_int_abs(a, c);
1532  }
1533 
1534  DECLARE_TEMP(3);
1535  REQUIRE(mp_int_copy(a, TEMP(0)));
1536  REQUIRE(mp_int_copy(b, TEMP(1)));
1537 
1538  TEMP(0)->sign = MP_ZPOS;
1539  TEMP(1)->sign = MP_ZPOS;
1540 
1541  int k = 0;
1542 
1543  { /* Divide out common factors of 2 from u and v */
1544  int div2_u = s_dp2k(TEMP(0));
1545  int div2_v = s_dp2k(TEMP(1));
1546 
1547  k = MIN(div2_u, div2_v);
1548  s_qdiv(TEMP(0), (mp_size) k);
1549  s_qdiv(TEMP(1), (mp_size) k);
1550  }
1551 
1552  if (mp_int_is_odd(TEMP(0)))
1553  {
1554  REQUIRE(mp_int_neg(TEMP(1), TEMP(2)));
1555  }
1556  else
1557  {
1558  REQUIRE(mp_int_copy(TEMP(0), TEMP(2)));
1559  }
1560 
1561  for (;;)
1562  {
1563  s_qdiv(TEMP(2), s_dp2k(TEMP(2)));
1564 
1565  if (CMPZ(TEMP(2)) > 0)
1566  {
1567  REQUIRE(mp_int_copy(TEMP(2), TEMP(0)));
1568  }
1569  else
1570  {
1571  REQUIRE(mp_int_neg(TEMP(2), TEMP(1)));
1572  }
1573 
1574  REQUIRE(mp_int_sub(TEMP(0), TEMP(1), TEMP(2)));
1575 
1576  if (CMPZ(TEMP(2)) == 0)
1577  break;
1578  }
1579 
1580  REQUIRE(mp_int_abs(TEMP(0), c));
1581  if (!s_qmul(c, (mp_size) k))
1582  REQUIRE(MP_MEMORY);
1583 
1584  CLEANUP_TEMP();
1585  return MP_OK;
1586 }
static int s_dp2k(mp_int z)
Definition: imath.c:2984
#define DECLARE_TEMP(N)
Definition: imath.c:206
static int s_qmul(mp_int z, mp_size p2)
Definition: imath.c:2873
static int CMPZ(mp_int Z)
Definition: imath.c:248
mp_result mp_int_copy(mp_int a, mp_int c)
Definition: imath.c:611
const mp_sign MP_ZPOS
Definition: imath.c:86
mp_result mp_int_sub(mp_int a, mp_int b, mp_int c)
Definition: imath.c:778
static bool mp_int_is_odd(mp_int z)
Definition: imath.h:122
#define CLEANUP_TEMP()
Definition: imath.c:222
#define REQUIRE(E)
Definition: imath.c:240
#define assert(TEST)
Definition: imath.c:73
#define TEMP(K)
Definition: imath.c:234
const mp_result MP_OK
Definition: imath.c:75
const mp_result MP_UNDEF
Definition: imath.c:80
static void s_qdiv(mp_int z, mp_size p2)
Definition: imath.c:2802
mp_result mp_int_neg(mp_int a, mp_int c)
Definition: imath.c:677
mp_result mp_int_abs(mp_int a, mp_int c)
Definition: imath.c:663
unsigned int mp_size
Definition: imath.h:33
const mp_result MP_MEMORY
Definition: imath.c:78
static int MIN(int A, int B)
Definition: imath.c:182

◆ mp_int_init()

mp_result mp_int_init ( mp_int  z)

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

Definition at line 464 of file imath.c.

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

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

465 {
466  if (z == NULL)
467  return MP_BADARG;
468 
469  z->single = 0;
470  z->digits = &(z->single);
471  z->alloc = 1;
472  z->used = 1;
473  z->sign = MP_ZPOS;
474 
475  return MP_OK;
476 }
mp_digit * digits
Definition: imath.h:55
mp_size alloc
Definition: imath.h:56
const mp_sign MP_ZPOS
Definition: imath.c:86
mp_digit single
Definition: imath.h:54
const mp_result MP_OK
Definition: imath.c:75
const mp_result MP_BADARG
Definition: imath.c:82
mp_sign sign
Definition: imath.h:58
mp_size used
Definition: imath.h:57

◆ mp_int_init_copy()

mp_result mp_int_init_copy ( mp_int  z,
mp_int  old 
)

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

Definition at line 520 of file imath.c.

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

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

521 {
522  assert(z != NULL && old != NULL);
523 
524  mp_size uold = MP_USED(old);
525 
526  if (uold == 1)
527  {
528  mp_int_init(z);
529  }
530  else
531  {
532  mp_size target = MAX(uold, default_precision);
533  mp_result res = mp_int_init_size(z, target);
534 
535  if (res != MP_OK)
536  return res;
537  }
538 
539  z->used = uold;
540  z->sign = old->sign;
541  COPY(MP_DIGITS(old), MP_DIGITS(z), uold);
542 
543  return MP_OK;
544 }
static mp_size default_precision
Definition: imath.c:281
static mp_size MP_USED(mp_int Z)
Definition: imath.h:74
static mp_size MAX(mp_size A, mp_size B)
Definition: imath.c:187
static void COPY(mp_digit *P, mp_digit *Q, mp_size S)
Definition: imath.c:141
mp_result mp_int_init(mp_int z)
Definition: imath.c:464
#define assert(TEST)
Definition: imath.c:73
mp_result mp_int_init_size(mp_int z, mp_size prec)
Definition: imath.c:490
const mp_result MP_OK
Definition: imath.c:75
mp_sign sign
Definition: imath.h:58
mp_size used
Definition: imath.h:57
int mp_result
Definition: imath.h:34
unsigned int mp_size
Definition: imath.h:33
static mp_digit * MP_DIGITS(mp_int Z)
Definition: imath.h:64

◆ mp_int_init_size()

mp_result mp_int_init_size ( mp_int  z,
mp_size  prec 
)

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

Definition at line 490 of file imath.c.

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

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

491 {
492  assert(z != NULL);
493 
494  if (prec == 0)
495  {
496  prec = default_precision;
497  }
498  else if (prec == 1)
499  {
500  return mp_int_init(z);
501  }
502  else
503  {
504  prec = s_round_prec(prec);
505  }
506 
507  z->digits = s_alloc(prec);
508  if (MP_DIGITS(z) == NULL)
509  return MP_MEMORY;
510 
511  z->digits[0] = 0;
512  z->used = 1;
513  z->alloc = prec;
514  z->sign = MP_ZPOS;
515 
516  return MP_OK;
517 }
static mp_size default_precision
Definition: imath.c:281
mp_digit * digits
Definition: imath.h:55
mp_size alloc
Definition: imath.h:56
static mp_size s_round_prec(mp_size P)
Definition: imath.c:124
const mp_sign MP_ZPOS
Definition: imath.c:86
mp_result mp_int_init(mp_int z)
Definition: imath.c:464
static mp_digit * s_alloc(mp_size num)
Definition: imath.c:2213
#define assert(TEST)
Definition: imath.c:73
const mp_result MP_OK
Definition: imath.c:75
mp_sign sign
Definition: imath.h:58
mp_size used
Definition: imath.h:57
static mp_digit * MP_DIGITS(mp_int Z)
Definition: imath.h:64
const mp_result MP_MEMORY
Definition: imath.c:78

◆ mp_int_init_uvalue()

mp_result mp_int_init_uvalue ( mp_int  z,
mp_usmall  uvalue 
)

Initializes z to the specified unsigned value at default precision.

Definition at line 557 of file imath.c.

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

Referenced by mp_int_is_even().

558 {
559  mpz_t vtmp;
560  mp_digit vbuf[MP_VALUE_DIGITS(uvalue)];
561 
562  s_ufake(&vtmp, uvalue, vbuf);
563  return mp_int_init_copy(z, &vtmp);
564 }
static void s_ufake(mp_int z, mp_usmall value, mp_digit vbuf[])
Definition: imath.c:2290
Definition: imath.h:52
#define MP_VALUE_DIGITS(V)
Definition: imath.c:119
mp_result mp_int_init_copy(mp_int z, mp_int old)
Definition: imath.c:520
uint32 mp_digit
Definition: imath.h:46

◆ mp_int_init_value()

mp_result mp_int_init_value ( mp_int  z,
mp_small  value 
)

Initializes z to the specified signed value at default precision.

Definition at line 547 of file imath.c.

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

Referenced by mp_int_is_even().

548 {
549  mpz_t vtmp;
551 
552  s_fake(&vtmp, value, vbuf);
553  return mp_int_init_copy(z, &vtmp);
554 }
static void s_fake(mp_int z, mp_small value, mp_digit vbuf[])
Definition: imath.c:2280
Definition: imath.h:52
static struct @145 value
#define MP_VALUE_DIGITS(V)
Definition: imath.c:119
mp_result mp_int_init_copy(mp_int z, mp_int old)
Definition: imath.c:520
uint32 mp_digit
Definition: imath.h:46

◆ mp_int_invmod()

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

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

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

Definition at line 1474 of file imath.c.

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

Referenced by mp_int_mod_value(), and pgp_elgamal_decrypt().

1475 {
1476  assert(a != NULL && m != NULL && c != NULL);
1477 
1478  if (CMPZ(a) == 0 || CMPZ(m) <= 0)
1479  return MP_RANGE;
1480 
1481  DECLARE_TEMP(2);
1482 
1483  REQUIRE(mp_int_egcd(a, m, TEMP(0), TEMP(1), NULL));
1484 
1485  if (mp_int_compare_value(TEMP(0), 1) != 0)
1486  {
1487  REQUIRE(MP_UNDEF);
1488  }
1489 
1490  /* It is first necessary to constrain the value to the proper range */
1491  REQUIRE(mp_int_mod(TEMP(1), m, TEMP(1)));
1492 
1493  /*
1494  * Now, if 'a' was originally negative, the value we have is actually the
1495  * magnitude of the negative representative; to get the positive value we
1496  * have to subtract from the modulus. Otherwise, the value is okay as it
1497  * stands.
1498  */
1499  if (MP_SIGN(a) == MP_NEG)
1500  {
1501  REQUIRE(mp_int_sub(m, TEMP(1), c));
1502  }
1503  else
1504  {
1505  REQUIRE(mp_int_copy(TEMP(1), c));
1506  }
1507 
1508  CLEANUP_TEMP();
1509  return MP_OK;
1510 }
#define DECLARE_TEMP(N)
Definition: imath.c:206
const mp_sign MP_NEG
Definition: imath.c:85
static mp_sign MP_SIGN(mp_int Z)
Definition: imath.h:79
static int CMPZ(mp_int Z)
Definition: imath.c:248
mp_result mp_int_copy(mp_int a, mp_int c)
Definition: imath.c:611
mp_result mp_int_mod(mp_int a, mp_int m, mp_int c)
Definition: imath.c:1122
const mp_result MP_RANGE
Definition: imath.c:79
mp_result mp_int_sub(mp_int a, mp_int b, mp_int c)
Definition: imath.c:778
#define CLEANUP_TEMP()
Definition: imath.c:222
#define REQUIRE(E)
Definition: imath.c:240
#define assert(TEST)
Definition: imath.c:73
#define TEMP(K)
Definition: imath.c:234
int mp_int_compare_value(mp_int z, mp_small value)
Definition: imath.c:1335
const mp_result MP_OK
Definition: imath.c:75
const mp_result MP_UNDEF
Definition: imath.c:80
mp_result mp_int_egcd(mp_int a, mp_int b, mp_int c, mp_int x, mp_int y)
Definition: imath.c:1593

◆ mp_int_is_pow2()

int mp_int_is_pow2 ( mp_int  z)

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

Definition at line 1750 of file imath.c.

References assert, and s_isp2().

Referenced by mp_int_mod_value().

1751 {
1752  assert(z != NULL);
1753 
1754  return s_isp2(z);
1755 }
#define assert(TEST)
Definition: imath.c:73
static int s_isp2(mp_int z)
Definition: imath.c:3010

◆ mp_int_lcm()

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

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

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

Definition at line 1716 of file imath.c.

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

Referenced by mp_int_mod_value().

1717 {
1718  assert(a != NULL && b != NULL && c != NULL);
1719 
1720  /*
1721  * Since a * b = gcd(a, b) * lcm(a, b), we can compute lcm(a, b) = (a /
1722  * gcd(a, b)) * b.
1723  *
1724  * This formulation insures everything works even if the input variables
1725  * share space.
1726  */
1727  DECLARE_TEMP(1);
1728  REQUIRE(mp_int_gcd(a, b, TEMP(0)));
1729  REQUIRE(mp_int_div(a, TEMP(0), TEMP(0), NULL));
1730  REQUIRE(mp_int_mul(TEMP(0), b, TEMP(0)));
1731  REQUIRE(mp_int_copy(TEMP(0), c));
1732 
1733  CLEANUP_TEMP();
1734  return MP_OK;
1735 }
mp_result mp_int_mul(mp_int a, mp_int b, mp_int c)
Definition: imath.c:857
#define DECLARE_TEMP(N)
Definition: imath.c:206
mp_result mp_int_gcd(mp_int a, mp_int b, mp_int c)
Definition: imath.c:1514
mp_result mp_int_copy(mp_int a, mp_int c)
Definition: imath.c:611
#define CLEANUP_TEMP()
Definition: imath.c:222
#define REQUIRE(E)
Definition: imath.c:240
mp_result mp_int_div(mp_int a, mp_int b, mp_int q, mp_int r)
Definition: imath.c:1002
#define assert(TEST)
Definition: imath.c:73
#define TEMP(K)
Definition: imath.c:234
const mp_result MP_OK
Definition: imath.c:75

◆ mp_int_mod()

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

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

Definition at line 1122 of file imath.c.

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

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

1123 {
1124  DECLARE_TEMP(1);
1125  mp_int out = (m == c) ? TEMP(0) : c;
1126 
1127  REQUIRE(mp_int_div(a, m, NULL, out));
1128  if (CMPZ(out) < 0)
1129  {
1130  REQUIRE(mp_int_add(out, m, c));
1131  }
1132  else
1133  {
1134  REQUIRE(mp_int_copy(out, c));
1135  }
1136  CLEANUP_TEMP();
1137  return MP_OK;
1138 }
#define DECLARE_TEMP(N)
Definition: imath.c:206
static int CMPZ(mp_int Z)
Definition: imath.c:248
mp_result mp_int_copy(mp_int a, mp_int c)
Definition: imath.c:611
Definition: imath.h:52
#define CLEANUP_TEMP()
Definition: imath.c:222
char * c
mp_result mp_int_add(mp_int a, mp_int b, mp_int c)
Definition: imath.c:693
#define REQUIRE(E)
Definition: imath.c:240
mp_result mp_int_div(mp_int a, mp_int b, mp_int q, mp_int r)
Definition: imath.c:1002
#define TEMP(K)
Definition: imath.c:234
const mp_result MP_OK
Definition: imath.c:75

◆ mp_int_mul()

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

Sets c to the product of a and b.

Definition at line 857 of file imath.c.

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

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

858 {
859  assert(a != NULL && b != NULL && c != NULL);
860 
861  /* If either input is zero, we can shortcut multiplication */
862  if (mp_int_compare_zero(a) == 0 || mp_int_compare_zero(b) == 0)
863  {
864  mp_int_zero(c);
865  return MP_OK;
866  }
867 
868  /* Output is positive if inputs have same sign, otherwise negative */
869  mp_sign osign = (MP_SIGN(a) == MP_SIGN(b)) ? MP_ZPOS : MP_NEG;
870 
871  /*
872  * If the output is not identical to any of the inputs, we'll write the
873  * results directly; otherwise, allocate a temporary space.
874  */
875  mp_size ua = MP_USED(a);
876  mp_size ub = MP_USED(b);
877  mp_size osize = MAX(ua, ub);
878 
879  osize = 4 * ((osize + 1) / 2);
880 
881  mp_digit *out;
882  mp_size p = 0;
883 
884  if (c == a || c == b)
885  {
886  p = MAX(s_round_prec(osize), default_precision);
887 
888  if ((out = s_alloc(p)) == NULL)
889  return MP_MEMORY;
890  }
891  else
892  {
893  if (!s_pad(c, osize))
894  return MP_MEMORY;
895 
896  out = MP_DIGITS(c);
897  }
898  ZERO(out, osize);
899 
900  if (!s_kmul(MP_DIGITS(a), MP_DIGITS(b), out, ua, ub))
901  return MP_MEMORY;
902 
903  /*
904  * If we allocated a new buffer, get rid of whatever memory c was already
905  * using, and fix up its fields to reflect that.
906  */
907  if (out != MP_DIGITS(c))
908  {
909  if ((void *) MP_DIGITS(c) != (void *) c)
910  s_free(MP_DIGITS(c));
911  c->digits = out;
912  c->alloc = p;
913  }
914 
915  c->used = osize; /* might not be true, but we'll fix it ... */
916  CLAMP(c); /* ... right here */
917  c->sign = osign;
918 
919  return MP_OK;
920 }
static void ZERO(mp_digit *P, mp_size S)
Definition: imath.c:131
static mp_size default_precision
Definition: imath.c:281
static mp_size MP_USED(mp_int Z)
Definition: imath.h:74
const mp_sign MP_NEG
Definition: imath.c:85
static mp_sign MP_SIGN(mp_int Z)
Definition: imath.h:79
static mp_size s_round_prec(mp_size P)
Definition: imath.c:124
static mp_size MAX(mp_size A, mp_size B)
Definition: imath.c:187
const mp_sign MP_ZPOS
Definition: imath.c:86
int mp_int_compare_zero(mp_int z)
Definition: imath.c:1316
static mp_digit * s_alloc(mp_size num)
Definition: imath.c:2213
#define assert(TEST)
Definition: imath.c:73
void mp_int_zero(mp_int z)
Definition: imath.c:653
static void CLAMP(mp_int z_)
Definition: imath.c:168
const mp_result MP_OK
Definition: imath.c:75
static bool s_pad(mp_int z, mp_size min)
Definition: imath.c:2253
unsigned char mp_sign
Definition: imath.h:32
unsigned int mp_size
Definition: imath.h:33
static mp_digit * MP_DIGITS(mp_int Z)
Definition: imath.h:64
const mp_result MP_MEMORY
Definition: imath.c:78
uint32 mp_digit
Definition: imath.h:46
static void s_free(void *ptr)
Definition: imath.c:2247
static int s_kmul(mp_digit *da, mp_digit *db, mp_digit *dc, mp_size size_a, mp_size size_b)
Definition: imath.c:2458

◆ mp_int_mul_pow2()

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

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

Definition at line 934 of file imath.c.

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

Referenced by mp_int_is_even().

935 {
936  assert(a != NULL && c != NULL && p2 >= 0);
937 
938  mp_result res = mp_int_copy(a, c);
939 
940  if (res != MP_OK)
941  return res;
942 
943  if (s_qmul(c, (mp_size) p2))
944  {
945  return MP_OK;
946  }
947  else
948  {
949  return MP_MEMORY;
950  }
951 }
static int s_qmul(mp_int z, mp_size p2)
Definition: imath.c:2873
mp_result mp_int_copy(mp_int a, mp_int c)
Definition: imath.c:611
#define assert(TEST)
Definition: imath.c:73
const mp_result MP_OK
Definition: imath.c:75
int mp_result
Definition: imath.h:34
unsigned int mp_size
Definition: imath.h:33
const mp_result MP_MEMORY
Definition: imath.c:78

◆ mp_int_mul_value()

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

Sets c to the product of a and value.

Definition at line 923 of file imath.c.

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

Referenced by mp_int_is_even(), and mp_int_root().

924 {
925  mpz_t vtmp;
927 
928  s_fake(&vtmp, value, vbuf);
929 
930  return mp_int_mul(a, &vtmp, c);
931 }
mp_result mp_int_mul(mp_int a, mp_int b, mp_int c)
Definition: imath.c:857
static void s_fake(mp_int z, mp_small value, mp_digit vbuf[])
Definition: imath.c:2280
Definition: imath.h:52
static struct @145 value
#define MP_VALUE_DIGITS(V)
Definition: imath.c:119
uint32 mp_digit
Definition: imath.h:46

◆ mp_int_multiply_threshold()

void mp_int_multiply_threshold ( mp_size  ndigits)

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

Definition at line 294 of file imath.c.

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

295 {
296  assert(thresh >= sizeof(mp_word));
297  multiply_threshold = thresh;
298 }
static mp_size multiply_threshold
Definition: imath.c:291
#define assert(TEST)
Definition: imath.c:73
uint64 mp_word
Definition: imath.h:47

◆ mp_int_neg()

mp_result mp_int_neg ( mp_int  a,
mp_int  c 
)

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

Definition at line 677 of file imath.c.

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

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

678 {
679  assert(a != NULL && c != NULL);
680 
681  mp_result res;
682 
683  if ((res = mp_int_copy(a, c)) != MP_OK)
684  return res;
685 
686  if (CMPZ(c) != 0)
687  c->sign = 1 - MP_SIGN(a);
688 
689  return MP_OK;
690 }
static mp_sign MP_SIGN(mp_int Z)
Definition: imath.h:79
static int CMPZ(mp_int Z)
Definition: imath.c:248
mp_result mp_int_copy(mp_int a, mp_int c)
Definition: imath.c:611
#define assert(TEST)
Definition: imath.c:73
const mp_result MP_OK
Definition: imath.c:75
mp_sign sign
Definition: imath.h:58
int mp_result
Definition: imath.h:34

◆ mp_int_read_binary()

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

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

Definition at line 2077 of file imath.c.

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

Referenced by mp_int_sqrt().

2078 {
2079  assert(z != NULL && buf != NULL && len > 0);
2080 
2081  /* Figure out how many digits are needed to represent this value */
2082  mp_size need = ((len * CHAR_BIT) + (MP_DIGIT_BIT - 1)) / MP_DIGIT_BIT;
2083 
2084  if (!s_pad(z, need))
2085  return MP_MEMORY;
2086 
2087  mp_int_zero(z);
2088 
2089  /*
2090  * If the high-order bit is set, take the 2's complement before reading
2091  * the value (it will be restored afterward)
2092  */
2093  if (buf[0] >> (CHAR_BIT - 1))
2094  {
2095  z->sign = MP_NEG;
2096  s_2comp(buf, len);
2097  }
2098 
2099  mp_digit *dz = MP_DIGITS(z);
2100  unsigned char *tmp = buf;
2101 
2102  for (int i = len; i > 0; --i, ++tmp)
2103  {
2104  s_qmul(z, (mp_size) CHAR_BIT);
2105  *dz |= *tmp;
2106  }
2107 
2108  /* Restore 2's complement if we took it before */
2109  if (MP_SIGN(z) == MP_NEG)
2110  s_2comp(buf, len);
2111 
2112  return MP_OK;
2113 }
const mp_sign MP_NEG
Definition: imath.c:85
static int s_qmul(mp_int z, mp_size p2)
Definition: imath.c:2873
static mp_sign MP_SIGN(mp_int Z)
Definition: imath.h:79
#define MP_DIGIT_BIT
Definition: imath.h:94
static void s_2comp(unsigned char *buf, int len)
Definition: imath.c:3519
static char * buf
Definition: pg_test_fsync.c:68
#define assert(TEST)
Definition: imath.c:73
void mp_int_zero(mp_int z)
Definition: imath.c:653
const mp_result MP_OK
Definition: imath.c:75
mp_sign sign
Definition: imath.h:58
static bool s_pad(mp_int z, mp_size min)
Definition: imath.c:2253
unsigned int mp_size
Definition: imath.h:33
int i
static mp_digit * MP_DIGITS(mp_int Z)
Definition: imath.h:64
const mp_result MP_MEMORY
Definition: imath.c:78
uint32 mp_digit
Definition: imath.h:46

◆ mp_int_read_cstring()

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

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

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

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

Requires MP_MIN_RADIX <= radix <= MP_MAX_RADIX.

Definition at line 1970 of file imath.c.

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

Referenced by mp_int_read_string(), and mp_int_sqrt().

1972 {
1973  assert(z != NULL && str != NULL);
1974  assert(radix >= MP_MIN_RADIX && radix <= MP_MAX_RADIX);
1975 
1976  /* Skip leading whitespace */
1977  while (isspace((unsigned char) *str))
1978  ++str;
1979 
1980  /* Handle leading sign tag (+/-, positive default) */
1981  switch (*str)
1982  {
1983  case '-':
1984  z->sign = MP_NEG;
1985  ++str;
1986  break;
1987  case '+':
1988  ++str; /* fallthrough */
1989  default:
1990  z->sign = MP_ZPOS;
1991  break;
1992  }
1993 
1994  /* Skip leading zeroes */
1995  int ch;
1996 
1997  while ((ch = s_ch2val(*str, radix)) == 0)
1998  ++str;
1999 
2000  /* Make sure there is enough space for the value */
2001  if (!s_pad(z, s_inlen(strlen(str), radix)))
2002  return MP_MEMORY;
2003 
2004  z->used = 1;
2005  z->digits[0] = 0;
2006 
2007  while (*str != '\0' && ((ch = s_ch2val(*str, radix)) >= 0))
2008  {
2009  s_dmul(z, (mp_digit) radix);
2010  s_dadd(z, (mp_digit) ch);
2011  ++str;
2012  }
2013 
2014  CLAMP(z);
2015 
2016  /* Override sign for zero, even if negative specified. */
2017  if (CMPZ(z) == 0)
2018  z->sign = MP_ZPOS;
2019 
2020  if (end != NULL)
2021  *end = unconstify(char *, str);
2022 
2023  /*
2024  * Return a truncation error if the string has unprocessed characters
2025  * remaining, so the caller can tell if the whole string was done
2026  */
2027  if (*str != '\0')
2028  {
2029  return MP_TRUNC;
2030  }
2031  else
2032  {
2033  return MP_OK;
2034  }
2035 }
mp_digit * digits
Definition: imath.h:55
const mp_sign MP_NEG
Definition: imath.c:85
static int CMPZ(mp_int Z)
Definition: imath.c:248
const mp_sign MP_ZPOS
Definition: imath.c:86
static mp_size s_inlen(int len, mp_size r)
Definition: imath.c:3465
const mp_result MP_TRUNC
Definition: imath.c:81
#define MP_MIN_RADIX
Definition: imath.h:100
#define assert(TEST)
Definition: imath.c:73
static void s_dadd(mp_int a, mp_digit b)
Definition: imath.c:2707
#define unconstify(underlying_type, expr)
Definition: c.h:1163
static void CLAMP(mp_int z_)
Definition: imath.c:168
const mp_result MP_OK
Definition: imath.c:75
mp_sign sign
Definition: imath.h:58
static bool s_pad(mp_int z, mp_size min)
Definition: imath.c:2253
mp_size used
Definition: imath.h:57
static int s_ch2val(char c, int r)
Definition: imath.c:3474
static void s_dmul(mp_int a, mp_digit b)
Definition: imath.c:2733
const mp_result MP_MEMORY
Definition: imath.c:78
uint32 mp_digit
Definition: imath.h:46
#define MP_MAX_RADIX
Definition: imath.h:101

◆ mp_int_read_string()

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

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

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

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

Requires MP_MIN_RADIX <= radix <= MP_MAX_RADIX.

Definition at line 1964 of file imath.c.

References mp_int_read_cstring().

Referenced by mp_int_sqrt().

1965 {
1966  return mp_int_read_cstring(z, radix, str, NULL);
1967 }
mp_result mp_int_read_cstring(mp_int z, mp_size radix, const char *str, char **end)
Definition: imath.c:1970

◆ mp_int_read_unsigned()

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

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

Definition at line 2147 of file imath.c.

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

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

2148 {
2149  assert(z != NULL && buf != NULL && len > 0);
2150 
2151  /* Figure out how many digits are needed to represent this value */
2152  mp_size need = ((len * CHAR_BIT) + (MP_DIGIT_BIT - 1)) / MP_DIGIT_BIT;
2153 
2154  if (!s_pad(z, need))
2155  return MP_MEMORY;
2156 
2157  mp_int_zero(z);
2158 
2159  unsigned char *tmp = buf;
2160 
2161  for (int i = len; i > 0; --i, ++tmp)
2162  {
2163  (void) s_qmul(z, CHAR_BIT);
2164  *MP_DIGITS(z) |= *tmp;
2165  }
2166 
2167  return MP_OK;
2168 }
static int s_qmul(mp_int z, mp_size p2)
Definition: imath.c:2873
#define MP_DIGIT_BIT
Definition: imath.h:94
static char * buf
Definition: pg_test_fsync.c:68
#define assert(TEST)
Definition: imath.c:73
void mp_int_zero(mp_int z)
Definition: imath.c:653
const mp_result MP_OK
Definition: imath.c:75
static bool s_pad(mp_int z, mp_size min)
Definition: imath.c:2253
unsigned int mp_size
Definition: imath.h:33
int i
static mp_digit * MP_DIGITS(mp_int Z)
Definition: imath.h:64
const mp_result MP_MEMORY
Definition: imath.c:78

◆ mp_int_redux_const()

mp_result mp_int_redux_const ( mp_int  m,
mp_int  c 
)

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

Definition at line 1466 of file imath.c.

References assert, and s_brmu().

Referenced by mp_int_mod_value().

1467 {
1468  assert(m != NULL && c != NULL && m != c);
1469 
1470  return s_brmu(c, m);
1471 }
#define assert(TEST)
Definition: imath.c:73
static mp_result s_brmu(mp_int z, mp_int m)
Definition: imath.c:3081

◆ mp_int_root()

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

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

Definition at line 1762 of file imath.c.

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

Referenced by mp_int_mod_value(), and mp_int_sqrt().

1763 {
1764  assert(a != NULL && c != NULL && b > 0);
1765 
1766  if (b == 1)
1767  {
1768  return mp_int_copy(a, c);
1769  }
1770  bool flips = false;
1771 
1772  if (MP_SIGN(a) == MP_NEG)
1773  {
1774  if (b % 2 == 0)
1775  {
1776  return MP_UNDEF; /* root does not exist for negative a with
1777  * even b */
1778  }
1779  else
1780  {
1781  flips = true;
1782  }
1783  }
1784 
1785  DECLARE_TEMP(5);
1786  REQUIRE(mp_int_copy(a, TEMP(0)));
1787  REQUIRE(mp_int_copy(a, TEMP(1)));
1788  TEMP(0)->sign = MP_ZPOS;
1789  TEMP(1)->sign = MP_ZPOS;
1790 
1791  for (;;)
1792  {
1793  REQUIRE(mp_int_expt(TEMP(1), b, TEMP(2)));
1794 
1795  if (mp_int_compare_unsigned(TEMP(2), TEMP(0)) <= 0)
1796  break;
1797 
1798  REQUIRE(mp_int_sub(TEMP(2), TEMP(0), TEMP(2)));
1799  REQUIRE(mp_int_expt(TEMP(1), b - 1, TEMP(3)));
1800  REQUIRE(mp_int_mul_value(TEMP(3), b, TEMP(3)));
1801  REQUIRE(mp_int_div(TEMP(2), TEMP(3), TEMP(4), NULL));
1802  REQUIRE(mp_int_sub(TEMP(1), TEMP(4), TEMP(4)));
1803 
1804  if (mp_int_compare_unsigned(TEMP(1), TEMP(4)) == 0)
1805  {
1806  REQUIRE(mp_int_sub_value(TEMP(4), 1, TEMP(4)));
1807  }
1808  REQUIRE(mp_int_copy(TEMP(4), TEMP(1)));
1809  }
1810 
1811  REQUIRE(mp_int_copy(TEMP(1), c));
1812 
1813  /* If the original value of a was negative, flip the output sign. */
1814  if (flips)
1815  (void) mp_int_neg(c, c); /* cannot fail */
1816 
1817  CLEANUP_TEMP();
1818  return MP_OK;
1819 }
int mp_int_compare_unsigned(mp_int a, mp_int b)
Definition: imath.c:1308
#define DECLARE_TEMP(N)
Definition: imath.c:206
const mp_sign MP_NEG
Definition: imath.c:85
static mp_sign MP_SIGN(mp_int Z)
Definition: imath.h:79
mp_result mp_int_mul_value(mp_int a, mp_small value, mp_int c)
Definition: imath.c:923
mp_result mp_int_copy(mp_int a, mp_int c)
Definition: imath.c:611
mp_result mp_int_expt(mp_int a, mp_small b, mp_int c)
Definition: imath.c:1179
mp_result mp_int_sub_value(mp_int a, mp_small value, mp_int c)
Definition: imath.c:846
const mp_sign MP_ZPOS
Definition: imath.c:86
mp_result mp_int_sub(mp_int a, mp_int b, mp_int c)
Definition: imath.c:778
#define CLEANUP_TEMP()
Definition: imath.c:222
#define REQUIRE(E)
Definition: imath.c:240
mp_result mp_int_div(mp_int a, mp_int b, mp_int q, mp_int r)
Definition: imath.c:1002
#define assert(TEST)
Definition: imath.c:73
#define TEMP(K)
Definition: imath.c:234
const mp_result MP_OK
Definition: imath.c:75
const mp_result MP_UNDEF
Definition: imath.c:80
mp_result mp_int_neg(mp_int a, mp_int c)
Definition: imath.c:677

◆ mp_int_set_uvalue()

mp_result mp_int_set_uvalue ( mp_int  z,
mp_usmall  uvalue 
)

Sets z to the value of the specified unsigned value.

Definition at line 577 of file imath.c.

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

Referenced by mp_int_is_even().

578 {
579  mpz_t vtmp;
580  mp_digit vbuf[MP_VALUE_DIGITS(uvalue)];
581 
582  s_ufake(&vtmp, uvalue, vbuf);
583  return mp_int_copy(&vtmp, z);
584 }
static void s_ufake(mp_int z, mp_usmall value, mp_digit vbuf[])
Definition: imath.c:2290
mp_result mp_int_copy(mp_int a, mp_int c)
Definition: imath.c:611
Definition: imath.h:52
#define MP_VALUE_DIGITS(V)
Definition: imath.c:119
uint32 mp_digit
Definition: imath.h:46

◆ mp_int_set_value()

mp_result mp_int_set_value ( mp_int  z,
mp_small  value 
)

Sets z to the value of the specified signed value.

Definition at line 567 of file imath.c.

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

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

568 {
569  mpz_t vtmp;
571 
572  s_fake(&vtmp, value, vbuf);
573  return mp_int_copy(&vtmp, z);
574 }
static void s_fake(mp_int z, mp_small value, mp_digit vbuf[])
Definition: imath.c:2280
mp_result mp_int_copy(mp_int a, mp_int c)
Definition: imath.c:611
Definition: imath.h:52
static struct @145 value
#define MP_VALUE_DIGITS(V)
Definition: imath.c:119
uint32 mp_digit
Definition: imath.h:46

◆ mp_int_sqr()

mp_result mp_int_sqr ( mp_int  a,
mp_int  c 
)

Sets c to the square of a.

Definition at line 954 of file imath.c.

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

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

955 {
956  assert(a != NULL && c != NULL);
957 
958  /* Get a temporary buffer big enough to hold the result */
959  mp_size osize = (mp_size) 4 * ((MP_USED(a) + 1) / 2);
960  mp_size p = 0;
961  mp_digit *out;
962 
963  if (a == c)
964  {
965  p = s_round_prec(osize);
966  p = MAX(p, default_precision);
967 
968  if ((out = s_alloc(p)) == NULL)
969  return MP_MEMORY;
970  }
971  else
972  {
973  if (!s_pad(c, osize))
974  return MP_MEMORY;
975 
976  out = MP_DIGITS(c);
977  }
978  ZERO(out, osize);
979 
980  s_ksqr(MP_DIGITS(a), out, MP_USED(a));
981 
982  /*
983  * Get rid of whatever memory c was already using, and fix up its fields
984  * to reflect the new digit array it's using
985  */
986  if (out != MP_DIGITS(c))
987  {
988  if ((void *) MP_DIGITS(c) != (void *) c)
989  s_free(MP_DIGITS(c));
990  c->digits = out;
991  c->alloc = p;
992  }
993 
994  c->used = osize; /* might not be true, but we'll fix it ... */
995  CLAMP(c); /* ... right here */
996  c->sign = MP_ZPOS;
997 
998  return MP_OK;
999 }
static void ZERO(mp_digit *P, mp_size S)
Definition: imath.c:131
static mp_size default_precision
Definition: imath.c:281
static mp_size MP_USED(mp_int Z)
Definition: imath.h:74
static mp_size s_round_prec(mp_size P)
Definition: imath.c:124
static mp_size MAX(mp_size A, mp_size B)
Definition: imath.c:187
const mp_sign MP_ZPOS
Definition: imath.c:86
static mp_digit * s_alloc(mp_size num)
Definition: imath.c:2213
#define assert(TEST)
Definition: imath.c:73
static void CLAMP(mp_int z_)
Definition: imath.c:168
const mp_result MP_OK
Definition: imath.c:75
static bool s_pad(mp_int z, mp_size min)
Definition: imath.c:2253
unsigned int mp_size
Definition: imath.h:33
static int s_ksqr(mp_digit *da, mp_digit *dc, mp_size size_a)
Definition: imath.c:2582
static mp_digit * MP_DIGITS(mp_int Z)
Definition: imath.h:64
const mp_result MP_MEMORY
Definition: imath.c:78
uint32 mp_digit
Definition: imath.h:46
static void s_free(void *ptr)
Definition: imath.c:2247

◆ mp_int_string_len()

mp_result mp_int_string_len ( mp_int  z,
mp_size  radix 
)

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

Definition at line 1948 of file imath.c.

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

Referenced by mp_int_sqrt().

1949 {
1950  assert(z != NULL);
1951  assert(radix >= MP_MIN_RADIX && radix <= MP_MAX_RADIX);
1952 
1953  int len = s_outlen(z, radix) + 1; /* for terminator */
1954 
1955  /* Allow for sign marker on negatives */
1956  if (MP_SIGN(z) == MP_NEG)
1957  len += 1;
1958 
1959  return len;
1960 }
static int s_outlen(mp_int z, mp_size r)
Definition: imath.c:3454
const mp_sign MP_NEG
Definition: imath.c:85
static mp_sign MP_SIGN(mp_int Z)
Definition: imath.h:79
#define MP_MIN_RADIX
Definition: imath.h:100
#define assert(TEST)
Definition: imath.c:73
#define MP_MAX_RADIX
Definition: imath.h:101

◆ mp_int_sub()

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

Sets c to the difference of a less b.

Definition at line 778 of file imath.c.

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

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

779 {
780  assert(a != NULL && b != NULL && c != NULL);
781 
782  mp_size ua = MP_USED(a);
783  mp_size ub = MP_USED(b);
784  mp_size max = MAX(ua, ub);
785 
786  if (MP_SIGN(a) != MP_SIGN(b))
787  {
788  /* Different signs -- add magnitudes and keep sign of a */
789  if (!s_pad(c, max))
790  return MP_MEMORY;
791 
792  mp_digit carry = s_uadd(MP_DIGITS(a), MP_DIGITS(b), MP_DIGITS(c), ua, ub);
793  mp_size uc = max;
794 
795  if (carry)
796  {
797  if (!s_pad(c, max + 1))
798  return MP_MEMORY;
799 
800  c->digits[max] = carry;
801  ++uc;
802  }
803 
804  c->used = uc;
805  c->sign = a->sign;
806 
807  }
808  else
809  {
810  /* Same signs -- subtract magnitudes */
811  if (!s_pad(c, max))
812  return MP_MEMORY;
813  mp_int x,
814  y;
815  mp_sign osign;
816 
817  int cmp = s_ucmp(a, b);
818 
819  if (cmp >= 0)
820  {
821  x = a;
822  y = b;
823  osign = MP_ZPOS;
824  }
825  else
826  {
827  x = b;
828  y = a;
829  osign = MP_NEG;
830  }
831 
832  if (MP_SIGN(a) == MP_NEG && cmp != 0)
833  osign = 1 - osign;
834 
835  s_usub(MP_DIGITS(x), MP_DIGITS(y), MP_DIGITS(c), MP_USED(x), MP_USED(y));
836  c->used = x->used;
837  CLAMP(c);
838 
839  c->sign = osign;
840  }
841 
842  return MP_OK;
843 }
static mp_size MP_USED(mp_int Z)
Definition: imath.h:74
mp_digit * digits
Definition: imath.h:55
const mp_sign MP_NEG
Definition: imath.c:85
static mp_sign MP_SIGN(mp_int Z)
Definition: imath.h:79
Definition: imath.h:52
static mp_size MAX(mp_size A, mp_size B)
Definition: imath.c:187
const mp_sign MP_ZPOS
Definition: imath.c:86
#define assert(TEST)
Definition: imath.c:73
static mp_digit s_uadd(mp_digit *da, mp_digit *db, mp_digit *dc, mp_size size_a, mp_size size_b)
Definition: imath.c:2387
static void CLAMP(mp_int z_)
Definition: imath.c:168
const mp_result MP_OK
Definition: imath.c:75
mp_sign sign
Definition: imath.h:58
static void s_usub(mp_digit *da, mp_digit *db, mp_digit *dc, mp_size size_a, mp_size size_b)
Definition: imath.c:2422
static bool s_pad(mp_int z, mp_size min)
Definition: imath.c:2253
unsigned char mp_sign
Definition: imath.h:32
mp_size used
Definition: imath.h:57
static int s_ucmp(mp_int a, mp_int b)
Definition: imath.c:2342
unsigned int mp_size
Definition: imath.h:33
static mp_digit * MP_DIGITS(mp_int Z)
Definition: imath.h:64
const mp_result MP_MEMORY
Definition: imath.c:78
uint32 mp_digit
Definition: imath.h:46
static int cmp(const chr *x, const chr *y, size_t len)
Definition: regc_locale.c:742

◆ mp_int_sub_value()

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

Sets c to the difference of a less value.

Definition at line 846 of file imath.c.

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

Referenced by mp_int_is_even(), and mp_int_root().

847 {
848  mpz_t vtmp;
850 
851  s_fake(&vtmp, value, vbuf);
852 
853  return mp_int_sub(a, &vtmp, c);
854 }
static void s_fake(mp_int z, mp_small value, mp_digit vbuf[])
Definition: imath.c:2280
Definition: imath.h:52
static struct @145 value
#define MP_VALUE_DIGITS(V)
Definition: imath.c:119
mp_result mp_int_sub(mp_int a, mp_int b, mp_int c)
Definition: imath.c:778
uint32 mp_digit
Definition: imath.h:46

◆ mp_int_swap()

void mp_int_swap ( mp_int  a,
mp_int  c 
)

Swaps the values and storage between a and c.

Definition at line 636 of file imath.c.

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

Referenced by mp_int_is_even().

637 {
638  if (a != c)
639  {
640  mpz_t tmp = *a;
641 
642  *a = *c;
643  *c = tmp;
644 
645  if (MP_DIGITS(a) == &(c->single))
646  a->digits = &(a->single);
647  if (MP_DIGITS(c) == &(a->single))
648  c->digits = &(c->single);
649  }
650 }
mp_digit * digits
Definition: imath.h:55
Definition: imath.h:52
char * c
mp_digit single
Definition: imath.h:54
static mp_digit * MP_DIGITS(mp_int Z)
Definition: imath.h:64

◆ mp_int_to_binary()

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

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

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

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

Definition at line 2061 of file imath.c.

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

Referenced by mp_int_sqrt().

2062 {
2063  static const int PAD_FOR_2C = 1;
2064 
2065  assert(z != NULL && buf != NULL);
2066 
2067  int limpos = limit;
2068  mp_result res = s_tobin(z, buf, &limpos, PAD_FOR_2C);
2069 
2070  if (MP_SIGN(z) == MP_NEG)
2071  s_2comp(buf, limpos);
2072 
2073  return res;
2074 }
const mp_sign MP_NEG
Definition: imath.c:85
static mp_sign MP_SIGN(mp_int Z)
Definition: imath.h:79
static void s_2comp(unsigned char *buf, int len)
Definition: imath.c:3519
static char * buf
Definition: pg_test_fsync.c:68
#define assert(TEST)
Definition: imath.c:73
static mp_result s_tobin(mp_int z, unsigned char *buf, int *limpos, int pad)
Definition: imath.c:3538
int mp_result
Definition: imath.h:34

◆ mp_int_to_int()

mp_result mp_int_to_int ( mp_int  z,
mp_small out 
)

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

Definition at line 1822 of file imath.c.

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

Referenced by mp_int_div_value(), and mp_int_sqrt().

1823 {
1824  assert(z != NULL);
1825 
1826  /* Make sure the value is representable as a small integer */
1827  mp_sign sz = MP_SIGN(z);
1828 
1829  if ((sz == MP_ZPOS && mp_int_compare_value(z, MP_SMALL_MAX) > 0) ||
1831  {
1832  return MP_RANGE;
1833  }
1834 
1835  mp_usmall uz = MP_USED(z);
1836  mp_digit *dz = MP_DIGITS(z) + uz - 1;
1837  mp_small uv = 0;
1838 
1839  while (uz > 0)
1840  {
1841  uv <<= MP_DIGIT_BIT / 2;
1842  uv = (uv << (MP_DIGIT_BIT / 2)) | *dz--;
1843  --uz;
1844  }
1845 
1846  if (out)
1847  *out = (mp_small) ((sz == MP_NEG) ? -uv : uv);
1848 
1849  return MP_OK;
1850 }
#define MP_SMALL_MAX
Definition: imath.h:97
static mp_size MP_USED(mp_int Z)
Definition: imath.h:74
long mp_small
Definition: imath.h:35
const mp_sign MP_NEG
Definition: imath.c:85
static mp_sign MP_SIGN(mp_int Z)
Definition: imath.h:79
#define MP_DIGIT_BIT
Definition: imath.h:94
const mp_result MP_RANGE
Definition: imath.c:79
const mp_sign MP_ZPOS
Definition: imath.c:86
#define assert(TEST)
Definition: imath.c:73
int mp_int_compare_value(mp_int z, mp_small value)
Definition: imath.c:1335
const mp_result MP_OK
Definition: imath.c:75
unsigned char mp_sign
Definition: imath.h:32
#define MP_SMALL_MIN
Definition: imath.h:96
static mp_digit * MP_DIGITS(mp_int Z)
Definition: imath.h:64
uint32 mp_digit
Definition: imath.h:46
unsigned long mp_usmall
Definition: imath.h:36

◆ mp_int_to_string()

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

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

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

Definition at line 1883 of file imath.c.

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

Referenced by mp_int_sqrt().

1884 {
1885  assert(z != NULL && str != NULL && limit >= 2);
1886  assert(radix >= MP_MIN_RADIX && radix <= MP_MAX_RADIX);
1887 
1888  int cmp = 0;
1889 
1890  if (CMPZ(z) == 0)
1891  {
1892  *str++ = s_val2ch(0, 1);
1893  }
1894  else
1895  {
1896  mp_result res;
1897  mpz_t tmp;
1898  char *h,
1899  *t;
1900 
1901  if ((res = mp_int_init_copy(&tmp, z)) != MP_OK)
1902  return res;
1903 
1904  if (MP_SIGN(z) == MP_NEG)
1905  {
1906  *str++ = '-';
1907  --limit;
1908  }
1909  h = str;
1910 
1911  /* Generate digits in reverse order until finished or limit reached */
1912  for ( /* */ ; limit > 0; --limit)
1913  {
1914  mp_digit d;
1915 
1916  if ((cmp = CMPZ(&tmp)) == 0)
1917  break;
1918 
1919  d = s_ddiv(&tmp, (mp_digit) radix);
1920  *str++ = s_val2ch(d, 1);
1921  }
1922  t = str - 1;
1923 
1924  /* Put digits back in correct output order */
1925  while (h < t)
1926  {
1927  char tc = *h;
1928 
1929  *h++ = *t;
1930  *t-- = tc;
1931  }
1932 
1933  mp_int_clear(&tmp);
1934  }
1935 
1936  *str = '\0';
1937  if (cmp == 0)
1938  {
1939  return MP_OK;
1940  }
1941  else
1942  {
1943  return MP_TRUNC;
1944  }
1945 }
static char s_val2ch(int v, int caps)
Definition: imath.c:3495
const mp_sign MP_NEG
Definition: imath.c:85
static mp_sign MP_SIGN(mp_int Z)
Definition: imath.h:79
static int CMPZ(mp_int Z)
Definition: imath.c:248
Definition: imath.h:52
mp_result mp_int_init_copy(mp_int z, mp_int old)
Definition: imath.c:520
const mp_result MP_TRUNC
Definition: imath.c:81
#define MP_MIN_RADIX
Definition: imath.h:100
#define assert(TEST)
Definition: imath.c:73
const mp_result MP_OK
Definition: imath.c:75
void mp_int_clear(mp_int z)
Definition: imath.c:587
int mp_result
Definition: imath.h:34
static mp_digit s_ddiv(mp_int a, mp_digit b)
Definition: imath.c:2773
uint32 mp_digit
Definition: imath.h:46
#define MP_MAX_RADIX
Definition: imath.h:101
static int cmp(const chr *x, const chr *y, size_t len)
Definition: regc_locale.c:742

◆ mp_int_to_uint()

mp_result mp_int_to_uint ( mp_int  z,
mp_usmall out 
)

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

Definition at line 1853 of file imath.c.

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

Referenced by mp_int_sqrt().

1854 {
1855  assert(z != NULL);
1856 
1857  /* Make sure the value is representable as an unsigned small integer */
1858  mp_size sz = MP_SIGN(z);
1859 
1860  if (sz == MP_NEG || mp_int_compare_uvalue(z, MP_USMALL_MAX) > 0)
1861  {
1862  return MP_RANGE;
1863  }
1864 
1865  mp_size uz = MP_USED(z);
1866  mp_digit *dz = MP_DIGITS(z) + uz - 1;
1867  mp_usmall uv = 0;
1868 
1869  while (uz > 0)
1870  {
1871  uv <<= MP_DIGIT_BIT / 2;
1872  uv = (uv << (MP_DIGIT_BIT / 2)) | *dz--;
1873  --uz;
1874  }
1875 
1876  if (out)
1877  *out = uv;
1878 
1879  return MP_OK;
1880 }
static mp_size MP_USED(mp_int Z)
Definition: imath.h:74
const mp_sign MP_NEG
Definition: imath.c:85
static mp_sign MP_SIGN(mp_int Z)
Definition: imath.h:79
#define MP_DIGIT_BIT
Definition: imath.h:94
const mp_result MP_RANGE
Definition: imath.c:79
#define MP_USMALL_MAX
Definition: imath.h:98
#define assert(TEST)
Definition: imath.c:73
const mp_result MP_OK
Definition: imath.c:75
int mp_int_compare_uvalue(mp_int z, mp_usmall uv)
Definition: imath.c:1354
unsigned int mp_size
Definition: imath.h:33
static mp_digit * MP_DIGITS(mp_int Z)
Definition: imath.h:64
uint32 mp_digit
Definition: imath.h:46
unsigned long mp_usmall
Definition: imath.h:36

◆ mp_int_to_unsigned()

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

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

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

Definition at line 2137 of file imath.c.

References assert, and s_tobin().

Referenced by bn_to_mpi(), and mp_int_sqrt().

2138 {
2139  static const int NO_PADDING = 0;
2140 
2141  assert(z != NULL && buf != NULL);
2142 
2143  return s_tobin(z, buf, &limit, NO_PADDING);
2144 }
static char * buf
Definition: pg_test_fsync.c:68
#define assert(TEST)
Definition: imath.c:73
static mp_result s_tobin(mp_int z, unsigned char *buf, int *limpos, int pad)
Definition: imath.c:3538

◆ mp_int_unsigned_len()

mp_result mp_int_unsigned_len ( mp_int  z)

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

Definition at line 2171 of file imath.c.

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

Referenced by mp_int_binary_len(), and mp_int_sqrt().

2172 {
2173  mp_result res = mp_int_count_bits(z);
2174 
2175  if (res <= 0)
2176  return res;
2177 
2178  int bytes = (res + (CHAR_BIT - 1)) / CHAR_BIT;
2179 
2180  return bytes;
2181 }
def bytes(source, encoding='ascii', errors='strict')
mp_result mp_int_count_bits(mp_int z)
Definition: imath.c:2038
int mp_result
Definition: imath.h:34

◆ mp_int_zero()

void mp_int_zero ( mp_int  z)

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

Definition at line 653 of file imath.c.

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

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

654 {
655  assert(z != NULL);
656 
657  z->digits[0] = 0;
658  z->used = 1;
659  z->sign = MP_ZPOS;
660 }
mp_digit * digits
Definition: imath.h:55
const mp_sign MP_ZPOS
Definition: imath.c:86
#define assert(TEST)
Definition: imath.c:73
mp_sign sign
Definition: imath.h:58
mp_size used
Definition: imath.h:57

◆ REV()

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

Definition at line 152 of file imath.c.

Referenced by s_tobin().

153 {
154  unsigned char *u_ = A;
155  unsigned char *v_ = u_ + N - 1;
156 
157  while (u_ < v_)
158  {
159  unsigned char xch = *u_;
160 
161  *u_++ = *v_;
162  *v_-- = xch;
163  }
164 }

◆ s_2comp()

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

Definition at line 3519 of file imath.c.

References i.

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

3520 {
3521  unsigned short s = 1;
3522 
3523  for (int i = len - 1; i >= 0; --i)
3524  {
3525  unsigned char c = ~buf[i];
3526 
3527  s = c + s;
3528  c = s & UCHAR_MAX;
3529  s >>= CHAR_BIT;
3530 
3531  buf[i] = c;
3532  }
3533 
3534  /* last carry out is ignored */
3535 }
char * c
static char * buf
Definition: pg_test_fsync.c:68
int i

◆ s_2expt()

static int s_2expt ( mp_int  z,
mp_small  k 
)
static

Definition at line 3038 of file imath.c.

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

Referenced by GROW(), and s_brmu().

3039 {
3040  mp_size ndig,
3041  rest;
3042  mp_digit *dz;
3043 
3044  ndig = (k + MP_DIGIT_BIT) / MP_DIGIT_BIT;
3045  rest = k % MP_DIGIT_BIT;
3046 
3047  if (!s_pad(z, ndig))
3048  return 0;
3049 
3050  dz = MP_DIGITS(z);
3051  ZERO(dz, ndig);
3052  *(dz + ndig - 1) = (1u << rest);
3053  z->used = ndig;
3054 
3055  return 1;
3056 }
static void ZERO(mp_digit *P, mp_size S)
Definition: imath.c:131
#define MP_DIGIT_BIT
Definition: imath.h:94
static bool s_pad(mp_int z, mp_size min)
Definition: imath.c:2253
mp_size used
Definition: imath.h:57
unsigned int mp_size
Definition: imath.h:33
static mp_digit * MP_DIGITS(mp_int Z)
Definition: imath.h:64
uint32 mp_digit
Definition: imath.h:46

◆ s_alloc()

static mp_digit * s_alloc ( mp_size  num)
static

Definition at line 2213 of file imath.c.

References assert, fill(), and px_alloc.

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

2214 {
2215  mp_digit *out = px_alloc(num * sizeof(mp_digit));
2216 
2217  assert(out != NULL);
2218 
2219 #if IMATH_DEBUG
2220  for (mp_size ix = 0; ix < num; ++ix)
2221  out[ix] = fill;
2222 #endif
2223  return out;
2224 }
static void fill(int length, int max, char filler, FILE *fp)
Definition: fe-print.c:761
#define assert(TEST)
Definition: imath.c:73
#define px_alloc(s)
Definition: px.h:44
unsigned int mp_size
Definition: imath.h:33
uint32 mp_digit
Definition: imath.h:46

◆ s_brmu()

static mp_result s_brmu ( mp_int  z,
mp_int  m 
)
static

Definition at line 3081 of file imath.c.

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

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

3082 {
3083  mp_size um = MP_USED(m) * 2;
3084 
3085  if (!s_pad(z, um))
3086  return MP_MEMORY;
3087 
3088  s_2expt(z, MP_DIGIT_BIT * um);
3089  return mp_int_div(z, m, z, NULL);
3090 }
static mp_size MP_USED(mp_int Z)
Definition: imath.h:74
#define MP_DIGIT_BIT
Definition: imath.h:94
mp_result mp_int_div(mp_int a, mp_int b, mp_int q, mp_int r)
Definition: imath.c:1002
static int s_2expt(mp_int z, mp_small k)
Definition: imath.c:3038
static bool s_pad(mp_int z, mp_size min)
Definition: imath.c:2253
unsigned int mp_size
Definition: imath.h:33
const mp_result MP_MEMORY
Definition: imath.c:78

◆ s_cdig()

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

Definition at line 2301 of file imath.c.

Referenced by GROW(), and s_ucmp().

2302 {
2303  mp_digit *dat = da + len - 1,
2304  *dbt = db + len - 1;
2305 
2306  for ( /* */ ; len != 0; --len, --dat, --dbt)
2307  {
2308  if (*dat > *dbt)
2309  {
2310  return 1;
2311  }
2312  else if (*dat < *dbt)
2313  {
2314  return -1;
2315  }
2316  }
2317 
2318  return 0;
2319 }
uint32 mp_digit
Definition: imath.h:46

◆ s_ch2val()

static int s_ch2val ( char  c,
int  r 
)
static

Definition at line 3474 of file imath.c.

Referenced by GROW(), and mp_int_read_cstring().

3475 {
3476  int out;
3477 
3478  /*
3479  * In some locales, isalpha() accepts characters outside the range A-Z,
3480  * producing out<0 or out>=36. The "out >= r" check will always catch
3481  * out>=36. Though nothing explicitly catches out<0, our caller reacts
3482  * the same way to every negative return value.
3483  */
3484  if (isdigit((unsigned char) c))
3485  out = c - '0';
3486  else if (r > 10 && isalpha((unsigned char) c))
3487  out = toupper((unsigned char) c) - 'A' + 10;
3488  else
3489  return -1;
3490 
3491  return (out >= r) ? -1 : out;
3492 }
char * c

◆ s_dadd()

static void s_dadd ( mp_int  a,
mp_digit  b 
)
static

Definition at line 2707 of file imath.c.

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

Referenced by GROW(), and mp_int_read_cstring().

2708 {
2709  mp_word w = 0;
2710  mp_digit *da = MP_DIGITS(a);
2711  mp_size ua = MP_USED(a);
2712 
2713  w = (mp_word) *da + b;
2714  *da++ = LOWER_HALF(w);
2715  w = UPPER_HALF(w);
2716 
2717  for (ua -= 1; ua > 0; --ua, ++da)
2718  {
2719  w = (mp_word) *da + w;
2720 
2721  *da = LOWER_HALF(w);
2722  w = UPPER_HALF(w);
2723  }
2724 
2725  if (w)
2726  {
2727  *da = (mp_digit) w;
2728  a->used += 1;
2729  }
2730 }
static mp_size MP_USED(mp_int Z)
Definition: imath.h:74
static mp_word UPPER_HALF(mp_word W)
Definition: imath.c:256
static mp_digit LOWER_HALF(mp_word W)
Definition: imath.c:261
mp_size used
Definition: imath.h:57
unsigned int mp_size
Definition: imath.h:33
static mp_digit * MP_DIGITS(mp_int Z)
Definition: imath.h:64
uint32 mp_digit
Definition: imath.h:46
uint64 mp_word
Definition: imath.h:47

◆ s_dbmul()

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

Definition at line 2755 of file imath.c.

References LOWER_HALF(), and UPPER_HALF().

Referenced by GROW(), and s_udiv_knuth().

2756 {
2757  mp_word w = 0;
2758 
2759  while (size_a > 0)
2760  {
2761  w = (mp_word) *da++ * (mp_word) b + w;
2762 
2763  *dc++ = LOWER_HALF(w);
2764  w = UPPER_HALF(w);
2765  --size_a;
2766  }
2767 
2768  if (w)
2769  *dc = LOWER_HALF(w);
2770 }
static mp_word UPPER_HALF(mp_word W)
Definition: imath.c:256
static mp_digit LOWER_HALF(mp_word W)
Definition: imath.c:261
uint64 mp_word
Definition: imath.h:47

◆ s_ddiv()

static mp_digit s_ddiv ( mp_int  a,
mp_digit  b 
)
static

Definition at line 2773 of file imath.c.

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

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

2774 {
2775  mp_word w = 0,
2776  qdigit;
2777  mp_size ua = MP_USED(a);
2778  mp_digit *da = MP_DIGITS(a) + ua - 1;
2779 
2780  for ( /* */ ; ua > 0; --ua, --da)
2781  {
2782  w = (w << MP_DIGIT_BIT) | *da;
2783 
2784  if (w >= b)
2785  {
2786  qdigit = w / b;
2787  w = w % b;
2788  }
2789  else
2790  {
2791  qdigit = 0;
2792  }
2793 
2794  *da = (mp_digit) qdigit;
2795  }
2796 
2797  CLAMP(a);
2798  return (mp_digit) w;
2799 }
static mp_size MP_USED(mp_int Z)
Definition: imath.h:74
#define MP_DIGIT_BIT
Definition: imath.h:94
static void CLAMP(mp_int z_)
Definition: imath.c:168
unsigned int mp_size
Definition: imath.h:33
static mp_digit * MP_DIGITS(mp_int Z)
Definition: imath.h:64
uint32 mp_digit
Definition: imath.h:46
uint64 mp_word
Definition: imath.h:47

◆ s_dmul()

static void s_dmul ( mp_int  a,
mp_digit  b 
)
static

Definition at line 2733 of file imath.c.

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

Referenced by GROW(), and mp_int_read_cstring().

2734 {
2735  mp_word w = 0;
2736  mp_digit *da = MP_DIGITS(a);
2737  mp_size ua = MP_USED(a);
2738 
2739  while (ua > 0)
2740  {
2741  w = (mp_word) *da * b + w;
2742  *da++ = LOWER_HALF(w);
2743  w = UPPER_HALF(w);
2744  --ua;
2745  }
2746 
2747  if (w)
2748  {
2749  *da = (mp_digit) w;
2750  a->used += 1;
2751  }
2752 }
static mp_size MP_USED(mp_int Z)
Definition: imath.h:74
static mp_word UPPER_HALF(mp_word W)
Definition: imath.c:256
static mp_digit LOWER_HALF(mp_word W)
Definition: imath.c:261
mp_size used
Definition: imath.h:57
unsigned int mp_size
Definition: imath.h:33
static mp_digit * MP_DIGITS(mp_int Z)
Definition: imath.h:64
uint32 mp_digit
Definition: imath.h:46
uint64 mp_word
Definition: imath.h:47

◆ s_dp2k()

static int s_dp2k ( mp_int  z)
static

Definition at line 2984 of file imath.c.

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

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

2985 {
2986  int k = 0;
2987  mp_digit *dp = MP_DIGITS(z),
2988  d;
2989 
2990  if (MP_USED(z) == 1 && *dp == 0)
2991  return 1;
2992 
2993  while (*dp == 0)
2994  {
2995  k += MP_DIGIT_BIT;
2996  ++dp;
2997  }
2998 
2999  d = *dp;
3000  while ((d & 1) == 0)
3001  {
3002  d >>= 1;
3003  ++k;
3004  }
3005 
3006  return k;
3007 }
static mp_size MP_USED(mp_int Z)
Definition: imath.h:74
#define MP_DIGIT_BIT
Definition: imath.h:94
static mp_digit * MP_DIGITS(mp_int Z)
Definition: imath.h:64
uint32 mp_digit
Definition: imath.h:46

◆ s_embar()

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

Definition at line 3149 of file imath.c.

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

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

3150 {
3151  mp_digit umu = MP_USED(mu);
3152  mp_digit *db = MP_DIGITS(b);
3153  mp_digit *dbt = db + MP_USED(b) - 1;
3154 
3155  DECLARE_TEMP(3);
3156  REQUIRE(GROW(TEMP(0), 4 * umu));
3157  REQUIRE(GROW(TEMP(1), 4 * umu));
3158  REQUIRE(GROW(TEMP(2), 4 * umu));
3159  ZERO(TEMP(0)->digits, TEMP(0)->alloc);
3160  ZERO(TEMP(1)->digits, TEMP(1)->alloc);
3161  ZERO(TEMP(2)->digits, TEMP(2)->alloc);
3162 
3163  (void) mp_int_set_value(c, 1);
3164 
3165  /* Take care of low-order digits */
3166  while (db < dbt)
3167  {
3168  mp_digit d = *db;
3169 
3170  for (int i = MP_DIGIT_BIT; i > 0; --i, d >>= 1)
3171  {
3172  if (d & 1)
3173  {
3174  /* The use of a second temporary avoids allocation */
3175  UMUL(c, a, TEMP(0));
3176  if (!s_reduce(TEMP(0), m, mu, TEMP(1), TEMP(2)))
3177  {
3178  REQUIRE(MP_MEMORY);
3179  }
3180  mp_int_copy(TEMP(0), c);
3181  }
3182 
3183  USQR(a, TEMP(0));
3184  assert(MP_SIGN(TEMP(0)) == MP_ZPOS);
3185  if (!s_reduce(TEMP(0), m, mu, TEMP(1), TEMP(2)))
3186  {
3187  REQUIRE(MP_MEMORY);
3188  }
3189  assert(MP_SIGN(TEMP(0)) == MP_ZPOS);
3190  mp_int_copy(TEMP(0), a);
3191  }
3192 
3193  ++db;
3194  }
3195 
3196  /* Take care of highest-order digit */
3197  mp_digit d = *dbt;
3198 
3199  for (;;)
3200  {
3201  if (d & 1)
3202  {
3203  UMUL(c, a, TEMP(0));
3204  if (!s_reduce(TEMP(0), m, mu, TEMP(1), TEMP(2)))
3205  {
3206  REQUIRE(MP_MEMORY);
3207  }
3208  mp_int_copy(TEMP(0), c);
3209  }
3210 
3211  d >>= 1;
3212  if (!d)
3213  break;
3214 
3215  USQR(a, TEMP(0));
3216  if (!s_reduce(TEMP(0), m, mu, TEMP(1), TEMP(2)))
3217  {
3218  REQUIRE(MP_MEMORY);
3219  }
3220  (void) mp_int_copy(TEMP(0), a);
3221  }
3222 
3223  CLEANUP_TEMP();
3224  return MP_OK;
3225 }
static void ZERO(mp_digit *P, mp_size S)
Definition: imath.c:131
static void USQR(mp_int X, mp_int Z)
Definition: imath.c:452
#define DECLARE_TEMP(N)
Definition: imath.c:206
static mp_size MP_USED(mp_int Z)
Definition: imath.h:74
static mp_sign MP_SIGN(mp_int Z)
Definition: imath.h:79
#define MP_DIGIT_BIT
Definition: imath.h:94
mp_result mp_int_copy(mp_int a, mp_int c)
Definition: imath.c:611
const mp_sign MP_ZPOS
Definition: imath.c:86
static void UMUL(mp_int X, mp_int Y, mp_int Z)
Definition: imath.c:438
#define CLEANUP_TEMP()
Definition: imath.c:222
#define REQUIRE(E)
Definition: imath.c:240
#define assert(TEST)
Definition: imath.c:73
#define TEMP(K)
Definition: imath.c:234
static int s_reduce(mp_int x, mp_int m, mp_int mu, mp_int q1, mp_int q2)
Definition: imath.c:3093
const mp_result MP_OK
Definition: imath.c:75
static mp_result GROW(mp_int Z, mp_size N)
Definition: imath.c:313
mp_result mp_int_set_value(mp_int z, mp_small value)
Definition: imath.c:567
int i
static mp_digit * MP_DIGITS(mp_int Z)
Definition: imath.h:64
const mp_result MP_MEMORY
Definition: imath.c:78
uint32 mp_digit
Definition: imath.h:46
int digits
Definition: informix.c:686

◆ s_fake()

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

Definition at line 2280 of file imath.c.

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

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

2281 {
2282  mp_usmall uv = (mp_usmall) (value < 0) ? -value : value;
2283 
2284  s_ufake(z, uv, vbuf);
2285  if (value < 0)
2286  z->sign = MP_NEG;
2287 }
static void s_ufake(mp_int z, mp_usmall value, mp_digit vbuf[])
Definition: imath.c:2290
const mp_sign MP_NEG
Definition: imath.c:85
static struct @145 value
mp_sign sign
Definition: imath.h:58
unsigned long mp_usmall
Definition: imath.h:36

◆ s_free()

static void s_free ( void *  ptr)
static

Definition at line 2247 of file imath.c.

References px_free.

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

2248 {
2249  px_free(ptr);
2250 }
#define px_free(p)
Definition: px.h:46

◆ s_inlen()

static mp_size s_inlen ( int  len,
mp_size  r 
)
static

Definition at line 3465 of file imath.c.

References MP_DIGIT_BIT, and s_log2.

Referenced by GROW(), and mp_int_read_cstring().

3466 {
3467  double raw = (double) len / s_log2[r];
3468  mp_size bits = (mp_size) (raw + 0.5);
3469 
3470  return (mp_size) ((bits + (MP_DIGIT_BIT - 1)) / MP_DIGIT_BIT) + 1;
3471 }
#define MP_DIGIT_BIT
Definition: imath.h:94
static const double s_log2[]
Definition: imath.c:105
unsigned int mp_size
Definition: imath.h:33

◆ s_isp2()

static int s_isp2 ( mp_int  z)
static

Definition at line 3010 of file imath.c.

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

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

3011 {
3012  mp_size uz = MP_USED(z),
3013  k = 0;
3014  mp_digit *dz = MP_DIGITS(z),
3015  d;
3016 
3017  while (uz > 1)
3018  {
3019  if (*dz++ != 0)
3020  return -1;
3021  k += MP_DIGIT_BIT;
3022  --uz;
3023  }
3024 
3025  d = *dz;
3026  while (d > 1)
3027  {
3028  if (d & 1)
3029  return -1;
3030  ++k;
3031  d >>= 1;
3032  }
3033 
3034  return (int) k;
3035 }
static mp_size MP_USED(mp_int Z)
Definition: imath.h:74
#define MP_DIGIT_BIT
Definition: imath.h:94
unsigned int mp_size
Definition: imath.h:33
static mp_digit * MP_DIGITS(mp_int Z)
Definition: imath.h:64
uint32 mp_digit
Definition: imath.h:46

◆ s_kmul()

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

Definition at line 2458 of file imath.c.

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

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

2460 {
2461  mp_size bot_size;
2462 
2463  /* Make sure b is the smaller of the two input values */
2464  if (size_b > size_a)
2465  {
2466  SWAP(mp_digit *, da, db);
2467  SWAP(mp_size, size_a, size_b);
2468  }
2469 
2470  /*
2471  * Insure that the bottom is the larger half in an odd-length split; the
2472  * code below relies on this being true.
2473  */
2474  bot_size = (size_a + 1) / 2;
2475 
2476  /*
2477  * If the values are big enough to bother with recursion, use the
2478  * Karatsuba algorithm to compute the product; otherwise use the normal
2479  * multiplication algorithm
2480  */
2481  if (multiply_threshold && size_a >= multiply_threshold && size_b > bot_size)
2482  {
2483  mp_digit *t1,
2484  *t2,
2485  *t3,
2486  carry;
2487 
2488  mp_digit *a_top = da + bot_size;
2489  mp_digit *b_top = db + bot_size;
2490 
2491  mp_size at_size = size_a - bot_size;
2492  mp_size bt_size = size_b - bot_size;
2493  mp_size buf_size = 2 * bot_size;
2494 
2495  /*
2496  * Do a single allocation for all three temporary buffers needed; each
2497  * buffer must be big enough to hold the product of two bottom halves,
2498  * and one buffer needs space for the completed product; twice the
2499  * space is plenty.
2500  */
2501  if ((t1 = s_alloc(4 * buf_size)) == NULL)
2502  return 0;
2503  t2 = t1 + buf_size;
2504  t3 = t2 + buf_size;
2505  ZERO(t1, 4 * buf_size);
2506 
2507  /*
2508  * t1 and t2 are initially used as temporaries to compute the inner
2509  * product (a1 + a0)(b1 + b0) = a1b1 + a1b0 + a0b1 + a0b0
2510  */
2511  carry = s_uadd(da, a_top, t1, bot_size, at_size); /* t1 = a1 + a0 */
2512  t1[bot_size] = carry;
2513 
2514  carry = s_uadd(db, b_top, t2, bot_size, bt_size); /* t2 = b1 + b0 */
2515  t2[bot_size] = carry;
2516 
2517  (void) s_kmul(t1, t2, t3, bot_size + 1, bot_size + 1); /* t3 = t1 * t2 */
2518 
2519  /*
2520  * Now we'll get t1 = a0b0 and t2 = a1b1, and subtract them out so
2521  * that we're left with only the pieces we want: t3 = a1b0 + a0b1
2522  */
2523  ZERO(t1, buf_size);
2524  ZERO(t2, buf_size);
2525  (void) s_kmul(da, db, t1, bot_size, bot_size); /* t1 = a0 * b0 */
2526  (void) s_kmul(a_top, b_top, t2, at_size, bt_size); /* t2 = a1 * b1 */
2527 
2528  /* Subtract out t1 and t2 to get the inner product */
2529  s_usub(t3, t1, t3, buf_size + 2, buf_size);
2530  s_usub(t3, t2, t3, buf_size + 2, buf_size);
2531 
2532  /* Assemble the output value */
2533  COPY(t1, dc, buf_size);
2534  carry = s_uadd(t3, dc + bot_size, dc + bot_size, buf_size + 1, buf_size);
2535  assert(carry == 0);
2536 
2537  carry =
2538  s_uadd(t2, dc + 2 * bot_size, dc + 2 * bot_size, buf_size, buf_size);
2539  assert(carry == 0);
2540 
2541  s_free(t1); /* note t2 and t3 are just internal pointers
2542  * to t1 */
2543  }
2544  else
2545  {
2546  s_umul(da, db, dc, size_a, size_b);
2547  }
2548 
2549  return 1;
2550 }
static void ZERO(mp_digit *P, mp_size S)
Definition: imath.c:131
static mp_size multiply_threshold
Definition: imath.c:291
static void COPY(mp_digit *P, mp_digit *Q, mp_size S)
Definition: imath.c:141
static mp_digit * s_alloc(mp_size num)
Definition: imath.c:2213
#define assert(TEST)
Definition: imath.c:73
static mp_digit s_uadd(mp_digit *da, mp_digit *db, mp_digit *dc, mp_size size_a, mp_size size_b)
Definition: imath.c:2387
static void s_usub(mp_digit *da, mp_digit *db, mp_digit *dc, mp_size size_a, mp_size size_b)
Definition: imath.c:2422
unsigned int mp_size
Definition: imath.h:33
static void s_umul(mp_digit *da, mp_digit *db, mp_digit *dc, mp_size size_a, mp_size size_b)
Definition: imath.c:2553
#define SWAP(T, A, B)
Definition: imath.c:194
uint32 mp_digit
Definition: imath.h:46
static void s_free(void *ptr)
Definition: imath.c:2247
static int s_kmul(mp_digit *da, mp_digit *db, mp_digit *dc, mp_size size_a, mp_size size_b)
Definition: imath.c:2458

◆ s_ksqr()

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

Definition at line 2582 of file imath.c.

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

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

2583 {
2584  if (multiply_threshold && size_a > multiply_threshold)
2585  {
2586  mp_size bot_size = (size_a + 1) / 2;
2587  mp_digit *a_top = da + bot_size;
2588  mp_digit *t1,
2589  *t2,
2590  *t3,
2592  mp_size at_size = size_a - bot_size;
2593  mp_size buf_size = 2 * bot_size;
2594 
2595  if ((t1 = s_alloc(4 * buf_size)) == NULL)
2596  return 0;
2597  t2 = t1 + buf_size;
2598  t3 = t2 + buf_size;
2599  ZERO(t1, 4 * buf_size);
2600 
2601  (void) s_ksqr(da, t1, bot_size); /* t1 = a0 ^ 2 */
2602  (void) s_ksqr(a_top, t2, at_size); /* t2 = a1 ^ 2 */
2603 
2604  (void) s_kmul(da, a_top, t3, bot_size, at_size); /* t3 = a0 * a1 */
2605 
2606  /* Quick multiply t3 by 2, shifting left (can't overflow) */
2607  {
2608  int i,
2609  top = bot_size + at_size;
2610  mp_word w,
2611  save = 0;
2612 
2613  for (i = 0; i < top; ++i)
2614  {
2615  w = t3[i];
2616  w = (w << 1) | save;
2617  t3[i] = LOWER_HALF(w);
2618  save = UPPER_HALF(w);
2619  }
2620  t3[i] = LOWER_HALF(save);
2621  }
2622 
2623  /* Assemble the output value */
2624  COPY(t1, dc, 2 * bot_size);
2625  carry = s_uadd(t3, dc + bot_size, dc + bot_size, buf_size + 1, buf_size);
2626  assert(carry == 0);
2627 
2628  carry =
2629  s_uadd(t2, dc + 2 * bot_size, dc + 2 * bot_size, buf_size, buf_size);
2630  assert(carry == 0);
2631 
2632  s_free(t1); /* note that t2 and t2 are internal pointers
2633  * only */
2634 
2635  }
2636  else
2637  {
2638  s_usqr(da, dc, size_a);
2639  }
2640 
2641  return 1;
2642 }
static void ZERO(mp_digit *P, mp_size S)
Definition: imath.c:131
static mp_size multiply_threshold
Definition: imath.c:291
static void s_usqr(mp_digit *da, mp_digit *dc, mp_size size_a)
Definition: imath.c:2645
static void COPY(mp_digit *P, mp_digit *Q, mp_size S)
Definition: imath.c:141
static mp_word UPPER_HALF(mp_word W)
Definition: imath.c:256
static mp_digit * s_alloc(mp_size num)
Definition: imath.c:2213
#define assert(TEST)
Definition: imath.c:73
static mp_digit s_uadd(mp_digit *da, mp_digit *db, mp_digit *dc, mp_size size_a, mp_size size_b)
Definition: imath.c:2387
static mp_digit LOWER_HALF(mp_word W)
Definition: imath.c:261
unsigned int mp_size
Definition: imath.h:33
int i
static int s_ksqr(mp_digit *da, mp_digit *dc, mp_size size_a)
Definition: imath.c:2582
uint32 mp_digit
Definition: imath.h:46
#define PG_USED_FOR_ASSERTS_ONLY
Definition: c.h:123
static void s_free(void *ptr)
Definition: imath.c:2247
uint64 mp_word
Definition: imath.h:47
static int s_kmul(mp_digit *da, mp_digit *db, mp_digit *dc, mp_size size_a, mp_size size_b)
Definition: imath.c:2458

◆ s_norm()

static int s_norm ( mp_int  a,
mp_int  b 
)
static

Definition at line 3059 of file imath.c.

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

Referenced by GROW(), and s_udiv_knuth().

3060 {
3061  mp_digit d = b->digits[MP_USED(b) - 1];
3062  int k = 0;
3063 
3064  while (d < (1u << (mp_digit) (MP_DIGIT_BIT - 1)))
3065  { /* d < (MP_RADIX / 2) */
3066  d <<= 1;
3067  ++k;
3068  }
3069 
3070  /* These multiplications can't fail */
3071  if (k != 0)
3072  {
3073  (void) s_qmul(a, (mp_size) k);
3074  (void) s_qmul(b, (mp_size) k);
3075  }
3076 
3077  return k;
3078 }
static mp_size MP_USED(mp_int Z)
Definition: imath.h:74
mp_digit * digits
Definition: imath.h:55
static int s_qmul(mp_int z, mp_size p2)
Definition: imath.c:2873
#define MP_DIGIT_BIT
Definition: imath.h:94
unsigned int mp_size
Definition: imath.h:33
uint32 mp_digit
Definition: imath.h:46

◆ s_outlen()

static int s_outlen ( mp_int  z,
mp_size  r 
)
static

Definition at line 3454 of file imath.c.

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

Referenced by GROW(), and mp_int_string_len().

3455 {
3456  assert(r >= MP_MIN_RADIX && r <= MP_MAX_RADIX);
3457 
3458  mp_result bits = mp_int_count_bits(z);
3459  double raw = (double) bits * s_log2[r];
3460 
3461  return (int) (raw + 0.999999);
3462 }
static const double s_log2[]
Definition: imath.c:105
mp_result mp_int_count_bits(mp_int z)
Definition: imath.c:2038
#define MP_MIN_RADIX
Definition: imath.h:100
#define assert(TEST)
Definition: imath.c:73
int mp_result
Definition: imath.h:34
#define MP_MAX_RADIX
Definition: imath.h:101

◆ s_pad()

static bool s_pad ( mp_int  z,
mp_size  min 
)
static

Definition at line 2253 of file imath.c.

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

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

2254 {
2255  if (MP_ALLOC(z) < min)
2256  {
2257  mp_size nsize = s_round_prec(min);
2258  mp_digit *tmp;
2259 
2260  if (z->digits == &(z->single))
2261  {
2262  if ((tmp = s_alloc(nsize)) == NULL)
2263  return false;
2264  tmp[0] = z->single;
2265  }
2266  else if ((tmp = s_realloc(MP_DIGITS(z), MP_ALLOC(z), nsize)) == NULL)
2267  {
2268  return false;
2269  }
2270 
2271  z->digits = tmp;
2272  z->alloc = nsize;
2273  }
2274 
2275  return true;
2276 }
mp_digit * digits
Definition: imath.h:55
mp_size alloc
Definition: imath.h:56
static mp_size s_round_prec(mp_size P)
Definition: imath.c:124
static mp_digit * s_alloc(mp_size num)
Definition: imath.c:2213
mp_digit single
Definition: imath.h:54
static mp_size MP_ALLOC(mp_int Z)
Definition: imath.h:69
unsigned int mp_size
Definition: imath.h:33
static mp_digit * MP_DIGITS(mp_int Z)
Definition: imath.h:64
uint32 mp_digit
Definition: imath.h:46
static mp_digit * s_realloc(mp_digit *old, mp_size osize, mp_size nsize)
Definition: imath.c:2227

◆ s_qdiv()

static void s_qdiv ( mp_int  z,
mp_size  p2 
)
static

Definition at line 2802 of file imath.c.

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

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

2803 {
2804  mp_size ndig = p2 / MP_DIGIT_BIT,
2805  nbits = p2 % MP_DIGIT_BIT;
2806  mp_size uz = MP_USED(z);
2807 
2808  if (ndig)
2809  {
2810  mp_size mark;
2811  mp_digit *to,
2812  *from;
2813 
2814  if (ndig >= uz)
2815  {
2816  mp_int_zero(z);
2817  return;
2818  }
2819 
2820  to = MP_DIGITS(z);
2821  from = to + ndig;
2822 
2823  for (mark = ndig; mark < uz; ++mark)
2824  {
2825  *to++ = *from++;
2826  }
2827 
2828  z->used = uz - ndig;
2829  }
2830 
2831  if (nbits)
2832  {
2833  mp_digit d = 0,
2834  *dz,
2835  save;
2836  mp_size up = MP_DIGIT_BIT - nbits;
2837 
2838  uz = MP_USED(z);
2839  dz = MP_DIGITS(z) + uz - 1;
2840 
2841  for ( /* */ ; uz > 0; --uz, --dz)
2842  {
2843  save = *dz;
2844 
2845  *dz = (*dz >> nbits) | (d << up);
2846  d = save;
2847  }
2848 
2849  CLAMP(z);
2850  }
2851 
2852  if (MP_USED(z) == 1 && z->digits[0] == 0)
2853  z->sign = MP_ZPOS;
2854 }
static mp_size MP_USED(mp_int Z)
Definition: imath.h:74
mp_digit * digits
Definition: imath.h:55
#define MP_DIGIT_BIT
Definition: imath.h:94
const mp_sign MP_ZPOS
Definition: imath.c:86
void mp_int_zero(mp_int z)
Definition: imath.c:653
static void CLAMP(mp_int z_)
Definition: imath.c:168
mp_sign sign
Definition: imath.h:58
mp_size used
Definition: imath.h:57
unsigned int mp_size
Definition: imath.h:33
static mp_digit * MP_DIGITS(mp_int Z)
Definition: imath.h:64
uint32 mp_digit
Definition: imath.h:46

◆ s_qmod()

static void s_qmod ( mp_int  z,
mp_size  p2 
)
static

Definition at line 2857 of file imath.c.

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

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

2858 {
2859  mp_size start = p2 / MP_DIGIT_BIT + 1,
2860  rest = p2 % MP_DIGIT_BIT;
2861  mp_size uz = MP_USED(z);
2862  mp_digit mask = (1u << rest) - 1;
2863 
2864  if (start <= uz)
2865  {
2866  z->used = start;
2867  z->digits[start - 1] &= mask;
2868  CLAMP(z);
2869  }
2870 }
static mp_size MP_USED(mp_int Z)
Definition: imath.h:74
mp_digit * digits
Definition: imath.h:55
#define MP_DIGIT_BIT
Definition: imath.h:94
static void CLAMP(mp_int z_)
Definition: imath.c:168
mp_size used
Definition: imath.h:57
unsigned int mp_size
Definition: imath.h:33
uint32 mp_digit
Definition: imath.h:46

◆ s_qmul()

static int s_qmul ( mp_int  z,
mp_size  p2 
)
static

Definition at line 2873 of file imath.c.

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

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

2874 {
2875  mp_size uz,
2876  need,
2877  rest,
2878  extra,
2879  i;
2880  mp_digit *from,
2881  *to,
2882  d;
2883 
2884  if (p2 == 0)
2885  return 1;
2886 
2887  uz = MP_USED(z);
2888  need = p2 / MP_DIGIT_BIT;
2889  rest = p2 % MP_DIGIT_BIT;
2890 
2891  /*
2892  * Figure out if we need an extra digit at the top end; this occurs if the
2893  * topmost `rest' bits of the high-order digit of z are not zero, meaning
2894  * they will be shifted off the end if not preserved
2895  */
2896  extra = 0;
2897  if (rest != 0)
2898  {
2899  mp_digit *dz = MP_DIGITS(z) + uz - 1;
2900 
2901  if ((*dz >> (MP_DIGIT_BIT - rest)) != 0)
2902  extra = 1;
2903  }
2904 
2905  if (!s_pad(z, uz + need + extra))
2906  return 0;
2907 
2908  /*
2909  * If we need to shift by whole digits, do that in one pass, then to back
2910  * and shift by partial digits.
2911  */
2912  if (need > 0)
2913  {
2914  from = MP_DIGITS(z) + uz - 1;
2915  to = from + need;
2916 
2917  for (i = 0; i < uz; ++i)
2918  *to-- = *from--;
2919 
2920  ZERO(MP_DIGITS(z), need);
2921  uz += need;
2922  }
2923 
2924  if (rest)
2925  {
2926  d = 0;
2927  for (i = need, from = MP_DIGITS(z) + need; i < uz; ++i, ++from)
2928  {
2929  mp_digit save = *from;
2930 
2931  *from = (*from << rest) | (d >> (MP_DIGIT_BIT - rest));
2932  d = save;
2933  }
2934 
2935  d >>= (MP_DIGIT_BIT - rest);
2936  if (d != 0)
2937  {
2938  *from = d;
2939  uz += extra;
2940  }
2941  }
2942 
2943  z->used = uz;
2944  CLAMP(z);
2945 
2946  return 1;
2947 }
static void ZERO(mp_digit *P, mp_size S)
Definition: imath.c:131
static mp_size MP_USED(mp_int Z)
Definition: imath.h:74
#define MP_DIGIT_BIT
Definition: imath.h:94
static void CLAMP(mp_int z_)
Definition: imath.c:168
static bool s_pad(mp_int z, mp_size min)
Definition: imath.c:2253
mp_size used
Definition: imath.h:57
unsigned int mp_size
Definition: imath.h:33
int i
static mp_digit * MP_DIGITS(mp_int Z)
Definition: imath.h:64
uint32 mp_digit
Definition: imath.h:46

◆ s_qsub()

static int s_qsub ( mp_int  z,
mp_size  p2 
)
static

Definition at line 2953 of file imath.c.

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

Referenced by GROW(), and s_reduce().

2954 {
2955  mp_digit hi = (1u << (p2 % MP_DIGIT_BIT)),
2956  *zp;
2957  mp_size tdig = (p2 / MP_DIGIT_BIT),
2958  pos;
2959  mp_word w = 0;
2960 
2961  if (!s_pad(z, tdig + 1))
2962  return 0;
2963 
2964  for (pos = 0, zp = MP_DIGITS(z); pos < tdig; ++pos, ++zp)
2965  {
2966  w = ((mp_word) MP_DIGIT_MAX + 1) - w - (mp_word) *zp;
2967 
2968  *zp = LOWER_HALF(w);
2969  w = UPPER_HALF(w) ? 0 : 1;
2970  }
2971 
2972  w = ((mp_word) MP_DIGIT_MAX + 1 + hi) - w - (mp_word) *zp;
2973  *zp = LOWER_HALF(w);
2974 
2975  assert(UPPER_HALF(w) != 0); /* no borrow out should be possible */
2976 
2977  z->sign = MP_ZPOS;
2978  CLAMP(z);
2979 
2980  return 1;
2981 }
#define MP_DIGIT_MAX
Definition: imath.h:48
#define MP_DIGIT_BIT
Definition: imath.h:94
const mp_sign MP_ZPOS
Definition: imath.c:86
static mp_word UPPER_HALF(mp_word W)
Definition: imath.c:256
#define assert(TEST)
Definition: imath.c:73
static void CLAMP(mp_int z_)
Definition: imath.c:168
mp_sign sign
Definition: imath.h:58
static bool s_pad(mp_int z, mp_size min)
Definition: imath.c:2253
static mp_digit LOWER_HALF(mp_word W)
Definition: imath.c:261
unsigned int mp_size
Definition: imath.h:33
static mp_digit * MP_DIGITS(mp_int Z)
Definition: imath.h:64
uint32 mp_digit
Definition: imath.h:46
uint64 mp_word
Definition: imath.h:47

◆ s_realloc()

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

Definition at line 2227 of file imath.c.

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

Referenced by s_pad().

2228 {
2229 #if IMATH_DEBUG
2230  mp_digit *new = s_alloc(nsize);
2231 
2232  assert(new != NULL);
2233 
2234  for (mp_size ix = 0; ix < nsize; ++ix)
2235  new[ix] = fill;
2236  memcpy(new, old, osize * sizeof(mp_digit));
2237 #else
2238  mp_digit *new = px_realloc(old, nsize * sizeof(mp_digit));
2239 
2240  assert(new != NULL);
2241 #endif
2242 
2243  return new;
2244 }
static void fill(int length, int max, char filler, FILE *fp)
Definition: fe-print.c:761
static mp_digit * s_alloc(mp_size num)
Definition: imath.c:2213
#define assert(TEST)
Definition: imath.c:73
#define px_realloc(p, s)
Definition: px.h:45
unsigned int mp_size
Definition: imath.h:33
uint32 mp_digit
Definition: imath.h:46

◆ s_reduce()

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

Definition at line 3093 of file imath.c.

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

Referenced by GROW(), and s_embar().

3094 {
3095  mp_size um = MP_USED(m),
3096  umb_p1,
3097  umb_m1;
3098 
3099  umb_p1 = (um + 1) * MP_DIGIT_BIT;
3100  umb_m1 = (um - 1) * MP_DIGIT_BIT;
3101 
3102  if (mp_int_copy(x, q1) != MP_OK)
3103  return 0;
3104 
3105  /* Compute q2 = floor((floor(x / b^(k-1)) * mu) / b^(k+1)) */
3106  s_qdiv(q1, umb_m1);
3107  UMUL(q1, mu, q2);
3108  s_qdiv(q2, umb_p1);
3109 
3110  /* Set x = x mod b^(k+1) */
3111  s_qmod(x, umb_p1);
3112 
3113  /*
3114  * Now, q is a guess for the quotient a / m. Compute x - q * m mod
3115  * b^(k+1), replacing x. This may be off by a factor of 2m, but no more
3116  * than that.
3117  */
3118  UMUL(q2, m, q1);
3119  s_qmod(q1, umb_p1);
3120  (void) mp_int_sub(x, q1, x); /* can't fail */
3121 
3122  /*
3123  * The result may be < 0; if it is, add b^(k+1) to pin it in the proper
3124  * range.
3125  */
3126  if ((CMPZ(x) < 0) && !s_qsub(x, umb_p1))
3127  return 0;
3128 
3129  /*
3130  * If x > m, we need to back it off until it is in range. This will be
3131  * required at most twice.
3132  */
3133  if (mp_int_compare(x, m) >= 0)
3134  {
3135  (void) mp_int_sub(x, m, x);
3136  if (mp_int_compare(x, m) >= 0)
3137  {
3138  (void) mp_int_sub(x, m, x);
3139  }
3140  }
3141 
3142  /* At this point, x has been properly reduced. */
3143  return 1;
3144 }
static mp_size MP_USED(mp_int Z)
Definition: imath.h:74
#define MP_DIGIT_BIT
Definition: imath.h:94
static int CMPZ(mp_int Z)
Definition: imath.c:248
static void s_qmod(mp_int z, mp_size p2)
Definition: imath.c:2857
mp_result mp_int_copy(mp_int a, mp_int c)
Definition: imath.c:611
static void UMUL(mp_int X, mp_int Y, mp_int Z)
Definition: imath.c:438
mp_result mp_int_sub(mp_int a, mp_int b, mp_int c)
Definition: imath.c:778
const mp_result MP_OK
Definition: imath.c:75
static void s_qdiv(mp_int z, mp_size p2)
Definition: imath.c:2802
unsigned int mp_size
Definition: imath.h:33
static int s_qsub(mp_int z, mp_size p2)
Definition: imath.c:2953
int mp_int_compare(mp_int a, mp_int b)
Definition: imath.c:1274

◆ s_round_prec()

static mp_size s_round_prec ( mp_size  P)
inlinestatic

Definition at line 124 of file imath.c.

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

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

◆ s_tobin()

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

Definition at line 3538 of file imath.c.

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

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

3539 {
3540  int pos = 0,
3541  limit = *limpos;
3542  mp_size uz = MP_USED(z);
3543  mp_digit *dz = MP_DIGITS(z);
3544 
3545  while (uz > 0 && pos < limit)
3546  {
3547  mp_digit d = *dz++;
3548  int i;
3549 
3550  for (i = sizeof(mp_digit); i > 0 && pos < limit; --i)
3551  {
3552  buf[pos++] = (unsigned char) d;
3553  d >>= CHAR_BIT;
3554 
3555  /* Don't write leading zeroes */
3556  if (d == 0 && uz == 1)
3557  i = 0; /* exit loop without signaling truncation */
3558  }
3559 
3560  /* Detect truncation (loop exited with pos >= limit) */
3561  if (i > 0)
3562  break;
3563 
3564  --uz;
3565  }
3566 
3567  if (pad != 0 && (buf[pos - 1] >> (CHAR_BIT - 1)))
3568  {
3569  if (pos < limit)
3570  {
3571  buf[pos++] = 0;
3572  }
3573  else
3574  {
3575  uz = 1;
3576  }
3577  }
3578 
3579  /* Digits are in reverse order, fix that */
3580  REV(buf, pos);
3581 
3582  /* Return the number of bytes actually written */
3583  *limpos = pos;
3584 
3585  return (uz == 0) ? MP_OK : MP_TRUNC;
3586 }
static void REV(unsigned char *A, int N)
Definition: imath.c:152
static mp_size MP_USED(mp_int Z)
Definition: imath.h:74
const mp_result MP_TRUNC
Definition: imath.c:81
static char * buf
Definition: pg_test_fsync.c:68
const mp_result MP_OK
Definition: imath.c:75
unsigned int mp_size
Definition: imath.h:33
int i
static mp_digit * MP_DIGITS(mp_int Z)
Definition: imath.h:64
uint32 mp_digit
Definition: imath.h:46

◆ s_uadd()

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

Definition at line 2387 of file imath.c.

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

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

2389 {
2390  mp_size pos;
2391  mp_word w = 0;
2392 
2393  /* Insure that da is the longer of the two to simplify later code */
2394  if (size_b > size_a)
2395  {
2396  SWAP(mp_digit *, da, db);
2397  SWAP(mp_size, size_a, size_b);
2398  }
2399 
2400  /* Add corresponding digits until the shorter number runs out */
2401  for (pos = 0; pos < size_b; ++pos, ++da, ++db, ++dc)
2402  {
2403  w = w + (mp_word) *da + (mp_word) *db;
2404  *dc = LOWER_HALF(w);
2405  w = UPPER_HALF(w);
2406  }
2407 
2408  /* Propagate carries as far as necessary */
2409  for ( /* */ ; pos < size_a; ++pos, ++da, ++dc)
2410  {
2411  w = w + *da;
2412 
2413  *dc = LOWER_HALF(w);
2414  w = UPPER_HALF(w);
2415  }
2416 
2417  /* Return carry out */
2418  return (mp_digit) w;
2419 }
static mp_word UPPER_HALF(mp_word W)
Definition: imath.c:256
static mp_digit LOWER_HALF(mp_word W)
Definition: imath.c:261
unsigned int mp_size
Definition: imath.h:33
#define SWAP(T, A, B)
Definition: imath.c:194
uint32 mp_digit
Definition: imath.h:46
uint64 mp_word
Definition: imath.h:47

◆ s_ucmp()

static int s_ucmp ( mp_int  a,
mp_int  b 
)
static

Definition at line 2342 of file imath.c.

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

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

2343 {
2344  mp_size ua = MP_USED(a),
2345  ub = MP_USED(b);
2346 
2347  if (ua > ub)
2348  {
2349  return 1;
2350  }
2351  else if (ub > ua)
2352  {
2353  return -1;
2354  }
2355  else
2356  {
2357  return s_cdig(MP_DIGITS(a), MP_DIGITS(b), ua);
2358  }
2359 }
static mp_size MP_USED(mp_int Z)
Definition: imath.h:74
static int s_cdig(mp_digit *da, mp_digit *db, mp_size len)
Definition: imath.c:2301
unsigned int mp_size
Definition: imath.h:33
static mp_digit * MP_DIGITS(mp_int Z)
Definition: imath.h:64

◆ s_udiv_knuth()

static mp_result s_udiv_knuth ( mp_int  a,
mp_int  b 
)
static

Definition at line 3248 of file imath.c.

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

Referenced by GROW(), and mp_int_div().

3249 {
3250  /* Force signs to positive */
3251  u->sign = MP_ZPOS;
3252  v->sign = MP_ZPOS;
3253 
3254  /* Use simple division algorithm when v is only one digit long */
3255  if (MP_USED(v) == 1)
3256  {
3257  mp_digit d,
3258  rem;
3259 
3260  d = v->digits[0];
3261  rem = s_ddiv(u, d);
3262  mp_int_set_value(v, rem);
3263  return MP_OK;
3264  }
3265 
3266  /*
3267  * Algorithm D
3268  *
3269  * The n and m variables are defined as used by Knuth. u is an n digit
3270  * number with digits u_{n-1}..u_0. v is an n+m digit number with digits
3271  * from v_{m+n-1}..v_0. We require that n > 1 and m >= 0
3272  */
3273  mp_size n = MP_USED(v);
3274  mp_size m = MP_USED(u) - n;
3275 
3276  assert(n > 1);
3277  /* assert(m >= 0) follows because m is unsigned. */
3278 
3279  /*
3280  * D1: Normalize. The normalization step provides the necessary condition
3281  * for Theorem B, which states that the quotient estimate for q_j, call it
3282  * qhat
3283  *
3284  * qhat = u_{j+n}u_{j+n-1} / v_{n-1}
3285  *
3286  * is bounded by
3287  *
3288  * qhat - 2 <= q_j <= qhat.
3289  *
3290  * That is, qhat is always greater than the actual quotient digit q, and
3291  * it is never more than two larger than the actual quotient digit.
3292  */
3293  int k = s_norm(u, v);
3294 
3295  /*
3296  * Extend size of u by one if needed.
3297  *
3298  * The algorithm begins with a value of u that has one more digit of
3299  * input. The normalization step sets u_{m+n}..u_0 = 2^k * u_{m+n-1}..u_0.
3300  * If the multiplication did not increase the number of digits of u, we
3301  * need to add a leading zero here.
3302  */
3303  if (k == 0 || MP_USED(u) != m + n + 1)
3304  {
3305  if (!s_pad(u, m + n + 1))
3306  return MP_MEMORY;
3307  u->digits[m + n] = 0;
3308  u->used = m + n + 1;
3309  }
3310 
3311  /*
3312  * Add a leading 0 to v.
3313  *
3314  * The multiplication in step D4 multiplies qhat * 0v_{n-1}..v_0. We need
3315  * to add the leading zero to v here to ensure that the multiplication
3316  * will produce the full n+1 digit result.
3317  */
3318  if (!s_pad(v, n + 1))
3319  return MP_MEMORY;
3320  v->digits[n] = 0;
3321 
3322  /*
3323  * Initialize temporary variables q and t. q allocates space for m+1
3324  * digits to store the quotient digits t allocates space for n+1 digits to
3325  * hold the result of q_j*v
3326  */
3327  DECLARE_TEMP(2);
3328  REQUIRE(GROW(TEMP(0), m + 1));
3329  REQUIRE(GROW(TEMP(1), n + 1));
3330 
3331  /* D2: Initialize j */
3332  int j = m;
3333  mpz_t r;
3334 
3335  r.digits = MP_DIGITS(u) + j; /* The contents of r are shared with u */
3336  r.used = n + 1;
3337  r.sign = MP_ZPOS;
3338  r.alloc = MP_ALLOC(u);
3339  ZERO(TEMP(1)->digits, TEMP(1)->alloc);
3340 
3341  /* Calculate the m+1 digits of the quotient result */
3342  for (; j >= 0; j--)
3343  {
3344  /* D3: Calculate q' */
3345  /* r->digits is aligned to position j of the number u */
3346  mp_word pfx,
3347  qhat;
3348 
3349  pfx = r.digits[n];
3350  pfx <<= MP_DIGIT_BIT / 2;
3351  pfx <<= MP_DIGIT_BIT / 2;
3352  pfx |= r.digits[n - 1]; /* pfx = u_{j+n}{j+n-1} */
3353 
3354  qhat = pfx / v->digits[n - 1];
3355 
3356  /*
3357  * Check to see if qhat > b, and decrease qhat if so. Theorem B
3358  * guarantess that qhat is at most 2 larger than the actual value, so
3359  * it is possible that qhat is greater than the maximum value that
3360  * will fit in a digit
3361  */
3362  if (qhat > MP_DIGIT_MAX)
3363  qhat = MP_DIGIT_MAX;
3364 
3365  /*
3366  * D4,D5,D6: Multiply qhat * v and test for a correct value of q
3367  *
3368  * We proceed a bit different than the way described by Knuth. This
3369  * way is simpler but less efficent. Instead of doing the multiply and
3370  * subtract then checking for underflow, we first do the multiply of
3371  * qhat * v and see if it is larger than the current remainder r. If
3372  * it is larger, we decrease qhat by one and try again. We may need to
3373  * decrease qhat one more time before we get a value that is smaller
3374  * than r.
3375  *
3376  * This way is less efficent than Knuth becuase we do more multiplies,
3377  * but we do not need to worry about underflow this way.
3378  */
3379  /* t = qhat * v */
3380  s_dbmul(MP_DIGITS(v), (mp_digit) qhat, TEMP(1)->digits, n + 1);
3381  TEMP(1)->used = n + 1;
3382  CLAMP(TEMP(1));
3383 
3384  /* Clamp r for the comparison. Comparisons do not like leading zeros. */
3385  CLAMP(&r);
3386  if (s_ucmp(TEMP(1), &r) > 0)
3387  { /* would the remainder be negative? */
3388  qhat -= 1; /* try a smaller q */
3389  s_dbmul(MP_DIGITS(v), (mp_digit) qhat, TEMP(1)->digits, n + 1);
3390  TEMP(1)->used = n + 1;
3391  CLAMP(TEMP(1));
3392  if (s_ucmp(TEMP(1), &r) > 0)
3393  { /* would the r