/Users/mourrain/Devel/mmx/algebramix/include/algebramix/vector_modular.hpp

Go to the documentation of this file.

/******************************************************************************
* MODULE     : vector_modular.hpp
* DESCRIPTION: header for low level vectorial computations over modular
* COPYRIGHT  : (C) 2008  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.
******************************************************************************/

#ifndef __MMX__VECTOR_MODULAR__HPP
#define __MMX__VECTOR_MODULAR__HPP
#include <numerix/modular.hpp>
#include <algebramix/vector_unrolled.hpp>

namespace mmx {

/******************************************************************************
* Optimized unrolling for modular operations
******************************************************************************/

// neg_op
template<typename R, typename M, nat n>
struct vec_neg_mod_helper {
  static const nat n1= (n>>1), n2= n-n1;
  static inline void op (R* dest, const R* s, const M& m) {
    vec_neg_mod_helper <R, M, n1>::op (dest   , s   , m);
    vec_neg_mod_helper <R, M, n2>::op (dest+n1, s+n1, m); }
};

template<typename R, typename M>
struct vec_neg_mod_helper<R, M, 1> {
  static inline void op (R* dest, const R* s, const M& m) {
    dest[0] = s[0];
    neg_mod (dest->rep, m); }
};

template<typename C, typename V, typename W, nat n>
struct vec_unary_helper<neg_op,
                        modular<modulus<C, V>, W>,
                        modular<modulus<C, V>, W>,
                        n> {    
  typedef modulus<C, V> M;
  typedef modular<M, W> R;
  static void op (R* dest, const R* s) {
    vec_neg_mod_helper<R, M, n>:: op (dest, s, R::get_modulus ()); }
};

// add_op
template<typename R, typename M, nat n>
struct vec_add_mod_helper {
  static const nat n1= (n>>1), n2= n-n1;
  static inline void op (R* dest, const R* s1, const R* s2, const M& m) {
    vec_add_mod_helper <R, M, n1>::op (dest   , s1   , s2   , m);
    vec_add_mod_helper <R, M, n2>::op (dest+n1, s1+n1, s2+n1, m); }
};

template<typename R, typename M>
struct vec_add_mod_helper<R, M, 1> {
  static inline void op (R* dest, const R* s1, const R* s2, const M& m) {
    dest[0] = s1[0];
    add_mod (dest->rep, s2->rep, m); }
};

template<typename C, typename V, typename W, nat n>
struct vec_binary_helper<add_op,
                         modular<modulus<C, V>, W>,
                         modular<modulus<C, V>, W>,
                         modular<modulus<C, V>, W>,
                         n> {   
  typedef modulus<C, V> M;
  typedef modular<M, W> R;
  static void op (R* dest, const R* s1, const R* s2) {
    vec_add_mod_helper<R, M, n>:: op (dest, s1, s2, R::get_modulus ()); }
};

// sub_op
template<typename R, typename M, nat n>
struct vec_sub_mod_helper {
  static const nat n1= (n>>1), n2= n-n1;
  static inline void op (R* dest, const R* s1, const R* s2, const M& m) {
    vec_sub_mod_helper <R, M, n1>::op (dest   , s1   , s2   , m);
    vec_sub_mod_helper <R, M, n2>::op (dest+n1, s1+n1, s2+n1, m); }
};

template<typename R, typename M>
struct vec_sub_mod_helper<R, M, 1> {
  static inline void op (R* dest, const R* s1, const R* s2, const M& m) {
    dest[0] = s1[0];
    sub_mod (dest->rep, s2->rep, m); }
};

template<typename C, typename V, typename W, nat n>
struct vec_binary_helper<sub_op,
                         modular<modulus<C, V>, W>,
                         modular<modulus<C, V>, W>,
                         modular<modulus<C, V>, W>,
                         n> {   
  typedef modulus<C, V> M;
  typedef modular<M, W> R;
  static void op (R* dest, const R* s1, const R* s2) {
    vec_sub_mod_helper<R, M, n>:: op (dest, s1, s2, R::get_modulus ()); }
};

// mul_op
template<typename R, typename M, nat n>
struct vec_mul_mod_helper {
  static const nat n1= (n>>1), n2= n-n1;
  static inline void op (R* dest, const R* s1, const R* s2, const M& m) {
    vec_mul_mod_helper <R, M, n1>::op (dest   , s1   , s2   , m);
    vec_mul_mod_helper <R, M, n2>::op (dest+n1, s1+n1, s2+n1, m); }
};

template<typename R, typename M>
struct vec_mul_mod_helper<R, M, 1> {
  static inline void op (R* dest, const R* s1, const R* s2, const M& m) {
    dest[0] = s1[0];
    mul_mod (dest->rep, s2->rep, m); }
};

template<typename C, typename V, typename W, nat n>
struct vec_binary_helper<mul_op,
                         modular<modulus<C, V>, W>,
                         modular<modulus<C, V>, W>,
                         modular<modulus<C, V>, W>,
                         n> {   
  typedef modulus<C, V> M;
  typedef modular<M, W> R;
  static void op (R* dest, const R* s1, const R* s2) {
    vec_mul_mod_helper<R, M, n>:: op (dest, s1, s2, R::get_modulus ()); }
};

// div_op
template<typename R, typename M, nat n>
struct vec_div_mod_helper {
  static const nat n1= (n>>1), n2= n-n1;
  static inline void op (R* dest, const R* s1, const R* s2, const M& m) {
    vec_div_mod_helper <R, M, n1>::op (dest   , s1   , s2   , m);
    vec_div_mod_helper <R, M, n2>::op (dest+n1, s1+n1, s2+n1, m); }
};

template<typename R, typename M>
struct vec_div_mod_helper<R, M, 1> {
  static inline void op (R* dest, const R* s1, const R* s2, const M& m) {
    dest[0] = s1[0];
    div_mod (dest->rep, s2->rep, m); }
};

template<typename C, typename V, typename W, nat n>
struct vec_binary_helper<div_op,
                         modular<modulus<C, V>, W>,
                         modular<modulus<C, V>, W>,
                         modular<modulus<C, V>, W>,
                         n> {   
  typedef modulus<C, V> M;
  typedef modular<M, W> R;
  static void op (R* dest, const R* s1, const R* s2) {
    vec_div_mod_helper<R, M, n>:: op (dest, s1, s2, R::get_modulus ()); }
};

/******************************************************************************
* Use modular vector operations by default
******************************************************************************/

template<typename V, typename W>
struct vector_variant_helper<modular<modulus<char,V>, W> > {
  typedef vector_unrolled<16,vector_unrolled<32> > VV;
};

template<typename V, typename W>
struct vector_variant_helper<modular<modulus<signed char,V>, W> > {
  typedef vector_unrolled<16,vector_unrolled<32> > VV;
};

template<typename V, typename W>
struct vector_variant_helper<modular<modulus<unsigned char,V>, W> > {
  typedef vector_unrolled<16,vector_unrolled<32> > VV;
};

template<typename V, typename W>
struct vector_variant_helper<modular<modulus<short int,V>, W> > {
  typedef vector_unrolled<8,vector_unrolled<32> > VV;
};

template<typename V, typename W>
struct vector_variant_helper<modular<modulus<short unsigned int,V>, W> > {
  typedef vector_unrolled<8,vector_unrolled<32> > VV;
};

template<typename V, typename W>
struct vector_variant_helper<modular<modulus<int,V>, W> > {
  typedef vector_unrolled<4,vector_unrolled<16> > VV;
};

template<typename V, typename W>
struct vector_variant_helper<modular<modulus<unsigned int,V>, W> > {
  typedef vector_unrolled<4,vector_unrolled<16> > VV;
};

template<typename V, typename W>
struct vector_variant_helper<modular<modulus<long int,V>, W> > {
  typedef vector_unrolled<4,vector_unrolled<16> > VV;
};

template<typename V, typename W>
struct vector_variant_helper<modular<modulus<long unsigned int,V>, W> > {
  typedef vector_unrolled<4,vector_unrolled<16> > VV;
};

template<typename V, typename W>
struct vector_variant_helper<modular<modulus<long long int,V>, W> > {
  typedef vector_unrolled<2,vector_unrolled<8> > VV;
};

template<typename V, typename W>
struct vector_variant_helper<modular<modulus<long long unsigned int,V>, W> > {
  typedef vector_unrolled<2,vector_unrolled<8> > VV;
};

} // namespace mmx
#endif //__MMX__VECTOR_MODULAR__HPP