Botan  1.11.15
src/lib/math/mp/mp_mulop.cpp
Go to the documentation of this file.
00001 /*
00002 * Simple O(N^2) Multiplication and Squaring
00003 * (C) 1999-2008 Jack Lloyd
00004 *
00005 * Botan is released under the Simplified BSD License (see license.txt)
00006 */
00007 
00008 #include <botan/internal/mp_core.h>
00009 #include <botan/internal/mp_madd.h>
00010 #include <botan/internal/mp_asmi.h>
00011 #include <botan/mem_ops.h>
00012 
00013 namespace Botan {
00014 
00015 extern "C" {
00016 
00017 /*
00018 * Simple O(N^2) Multiplication
00019 */
00020 void bigint_simple_mul(word z[], const word x[], size_t x_size,
00021                                  const word y[], size_t y_size)
00022    {
00023    const size_t x_size_8 = x_size - (x_size % 8);
00024 
00025    clear_mem(z, x_size + y_size);
00026 
00027    for(size_t i = 0; i != y_size; ++i)
00028       {
00029       const word y_i = y[i];
00030 
00031       word carry = 0;
00032 
00033       for(size_t j = 0; j != x_size_8; j += 8)
00034          carry = word8_madd3(z + i + j, x + j, y_i, carry);
00035 
00036       for(size_t j = x_size_8; j != x_size; ++j)
00037          z[i+j] = word_madd3(x[j], y_i, z[i+j], &carry);
00038 
00039       z[x_size+i] = carry;
00040       }
00041    }
00042 
00043 /*
00044 * Simple O(N^2) Squaring
00045 *
00046 * This is exactly the same algorithm as bigint_simple_mul, however
00047 * because C/C++ compilers suck at alias analysis it is good to have
00048 * the version where the compiler knows that x == y
00049 *
00050 * There is an O(n^1.5) squaring algorithm specified in Handbook of
00051 * Applied Cryptography, chapter 14
00052 *
00053 */
00054 void bigint_simple_sqr(word z[], const word x[], size_t x_size)
00055    {
00056    const size_t x_size_8 = x_size - (x_size % 8);
00057 
00058    clear_mem(z, 2*x_size);
00059 
00060    for(size_t i = 0; i != x_size; ++i)
00061       {
00062       const word x_i = x[i];
00063       word carry = 0;
00064 
00065       for(size_t j = 0; j != x_size_8; j += 8)
00066          carry = word8_madd3(z + i + j, x + j, x_i, carry);
00067 
00068       for(size_t j = x_size_8; j != x_size; ++j)
00069          z[i+j] = word_madd3(x[j], x_i, z[i+j], &carry);
00070 
00071       z[x_size+i] = carry;
00072       }
00073    }
00074 
00075 }
00076 
00077 }