mpi.c

支持SSL v2/v3, TLS, PKCS #5, PKCS #7, PKCS #11, PKCS #12, S/MIME, X.509v3证书等安全协议或标准的开发库编译用到NSPR

    /* Save sign for later, and take absolute value */
    sgn = SIGN(&tmp); SIGN(&tmp) = ZPOS;

    /* Generate output digits in reverse order      */
    while(mp_cmp_z(&tmp) != 0) {
      if((res = mp_div_d(&tmp, rdx, &tmp, &rem)) != MP_OKAY) {
	mp_clear(&tmp);
	return res;
      }

      /* Generate digits, use capital letters */
      ch = s_mp_todigit(rem, radix, 0);

      str[pos++] = ch;
    }

    /* Add - sign if original value was negative */
    if(sgn == NEG)
      str[pos++] = '-';

    /* Add trailing NUL to end the string        */
    str[pos--] = '\0';

    /* Reverse the digits and sign indicator     */
    ix = 0;
    while(ix < pos) {
      char tmp = str[ix];

      str[ix] = str[pos];
      str[pos] = tmp;
      ++ix;
      --pos;
    }
    
    mp_clear(&tmp);
  }

  return MP_OKAY;

} /* end mp_toradix() */

/* }}} */

/* {{{ mp_tovalue(ch, r) */

int    mp_tovalue(char ch, int r)
{
  return s_mp_tovalue(ch, r);

} /* end mp_tovalue() */

/* }}} */

/* }}} */

/* {{{ mp_strerror(ec) */

/*
  mp_strerror(ec)

  Return a string describing the meaning of error code 'ec'.  The
  string returned is allocated in static memory, so the caller should
  not attempt to modify or free the memory associated with this
  string.
 */
const char  *mp_strerror(mp_err ec)
{
  int   aec = (ec < 0) ? -ec : ec;

  /* Code values are negative, so the senses of these comparisons
     are accurate */
  if(ec < MP_LAST_CODE || ec > MP_OKAY) {
    return mp_err_string[0];  /* unknown error code */
  } else {
    return mp_err_string[aec + 1];
  }

} /* end mp_strerror() */

/* }}} */

/*========================================================================*/
/*------------------------------------------------------------------------*/
/* Static function definitions (internal use only)                        */

/* {{{ Memory management */

/* {{{ s_mp_grow(mp, min) */

/* Make sure there are at least 'min' digits allocated to mp              */
mp_err   s_mp_grow(mp_int *mp, mp_size min)
{
  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() */

/* }}} */

/* {{{ s_mp_pad(mp, min) */

/* Make sure the used size of mp is at least 'min', growing if needed     */
mp_err   s_mp_pad(mp_int *mp, mp_size min)
{
  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() */

/* }}} */

/* {{{ s_mp_setz(dp, count) */

#if MP_MACRO == 0
/* Set 'count' digits pointed to by dp to be zeroes                       */
void s_mp_setz(mp_digit *dp, mp_size count)
{
#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() */
#endif

/* }}} */

/* {{{ s_mp_copy(sp, dp, count) */

#if MP_MACRO == 0
/* Copy 'count' digits from sp to dp                                      */
void s_mp_copy(const mp_digit *sp, mp_digit *dp, mp_size count)
{
#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() */
#endif

/* }}} */

/* {{{ s_mp_alloc(nb, ni) */

#if MP_MACRO == 0
/* Allocate ni records of nb bytes each, and return a pointer to that     */
void    *s_mp_alloc(size_t nb, size_t ni)
{
  ++mp_allocs;
  return calloc(nb, ni);

} /* end s_mp_alloc() */
#endif

/* }}} */

/* {{{ s_mp_free(ptr) */

#if MP_MACRO == 0
/* Free the memory pointed to by ptr                                      */
void     s_mp_free(void *ptr)
{
  if(ptr) {
    ++mp_frees;
    free(ptr);
  }
} /* end s_mp_free() */
#endif

/* }}} */

/* {{{ s_mp_clamp(mp) */

#if MP_MACRO == 0
/* Remove leading zeroes from the given value                             */
void     s_mp_clamp(mp_int *mp)
{
  mp_size used = MP_USED(mp);
  while (used > 1 && DIGIT(mp, used - 1) == 0)
    --used;
  MP_USED(mp) = used;
} /* end s_mp_clamp() */
#endif

/* }}} */

/* {{{ s_mp_exch(a, b) */

/* Exchange the data for a and b; (b, a) = (a, b)                         */
void     s_mp_exch(mp_int *a, mp_int *b)
{
  mp_int   tmp;

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

} /* end s_mp_exch() */

/* }}} */

/* }}} */

/* {{{ Arithmetic helpers */

/* {{{ s_mp_lshd(mp, p) */

/* 
   Shift mp leftward by p digits, growing if needed, and zero-filling
   the in-shifted digits at the right end.  This is a convenient
   alternative to multiplication by powers of the radix
   The value of USED(mp) must already have been set to the value for
   the shifted result.
 */   

mp_err   s_mp_lshd(mp_int *mp, mp_size p)
{
  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() */

/* }}} */

/* {{{ s_mp_mul_2d(mp, d) */

/*
  Multiply the integer by 2^d, where d is a number of bits.  This
  amounts to a bitwise shift of the value.
 */
mp_err   s_mp_mul_2d(mp_int *mp, mp_digit d)
{
  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() */

/* {{{ s_mp_rshd(mp, p) */

/* 
   Shift mp rightward by p digits.  Maintains the invariant that
   digits above the precision are all zero.  Digits shifted off the
   end are lost.  Cannot fail.
 */

void     s_mp_rshd(mp_int *mp, mp_size p)
{
  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() */

/* }}} */

/* {{{ s_mp_div_2(mp) */

/* Divide by two -- take advantage of radix properties to do it fast      */
void     s_mp_div_2(mp_int *mp)
{
  s_mp_div_2d(mp, 1);

} /* end s_mp_div_2() */

/* }}} */

/* {{{ s_mp_mul_2(mp) */

mp_err s_mp_mul_2(mp_int *mp)
{
  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() */

/* }}} */

/* {{{ s_mp_mod_2d(mp, d) */

/*
  Remainder the integer by 2^d, where d is a number of bits.  This
  amounts to a bitwise AND of the value, and does not require the full
  division code
 */
void     s_mp_mod_2d(mp_int *mp, mp_digit d)
{
  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() */

/* }}} */

/* {{{ s_mp_div_2d(mp, d) */

/*
  Divide the integer by 2^d, where d is a number of bits.  This
  amounts to a bitwise shift of the value, and does not require the
  full division code (used in Barrett reduction, see below)
 */
void     s_mp_div_2d(mp_int *mp, mp_digit d)
{
  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() */

/* }}} */

/* {{{ s_mp_norm(a, b, *d) */

/*
  s_mp_norm(a, b, *d)

  Normalize a and b for division, where b is the divisor.  In order
  that we might make good guesses for quotient digits, we want the
  leading digit of b to be at least half the radix, which we
  accomplish by multiplying a and b by a power of 2.  The exponent 
  (shift count) is placed in *pd, so that the remainder can be shifted 
  back at the end of the division process.
 */

mp_err   s_mp_norm(mp_int *a, mp_int *b, mp_digit *pd)
{
  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() */

/* }}} */

/* }}} */

/* {{{ Primitive digit arithmetic */

/* {{{ s_mp_add_d(mp, d) */

/* Add d to |mp| in place                                                 */
mp_err   s_mp_add_d(mp_int *mp, mp_digit d)    /* unsigned digit addition */
{
#if !defined(MP_NO_MP_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() */

/* }}} */

/* {{{ s_mp_sub_d(mp, d) */

/* Subtract d from |mp| in place, assumes |mp| > d                        */
mp_err   s_mp_sub_d(mp_int *mp, mp_digit d)    /* unsigned digit subtract */
{
#if !defined(MP_NO_MP_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() */

/* }}} */

/* {{{ s_mp_mul_d(a, d) */

/* Compute a = a * d, single digit multiplication                         */
mp_err   s_mp_mul_d(mp_int *a, mp_digit d)
{
  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