Wire Sysio Wire Sysion 1.0.0
Loading...
Searching...
No Matches
zm2.h
Go to the documentation of this file.
1#pragma once
2
8#include "zm.h"
9#ifdef MIE_ATE_USE_GMP
10#include <gmpxx.h>
11#endif
12
13namespace mie {
14
15class Fp : public local::addsubmul<Fp,
16 local::comparable<Fp,
17 local::hasNegative<Fp,
18 local::inversible<Fp> > > > {
19public:
21
22 /*
23 double size of Fp
24 */
25 enum {
26 N = 32 / sizeof(Unit)
27 };
29 {
30 }
32 {
33 set(x);
34 }
35 MIE_FORCE_INLINE explicit Fp(const std::string& str)
36 {
37 set(str);
38 }
39 MIE_FORCE_INLINE explicit Fp(const mie::Unit *x)
40 {
41 std::copy(x, x + N, v_);
42 }
43 Fp(const mie::Vuint& rhs)
44 {
45 set(rhs);
46 }
47 void set(int x)
48 {
49 if (x == 0) {
50 clear();
51 } else if (x == 1) {
52 const mie::Vuint& r = getMontgomeryR();
53 assert(r.size() == N);
54 std::copy(&r[0], &r[0] + N, v_);
55 } else if (x > 0) {
56 v_[0] = x;
57 std::fill(v_ + 1, v_ + N, 0);
58 mul(*this, *this, montgomeryR2_);
59 } else {
60 v_[0] = -x;
61 std::fill(v_ + 1, v_ + N, 0);
62 mul(*this, *this, montgomeryR2_);
63 neg(*this, *this);
64 }
65 }
66 void set(const std::string& str)
67 {
68 set(mie::Vuint(str));
69 }
70 void set(const mie::Vuint& x)
71 {
72 assert(x < getModulo());
73 mie::Vuint y(x);
74// count++;std::cout << "count=" << count << ", x=" << x << std::endl;
75 y *= getMontgomeryR();
76 y %= getModulo();
77 setDirect(*this, y);
78 }
79 static inline int compare(const Fp& x, const Fp& y)
80 {
81 return mie::local::PrimitiveFunction::compare(&x[0], N, &y[0], N);
82 }
83 static void (*add)(Fp& out, const Fp& x, const Fp& y);
84
85 // add without mod
86 static void (*addNC)(Fp& out, const Fp& x, const Fp& y);
87 static void (*subNC)(Fp& out, const Fp& x, const Fp& y);
88 static void (*shr1)(Fp& out, const Fp& x);
89 static void (*shr2)(Fp& out, const Fp& x);
90
91 static void (*sub)(Fp& out, const Fp& x, const Fp& y);
92 static void (*neg)(Fp& out, const Fp& x);
93 static void (*mul)(Fp& out, const Fp& x, const Fp& y);
94 static int (*preInv)(Fp& r, const Fp& x);
95 /*
96 z = 3z + 2x
97 */
98 static inline void _3z_add_2xC(Fp& z, const Fp& x)
99 {
100 addNC(z, z, x);
101 addNC(z, z, z);
102 addNC(z, z, x);
103 fast_modp(z);
104 }
105 /*
106 z = 2z + 3x
107 */
108 static inline void _2z_add_3x(Fp& z, const Fp& x)
109 {
110 addNC(z, x, z);
111 addNC(z, z, z);
112 addNC(z, z, x);
113 fast_modp(z);
114 }
115
116 inline friend std::ostream& operator<<(std::ostream& os, const Fp& x)
117 {
118 return os << x.toString(os.flags() & std::ios_base::hex ? 16 : 10);
119 }
120 inline friend std::istream& operator>>(std::istream& is, Fp& x)
121 {
122 std::string str;
123 mie::local::getDigits(is, str);
124 x.set(str);
125 return is;
126 }
128 {
129 Unit t = 0;
130 for (size_t i = 0; i < N; i++) {
131 t |= v_[i];
132 }
133 return t == 0;
134 }
136 {
137 std::fill(v_, v_ + N, 0);
138 }
139 static inline void fromMont(Fp& y, const Fp& x)
140 {
141 mul(y, x, one_);
142 }
143 static inline void toMont(Fp& y, const Fp& x)
144 {
145 mul(y, x, montgomeryR2_);
146 }
147 // return real low value
148 Unit getLow() const
149 {
150 Fp t;
151 fromMont(t, *this);
152 return t.v_[0];
153 }
154 bool isOdd() const
155 {
156 return (getLow() & 1) != 0;
157 }
159 {
160 Fp t;
161 fromMont(t, *this);
162 mie::Vuint ret(t.v_, N);
163 return ret;
164 }
165 static inline void inv(Fp& out, const Fp& x)
166 {
167#ifdef MIE_USE_X64ASM
168 Fp r;
169 int k = preInv(r, x);
170#else
171 static const Fp p(&p_[0]);
172 Fp u, v, r, s;
173 u = p;
174 v = x;
175 r.clear();
176 s.clear(); s[0] = 1; // s is real 1
177 int k = 0;
178 while (!v.isZero()) {
179 if ((u[0] & 1) == 0) {
180 shr1(u, u);
181 addNC(s, s, s);
182 } else if ((v[0] & 1) == 0) {
183 shr1(v, v);
184 addNC(r, r, r);
185 } else if (v >= u) {
186 subNC(v, v, u);
187 addNC(s, s, r);
188 shr1(v, v);
189 addNC(r, r, r);
190 } else {
191 subNC(u, u, v);
192 addNC(r, r, s);
193 shr1(u, u);
194 addNC(s, s, s);
195 }
196 k++;
197 }
198 if (r >= p) {
199 subNC(r, r, p);
200 }
201 assert(!r.isZero());
202 subNC(r, p, r);
203#endif
204 /*
205 xr = 2^k
206 R = 2^256
207 get r2^(-k)R^2 = r 2^(512 - k)
208 */
209 mul(out, r, invTbl_[k]);
210 }
211 void inverse()
212 {
213 inv(*this, *this);
214 }
215
216 static inline void divBy2(Fp &z, const Fp &x)
217 {
218 unsigned int i = x[0] & 0x1;
219 shr1(z, x);
220 addNC(z, z, halfTbl_[i]);
221 }
222
223 static inline void divBy4(Fp &z, const Fp &x)
224 {
225 unsigned int i = x[0] & 0x3;
226 shr2(z, x);
227 addNC(z, z, quarterTbl_[i]);
228 }
229
230 /* z <- z mod p for z in [0, 6p] */
231 static inline void fast_modp(Fp &z)
232 {
233 uint64_t t = z.v_[3] >> 61;
234 z -= getDirectP((int)t);
235 }
236
237 template<class T>
238 static MIE_FORCE_INLINE void setDirect(Fp& out, const T& in)
239 {
240 const size_t n = in.size();
241// assert(n <= N);
242 if (n < N) {
243 std::copy(&in[0], &in[0] + n, out.v_);
244 std::fill(out.v_ + n, out.v_ + N, 0);
245 } else {
246 // ignore in[i] for i >= N
247 std::copy(&in[0], &in[0] + N, out.v_);
248 }
249 }
250 std::string toString(int base = 10) const { return get().toString(base); }
251 MIE_FORCE_INLINE const Unit& operator[](size_t i) const { return v_[i]; }
252 MIE_FORCE_INLINE Unit& operator[](size_t i) { return v_[i]; }
253 MIE_FORCE_INLINE size_t size() const { return N; }
254
255 static void setModulo(const mie::Vuint& p, int mode, bool useMulx = true, bool definedBN_SUPPORT_SNARK =
256#ifdef BN_SUPPORT_SNARK
257 true
258#else
259 false
260#endif
261 );
262 static inline const mie::Vuint& getModulo() { return p_; }
263 static const Fp& getDirectP(int n); /* n = 0..6 */
264 static inline const mie::Vuint& getMontgomeryR() { return montgomeryR_; }
265private:
266 MIE_ALIGN(16) Unit v_[N];
267 static mie::Vuint p_;
268 static mie::Fp invTbl_[512];
269public:
270 static mie::Fp *halfTbl_; // [2] = [0, 1/2 mod p]
271private:
272 static mie::Fp *quarterTbl_; // [4] = [0, 1/4, 2/4, 3/4]
273 static mie::Vuint montgomeryR_; // 1 = 1r
274 static mie::Vuint p_add1_div4_; // (p + 1) / 4
275 static mie::Fp montgomeryR2_; // m(x, r^2) = xr ; x -> xr
276 static mie::Fp one_; // 1
277 // m(xr, r^(-2)r) = xr^(-1) ; xr -> xr^(-1)
278
279 static void setTablesForDiv(const mie::Vuint& p);
280
281public:
282 static inline void square(Fp& out, const Fp& x) { mul(out, x, x); }
283#ifdef MIE_ATE_USE_GMP
284 static void toMpz(mpz_class& y, const Fp& x)
285 {
286 mpz_import(y.get_mpz_t(), N, -1, sizeof(Unit), 0, 0, x.v_);
287 }
288 static void fromMpz(Fp& y, const mpz_class& x)
289 {
290 size_t size;
291 mpz_export(y.v_, &size, -1, sizeof(Unit), 0, 0, x.get_mpz_t());
292 for (size_t i = size; i < N; i++) {
293 y.v_[i] = 0;
294 }
295 }
296#endif
297 static bool squareRoot(Fp& y, const Fp& x)
298 {
299 Fp t;
300 t = mie::power(x, p_add1_div4_);
301 if (t * t != x) return false;
302 y = t;
303 return true;
304 }
305
306 struct Dbl : public local::addsubmul<Dbl,
307 local::comparable<Dbl,
308 local::hasNegative<Dbl> > > {
309 enum {
310 SIZE = sizeof(Unit) * N * 2
311 };
312 static MIE_FORCE_INLINE void setDirect(Dbl &out, const mie::Vuint &in)
313 {
314 const size_t n = in.size();
315 if (n < N * 2) {
316 std::copy(&in[0], &in[0] + n, out.v_);
317 std::fill(out.v_ + n, out.v_ + N * 2, 0);
318 } else {
319 // ignore in[i] for i >= N * 2
320 std::copy(&in[0], &in[0] + N * 2, out.v_);
321 }
322 }
323 static MIE_FORCE_INLINE void setDirect(Dbl &out, const std::string &in)
324 {
325 mie::Vuint t(in);
326 setDirect(out, t);
327 }
328
329 template<class T>
330 void setDirect(const T &in) { setDirect(*this, in); }
331
333 {
334 std::fill(v_, v_ + N * 2, 0);
335 }
336
337 Unit *ptr() { return v_; }
338 const Unit *const_ptr() const { return v_; }
339 mie::Vuint getDirect() const { return mie::Vuint(v_, N * 2); }
340 MIE_FORCE_INLINE const Unit& operator[](size_t i) const { return v_[i]; }
341 MIE_FORCE_INLINE Unit& operator[](size_t i) { return v_[i]; }
342 MIE_FORCE_INLINE size_t size() const { return N * 2; }
343
344 std::string toString(int base = 10) const
345 {
346 return ("Dbl(" + getDirect().toString(base) + ")");
347 }
348 friend inline std::ostream& operator<<(std::ostream& os, const Dbl& x)
349 {
350 return os << x.toString(os.flags() & std::ios_base::hex ? 16 : 10);
351 }
352
353 Dbl() {}
354 explicit Dbl(const Fp &x)
355 {
356 mul(*this, x, montgomeryR2_);
357 }
358 explicit Dbl(const std::string &str) { setDirect(*this, str); }
359
360 static inline int compare(const Dbl& x, const Dbl& y)
361 {
362 return mie::local::PrimitiveFunction::compare(&x[0], N * 2, &y[0], N * 2);
363 }
364
365 typedef void (uni_op)(Dbl &z, const Dbl &x);
366 typedef void (bin_op)(Dbl &z, const Dbl &x, const Dbl &y);
367
368 /*
369 z = (x + y) mod px
370 */
371 static bin_op *add;
372 static bin_op *addNC;
373
374 static uni_op *neg;
375
376 /*
377 z = (x - y) mod px
378 */
379 static bin_op *sub;
380 static bin_op *subNC;
381
382 static void subOpt1(Dbl &z, const Dbl &x, const Dbl &y)
383 {
384 assert(&z != &x);
385 assert(&z != &y);
386 addNC(z, x, pNTbl_[1]);
387 subNC(z, z, y);
388 }
389
390 /*
391 z = x * y
392 */
393 static void (*mul)(Dbl &z, const Fp &x, const Fp &y);
394
395 /*
396 z = MontgomeryReduction(x)
397 */
398 static void (*mod)(Fp &z, const Dbl &x);
399
400 /*
401 x <- x mod pN
402 */
403 static Dbl *pNTbl_; // [4];
404 private:
405 MIE_ALIGN(16) Unit v_[N * 2];
406 };
407};
408
409namespace util {
410template<>
411struct IntTag<mie::Fp> {
412 typedef size_t value_type;
413 static inline value_type getBlock(const mie::Fp&, size_t)
414 {
415 err();
416 return 0;
417 }
418 static inline size_t getBlockSize(const mie::Fp&)
419 {
420 err();
421 return 0;
422 }
423 static inline void err()
424 {
425 printf("Use mie::Vuint intead of Fp for the 3rd parameter for ScalarMulti\n");
426 exit(1);
427 }
428};
429
430} // mie::util
431
432} // mie
const mie::Vuint & p
Definition bn.cpp:27
const mie::Vuint & r
Definition bn.cpp:28
Definition zm2.h:18
static void(* add)(Fp &out, const Fp &x, const Fp &y)
Definition zm2.h:83
Fp()
Definition zm2.h:28
MIE_FORCE_INLINE size_t size() const
Definition zm2.h:253
static void(* addNC)(Fp &out, const Fp &x, const Fp &y)
Definition zm2.h:86
MIE_FORCE_INLINE Fp(int x)
Definition zm2.h:31
void set(const std::string &str)
Definition zm2.h:66
static void(* shr2)(Fp &out, const Fp &x)
Definition zm2.h:89
mie::Unit value_type
Definition zm2.h:20
MIE_FORCE_INLINE Fp(const mie::Unit *x)
Definition zm2.h:39
static void(* mul)(Fp &out, const Fp &x, const Fp &y)
Definition zm2.h:93
void set(const mie::Vuint &x)
Definition zm2.h:70
static int(* preInv)(Fp &r, const Fp &x)
Definition zm2.h:94
static void inv(Fp &out, const Fp &x)
Definition zm2.h:165
MIE_FORCE_INLINE const Unit & operator[](size_t i) const
Definition zm2.h:251
static int compare(const Fp &x, const Fp &y)
Definition zm2.h:79
bool isOdd() const
Definition zm2.h:154
MIE_FORCE_INLINE Unit & operator[](size_t i)
Definition zm2.h:252
void set(int x)
Definition zm2.h:47
MIE_FORCE_INLINE Fp(const std::string &str)
Definition zm2.h:35
static mie::Fp * halfTbl_
Definition zm2.h:270
static const mie::Vuint & getModulo()
Definition zm2.h:262
friend std::istream & operator>>(std::istream &is, Fp &x)
Definition zm2.h:120
@ N
Definition zm2.h:26
static const Fp & getDirectP(int n)
Definition zm2.cpp:126
static void _3z_add_2xC(Fp &z, const Fp &x)
Definition zm2.h:98
static void divBy2(Fp &z, const Fp &x)
Definition zm2.h:216
friend std::ostream & operator<<(std::ostream &os, const Fp &x)
Definition zm2.h:116
static void fromMont(Fp &y, const Fp &x)
Definition zm2.h:139
MIE_FORCE_INLINE bool isZero() const
Definition zm2.h:127
Unit getLow() const
Definition zm2.h:148
MIE_FORCE_INLINE void clear()
Definition zm2.h:135
static void(* neg)(Fp &out, const Fp &x)
Definition zm2.h:92
static const mie::Vuint & getMontgomeryR()
Definition zm2.h:264
static void toMont(Fp &y, const Fp &x)
Definition zm2.h:143
static void divBy4(Fp &z, const Fp &x)
Definition zm2.h:223
static void(* sub)(Fp &out, const Fp &x, const Fp &y)
Definition zm2.h:91
static void(* subNC)(Fp &out, const Fp &x, const Fp &y)
Definition zm2.h:87
Fp(const mie::Vuint &rhs)
Definition zm2.h:43
static void(* shr1)(Fp &out, const Fp &x)
Definition zm2.h:88
std::string toString(int base=10) const
Definition zm2.h:250
static void fast_modp(Fp &z)
Definition zm2.h:231
static MIE_FORCE_INLINE void setDirect(Fp &out, const T &in)
Definition zm2.h:238
static void _2z_add_3x(Fp &z, const Fp &x)
Definition zm2.h:108
static bool squareRoot(Fp &y, const Fp &x)
Definition zm2.h:297
void inverse()
Definition zm2.h:211
static void setModulo(const mie::Vuint &p, int mode, bool useMulx=true, bool definedBN_SUPPORT_SNARK=false)
Definition zm2.cpp:3592
static void square(Fp &out, const Fp &x)
Definition zm2.h:282
mie::Vuint get() const
Definition zm2.h:158
os_t os
std::istream & getDigits(std::istream &is, std::string &str, bool allowNegative=false)
Definition zm.h:84
Definition zm.h:60
uint32_t Unit
Definition zm.h:66
T power(const T &x, const S &y)
Definition zm.h:1389
VuintT< local::FixedBuffer< mie::Unit, MIE_ZM_VUINT_BIT_LEN > > Vuint
Definition zm.h:1161
#define T(meth, val, expected)
unsigned __int64 uint64_t
Definition stdint.h:136
MIE_FORCE_INLINE void clear()
Definition zm2.h:332
MIE_FORCE_INLINE const Unit & operator[](size_t i) const
Definition zm2.h:340
static void subOpt1(Dbl &z, const Dbl &x, const Dbl &y)
Definition zm2.h:382
static int compare(const Dbl &x, const Dbl &y)
Definition zm2.h:360
static MIE_FORCE_INLINE void setDirect(Dbl &out, const std::string &in)
Definition zm2.h:323
static MIE_FORCE_INLINE void setDirect(Dbl &out, const mie::Vuint &in)
Definition zm2.h:312
std::string toString(int base=10) const
Definition zm2.h:344
friend std::ostream & operator<<(std::ostream &os, const Dbl &x)
Definition zm2.h:348
Unit * ptr()
Definition zm2.h:337
const Unit * const_ptr() const
Definition zm2.h:338
MIE_FORCE_INLINE size_t size() const
Definition zm2.h:342
static uni_op * neg
Definition zm2.h:374
static void(* mod)(Fp &z, const Dbl &x)
Definition zm2.h:398
void bin_op(Dbl &z, const Dbl &x, const Dbl &y)
Definition zm2.h:366
static bin_op * sub
Definition zm2.h:379
mie::Vuint getDirect() const
Definition zm2.h:339
void setDirect(const T &in)
Definition zm2.h:330
static bin_op * subNC
Definition zm2.h:380
Dbl(const std::string &str)
Definition zm2.h:358
static Dbl * pNTbl_
Definition zm2.h:403
static bin_op * addNC
Definition zm2.h:372
Dbl(const Fp &x)
Definition zm2.h:354
static void(* mul)(Dbl &z, const Fp &x, const Fp &y)
Definition zm2.h:393
void uni_op(Dbl &z, const Dbl &x)
Definition zm2.h:365
static bin_op * add
Definition zm2.h:371
MIE_FORCE_INLINE Unit & operator[](size_t i)
Definition zm2.h:341
size_t size() const
Definition zm.h:519
void clear()
Definition zm.h:406
bool isZero() const
Definition zm.h:521
std::string toString(int base=10) const
Definition zm.h:407
static int compare(const Unit *x, size_t xn, const Unit *y, size_t yn)
Definition zm.h:183
static value_type getBlock(const mie::Fp &, size_t)
Definition zm2.h:413
static size_t getBlockSize(const mie::Fp &)
Definition zm2.h:418
static void err()
Definition zm2.h:423
CK_RV ret
char * s
bool set
#define MIE_ALIGN(x)
Definition zm.h:50
#define MIE_FORCE_INLINE
Definition zm.h:53