/Users/mourrain/Devel/mmx/algebramix/src/kronecker_int.cpp

Go to the documentation of this file.

/******************************************************************************
* MODULE     : kronecker_int.cpp
* DESCRIPTION: Breaking big integers into hardware parts and recomposing them
* COPYRIGHT  : (C) 2009  Gregoire Lecerf
*******************************************************************************
* This software falls under the GNU general public license and comes WITHOUT
* ANY WARRANTY WHATSOEVER. See the file $TEXMACS_PATH/LICENSE for more details.
* If you don't have this file, write to the Free Software Foundation, Inc.,
* 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
******************************************************************************/

#include <numerix/integer.hpp>
namespace mmx {

/******************************************************************************
* Naive encoding and decoding of integer polynomials using Kronecker's method
******************************************************************************/

#if !defined(__GNU_MP__)
template<typename I> static inline void
encode_kronecker_int (integer& dest, const I* src, nat n, xnat bits) {
  if (n == 0) dest= 0;
  else if (n == 1) dest= src[0];
  else {
    nat h= n>>1;
    integer aux;
    encode_kronecker_int (aux , src+h, n-h, bits);
    encode_kronecker_int (dest, src  , h  , bits);
    dest += (aux << (h*bits));
  }
}

#define IMPLEMENTATION_HELPER(I)                                        \
  void                                                                  \
  encode_kronecker (integer& dest, const I* src, nat n, xnat bits) {    \
    encode_kronecker_int (dest, src, n, bits); }
IMPLEMENTATION_HELPER (unsigned char)
IMPLEMENTATION_HELPER (unsigned short)
IMPLEMENTATION_HELPER (unsigned int)
IMPLEMENTATION_HELPER (unsigned long int)
IMPLEMENTATION_HELPER (unsigned long long int)
IMPLEMENTATION_HELPER (signed char)
IMPLEMENTATION_HELPER (short int)
IMPLEMENTATION_HELPER (int)
IMPLEMENTATION_HELPER (long int)
IMPLEMENTATION_HELPER (long long int)
#undef IMPLEMENTATION_HELPER

template<typename I> static inline void
decode_kronecker_int (I* dest, nat n, xnat bits, const integer& src) {
  static const integer mask= (integer (1) << (8 * sizeof (I))) - 1;
  if (n == 0);
  else if (n == 1) 
    dest[0]= src > 0 ? as<I> (src & mask) : - as<I> ((-src) & mask);
  else if (src > 0) {
    nat h= n>>1;
    integer aux= src >> (h*bits);
    if (src[h*bits-1]) aux += 1;
    decode_kronecker (dest+h, n-h, bits, aux);
    aux= src - (aux << (h*bits));
    decode_kronecker (dest, h, bits, aux);
  }
  else {
    integer bis= -src;
    nat h= n>>1;
    integer aux= bis >> (h*bits);
    if (bis[h*bits-1]) aux += 1;
    decode_kronecker (dest+h, n-h, bits, -aux);
    aux= bis - (aux << (h*bits));
    decode_kronecker (dest, h, bits, -aux);
  }
}

template<typename I> static inline void
decode_kronecker_uint (I* dest, nat n, xnat bits, const integer& src) {
  if (n == 0);
  else if (n == 1) dest[0]= as<I> (src);
  else {
    nat h= n>>1;
    integer aux= src >> (h*bits);
    decode_kronecker_int (dest+h, n-h, bits, aux);
    aux= src - (aux << (h*bits));
    decode_kronecker_int (dest, h, bits, aux);
  }
}

#define IMPLEMENTATION_HELPER(I)                                        \
  void                                                                  \
  decode_kronecker (I* dest, nat n, xnat bits, const integer& src) {    \
    decode_kronecker_uint (dest, n, bits, src); }
IMPLEMENTATION_HELPER (unsigned char)
IMPLEMENTATION_HELPER (unsigned short int)
IMPLEMENTATION_HELPER (unsigned int)
IMPLEMENTATION_HELPER (unsigned long int)
IMPLEMENTATION_HELPER (unsigned long long int)
#undef IMPLEMENTATION_HELPER

#define IMPLEMENTATION_HELPER(I)                                        \
  void                                                                  \
  decode_kronecker (I* dest, nat n, xnat bits, const integer& src) {    \
    decode_kronecker_int (dest, n, bits, src); }
IMPLEMENTATION_HELPER (signed char)
IMPLEMENTATION_HELPER (short int)
IMPLEMENTATION_HELPER (int)
IMPLEMENTATION_HELPER (long int)
IMPLEMENTATION_HELPER (long long int)
#undef IMPLEMENTATION_HELPER

#else
/******************************************************************************
* Specific implementation for GMP
******************************************************************************/

// from polynomial_gmp.cpp
#define DECLARE_HELPER(I)                                               \
  void mpz_encode_kronecker (mpz_t dest, const I* src,                  \
                             unsigned long n, unsigned long bits);      \
  void mpz_decode_kronecker (I* dest, unsigned long n,                  \
                             unsigned long bits, const mpz_t src);
DECLARE_HELPER(unsigned char)
DECLARE_HELPER(unsigned short)
DECLARE_HELPER(unsigned int)
DECLARE_HELPER(unsigned long int)
DECLARE_HELPER(unsigned long long int)
#undef DECLARE_HELPER

#define IMPLEMENTATION_HELPER(I)                                        \
  void encode_kronecker (integer& dest,                                 \
                         const I* src, nat n, xnat bits) {              \
    typedef unsigned_of_helper<I>::type U;                              \
    mpz_encode_kronecker (*dest, (const U*) (const I*) src,             \
                          (unsigned long) n,                            \
                          (unsigned long) bits); }                      \
  void decode_kronecker (I* dest, nat n, xnat bits,                     \
                         const integer& src) {                          \
    typedef unsigned_of_helper<I>::type U;                              \
    mpz_decode_kronecker ((U*) (void*) dest, (unsigned long) n,         \
                          (unsigned long) bits, *src); }
IMPLEMENTATION_HELPER(signed char)
IMPLEMENTATION_HELPER(unsigned char)
IMPLEMENTATION_HELPER(short int)
IMPLEMENTATION_HELPER(unsigned short)
IMPLEMENTATION_HELPER(int)
IMPLEMENTATION_HELPER(unsigned int)
IMPLEMENTATION_HELPER(long int)
IMPLEMENTATION_HELPER(unsigned long int)
IMPLEMENTATION_HELPER(long long int)
IMPLEMENTATION_HELPER(unsigned long long int)
#undef IMPLEMENTATION_HELPER

#endif // __GNU_MP__

/******************************************************************************
* Multiply two integer polynomials stored in segments using Kronecker's method
******************************************************************************/

template<typename I> static inline void
mul_kronecker_int (I* dest,
                   const I* src1, nat n1,
                   const I* src2, nat n2)
{
  if (n1 == 0 && n2 == 0) return;
  for (nat i= 0; i < n1 + n2 - 1; i++) dest[i]= 0;
  while (n1 > 0 && src1[n1-1] == 0) n1--;
  while (n2 > 0 && src2[n2-1] == 0) n2--;
  if (n1 == 0 || n2 == 0) return;

  xnat bits= 16 * sizeof (I) + bit_size (min (n1, n2));
  integer aux1, aux2;
  encode_kronecker (aux1, src1, n1, bits);
  encode_kronecker (aux2, src2, n2, bits);
  integer aux= aux1 * aux2;
  decode_kronecker (dest, n1+n2-1, bits, aux);
}

#define IMPLEMENTATION_HELPER(I)                                        \
  void                                                                  \
  mul_kronecker (I* dest, const I* src1, nat n1, const I* src2, nat n2) { \
    mul_kronecker_int (dest, src1, n1, src2, n2); }
IMPLEMENTATION_HELPER (signed char)
IMPLEMENTATION_HELPER (unsigned char)
IMPLEMENTATION_HELPER (signed short int)
IMPLEMENTATION_HELPER (unsigned short int)
IMPLEMENTATION_HELPER (int)
IMPLEMENTATION_HELPER (unsigned int)
IMPLEMENTATION_HELPER (long int)
IMPLEMENTATION_HELPER (unsigned long int)
IMPLEMENTATION_HELPER (long long int)
IMPLEMENTATION_HELPER (unsigned long long int)
#undef IMPLEMENTATION_HELPER

template<typename I> static inline void
square_kronecker_int (I* dest, const I* src, nat n) {
  if (n == 0) return;
  for (nat i= 0; i < 2 * n - 1; i++) dest[i]= 0;
  while (n > 0 && src[n-1] == 0) n--;
  if (n == 0) return;
  if (n == 1) { dest[0]= square (src[0]); return; }

  xnat bits= 16 * sizeof (I) + bit_size (n);
  integer aux1;
  encode_kronecker (aux1, src, n, bits);
  integer aux= square (aux1);
  decode_kronecker (dest, 2*n - 1, bits, aux);
}

#define IMPLEMENTATION_HELPER(I)                                        \
  void                                                                  \
  square_kronecker (I* dest, const I* src, nat n) {                     \
    square_kronecker_int (dest, src, n); }
IMPLEMENTATION_HELPER (signed char)
IMPLEMENTATION_HELPER (unsigned char)
IMPLEMENTATION_HELPER (signed short int)
IMPLEMENTATION_HELPER (unsigned short int)
IMPLEMENTATION_HELPER (int)
IMPLEMENTATION_HELPER (unsigned int)
IMPLEMENTATION_HELPER (long int)
IMPLEMENTATION_HELPER (unsigned long int)
IMPLEMENTATION_HELPER (long long int)
IMPLEMENTATION_HELPER (unsigned long long int)
#undef IMPLEMENTATION_HELPER

} // namespace mmx