PostgreSQL Source Code  git master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros
imath.h File Reference
#include <limits.h>
Include dependency graph for imath.h:
This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Data Structures

struct  mpz
 

Macros

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

Typedefs

typedef unsigned char mp_sign
 
typedef unsigned int mp_size
 
typedef int mp_result
 
typedef uint32 mp_digit
 
typedef uint64 mp_word
 
typedef struct mpz mpz_t
 
typedef struct mpzmp_int
 

Functions

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

Variables

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

Macro Definition Documentation

#define MP_ALLOC (   Z)    ((Z)->alloc)

Definition at line 68 of file imath.h.

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

#define MP_DIGIT_MAX   0xFFFFFFFFULL

Definition at line 47 of file imath.h.

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

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

Definition at line 91 of file imath.h.

Referenced by mp_int_egcd().

#define mp_int_is_odd (   Z)    ((Z)->digits[0] & 1)

Definition at line 90 of file imath.h.

Referenced by mp_int_egcd(), and mp_int_gcd().

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

Definition at line 129 of file imath.h.

#define MP_MAX_RADIX   36

Definition at line 85 of file imath.h.

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

#define MP_MIN_RADIX   2

Definition at line 84 of file imath.h.

#define MP_WORD_BIT   (sizeof(mp_word) * CHAR_BIT)

Definition at line 82 of file imath.h.

#define MP_WORD_MAX   0xFFFFFFFFFFFFFFFFULL

Definition at line 48 of file imath.h.

#define USE_LONG_LONG

Definition at line 35 of file imath.h.

Typedef Documentation

Definition at line 44 of file imath.h.

typedef struct mpz * mp_int

Definition at line 41 of file imath.h.

typedef unsigned char mp_sign

Definition at line 39 of file imath.h.

typedef unsigned int mp_size

Definition at line 40 of file imath.h.

typedef uint64 mp_word

Definition at line 45 of file imath.h.

typedef struct mpz mpz_t

Function Documentation

const char* mp_error_string ( mp_result  res)

Definition at line 2259 of file imath.c.

References s_error_msg, and s_unknown_err.

2260 {
2261  int ix;
2262 
2263  if (res > 0)
2264  return s_unknown_err;
2265 
2266  res = -res;
2267  for (ix = 0; ix < res && s_error_msg[ix] != NULL; ++ix)
2268  ;
2269 
2270  if (s_error_msg[ix] != NULL)
2271  return s_error_msg[ix];
2272  else
2273  return s_unknown_err;
2274 }
static const char * s_error_msg[]
Definition: imath.c:56
static const char * s_unknown_err
Definition: imath.c:55
mp_size mp_get_default_precision ( void  )

Definition at line 319 of file imath.c.

References default_precision.

320 {
321  return default_precision;
322 }
static mp_size default_precision
Definition: imath.c:167
mp_size mp_get_multiply_threshold ( void  )

Definition at line 341 of file imath.c.

References multiply_threshold.

342 {
343  return multiply_threshold;
344 }
static mp_size multiply_threshold
Definition: imath.c:170
mp_result mp_int_abs ( mp_int  a,
mp_int  c 
)

Definition at line 569 of file imath.c.

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

Referenced by mp_int_egcd(), and mp_int_gcd().

570 {
571  mp_result res;
572 
573  CHECK(a != NULL && c != NULL);
574 
575  if ((res = mp_int_copy(a, c)) != MP_OK)
576  return res;
577 
578  MP_SIGN(c) = MP_ZPOS;
579  return MP_OK;
580 }
mp_result mp_int_copy(mp_int a, mp_int c)
Definition: imath.c:510
const mp_sign MP_ZPOS
Definition: imath.c:53
const mp_result MP_OK
Definition: imath.c:43
#define MP_SIGN(Z)
Definition: imath.h:70
int mp_result
Definition: imath.h:41
#define CHECK(TEST)
Definition: imath.c:74
mp_result mp_int_add ( mp_int  a,
mp_int  b,
mp_int  c 
)

Definition at line 607 of file imath.c.

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

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

608 {
609  mp_size ua,
610  ub,
611  uc,
612  max;
613 
614  CHECK(a != NULL && b != NULL && c != NULL);
615 
616  ua = MP_USED(a);
617  ub = MP_USED(b);
618  uc = MP_USED(c);
619  max = MAX(ua, ub);
620 
621  if (MP_SIGN(a) == MP_SIGN(b))
622  {
623  /* Same sign -- add magnitudes, preserve sign of addends */
624  mp_digit carry;
625 
626  if (!s_pad(c, max))
627  return MP_MEMORY;
628 
629  carry = s_uadd(MP_DIGITS(a), MP_DIGITS(b), MP_DIGITS(c), ua, ub);
630  uc = max;
631 
632  if (carry)
633  {
634  if (!s_pad(c, max + 1))
635  return MP_MEMORY;
636 
637  c->digits[max] = carry;
638  ++uc;
639  }
640 
641  MP_USED(c) = uc;
642  MP_SIGN(c) = MP_SIGN(a);
643 
644  }
645  else
646  {
647  /* Different signs -- subtract magnitudes, preserve sign of greater */
648  mp_int x,
649  y;
650  int cmp = s_ucmp(a, b); /* magnitude comparison, sign ignored */
651 
652  /* Set x to max(a, b), y to min(a, b) to simplify later code */
653  if (cmp >= 0)
654  {
655  x = a;
656  y = b;
657  }
658  else
659  {
660  x = b;
661  y = a;
662  }
663 
664  if (!s_pad(c, MP_USED(x)))
665  return MP_MEMORY;
666 
667  /* Subtract smaller from larger */
668  s_usub(MP_DIGITS(x), MP_DIGITS(y), MP_DIGITS(c), MP_USED(x), MP_USED(y));
669  MP_USED(c) = MP_USED(x);
670  CLAMP(c);
671 
672  /* Give result the sign of the larger */
673  MP_SIGN(c) = MP_SIGN(x);
674  }
675 
676  return MP_OK;
677 }
static int s_pad(mp_int z, mp_size min)
Definition: imath.c:2324
#define MAX(A, B)
Definition: imath.c:139
mp_digit * digits
Definition: imath.h:59
#define MP_DIGITS(Z)
Definition: imath.h:67
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:2464
const mp_result MP_OK
Definition: imath.c:43
static void s_usub(mp_digit *da, mp_digit *db, mp_digit *dc, mp_size size_a, mp_size size_b)
Definition: imath.c:2503
#define MP_USED(Z)
Definition: imath.h:69
#define MP_SIGN(Z)
Definition: imath.h:70
static int s_ucmp(mp_int a, mp_int b)
Definition: imath.c:2425
unsigned int mp_size
Definition: imath.h:40
#define CHECK(TEST)
Definition: imath.c:74
#define CLAMP(Z)
Definition: imath.c:131
const mp_result MP_MEMORY
Definition: imath.c:46
uint32 mp_digit
Definition: imath.h:44
Definition: imath.h:57
static int cmp(const chr *x, const chr *y, size_t len)
Definition: regc_locale.c:742
mp_result mp_int_add_value ( mp_int  a,
int  value,
mp_int  c 
)

Definition at line 684 of file imath.c.

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

685 {
686  mpz_t vtmp;
688 
689  s_fake(&vtmp, value, vbuf);
690 
691  return mp_int_add(a, &vtmp, c);
692 }
#define MP_VALUE_DIGITS(V)
Definition: imath.c:109
static struct @121 value
mp_result mp_int_add(mp_int a, mp_int b, mp_int c)
Definition: imath.c:607
static void s_fake(mp_int z, int value, mp_digit vbuf[])
Definition: imath.c:2364
uint32 mp_digit
Definition: imath.h:44
Definition: imath.h:57
mp_int mp_int_alloc ( void  )

Definition at line 371 of file imath.c.

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

Referenced by mp_new().

372 {
373  mp_int out = px_alloc(sizeof(mpz_t));
374 
375  assert(out != NULL);
376  out->digits = NULL;
377  out->used = 0;
378  out->alloc = 0;
379  out->sign = 0;
380 
381  return out;
382 }
mp_digit * digits
Definition: imath.h:59
mp_size used
Definition: imath.h:61
#define assert(TEST)
Definition: imath.c:37
mp_sign sign
Definition: imath.h:62
#define px_alloc(s)
Definition: px.h:44
mp_size alloc
Definition: imath.h:60
Definition: imath.h:57
mp_result mp_int_binary_len ( mp_int  z)

Definition at line 2170 of file imath.c.

References mp_int_count_bits(), and mp_int_unsigned_len().

2171 {
2172  mp_result res = mp_int_count_bits(z);
2173  int bytes = mp_int_unsigned_len(z);
2174 
2175  if (res <= 0)
2176  return res;
2177 
2178  bytes = (res + (CHAR_BIT - 1)) / CHAR_BIT;
2179 
2180  /*
2181  * If the highest-order bit falls exactly on a byte boundary, we need to
2182  * pad with an extra byte so that the sign will be read correctly when
2183  * reading it back in.
2184  */
2185  if (bytes * CHAR_BIT == res)
2186  ++bytes;
2187 
2188  return bytes;
2189 }
mp_result mp_int_count_bits(mp_int z)
Definition: imath.c:2073
mp_result mp_int_unsigned_len(mp_int z)
Definition: imath.c:2241
int mp_result
Definition: imath.h:41
void mp_int_clear ( mp_int  z)

Definition at line 478 of file imath.c.

References MP_DIGITS, and s_free.

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

479 {
480  if (z == NULL)
481  return;
482 
483  if (MP_DIGITS(z) != NULL)
484  {
485  s_free(MP_DIGITS(z));
486  MP_DIGITS(z) = NULL;
487  }
488 }
#define s_free(P)
Definition: imath.c:182
#define MP_DIGITS(Z)
Definition: imath.h:67
int mp_int_compare ( mp_int  a,
mp_int  b 
)

Definition at line 1242 of file imath.c.

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

Referenced by mp_int_egcd(), and s_reduce().

1243 {
1244  mp_sign sa;
1245 
1246  CHECK(a != NULL && b != NULL);
1247 
1248  sa = MP_SIGN(a);
1249  if (sa == MP_SIGN(b))
1250  {
1251  int cmp = s_ucmp(a, b);
1252 
1253  /*
1254  * If they're both zero or positive, the normal comparison applies; if
1255  * both negative, the sense is reversed.
1256  */
1257  if (sa == MP_ZPOS)
1258  return cmp;
1259  else
1260  return -cmp;
1261 
1262  }
1263  else
1264  {
1265  if (sa == MP_ZPOS)
1266  return 1;
1267  else
1268  return -1;
1269  }
1270 }
const mp_sign MP_ZPOS
Definition: imath.c:53
#define MP_SIGN(Z)
Definition: imath.h:70
unsigned char mp_sign
Definition: imath.h:39
static int s_ucmp(mp_int a, mp_int b)
Definition: imath.c:2425
#define CHECK(TEST)
Definition: imath.c:74
static int cmp(const chr *x, const chr *y, size_t len)
Definition: regc_locale.c:742
int mp_int_compare_unsigned ( mp_int  a,
mp_int  b 
)

Definition at line 1277 of file imath.c.

References NRCHECK, and s_ucmp().

Referenced by mp_int_sqrt().

1278 {
1279  NRCHECK(a != NULL && b != NULL);
1280 
1281  return s_ucmp(a, b);
1282 }
#define NRCHECK(TEST)
Definition: imath.c:75
static int s_ucmp(mp_int a, mp_int b)
Definition: imath.c:2425
int mp_int_compare_value ( mp_int  z,
int  value 
)

Definition at line 1306 of file imath.c.

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

Referenced by mp_int_invmod(), and mp_int_to_int().

1307 {
1308  mp_sign vsign = (value < 0) ? MP_NEG : MP_ZPOS;
1309  int cmp;
1310 
1311  CHECK(z != NULL);
1312 
1313  if (vsign == MP_SIGN(z))
1314  {
1315  cmp = s_vcmp(z, value);
1316 
1317  if (vsign == MP_ZPOS)
1318  return cmp;
1319  else
1320  return -cmp;
1321  }
1322  else
1323  {
1324  if (value < 0)
1325  return 1;
1326  else
1327  return -1;
1328  }
1329 }
const mp_sign MP_NEG
Definition: imath.c:52
const mp_sign MP_ZPOS
Definition: imath.c:53
static struct @121 value
#define MP_SIGN(Z)
Definition: imath.h:70
static int s_vcmp(mp_int a, int v)
Definition: imath.c:2443
unsigned char mp_sign
Definition: imath.h:39
#define CHECK(TEST)
Definition: imath.c:74
static int cmp(const chr *x, const chr *y, size_t len)
Definition: regc_locale.c:742
int mp_int_compare_zero ( mp_int  z)

Definition at line 1289 of file imath.c.

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

Referenced by mp_int_mul().

1290 {
1291  NRCHECK(z != NULL);
1292 
1293  if (MP_USED(z) == 1 && z->digits[0] == 0)
1294  return 0;
1295  else if (MP_SIGN(z) == MP_ZPOS)
1296  return 1;
1297  else
1298  return -1;
1299 }
mp_digit * digits
Definition: imath.h:59
#define NRCHECK(TEST)
Definition: imath.c:75
const mp_sign MP_ZPOS
Definition: imath.c:53
#define MP_USED(Z)
Definition: imath.h:69
#define MP_SIGN(Z)
Definition: imath.h:70
mp_result mp_int_copy ( mp_int  a,
mp_int  c 
)

Definition at line 510 of file imath.c.

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

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

511 {
512  CHECK(a != NULL && c != NULL);
513 
514  if (a != c)
515  {
516  mp_size ua = MP_USED(a);
517  mp_digit *da,
518  *dc;
519 
520  if (!s_pad(c, ua))
521  return MP_MEMORY;
522 
523  da = MP_DIGITS(a);
524  dc = MP_DIGITS(c);
525  COPY(da, dc, ua);
526 
527  MP_USED(c) = ua;
528  MP_SIGN(c) = MP_SIGN(a);
529  }
530 
531  return MP_OK;
532 }
static int s_pad(mp_int z, mp_size min)
Definition: imath.c:2324
#define MP_DIGITS(Z)
Definition: imath.h:67
const mp_result MP_OK
Definition: imath.c:43
#define MP_USED(Z)
Definition: imath.h:69
#define MP_SIGN(Z)
Definition: imath.h:70
unsigned int mp_size
Definition: imath.h:40
#define CHECK(TEST)
Definition: imath.c:74
const mp_result MP_MEMORY
Definition: imath.c:46
uint32 mp_digit
Definition: imath.h:44
#define COPY(P, Q, S)
Definition: imath.c:120
mp_result mp_int_count_bits ( mp_int  z)

Definition at line 2073 of file imath.c.

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

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

2074 {
2075  mp_size nbits = 0,
2076  uz;
2077  mp_digit d;
2078 
2079  CHECK(z != NULL);
2080 
2081  uz = MP_USED(z);
2082  if (uz == 1 && z->digits[0] == 0)
2083  return 1;
2084 
2085  --uz;
2086  nbits = uz * MP_DIGIT_BIT;
2087  d = z->digits[uz];
2088 
2089  while (d != 0)
2090  {
2091  d >>= 1;
2092  ++nbits;
2093  }
2094 
2095  return nbits;
2096 }
mp_digit * digits
Definition: imath.h:59
#define MP_DIGIT_BIT
Definition: imath.h:81
#define MP_USED(Z)
Definition: imath.h:69
unsigned int mp_size
Definition: imath.h:40
#define CHECK(TEST)
Definition: imath.c:74
uint32 mp_digit
Definition: imath.h:44
mp_result mp_int_div ( mp_int  a,
mp_int  b,
mp_int  q,
mp_int  r 
)

Definition at line 955 of file imath.c.

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

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

956 {
957  int cmp,
958  last = 0,
959  lg;
960  mp_result res = MP_OK;
961  mpz_t temp[2];
962  mp_int qout,
963  rout;
964  mp_sign sa = MP_SIGN(a),
965  sb = MP_SIGN(b);
966 
967  CHECK(a != NULL && b != NULL && q != r);
968 
969  if (CMPZ(b) == 0)
970  return MP_UNDEF;
971  else if ((cmp = s_ucmp(a, b)) < 0)
972  {
973  /*
974  * If |a| < |b|, no division is required: q = 0, r = a
975  */
976  if (r && (res = mp_int_copy(a, r)) != MP_OK)
977  return res;
978 
979  if (q)
980  mp_int_zero(q);
981 
982  return MP_OK;
983  }
984  else if (cmp == 0)
985  {
986  /*
987  * If |a| = |b|, no division is required: q = 1 or -1, r = 0
988  */
989  if (r)
990  mp_int_zero(r);
991 
992  if (q)
993  {
994  mp_int_zero(q);
995  q->digits[0] = 1;
996 
997  if (sa != sb)
998  MP_SIGN(q) = MP_NEG;
999  }
1000 
1001  return MP_OK;
1002  }
1003 
1004  /*
1005  * When |a| > |b|, real division is required. We need someplace to store
1006  * quotient and remainder, but q and r are allowed to be NULL or to
1007  * overlap with the inputs.
1008  */
1009  if ((lg = s_isp2(b)) < 0)
1010  {
1011  if (q && b != q && (res = mp_int_copy(a, q)) == MP_OK)
1012  {
1013  qout = q;
1014  }
1015  else
1016  {
1017  qout = TEMP(last);
1018  SETUP(mp_int_init_copy(TEMP(last), a), last);
1019  }
1020 
1021  if (r && a != r && (res = mp_int_copy(b, r)) == MP_OK)
1022  {
1023  rout = r;
1024  }
1025  else
1026  {
1027  rout = TEMP(last);
1028  SETUP(mp_int_init_copy(TEMP(last), b), last);
1029  }
1030 
1031  if ((res = s_udiv(qout, rout)) != MP_OK)
1032  goto CLEANUP;
1033  }
1034  else
1035  {
1036  if (q && (res = mp_int_copy(a, q)) != MP_OK)
1037  goto CLEANUP;
1038  if (r && (res = mp_int_copy(a, r)) != MP_OK)
1039  goto CLEANUP;
1040 
1041  if (q)
1042  s_qdiv(q, (mp_size) lg);
1043  qout = q;
1044  if (r)
1045  s_qmod(r, (mp_size) lg);
1046  rout = r;
1047  }
1048 
1049  /* Recompute signs for output */
1050  if (rout)
1051  {
1052  MP_SIGN(rout) = sa;
1053  if (CMPZ(rout) == 0)
1054  MP_SIGN(rout) = MP_ZPOS;
1055  }
1056  if (qout)
1057  {
1058  MP_SIGN(qout) = (sa == sb) ? MP_ZPOS : MP_NEG;
1059  if (CMPZ(qout) == 0)
1060  MP_SIGN(qout) = MP_ZPOS;
1061  }
1062 
1063  if (q && (res = mp_int_copy(qout, q)) != MP_OK)
1064  goto CLEANUP;
1065  if (r && (res = mp_int_copy(rout, r)) != MP_OK)
1066  goto CLEANUP;
1067 
1068 CLEANUP:
1069  while (--last >= 0)
1070  mp_int_clear(TEMP(last));
1071 
1072  return res;
1073 }
const mp_sign MP_NEG
Definition: imath.c:52
mp_digit * digits
Definition: imath.h:59
static void s_qmod(mp_int z, mp_size p2)
Definition: imath.c:2976
mp_result mp_int_copy(mp_int a, mp_int c)
Definition: imath.c:510
#define CMPZ(Z)
Definition: imath.c:146
const mp_sign MP_ZPOS
Definition: imath.c:53
mp_result mp_int_init_copy(mp_int z, mp_int old)
Definition: imath.c:412
#define SETUP(E, C)
Definition: imath.c:143
void mp_int_zero(mp_int z)
Definition: imath.c:555
#define TEMP(K)
Definition: imath.c:142
static int s_isp2(mp_int z)
Definition: imath.c:3143
const mp_result MP_OK
Definition: imath.c:43
const mp_result MP_UNDEF
Definition: imath.c:48
static void s_qdiv(mp_int z, mp_size p2)
Definition: imath.c:2919
#define MP_SIGN(Z)
Definition: imath.h:70
unsigned char mp_sign
Definition: imath.h:39
void mp_int_clear(mp_int z)
Definition: imath.c:478
static mp_result s_udiv(mp_int a, mp_int b)
Definition: imath.c:3399
static int s_ucmp(mp_int a, mp_int b)
Definition: imath.c:2425
int mp_result
Definition: imath.h:41
unsigned int mp_size
Definition: imath.h:40
#define CHECK(TEST)
Definition: imath.c:74
Definition: imath.h:57
static int cmp(const chr *x, const chr *y, size_t len)
Definition: regc_locale.c:742
mp_result mp_int_div_pow2 ( mp_int  a,
int  p2,
mp_int  q,
mp_int  r 
)

Definition at line 1146 of file imath.c.

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

Referenced by mp_int_sqrt().

1147 {
1148  mp_result res = MP_OK;
1149 
1150  CHECK(a != NULL && p2 >= 0 && q != r);
1151 
1152  if (q != NULL && (res = mp_int_copy(a, q)) == MP_OK)
1153  s_qdiv(q, (mp_size) p2);
1154 
1155  if (res == MP_OK && r != NULL && (res = mp_int_copy(a, r)) == MP_OK)
1156  s_qmod(r, (mp_size) p2);
1157 
1158  return res;
1159 }
static void s_qmod(mp_int z, mp_size p2)
Definition: imath.c:2976
mp_result mp_int_copy(mp_int a, mp_int c)
Definition: imath.c:510
const mp_result MP_OK
Definition: imath.c:43
static void s_qdiv(mp_int z, mp_size p2)
Definition: imath.c:2919
int mp_result
Definition: imath.h:41
unsigned int mp_size
Definition: imath.h:40
#define CHECK(TEST)
Definition: imath.c:74
mp_result mp_int_div_value ( mp_int  a,
int  value,
mp_int  q,
int *  r 
)

Definition at line 1119 of file imath.c.

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

Referenced by mp_int_divisible_value().

1120 {
1121  mpz_t vtmp,
1122  rtmp;
1124  mp_result res;
1125 
1126  if ((res = mp_int_init(&rtmp)) != MP_OK)
1127  return res;
1128  s_fake(&vtmp, value, vbuf);
1129 
1130  if ((res = mp_int_div(a, &vtmp, q, &rtmp)) != MP_OK)
1131  goto CLEANUP;
1132 
1133  if (r)
1134  (void) mp_int_to_int(&rtmp, r); /* can't fail */
1135 
1136 CLEANUP:
1137  mp_int_clear(&rtmp);
1138  return res;
1139 }
#define MP_VALUE_DIGITS(V)
Definition: imath.c:109
static struct @121 value
mp_result mp_int_to_int(mp_int z, int *out)
Definition: imath.c:1865
mp_result mp_int_init(mp_int z)
Definition: imath.c:361
mp_result mp_int_div(mp_int a, mp_int b, mp_int q, mp_int r)
Definition: imath.c:955
const mp_result MP_OK
Definition: imath.c:43
void mp_int_clear(mp_int z)
Definition: imath.c:478
static void s_fake(mp_int z, int value, mp_digit vbuf[])
Definition: imath.c:2364
int mp_result
Definition: imath.h:41
uint32 mp_digit
Definition: imath.h:44
Definition: imath.h:57
int mp_int_divisible_value ( mp_int  a,
int  v 
)

Definition at line 1781 of file imath.c.

References mp_int_div_value(), and MP_OK.

1782 {
1783  int rem = 0;
1784 
1785  if (mp_int_div_value(a, v, NULL, &rem) != MP_OK)
1786  return 0;
1787 
1788  return rem == 0;
1789 }
mp_result mp_int_div_value(mp_int a, int value, mp_int q, int *r)
Definition: imath.c:1119
const mp_result MP_OK
Definition: imath.c:43
mp_result mp_int_egcd ( mp_int  a,
mp_int  b,
mp_int  c,
mp_int  x,
mp_int  y 
)

Definition at line 1631 of file imath.c.

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

Referenced by mp_int_invmod().

1633 {
1634  int k,
1635  last = 0,
1636  ca,
1637  cb;
1638  mpz_t temp[8];
1639  mp_result res;
1640 
1641  CHECK(a != NULL && b != NULL && c != NULL &&
1642  (x != NULL || y != NULL));
1643 
1644  ca = CMPZ(a);
1645  cb = CMPZ(b);
1646  if (ca == 0 && cb == 0)
1647  return MP_UNDEF;
1648  else if (ca == 0)
1649  {
1650  if ((res = mp_int_abs(b, c)) != MP_OK)
1651  return res;
1652  mp_int_zero(x);
1653  (void) mp_int_set_value(y, 1);
1654  return MP_OK;
1655  }
1656  else if (cb == 0)
1657  {
1658  if ((res = mp_int_abs(a, c)) != MP_OK)
1659  return res;
1660  (void) mp_int_set_value(x, 1);
1661  mp_int_zero(y);
1662  return MP_OK;
1663  }
1664 
1665  /*
1666  * Initialize temporaries: A:0, B:1, C:2, D:3, u:4, v:5, ou:6, ov:7
1667  */
1668  for (last = 0; last < 4; ++last)
1669  {
1670  if ((res = mp_int_init(TEMP(last))) != MP_OK)
1671  goto CLEANUP;
1672  }
1673  TEMP(0)->digits[0] = 1;
1674  TEMP(3)->digits[0] = 1;
1675 
1676  SETUP(mp_int_init_copy(TEMP(4), a), last);
1677  SETUP(mp_int_init_copy(TEMP(5), b), last);
1678 
1679  /* We will work with absolute values here */
1680  MP_SIGN(TEMP(4)) = MP_ZPOS;
1681  MP_SIGN(TEMP(5)) = MP_ZPOS;
1682 
1683  { /* Divide out common factors of 2 from u and v */
1684  int div2_u = s_dp2k(TEMP(4)),
1685  div2_v = s_dp2k(TEMP(5));
1686 
1687  k = MIN(div2_u, div2_v);
1688  s_qdiv(TEMP(4), k);
1689  s_qdiv(TEMP(5), k);
1690  }
1691 
1692  SETUP(mp_int_init_copy(TEMP(6), TEMP(4)), last);
1693  SETUP(mp_int_init_copy(TEMP(7), TEMP(5)), last);
1694 
1695  for (;;)
1696  {
1697  while (mp_int_is_even(TEMP(4)))
1698  {
1699  s_qdiv(TEMP(4), 1);
1700 
1701  if (mp_int_is_odd(TEMP(0)) || mp_int_is_odd(TEMP(1)))
1702  {
1703  if ((res = mp_int_add(TEMP(0), TEMP(7), TEMP(0))) != MP_OK)
1704  goto CLEANUP;
1705  if ((res = mp_int_sub(TEMP(1), TEMP(6), TEMP(1))) != MP_OK)
1706  goto CLEANUP;
1707  }
1708 
1709  s_qdiv(TEMP(0), 1);
1710  s_qdiv(TEMP(1), 1);
1711  }
1712 
1713  while (mp_int_is_even(TEMP(5)))
1714  {
1715  s_qdiv(TEMP(5), 1);
1716 
1717  if (mp_int_is_odd(TEMP(2)) || mp_int_is_odd(TEMP(3)))
1718  {
1719  if ((res = mp_int_add(TEMP(2), TEMP(7), TEMP(2))) != MP_OK)
1720  goto CLEANUP;
1721  if ((res = mp_int_sub(TEMP(3), TEMP(6), TEMP(3))) != MP_OK)
1722  goto CLEANUP;
1723  }
1724 
1725  s_qdiv(TEMP(2), 1);
1726  s_qdiv(TEMP(3), 1);
1727  }
1728 
1729  if (mp_int_compare(TEMP(4), TEMP(5)) >= 0)
1730  {
1731  if ((res = mp_int_sub(TEMP(4), TEMP(5), TEMP(4))) != MP_OK)
1732  goto CLEANUP;
1733  if ((res = mp_int_sub(TEMP(0), TEMP(2), TEMP(0))) != MP_OK)
1734  goto CLEANUP;
1735  if ((res = mp_int_sub(TEMP(1), TEMP(3), TEMP(1))) != MP_OK)
1736  goto CLEANUP;
1737  }
1738  else
1739  {
1740  if ((res = mp_int_sub(TEMP(5), TEMP(4), TEMP(5))) != MP_OK)
1741  goto CLEANUP;
1742  if ((res = mp_int_sub(TEMP(2), TEMP(0), TEMP(2))) != MP_OK)
1743  goto CLEANUP;
1744  if ((res = mp_int_sub(TEMP(3), TEMP(1), TEMP(3))) != MP_OK)
1745  goto CLEANUP;
1746  }
1747 
1748  if (CMPZ(TEMP(4)) == 0)
1749  {
1750  if (x && (res = mp_int_copy(TEMP(2), x)) != MP_OK)
1751  goto CLEANUP;
1752  if (y && (res = mp_int_copy(TEMP(3), y)) != MP_OK)
1753  goto CLEANUP;
1754  if (c)
1755  {
1756  if (!s_qmul(TEMP(5), k))
1757  {
1758  res = MP_MEMORY;
1759  goto CLEANUP;
1760  }
1761 
1762  res = mp_int_copy(TEMP(5), c);
1763  }
1764 
1765  break;
1766  }
1767  }
1768 
1769 CLEANUP:
1770  while (--last >= 0)
1771  mp_int_clear(TEMP(last));
1772 
1773  return res;
1774 }
static int s_dp2k(mp_int z)
Definition: imath.c:3113
static int s_qmul(mp_int z, mp_size p2)
Definition: imath.c:2996
mp_result mp_int_copy(mp_int a, mp_int c)
Definition: imath.c:510
#define mp_int_is_even(Z)
Definition: imath.h:91
#define CMPZ(Z)
Definition: imath.c:146
const mp_sign MP_ZPOS
Definition: imath.c:53
mp_result mp_int_sub(mp_int a, mp_int b, mp_int c)
Definition: imath.c:699
mp_result mp_int_init_copy(mp_int z, mp_int old)
Definition: imath.c:412
#define SETUP(E, C)
Definition: imath.c:143
mp_result mp_int_init(mp_int z)
Definition: imath.c:361
mp_result mp_int_add(mp_int a, mp_int b, mp_int c)
Definition: imath.c:607
#define mp_int_is_odd(Z)
Definition: imath.h:90
void mp_int_zero(mp_int z)
Definition: imath.c:555
#define TEMP(K)
Definition: imath.c:142
mp_result mp_int_set_value(mp_int z, int value)
Definition: imath.c:455
const mp_result MP_OK
Definition: imath.c:43
const mp_result MP_UNDEF
Definition: imath.c:48
static void s_qdiv(mp_int z, mp_size p2)
Definition: imath.c:2919
#define MP_SIGN(Z)
Definition: imath.h:70
mp_result mp_int_abs(mp_int a, mp_int c)
Definition: imath.c:569
void mp_int_clear(mp_int z)
Definition: imath.c:478
int mp_result
Definition: imath.h:41
#define CHECK(TEST)
Definition: imath.c:74
const mp_result MP_MEMORY
Definition: imath.c:46
#define MIN(A, B)
Definition: imath.c:138
Definition: imath.h:57
int mp_int_compare(mp_int a, mp_int b)
Definition: imath.c:1242
mp_result mp_int_expt ( mp_int  a,
int  b,
mp_int  c 
)

Definition at line 1166 of file imath.c.

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

1167 {
1168  mpz_t t;
1169  mp_result res;
1170  unsigned int v = abs(b);
1171 
1172  CHECK(b >= 0 && c != NULL);
1173 
1174  if ((res = mp_int_init_copy(&t, a)) != MP_OK)
1175  return res;
1176 
1177  (void) mp_int_set_value(c, 1);
1178  while (v != 0)
1179  {
1180  if (v & 1)
1181  {
1182  if ((res = mp_int_mul(c, &t, c)) != MP_OK)
1183  goto CLEANUP;
1184  }
1185 
1186  v >>= 1;
1187  if (v == 0)
1188  break;
1189 
1190  if ((res = mp_int_sqr(&t, &t)) != MP_OK)
1191  goto CLEANUP;
1192  }
1193 
1194 CLEANUP:
1195  mp_int_clear(&t);
1196  return res;
1197 }
mp_result mp_int_mul(mp_int a, mp_int b, mp_int c)
Definition: imath.c:794
mp_result mp_int_init_copy(mp_int z, mp_int old)
Definition: imath.c:412
mp_result mp_int_set_value(mp_int z, int value)
Definition: imath.c:455
const mp_result MP_OK
Definition: imath.c:43
mp_result mp_int_sqr(mp_int a, mp_int c)
Definition: imath.c:902
void mp_int_clear(mp_int z)
Definition: imath.c:478
int mp_result
Definition: imath.h:41
#define CHECK(TEST)
Definition: imath.c:74
Definition: imath.h:57
mp_result mp_int_expt_value ( int  a,
int  b,
mp_int  c 
)

Definition at line 1204 of file imath.c.

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

1205 {
1206  mpz_t t;
1207  mp_result res;
1208  unsigned int v = abs(b);
1209 
1210  CHECK(b >= 0 && c != NULL);
1211 
1212  if ((res = mp_int_init_value(&t, a)) != MP_OK)
1213  return res;
1214 
1215  (void) mp_int_set_value(c, 1);
1216  while (v != 0)
1217  {
1218  if (v & 1)
1219  {
1220  if ((res = mp_int_mul(c, &t, c)) != MP_OK)
1221  goto CLEANUP;
1222  }
1223 
1224  v >>= 1;
1225  if (v == 0)
1226  break;
1227 
1228  if ((res = mp_int_sqr(&t, &t)) != MP_OK)
1229  goto CLEANUP;
1230  }
1231 
1232 CLEANUP:
1233  mp_int_clear(&t);
1234  return res;
1235 }
mp_result mp_int_mul(mp_int a, mp_int b, mp_int c)
Definition: imath.c:794
mp_result mp_int_init_value(mp_int z, int value)
Definition: imath.c:438
mp_result mp_int_set_value(mp_int z, int value)
Definition: imath.c:455
const mp_result MP_OK
Definition: imath.c:43
mp_result mp_int_sqr(mp_int a, mp_int c)
Definition: imath.c:902
void mp_int_clear(mp_int z)
Definition: imath.c:478
int mp_result
Definition: imath.h:41
#define CHECK(TEST)
Definition: imath.c:74
Definition: imath.h:57
mp_result mp_int_exptmod ( mp_int  a,
mp_int  b,
mp_int  m,
mp_int  c 
)

Definition at line 1336 of file imath.c.

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

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

1337 {
1338  mp_result res;
1339  mp_size um;
1340  mpz_t temp[3];
1341  mp_int s;
1342  int last = 0;
1343 
1344  CHECK(a != NULL && b != NULL && c != NULL && m != NULL);
1345 
1346  /* Zero moduli and negative exponents are not considered. */
1347  if (CMPZ(m) == 0)
1348  return MP_UNDEF;
1349  if (CMPZ(b) < 0)
1350  return MP_RANGE;
1351 
1352  um = MP_USED(m);
1353  SETUP(mp_int_init_size(TEMP(0), 2 * um), last);
1354  SETUP(mp_int_init_size(TEMP(1), 2 * um), last);
1355 
1356  if (c == b || c == m)
1357  {
1358  SETUP(mp_int_init_size(TEMP(2), 2 * um), last);
1359  s = TEMP(2);
1360  }
1361  else
1362  {
1363  s = c;
1364  }
1365 
1366  if ((res = mp_int_mod(a, m, TEMP(0))) != MP_OK)
1367  goto CLEANUP;
1368 
1369  if ((res = s_brmu(TEMP(1), m)) != MP_OK)
1370  goto CLEANUP;
1371 
1372  if ((res = s_embar(TEMP(0), b, m, TEMP(1), s)) != MP_OK)
1373  goto CLEANUP;
1374 
1375  res = mp_int_copy(s, c);
1376 
1377 CLEANUP:
1378  while (--last >= 0)
1379  mp_int_clear(TEMP(last));
1380 
1381  return res;
1382 }
mp_result mp_int_copy(mp_int a, mp_int c)
Definition: imath.c:510
mp_result mp_int_mod(mp_int a, mp_int m, mp_int c)
Definition: imath.c:1080
const mp_result MP_RANGE
Definition: imath.c:47
#define CMPZ(Z)
Definition: imath.c:146
static mp_result s_embar(mp_int a, mp_int b, mp_int m, mp_int mu, mp_int c)
Definition: imath.c:3298
#define SETUP(E, C)
Definition: imath.c:143
char * c
mp_result mp_int_init_size(mp_int z, mp_size prec)
Definition: imath.c:389
#define TEMP(K)
Definition: imath.c:142
const mp_result MP_OK
Definition: imath.c:43
const mp_result MP_UNDEF
Definition: imath.c:48
#define MP_USED(Z)
Definition: imath.h:69
static mp_result s_brmu(mp_int z, mp_int m)
Definition: imath.c:3226
void mp_int_clear(mp_int z)
Definition: imath.c:478
int mp_result
Definition: imath.h:41
unsigned int mp_size
Definition: imath.h:40
#define CHECK(TEST)
Definition: imath.c:74
Definition: imath.h:57
mp_result mp_int_exptmod_bvalue ( int  value,
mp_int  b,
mp_int  m,
mp_int  c 
)

Definition at line 1404 of file imath.c.

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

1406 {
1407  mpz_t vtmp;
1409 
1410  s_fake(&vtmp, value, vbuf);
1411 
1412  return mp_int_exptmod(&vtmp, b, m, c);
1413 }
#define MP_VALUE_DIGITS(V)
Definition: imath.c:109
static struct @121 value
mp_result mp_int_exptmod(mp_int a, mp_int b, mp_int m, mp_int c)
Definition: imath.c:1336
static void s_fake(mp_int z, int value, mp_digit vbuf[])
Definition: imath.c:2364
uint32 mp_digit
Definition: imath.h:44
Definition: imath.h:57
mp_result mp_int_exptmod_evalue ( mp_int  a,
int  value,
mp_int  m,
mp_int  c 
)

Definition at line 1389 of file imath.c.

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

1390 {
1391  mpz_t vtmp;
1393 
1394  s_fake(&vtmp, value, vbuf);
1395 
1396  return mp_int_exptmod(a, &vtmp, m, c);
1397 }
#define MP_VALUE_DIGITS(V)
Definition: imath.c:109
static struct @121 value
mp_result mp_int_exptmod(mp_int a, mp_int b, mp_int m, mp_int c)
Definition: imath.c:1336
static void s_fake(mp_int z, int value, mp_digit vbuf[])
Definition: imath.c:2364
uint32 mp_digit
Definition: imath.h:44
Definition: imath.h:57
mp_result mp_int_exptmod_known ( mp_int  a,
mp_int  b,
mp_int  m,
mp_int  mu,
mp_int  c 
)

Definition at line 1420 of file imath.c.

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

1421 {
1422  mp_result res;
1423  mp_size um;
1424  mpz_t temp[2];
1425  mp_int s;
1426  int last = 0;
1427 
1428  CHECK(a && b && m && c);
1429 
1430  /* Zero moduli and negative exponents are not considered. */
1431  if (CMPZ(m) == 0)
1432  return MP_UNDEF;
1433  if (CMPZ(b) < 0)
1434  return MP_RANGE;
1435 
1436  um = MP_USED(m);
1437  SETUP(mp_int_init_size(TEMP(0), 2 * um), last);
1438 
1439  if (c == b || c == m)
1440  {
1441  SETUP(mp_int_init_size(TEMP(1), 2 * um), last);
1442  s = TEMP(1);
1443  }
1444  else
1445  {
1446  s = c;
1447  }
1448 
1449  if ((res = mp_int_mod(a, m, TEMP(0))) != MP_OK)
1450  goto CLEANUP;
1451 
1452  if ((res = s_embar(TEMP(0), b, m, mu, s)) != MP_OK)
1453  goto CLEANUP;
1454 
1455  res = mp_int_copy(s, c);
1456 
1457 CLEANUP:
1458  while (--last >= 0)
1459  mp_int_clear(TEMP(last));
1460 
1461  return res;
1462 }
mp_result mp_int_copy(mp_int a, mp_int c)
Definition: imath.c:510
mp_result mp_int_mod(mp_int a, mp_int m, mp_int c)
Definition: imath.c:1080
const mp_result MP_RANGE
Definition: imath.c:47
#define CMPZ(Z)
Definition: imath.c:146
static mp_result s_embar(mp_int a, mp_int b, mp_int m, mp_int mu, mp_int c)
Definition: imath.c:3298
#define SETUP(E, C)
Definition: imath.c:143
char * c
mp_result mp_int_init_size(mp_int z, mp_size prec)
Definition: imath.c:389
#define TEMP(K)
Definition: imath.c:142
const mp_result MP_OK
Definition: imath.c:43
const mp_result MP_UNDEF
Definition: imath.c:48
#define MP_USED(Z)
Definition: imath.h:69
void mp_int_clear(mp_int z)
Definition: imath.c:478
int mp_result
Definition: imath.h:41
unsigned int mp_size
Definition: imath.h:40
#define CHECK(TEST)
Definition: imath.c:74
Definition: imath.h:57
void mp_int_free ( mp_int  z)

Definition at line 495 of file imath.c.

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

Referenced by mp_clear_free().

496 {
497  NRCHECK(z != NULL);
498 
499  if (z->digits != NULL)
500  mp_int_clear(z);
501 
502  px_free(z);
503 }
mp_digit * digits
Definition: imath.h:59
#define px_free(p)
Definition: px.h:46
#define NRCHECK(TEST)
Definition: imath.c:75
void mp_int_clear(mp_int z)
Definition: imath.c:478
mp_result mp_int_gcd ( mp_int  a,
mp_int  b,
mp_int  c 
)

Definition at line 1536 of file imath.c.

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

1537 {
1538  int ca,
1539  cb,
1540  k = 0;
1541  mpz_t u,
1542  v,
1543  t;
1544  mp_result res;
1545 
1546  CHECK(a != NULL && b != NULL && c != NULL);
1547 
1548  ca = CMPZ(a);
1549  cb = CMPZ(b);
1550  if (ca == 0 && cb == 0)
1551  return MP_UNDEF;
1552  else if (ca == 0)
1553  return mp_int_abs(b, c);
1554  else if (cb == 0)
1555  return mp_int_abs(a, c);
1556 
1557  if ((res = mp_int_init(&t)) != MP_OK)
1558  return res;
1559  if ((res = mp_int_init_copy(&u, a)) != MP_OK)
1560  goto U;
1561  if ((res = mp_int_init_copy(&v, b)) != MP_OK)
1562  goto V;
1563 
1564  MP_SIGN(&u) = MP_ZPOS;
1565  MP_SIGN(&v) = MP_ZPOS;
1566 
1567  { /* Divide out common factors of 2 from u and v */
1568  int div2_u = s_dp2k(&u),
1569  div2_v = s_dp2k(&v);
1570 
1571  k = MIN(div2_u, div2_v);
1572  s_qdiv(&u, (mp_size) k);
1573  s_qdiv(&v, (mp_size) k);
1574  }
1575 
1576  if (mp_int_is_odd(&u))
1577  {
1578  if ((res = mp_int_neg(&v, &t)) != MP_OK)
1579  goto CLEANUP;
1580  }
1581  else
1582  {
1583  if ((res = mp_int_copy(&u, &t)) != MP_OK)
1584  goto CLEANUP;
1585  }
1586 
1587  for (;;)
1588  {
1589  s_qdiv(&t, s_dp2k(&t));
1590 
1591  if (CMPZ(&t) > 0)
1592  {
1593  if ((res = mp_int_copy(&t, &u)) != MP_OK)
1594  goto CLEANUP;
1595  }
1596  else
1597  {
1598  if ((res = mp_int_neg(&t, &v)) != MP_OK)
1599  goto CLEANUP;
1600  }
1601 
1602  if ((res = mp_int_sub(&u, &v, &t)) != MP_OK)
1603  goto CLEANUP;
1604 
1605  if (CMPZ(&t) == 0)
1606  break;
1607  }
1608 
1609  if ((res = mp_int_abs(&u, c)) != MP_OK)
1610  goto CLEANUP;
1611  if (!s_qmul(c, (mp_size) k))
1612  res = MP_MEMORY;
1613 
1614 CLEANUP:
1615  mp_int_clear(&v);
1616 V: mp_int_clear(&u);
1617 U: mp_int_clear(&t);
1618 
1619  return res;
1620 }
static int s_dp2k(mp_int z)
Definition: imath.c:3113
static int s_qmul(mp_int z, mp_size p2)
Definition: imath.c:2996
mp_result mp_int_copy(mp_int a, mp_int c)
Definition: imath.c:510
#define CMPZ(Z)
Definition: imath.c:146
const mp_sign MP_ZPOS
Definition: imath.c:53
mp_result mp_int_sub(mp_int a, mp_int b, mp_int c)
Definition: imath.c:699
mp_result mp_int_init_copy(mp_int z, mp_int old)
Definition: imath.c:412
mp_result mp_int_init(mp_int z)
Definition: imath.c:361
#define mp_int_is_odd(Z)
Definition: imath.h:90
const mp_result MP_OK
Definition: imath.c:43
const mp_result MP_UNDEF
Definition: imath.c:48
static void s_qdiv(mp_int z, mp_size p2)
Definition: imath.c:2919
#define MP_SIGN(Z)
Definition: imath.h:70
mp_result mp_int_neg(mp_int a, mp_int c)
Definition: imath.c:587
mp_result mp_int_abs(mp_int a, mp_int c)
Definition: imath.c:569
void mp_int_clear(mp_int z)
Definition: imath.c:478
int mp_result
Definition: imath.h:41
unsigned int mp_size
Definition: imath.h:40
#define CHECK(TEST)
Definition: imath.c:74
const mp_result MP_MEMORY
Definition: imath.c:46
#define MIN(A, B)
Definition: imath.c:138
Definition: imath.h:57
mp_result mp_int_init ( mp_int  z)

Definition at line 361 of file imath.c.

References default_precision, and mp_int_init_size().

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

362 {
364 }
static mp_size default_precision
Definition: imath.c:167
mp_result mp_int_init_size(mp_int z, mp_size prec)
Definition: imath.c:389
mp_result mp_int_init_copy ( mp_int  z,
mp_int  old 
)

Definition at line 412 of file imath.c.

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

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

413 {
414  mp_result res;
415  mp_size uold,
416  target;
417 
418  CHECK(z != NULL && old != NULL);
419 
420  uold = MP_USED(old);
421  target = MAX(uold, default_precision);
422 
423  if ((res = mp_int_init_size(z, target)) != MP_OK)
424  return res;
425 
426  MP_USED(z) = uold;
427  MP_SIGN(z) = MP_SIGN(old);
428  COPY(MP_DIGITS(old), MP_DIGITS(z), uold);
429 
430  return MP_OK;
431 }
static mp_size default_precision
Definition: imath.c:167
#define MAX(A, B)
Definition: imath.c:139
mp_result mp_int_init_size(mp_int z, mp_size prec)
Definition: imath.c:389
#define MP_DIGITS(Z)
Definition: imath.h:67
const mp_result MP_OK
Definition: imath.c:43
#define MP_USED(Z)
Definition: imath.h:69
#define MP_SIGN(Z)
Definition: imath.h:70
int mp_result
Definition: imath.h:41
unsigned int mp_size
Definition: imath.h:40
#define CHECK(TEST)
Definition: imath.c:74
#define COPY(P, Q, S)
Definition: imath.c:120
mp_result mp_int_init_size ( mp_int  z,
mp_size  prec 
)

Definition at line 389 of file imath.c.

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

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

390 {
391  CHECK(z != NULL);
392 
393  prec = (mp_size) ROUND_PREC(prec);
394  prec = MAX(prec, default_precision);
395 
396  if ((MP_DIGITS(z) = s_alloc(prec)) == NULL)
397  return MP_MEMORY;
398 
399  z->digits[0] = 0;
400  MP_USED(z) = 1;
401  MP_ALLOC(z) = prec;
402  MP_SIGN(z) = MP_ZPOS;
403 
404  return MP_OK;
405 }
static mp_size default_precision
Definition: imath.c:167
#define MP_ALLOC(Z)
Definition: imath.h:68
#define MAX(A, B)
Definition: imath.c:139
mp_digit * digits
Definition: imath.h:59
const mp_sign MP_ZPOS
Definition: imath.c:53
#define ROUND_PREC(P)
Definition: imath.c:113
static mp_digit * s_alloc(mp_size num)
Definition: imath.c:2284
#define MP_DIGITS(Z)
Definition: imath.h:67
const mp_result MP_OK
Definition: imath.c:43
#define MP_USED(Z)
Definition: imath.h:69
#define MP_SIGN(Z)
Definition: imath.h:70
unsigned int mp_size
Definition: imath.h:40
#define CHECK(TEST)
Definition: imath.c:74
const mp_result MP_MEMORY
Definition: imath.c:46
mp_result mp_int_init_value ( mp_int  z,
int  value 
)

Definition at line 438 of file imath.c.

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

Referenced by mp_int_expt_value().

439 {
440  mp_result res;
441 
442  CHECK(z != NULL);
443 
444  if ((res = mp_int_init(z)) != MP_OK)
445  return res;
446 
447  return mp_int_set_value(z, value);
448 }
static struct @121 value
mp_result mp_int_init(mp_int z)
Definition: imath.c:361
mp_result mp_int_set_value(mp_int z, int value)
Definition: imath.c:455
const mp_result MP_OK
Definition: imath.c:43
int mp_result
Definition: imath.h:41
#define CHECK(TEST)
Definition: imath.c:74
mp_result mp_int_invmod ( mp_int  a,
mp_int  m,
mp_int  c 
)

Definition at line 1481 of file imath.c.

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

Referenced by pgp_elgamal_decrypt().

1482 {
1483  mp_result res;
1484  mp_sign sa;
1485  int last = 0;
1486  mpz_t temp[2];
1487 
1488  CHECK(a != NULL && m != NULL && c != NULL);
1489 
1490  if (CMPZ(a) == 0 || CMPZ(m) <= 0)
1491  return MP_RANGE;
1492 
1493  sa = MP_SIGN(a); /* need this for the result later */
1494 
1495  for (last = 0; last < 2; ++last)
1496  if ((res = mp_int_init(TEMP(last))) != MP_OK)
1497  goto CLEANUP;
1498 
1499  if ((res = mp_int_egcd(a, m, TEMP(0), TEMP(1), NULL)) != MP_OK)
1500  goto CLEANUP;
1501 
1502  if (mp_int_compare_value(TEMP(0), 1) != 0)
1503  {
1504  res = MP_UNDEF;
1505  goto CLEANUP;
1506  }
1507 
1508  /* It is first necessary to constrain the value to the proper range */
1509  if ((res = mp_int_mod(TEMP(1), m, TEMP(1))) != MP_OK)
1510  goto CLEANUP;
1511 
1512  /*
1513  * Now, if 'a' was originally negative, the value we have is actually the
1514  * magnitude of the negative representative; to get the positive value we
1515  * have to subtract from the modulus. Otherwise, the value is okay as it
1516  * stands.
1517  */
1518  if (sa == MP_NEG)
1519  res = mp_int_sub(m, TEMP(1), c);
1520  else
1521  res = mp_int_copy(TEMP(1), c);
1522 
1523 CLEANUP:
1524  while (--last >= 0)
1525  mp_int_clear(TEMP(last));
1526 
1527  return res;
1528 }
const mp_sign MP_NEG
Definition: imath.c:52
mp_result mp_int_copy(mp_int a, mp_int c)
Definition: imath.c:510
mp_result mp_int_mod(mp_int a, mp_int m, mp_int c)
Definition: imath.c:1080
const mp_result MP_RANGE
Definition: imath.c:47
#define CMPZ(Z)
Definition: imath.c:146
mp_result mp_int_sub(mp_int a, mp_int b, mp_int c)
Definition: imath.c:699
mp_result mp_int_init(mp_int z)
Definition: imath.c:361
#define TEMP(K)
Definition: imath.c:142
const mp_result MP_OK
Definition: imath.c:43
const mp_result MP_UNDEF
Definition: imath.c:48
#define MP_SIGN(Z)
Definition: imath.h:70
unsigned char mp_sign
Definition: imath.h:39
void mp_int_clear(mp_int z)
Definition: imath.c:478
int mp_result
Definition: imath.h:41
#define CHECK(TEST)
Definition: imath.c:74
int mp_int_compare_value(mp_int z, int value)
Definition: imath.c:1306
mp_result mp_int_egcd(mp_int a, mp_int b, mp_int c, mp_int x, mp_int y)
Definition: imath.c:1631
Definition: imath.h:57
int mp_int_is_pow2 ( mp_int  z)

Definition at line 1796 of file imath.c.

References CHECK, and s_isp2().

1797 {
1798  CHECK(z != NULL);
1799 
1800  return s_isp2(z);
1801 }
static int s_isp2(mp_int z)
Definition: imath.c:3143
#define CHECK(TEST)
Definition: imath.c:74
mp_result mp_int_mod ( mp_int  a,
mp_int  m,
mp_int  c 
)

Definition at line 1080 of file imath.c.

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

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

1081 {
1082  mp_result res;
1083  mpz_t tmp;
1084  mp_int out;
1085 
1086  if (m == c)
1087  {
1088  if ((res = mp_int_init(&tmp)) != MP_OK)
1089  return res;
1090 
1091  out = &tmp;
1092  }
1093  else
1094  {
1095  out = c;
1096  }
1097 
1098  if ((res = mp_int_div(a, m, NULL, out)) != MP_OK)
1099  goto CLEANUP;
1100 
1101  if (CMPZ(out) < 0)
1102  res = mp_int_add(out, m, c);
1103  else
1104  res = mp_int_copy(out, c);
1105 
1106 CLEANUP:
1107  if (out != c)
1108  mp_int_clear(&tmp);
1109 
1110  return res;
1111 }
mp_result mp_int_copy(mp_int a, mp_int c)
Definition: imath.c:510
#define CMPZ(Z)
Definition: imath.c:146
mp_result mp_int_init(mp_int z)
Definition: imath.c:361
char * c
mp_result mp_int_add(mp_int a, mp_int b, mp_int c)
Definition: imath.c:607
mp_result mp_int_div(mp_int a, mp_int b, mp_int q, mp_int r)
Definition: imath.c:955
const mp_result MP_OK
Definition: imath.c:43
void mp_int_clear(mp_int z)
Definition: imath.c:478
int mp_result
Definition: imath.h:41
Definition: imath.h:57
mp_result mp_int_mul ( mp_int  a,
mp_int  b,
mp_int  c 
)

Definition at line 794 of file imath.c.

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

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

795 {
796  mp_digit *out;
797  mp_size osize,
798  ua,
799  ub,
800  p = 0;
801  mp_sign osign;
802 
803  CHECK(a != NULL && b != NULL && c != NULL);
804 
805  /* If either input is zero, we can shortcut multiplication */
806  if (mp_int_compare_zero(a) == 0 || mp_int_compare_zero(b) == 0)
807  {
808  mp_int_zero(c);
809  return MP_OK;
810  }
811 
812  /* Output is positive if inputs have same sign, otherwise negative */
813  osign = (MP_SIGN(a) == MP_SIGN(b)) ? MP_ZPOS : MP_NEG;
814 
815  /*
816  * If the output is not equal to any of the inputs, we'll write the
817  * results there directly; otherwise, allocate a temporary space.
818  */
819  ua = MP_USED(a);
820  ub = MP_USED(b);
821  osize = MAX(ua, ub);
822  osize = 4 * ((osize + 1) / 2);
823 
824  if (c == a || c == b)
825  {
826  p = ROUND_PREC(osize);
827  p = MAX(p, default_precision);
828 
829  if ((out = s_alloc(p)) == NULL)
830  return MP_MEMORY;
831  }
832  else
833  {
834  if (!s_pad(c, osize))
835  return MP_MEMORY;
836 
837  out = MP_DIGITS(c);
838  }
839  ZERO(out, osize);
840 
841  if (!s_kmul(MP_DIGITS(a), MP_DIGITS(b), out, ua, ub))
842  return MP_MEMORY;
843 
844  /*
845  * If we allocated a new buffer, get rid of whatever memory c was already
846  * using, and fix up its fields to reflect that.
847  */
848  if (out != MP_DIGITS(c))
849  {
850  s_free(MP_DIGITS(c));
851  MP_DIGITS(c) = out;
852  MP_ALLOC(c) = p;
853  }
854 
855  MP_USED(c) = osize; /* might not be true, but we'll fix it ... */
856  CLAMP(c); /* ... right here */
857  MP_SIGN(c) = osign;
858 
859  return MP_OK;
860 }
static int s_pad(mp_int z, mp_size min)
Definition: imath.c:2324
static mp_size default_precision
Definition: imath.c:167
#define MP_ALLOC(Z)
Definition: imath.h:68
#define MAX(A, B)
Definition: imath.c:139
const mp_sign MP_NEG
Definition: imath.c:52
#define s_free(P)
Definition: imath.c:182
#define ZERO(P, S)
Definition: imath.c:116
const mp_sign MP_ZPOS
Definition: imath.c:53
#define ROUND_PREC(P)
Definition: imath.c:113
int mp_int_compare_zero(mp_int z)
Definition: imath.c:1289
static mp_digit * s_alloc(mp_size num)
Definition: imath.c:2284
void mp_int_zero(mp_int z)
Definition: imath.c:555
#define MP_DIGITS(Z)
Definition: imath.h:67
const mp_result MP_OK
Definition: imath.c:43
#define MP_USED(Z)
Definition: imath.h:69
#define MP_SIGN(Z)
Definition: imath.h:70
unsigned char mp_sign
Definition: imath.h:39
unsigned int mp_size
Definition: imath.h:40
#define CHECK(TEST)
Definition: imath.c:74
#define CLAMP(Z)
Definition: imath.c:131
const mp_result MP_MEMORY
Definition: imath.c:46
uint32 mp_digit
Definition: imath.h:44
static int s_kmul(mp_digit *da, mp_digit *db, mp_digit *dc, mp_size size_a, mp_size size_b)
Definition: imath.c:2541
mp_result mp_int_mul_pow2 ( mp_int  a,
int  p2,
mp_int  c 
)

Definition at line 882 of file imath.c.

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

883 {
884  mp_result res;
885 
886  CHECK(a != NULL && c != NULL && p2 >= 0);
887 
888  if ((res = mp_int_copy(a, c)) != MP_OK)
889  return res;
890 
891  if (s_qmul(c, (mp_size) p2))
892  return MP_OK;
893  else
894  return MP_MEMORY;
895 }
static int s_qmul(mp_int z, mp_size p2)
Definition: imath.c:2996
mp_result mp_int_copy(mp_int a, mp_int c)
Definition: imath.c:510
const mp_result MP_OK
Definition: imath.c:43
int mp_result
Definition: imath.h:41
unsigned int mp_size
Definition: imath.h:40
#define CHECK(TEST)
Definition: imath.c:74
const mp_result MP_MEMORY
Definition: imath.c:46
mp_result mp_int_mul_value ( mp_int  a,
int  value,
mp_int  c 
)

Definition at line 867 of file imath.c.

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

868 {
869  mpz_t vtmp;
871 
872  s_fake(&vtmp, value, vbuf);
873 
874  return mp_int_mul(a, &vtmp, c);
875 }
mp_result mp_int_mul(mp_int a, mp_int b, mp_int c)
Definition: imath.c:794
#define MP_VALUE_DIGITS(V)
Definition: imath.c:109
static struct @121 value
static void s_fake(mp_int z, int value, mp_digit vbuf[])
Definition: imath.c:2364
uint32 mp_digit
Definition: imath.h:44
Definition: imath.h:57
mp_result mp_int_neg ( mp_int  a,
mp_int  c 
)

Definition at line 587 of file imath.c.

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

Referenced by mp_int_gcd().

588 {
589  mp_result res;
590 
591  CHECK(a != NULL && c != NULL);
592 
593  if ((res = mp_int_copy(a, c)) != MP_OK)
594  return res;
595 
596  if (CMPZ(c) != 0)
597  MP_SIGN(c) = 1 - MP_SIGN(a);
598 
599  return MP_OK;
600 }
mp_result mp_int_copy(mp_int a, mp_int c)
Definition: imath.c:510
#define CMPZ(Z)
Definition: imath.c:146
const mp_result MP_OK
Definition: imath.c:43
#define MP_SIGN(Z)
Definition: imath.h:70
int mp_result
Definition: imath.h:41
#define CHECK(TEST)
Definition: imath.c:74
mp_result mp_int_read_binary ( mp_int  z,
unsigned char *  buf,
int  len 
)

Definition at line 2125 of file imath.c.

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

2126 {
2127  mp_size need,
2128  i;
2129  unsigned char *tmp;
2130  mp_digit *dz;
2131 
2132  CHECK(z != NULL && buf != NULL && len > 0);
2133 
2134  /* Figure out how many digits are needed to represent this value */
2135  need = ((len * CHAR_BIT) + (MP_DIGIT_BIT - 1)) / MP_DIGIT_BIT;
2136  if (!s_pad(z, need))
2137  return MP_MEMORY;
2138 
2139  mp_int_zero(z);
2140 
2141  /*
2142  * If the high-order bit is set, take the 2's complement before reading
2143  * the value (it will be restored afterward)
2144  */
2145  if (buf[0] >> (CHAR_BIT - 1))
2146  {
2147  MP_SIGN(z) = MP_NEG;
2148  s_2comp(buf, len);
2149  }
2150 
2151  dz = MP_DIGITS(z);
2152  for (tmp = buf, i = len; i > 0; --i, ++tmp)
2153  {
2154  s_qmul(z, (mp_size) CHAR_BIT);
2155  *dz |= *tmp;
2156  }
2157 
2158  /* Restore 2's complement if we took it before */
2159  if (MP_SIGN(z) == MP_NEG)
2160  s_2comp(buf, len);
2161 
2162  return MP_OK;
2163 }
static int s_pad(mp_int z, mp_size min)
Definition: imath.c:2324
const mp_sign MP_NEG
Definition: imath.c:52
static int s_qmul(mp_int z, mp_size p2)
Definition: imath.c:2996
#define MP_DIGIT_BIT
Definition: imath.h:81
static void s_2comp(unsigned char *buf, int len)
Definition: imath.c:3579
static char * buf
Definition: pg_test_fsync.c:67
void mp_int_zero(mp_int z)
Definition: imath.c:555
#define MP_DIGITS(Z)
Definition: imath.h:67
const mp_result MP_OK
Definition: imath.c:43
#define MP_SIGN(Z)
Definition: imath.h:70
unsigned int mp_size
Definition: imath.h:40
#define CHECK(TEST)
Definition: imath.c:74
int i
const mp_result MP_MEMORY
Definition: imath.c:46
uint32 mp_digit
Definition: imath.h:44
mp_result mp_int_read_cstring ( mp_int  z,
mp_size  radix,
const char *  str,
char **  end 
)

Definition at line 2004 of file imath.c.

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

Referenced by mp_int_read_string().

2005 {
2006  int ch;
2007 
2008  CHECK(z != NULL && str != NULL);
2009 
2010  if (radix < MP_MIN_RADIX || radix > MP_MAX_RADIX)
2011  return MP_RANGE;
2012 
2013  /* Skip leading whitespace */
2014  while (isspace((unsigned char) *str))
2015  ++str;
2016 
2017  /* Handle leading sign tag (+/-, positive default) */
2018  switch (*str)
2019  {
2020  case '-':
2021  MP_SIGN(z) = MP_NEG;
2022  ++str;
2023  break;
2024  case '+':
2025  ++str; /* fallthrough */
2026  default:
2027  MP_SIGN(z) = MP_ZPOS;
2028  break;
2029  }
2030 
2031  /* Skip leading zeroes */
2032  while ((ch = s_ch2val(*str, radix)) == 0)
2033  ++str;
2034 
2035  /* Make sure there is enough space for the value */
2036  if (!s_pad(z, s_inlen(strlen(str), radix)))
2037  return MP_MEMORY;
2038 
2039  MP_USED(z) = 1;
2040  z->digits[0] = 0;
2041 
2042  while (*str != '\0' && ((ch = s_ch2val(*str, radix)) >= 0))
2043  {
2044  s_dmul(z, (mp_digit) radix);
2045  s_dadd(z, (mp_digit) ch);
2046  ++str;
2047  }
2048 
2049  CLAMP(z);
2050 
2051  /* Override sign for zero, even if negative specified. */
2052  if (CMPZ(z) == 0)
2053  MP_SIGN(z) = MP_ZPOS;
2054 
2055  if (end != NULL)
2056  *end = (char *) str;
2057 
2058  /*
2059  * Return a truncation error if the string has unprocessed characters
2060  * remaining, so the caller can tell if the whole string was done
2061  */
2062  if (*str != '\0')
2063  return MP_TRUNC;
2064  else
2065  return MP_OK;
2066 }
static int s_pad(mp_int z, mp_size min)
Definition: imath.c:2324
const mp_sign MP_NEG
Definition: imath.c:52
mp_digit * digits
Definition: imath.h:59
const mp_result MP_RANGE
Definition: imath.c:47
#define CMPZ(Z)
Definition: imath.c:146
const mp_sign MP_ZPOS
Definition: imath.c:53
static mp_size s_inlen(int len, mp_size r)
Definition: imath.c:3525
const mp_result MP_TRUNC
Definition: imath.c:49
static void s_dadd(mp_int a, mp_digit b)
Definition: imath.c:2808
const mp_result MP_OK
Definition: imath.c:43
#define MP_USED(Z)
Definition: imath.h:69
#define MP_SIGN(Z)
Definition: imath.h:70
static int s_ch2val(char c, int r)
Definition: imath.c:3538
#define CHECK(TEST)
Definition: imath.c:74
static void s_dmul(mp_int a, mp_digit b)
Definition: imath.c:2838
#define CLAMP(Z)
Definition: imath.c:131
const mp_result MP_MEMORY
Definition: imath.c:46
uint32 mp_digit
Definition: imath.h:44
#define MP_MAX_RADIX
Definition: imath.h:85
mp_result mp_int_read_string ( mp_int  z,
mp_size  radix,
const char *  str 
)

Definition at line 1993 of file imath.c.

References mp_int_read_cstring().

1994 {
1995  return mp_int_read_cstring(z, radix, str, NULL);
1996 
1997 }
mp_result mp_int_read_cstring(mp_int z, mp_size radix, const char *str, char **end)
Definition: imath.c:2004
mp_result mp_int_read_unsigned ( mp_int  z,
unsigned char *  buf,
int  len 
)

Definition at line 2210 of file imath.c.

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

Referenced by mp_px_rand(), and mpi_to_bn().

2211 {
2212  mp_size need,
2213  i;
2214  unsigned char *tmp;
2215  mp_digit *dz;
2216 
2217  CHECK(z != NULL && buf != NULL && len > 0);
2218 
2219  /* Figure out how many digits are needed to represent this value */
2220  need = ((len * CHAR_BIT) + (MP_DIGIT_BIT - 1)) / MP_DIGIT_BIT;
2221  if (!s_pad(z, need))
2222  return MP_MEMORY;
2223 
2224  mp_int_zero(z);
2225 
2226  dz = MP_DIGITS(z);
2227  for (tmp = buf, i = len; i > 0; --i, ++tmp)
2228  {
2229  (void) s_qmul(z, CHAR_BIT);
2230  *dz |= *tmp;
2231  }
2232 
2233  return MP_OK;
2234 }
static int s_pad(mp_int z, mp_size min)
Definition: imath.c:2324
static int s_qmul(mp_int z, mp_size p2)
Definition: imath.c:2996
#define MP_DIGIT_BIT
Definition: imath.h:81
static char * buf
Definition: pg_test_fsync.c:67
void mp_int_zero(mp_int z)
Definition: imath.c:555
#define MP_DIGITS(Z)
Definition: imath.h:67
const mp_result MP_OK
Definition: imath.c:43
unsigned int mp_size
Definition: imath.h:40
#define CHECK(TEST)
Definition: imath.c:74
int i
const mp_result MP_MEMORY
Definition: imath.c:46
uint32 mp_digit
Definition: imath.h:44
mp_result mp_int_redux_const ( mp_int  m,
mp_int  c 
)

Definition at line 1469 of file imath.c.

References CHECK, and s_brmu().

1470 {
1471  CHECK(m != NULL && c != NULL && m != c);
1472 
1473  return s_brmu(c, m);
1474 }
static mp_result s_brmu(mp_int z, mp_int m)
Definition: imath.c:3226
#define CHECK(TEST)
Definition: imath.c:74
mp_result mp_int_set_value ( mp_int  z,
int  value 
)

Definition at line 455 of file imath.c.

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

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

456 {
457  mp_size ndig;
458 
459  CHECK(z != NULL);
460 
461  /* How many digits to copy */
462  ndig = (mp_size) MP_VALUE_DIGITS(value);
463 
464  if (!s_pad(z, ndig))
465  return MP_MEMORY;
466 
467  MP_USED(z) = (mp_size) s_vpack(value, MP_DIGITS(z));
468  MP_SIGN(z) = (value < 0) ? MP_NEG : MP_ZPOS;
469 
470  return MP_OK;
471 }
static int s_pad(mp_int z, mp_size min)
Definition: imath.c:2324
const mp_sign MP_NEG
Definition: imath.c:52
#define MP_VALUE_DIGITS(V)
Definition: imath.c:109
const mp_sign MP_ZPOS
Definition: imath.c:53
static struct @121 value
#define MP_DIGITS(Z)
Definition: imath.h:67
const mp_result MP_OK
Definition: imath.c:43
#define MP_USED(Z)
Definition: imath.h:69
#define MP_SIGN(Z)
Definition: imath.h:70
static int s_vpack(int v, mp_digit t[])
Definition: imath.c:2400
unsigned int mp_size
Definition: imath.h:40
#define CHECK(TEST)
Definition: imath.c:74
const mp_result MP_MEMORY
Definition: imath.c:46
mp_result mp_int_sqr ( mp_int  a,
mp_int  c 
)

Definition at line 902 of file imath.c.

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

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

903 {
904  mp_digit *out;
905  mp_size osize,
906  p = 0;
907 
908  CHECK(a != NULL && c != NULL);
909 
910  /* Get a temporary buffer big enough to hold the result */
911  osize = (mp_size) 4 * ((MP_USED(a) + 1) / 2);
912 
913  if (a == c)
914  {
915  p = ROUND_PREC(osize);
916  p = MAX(p, default_precision);
917 
918  if ((out = s_alloc(p)) == NULL)
919  return MP_MEMORY;
920  }
921  else
922  {
923  if (!s_pad(c, osize))
924  return MP_MEMORY;
925 
926  out = MP_DIGITS(c);
927  }
928  ZERO(out, osize);
929 
930  s_ksqr(MP_DIGITS(a), out, MP_USED(a));
931 
932  /*
933  * Get rid of whatever memory c was already using, and fix up its fields
934  * to reflect the new digit array it's using
935  */
936  if (out != MP_DIGITS(c))
937  {
938  s_free(MP_DIGITS(c));
939  MP_DIGITS(c) = out;
940  MP_ALLOC(c) = p;
941  }
942 
943  MP_USED(c) = osize; /* might not be true, but we'll fix it ... */
944  CLAMP(c); /* ... right here */
945  MP_SIGN(c) = MP_ZPOS;
946 
947  return MP_OK;
948 }
static int s_pad(mp_int z, mp_size min)
Definition: imath.c:2324
static mp_size default_precision
Definition: imath.c:167
#define MP_ALLOC(Z)
Definition: imath.h:68
#define MAX(A, B)
Definition: imath.c:139
#define s_free(P)
Definition: imath.c:182
#define ZERO(P, S)
Definition: imath.c:116
const mp_sign MP_ZPOS
Definition: imath.c:53
#define ROUND_PREC(P)
Definition: imath.c:113
static mp_digit * s_alloc(mp_size num)
Definition: imath.c:2284
#define MP_DIGITS(Z)
Definition: imath.h:67
const mp_result MP_OK
Definition: imath.c:43
#define MP_USED(Z)
Definition: imath.h:69
#define MP_SIGN(Z)
Definition: imath.h:70
unsigned int mp_size
Definition: imath.h:40
#define CHECK(TEST)
Definition: imath.c:74
static int s_ksqr(mp_digit *da, mp_digit *dc, mp_size size_a)
Definition: imath.c:2677
#define CLAMP(Z)
Definition: imath.c:131
const mp_result MP_MEMORY
Definition: imath.c:46
uint32 mp_digit
Definition: imath.h:44
mp_result mp_int_sqrt ( mp_int  a,
mp_int  c 
)

Definition at line 1808 of file imath.c.

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

1809 {
1810  mp_result res = MP_OK;
1811  mpz_t temp[2];
1812  int last = 0;
1813 
1814  CHECK(a != NULL && c != NULL);
1815 
1816  /* The square root of a negative value does not exist in the integers. */
1817  if (MP_SIGN(a) == MP_NEG)
1818  return MP_UNDEF;
1819 
1820  SETUP(mp_int_init_copy(TEMP(last), a), last);
1821  SETUP(mp_int_init(TEMP(last)), last);
1822 
1823  for (;;)
1824  {
1825  if ((res = mp_int_sqr(TEMP(0), TEMP(1))) != MP_OK)
1826  goto CLEANUP;
1827 
1828  if (mp_int_compare_unsigned(a, TEMP(1)) == 0)
1829  break;
1830 
1831  if ((res = mp_int_copy(a, TEMP(1))) != MP_OK)
1832  goto CLEANUP;
1833  if ((res = mp_int_div(TEMP(1), TEMP(0), TEMP(1), NULL)) != MP_OK)
1834  goto CLEANUP;
1835  if ((res = mp_int_add(TEMP(0), TEMP(1), TEMP(1))) != MP_OK)
1836  goto CLEANUP;
1837  if ((res = mp_int_div_pow2(TEMP(1), 1, TEMP(1), NULL)) != MP_OK)
1838  goto CLEANUP;
1839 
1840  if (mp_int_compare_unsigned(TEMP(0), TEMP(1)) == 0)
1841  break;
1842  if ((res = mp_int_sub_value(TEMP(0), 1, TEMP(0))) != MP_OK)
1843  goto CLEANUP;
1844  if (mp_int_compare_unsigned(TEMP(0), TEMP(1)) == 0)
1845  break;
1846 
1847  if ((res = mp_int_copy(TEMP(1), TEMP(0))) != MP_OK)
1848  goto CLEANUP;
1849  }
1850 
1851  res = mp_int_copy(TEMP(0), c);
1852 
1853 CLEANUP:
1854  while (--last >= 0)
1855  mp_int_clear(TEMP(last));
1856 
1857  return res;
1858 }
int mp_int_compare_unsigned(mp_int a, mp_int b)
Definition: imath.c:1277
const mp_sign MP_NEG
Definition: imath.c:52
mp_result mp_int_sub_value(mp_int a, int value, mp_int c)
Definition: imath.c:779
mp_result mp_int_div_pow2(mp_int a, int p2, mp_int q, mp_int r)
Definition: imath.c:1146
mp_result mp_int_copy(mp_int a, mp_int c)
Definition: imath.c:510
mp_result mp_int_init_copy(mp_int z, mp_int old)
Definition: imath.c:412
#define SETUP(E, C)
Definition: imath.c:143
mp_result mp_int_init(mp_int z)
Definition: imath.c:361
mp_result mp_int_add(mp_int a, mp_int b, mp_int c)
Definition: imath.c:607
mp_result mp_int_div(mp_int a, mp_int b, mp_int q, mp_int r)
Definition: imath.c:955
#define TEMP(K)
Definition: imath.c:142
const mp_result MP_OK
Definition: imath.c:43
mp_result mp_int_sqr(mp_int a, mp_int c)
Definition: imath.c:902
const mp_result MP_UNDEF
Definition: imath.c:48
#define MP_SIGN(Z)
Definition: imath.h:70
void mp_int_clear(mp_int z)
Definition: imath.c:478
int mp_result
Definition: imath.h:41
#define CHECK(TEST)
Definition: imath.c:74
Definition: imath.h:57
mp_result mp_int_string_len ( mp_int  z,
mp_size  radix 
)

Definition at line 1969 of file imath.c.

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

1970 {
1971  int len;
1972 
1973  CHECK(z != NULL);
1974 
1975  if (radix < MP_MIN_RADIX || radix > MP_MAX_RADIX)
1976  return MP_RANGE;
1977 
1978  len = s_outlen(z, radix) + 1; /* for terminator */
1979 
1980  /* Allow for sign marker on negatives */
1981  if (MP_SIGN(z) == MP_NEG)
1982  len += 1;
1983 
1984  return len;
1985 }
static int s_outlen(mp_int z, mp_size r)
Definition: imath.c:3509
const mp_sign MP_NEG
Definition: imath.c:52
const mp_result MP_RANGE
Definition: imath.c:47
#define MP_SIGN(Z)
Definition: imath.h:70
#define CHECK(TEST)
Definition: imath.c:74
#define MP_MAX_RADIX
Definition: imath.h:85
mp_result mp_int_sub ( mp_int  a,
mp_int  b,
mp_int  c 
)

Definition at line 699 of file imath.c.

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

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

700 {
701  mp_size ua,
702  ub,
703  uc,
704  max;
705 
706  CHECK(a != NULL && b != NULL && c != NULL);
707 
708  ua = MP_USED(a);
709  ub = MP_USED(b);
710  uc = MP_USED(c);
711  max = MAX(ua, ub);
712 
713  if (MP_SIGN(a) != MP_SIGN(b))
714  {
715  /* Different signs -- add magnitudes and keep sign of a */
716  mp_digit carry;
717 
718  if (!s_pad(c, max))
719  return MP_MEMORY;
720 
721  carry = s_uadd(MP_DIGITS(a), MP_DIGITS(b), MP_DIGITS(c), ua, ub);
722  uc = max;
723 
724  if (carry)
725  {
726  if (!s_pad(c, max + 1))
727  return MP_MEMORY;
728 
729  c->digits[max] = carry;
730  ++uc;
731  }
732 
733  MP_USED(c) = uc;
734  MP_SIGN(c) = MP_SIGN(a);
735 
736  }
737  else
738  {
739  /* Same signs -- subtract magnitudes */
740  mp_int x,
741  y;
742  mp_sign osign;
743  int cmp = s_ucmp(a, b);
744 
745  if (!s_pad(c, max))
746  return MP_MEMORY;
747 
748  if (cmp >= 0)
749  {
750  x = a;
751  y = b;
752  osign = MP_ZPOS;
753  }
754  else
755  {
756  x = b;
757  y = a;
758  osign = MP_NEG;
759  }
760 
761  if (MP_SIGN(a) == MP_NEG && cmp != 0)
762  osign = 1 - osign;
763 
764  s_usub(MP_DIGITS(x), MP_DIGITS(y), MP_DIGITS(c), MP_USED(x), MP_USED(y));
765  MP_USED(c) = MP_USED(x);
766  CLAMP(c);
767 
768  MP_SIGN(c) = osign;
769  }
770 
771  return MP_OK;
772 }
static int s_pad(mp_int z, mp_size min)
Definition: imath.c:2324
#define MAX(A, B)
Definition: imath.c:139
const mp_sign MP_NEG
Definition: imath.c:52
mp_digit * digits
Definition: imath.h:59
const mp_sign MP_ZPOS
Definition: imath.c:53
#define MP_DIGITS(Z)
Definition: imath.h:67
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:2464
const mp_result MP_OK
Definition: imath.c:43
static void s_usub(mp_digit *da, mp_digit *db, mp_digit *dc, mp_size size_a, mp_size size_b)
Definition: imath.c:2503
#define MP_USED(Z)
Definition: imath.h:69
#define MP_SIGN(Z)
Definition: imath.h:70
unsigned char mp_sign
Definition: imath.h:39
static int s_ucmp(mp_int a, mp_int b)
Definition: imath.c:2425
unsigned int mp_size
Definition: imath.h:40
#define CHECK(TEST)
Definition: imath.c:74
#define CLAMP(Z)
Definition: imath.c:131
const mp_result MP_MEMORY
Definition: imath.c:46
uint32 mp_digit
Definition: imath.h:44
Definition: imath.h:57
static int cmp(const chr *x, const chr *y, size_t len)
Definition: regc_locale.c:742
mp_result mp_int_sub_value ( mp_int  a,
int  value,
mp_int  c 
)

Definition at line 779 of file imath.c.

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

Referenced by mp_int_sqrt().

780 {
781  mpz_t vtmp;
783 
784  s_fake(&vtmp, value, vbuf);
785 
786  return mp_int_sub(a, &vtmp, c);
787 }
#define MP_VALUE_DIGITS(V)
Definition: imath.c:109
mp_result mp_int_sub(mp_int a, mp_int b, mp_int c)
Definition: imath.c:699
static struct @121 value
static void s_fake(mp_int z, int value, mp_digit vbuf[])
Definition: imath.c:2364
uint32 mp_digit
Definition: imath.h:44
Definition: imath.h:57
void mp_int_swap ( mp_int  a,
mp_int  c 
)

Definition at line 539 of file imath.c.

540 {
541  if (a != c)
542  {
543  mpz_t tmp = *a;
544 
545  *a = *c;
546  *c = tmp;
547  }
548 }
char * c
Definition: imath.h:57
mp_result mp_int_to_binary ( mp_int  z,
unsigned char *  buf,
int  limit 
)

Definition at line 2103 of file imath.c.

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

2104 {
2105  static const int PAD_FOR_2C = 1;
2106 
2107  mp_result res;
2108  int limpos = limit;
2109 
2110  CHECK(z != NULL && buf != NULL);
2111 
2112  res = s_tobin(z, buf, &limpos, PAD_FOR_2C);
2113 
2114  if (MP_SIGN(z) == MP_NEG)
2115  s_2comp(buf, limpos);
2116 
2117  return res;
2118 }
const mp_sign MP_NEG
Definition: imath.c:52
static void s_2comp(unsigned char *buf, int len)
Definition: imath.c:3579
static char * buf
Definition: pg_test_fsync.c:67
#define MP_SIGN(Z)
Definition: imath.h:70
static mp_result s_tobin(mp_int z, unsigned char *buf, int *limpos, int pad)
Definition: imath.c:3603
int mp_result
Definition: imath.h:41
#define CHECK(TEST)
Definition: imath.c:74
mp_result mp_int_to_int ( mp_int  z,
int *  out 
)

Definition at line 1865 of file imath.c.

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

Referenced by mp_int_div_value().

1866 {
1867  unsigned int uv = 0;
1868  mp_size uz;
1869  mp_digit *dz;
1870  mp_sign sz;
1871 
1872  CHECK(z != NULL);
1873 
1874  /* Make sure the value is representable as an int */
1875  sz = MP_SIGN(z);
1876  if ((sz == MP_ZPOS && mp_int_compare_value(z, INT_MAX) > 0) ||
1877  mp_int_compare_value(z, INT_MIN) < 0)
1878  return MP_RANGE;
1879 
1880  uz = MP_USED(z);
1881  dz = MP_DIGITS(z) + uz - 1;
1882 
1883  while (uz > 0)
1884  {
1885  uv <<= MP_DIGIT_BIT / 2;
1886  uv = (uv << (MP_DIGIT_BIT / 2)) | *dz--;
1887  --uz;
1888  }
1889 
1890  if (out)
1891  *out = (sz == MP_NEG) ? -(int) uv : (int) uv;
1892 
1893  return MP_OK;
1894 }
const mp_sign MP_NEG
Definition: imath.c:52
#define MP_DIGIT_BIT
Definition: imath.h:81
const mp_result MP_RANGE
Definition: imath.c:47
const mp_sign MP_ZPOS
Definition: imath.c:53
#define MP_DIGITS(Z)
Definition: imath.h:67
const mp_result MP_OK
Definition: imath.c:43
#define MP_USED(Z)
Definition: imath.h:69
#define MP_SIGN(Z)
Definition: imath.h:70
unsigned char mp_sign
Definition: imath.h:39
unsigned int mp_size
Definition: imath.h:40
#define CHECK(TEST)
Definition: imath.c:74
uint32 mp_digit
Definition: imath.h:44
int mp_int_compare_value(mp_int z, int value)
Definition: imath.c:1306
mp_result mp_int_to_string ( mp_int  z,
mp_size  radix,
char *  str,
int  limit 
)

Definition at line 1901 of file imath.c.

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

1903 {
1904  mp_result res;
1905  int cmp = 0;
1906 
1907  CHECK(z != NULL && str != NULL && limit >= 2);
1908 
1909  if (radix < MP_MIN_RADIX || radix > MP_MAX_RADIX)
1910  return MP_RANGE;
1911 
1912  if (CMPZ(z) == 0)
1913  {
1914  *str++ = s_val2ch(0, mp_flags & MP_CAP_DIGITS);
1915  }
1916  else
1917  {
1918  mpz_t tmp;
1919  char *h,
1920  *t;
1921 
1922  if ((res = mp_int_init_copy(&tmp, z)) != MP_OK)
1923  return res;
1924 
1925  if (MP_SIGN(z) == MP_NEG)
1926  {
1927  *str++ = '-';
1928  --limit;
1929  }
1930  h = str;
1931 
1932  /* Generate digits in reverse order until finished or limit reached */
1933  for ( /* */ ; limit > 0; --limit)
1934  {
1935  mp_digit d;
1936 
1937  if ((cmp = CMPZ(&tmp)) == 0)
1938  break;
1939 
1940  d = s_ddiv(&tmp, (mp_digit) radix);
1941  *str++ = s_val2ch(d, mp_flags & MP_CAP_DIGITS);
1942  }
1943  t = str - 1;
1944 
1945  /* Put digits back in correct output order */
1946  while (h < t)
1947  {
1948  char tc = *h;
1949 
1950  *h++ = *t;
1951  *t-- = tc;
1952  }
1953 
1954  mp_int_clear(&tmp);
1955  }
1956 
1957  *str = '\0';
1958  if (cmp == 0)
1959  return MP_OK;
1960  else
1961  return MP_TRUNC;
1962 }
static char s_val2ch(int v, int caps)
Definition: imath.c:3557
const mp_sign MP_NEG
Definition: imath.c:52
#define MP_CAP_DIGITS
Definition: imath.c:70
static mp_word mp_flags
Definition: imath.c:173
const mp_result MP_RANGE
Definition: imath.c:47
#define CMPZ(Z)
Definition: imath.c:146
mp_result mp_int_init_copy(mp_int z, mp_int old)
Definition: imath.c:412
const mp_result MP_TRUNC
Definition: imath.c:49
const mp_result MP_OK
Definition: imath.c:43
#define MP_SIGN(Z)
Definition: imath.h:70
void mp_int_clear(mp_int z)
Definition: imath.c:478
int mp_result
Definition: imath.h:41
#define CHECK(TEST)
Definition: imath.c:74
static mp_digit s_ddiv(mp_int a, mp_digit b)
Definition: imath.c:2886
uint32 mp_digit
Definition: imath.h:44
Definition: imath.h:57
#define MP_MAX_RADIX
Definition: imath.h:85
static int cmp(const chr *x, const chr *y, size_t len)
Definition: regc_locale.c:742
mp_result mp_int_to_unsigned ( mp_int  z,
unsigned char *  buf,
int  limit 
)

Definition at line 2196 of file imath.c.

References CHECK, and s_tobin().

Referenced by bn_to_mpi().

2197 {
2198  static const int NO_PADDING = 0;
2199 
2200  CHECK(z != NULL && buf != NULL);
2201 
2202  return s_tobin(z, buf, &limit, NO_PADDING);
2203 }
static char * buf
Definition: pg_test_fsync.c:67
static mp_result s_tobin(mp_int z, unsigned char *buf, int *limpos, int pad)
Definition: imath.c:3603
#define CHECK(TEST)
Definition: imath.c:74
mp_result mp_int_unsigned_len ( mp_int  z)

Definition at line 2241 of file imath.c.

References mp_int_count_bits().

Referenced by mp_int_binary_len().

2242 {
2243  mp_result res = mp_int_count_bits(z);
2244  int bytes;
2245 
2246  if (res <= 0)
2247  return res;
2248 
2249  bytes = (res + (CHAR_BIT - 1)) / CHAR_BIT;
2250 
2251  return bytes;
2252 }
mp_result mp_int_count_bits(mp_int z)
Definition: imath.c:2073
int mp_result
Definition: imath.h:41
void mp_int_zero ( mp_int  z)

Definition at line 555 of file imath.c.

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

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

556 {
557  NRCHECK(z != NULL);
558 
559  z->digits[0] = 0;
560  MP_USED(z) = 1;
561  MP_SIGN(z) = MP_ZPOS;
562 }
mp_digit * digits
Definition: imath.h:59
#define NRCHECK(TEST)
Definition: imath.c:75
const mp_sign MP_ZPOS
Definition: imath.c:53
#define MP_USED(Z)
Definition: imath.h:69
#define MP_SIGN(Z)
Definition: imath.h:70
void mp_set_default_precision ( mp_size  s)

Definition at line 329 of file imath.c.

References default_precision, NRCHECK, and ROUND_PREC.

330 {
331  NRCHECK(s > 0);
332 
334 }
static mp_size default_precision
Definition: imath.c:167
#define NRCHECK(TEST)
Definition: imath.c:75
#define ROUND_PREC(P)
Definition: imath.c:113
unsigned int mp_size
Definition: imath.h:40
void mp_set_multiply_threshold ( mp_size  s)

Definition at line 351 of file imath.c.

References multiply_threshold.

352 {
353  multiply_threshold = s;
354 }
static mp_size multiply_threshold
Definition: imath.c:170

Variable Documentation

const mp_result MP_BADARG

Definition at line 50 of file imath.c.

const mp_result MP_FALSE

Definition at line 44 of file imath.c.

const mp_result MP_TRUE

Definition at line 45 of file imath.c.

const mp_result MP_TRUNC

Definition at line 49 of file imath.c.

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