00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013 #ifndef __MMX__MODULUS_NAIVE__HPP
00014 #define __MMX__MODULUS_NAIVE__HPP
00015 #include "basix/port.hpp"
00016
00017 namespace mmx {
00018 #define TMPL template<typename C, typename M>
00019
00020
00021
00022
00023
00024 struct modulus_normalization_naive {
00027 template<typename C> static inline bool
00028 normalize (C& p) { return true; }
00029 };
00030
00031 template<typename V>
00032 struct modulus_reduction_naive : public V {
00033 TMPL static inline void
00034 reduce_mod (C& dest, const M& m) {
00035 if (m.p != 0) dest = rem (dest, m.p); }
00036
00037 TMPL static inline void
00038 reduce_mod (C& dest, const M& m, C& carry) {
00039 if (m.p != 0) {
00040 carry= quo (dest, m.p);
00041 dest = rem (dest, m.p);
00042 }
00043 else
00044 carry= 0; }
00045
00046 TMPL static inline void
00047 reduce_mod (C& dest, const C& s, const M& m) {
00048 if (m.p != 0) dest = rem (s, m.p); else dest = s; }
00049
00050 TMPL static inline void
00051 reduce_mod (C& dest, const C& s, const M& m, C& carry) {
00052 if (m.p != 0) {
00053 carry= quo (s, m.p);
00054 dest = rem (s, m.p);
00055 }
00056 else {
00057 carry= 0;
00058 dest= s;
00059 } }
00060 };
00061
00062
00063
00064
00065
00066 template<typename V>
00067 struct modulus_add_naive : public V {
00068
00069 TMPL static inline void
00070 neg_mod (C& dest, const M& m) {
00071 dest = - dest;
00072 V::reduce_mod (dest, m);}
00073
00074 TMPL static inline void
00075 neg_mod (C& dest, const M& m, C& carry) {
00076 dest= carry - dest;
00077 V::reduce_mod (dest, m, carry); }
00078
00079 TMPL static inline void
00080 neg_mod (C& dest, const C& s, const M& m) {
00081 V::reduce_mod (dest, -s, m);}
00082
00083 TMPL static inline void
00084 neg_mod (C& dest, const C& s, const M& m, C& carry) {
00085 V::reduce_mod (dest, carry - s, m, carry); }
00086
00087 TMPL static inline void
00088 add_mod (C& dest, const C& s, const M& m) {
00089 dest += s;
00090 V::reduce_mod (dest, m); }
00091
00092 TMPL static inline void
00093 add_mod (C& dest, const C& s, const M& m, C& carry) {
00094 dest += s + carry;
00095 V::reduce_mod (dest, m, carry); }
00096
00097 TMPL static inline void
00098 add_mod (C& dest, const C& s1, const C& s2, const M& m) {
00099 V::reduce_mod (dest, s1 + s2, m); }
00100
00101 TMPL static inline void
00102 add_mod (C& dest, const C& s1, const C& s2, const M& m, C& carry) {
00103 V::reduce_mod (dest, s1 + s2 + carry, m, carry); }
00104
00105 TMPL static inline void
00106 sub_mod (C& dest, const C& s, const M& m) {
00107 dest -= s;
00108 V::reduce_mod (dest, m); }
00109
00110 TMPL static inline void
00111 sub_mod (C& dest, const C& s, const M& m, C& carry) {
00112 dest -= s + carry;
00113 V::reduce_mod (dest, m, carry); }
00114
00115 TMPL static inline void
00116 sub_mod (C& dest, const C& s1, const C& s2, const M& m) {
00117 V::reduce_mod (dest, s1 - s2, m); }
00118
00119 TMPL static inline void
00120 sub_mod (C& dest, const C& s1, const C& s2, const M& m, C& carry) {
00121 V::reduce_mod (dest, s1 - s2 + carry, m, carry); }
00122
00123 };
00124
00125 template<typename V>
00126 struct modulus_mul_naive : public V {
00127
00128 TMPL static inline void
00129 mul_mod (C& dest, const C& s, const M& m) {
00130 dest *= s;
00131 V::reduce_mod (dest, m); }
00132
00133 TMPL static inline void
00134 mul_mod (C& dest, const C& s, const M& m, C& carry) {
00135 dest *= s;
00136 dest += carry;
00137 V::reduce_mod (dest, m, carry); }
00138
00139 TMPL static inline void
00140 mul_mod (C& dest, const C& s1, const C& s2, const M& m) {
00141 V::reduce_mod (dest, s1 * s2, m); }
00142
00143 TMPL static inline void
00144 mul_mod (C& dest, const C& s1, const C& s2, const M& m, C& carry) {
00145 V::reduce_mod (dest, s1 * s2 + carry, m, carry); }
00146 };
00147
00148 template<typename V>
00149 struct modulus_inv_naive : public V {
00150
00151 TMPL static inline bool
00152 is_invertible_mod (const C& s, const M& m) {
00153 (void) m;
00154 return ((s == (C) 1) || (s == (C) -1)); }
00155
00156 TMPL static inline void
00157 inv_mod (C& dest, const M& m) {
00158 (void) m;
00159 if ((dest == (C) 1) || (dest == (C) -1)) return;
00160 ERROR ("inv_mod: argument is not invertible"); }
00161
00162 TMPL static inline void
00163 inv_mod (C& dest, const C& s, const M& m) {
00164 (void) m;
00165 if ((s == (C) 1) || (s == (C) -1)) { dest = s; return; }
00166 ERROR ("inv_mod: argument is not invertible"); }
00167 };
00168
00169 template<typename V>
00170 struct modulus_div_naive : public V {
00171
00172 TMPL static inline void
00173 div_mod (C& dest, const C& s, const M& m) {
00174 C t = s;
00175 V::inv_mod (t, m);
00176 V::mul_mod (dest, t, m); }
00177
00178 TMPL static inline void
00179 div_mod (C& dest, const C& s1, const C& s2, const M& m) {
00180 C t;
00181 V::inv_mod (t, s2, m);
00182 V::mul_mod (dest, s1, t, m); }
00183 };
00184
00185
00186
00187
00188
00189 template<typename V>
00190 struct modulus_encoding_naive : public V {
00191
00192 TMPL static inline void
00193 encode_mod (C& dest, const C& s, const M& m) {
00194 dest = s;
00195 V::reduce_mod (dest, m); }
00196
00197 TMPL static inline void
00198 decode_mod (C& dest, const C& s, const M& m) {
00199 (void) m;
00200 dest = s; }
00201 };
00202
00203
00204
00205
00206
00207 struct modulus_naive:
00208 public modulus_encoding_naive<
00209 modulus_div_naive<
00210 modulus_inv_naive<
00211 modulus_mul_naive<
00212 modulus_add_naive<
00213 modulus_reduction_naive<
00214 modulus_normalization_naive> > > > > > {};
00215
00216
00217
00218
00219
00220 template<typename C>
00221 struct modulus_variant_helper { typedef modulus_naive MV; };
00222
00223 #undef TMPL
00224 }
00225 #endif //__MMX__MODULUS_NAIVE__HPP