Back to index

lightning-sunbird  0.9+nobinonly
Classes | Defines | Functions | Variables
mpi-priv.h File Reference
#include "mpi.h"
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes

struct  mp_mont_modulus

Defines

#define DIAG(T, V)
#define LOG_V_2(R)   s_logv_2[(R)]
#define CARRYOUT(W)   (mp_digit)((W)>>DIGIT_BIT)
#define ACCUM(W)   (mp_digit)(W)
#define MP_MIN(a, b)   (((a) < (b)) ? (a) : (b))
#define MP_MAX(a, b)   (((a) > (b)) ? (a) : (b))
#define MP_HOWMANY(a, b)   (((a) + (b) - 1)/(b))
#define MP_ROUNDUP(a, b)   (MP_HOWMANY(a,b) * (b))
#define MP_LT   -1
#define MP_EQ   0
#define MP_GT   1
#define MPI_ASM_DECL
#define s_mp_mul_d_add_offset(a, b, c, off)   (s_mpv_mul_d_add_prop(MP_DIGITS(a), MP_USED(a), b, MP_DIGITS(c) + off), MP_OKAY)

Functions

void s_mp_setz (mp_digit *dp, mp_size count)
void s_mp_copy (const mp_digit *sp, mp_digit *dp, mp_size count)
voids_mp_alloc (size_t nb, size_t ni)
void s_mp_free (void *ptr)
mp_err s_mp_grow (mp_int *mp, mp_size min)
mp_err s_mp_pad (mp_int *mp, mp_size min)
void s_mp_clamp (mp_int *mp)
void s_mp_exch (mp_int *a, mp_int *b)
mp_err s_mp_lshd (mp_int *mp, mp_size p)
void s_mp_rshd (mp_int *mp, mp_size p)
mp_err s_mp_mul_2d (mp_int *mp, mp_digit d)
void s_mp_div_2d (mp_int *mp, mp_digit d)
void s_mp_mod_2d (mp_int *mp, mp_digit d)
void s_mp_div_2 (mp_int *mp)
mp_err s_mp_mul_2 (mp_int *mp)
mp_err s_mp_norm (mp_int *a, mp_int *b, mp_digit *pd)
mp_err s_mp_add_d (mp_int *mp, mp_digit d)
mp_err s_mp_sub_d (mp_int *mp, mp_digit d)
mp_err s_mp_mul_d (mp_int *mp, mp_digit d)
mp_err s_mp_div_d (mp_int *mp, mp_digit d, mp_digit *r)
mp_err s_mp_reduce (mp_int *x, const mp_int *m, const mp_int *mu)
mp_err s_mp_add (mp_int *a, const mp_int *b)
mp_err s_mp_add_3arg (const mp_int *a, const mp_int *b, mp_int *c)
mp_err s_mp_sub (mp_int *a, const mp_int *b)
mp_err s_mp_sub_3arg (const mp_int *a, const mp_int *b, mp_int *c)
mp_err s_mp_add_offset (mp_int *a, mp_int *b, mp_size offset)
mp_err s_mp_mul (mp_int *a, const mp_int *b)
mp_err s_mp_sqr (mp_int *a)
mp_err s_mp_div (mp_int *rem, mp_int *div, mp_int *quot)
mp_err s_mp_exptmod (const mp_int *a, const mp_int *b, const mp_int *m, mp_int *c)
mp_err s_mp_2expt (mp_int *a, mp_digit k)
int s_mp_cmp (const mp_int *a, const mp_int *b)
int s_mp_cmp_d (const mp_int *a, mp_digit d)
int s_mp_ispow2 (const mp_int *v)
int s_mp_ispow2d (mp_digit d)
int s_mp_tovalue (char ch, int r)
char s_mp_todigit (mp_digit val, int r, int low)
int s_mp_outlen (int bits, int r)
mp_digit s_mp_invmod_radix (mp_digit P)
mp_err s_mp_invmod_odd_m (const mp_int *a, const mp_int *m, mp_int *c)
mp_err s_mp_invmod_2d (const mp_int *a, mp_size k, mp_int *c)
mp_err s_mp_invmod_even_m (const mp_int *a, const mp_int *m, mp_int *c)
void MPI_ASM_DECL s_mpv_mul_d (const mp_digit *a, mp_size a_len, mp_digit b, mp_digit *c)
void MPI_ASM_DECL s_mpv_mul_d_add (const mp_digit *a, mp_size a_len, mp_digit b, mp_digit *c)
void MPI_ASM_DECL s_mpv_mul_d_add_prop (const mp_digit *a, mp_size a_len, mp_digit b, mp_digit *c)
void MPI_ASM_DECL s_mpv_sqr_add_prop (const mp_digit *a, mp_size a_len, mp_digit *sqrs)
mp_err MPI_ASM_DECL s_mpv_div_2dx1d (mp_digit Nhi, mp_digit Nlo, mp_digit divisor, mp_digit *quot, mp_digit *rem)
mp_err s_mp_mul_mont (const mp_int *a, const mp_int *b, mp_int *c, mp_mont_modulus *mmm)
mp_err s_mp_redc (mp_int *T, mp_mont_modulus *mmm)
unsigned long s_mpi_getProcessorLineSize ()

Variables

const float s_logv_2 []
unsigned long mp_allocs
unsigned long mp_frees
unsigned long mp_copies

Class Documentation

struct mp_mont_modulus

Definition at line 293 of file mpi-priv.h.

Collaboration diagram for mp_mont_modulus:
Class Members
mp_size b
mp_int N
mp_digit n0prime

Define Documentation

#define ACCUM (   W)    (mp_digit)(W)

Definition at line 113 of file mpi-priv.h.

#define CARRYOUT (   W)    (mp_digit)((W)>>DIGIT_BIT)

Definition at line 112 of file mpi-priv.h.

#define DIAG (   T,
  V 
)

Definition at line 59 of file mpi-priv.h.

#define LOG_V_2 (   R)    s_logv_2[(R)]

Definition at line 85 of file mpi-priv.h.

#define MP_EQ   0

Definition at line 125 of file mpi-priv.h.

#define MP_GT   1

Definition at line 126 of file mpi-priv.h.

#define MP_HOWMANY (   a,
  b 
)    (((a) + (b) - 1)/(b))

Definition at line 117 of file mpi-priv.h.

#define MP_LT   -1

Definition at line 124 of file mpi-priv.h.

#define MP_MAX (   a,
  b 
)    (((a) > (b)) ? (a) : (b))

Definition at line 116 of file mpi-priv.h.

#define MP_MIN (   a,
  b 
)    (((a) < (b)) ? (a) : (b))

Definition at line 115 of file mpi-priv.h.

#define MP_ROUNDUP (   a,
  b 
)    (MP_HOWMANY(a,b) * (b))

Definition at line 118 of file mpi-priv.h.

Definition at line 254 of file mpi-priv.h.

#define s_mp_mul_d_add_offset (   a,
  b,
  c,
  off 
)    (s_mpv_mul_d_add_prop(MP_DIGITS(a), MP_USED(a), b, MP_DIGITS(c) + off), MP_OKAY)

Definition at line 290 of file mpi-priv.h.


Function Documentation

mp_err s_mp_2expt ( mp_int a,
mp_digit  k 
)

Definition at line 4330 of file mpi.c.

{
  mp_err    res;
  mp_size   dig, bit;

  dig = k / DIGIT_BIT;
  bit = k % DIGIT_BIT;

  mp_zero(a);
  if((res = s_mp_pad(a, dig + 1)) != MP_OKAY)
    return res;
  
  DIGIT(a, dig) |= ((mp_digit)1 << bit);

  return MP_OKAY;

} /* end s_mp_2expt() */

Here is the call graph for this function:

mp_err s_mp_add ( mp_int a,
const mp_int b 
)

Definition at line 3474 of file mpi.c.

{
#if !defined(MP_NO_MP_WORD) && !defined(MP_NO_ADD_WORD)
  mp_word   w = 0;
#else
  mp_digit  d, sum, carry = 0;
#endif
  mp_digit *pa, *pb;
  mp_size   ix;
  mp_size   used;
  mp_err    res;

  /* Make sure a has enough precision for the output value */
  if((USED(b) > USED(a)) && (res = s_mp_pad(a, USED(b))) != MP_OKAY)
    return res;

  /*
    Add up all digits up to the precision of b.  If b had initially
    the same precision as a, or greater, we took care of it by the
    padding step above, so there is no problem.  If b had initially
    less precision, we'll have to make sure the carry out is duly
    propagated upward among the higher-order digits of the sum.
   */
  pa = MP_DIGITS(a);
  pb = MP_DIGITS(b);
  used = MP_USED(b);
  for(ix = 0; ix < used; ix++) {
#if !defined(MP_NO_MP_WORD) && !defined(MP_NO_ADD_WORD)
    w = w + *pa + *pb++;
    *pa++ = ACCUM(w);
    w = CARRYOUT(w);
#else
    d = *pa;
    sum = d + *pb++;
    d = (sum < d);                 /* detect overflow */
    *pa++ = sum += carry;
    carry = d + (sum < carry);            /* detect overflow */
#endif
  }

  /* If we run out of 'b' digits before we're actually done, make
     sure the carries get propagated upward...  
   */
  used = MP_USED(a);
#if !defined(MP_NO_MP_WORD) && !defined(MP_NO_ADD_WORD)
  while (w && ix < used) {
    w = w + *pa;
    *pa++ = ACCUM(w);
    w = CARRYOUT(w);
    ++ix;
  }
#else
  while (carry && ix < used) {
    sum = carry + *pa;
    *pa++ = sum;
    carry = !sum;
    ++ix;
  }
#endif

  /* If there's an overall carry out, increase precision and include
     it.  We could have done this initially, but why touch the memory
     allocator unless we're sure we have to?
   */
#if !defined(MP_NO_MP_WORD) && !defined(MP_NO_ADD_WORD)
  if (w) {
    if((res = s_mp_pad(a, used + 1)) != MP_OKAY)
      return res;

    DIGIT(a, ix) = (mp_digit)w;
  }
#else
  if (carry) {
    if((res = s_mp_pad(a, used + 1)) != MP_OKAY)
      return res;

    DIGIT(a, used) = carry;
  }
#endif

  return MP_OKAY;
} /* end s_mp_add() */

Here is the call graph for this function:

mp_err s_mp_add_3arg ( const mp_int a,
const mp_int b,
mp_int c 
)

Definition at line 3560 of file mpi.c.

{
  mp_digit *pa, *pb, *pc;
#if !defined(MP_NO_MP_WORD) && !defined(MP_NO_ADD_WORD)
  mp_word   w = 0;
#else
  mp_digit  sum, carry = 0, d;
#endif
  mp_size   ix;
  mp_size   used;
  mp_err    res;

  MP_SIGN(c) = MP_SIGN(a);
  if (MP_USED(a) < MP_USED(b)) {
    const mp_int *xch = a;
    a = b;
    b = xch;
  }

  /* Make sure a has enough precision for the output value */
  if (MP_OKAY != (res = s_mp_pad(c, MP_USED(a))))
    return res;

  /*
    Add up all digits up to the precision of b.  If b had initially
    the same precision as a, or greater, we took care of it by the
    exchange step above, so there is no problem.  If b had initially
    less precision, we'll have to make sure the carry out is duly
    propagated upward among the higher-order digits of the sum.
   */
  pa = MP_DIGITS(a);
  pb = MP_DIGITS(b);
  pc = MP_DIGITS(c);
  used = MP_USED(b);
  for (ix = 0; ix < used; ix++) {
#if !defined(MP_NO_MP_WORD) && !defined(MP_NO_ADD_WORD)
    w = w + *pa++ + *pb++;
    *pc++ = ACCUM(w);
    w = CARRYOUT(w);
#else
    d = *pa++;
    sum = d + *pb++;
    d = (sum < d);                 /* detect overflow */
    *pc++ = sum += carry;
    carry = d + (sum < carry);            /* detect overflow */
#endif
  }

  /* If we run out of 'b' digits before we're actually done, make
     sure the carries get propagated upward...  
   */
  for (used = MP_USED(a); ix < used; ++ix) {
#if !defined(MP_NO_MP_WORD) && !defined(MP_NO_ADD_WORD)
    w = w + *pa++;
    *pc++ = ACCUM(w);
    w = CARRYOUT(w);
#else
    *pc++ = sum = carry + *pa++;
    carry = (sum < carry);
#endif
  }

  /* If there's an overall carry out, increase precision and include
     it.  We could have done this initially, but why touch the memory
     allocator unless we're sure we have to?
   */
#if !defined(MP_NO_MP_WORD) && !defined(MP_NO_ADD_WORD)
  if (w) {
    if((res = s_mp_pad(c, used + 1)) != MP_OKAY)
      return res;

    DIGIT(c, used) = (mp_digit)w;
    ++used;
  }
#else
  if (carry) {
    if((res = s_mp_pad(c, used + 1)) != MP_OKAY)
      return res;

    DIGIT(c, used) = carry;
    ++used;
  }
#endif
  MP_USED(c) = used;
  return MP_OKAY;
}

Here is the call graph for this function:

mp_err s_mp_add_d ( mp_int mp,
mp_digit  d 
)

Definition at line 3213 of file mpi.c.

{
#if !defined(MP_NO_MP_WORD) && !defined(MP_NO_ADD_WORD)
  mp_word   w, k = 0;
  mp_size   ix = 1;

  w = (mp_word)DIGIT(mp, 0) + d;
  DIGIT(mp, 0) = ACCUM(w);
  k = CARRYOUT(w);

  while(ix < USED(mp) && k) {
    w = (mp_word)DIGIT(mp, ix) + k;
    DIGIT(mp, ix) = ACCUM(w);
    k = CARRYOUT(w);
    ++ix;
  }

  if(k != 0) {
    mp_err  res;

    if((res = s_mp_pad(mp, USED(mp) + 1)) != MP_OKAY)
      return res;

    DIGIT(mp, ix) = (mp_digit)k;
  }

  return MP_OKAY;
#else
  mp_digit * pmp = MP_DIGITS(mp);
  mp_digit sum, mp_i, carry = 0;
  mp_err   res = MP_OKAY;
  int used = (int)MP_USED(mp);

  mp_i = *pmp;
  *pmp++ = sum = d + mp_i;
  carry = (sum < d);
  while (carry && --used > 0) {
    mp_i = *pmp;
    *pmp++ = sum = carry + mp_i;
    carry = !sum;
  }
  if (carry && !used) {
    /* mp is growing */
    used = MP_USED(mp);
    MP_CHECKOK( s_mp_pad(mp, used + 1) );
    MP_DIGIT(mp, used) = carry;
  }
CLEANUP:
  return res;
#endif
} /* end s_mp_add_d() */

Here is the call graph for this function:

mp_err s_mp_add_offset ( mp_int a,
mp_int b,
mp_size  offset 
)

Definition at line 3649 of file mpi.c.

{
#if !defined(MP_NO_MP_WORD) && !defined(MP_NO_ADD_WORD)
  mp_word   w, k = 0;
#else
  mp_digit  d, sum, carry = 0;
#endif
  mp_size   ib;
  mp_size   ia;
  mp_size   lim;
  mp_err    res;

  /* Make sure a has enough precision for the output value */
  lim = MP_USED(b) + offset;
  if((lim > USED(a)) && (res = s_mp_pad(a, lim)) != MP_OKAY)
    return res;

  /*
    Add up all digits up to the precision of b.  If b had initially
    the same precision as a, or greater, we took care of it by the
    padding step above, so there is no problem.  If b had initially
    less precision, we'll have to make sure the carry out is duly
    propagated upward among the higher-order digits of the sum.
   */
  lim = USED(b);
  for(ib = 0, ia = offset; ib < lim; ib++, ia++) {
#if !defined(MP_NO_MP_WORD) && !defined(MP_NO_ADD_WORD)
    w = (mp_word)DIGIT(a, ia) + DIGIT(b, ib) + k;
    DIGIT(a, ia) = ACCUM(w);
    k = CARRYOUT(w);
#else
    d = MP_DIGIT(a, ia);
    sum = d + MP_DIGIT(b, ib);
    d = (sum < d);
    MP_DIGIT(a,ia) = sum += carry;
    carry = d + (sum < carry);
#endif
  }

  /* If we run out of 'b' digits before we're actually done, make
     sure the carries get propagated upward...  
   */
#if !defined(MP_NO_MP_WORD) && !defined(MP_NO_ADD_WORD)
  for (lim = MP_USED(a); k && (ia < lim); ++ia) {
    w = (mp_word)DIGIT(a, ia) + k;
    DIGIT(a, ia) = ACCUM(w);
    k = CARRYOUT(w);
  }
#else
  for (lim = MP_USED(a); carry && (ia < lim); ++ia) {
    d = MP_DIGIT(a, ia);
    MP_DIGIT(a,ia) = sum = d + carry;
    carry = (sum < d);
  }
#endif

  /* If there's an overall carry out, increase precision and include
     it.  We could have done this initially, but why touch the memory
     allocator unless we're sure we have to?
   */
#if !defined(MP_NO_MP_WORD) && !defined(MP_NO_ADD_WORD)
  if(k) {
    if((res = s_mp_pad(a, USED(a) + 1)) != MP_OKAY)
      return res;

    DIGIT(a, ia) = (mp_digit)k;
  }
#else
  if (carry) {
    if((res = s_mp_pad(a, lim + 1)) != MP_OKAY)
      return res;

    DIGIT(a, lim) = carry;
  }
#endif
  s_mp_clamp(a);

  return MP_OKAY;

} /* end s_mp_add_offset() */

Here is the call graph for this function:

void* s_mp_alloc ( size_t  nb,
size_t  ni 
)

Definition at line 2874 of file mpi.c.

{
  ++mp_allocs;
  return calloc(nb, ni);

} /* end s_mp_alloc() */

Here is the call graph for this function:

void s_mp_clamp ( mp_int mp)

Definition at line 2903 of file mpi.c.

{
  mp_size used = MP_USED(mp);
  while (used > 1 && DIGIT(mp, used - 1) == 0)
    --used;
  MP_USED(mp) = used;
} /* end s_mp_clamp() */
int s_mp_cmp ( const mp_int a,
const mp_int b 
)

Definition at line 4419 of file mpi.c.

{
  mp_size used_a = MP_USED(a);
  {
    mp_size used_b = MP_USED(b);

    if (used_a > used_b)
      goto IS_GT;
    if (used_a < used_b)
      goto IS_LT;
  }
  {
    mp_digit *pa, *pb;
    mp_digit da = 0, db = 0;

#define CMP_AB(n) if ((da = pa[n]) != (db = pb[n])) goto done

    pa = MP_DIGITS(a) + used_a;
    pb = MP_DIGITS(b) + used_a;
    while (used_a >= 4) {
      pa     -= 4;
      pb     -= 4;
      used_a -= 4;
      CMP_AB(3);
      CMP_AB(2);
      CMP_AB(1);
      CMP_AB(0);
    }
    while (used_a-- > 0 && ((da = *--pa) == (db = *--pb))) 
      /* do nothing */;
done:
    if (da > db)
      goto IS_GT;
    if (da < db) 
      goto IS_LT;
  }
  return MP_EQ;
IS_LT:
  return MP_LT;
IS_GT:
  return MP_GT;
} /* end s_mp_cmp() */

Here is the call graph for this function:

int s_mp_cmp_d ( const mp_int a,
mp_digit  d 
)

Definition at line 4467 of file mpi.c.

{
  if(USED(a) > 1)
    return MP_GT;

  if(DIGIT(a, 0) < d)
    return MP_LT;
  else if(DIGIT(a, 0) > d)
    return MP_GT;
  else
    return MP_EQ;

} /* end s_mp_cmp_d() */
void s_mp_copy ( const mp_digit sp,
mp_digit dp,
mp_size  count 
)

Definition at line 2854 of file mpi.c.

{
#if MP_MEMCPY == 0
  int  ix;

  for(ix = 0; ix < count; ix++)
    dp[ix] = sp[ix];
#else
  memcpy(dp, sp, count * sizeof(mp_digit));
#endif

} /* end s_mp_copy() */

Here is the call graph for this function:

mp_err s_mp_div ( mp_int rem,
mp_int div,
mp_int quot 
)

Definition at line 4192 of file mpi.c.

{
  mp_int   part, t;
#if !defined(MP_NO_MP_WORD) && !defined(MP_NO_DIV_WORD)
  mp_word  q_msd;
#else
  mp_digit q_msd;
#endif
  mp_err   res;
  mp_digit d;
  mp_digit div_msd;
  int      ix;

  if(mp_cmp_z(div) == 0)
    return MP_RANGE;

  /* Shortcut if divisor is power of two */
  if((ix = s_mp_ispow2(div)) >= 0) {
    MP_CHECKOK( mp_copy(rem, quot) );
    s_mp_div_2d(quot, (mp_digit)ix);
    s_mp_mod_2d(rem,  (mp_digit)ix);

    return MP_OKAY;
  }

  DIGITS(&t) = 0;
  MP_SIGN(rem) = ZPOS;
  MP_SIGN(div) = ZPOS;

  /* A working temporary for division     */
  MP_CHECKOK( mp_init_size(&t, MP_ALLOC(rem)));

  /* Normalize to optimize guessing       */
  MP_CHECKOK( s_mp_norm(rem, div, &d) );

  part = *rem;

  /* Perform the division itself...woo!   */
  MP_USED(quot) = MP_ALLOC(quot);

  /* Find a partial substring of rem which is at least div */
  /* If we didn't find one, we're finished dividing    */
  while (MP_USED(rem) > MP_USED(div) || s_mp_cmp(rem, div) >= 0) {
    int i;
    int unusedRem;

    unusedRem = MP_USED(rem) - MP_USED(div);
    MP_DIGITS(&part) = MP_DIGITS(rem) + unusedRem;
    MP_ALLOC(&part)  = MP_ALLOC(rem)  - unusedRem;
    MP_USED(&part)   = MP_USED(div);
    if (s_mp_cmp(&part, div) < 0) {
      -- unusedRem;
#if MP_ARGCHK == 2
      assert(unusedRem >= 0);
#endif
      -- MP_DIGITS(&part);
      ++ MP_USED(&part);
      ++ MP_ALLOC(&part);
    }

    /* Compute a guess for the next quotient digit       */
    q_msd = MP_DIGIT(&part, MP_USED(&part) - 1);
    div_msd = MP_DIGIT(div, MP_USED(div) - 1);
    if (q_msd >= div_msd) {
      q_msd = 1;
    } else if (MP_USED(&part) > 1) {
#if !defined(MP_NO_MP_WORD) && !defined(MP_NO_DIV_WORD)
      q_msd = (q_msd << MP_DIGIT_BIT) | MP_DIGIT(&part, MP_USED(&part) - 2);
      q_msd /= div_msd;
      if (q_msd == RADIX)
        --q_msd;
#else
      mp_digit r;
      MP_CHECKOK( s_mpv_div_2dx1d(q_msd, MP_DIGIT(&part, MP_USED(&part) - 2), 
                              div_msd, &q_msd, &r) );
#endif
    } else {
      q_msd = 0;
    }
#if MP_ARGCHK == 2
    assert(q_msd > 0); /* This case should never occur any more. */
#endif
    if (q_msd <= 0)
      break;

    /* See what that multiplies out to                   */
    mp_copy(div, &t);
    MP_CHECKOK( s_mp_mul_d(&t, (mp_digit)q_msd) );

    /* 
       If it's too big, back it off.  We should not have to do this
       more than once, or, in rare cases, twice.  Knuth describes a
       method by which this could be reduced to a maximum of once, but
       I didn't implement that here.
     * When using s_mpv_div_2dx1d, we may have to do this 3 times.
     */
    for (i = 4; s_mp_cmp(&t, &part) > 0 && i > 0; --i) {
      --q_msd;
      s_mp_sub(&t, div);    /* t -= div */
    }
    if (i < 0) {
      res = MP_RANGE;
      goto CLEANUP;
    }

    /* At this point, q_msd should be the right next digit   */
    MP_CHECKOK( s_mp_sub(&part, &t) );    /* part -= t */
    s_mp_clamp(rem);

    /*
      Include the digit in the quotient.  We allocated enough memory
      for any quotient we could ever possibly get, so we should not
      have to check for failures here
     */
    MP_DIGIT(quot, unusedRem) = (mp_digit)q_msd;
  }

  /* Denormalize remainder                */
  if (d) {
    s_mp_div_2d(rem, d);
  }

  s_mp_clamp(quot);

CLEANUP:
  mp_clear(&t);

  return res;

} /* end s_mp_div() */

Here is the call graph for this function:

void s_mp_div_2 ( mp_int mp)

Definition at line 3063 of file mpi.c.

{
  s_mp_div_2d(mp, 1);

} /* end s_mp_div_2() */

Here is the call graph for this function:

void s_mp_div_2d ( mp_int mp,
mp_digit  d 
)

Definition at line 3143 of file mpi.c.

{
  int       ix;
  mp_digit  save, next, mask;

  s_mp_rshd(mp, d / DIGIT_BIT);
  d %= DIGIT_BIT;
  if (d) {
    mask = ((mp_digit)1 << d) - 1;
    save = 0;
    for(ix = USED(mp) - 1; ix >= 0; ix--) {
      next = DIGIT(mp, ix) & mask;
      DIGIT(mp, ix) = (DIGIT(mp, ix) >> d) | (save << (DIGIT_BIT - d));
      save = next;
    }
  }
  s_mp_clamp(mp);

} /* end s_mp_div_2d() */

Here is the call graph for this function:

mp_err s_mp_div_d ( mp_int mp,
mp_digit  d,
mp_digit r 
)

Definition at line 3359 of file mpi.c.

{
#if !defined(MP_NO_MP_WORD) && !defined(MP_NO_DIV_WORD)
  mp_word   w = 0, q;
#else
  mp_digit  w, q;
#endif
  int       ix;
  mp_err    res;
  mp_int    quot;
  mp_int    rem;

  if(d == 0)
    return MP_RANGE;
  if (d == 1) {
    if (r)
      *r = 0;
    return MP_OKAY;
  }
  /* could check for power of 2 here, but mp_div_d does that. */
  if (MP_USED(mp) == 1) {
    mp_digit n   = MP_DIGIT(mp,0);
    mp_digit rem;

    q   = n / d;
    rem = n % d;
    MP_DIGIT(mp,0) = q;
    if (r)
      *r = rem;
    return MP_OKAY;
  }

  MP_DIGITS(&rem)  = 0;
  MP_DIGITS(&quot) = 0;
  /* Make room for the quotient */
  MP_CHECKOK( mp_init_size(&quot, USED(mp)) );

#if !defined(MP_NO_MP_WORD) && !defined(MP_NO_DIV_WORD)
  for(ix = USED(mp) - 1; ix >= 0; ix--) {
    w = (w << DIGIT_BIT) | DIGIT(mp, ix);

    if(w >= d) {
      q = w / d;
      w = w % d;
    } else {
      q = 0;
    }

    s_mp_lshd(&quot, 1);
    DIGIT(&quot, 0) = (mp_digit)q;
  }
#else
  {
    mp_digit p;
#if !defined(MP_ASSEMBLY_DIV_2DX1D)
    mp_digit norm;
#endif

    MP_CHECKOK( mp_init_copy(&rem, mp) );

#if !defined(MP_ASSEMBLY_DIV_2DX1D)
    MP_DIGIT(&quot, 0) = d;
    MP_CHECKOK( s_mp_norm(&rem, &quot, &norm) );
    if (norm)
      d <<= norm;
    MP_DIGIT(&quot, 0) = 0;
#endif

    p = 0;
    for (ix = USED(&rem) - 1; ix >= 0; ix--) {
      w = DIGIT(&rem, ix);

      if (p) {
        MP_CHECKOK( s_mpv_div_2dx1d(p, w, d, &q, &w) );
      } else if (w >= d) {
       q = w / d;
       w = w % d;
      } else {
       q = 0;
      }

      MP_CHECKOK( s_mp_lshd(&quot, 1) );
      DIGIT(&quot, 0) = q;
      p = w;
    }
#if !defined(MP_ASSEMBLY_DIV_2DX1D)
    if (norm)
      w >>= norm;
#endif
  }
#endif

  /* Deliver the remainder, if desired */
  if(r)
    *r = (mp_digit)w;

  s_mp_clamp(&quot);
  mp_exch(&quot, mp);
CLEANUP:
  mp_clear(&quot);
  mp_clear(&rem);

  return res;
} /* end s_mp_div_d() */

Here is the call graph for this function:

void s_mp_exch ( mp_int a,
mp_int b 
)

Definition at line 2917 of file mpi.c.

{
  mp_int   tmp;

  tmp = *a;
  *a = *b;
  *b = tmp;

} /* end s_mp_exch() */
mp_err s_mp_exptmod ( const mp_int a,
const mp_int b,
const mp_int m,
mp_int c 
)

Definition at line 1494 of file mpi.c.

{
  mp_int   s, x, mu;
  mp_err   res;
  mp_digit d;
  int      dig, bit;

  ARGCHK(a != NULL && b != NULL && c != NULL, MP_BADARG);

  if(mp_cmp_z(b) < 0 || mp_cmp_z(m) <= 0)
    return MP_RANGE;

  if((res = mp_init(&s)) != MP_OKAY)
    return res;
  if((res = mp_init_copy(&x, a)) != MP_OKAY ||
     (res = mp_mod(&x, m, &x)) != MP_OKAY)
    goto X;
  if((res = mp_init(&mu)) != MP_OKAY)
    goto MU;

  mp_set(&s, 1);

  /* mu = b^2k / m */
  s_mp_add_d(&mu, 1); 
  s_mp_lshd(&mu, 2 * USED(m));
  if((res = mp_div(&mu, m, &mu, NULL)) != MP_OKAY)
    goto CLEANUP;

  /* Loop over digits of b in ascending order, except highest order */
  for(dig = 0; dig < (USED(b) - 1); dig++) {
    d = DIGIT(b, dig);

    /* Loop over the bits of the lower-order digits */
    for(bit = 0; bit < DIGIT_BIT; bit++) {
      if(d & 1) {
       if((res = s_mp_mul(&s, &x)) != MP_OKAY)
         goto CLEANUP;
       if((res = s_mp_reduce(&s, m, &mu)) != MP_OKAY)
         goto CLEANUP;
      }

      d >>= 1;

      if((res = s_mp_sqr(&x)) != MP_OKAY)
       goto CLEANUP;
      if((res = s_mp_reduce(&x, m, &mu)) != MP_OKAY)
       goto CLEANUP;
    }
  }

  /* Now do the last digit... */
  d = DIGIT(b, dig);

  while(d) {
    if(d & 1) {
      if((res = s_mp_mul(&s, &x)) != MP_OKAY)
       goto CLEANUP;
      if((res = s_mp_reduce(&s, m, &mu)) != MP_OKAY)
       goto CLEANUP;
    }

    d >>= 1;

    if((res = s_mp_sqr(&x)) != MP_OKAY)
      goto CLEANUP;
    if((res = s_mp_reduce(&x, m, &mu)) != MP_OKAY)
      goto CLEANUP;
  }

  s_mp_exch(&s, c);

 CLEANUP:
  mp_clear(&mu);
 MU:
  mp_clear(&x);
 X:
  mp_clear(&s);

  return res;

} /* end s_mp_exptmod() */

Here is the call graph for this function:

void s_mp_free ( void ptr)

Definition at line 2888 of file mpi.c.

{
  if(ptr) {
    ++mp_frees;
    free(ptr);
  }
} /* end s_mp_free() */
mp_err s_mp_grow ( mp_int mp,
mp_size  min 
)

Definition at line 2777 of file mpi.c.

{
  if(min > ALLOC(mp)) {
    mp_digit   *tmp;

    /* Set min to next nearest default precision block size */
    min = MP_ROUNDUP(min, s_mp_defprec);

    if((tmp = s_mp_alloc(min, sizeof(mp_digit))) == NULL)
      return MP_MEM;

    s_mp_copy(DIGITS(mp), tmp, USED(mp));

#if MP_CRYPTO
    s_mp_setz(DIGITS(mp), ALLOC(mp));
#endif
    s_mp_free(DIGITS(mp));
    DIGITS(mp) = tmp;
    ALLOC(mp) = min;
  }

  return MP_OKAY;

} /* end s_mp_grow() */

Here is the call graph for this function:

mp_err s_mp_invmod_2d ( const mp_int a,
mp_size  k,
mp_int c 
)

Definition at line 2279 of file mpi.c.

{
  mp_err res;
  mp_size ix = k + 4;
  mp_int t0, t1, val, tmp, two2k;

  static const mp_digit d2 = 2;
  static const mp_int two = { MP_ZPOS, 1, 1, (mp_digit *)&d2 };

  if (mp_iseven(a))
    return MP_UNDEF;
  if (k <= MP_DIGIT_BIT) {
    mp_digit i = s_mp_invmod_radix(MP_DIGIT(a,0));
    if (k < MP_DIGIT_BIT)
      i &= ((mp_digit)1 << k) - (mp_digit)1;
    mp_set(c, i);
    return MP_OKAY;
  }
  MP_DIGITS(&t0) = 0;
  MP_DIGITS(&t1) = 0;
  MP_DIGITS(&val) = 0;
  MP_DIGITS(&tmp) = 0;
  MP_DIGITS(&two2k) = 0;
  MP_CHECKOK( mp_init_copy(&val, a) );
  s_mp_mod_2d(&val, k);
  MP_CHECKOK( mp_init_copy(&t0, &val) );
  MP_CHECKOK( mp_init_copy(&t1, &t0)  );
  MP_CHECKOK( mp_init(&tmp) );
  MP_CHECKOK( mp_init(&two2k) );
  MP_CHECKOK( s_mp_2expt(&two2k, k) );
  do {
    MP_CHECKOK( mp_mul(&val, &t1, &tmp)  );
    MP_CHECKOK( mp_sub(&two, &tmp, &tmp) );
    MP_CHECKOK( mp_mul(&t1, &tmp, &t1)   );
    s_mp_mod_2d(&t1, k);
    while (MP_SIGN(&t1) != MP_ZPOS) {
      MP_CHECKOK( mp_add(&t1, &two2k, &t1) );
    }
    if (mp_cmp(&t1, &t0) == MP_EQ) 
      break;
    MP_CHECKOK( mp_copy(&t1, &t0) );
  } while (--ix > 0);
  if (!ix) {
    res = MP_UNDEF;
  } else {
    mp_exch(c, &t1);
  }

CLEANUP:
  mp_clear(&t0);
  mp_clear(&t1);
  mp_clear(&val);
  mp_clear(&tmp);
  mp_clear(&two2k);
  return res;
}

Here is the call graph for this function:

Definition at line 2336 of file mpi.c.

{
  mp_err res;
  mp_size k;
  mp_int oddFactor, evenFactor;    /* factors of the modulus */
  mp_int oddPart, evenPart; /* parts to combine via CRT. */
  mp_int C2, tmp1, tmp2;

  /*static const mp_digit d1 = 1; */
  /*static const mp_int one = { MP_ZPOS, 1, 1, (mp_digit *)&d1 }; */

  if ((res = s_mp_ispow2(m)) >= 0) {
    k = res;
    return s_mp_invmod_2d(a, k, c);
  }
  MP_DIGITS(&oddFactor) = 0;
  MP_DIGITS(&evenFactor) = 0;
  MP_DIGITS(&oddPart) = 0;
  MP_DIGITS(&evenPart) = 0;
  MP_DIGITS(&C2)     = 0;
  MP_DIGITS(&tmp1)   = 0;
  MP_DIGITS(&tmp2)   = 0;

  MP_CHECKOK( mp_init_copy(&oddFactor, m) );    /* oddFactor = m */
  MP_CHECKOK( mp_init(&evenFactor) );
  MP_CHECKOK( mp_init(&oddPart) );
  MP_CHECKOK( mp_init(&evenPart) );
  MP_CHECKOK( mp_init(&C2)     );
  MP_CHECKOK( mp_init(&tmp1)   );
  MP_CHECKOK( mp_init(&tmp2)   );

  k = mp_trailing_zeros(m);
  s_mp_div_2d(&oddFactor, k);
  MP_CHECKOK( s_mp_2expt(&evenFactor, k) );

  /* compute a**-1 mod oddFactor. */
  MP_CHECKOK( s_mp_invmod_odd_m(a, &oddFactor, &oddPart) );
  /* compute a**-1 mod evenFactor, where evenFactor == 2**k. */
  MP_CHECKOK( s_mp_invmod_2d(   a,       k,    &evenPart) );

  /* Use Chinese Remainer theorem to compute a**-1 mod m. */
  /* let m1 = oddFactor,  v1 = oddPart, 
   * let m2 = evenFactor, v2 = evenPart.
   */

  /* Compute C2 = m1**-1 mod m2. */
  MP_CHECKOK( s_mp_invmod_2d(&oddFactor, k,    &C2) );

  /* compute u = (v2 - v1)*C2 mod m2 */
  MP_CHECKOK( mp_sub(&evenPart, &oddPart,   &tmp1) );
  MP_CHECKOK( mp_mul(&tmp1,     &C2,        &tmp2) );
  s_mp_mod_2d(&tmp2, k);
  while (MP_SIGN(&tmp2) != MP_ZPOS) {
    MP_CHECKOK( mp_add(&tmp2, &evenFactor, &tmp2) );
  }

  /* compute answer = v1 + u*m1 */
  MP_CHECKOK( mp_mul(&tmp2,     &oddFactor, c) );
  MP_CHECKOK( mp_add(&oddPart,  c,          c) );
  /* not sure this is necessary, but it's low cost if not. */
  MP_CHECKOK( mp_mod(c,         m,          c) );

CLEANUP:
  mp_clear(&oddFactor);
  mp_clear(&evenFactor);
  mp_clear(&oddPart);
  mp_clear(&evenPart);
  mp_clear(&C2);
  mp_clear(&tmp1);
  mp_clear(&tmp2);
  return res;
}

Here is the call graph for this function:

mp_err s_mp_invmod_odd_m ( const mp_int a,
const mp_int m,
mp_int c 
)

Definition at line 2207 of file mpi.c.

{
  int k;
  mp_err  res;
  mp_int  x;

  ARGCHK(a && m && c, MP_BADARG);

  if(mp_cmp_z(a) == 0 || mp_cmp_z(m) == 0)
    return MP_RANGE;
  if (mp_iseven(m))
    return MP_UNDEF;

  MP_DIGITS(&x) = 0;

  if (a == c) {
    if ((res = mp_init_copy(&x, a)) != MP_OKAY)
      return res;
    if (a == m) 
      m = &x;
    a = &x;
  } else if (m == c) {
    if ((res = mp_init_copy(&x, m)) != MP_OKAY)
      return res;
    m = &x;
  } else {
    MP_DIGITS(&x) = 0;
  }

  MP_CHECKOK( s_mp_almost_inverse(a, m, c) );
  k = res;
  MP_CHECKOK( s_mp_fixup_reciprocal(c, m, k, c) );
CLEANUP:
  mp_clear(&x);
  return res;
}

Here is the call graph for this function:

Definition at line 2150 of file mpi.c.

{
  mp_digit T = P;
  T *= 2 - (P * T);
  T *= 2 - (P * T);
  T *= 2 - (P * T);
  T *= 2 - (P * T);
#if !defined(MP_USE_UINT_DIGIT)
  T *= 2 - (P * T);
  T *= 2 - (P * T);
#endif
  return T;
}

Definition at line 4489 of file mpi.c.

{
  mp_digit d;
  int      extra = 0, ix;

  ix = MP_USED(v) - 1;
  d = MP_DIGIT(v, ix); /* most significant digit of v */

  extra = s_mp_ispow2d(d);
  if (extra < 0 || ix == 0)
    return extra;

  while (--ix >= 0) {
    if (DIGIT(v, ix) != 0)
      return -1; /* not a power of two */
    extra += MP_DIGIT_BIT;
  }

  return extra;

} /* end s_mp_ispow2() */

Here is the call graph for this function:

Definition at line 4515 of file mpi.c.

{
  if ((d != 0) && ((d & (d-1)) == 0)) { /* d is a power of 2 */
    int pow = 0;
#if defined (MP_USE_UINT_DIGIT)
    if (d & 0xffff0000U)
      pow += 16;
    if (d & 0xff00ff00U)
      pow += 8;
    if (d & 0xf0f0f0f0U)
      pow += 4;
    if (d & 0xccccccccU)
      pow += 2;
    if (d & 0xaaaaaaaaU)
      pow += 1;
#elif defined(MP_USE_LONG_LONG_DIGIT)
    if (d & 0xffffffff00000000ULL)
      pow += 32;
    if (d & 0xffff0000ffff0000ULL)
      pow += 16;
    if (d & 0xff00ff00ff00ff00ULL)
      pow += 8;
    if (d & 0xf0f0f0f0f0f0f0f0ULL)
      pow += 4;
    if (d & 0xccccccccccccccccULL)
      pow += 2;
    if (d & 0xaaaaaaaaaaaaaaaaULL)
      pow += 1;
#elif defined(MP_USE_LONG_DIGIT)
    if (d & 0xffffffff00000000UL)
      pow += 32;
    if (d & 0xffff0000ffff0000UL)
      pow += 16;
    if (d & 0xff00ff00ff00ff00UL)
      pow += 8;
    if (d & 0xf0f0f0f0f0f0f0f0UL)
      pow += 4;
    if (d & 0xccccccccccccccccUL)
      pow += 2;
    if (d & 0xaaaaaaaaaaaaaaaaUL)
      pow += 1;
#else
#error "unknown type for mp_digit"
#endif
    return pow;
  }
  return -1;

} /* end s_mp_ispow2d() */
mp_err s_mp_lshd ( mp_int mp,
mp_size  p 
)

Definition at line 2943 of file mpi.c.

{
  mp_err  res;
  mp_size pos;
  int     ix;

  if(p == 0)
    return MP_OKAY;

  if (MP_USED(mp) == 1 && MP_DIGIT(mp, 0) == 0)
    return MP_OKAY;

  if((res = s_mp_pad(mp, USED(mp) + p)) != MP_OKAY)
    return res;

  pos = USED(mp) - 1;

  /* Shift all the significant figures over as needed */
  for(ix = pos - p; ix >= 0; ix--) 
    DIGIT(mp, ix + p) = DIGIT(mp, ix);

  /* Fill the bottom digits with zeroes */
  for(ix = 0; ix < p; ix++)
    DIGIT(mp, ix) = 0;

  return MP_OKAY;

} /* end s_mp_lshd() */

Here is the call graph for this function:

void s_mp_mod_2d ( mp_int mp,
mp_digit  d 
)

Definition at line 3113 of file mpi.c.

{
  mp_size  ndig = (d / DIGIT_BIT), nbit = (d % DIGIT_BIT);
  mp_size  ix;
  mp_digit dmask;

  if(ndig >= USED(mp))
    return;

  /* Flush all the bits above 2^d in its digit */
  dmask = ((mp_digit)1 << nbit) - 1;
  DIGIT(mp, ndig) &= dmask;

  /* Flush all digits above the one with 2^d in it */
  for(ix = ndig + 1; ix < USED(mp); ix++)
    DIGIT(mp, ix) = 0;

  s_mp_clamp(mp);

} /* end s_mp_mod_2d() */

Here is the call graph for this function:

mp_err s_mp_mul ( mp_int a,
const mp_int b 
)

Definition at line 3873 of file mpi.c.

{
  return mp_mul(a, b, a);
} /* end s_mp_mul() */

Here is the call graph for this function:

Definition at line 3073 of file mpi.c.

{
  mp_digit *pd;
  int      ix, used;
  mp_digit kin = 0;

  /* Shift digits leftward by 1 bit */
  used = MP_USED(mp);
  pd = MP_DIGITS(mp);
  for (ix = 0; ix < used; ix++) {
    mp_digit d = *pd;
    *pd++ = (d << 1) | kin;
    kin = (d >> (DIGIT_BIT - 1));
  }

  /* Deal with rollover from last digit */
  if (kin) {
    if (ix >= ALLOC(mp)) {
      mp_err res;
      if((res = s_mp_grow(mp, ALLOC(mp) + 1)) != MP_OKAY)
       return res;
    }

    DIGIT(mp, ix) = kin;
    USED(mp) += 1;
  }

  return MP_OKAY;

} /* end s_mp_mul_2() */

Here is the call graph for this function:

mp_err s_mp_mul_2d ( mp_int mp,
mp_digit  d 
)

Definition at line 2980 of file mpi.c.

{
  mp_err   res;
  mp_digit dshift, bshift;
  mp_digit mask;

  ARGCHK(mp != NULL,  MP_BADARG);

  dshift = d / MP_DIGIT_BIT;
  bshift = d % MP_DIGIT_BIT;
  /* bits to be shifted out of the top word */
  mask   = ((mp_digit)~0 << (MP_DIGIT_BIT - bshift)); 
  mask  &= MP_DIGIT(mp, MP_USED(mp) - 1);

  if (MP_OKAY != (res = s_mp_pad(mp, MP_USED(mp) + dshift + (mask != 0) )))
    return res;

  if (dshift && MP_OKAY != (res = s_mp_lshd(mp, dshift)))
    return res;

  if (bshift) { 
    mp_digit *pa = MP_DIGITS(mp);
    mp_digit *alim = pa + MP_USED(mp);
    mp_digit  prev = 0;

    for (pa += dshift; pa < alim; ) {
      mp_digit x = *pa;
      *pa++ = (x << bshift) | prev;
      prev = x >> (DIGIT_BIT - bshift);
    }
  }

  s_mp_clamp(mp);
  return MP_OKAY;
} /* end s_mp_mul_2d() */

Here is the call graph for this function:

mp_err s_mp_mul_d ( mp_int mp,
mp_digit  d 
)

Definition at line 3320 of file mpi.c.

{
  mp_err  res;
  mp_size used;
  int     pow;

  if (!d) {
    mp_zero(a);
    return MP_OKAY;
  }
  if (d == 1)
    return MP_OKAY;
  if (0 <= (pow = s_mp_ispow2d(d))) {
    return s_mp_mul_2d(a, (mp_digit)pow);
  }

  used = MP_USED(a);
  MP_CHECKOK( s_mp_pad(a, used + 1) );

  s_mpv_mul_d(MP_DIGITS(a), used, d, MP_DIGITS(a));

  s_mp_clamp(a);

CLEANUP:
  return res;
  
} /* end s_mp_mul_d() */

Here is the call graph for this function:

mp_err s_mp_mul_mont ( const mp_int a,
const mp_int b,
mp_int c,
mp_mont_modulus mmm 
)

Definition at line 113 of file mpmontg.c.

{
  mp_digit *pb;
  mp_digit m_i;
  mp_err   res;
  mp_size  ib;
  mp_size  useda, usedb;

  ARGCHK(a != NULL && b != NULL && c != NULL, MP_BADARG);

  if (MP_USED(a) < MP_USED(b)) {
    const mp_int *xch = b;  /* switch a and b, to do fewer outer loops */
    b = a;
    a = xch;
  }

  MP_USED(c) = 1; MP_DIGIT(c, 0) = 0;
  ib = MP_USED(a) + MP_MAX(MP_USED(b), MP_USED(&mmm->N)) + 2;
  if((res = s_mp_pad(c, ib)) != MP_OKAY)
    goto CLEANUP;

  useda = MP_USED(a);
  pb = MP_DIGITS(b);
  s_mpv_mul_d(MP_DIGITS(a), useda, *pb++, MP_DIGITS(c));
  s_mp_setz(MP_DIGITS(c) + useda + 1, ib - (useda + 1));
  m_i = MP_DIGIT(c, 0) * mmm->n0prime;
  s_mp_mul_d_add_offset(&mmm->N, m_i, c, 0);

  /* Outer loop:  Digits of b */
  usedb = MP_USED(b);
  for (ib = 1; ib < usedb; ib++) {
    mp_digit b_i    = *pb++;

    /* Inner product:  Digits of a */
    if (b_i)
      s_mpv_mul_d_add_prop(MP_DIGITS(a), useda, b_i, MP_DIGITS(c) + ib);
    m_i = MP_DIGIT(c, ib) * mmm->n0prime;
    s_mp_mul_d_add_offset(&mmm->N, m_i, c, ib);
  }
  if (usedb < MP_USED(&mmm->N)) {
    for (usedb = MP_USED(&mmm->N); ib < usedb; ++ib ) {
      m_i = MP_DIGIT(c, ib) * mmm->n0prime;
      s_mp_mul_d_add_offset(&mmm->N, m_i, c, ib);
    }
  }
  s_mp_clamp(c);
  s_mp_div_2d(c, mmm->b); 
  if (s_mp_cmp(c, &mmm->N) >= 0) {
    MP_CHECKOK( s_mp_sub(c, &mmm->N) );
  }
  res = MP_OKAY;

CLEANUP:
  return res;
}

Here is the call graph for this function:

mp_err s_mp_norm ( mp_int a,
mp_int b,
mp_digit pd 
)

Definition at line 3178 of file mpi.c.

{
  mp_digit  d;
  mp_digit  mask;
  mp_digit  b_msd;
  mp_err    res    = MP_OKAY;

  d = 0;
  mask  = DIGIT_MAX & ~(DIGIT_MAX >> 1);  /* mask is msb of digit */
  b_msd = DIGIT(b, USED(b) - 1);
  while (!(b_msd & mask)) {
    b_msd <<= 1;
    ++d;
  }

  if (d) {
    MP_CHECKOK( s_mp_mul_2d(a, d) );
    MP_CHECKOK( s_mp_mul_2d(b, d) );
  }

  *pd = d;
CLEANUP:
  return res;

} /* end s_mp_norm() */

Here is the call graph for this function:

int s_mp_outlen ( int  bits,
int  r 
)

Definition at line 4648 of file mpi.c.

{
  return (int)((double)bits * LOG_V_2(r) + 1.5) + 1;

} /* end s_mp_outlen() */
mp_err s_mp_pad ( mp_int mp,
mp_size  min 
)

Definition at line 2807 of file mpi.c.

{
  if(min > USED(mp)) {
    mp_err  res;

    /* Make sure there is room to increase precision  */
    if (min > ALLOC(mp)) {
      if ((res = s_mp_grow(mp, min)) != MP_OKAY)
       return res;
    } else {
      s_mp_setz(DIGITS(mp) + USED(mp), min - USED(mp));
    }

    /* Increase precision; should already be 0-filled */
    USED(mp) = min;
  }

  return MP_OKAY;

} /* end s_mp_pad() */

Here is the call graph for this function:

mp_err s_mp_redc ( mp_int T,
mp_mont_modulus mmm 
)

Definition at line 80 of file mpmontg.c.

{
  mp_err res;
  mp_size i;

  i = MP_USED(T) + MP_USED(&mmm->N) + 2;
  MP_CHECKOK( s_mp_pad(T, i) );
  for (i = 0; i < MP_USED(&mmm->N); ++i ) {
    mp_digit m_i = MP_DIGIT(T, i) * mmm->n0prime;
    /* T += N * m_i * (MP_RADIX ** i); */
    MP_CHECKOK( s_mp_mul_d_add_offset(&mmm->N, m_i, T, i) );
  }
  s_mp_clamp(T);

  /* T /= R */
  s_mp_div_2d(T, mmm->b); 

  if ((res = s_mp_cmp(T, &mmm->N)) >= 0) {
    /* T = T - N */
    MP_CHECKOK( s_mp_sub(T, &mmm->N) );
#ifdef DEBUG
    if ((res = mp_cmp(T, &mmm->N)) >= 0) {
      res = MP_UNDEF;
      goto CLEANUP;
    }
#endif
  }
  res = MP_OKAY;
CLEANUP:
  return res;
}

Here is the call graph for this function:

mp_err s_mp_reduce ( mp_int x,
const mp_int m,
const mp_int mu 
)

Definition at line 4365 of file mpi.c.

{
  mp_int   q;
  mp_err   res;

  if((res = mp_init_copy(&q, x)) != MP_OKAY)
    return res;

  s_mp_rshd(&q, USED(m) - 1);  /* q1 = x / b^(k-1)  */
  s_mp_mul(&q, mu);            /* q2 = q1 * mu      */
  s_mp_rshd(&q, USED(m) + 1);  /* q3 = q2 / b^(k+1) */

  /* x = x mod b^(k+1), quick (no division) */
  s_mp_mod_2d(x, DIGIT_BIT * (USED(m) + 1));

  /* q = q * m mod b^(k+1), quick (no division) */
  s_mp_mul(&q, m);
  s_mp_mod_2d(&q, DIGIT_BIT * (USED(m) + 1));

  /* x = x - q */
  if((res = mp_sub(x, &q, x)) != MP_OKAY)
    goto CLEANUP;

  /* If x < 0, add b^(k+1) to it */
  if(mp_cmp_z(x) < 0) {
    mp_set(&q, 1);
    if((res = s_mp_lshd(&q, USED(m) + 1)) != MP_OKAY)
      goto CLEANUP;
    if((res = mp_add(x, &q, x)) != MP_OKAY)
      goto CLEANUP;
  }

  /* Back off if it's too big */
  while(mp_cmp(x, m) >= 0) {
    if((res = s_mp_sub(x, m)) != MP_OKAY)
      break;
  }

 CLEANUP:
  mp_clear(&q);

  return res;

} /* end s_mp_reduce() */

Here is the call graph for this function:

void s_mp_rshd ( mp_int mp,
mp_size  p 
)

Definition at line 3024 of file mpi.c.

{
  mp_size  ix;
  mp_digit *src, *dst;

  if(p == 0)
    return;

  /* Shortcut when all digits are to be shifted off */
  if(p >= USED(mp)) {
    s_mp_setz(DIGITS(mp), ALLOC(mp));
    USED(mp) = 1;
    SIGN(mp) = ZPOS;
    return;
  }

  /* Shift all the significant figures over as needed */
  dst = MP_DIGITS(mp);
  src = dst + p;
  for (ix = USED(mp) - p; ix > 0; ix--)
    *dst++ = *src++;

  MP_USED(mp) -= p;
  /* Fill the top digits with zeroes */
  while (p-- > 0)
    *dst++ = 0;

#if 0
  /* Strip off any leading zeroes    */
  s_mp_clamp(mp);
#endif

} /* end s_mp_rshd() */

Here is the call graph for this function:

void s_mp_setz ( mp_digit dp,
mp_size  count 
)

Definition at line 2834 of file mpi.c.

{
#if MP_MEMSET == 0
  int  ix;

  for(ix = 0; ix < count; ix++)
    dp[ix] = 0;
#else
  memset(dp, 0, count * sizeof(mp_digit));
#endif

} /* end s_mp_setz() */

Here is the call graph for this function:

Definition at line 4166 of file mpi.c.

{
  mp_err   res;
  mp_int   tmp;

  if((res = mp_init_size(&tmp, 2 * USED(a))) != MP_OKAY)
    return res;
  res = mp_sqr(a, &tmp);
  if (res == MP_OKAY) {
    s_mp_exch(&tmp, a);
  }
  mp_clear(&tmp);
  return res;
}

Here is the call graph for this function:

mp_err s_mp_sub ( mp_int a,
const mp_int b 
)

Definition at line 3735 of file mpi.c.

{
  mp_digit *pa, *pb, *limit;
#if !defined(MP_NO_MP_WORD) && !defined(MP_NO_SUB_WORD)
  mp_sword  w = 0;
#else
  mp_digit  d, diff, borrow = 0;
#endif

  /*
    Subtract and propagate borrow.  Up to the precision of b, this
    accounts for the digits of b; after that, we just make sure the
    carries get to the right place.  This saves having to pad b out to
    the precision of a just to make the loops work right...
   */
  pa = MP_DIGITS(a);
  pb = MP_DIGITS(b);
  limit = pb + MP_USED(b);
  while (pb < limit) {
#if !defined(MP_NO_MP_WORD) && !defined(MP_NO_SUB_WORD)
    w = w + *pa - *pb++;
    *pa++ = ACCUM(w);
    w >>= MP_DIGIT_BIT;
#else
    d = *pa;
    diff = d - *pb++;
    d = (diff > d);                       /* detect borrow */
    if (borrow && --diff == MP_DIGIT_MAX)
      ++d;
    *pa++ = diff;
    borrow = d;      
#endif
  }
  limit = MP_DIGITS(a) + MP_USED(a);
#if !defined(MP_NO_MP_WORD) && !defined(MP_NO_SUB_WORD)
  while (w && pa < limit) {
    w = w + *pa;
    *pa++ = ACCUM(w);
    w >>= MP_DIGIT_BIT;
  }
#else
  while (borrow && pa < limit) {
    d = *pa;
    *pa++ = diff = d - borrow;
    borrow = (diff > d);
  }
#endif

  /* Clobber any leading zeroes we created    */
  s_mp_clamp(a);

  /* 
     If there was a borrow out, then |b| > |a| in violation
     of our input invariant.  We've already done the work,
     but we'll at least complain about it...
   */
#if !defined(MP_NO_MP_WORD) && !defined(MP_NO_SUB_WORD)
  return w ? MP_RANGE : MP_OKAY;
#else
  return borrow ? MP_RANGE : MP_OKAY;
#endif
} /* end s_mp_sub() */

Here is the call graph for this function:

mp_err s_mp_sub_3arg ( const mp_int a,
const mp_int b,
mp_int c 
)

Definition at line 3801 of file mpi.c.

{
  mp_digit *pa, *pb, *pc;
#if !defined(MP_NO_MP_WORD) && !defined(MP_NO_SUB_WORD)
  mp_sword  w = 0;
#else
  mp_digit  d, diff, borrow = 0;
#endif
  int       ix, limit;
  mp_err    res;

  MP_SIGN(c) = MP_SIGN(a);

  /* Make sure a has enough precision for the output value */
  if (MP_OKAY != (res = s_mp_pad(c, MP_USED(a))))
    return res;

  /*
    Subtract and propagate borrow.  Up to the precision of b, this
    accounts for the digits of b; after that, we just make sure the
    carries get to the right place.  This saves having to pad b out to
    the precision of a just to make the loops work right...
   */
  pa = MP_DIGITS(a);
  pb = MP_DIGITS(b);
  pc = MP_DIGITS(c);
  limit = MP_USED(b);
  for (ix = 0; ix < limit; ++ix) {
#if !defined(MP_NO_MP_WORD) && !defined(MP_NO_SUB_WORD)
    w = w + *pa++ - *pb++;
    *pc++ = ACCUM(w);
    w >>= MP_DIGIT_BIT;
#else
    d = *pa++;
    diff = d - *pb++;
    d = (diff > d);
    if (borrow && --diff == MP_DIGIT_MAX)
      ++d;
    *pc++ = diff;
    borrow = d;
#endif
  }
  for (limit = MP_USED(a); ix < limit; ++ix) {
#if !defined(MP_NO_MP_WORD) && !defined(MP_NO_SUB_WORD)
    w = w + *pa++;
    *pc++ = ACCUM(w);
    w >>= MP_DIGIT_BIT;
#else
    d = *pa++;
    *pc++ = diff = d - borrow;
    borrow = (diff > d);
#endif
  }

  /* Clobber any leading zeroes we created    */
  MP_USED(c) = ix;
  s_mp_clamp(c);

  /* 
     If there was a borrow out, then |b| > |a| in violation
     of our input invariant.  We've already done the work,
     but we'll at least complain about it...
   */
#if !defined(MP_NO_MP_WORD) && !defined(MP_NO_SUB_WORD)
  return w ? MP_RANGE : MP_OKAY;
#else
  return borrow ? MP_RANGE : MP_OKAY;
#endif
}

Here is the call graph for this function:

mp_err s_mp_sub_d ( mp_int mp,
mp_digit  d 
)

Definition at line 3270 of file mpi.c.

{
#if !defined(MP_NO_MP_WORD) && !defined(MP_NO_SUB_WORD)
  mp_word   w, b = 0;
  mp_size   ix = 1;

  /* Compute initial subtraction    */
  w = (RADIX + (mp_word)DIGIT(mp, 0)) - d;
  b = CARRYOUT(w) ? 0 : 1;
  DIGIT(mp, 0) = ACCUM(w);

  /* Propagate borrows leftward     */
  while(b && ix < USED(mp)) {
    w = (RADIX + (mp_word)DIGIT(mp, ix)) - b;
    b = CARRYOUT(w) ? 0 : 1;
    DIGIT(mp, ix) = ACCUM(w);
    ++ix;
  }

  /* Remove leading zeroes          */
  s_mp_clamp(mp);

  /* If we have a borrow out, it's a violation of the input invariant */
  if(b)
    return MP_RANGE;
  else
    return MP_OKAY;
#else
  mp_digit *pmp = MP_DIGITS(mp);
  mp_digit mp_i, diff, borrow;
  mp_size  used = MP_USED(mp);

  mp_i = *pmp;
  *pmp++ = diff = mp_i - d;
  borrow = (diff > mp_i);
  while (borrow && --used) {
    mp_i = *pmp;
    *pmp++ = diff = mp_i - borrow;
    borrow = (diff > mp_i);
  }
  s_mp_clamp(mp);
  return (borrow && !used) ? MP_RANGE : MP_OKAY;
#endif
} /* end s_mp_sub_d() */

Here is the call graph for this function:

char s_mp_todigit ( mp_digit  val,
int  r,
int  low 
)

Definition at line 4623 of file mpi.c.

{
  char   ch;

  if(val >= r)
    return 0;

  ch = s_dmap_1[val];

  if(r <= 36 && low)
    ch = tolower(ch);

  return ch;

} /* end s_mp_todigit() */

Here is the call graph for this function:

int s_mp_tovalue ( char  ch,
int  r 
)

Definition at line 4581 of file mpi.c.

{
  int    val, xch;
  
  if(r > 36)
    xch = ch;
  else
    xch = toupper(ch);

  if(isdigit(xch))
    val = xch - '0';
  else if(isupper(xch))
    val = xch - 'A' + 10;
  else if(islower(xch))
    val = xch - 'a' + 36;
  else if(xch == '+')
    val = 62;
  else if(xch == '/')
    val = 63;
  else 
    return -1;

  if(val < 0 || val >= r)
    return -1;

  return val;

} /* end s_mp_tovalue() */

Here is the call graph for this function:

Definition at line 789 of file mpcpucache.c.

{
   return 32;
}

Here is the caller graph for this function:

mp_err MPI_ASM_DECL s_mpv_div_2dx1d ( mp_digit  Nhi,
mp_digit  Nlo,
mp_digit  divisor,
mp_digit quot,
mp_digit rem 
)

Definition at line 4126 of file mpi.c.

{
    mp_digit d1, d0, q1, q0;
    mp_digit r1, r0, m;

    d1 = divisor >> MP_HALF_DIGIT_BIT;
    d0 = divisor & MP_HALF_DIGIT_MAX;
    r1 = Nhi % d1;
    q1 = Nhi / d1;
    m = q1 * d0;
    r1 = (r1 << MP_HALF_DIGIT_BIT) | (Nlo >> MP_HALF_DIGIT_BIT);
    if (r1 < m) {
        q1--, r1 += divisor;
        if (r1 >= divisor && r1 < m) {
           q1--, r1 += divisor;
       }
    }
    r1 -= m;
    r0 = r1 % d1;
    q0 = r1 / d1;
    m = q0 * d0;
    r0 = (r0 << MP_HALF_DIGIT_BIT) | (Nlo & MP_HALF_DIGIT_MAX);
    if (r0 < m) {
        q0--, r0 += divisor;
        if (r0 >= divisor && r0 < m) {
           q0--, r0 += divisor;
       }
    }
    if (qp)
       *qp = (q1 << MP_HALF_DIGIT_BIT) | q0;
    if (rp)
       *rp = r0 - m;
    return MP_OKAY;
}

Here is the call graph for this function:

void MPI_ASM_DECL s_mpv_mul_d ( const mp_digit a,
mp_size  a_len,
mp_digit  b,
mp_digit c 
)

Definition at line 3910 of file mpi.c.

{
#if !defined(MP_NO_MP_WORD) && !defined(MP_NO_MUL_WORD)
  mp_digit   d = 0;

  /* Inner product:  Digits of a */
  while (a_len--) {
    mp_word w = ((mp_word)b * *a++) + d;
    *c++ = ACCUM(w);
    d = CARRYOUT(w);
  }
  *c = d;
#else
  mp_digit carry = 0;
  while (a_len--) {
    mp_digit a_i = *a++;
    mp_digit a0b0, a1b1;

    MP_MUL_DxD(a_i, b, a1b1, a0b0);

    a0b0 += carry;
    if (a0b0 < carry)
      ++a1b1;
    *c++ = a0b0;
    carry = a1b1;
  }
  *c = carry;
#endif
}

Here is the call graph for this function:

Definition at line 3941 of file mpi.c.

{
#if !defined(MP_NO_MP_WORD) && !defined(MP_NO_MUL_WORD)
  mp_digit   d = 0;

  /* Inner product:  Digits of a */
  while (a_len--) {
    mp_word w = ((mp_word)b * *a++) + *c + d;
    *c++ = ACCUM(w);
    d = CARRYOUT(w);
  }
  *c = d;
#else
  mp_digit carry = 0;
  while (a_len--) {
    mp_digit a_i = *a++;
    mp_digit a0b0, a1b1;

    MP_MUL_DxD(a_i, b, a1b1, a0b0);

    a0b0 += carry;
    if (a0b0 < carry)
      ++a1b1;
    a0b0 += a_i = *c;
    if (a0b0 < a_i)
      ++a1b1;
    *c++ = a0b0;
    carry = a1b1;
  }
  *c = carry;
#endif
}

Here is the call graph for this function:

Definition at line 3977 of file mpi.c.

{
#if !defined(MP_NO_MP_WORD) && !defined(MP_NO_MUL_WORD)
  mp_digit   d = 0;

  /* Inner product:  Digits of a */
  while (a_len--) {
    mp_word w = ((mp_word)b * *a++) + *c + d;
    *c++ = ACCUM(w);
    d = CARRYOUT(w);
  }

  while (d) {
    mp_word w = (mp_word)*c + d;
    *c++ = ACCUM(w);
    d = CARRYOUT(w);
  }
#else
  mp_digit carry = 0;
  while (a_len--) {
    mp_digit a_i = *a++;
    mp_digit a0b0, a1b1;

    MP_MUL_DxD(a_i, b, a1b1, a0b0);

    a0b0 += carry;
    if (a0b0 < carry)
      ++a1b1;

    a0b0 += a_i = *c;
    if (a0b0 < a_i)
      ++a1b1;

    *c++ = a0b0;
    carry = a1b1;
  }
  while (carry) {
    mp_digit c_i = *c;
    carry += c_i;
    *c++ = carry;
    carry = carry < c_i;
  }
#endif
}

Here is the call graph for this function:

Definition at line 4049 of file mpi.c.

{
#if !defined(MP_NO_MP_WORD) && !defined(MP_NO_MUL_WORD)
  mp_word  w;
  mp_digit d;
  mp_size  ix;

  w  = 0;
#define ADD_SQUARE(n) \
    d = pa[n]; \
    w += (d * (mp_word)d) + ps[2*n]; \
    ps[2*n] = ACCUM(w); \
    w = (w >> DIGIT_BIT) + ps[2*n+1]; \
    ps[2*n+1] = ACCUM(w); \
    w = (w >> DIGIT_BIT)

  for (ix = a_len; ix >= 4; ix -= 4) {
    ADD_SQUARE(0);
    ADD_SQUARE(1);
    ADD_SQUARE(2);
    ADD_SQUARE(3);
    pa += 4;
    ps += 8;
  }
  if (ix) {
    ps += 2*ix;
    pa += ix;
    switch (ix) {
    case 3: ADD_SQUARE(-3); /* FALLTHRU */
    case 2: ADD_SQUARE(-2); /* FALLTHRU */
    case 1: ADD_SQUARE(-1); /* FALLTHRU */
    case 0: break;
    }
  }
  while (w) {
    w += *ps;
    *ps++ = ACCUM(w);
    w = (w >> DIGIT_BIT);
  }
#else
  mp_digit carry = 0;
  while (a_len--) {
    mp_digit a_i = *pa++;
    mp_digit a0a0, a1a1;

    MP_SQR_D(a_i, a1a1, a0a0);

    /* here a1a1 and a0a0 constitute a_i ** 2 */
    a0a0 += carry;
    if (a0a0 < carry)
      ++a1a1;

    /* now add to ps */
    a0a0 += a_i = *ps;
    if (a0a0 < a_i)
      ++a1a1;
    *ps++ = a0a0;
    a1a1 += a_i = *ps;
    carry = (a1a1 < a_i);
    *ps++ = a1a1;
  }
  while (carry) {
    mp_digit s_i = *ps;
    carry += s_i;
    *ps++ = carry;
    carry = carry < s_i;
  }
#endif
}

Here is the call graph for this function:


Variable Documentation

unsigned long mp_allocs

Definition at line 89 of file mpi.c.

unsigned long mp_copies

Definition at line 91 of file mpi.c.

unsigned long mp_frees

Definition at line 90 of file mpi.c.

const float s_logv_2[]

Definition at line 43 of file logtab.h.