Electroneum
field_5x52_impl.h
Go to the documentation of this file.
1 /***********************************************************************
2  * Copyright (c) 2013, 2014 Pieter Wuille *
3  * Distributed under the MIT software license, see the accompanying *
4  * file COPYING or https://www.opensource.org/licenses/mit-license.php.*
5  ***********************************************************************/
6 
7 #ifndef SECP256K1_FIELD_REPR_IMPL_H
8 #define SECP256K1_FIELD_REPR_IMPL_H
9 
10 #include "checkmem.h"
11 #include "util.h"
12 #include "field.h"
13 #include "modinv64_impl.h"
14 
15 #if defined(USE_ASM_X86_64)
16 #include "field_5x52_asm_impl.h"
17 #else
18 #include "field_5x52_int128_impl.h"
19 #endif
20 
36 #ifdef VERIFY
37 static void secp256k1_fe_verify(const secp256k1_fe *a) {
38  const uint64_t *d = a->n;
39  int m = a->normalized ? 1 : 2 * a->magnitude, r = 1;
40  /* secp256k1 'p' value defined in "Standards for Efficient Cryptography" (SEC2) 2.7.1. */
41  r &= (d[0] <= 0xFFFFFFFFFFFFFULL * m);
42  r &= (d[1] <= 0xFFFFFFFFFFFFFULL * m);
43  r &= (d[2] <= 0xFFFFFFFFFFFFFULL * m);
44  r &= (d[3] <= 0xFFFFFFFFFFFFFULL * m);
45  r &= (d[4] <= 0x0FFFFFFFFFFFFULL * m);
46  r &= (a->magnitude >= 0);
47  r &= (a->magnitude <= 2048);
48  if (a->normalized) {
49  r &= (a->magnitude <= 1);
50  if (r && (d[4] == 0x0FFFFFFFFFFFFULL) && ((d[3] & d[2] & d[1]) == 0xFFFFFFFFFFFFFULL)) {
51  r &= (d[0] < 0xFFFFEFFFFFC2FULL);
52  }
53  }
54  VERIFY_CHECK(r == 1);
55 }
56 #endif
57 
58 static void secp256k1_fe_get_bounds(secp256k1_fe *r, int m) {
59  VERIFY_CHECK(m >= 0);
60  VERIFY_CHECK(m <= 2048);
61  r->n[0] = 0xFFFFFFFFFFFFFULL * 2 * m;
62  r->n[1] = 0xFFFFFFFFFFFFFULL * 2 * m;
63  r->n[2] = 0xFFFFFFFFFFFFFULL * 2 * m;
64  r->n[3] = 0xFFFFFFFFFFFFFULL * 2 * m;
65  r->n[4] = 0x0FFFFFFFFFFFFULL * 2 * m;
66 #ifdef VERIFY
67  r->magnitude = m;
68  r->normalized = (m == 0);
69  secp256k1_fe_verify(r);
70 #endif
71 }
72 
73 static void secp256k1_fe_normalize(secp256k1_fe *r) {
74  uint64_t t0 = r->n[0], t1 = r->n[1], t2 = r->n[2], t3 = r->n[3], t4 = r->n[4];
75 
76  /* Reduce t4 at the start so there will be at most a single carry from the first pass */
77  uint64_t m;
78  uint64_t x = t4 >> 48; t4 &= 0x0FFFFFFFFFFFFULL;
79 
80  /* The first pass ensures the magnitude is 1, ... */
81  t0 += x * 0x1000003D1ULL;
82  t1 += (t0 >> 52); t0 &= 0xFFFFFFFFFFFFFULL;
83  t2 += (t1 >> 52); t1 &= 0xFFFFFFFFFFFFFULL; m = t1;
84  t3 += (t2 >> 52); t2 &= 0xFFFFFFFFFFFFFULL; m &= t2;
85  t4 += (t3 >> 52); t3 &= 0xFFFFFFFFFFFFFULL; m &= t3;
86 
87  /* ... except for a possible carry at bit 48 of t4 (i.e. bit 256 of the field element) */
88  VERIFY_CHECK(t4 >> 49 == 0);
89 
90  /* At most a single final reduction is needed; check if the value is >= the field characteristic */
91  x = (t4 >> 48) | ((t4 == 0x0FFFFFFFFFFFFULL) & (m == 0xFFFFFFFFFFFFFULL)
92  & (t0 >= 0xFFFFEFFFFFC2FULL));
93 
94  /* Apply the final reduction (for constant-time behaviour, we do it always) */
95  t0 += x * 0x1000003D1ULL;
96  t1 += (t0 >> 52); t0 &= 0xFFFFFFFFFFFFFULL;
97  t2 += (t1 >> 52); t1 &= 0xFFFFFFFFFFFFFULL;
98  t3 += (t2 >> 52); t2 &= 0xFFFFFFFFFFFFFULL;
99  t4 += (t3 >> 52); t3 &= 0xFFFFFFFFFFFFFULL;
100 
101  /* If t4 didn't carry to bit 48 already, then it should have after any final reduction */
102  VERIFY_CHECK(t4 >> 48 == x);
103 
104  /* Mask off the possible multiple of 2^256 from the final reduction */
105  t4 &= 0x0FFFFFFFFFFFFULL;
106 
107  r->n[0] = t0; r->n[1] = t1; r->n[2] = t2; r->n[3] = t3; r->n[4] = t4;
108 
109 #ifdef VERIFY
110  r->magnitude = 1;
111  r->normalized = 1;
112  secp256k1_fe_verify(r);
113 #endif
114 }
115 
116 static void secp256k1_fe_normalize_weak(secp256k1_fe *r) {
117  uint64_t t0 = r->n[0], t1 = r->n[1], t2 = r->n[2], t3 = r->n[3], t4 = r->n[4];
118 
119  /* Reduce t4 at the start so there will be at most a single carry from the first pass */
120  uint64_t x = t4 >> 48; t4 &= 0x0FFFFFFFFFFFFULL;
121 
122  /* The first pass ensures the magnitude is 1, ... */
123  t0 += x * 0x1000003D1ULL;
124  t1 += (t0 >> 52); t0 &= 0xFFFFFFFFFFFFFULL;
125  t2 += (t1 >> 52); t1 &= 0xFFFFFFFFFFFFFULL;
126  t3 += (t2 >> 52); t2 &= 0xFFFFFFFFFFFFFULL;
127  t4 += (t3 >> 52); t3 &= 0xFFFFFFFFFFFFFULL;
128 
129  /* ... except for a possible carry at bit 48 of t4 (i.e. bit 256 of the field element) */
130  VERIFY_CHECK(t4 >> 49 == 0);
131 
132  r->n[0] = t0; r->n[1] = t1; r->n[2] = t2; r->n[3] = t3; r->n[4] = t4;
133 
134 #ifdef VERIFY
135  r->magnitude = 1;
136  secp256k1_fe_verify(r);
137 #endif
138 }
139 
140 static void secp256k1_fe_normalize_var(secp256k1_fe *r) {
141  uint64_t t0 = r->n[0], t1 = r->n[1], t2 = r->n[2], t3 = r->n[3], t4 = r->n[4];
142 
143  /* Reduce t4 at the start so there will be at most a single carry from the first pass */
144  uint64_t m;
145  uint64_t x = t4 >> 48; t4 &= 0x0FFFFFFFFFFFFULL;
146 
147  /* The first pass ensures the magnitude is 1, ... */
148  t0 += x * 0x1000003D1ULL;
149  t1 += (t0 >> 52); t0 &= 0xFFFFFFFFFFFFFULL;
150  t2 += (t1 >> 52); t1 &= 0xFFFFFFFFFFFFFULL; m = t1;
151  t3 += (t2 >> 52); t2 &= 0xFFFFFFFFFFFFFULL; m &= t2;
152  t4 += (t3 >> 52); t3 &= 0xFFFFFFFFFFFFFULL; m &= t3;
153 
154  /* ... except for a possible carry at bit 48 of t4 (i.e. bit 256 of the field element) */
155  VERIFY_CHECK(t4 >> 49 == 0);
156 
157  /* At most a single final reduction is needed; check if the value is >= the field characteristic */
158  x = (t4 >> 48) | ((t4 == 0x0FFFFFFFFFFFFULL) & (m == 0xFFFFFFFFFFFFFULL)
159  & (t0 >= 0xFFFFEFFFFFC2FULL));
160 
161  if (x) {
162  t0 += 0x1000003D1ULL;
163  t1 += (t0 >> 52); t0 &= 0xFFFFFFFFFFFFFULL;
164  t2 += (t1 >> 52); t1 &= 0xFFFFFFFFFFFFFULL;
165  t3 += (t2 >> 52); t2 &= 0xFFFFFFFFFFFFFULL;
166  t4 += (t3 >> 52); t3 &= 0xFFFFFFFFFFFFFULL;
167 
168  /* If t4 didn't carry to bit 48 already, then it should have after any final reduction */
169  VERIFY_CHECK(t4 >> 48 == x);
170 
171  /* Mask off the possible multiple of 2^256 from the final reduction */
172  t4 &= 0x0FFFFFFFFFFFFULL;
173  }
174 
175  r->n[0] = t0; r->n[1] = t1; r->n[2] = t2; r->n[3] = t3; r->n[4] = t4;
176 
177 #ifdef VERIFY
178  r->magnitude = 1;
179  r->normalized = 1;
180  secp256k1_fe_verify(r);
181 #endif
182 }
183 
184 static int secp256k1_fe_normalizes_to_zero(const secp256k1_fe *r) {
185  uint64_t t0 = r->n[0], t1 = r->n[1], t2 = r->n[2], t3 = r->n[3], t4 = r->n[4];
186 
187  /* z0 tracks a possible raw value of 0, z1 tracks a possible raw value of P */
188  uint64_t z0, z1;
189 
190  /* Reduce t4 at the start so there will be at most a single carry from the first pass */
191  uint64_t x = t4 >> 48; t4 &= 0x0FFFFFFFFFFFFULL;
192 
193  /* The first pass ensures the magnitude is 1, ... */
194  t0 += x * 0x1000003D1ULL;
195  t1 += (t0 >> 52); t0 &= 0xFFFFFFFFFFFFFULL; z0 = t0; z1 = t0 ^ 0x1000003D0ULL;
196  t2 += (t1 >> 52); t1 &= 0xFFFFFFFFFFFFFULL; z0 |= t1; z1 &= t1;
197  t3 += (t2 >> 52); t2 &= 0xFFFFFFFFFFFFFULL; z0 |= t2; z1 &= t2;
198  t4 += (t3 >> 52); t3 &= 0xFFFFFFFFFFFFFULL; z0 |= t3; z1 &= t3;
199  z0 |= t4; z1 &= t4 ^ 0xF000000000000ULL;
200 
201  /* ... except for a possible carry at bit 48 of t4 (i.e. bit 256 of the field element) */
202  VERIFY_CHECK(t4 >> 49 == 0);
203 
204  return (z0 == 0) | (z1 == 0xFFFFFFFFFFFFFULL);
205 }
206 
207 static int secp256k1_fe_normalizes_to_zero_var(const secp256k1_fe *r) {
208  uint64_t t0, t1, t2, t3, t4;
209  uint64_t z0, z1;
210  uint64_t x;
211 
212  t0 = r->n[0];
213  t4 = r->n[4];
214 
215  /* Reduce t4 at the start so there will be at most a single carry from the first pass */
216  x = t4 >> 48;
217 
218  /* The first pass ensures the magnitude is 1, ... */
219  t0 += x * 0x1000003D1ULL;
220 
221  /* z0 tracks a possible raw value of 0, z1 tracks a possible raw value of P */
222  z0 = t0 & 0xFFFFFFFFFFFFFULL;
223  z1 = z0 ^ 0x1000003D0ULL;
224 
225  /* Fast return path should catch the majority of cases */
226  if ((z0 != 0ULL) & (z1 != 0xFFFFFFFFFFFFFULL)) {
227  return 0;
228  }
229 
230  t1 = r->n[1];
231  t2 = r->n[2];
232  t3 = r->n[3];
233 
234  t4 &= 0x0FFFFFFFFFFFFULL;
235 
236  t1 += (t0 >> 52);
237  t2 += (t1 >> 52); t1 &= 0xFFFFFFFFFFFFFULL; z0 |= t1; z1 &= t1;
238  t3 += (t2 >> 52); t2 &= 0xFFFFFFFFFFFFFULL; z0 |= t2; z1 &= t2;
239  t4 += (t3 >> 52); t3 &= 0xFFFFFFFFFFFFFULL; z0 |= t3; z1 &= t3;
240  z0 |= t4; z1 &= t4 ^ 0xF000000000000ULL;
241 
242  /* ... except for a possible carry at bit 48 of t4 (i.e. bit 256 of the field element) */
243  VERIFY_CHECK(t4 >> 49 == 0);
244 
245  return (z0 == 0) | (z1 == 0xFFFFFFFFFFFFFULL);
246 }
247 
248 SECP256K1_INLINE static void secp256k1_fe_set_int(secp256k1_fe *r, int a) {
249  VERIFY_CHECK(0 <= a && a <= 0x7FFF);
250  r->n[0] = a;
251  r->n[1] = r->n[2] = r->n[3] = r->n[4] = 0;
252 #ifdef VERIFY
253  r->magnitude = (a != 0);
254  r->normalized = 1;
255  secp256k1_fe_verify(r);
256 #endif
257 }
258 
259 SECP256K1_INLINE static int secp256k1_fe_is_zero(const secp256k1_fe *a) {
260  const uint64_t *t = a->n;
261 #ifdef VERIFY
262  VERIFY_CHECK(a->normalized);
263  secp256k1_fe_verify(a);
264 #endif
265  return (t[0] | t[1] | t[2] | t[3] | t[4]) == 0;
266 }
267 
268 SECP256K1_INLINE static int secp256k1_fe_is_odd(const secp256k1_fe *a) {
269 #ifdef VERIFY
270  VERIFY_CHECK(a->normalized);
271  secp256k1_fe_verify(a);
272 #endif
273  return a->n[0] & 1;
274 }
275 
276 SECP256K1_INLINE static void secp256k1_fe_clear(secp256k1_fe *a) {
277  int i;
278 #ifdef VERIFY
279  a->magnitude = 0;
280  a->normalized = 1;
281 #endif
282  for (i=0; i<5; i++) {
283  a->n[i] = 0;
284  }
285 }
286 
287 static int secp256k1_fe_cmp_var(const secp256k1_fe *a, const secp256k1_fe *b) {
288  int i;
289 #ifdef VERIFY
290  VERIFY_CHECK(a->normalized);
291  VERIFY_CHECK(b->normalized);
292  secp256k1_fe_verify(a);
293  secp256k1_fe_verify(b);
294 #endif
295  for (i = 4; i >= 0; i--) {
296  if (a->n[i] > b->n[i]) {
297  return 1;
298  }
299  if (a->n[i] < b->n[i]) {
300  return -1;
301  }
302  }
303  return 0;
304 }
305 
306 static int secp256k1_fe_set_b32(secp256k1_fe *r, const unsigned char *a) {
307  int ret;
308  r->n[0] = (uint64_t)a[31]
309  | ((uint64_t)a[30] << 8)
310  | ((uint64_t)a[29] << 16)
311  | ((uint64_t)a[28] << 24)
312  | ((uint64_t)a[27] << 32)
313  | ((uint64_t)a[26] << 40)
314  | ((uint64_t)(a[25] & 0xF) << 48);
315  r->n[1] = (uint64_t)((a[25] >> 4) & 0xF)
316  | ((uint64_t)a[24] << 4)
317  | ((uint64_t)a[23] << 12)
318  | ((uint64_t)a[22] << 20)
319  | ((uint64_t)a[21] << 28)
320  | ((uint64_t)a[20] << 36)
321  | ((uint64_t)a[19] << 44);
322  r->n[2] = (uint64_t)a[18]
323  | ((uint64_t)a[17] << 8)
324  | ((uint64_t)a[16] << 16)
325  | ((uint64_t)a[15] << 24)
326  | ((uint64_t)a[14] << 32)
327  | ((uint64_t)a[13] << 40)
328  | ((uint64_t)(a[12] & 0xF) << 48);
329  r->n[3] = (uint64_t)((a[12] >> 4) & 0xF)
330  | ((uint64_t)a[11] << 4)
331  | ((uint64_t)a[10] << 12)
332  | ((uint64_t)a[9] << 20)
333  | ((uint64_t)a[8] << 28)
334  | ((uint64_t)a[7] << 36)
335  | ((uint64_t)a[6] << 44);
336  r->n[4] = (uint64_t)a[5]
337  | ((uint64_t)a[4] << 8)
338  | ((uint64_t)a[3] << 16)
339  | ((uint64_t)a[2] << 24)
340  | ((uint64_t)a[1] << 32)
341  | ((uint64_t)a[0] << 40);
342  ret = !((r->n[4] == 0x0FFFFFFFFFFFFULL) & ((r->n[3] & r->n[2] & r->n[1]) == 0xFFFFFFFFFFFFFULL) & (r->n[0] >= 0xFFFFEFFFFFC2FULL));
343 #ifdef VERIFY
344  r->magnitude = 1;
345  if (ret) {
346  r->normalized = 1;
347  secp256k1_fe_verify(r);
348  } else {
349  r->normalized = 0;
350  }
351 #endif
352  return ret;
353 }
354 
356 static void secp256k1_fe_get_b32(unsigned char *r, const secp256k1_fe *a) {
357 #ifdef VERIFY
358  VERIFY_CHECK(a->normalized);
359  secp256k1_fe_verify(a);
360 #endif
361  r[0] = (a->n[4] >> 40) & 0xFF;
362  r[1] = (a->n[4] >> 32) & 0xFF;
363  r[2] = (a->n[4] >> 24) & 0xFF;
364  r[3] = (a->n[4] >> 16) & 0xFF;
365  r[4] = (a->n[4] >> 8) & 0xFF;
366  r[5] = a->n[4] & 0xFF;
367  r[6] = (a->n[3] >> 44) & 0xFF;
368  r[7] = (a->n[3] >> 36) & 0xFF;
369  r[8] = (a->n[3] >> 28) & 0xFF;
370  r[9] = (a->n[3] >> 20) & 0xFF;
371  r[10] = (a->n[3] >> 12) & 0xFF;
372  r[11] = (a->n[3] >> 4) & 0xFF;
373  r[12] = ((a->n[2] >> 48) & 0xF) | ((a->n[3] & 0xF) << 4);
374  r[13] = (a->n[2] >> 40) & 0xFF;
375  r[14] = (a->n[2] >> 32) & 0xFF;
376  r[15] = (a->n[2] >> 24) & 0xFF;
377  r[16] = (a->n[2] >> 16) & 0xFF;
378  r[17] = (a->n[2] >> 8) & 0xFF;
379  r[18] = a->n[2] & 0xFF;
380  r[19] = (a->n[1] >> 44) & 0xFF;
381  r[20] = (a->n[1] >> 36) & 0xFF;
382  r[21] = (a->n[1] >> 28) & 0xFF;
383  r[22] = (a->n[1] >> 20) & 0xFF;
384  r[23] = (a->n[1] >> 12) & 0xFF;
385  r[24] = (a->n[1] >> 4) & 0xFF;
386  r[25] = ((a->n[0] >> 48) & 0xF) | ((a->n[1] & 0xF) << 4);
387  r[26] = (a->n[0] >> 40) & 0xFF;
388  r[27] = (a->n[0] >> 32) & 0xFF;
389  r[28] = (a->n[0] >> 24) & 0xFF;
390  r[29] = (a->n[0] >> 16) & 0xFF;
391  r[30] = (a->n[0] >> 8) & 0xFF;
392  r[31] = a->n[0] & 0xFF;
393 }
394 
395 SECP256K1_INLINE static void secp256k1_fe_negate(secp256k1_fe *r, const secp256k1_fe *a, int m) {
396 #ifdef VERIFY
397  VERIFY_CHECK(a->magnitude <= m);
398  secp256k1_fe_verify(a);
399  VERIFY_CHECK(0xFFFFEFFFFFC2FULL * 2 * (m + 1) >= 0xFFFFFFFFFFFFFULL * 2 * m);
400  VERIFY_CHECK(0xFFFFFFFFFFFFFULL * 2 * (m + 1) >= 0xFFFFFFFFFFFFFULL * 2 * m);
401  VERIFY_CHECK(0x0FFFFFFFFFFFFULL * 2 * (m + 1) >= 0x0FFFFFFFFFFFFULL * 2 * m);
402 #endif
403  r->n[0] = 0xFFFFEFFFFFC2FULL * 2 * (m + 1) - a->n[0];
404  r->n[1] = 0xFFFFFFFFFFFFFULL * 2 * (m + 1) - a->n[1];
405  r->n[2] = 0xFFFFFFFFFFFFFULL * 2 * (m + 1) - a->n[2];
406  r->n[3] = 0xFFFFFFFFFFFFFULL * 2 * (m + 1) - a->n[3];
407  r->n[4] = 0x0FFFFFFFFFFFFULL * 2 * (m + 1) - a->n[4];
408 #ifdef VERIFY
409  r->magnitude = m + 1;
410  r->normalized = 0;
411  secp256k1_fe_verify(r);
412 #endif
413 }
414 
415 SECP256K1_INLINE static void secp256k1_fe_mul_int(secp256k1_fe *r, int a) {
416  r->n[0] *= a;
417  r->n[1] *= a;
418  r->n[2] *= a;
419  r->n[3] *= a;
420  r->n[4] *= a;
421 #ifdef VERIFY
422  r->magnitude *= a;
423  r->normalized = 0;
424  secp256k1_fe_verify(r);
425 #endif
426 }
427 
428 SECP256K1_INLINE static void secp256k1_fe_add(secp256k1_fe *r, const secp256k1_fe *a) {
429 #ifdef VERIFY
430  secp256k1_fe_verify(a);
431 #endif
432  r->n[0] += a->n[0];
433  r->n[1] += a->n[1];
434  r->n[2] += a->n[2];
435  r->n[3] += a->n[3];
436  r->n[4] += a->n[4];
437 #ifdef VERIFY
438  r->magnitude += a->magnitude;
439  r->normalized = 0;
440  secp256k1_fe_verify(r);
441 #endif
442 }
443 
444 static void secp256k1_fe_mul(secp256k1_fe *r, const secp256k1_fe *a, const secp256k1_fe * SECP256K1_RESTRICT b) {
445 #ifdef VERIFY
446  VERIFY_CHECK(a->magnitude <= 8);
447  VERIFY_CHECK(b->magnitude <= 8);
448  secp256k1_fe_verify(a);
449  secp256k1_fe_verify(b);
450  VERIFY_CHECK(r != b);
451  VERIFY_CHECK(a != b);
452 #endif
453  secp256k1_fe_mul_inner(r->n, a->n, b->n);
454 #ifdef VERIFY
455  r->magnitude = 1;
456  r->normalized = 0;
457  secp256k1_fe_verify(r);
458 #endif
459 }
460 
461 static void secp256k1_fe_sqr(secp256k1_fe *r, const secp256k1_fe *a) {
462 #ifdef VERIFY
463  VERIFY_CHECK(a->magnitude <= 8);
464  secp256k1_fe_verify(a);
465 #endif
466  secp256k1_fe_sqr_inner(r->n, a->n);
467 #ifdef VERIFY
468  r->magnitude = 1;
469  r->normalized = 0;
470  secp256k1_fe_verify(r);
471 #endif
472 }
473 
474 static SECP256K1_INLINE void secp256k1_fe_cmov(secp256k1_fe *r, const secp256k1_fe *a, int flag) {
475  uint64_t mask0, mask1;
476  SECP256K1_CHECKMEM_CHECK_VERIFY(r->n, sizeof(r->n));
477  mask0 = flag + ~((uint64_t)0);
478  mask1 = ~mask0;
479  r->n[0] = (r->n[0] & mask0) | (a->n[0] & mask1);
480  r->n[1] = (r->n[1] & mask0) | (a->n[1] & mask1);
481  r->n[2] = (r->n[2] & mask0) | (a->n[2] & mask1);
482  r->n[3] = (r->n[3] & mask0) | (a->n[3] & mask1);
483  r->n[4] = (r->n[4] & mask0) | (a->n[4] & mask1);
484 #ifdef VERIFY
485  if (flag) {
486  r->magnitude = a->magnitude;
487  r->normalized = a->normalized;
488  }
489 #endif
490 }
491 
492 static SECP256K1_INLINE void secp256k1_fe_half(secp256k1_fe *r) {
493  uint64_t t0 = r->n[0], t1 = r->n[1], t2 = r->n[2], t3 = r->n[3], t4 = r->n[4];
494  uint64_t one = (uint64_t)1;
495  uint64_t mask = -(t0 & one) >> 12;
496 
497 #ifdef VERIFY
498  secp256k1_fe_verify(r);
499  VERIFY_CHECK(r->magnitude < 32);
500 #endif
501 
502  /* Bounds analysis (over the rationals).
503  *
504  * Let m = r->magnitude
505  * C = 0xFFFFFFFFFFFFFULL * 2
506  * D = 0x0FFFFFFFFFFFFULL * 2
507  *
508  * Initial bounds: t0..t3 <= C * m
509  * t4 <= D * m
510  */
511 
512  t0 += 0xFFFFEFFFFFC2FULL & mask;
513  t1 += mask;
514  t2 += mask;
515  t3 += mask;
516  t4 += mask >> 4;
517 
518  VERIFY_CHECK((t0 & one) == 0);
519 
520  /* t0..t3: added <= C/2
521  * t4: added <= D/2
522  *
523  * Current bounds: t0..t3 <= C * (m + 1/2)
524  * t4 <= D * (m + 1/2)
525  */
526 
527  r->n[0] = (t0 >> 1) + ((t1 & one) << 51);
528  r->n[1] = (t1 >> 1) + ((t2 & one) << 51);
529  r->n[2] = (t2 >> 1) + ((t3 & one) << 51);
530  r->n[3] = (t3 >> 1) + ((t4 & one) << 51);
531  r->n[4] = (t4 >> 1);
532 
533  /* t0..t3: shifted right and added <= C/4 + 1/2
534  * t4: shifted right
535  *
536  * Current bounds: t0..t3 <= C * (m/2 + 1/2)
537  * t4 <= D * (m/2 + 1/4)
538  */
539 
540 #ifdef VERIFY
541  /* Therefore the output magnitude (M) has to be set such that:
542  * t0..t3: C * M >= C * (m/2 + 1/2)
543  * t4: D * M >= D * (m/2 + 1/4)
544  *
545  * It suffices for all limbs that, for any input magnitude m:
546  * M >= m/2 + 1/2
547  *
548  * and since we want the smallest such integer value for M:
549  * M == floor(m/2) + 1
550  */
551  r->magnitude = (r->magnitude >> 1) + 1;
552  r->normalized = 0;
553  secp256k1_fe_verify(r);
554 #endif
555 }
556 
557 static SECP256K1_INLINE void secp256k1_fe_storage_cmov(secp256k1_fe_storage *r, const secp256k1_fe_storage *a, int flag) {
558  uint64_t mask0, mask1;
559  SECP256K1_CHECKMEM_CHECK_VERIFY(r->n, sizeof(r->n));
560  mask0 = flag + ~((uint64_t)0);
561  mask1 = ~mask0;
562  r->n[0] = (r->n[0] & mask0) | (a->n[0] & mask1);
563  r->n[1] = (r->n[1] & mask0) | (a->n[1] & mask1);
564  r->n[2] = (r->n[2] & mask0) | (a->n[2] & mask1);
565  r->n[3] = (r->n[3] & mask0) | (a->n[3] & mask1);
566 }
567 
568 static void secp256k1_fe_to_storage(secp256k1_fe_storage *r, const secp256k1_fe *a) {
569 #ifdef VERIFY
570  VERIFY_CHECK(a->normalized);
571 #endif
572  r->n[0] = a->n[0] | a->n[1] << 52;
573  r->n[1] = a->n[1] >> 12 | a->n[2] << 40;
574  r->n[2] = a->n[2] >> 24 | a->n[3] << 28;
575  r->n[3] = a->n[3] >> 36 | a->n[4] << 16;
576 }
577 
578 static SECP256K1_INLINE void secp256k1_fe_from_storage(secp256k1_fe *r, const secp256k1_fe_storage *a) {
579  r->n[0] = a->n[0] & 0xFFFFFFFFFFFFFULL;
580  r->n[1] = a->n[0] >> 52 | ((a->n[1] << 12) & 0xFFFFFFFFFFFFFULL);
581  r->n[2] = a->n[1] >> 40 | ((a->n[2] << 24) & 0xFFFFFFFFFFFFFULL);
582  r->n[3] = a->n[2] >> 28 | ((a->n[3] << 36) & 0xFFFFFFFFFFFFFULL);
583  r->n[4] = a->n[3] >> 16;
584 #ifdef VERIFY
585  r->magnitude = 1;
586  r->normalized = 1;
587  secp256k1_fe_verify(r);
588 #endif
589 }
590 
591 static void secp256k1_fe_from_signed62(secp256k1_fe *r, const secp256k1_modinv64_signed62 *a) {
592  const uint64_t M52 = UINT64_MAX >> 12;
593  const uint64_t a0 = a->v[0], a1 = a->v[1], a2 = a->v[2], a3 = a->v[3], a4 = a->v[4];
594 
595  /* The output from secp256k1_modinv64{_var} should be normalized to range [0,modulus), and
596  * have limbs in [0,2^62). The modulus is < 2^256, so the top limb must be below 2^(256-62*4).
597  */
598  VERIFY_CHECK(a0 >> 62 == 0);
599  VERIFY_CHECK(a1 >> 62 == 0);
600  VERIFY_CHECK(a2 >> 62 == 0);
601  VERIFY_CHECK(a3 >> 62 == 0);
602  VERIFY_CHECK(a4 >> 8 == 0);
603 
604  r->n[0] = a0 & M52;
605  r->n[1] = (a0 >> 52 | a1 << 10) & M52;
606  r->n[2] = (a1 >> 42 | a2 << 20) & M52;
607  r->n[3] = (a2 >> 32 | a3 << 30) & M52;
608  r->n[4] = (a3 >> 22 | a4 << 40);
609 
610 #ifdef VERIFY
611  r->magnitude = 1;
612  r->normalized = 1;
613  secp256k1_fe_verify(r);
614 #endif
615 }
616 
617 static void secp256k1_fe_to_signed62(secp256k1_modinv64_signed62 *r, const secp256k1_fe *a) {
618  const uint64_t M62 = UINT64_MAX >> 2;
619  const uint64_t a0 = a->n[0], a1 = a->n[1], a2 = a->n[2], a3 = a->n[3], a4 = a->n[4];
620 
621 #ifdef VERIFY
622  VERIFY_CHECK(a->normalized);
623 #endif
624 
625  r->v[0] = (a0 | a1 << 52) & M62;
626  r->v[1] = (a1 >> 10 | a2 << 42) & M62;
627  r->v[2] = (a2 >> 20 | a3 << 32) & M62;
628  r->v[3] = (a3 >> 30 | a4 << 22) & M62;
629  r->v[4] = a4 >> 40;
630 }
631 
632 static const secp256k1_modinv64_modinfo secp256k1_const_modinfo_fe = {
633  {{-0x1000003D1LL, 0, 0, 0, 256}},
634  0x27C7F6E22DDACACFLL
635 };
636 
637 static void secp256k1_fe_inv(secp256k1_fe *r, const secp256k1_fe *x) {
638  secp256k1_fe tmp;
640 
641  tmp = *x;
642  secp256k1_fe_normalize(&tmp);
643  secp256k1_fe_to_signed62(&s, &tmp);
644  secp256k1_modinv64(&s, &secp256k1_const_modinfo_fe);
645  secp256k1_fe_from_signed62(r, &s);
646 
647 #ifdef VERIFY
648  VERIFY_CHECK(secp256k1_fe_normalizes_to_zero(r) == secp256k1_fe_normalizes_to_zero(&tmp));
649 #endif
650 }
651 
652 static void secp256k1_fe_inv_var(secp256k1_fe *r, const secp256k1_fe *x) {
653  secp256k1_fe tmp;
655 
656  tmp = *x;
657  secp256k1_fe_normalize_var(&tmp);
658  secp256k1_fe_to_signed62(&s, &tmp);
659  secp256k1_modinv64_var(&s, &secp256k1_const_modinfo_fe);
660  secp256k1_fe_from_signed62(r, &s);
661 
662 #ifdef VERIFY
663  VERIFY_CHECK(secp256k1_fe_normalizes_to_zero(r) == secp256k1_fe_normalizes_to_zero(&tmp));
664 #endif
665 }
666 
667 #endif /* SECP256K1_FIELD_REPR_IMPL_H */
#define VERIFY_CHECK(cond)
Definition: util.h:96
t0
Definition: pow22523.h:53
#define SECP256K1_INLINE
Definition: secp256k1.h:131
t3
Definition: pow225521.h:103
unsigned __int64 uint64_t
Definition: stdint.h:136
uint32_t n[10]
Definition: field_10x26.h:16
#define UINT64_MAX
Definition: stdint.h:189
const GenericPointer< typename T::ValueType > T2 T::AllocatorType & a
Definition: pointer.h:1124
t2
Definition: pow22523.h:103
t1
Definition: pow22523.h:58
#define SECP256K1_CHECKMEM_CHECK_VERIFY(p, len)
Definition: checkmem.h:85
#define SECP256K1_RESTRICT
Definition: util.h:137