mp_mul.cpp

来自「含有多种公开密钥算法、多种块加密、多种数据流加密、多种HASH函数、多种Chec」· C++ 代码 · 共 77 行

/*************************************************
* MP Multiplication Source File                  *
* (C) 1999-2002 The Botan Project                *
*************************************************/

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

namespace Botan {

namespace {

/*************************************************
* Simple O(N^2) Multiplication                   *
*************************************************/
void simple_multiply(word* const z,
                     const word* x, u32bit x_size,
                     const word* y, u32bit y_size)
   {
   for(u32bit j = 0; j != x_size; j++)
       {
      word carry = 0, x_j = x[j];
      for(u32bit k = 0; k != y_size; k++)
         {
         dword product = (dword)z[j+k] + (dword)x_j * y[k] + carry;
         z[j+k] = MP_LOW_WORD(product);
         carry = MP_HIGH_WORD(product);
         }
      z[j+y_size] = carry;
      }
   }

/*************************************************
* Length Checking                                *
*************************************************/
bool use_operation(u32bit x_sw, u32bit y_sw, u32bit x_size, u32bit y_size,
                   u32bit limit, u32bit min = 0)
   {
   return (x_sw <= limit && y_sw <= limit &&
           x_size >= limit && y_size >= limit &&
           (x_sw + y_sw) >= min);
   }

}

/*************************************************
* MP Multiplication                              *
*************************************************/
void bigint_mul3(word* const z, u32bit,
                 const word* x, u32bit x_size, u32bit x_sw,
                 const word* y, u32bit y_size, u32bit y_sw)
   {
   static const u32bit KARATSUBA_16_BOUND = 24;
   static const u32bit KARATSUBA_32_BOUND = 48;
   static const u32bit KARATSUBA_64_BOUND = 96;
   static const u32bit KARATSUBA_128_BOUND = 192;

   if(x_size < 4 || y_size < 4)
      simple_multiply(z, x, x_sw, y, y_sw);
   else if(use_operation(x_sw, y_sw, x_size, y_size, 4))
      bigint_comba4(z, x, y);
   else if(use_operation(x_sw, y_sw, x_size, y_size, 8))
      bigint_comba8(z, x, y);
   else if(use_operation(x_sw, y_sw, x_size, y_size, 16, KARATSUBA_16_BOUND))
      bigint_karat16(z, x, y);
   else if(use_operation(x_sw, y_sw, x_size, y_size, 32, KARATSUBA_32_BOUND))
      bigint_karat32(z, x, y);
   else if(use_operation(x_sw, y_sw, x_size, y_size, 64, KARATSUBA_64_BOUND))
      bigint_karat64(z, x, y);
   else if(use_operation(x_sw, y_sw, x_size, y_size, 128, KARATSUBA_128_BOUND))
      bigint_karat128(z, x, y);
   else
      simple_multiply(z, x, x_sw, y, y_sw);
   }

}