PostgreSQL Source Code  git master
imath.h File Reference
#include <limits.h>
Include dependency graph for imath.h:
This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Data Structures

struct  mpz_t
 

Macros

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

Typedefs

typedef unsigned char mp_sign
 
typedef unsigned int mp_size
 
typedef int mp_result
 
typedef long mp_small
 
typedef unsigned long mp_usmall
 
typedef uint32 mp_digit
 
typedef uint64 mp_word
 
typedef struct mpz_tmp_int
 

Functions

static mp_digitMP_DIGITS (mp_int Z)
 
static mp_size MP_ALLOC (mp_int Z)
 
static mp_size MP_USED (mp_int Z)
 
static mp_sign MP_SIGN (mp_int Z)
 
void mp_int_default_precision (mp_size ndigits)
 
void mp_int_multiply_threshold (mp_size ndigits)
 
static bool mp_int_is_odd (mp_int z)
 
static bool mp_int_is_even (mp_int z)
 
mp_result mp_int_init (mp_int z)
 
mp_int mp_int_alloc (void)
 
mp_result mp_int_init_size (mp_int z, mp_size prec)
 
mp_result mp_int_init_copy (mp_int z, mp_int old)
 
mp_result mp_int_init_value (mp_int z, mp_small value)
 
mp_result mp_int_init_uvalue (mp_int z, mp_usmall uvalue)
 
mp_result mp_int_set_value (mp_int z, mp_small value)
 
mp_result mp_int_set_uvalue (mp_int z, mp_usmall uvalue)
 
void mp_int_clear (mp_int z)
 
void mp_int_free (mp_int z)
 
mp_result mp_int_copy (mp_int a, mp_int c)
 
void mp_int_swap (mp_int a, mp_int c)
 
void mp_int_zero (mp_int z)
 
mp_result mp_int_abs (mp_int a, mp_int c)
 
mp_result mp_int_neg (mp_int a, mp_int c)
 
mp_result mp_int_add (mp_int a, mp_int b, mp_int c)
 
mp_result mp_int_add_value (mp_int a, mp_small value, mp_int c)
 
mp_result mp_int_sub (mp_int a, mp_int b, mp_int c)
 
mp_result mp_int_sub_value (mp_int a, mp_small value, mp_int c)
 
mp_result mp_int_mul (mp_int a, mp_int b, mp_int c)
 
mp_result mp_int_mul_value (mp_int a, mp_small value, mp_int c)
 
mp_result mp_int_mul_pow2 (mp_int a, mp_small p2, mp_int c)
 
mp_result mp_int_sqr (mp_int a, mp_int c)
 
mp_result mp_int_div (mp_int a, mp_int b, mp_int q, mp_int r)
 
mp_result mp_int_div_value (mp_int a, mp_small value, mp_int q, mp_small *r)
 
mp_result mp_int_div_pow2 (mp_int a, mp_small p2, mp_int q, mp_int r)
 
mp_result mp_int_mod (mp_int a, mp_int m, mp_int c)
 
mp_result mp_int_expt (mp_int a, mp_small b, mp_int c)
 
mp_result mp_int_expt_value (mp_small a, mp_small b, mp_int c)
 
mp_result mp_int_expt_full (mp_int a, mp_int b, mp_int c)
 
static mp_result mp_int_mod_value (mp_int a, mp_small value, mp_small *r)
 
int mp_int_compare (mp_int a, mp_int b)
 
int mp_int_compare_unsigned (mp_int a, mp_int b)
 
int mp_int_compare_zero (mp_int z)
 
int mp_int_compare_value (mp_int z, mp_small v)
 
int mp_int_compare_uvalue (mp_int z, mp_usmall uv)
 
bool mp_int_divisible_value (mp_int a, mp_small v)
 
int mp_int_is_pow2 (mp_int z)
 
mp_result mp_int_exptmod (mp_int a, mp_int b, mp_int m, mp_int c)
 
mp_result mp_int_exptmod_evalue (mp_int a, mp_small value, mp_int m, mp_int c)
 
mp_result mp_int_exptmod_bvalue (mp_small value, mp_int b, mp_int m, mp_int c)
 
mp_result mp_int_exptmod_known (mp_int a, mp_int b, mp_int m, mp_int mu, mp_int c)
 
mp_result mp_int_redux_const (mp_int m, mp_int c)
 
mp_result mp_int_invmod (mp_int a, mp_int m, mp_int c)
 
mp_result mp_int_gcd (mp_int a, mp_int b, mp_int c)
 
mp_result mp_int_egcd (mp_int a, mp_int b, mp_int c, mp_int x, mp_int y)
 
mp_result mp_int_lcm (mp_int a, mp_int b, mp_int c)
 
mp_result mp_int_root (mp_int a, mp_small b, mp_int c)
 
static mp_result mp_int_sqrt (mp_int a, mp_int c)
 
mp_result mp_int_to_int (mp_int z, mp_small *out)
 
mp_result mp_int_to_uint (mp_int z, mp_usmall *out)
 
mp_result mp_int_to_string (mp_int z, mp_size radix, char *str, int limit)
 
mp_result mp_int_string_len (mp_int z, mp_size radix)
 
mp_result mp_int_read_string (mp_int z, mp_size radix, const char *str)
 
mp_result mp_int_read_cstring (mp_int z, mp_size radix, const char *str, char **end)
 
mp_result mp_int_count_bits (mp_int z)
 
mp_result mp_int_to_binary (mp_int z, unsigned char *buf, int limit)
 
mp_result mp_int_read_binary (mp_int z, unsigned char *buf, int len)
 
mp_result mp_int_binary_len (mp_int z)
 
mp_result mp_int_to_unsigned (mp_int z, unsigned char *buf, int limit)
 
mp_result mp_int_read_unsigned (mp_int z, unsigned char *buf, int len)
 
mp_result mp_int_unsigned_len (mp_int z)
 
const char * mp_error_string (mp_result res)
 

Variables

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

Macro Definition Documentation

◆ MP_DIGIT_BIT

◆ MP_DIGIT_MAX

#define MP_DIGIT_MAX   (PG_UINT32_MAX * UINT64CONST(1))

Definition at line 48 of file imath.h.

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

◆ MP_MAX_RADIX

#define MP_MAX_RADIX   36

Definition at line 101 of file imath.h.

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

◆ MP_MIN_RADIX

#define MP_MIN_RADIX   2

Definition at line 100 of file imath.h.

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

◆ MP_SMALL_MAX

#define MP_SMALL_MAX   LONG_MAX

Definition at line 97 of file imath.h.

Referenced by mp_int_to_int().

◆ MP_SMALL_MIN

#define MP_SMALL_MIN   LONG_MIN

Definition at line 96 of file imath.h.

Referenced by mp_int_to_int().

◆ MP_USMALL_MAX

#define MP_USMALL_MAX   ULONG_MAX

Definition at line 98 of file imath.h.

Referenced by mp_int_to_uint().

◆ MP_WORD_BIT

#define MP_WORD_BIT   (sizeof(mp_word) * CHAR_BIT)

Definition at line 95 of file imath.h.

Referenced by HIGH_BIT_SET().

◆ MP_WORD_MAX

#define MP_WORD_MAX   (PG_UINT64_MAX)

Definition at line 49 of file imath.h.

Referenced by ADD_WILL_OVERFLOW().

Typedef Documentation

◆ mp_digit

typedef uint32 mp_digit

Definition at line 46 of file imath.h.

◆ mp_int

typedef struct mpz_t * mp_int

◆ mp_result

typedef int mp_result

Definition at line 34 of file imath.h.

◆ mp_sign

typedef unsigned char mp_sign

Definition at line 32 of file imath.h.

◆ mp_size

typedef unsigned int mp_size

Definition at line 33 of file imath.h.

◆ mp_small

typedef long mp_small

Definition at line 35 of file imath.h.

◆ mp_usmall

typedef unsigned long mp_usmall

Definition at line 36 of file imath.h.

◆ mp_word

typedef uint64 mp_word

Definition at line 47 of file imath.h.

Function Documentation

◆ MP_ALLOC()

static mp_size MP_ALLOC ( mp_int  Z)
inlinestatic

Definition at line 69 of file imath.h.

References mpz_t::alloc.

Referenced by s_pad(), and s_udiv_knuth().

70 {
71  return Z->alloc;
72 }
mp_size alloc
Definition: imath.h:56

◆ MP_DIGITS()

◆ mp_error_string()

const char* mp_error_string ( mp_result  res)

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

Definition at line 2184 of file imath.c.

References fill(), s_error_msg, and s_unknown_err.

Referenced by mp_int_sqrt().

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
#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
static struct @143 value
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 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
static struct @143 value
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
#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
static struct @143 value
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
#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
static struct @143 value
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
#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
static struct @143 value
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
#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
static struct @143 value
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_even()

◆ mp_int_is_odd()

static bool mp_int_is_odd ( mp_int  z)
inlinestatic

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

Definition at line 122 of file imath.h.

References mpz_t::digits.

Referenced by mp_int_egcd(), and mp_int_gcd().

123 {
124  return (z->digits[0] & 1) != 0;
125 }
mp_digit * digits
Definition: imath.h:55

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

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

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

Definition at line 249 of file imath.h.

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

250 {
251  return mp_int_div_value(a, value, 0, r);
252 }
mp_result mp_int_div_value(mp_int a, mp_small value, mp_int q, mp_small *r)
Definition: imath.c:1141
static struct @143 value

◆ 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
#define MP_VALUE_DIGITS(V)
Definition: imath.c:119
static struct @143 value
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:67
#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:1206
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:67
#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
#define MP_VALUE_DIGITS(V)
Definition: imath.c:119
static struct @143 value
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_sqrt()

static mp_result mp_int_sqrt ( mp_int  a,
mp_int  c 
)
inlinestatic

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

Definition at line 335 of file imath.h.

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

336 {
337  return mp_int_root(a, 2, c);
338 }
mp_result mp_int_root(mp_int a, mp_small b, mp_int c)
Definition: imath.c:1762

◆ 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
#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
static struct @143 value
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:67
#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:67
#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

◆ MP_SIGN()

◆ MP_USED()

Variable Documentation

◆ MP_BADARG

const mp_result MP_BADARG

Definition at line 82 of file imath.c.

Referenced by mp_int_init(), and MP_SIGN().

◆ MP_FALSE

const mp_result MP_FALSE

Definition at line 76 of file imath.c.

Referenced by MP_SIGN().

◆ MP_MEMORY

◆ MP_MINERR

const mp_result MP_MINERR

Definition at line 83 of file imath.c.

Referenced by MP_SIGN().

◆ MP_NEG

◆ MP_OK

◆ MP_RANGE

◆ MP_TRUE

const mp_result MP_TRUE

Definition at line 77 of file imath.c.

Referenced by MP_SIGN().

◆ MP_TRUNC

const mp_result MP_TRUNC

Definition at line 81 of file imath.c.

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

◆ MP_UNDEF

◆ MP_ZPOS