divide.cpp

含有多种公开密钥算法、多种块加密、多种数据流加密、多种HASH函数、多种CheckSum校验、多种MAC校验等几十种加密算法的程序

/*************************************************
* Division Algorithm Source File                 *
* (C) 1999-2002 The Botan Project                *
*************************************************/

#include <botan/numthry.h>
#include <botan/mp_core.h>

namespace Botan {

/*************************************************
* Solve x = q * y + r                            *
*************************************************/
void divide(const BigInt& x, const BigInt& y_arg, BigInt& q, BigInt& r)
   {
   BigInt y = y_arg;
   r = x;

   r.set_sign(Positive);
   y.set_sign(Positive);

   modifying_divide(r, y, q);

   if(x.sign() == Negative)
      {
      q.flip_sign();
      if(r.is_nonzero()) { --q; r = y_arg.abs() - r; }
      }
   if(y_arg.sign() == Negative)
      q.flip_sign();
   }

/*************************************************
* Solve x = q * y + r                            *
*************************************************/
void positive_divide(const BigInt& x, const BigInt& y_arg,
                     BigInt& q, BigInt& r)
   {
   BigInt y = y_arg;
   r = x;
   modifying_divide(r, y, q);
   }

/*************************************************
* Solve x = q * y + r                            *
*************************************************/
void modifying_divide(BigInt& x, BigInt& y, BigInt& q)
   {
   if(y.is_zero())
      throw BigInt::DivideByZero();
   if(x.is_negative() || y.is_negative())
      throw Invalid_Argument("Arguments to modifying_divide must be positive");

   s32bit compare = x.cmp(y);
   if(compare == -1) { q = BigInt::zero(); return; }
   if(compare ==  0) { q = BigInt::one(); x = BigInt::zero(); return; }

   u32bit shifts = 0;
   while(y[y.sig_words()-1] < MP_WORD_TOP_BIT)
      { x <<= 1; y <<= 1; shifts++; }

   x.shrink();
   y.shrink();

   u32bit n = x.size() - 1, t = y.size() - 1;
   q.reg.create(n - t + 1);
   if(n <= t)
      {
      while(x > y) { x -= y; q.add(1); }
      x >>= shifts;
      return;
      }

   BigInt temp = y << (MP_WORD_BITS * (n-t));

   while(x >= temp) { x -= temp; q[n-t]++; }

   for(u32bit j = n; j != t; j--)
      {
      const u32bit x_j = x.word_at(j);
      const u32bit x_j1 = x.word_at(j-1);
      const u32bit y_t = y.word_at(t);

      if(x_j == y_t)
         q[j-t-1] = MP_WORD_MAX;
      else
         q[j-t-1] = (((dword)x_j << MP_WORD_BITS) | x_j1) / y_t;

      while(bigint_divcore(q[j-t-1], y_t, y.word_at(t-1),
                           x_j, x_j1, x.word_at(j-2)))
         q[j-t-1]--;

      x -= (q[j-t-1] * y) << (MP_WORD_BITS * (j-t-1));
      if(x.is_negative())
         {
         x += y << (MP_WORD_BITS * (j-t-1));
         q[j-t-1]--;
         }
      }
   x >>= shifts;
   }

}