flint.c

用扩展欧拉法求逆元 rsa算法的必须组成函数模块 带对话框

      ISPURGED_L  ((2, sizeof (b_l), b_l,
                       sizeof (r_l), r_l));
      return E_CLINT_OK;
    }
  else if (i == 0)
    {
      SETONE_L (quot_l);
      SETZERO_L (rem_l);

      PURGEVARS_L ((2, sizeof (b_l), b_l,
                       sizeof (r_l), r_l));
      ISPURGED_L  ((2, sizeof (b_l), b_l,
                       sizeof (r_l), r_l));
      return E_CLINT_OK;
    }

  if (DIGITS_L (b_l) == 1)
    {
      goto shortdiv;
    }

  /* Step 1 */
  msdptrb_l = MSDPTR_L (b_l);

  bn = *msdptrb_l;
  while (bn < BASEDIV2)
    {
      d++;
      bn <<= 1;
    }

  sbitsminusd = (int)BITPERDGT - d;

  if (d > 0)
    {
      bn += *(msdptrb_l - 1) >> sbitsminusd;

      if (DIGITS_L (b_l) > 2)
        {
          bn_1 = (USHORT)((*(msdptrb_l - 1) << d) + (*(msdptrb_l - 2) >> sbitsminusd));
        }
      else
        {
          bn_1 = (USHORT)(*(msdptrb_l - 1) << d);
        }
    }
  else
    {
      bn_1 = (USHORT)(*(msdptrb_l - 1));
    }

  /* Steps 2 and 3 */
  msdptrr_l = MSDPTR_L (r_l) + 1;
  lsdptrr_l = MSDPTR_L (r_l) - DIGITS_L (b_l) + 1;
  *msdptrr_l = 0;

  qptr_l = quot_l + DIGITS_L (r_l) - DIGITS_L (b_l) + 1;

  /* Step 4 */
  while (lsdptrr_l >= LSDPTR_L (r_l))
    {
      ri = (USHORT)((*msdptrr_l << d) + (*(msdptrr_l - 1) >> sbitsminusd));

      ri_1 = (USHORT)((*(msdptrr_l - 1) << d) + (*(msdptrr_l - 2) >> sbitsminusd));

      if (msdptrr_l - 3 > r_l)
        {
          ri_2 = (USHORT)((*(msdptrr_l - 2) << d) + (*(msdptrr_l - 3) >> sbitsminusd));
        }
      else
        {
          ri_2 = (USHORT)(*(msdptrr_l - 2) << d);
        }

      if (ri != bn)               /* almost always */
        {
          qhat = (USHORT)((rhat = ((ULONG)ri << BITPERDGT) + (ULONG)ri_1) / bn);
          right = ((rhat = (rhat - (ULONG)bn * qhat)) << BITPERDGT) + ri_2;

          /* test qhat */

          if ((left = (ULONG)bn_1 * qhat) > right)
            {
              qhat--;
              if ((rhat + bn) < BASE)
                  /* else bn_1 * qhat < rhat * b_l */
                {
                  if ((left - bn_1) > (right + ((ULONG)bn << BITPERDGT)))
                    {
                      qhat--;
                    }
                }
            }
        }
      else                        /* ri == bn, almost never */
        {
          qhat = BASEMINONE;
          right = ((ULONG)(rhat = (ULONG)bn + (ULONG)ri_1) << BITPERDGT) + ri_2;
          if (rhat < BASE)       /* else bn_1 * qhat < rhat * b_l */
            {
              /* test qhat */

              if ((left = (ULONG)bn_1 * qhat) > right)
                {
                  qhat--;
                  if ((rhat + bn) < BASE)
                      /* else bn_1 * qhat < rhat * b_l */
                    {
                      if ((left - bn_1) > (right + ((ULONG)bn << BITPERDGT)))
                        {
                          qhat--;
                        }
                    }
                }
            }
        }

      /* Step 5 */
      borrow = BASE;
      carry = 0;
      for (bptr_l = LSDPTR_L (b_l), rptr_l = lsdptrr_l; bptr_l <= msdptrb_l; bptr_l++, rptr_l++)
        {
          if (borrow >= BASE)
            {
              *rptr_l = (USHORT)(borrow = ((ULONG)(*rptr_l) + BASE -
                         (ULONG)(USHORT)(carry = (ULONG)(*bptr_l) *
                         qhat + (ULONG)(USHORT)(carry >> BITPERDGT))));
            }
          else
            {
              *rptr_l = (USHORT)(borrow = ((ULONG)(*rptr_l) + BASEMINONEL -
                                (ULONG)(USHORT)(carry = (ULONG)(*bptr_l) *
                                qhat + (ULONG)(USHORT)(carry >> BITPERDGT))));
            }
        }

      if (borrow >= BASE)
        {
          *rptr_l = (USHORT)(borrow = ((ULONG)(*rptr_l) + BASE -
                             (ULONG)(USHORT)(carry >> BITPERDGT)));
        }
      else
        {
          *rptr_l = (USHORT)(borrow = ((ULONG)(*rptr_l) + BASEMINONEL -
                                    (ULONG)(USHORT)(carry >> BITPERDGT)));
        }

      /* Step 6 */
      *qptr_l = qhat;

      if (borrow < BASE)
        {
          carry = 0;
          for (bptr_l = LSDPTR_L (b_l), rptr_l = lsdptrr_l; bptr_l <= msdptrb_l; bptr_l++, rptr_l++)
            {
              *rptr_l = (USHORT)(carry = ((ULONG)(*rptr_l) + (ULONG)(*bptr_l) +
                                          (ULONG)(USHORT)(carry >> BITPERDGT)));
            }
          *rptr_l += (USHORT)(carry >> BITPERDGT);
          (*qptr_l)--;
        }

      /* Step 7 */
      msdptrr_l--;
      lsdptrr_l--;
      qptr_l--;
    }

  /* Step 8 */
  SETDIGITS_L (quot_l, DIGITS_L (r_l) - DIGITS_L (b_l) + 1);
  RMLDZRS_L (quot_l);

  SETDIGITS_L (r_l, DIGITS_L (b_l));
  cpy_l (rem_l, r_l);

  /* Purging of variables */
  PURGEVARS_L ((17, sizeof (bv), &bv,
                    sizeof (rv), &rv,
                    sizeof (qhat), &qhat,
                    sizeof (ri), &ri,
                    sizeof (ri_1), &ri_1,
                    sizeof (ri_2), &ri_2,
                    sizeof (bn), &bn,
                    sizeof (bn_1), &bn_1,
                    sizeof (right), &right,
                    sizeof (left), &left,
                    sizeof (rhat), &rhat,
                    sizeof (borrow), &borrow,
                    sizeof (carry), &carry,
                    sizeof (sbitsminusd), &sbitsminusd,
                    sizeof (d), &d,
                    sizeof (b_l), b_l,
                    sizeof (r_l), r_l));

  ISPURGED_L  ((17, sizeof (bv), &bv,
                    sizeof (rv), &rv,
                    sizeof (qhat), &qhat,
                    sizeof (ri), &ri,
                    sizeof (ri_1), &ri_1,
                    sizeof (ri_2), &ri_2,
                    sizeof (bn), &bn,
                    sizeof (bn_1), &bn_1,
                    sizeof (right), &right,
                    sizeof (left), &left,
                    sizeof (rhat), &rhat,
                    sizeof (borrow), &borrow,
                    sizeof (carry), &carry,
                    sizeof (sbitsminusd), &sbitsminusd,
                    sizeof (d), &d,
                    sizeof (b_l), b_l,
                    sizeof (r_l), r_l));

  return E_CLINT_OK;

  /* Division by divisor with one-digit */
  shortdiv:

  rv = 0;
  bv = *LSDPTR_L (b_l);
  for (rptr_l = MSDPTR_L (r_l), qptr_l = quot_l + DIGITS_L (r_l); rptr_l >= LSDPTR_L (r_l); rptr_l--, qptr_l--)
    {
      *qptr_l = (USHORT)((rhat = ((((ULONG)rv) << BITPERDGT) +
                                          (ULONG)*rptr_l)) / bv);
      rv = (USHORT)(rhat - (ULONG)bv * (ULONG)*qptr_l);
    }

  SETDIGITS_L (quot_l, DIGITS_L (r_l));

  RMLDZRS_L (quot_l);
  u2clint_l (rem_l, rv);

  /* Purging of variables */
  PURGEVARS_L ((4, sizeof (rv), &rv,
                   sizeof (bv), &bv,
                   sizeof (b_l), b_l,
                   sizeof (r_l), r_l));

  ISPURGED_L  ((4, sizeof (rv), &rv,
                   sizeof (bv), &bv,
                   sizeof (b_l), b_l,
                   sizeof (r_l), r_l));

  return E_CLINT_OK;
}
#endif /* FLINT_ASM */


/******************************************************************************/
/*                                                                            */
/*  Function:  Binary rightshift by 1 bit                                     */
/*  Syntax:    int shr_l (CLINT a_l);                                         */
/*  Input:     a_l (Operand)                                                  */
/*  Output:    a_l (Shifted value)                                            */
/*  Returns:   E_CLINT_OK : Everything O.K.                                   */
/*             E_CLINT_UFL: Underflow                                         */
/*                                                                            */
/******************************************************************************/
int __FLINT_API
shr_l (CLINT a_l)
{
  clint *ap_l;
  USHORT help, carry = 0;

  if (DIGITS_L (a_l) == 0)
    {
      return E_CLINT_UFL;          /* Underflow */
    }

  for (ap_l = MSDPTR_L (a_l); ap_l > a_l; ap_l--)
    {
      help = (USHORT)((USHORT)(*ap_l >> 1) | (USHORT)(carry << (BITPERDGT - 1)));
      carry = (USHORT)(*ap_l & 1U);
      *ap_l = help;
    }

  RMLDZRS_L (a_l);

  /* Purging of variables */
  PURGEVARS_L ((2, sizeof (help), &help,
                   sizeof (carry), &carry));

  ISPURGED_L  ((2, sizeof (help), &help,
                   sizeof (carry), &carry));

  return E_CLINT_OK;
}


/******************************************************************************/
/*                                                                            */
/*  Function:  Binary leftshift by 1 bit                                      */
/*  Syntax:    int shl_l (CLINT a_l);                                         */
/*  Input:     a_l (Operand)                                                  */
/*  Output:    a_l (Shifted value)                                            */
/*  Returns:   E_CLINT_OK : Everything O.K.                                   */
/*             E_CLINT_OFL: Overflow                                          */
/*                                                                            */
/******************************************************************************/
int __FLINT_API
shl_l (CLINT a_l)
{
  clint *ap_l, *msdptra_l;
  ULONG carry = 0L;
  int error = E_CLINT_OK;

  RMLDZRS_L (a_l);
  if (ld_l (a_l) >= (USHORT)CLINTMAXBIT)
    {
      SETDIGITS_L (a_l, CLINTMAXDIGIT);
      error = E_CLINT_OFL;         /* Overflow */
    }

  msdptra_l = MSDPTR_L (a_l);
  for (ap_l = LSDPTR_L (a_l); ap_l <= msdptra_l; ap_l++)
    {
      *ap_l = (USHORT)(carry = ((ULONG)(*ap_l) << 1) | (carry >> BITPERDGT));
    }

  if (carry >> BITPERDGT)
    {
      if (DIGITS_L (a_l) < CLINTMAXDIGIT)
        {
          *ap_l = 1;
          INCDIGITS_L (a_l);
          error = E_CLINT_OK;
        }
      else
        {
          error = E_CLINT_OFL;
        }
    }

  RMLDZRS_L (a_l);

  /* Purging of variables */
  PURGEVARS_L ((1, sizeof (carry), &carry));
  ISPURGED_L  ((1, sizeof (carry), &carry));

  return error;
}


/******************************************************************************/
/*                                                                            */
/*  Function:  Binary left-/rightshift by n bits                              */
/*  Syntax:    int shift_l (CLINT n_l, long int noofbits);                    */
/*  Input:     n_l (Operand)                                                  */
/*             noofbits (Number of places to be shifted)                      */
/*             negative sign: Shift right                                     */
/*             positive sign: Shift left                                      */
/*  Output:    a_l (Shifted value)                                            */
/*  Returns:   E_CLINT_OK : Everything O.K.                                   */
/*             E_CLINT_OFL: Overflow                                          */
/*             E_CLINT_UFL: Underflow                                         */
/*                                                                            */
/******************************************************************************/
int __FLINT_API
shift_l (CLINT n_l, long int noofbits)
{
  USHORT shorts = (USHORT)((ULONG)(noofbits < 0 ? -noofbits : noofbits) / BITPERDGT);
  USHORT bits = (USHORT)((ULONG)(noofbits < 0 ? -noofbits : noofbits) % BITPERDGT);
  long int resl;
  USHORT i;
  int error = E_CLINT_OK;

  clint *nptr_l;
  clint *msdptrn_l;

  RMLDZRS_L (n_l);
  resl = (int)ld_l (n_l) + noofbits;

  if (DIGITS_L (n_l) == 0)
    {
      shorts = bits = 0;
      return ((resl < 0) ? E_CLINT_UFL : E_CLINT_OK);
    }

  if (noofbits == 0)
    {