Electroneum
field_10x26_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 "modinv32_impl.h"
14 
24 #ifdef VERIFY
25 static void secp256k1_fe_verify(const secp256k1_fe *a) {
26  const uint32_t *d = a->n;
27  int m = a->normalized ? 1 : 2 * a->magnitude, r = 1;
28  r &= (d[0] <= 0x3FFFFFFUL * m);
29  r &= (d[1] <= 0x3FFFFFFUL * m);
30  r &= (d[2] <= 0x3FFFFFFUL * m);
31  r &= (d[3] <= 0x3FFFFFFUL * m);
32  r &= (d[4] <= 0x3FFFFFFUL * m);
33  r &= (d[5] <= 0x3FFFFFFUL * m);
34  r &= (d[6] <= 0x3FFFFFFUL * m);
35  r &= (d[7] <= 0x3FFFFFFUL * m);
36  r &= (d[8] <= 0x3FFFFFFUL * m);
37  r &= (d[9] <= 0x03FFFFFUL * m);
38  r &= (a->magnitude >= 0);
39  r &= (a->magnitude <= 32);
40  if (a->normalized) {
41  r &= (a->magnitude <= 1);
42  if (r && (d[9] == 0x03FFFFFUL)) {
43  uint32_t mid = d[8] & d[7] & d[6] & d[5] & d[4] & d[3] & d[2];
44  if (mid == 0x3FFFFFFUL) {
45  r &= ((d[1] + 0x40UL + ((d[0] + 0x3D1UL) >> 26)) <= 0x3FFFFFFUL);
46  }
47  }
48  }
49  VERIFY_CHECK(r == 1);
50 }
51 #endif
52 
53 static void secp256k1_fe_get_bounds(secp256k1_fe *r, int m) {
54  VERIFY_CHECK(m >= 0);
55  VERIFY_CHECK(m <= 2048);
56  r->n[0] = 0x3FFFFFFUL * 2 * m;
57  r->n[1] = 0x3FFFFFFUL * 2 * m;
58  r->n[2] = 0x3FFFFFFUL * 2 * m;
59  r->n[3] = 0x3FFFFFFUL * 2 * m;
60  r->n[4] = 0x3FFFFFFUL * 2 * m;
61  r->n[5] = 0x3FFFFFFUL * 2 * m;
62  r->n[6] = 0x3FFFFFFUL * 2 * m;
63  r->n[7] = 0x3FFFFFFUL * 2 * m;
64  r->n[8] = 0x3FFFFFFUL * 2 * m;
65  r->n[9] = 0x03FFFFFUL * 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  uint32_t t0 = r->n[0], t1 = r->n[1], t2 = r->n[2], t3 = r->n[3], t4 = r->n[4],
75  t5 = r->n[5], t6 = r->n[6], t7 = r->n[7], t8 = r->n[8], t9 = r->n[9];
76 
77  /* Reduce t9 at the start so there will be at most a single carry from the first pass */
78  uint32_t m;
79  uint32_t x = t9 >> 22; t9 &= 0x03FFFFFUL;
80 
81  /* The first pass ensures the magnitude is 1, ... */
82  t0 += x * 0x3D1UL; t1 += (x << 6);
83  t1 += (t0 >> 26); t0 &= 0x3FFFFFFUL;
84  t2 += (t1 >> 26); t1 &= 0x3FFFFFFUL;
85  t3 += (t2 >> 26); t2 &= 0x3FFFFFFUL; m = t2;
86  t4 += (t3 >> 26); t3 &= 0x3FFFFFFUL; m &= t3;
87  t5 += (t4 >> 26); t4 &= 0x3FFFFFFUL; m &= t4;
88  t6 += (t5 >> 26); t5 &= 0x3FFFFFFUL; m &= t5;
89  t7 += (t6 >> 26); t6 &= 0x3FFFFFFUL; m &= t6;
90  t8 += (t7 >> 26); t7 &= 0x3FFFFFFUL; m &= t7;
91  t9 += (t8 >> 26); t8 &= 0x3FFFFFFUL; m &= t8;
92 
93  /* ... except for a possible carry at bit 22 of t9 (i.e. bit 256 of the field element) */
94  VERIFY_CHECK(t9 >> 23 == 0);
95 
96  /* At most a single final reduction is needed; check if the value is >= the field characteristic */
97  x = (t9 >> 22) | ((t9 == 0x03FFFFFUL) & (m == 0x3FFFFFFUL)
98  & ((t1 + 0x40UL + ((t0 + 0x3D1UL) >> 26)) > 0x3FFFFFFUL));
99 
100  /* Apply the final reduction (for constant-time behaviour, we do it always) */
101  t0 += x * 0x3D1UL; t1 += (x << 6);
102  t1 += (t0 >> 26); t0 &= 0x3FFFFFFUL;
103  t2 += (t1 >> 26); t1 &= 0x3FFFFFFUL;
104  t3 += (t2 >> 26); t2 &= 0x3FFFFFFUL;
105  t4 += (t3 >> 26); t3 &= 0x3FFFFFFUL;
106  t5 += (t4 >> 26); t4 &= 0x3FFFFFFUL;
107  t6 += (t5 >> 26); t5 &= 0x3FFFFFFUL;
108  t7 += (t6 >> 26); t6 &= 0x3FFFFFFUL;
109  t8 += (t7 >> 26); t7 &= 0x3FFFFFFUL;
110  t9 += (t8 >> 26); t8 &= 0x3FFFFFFUL;
111 
112  /* If t9 didn't carry to bit 22 already, then it should have after any final reduction */
113  VERIFY_CHECK(t9 >> 22 == x);
114 
115  /* Mask off the possible multiple of 2^256 from the final reduction */
116  t9 &= 0x03FFFFFUL;
117 
118  r->n[0] = t0; r->n[1] = t1; r->n[2] = t2; r->n[3] = t3; r->n[4] = t4;
119  r->n[5] = t5; r->n[6] = t6; r->n[7] = t7; r->n[8] = t8; r->n[9] = t9;
120 
121 #ifdef VERIFY
122  r->magnitude = 1;
123  r->normalized = 1;
124  secp256k1_fe_verify(r);
125 #endif
126 }
127 
128 static void secp256k1_fe_normalize_weak(secp256k1_fe *r) {
129  uint32_t t0 = r->n[0], t1 = r->n[1], t2 = r->n[2], t3 = r->n[3], t4 = r->n[4],
130  t5 = r->n[5], t6 = r->n[6], t7 = r->n[7], t8 = r->n[8], t9 = r->n[9];
131 
132  /* Reduce t9 at the start so there will be at most a single carry from the first pass */
133  uint32_t x = t9 >> 22; t9 &= 0x03FFFFFUL;
134 
135  /* The first pass ensures the magnitude is 1, ... */
136  t0 += x * 0x3D1UL; t1 += (x << 6);
137  t1 += (t0 >> 26); t0 &= 0x3FFFFFFUL;
138  t2 += (t1 >> 26); t1 &= 0x3FFFFFFUL;
139  t3 += (t2 >> 26); t2 &= 0x3FFFFFFUL;
140  t4 += (t3 >> 26); t3 &= 0x3FFFFFFUL;
141  t5 += (t4 >> 26); t4 &= 0x3FFFFFFUL;
142  t6 += (t5 >> 26); t5 &= 0x3FFFFFFUL;
143  t7 += (t6 >> 26); t6 &= 0x3FFFFFFUL;
144  t8 += (t7 >> 26); t7 &= 0x3FFFFFFUL;
145  t9 += (t8 >> 26); t8 &= 0x3FFFFFFUL;
146 
147  /* ... except for a possible carry at bit 22 of t9 (i.e. bit 256 of the field element) */
148  VERIFY_CHECK(t9 >> 23 == 0);
149 
150  r->n[0] = t0; r->n[1] = t1; r->n[2] = t2; r->n[3] = t3; r->n[4] = t4;
151  r->n[5] = t5; r->n[6] = t6; r->n[7] = t7; r->n[8] = t8; r->n[9] = t9;
152 
153 #ifdef VERIFY
154  r->magnitude = 1;
155  secp256k1_fe_verify(r);
156 #endif
157 }
158 
159 static void secp256k1_fe_normalize_var(secp256k1_fe *r) {
160  uint32_t t0 = r->n[0], t1 = r->n[1], t2 = r->n[2], t3 = r->n[3], t4 = r->n[4],
161  t5 = r->n[5], t6 = r->n[6], t7 = r->n[7], t8 = r->n[8], t9 = r->n[9];
162 
163  /* Reduce t9 at the start so there will be at most a single carry from the first pass */
164  uint32_t m;
165  uint32_t x = t9 >> 22; t9 &= 0x03FFFFFUL;
166 
167  /* The first pass ensures the magnitude is 1, ... */
168  t0 += x * 0x3D1UL; t1 += (x << 6);
169  t1 += (t0 >> 26); t0 &= 0x3FFFFFFUL;
170  t2 += (t1 >> 26); t1 &= 0x3FFFFFFUL;
171  t3 += (t2 >> 26); t2 &= 0x3FFFFFFUL; m = t2;
172  t4 += (t3 >> 26); t3 &= 0x3FFFFFFUL; m &= t3;
173  t5 += (t4 >> 26); t4 &= 0x3FFFFFFUL; m &= t4;
174  t6 += (t5 >> 26); t5 &= 0x3FFFFFFUL; m &= t5;
175  t7 += (t6 >> 26); t6 &= 0x3FFFFFFUL; m &= t6;
176  t8 += (t7 >> 26); t7 &= 0x3FFFFFFUL; m &= t7;
177  t9 += (t8 >> 26); t8 &= 0x3FFFFFFUL; m &= t8;
178 
179  /* ... except for a possible carry at bit 22 of t9 (i.e. bit 256 of the field element) */
180  VERIFY_CHECK(t9 >> 23 == 0);
181 
182  /* At most a single final reduction is needed; check if the value is >= the field characteristic */
183  x = (t9 >> 22) | ((t9 == 0x03FFFFFUL) & (m == 0x3FFFFFFUL)
184  & ((t1 + 0x40UL + ((t0 + 0x3D1UL) >> 26)) > 0x3FFFFFFUL));
185 
186  if (x) {
187  t0 += 0x3D1UL; t1 += (x << 6);
188  t1 += (t0 >> 26); t0 &= 0x3FFFFFFUL;
189  t2 += (t1 >> 26); t1 &= 0x3FFFFFFUL;
190  t3 += (t2 >> 26); t2 &= 0x3FFFFFFUL;
191  t4 += (t3 >> 26); t3 &= 0x3FFFFFFUL;
192  t5 += (t4 >> 26); t4 &= 0x3FFFFFFUL;
193  t6 += (t5 >> 26); t5 &= 0x3FFFFFFUL;
194  t7 += (t6 >> 26); t6 &= 0x3FFFFFFUL;
195  t8 += (t7 >> 26); t7 &= 0x3FFFFFFUL;
196  t9 += (t8 >> 26); t8 &= 0x3FFFFFFUL;
197 
198  /* If t9 didn't carry to bit 22 already, then it should have after any final reduction */
199  VERIFY_CHECK(t9 >> 22 == x);
200 
201  /* Mask off the possible multiple of 2^256 from the final reduction */
202  t9 &= 0x03FFFFFUL;
203  }
204 
205  r->n[0] = t0; r->n[1] = t1; r->n[2] = t2; r->n[3] = t3; r->n[4] = t4;
206  r->n[5] = t5; r->n[6] = t6; r->n[7] = t7; r->n[8] = t8; r->n[9] = t9;
207 
208 #ifdef VERIFY
209  r->magnitude = 1;
210  r->normalized = 1;
211  secp256k1_fe_verify(r);
212 #endif
213 }
214 
215 static int secp256k1_fe_normalizes_to_zero(const secp256k1_fe *r) {
216  uint32_t t0 = r->n[0], t1 = r->n[1], t2 = r->n[2], t3 = r->n[3], t4 = r->n[4],
217  t5 = r->n[5], t6 = r->n[6], t7 = r->n[7], t8 = r->n[8], t9 = r->n[9];
218 
219  /* z0 tracks a possible raw value of 0, z1 tracks a possible raw value of P */
220  uint32_t z0, z1;
221 
222  /* Reduce t9 at the start so there will be at most a single carry from the first pass */
223  uint32_t x = t9 >> 22; t9 &= 0x03FFFFFUL;
224 
225  /* The first pass ensures the magnitude is 1, ... */
226  t0 += x * 0x3D1UL; t1 += (x << 6);
227  t1 += (t0 >> 26); t0 &= 0x3FFFFFFUL; z0 = t0; z1 = t0 ^ 0x3D0UL;
228  t2 += (t1 >> 26); t1 &= 0x3FFFFFFUL; z0 |= t1; z1 &= t1 ^ 0x40UL;
229  t3 += (t2 >> 26); t2 &= 0x3FFFFFFUL; z0 |= t2; z1 &= t2;
230  t4 += (t3 >> 26); t3 &= 0x3FFFFFFUL; z0 |= t3; z1 &= t3;
231  t5 += (t4 >> 26); t4 &= 0x3FFFFFFUL; z0 |= t4; z1 &= t4;
232  t6 += (t5 >> 26); t5 &= 0x3FFFFFFUL; z0 |= t5; z1 &= t5;
233  t7 += (t6 >> 26); t6 &= 0x3FFFFFFUL; z0 |= t6; z1 &= t6;
234  t8 += (t7 >> 26); t7 &= 0x3FFFFFFUL; z0 |= t7; z1 &= t7;
235  t9 += (t8 >> 26); t8 &= 0x3FFFFFFUL; z0 |= t8; z1 &= t8;
236  z0 |= t9; z1 &= t9 ^ 0x3C00000UL;
237 
238  /* ... except for a possible carry at bit 22 of t9 (i.e. bit 256 of the field element) */
239  VERIFY_CHECK(t9 >> 23 == 0);
240 
241  return (z0 == 0) | (z1 == 0x3FFFFFFUL);
242 }
243 
244 static int secp256k1_fe_normalizes_to_zero_var(const secp256k1_fe *r) {
245  uint32_t t0, t1, t2, t3, t4, t5, t6, t7, t8, t9;
246  uint32_t z0, z1;
247  uint32_t x;
248 
249  t0 = r->n[0];
250  t9 = r->n[9];
251 
252  /* Reduce t9 at the start so there will be at most a single carry from the first pass */
253  x = t9 >> 22;
254 
255  /* The first pass ensures the magnitude is 1, ... */
256  t0 += x * 0x3D1UL;
257 
258  /* z0 tracks a possible raw value of 0, z1 tracks a possible raw value of P */
259  z0 = t0 & 0x3FFFFFFUL;
260  z1 = z0 ^ 0x3D0UL;
261 
262  /* Fast return path should catch the majority of cases */
263  if ((z0 != 0UL) & (z1 != 0x3FFFFFFUL)) {
264  return 0;
265  }
266 
267  t1 = r->n[1];
268  t2 = r->n[2];
269  t3 = r->n[3];
270  t4 = r->n[4];
271  t5 = r->n[5];
272  t6 = r->n[6];
273  t7 = r->n[7];
274  t8 = r->n[8];
275 
276  t9 &= 0x03FFFFFUL;
277  t1 += (x << 6);
278 
279  t1 += (t0 >> 26);
280  t2 += (t1 >> 26); t1 &= 0x3FFFFFFUL; z0 |= t1; z1 &= t1 ^ 0x40UL;
281  t3 += (t2 >> 26); t2 &= 0x3FFFFFFUL; z0 |= t2; z1 &= t2;
282  t4 += (t3 >> 26); t3 &= 0x3FFFFFFUL; z0 |= t3; z1 &= t3;
283  t5 += (t4 >> 26); t4 &= 0x3FFFFFFUL; z0 |= t4; z1 &= t4;
284  t6 += (t5 >> 26); t5 &= 0x3FFFFFFUL; z0 |= t5; z1 &= t5;
285  t7 += (t6 >> 26); t6 &= 0x3FFFFFFUL; z0 |= t6; z1 &= t6;
286  t8 += (t7 >> 26); t7 &= 0x3FFFFFFUL; z0 |= t7; z1 &= t7;
287  t9 += (t8 >> 26); t8 &= 0x3FFFFFFUL; z0 |= t8; z1 &= t8;
288  z0 |= t9; z1 &= t9 ^ 0x3C00000UL;
289 
290  /* ... except for a possible carry at bit 22 of t9 (i.e. bit 256 of the field element) */
291  VERIFY_CHECK(t9 >> 23 == 0);
292 
293  return (z0 == 0) | (z1 == 0x3FFFFFFUL);
294 }
295 
296 SECP256K1_INLINE static void secp256k1_fe_set_int(secp256k1_fe *r, int a) {
297  VERIFY_CHECK(0 <= a && a <= 0x7FFF);
298  r->n[0] = a;
299  r->n[1] = r->n[2] = r->n[3] = r->n[4] = r->n[5] = r->n[6] = r->n[7] = r->n[8] = r->n[9] = 0;
300 #ifdef VERIFY
301  r->magnitude = (a != 0);
302  r->normalized = 1;
303  secp256k1_fe_verify(r);
304 #endif
305 }
306 
307 SECP256K1_INLINE static int secp256k1_fe_is_zero(const secp256k1_fe *a) {
308  const uint32_t *t = a->n;
309 #ifdef VERIFY
310  VERIFY_CHECK(a->normalized);
311  secp256k1_fe_verify(a);
312 #endif
313  return (t[0] | t[1] | t[2] | t[3] | t[4] | t[5] | t[6] | t[7] | t[8] | t[9]) == 0;
314 }
315 
316 SECP256K1_INLINE static int secp256k1_fe_is_odd(const secp256k1_fe *a) {
317 #ifdef VERIFY
318  VERIFY_CHECK(a->normalized);
319  secp256k1_fe_verify(a);
320 #endif
321  return a->n[0] & 1;
322 }
323 
324 SECP256K1_INLINE static void secp256k1_fe_clear(secp256k1_fe *a) {
325  int i;
326 #ifdef VERIFY
327  a->magnitude = 0;
328  a->normalized = 1;
329 #endif
330  for (i=0; i<10; i++) {
331  a->n[i] = 0;
332  }
333 }
334 
335 static int secp256k1_fe_cmp_var(const secp256k1_fe *a, const secp256k1_fe *b) {
336  int i;
337 #ifdef VERIFY
338  VERIFY_CHECK(a->normalized);
339  VERIFY_CHECK(b->normalized);
340  secp256k1_fe_verify(a);
341  secp256k1_fe_verify(b);
342 #endif
343  for (i = 9; i >= 0; i--) {
344  if (a->n[i] > b->n[i]) {
345  return 1;
346  }
347  if (a->n[i] < b->n[i]) {
348  return -1;
349  }
350  }
351  return 0;
352 }
353 
354 static int secp256k1_fe_set_b32(secp256k1_fe *r, const unsigned char *a) {
355  int ret;
356  r->n[0] = (uint32_t)a[31] | ((uint32_t)a[30] << 8) | ((uint32_t)a[29] << 16) | ((uint32_t)(a[28] & 0x3) << 24);
357  r->n[1] = (uint32_t)((a[28] >> 2) & 0x3f) | ((uint32_t)a[27] << 6) | ((uint32_t)a[26] << 14) | ((uint32_t)(a[25] & 0xf) << 22);
358  r->n[2] = (uint32_t)((a[25] >> 4) & 0xf) | ((uint32_t)a[24] << 4) | ((uint32_t)a[23] << 12) | ((uint32_t)(a[22] & 0x3f) << 20);
359  r->n[3] = (uint32_t)((a[22] >> 6) & 0x3) | ((uint32_t)a[21] << 2) | ((uint32_t)a[20] << 10) | ((uint32_t)a[19] << 18);
360  r->n[4] = (uint32_t)a[18] | ((uint32_t)a[17] << 8) | ((uint32_t)a[16] << 16) | ((uint32_t)(a[15] & 0x3) << 24);
361  r->n[5] = (uint32_t)((a[15] >> 2) & 0x3f) | ((uint32_t)a[14] << 6) | ((uint32_t)a[13] << 14) | ((uint32_t)(a[12] & 0xf) << 22);
362  r->n[6] = (uint32_t)((a[12] >> 4) & 0xf) | ((uint32_t)a[11] << 4) | ((uint32_t)a[10] << 12) | ((uint32_t)(a[9] & 0x3f) << 20);
363  r->n[7] = (uint32_t)((a[9] >> 6) & 0x3) | ((uint32_t)a[8] << 2) | ((uint32_t)a[7] << 10) | ((uint32_t)a[6] << 18);
364  r->n[8] = (uint32_t)a[5] | ((uint32_t)a[4] << 8) | ((uint32_t)a[3] << 16) | ((uint32_t)(a[2] & 0x3) << 24);
365  r->n[9] = (uint32_t)((a[2] >> 2) & 0x3f) | ((uint32_t)a[1] << 6) | ((uint32_t)a[0] << 14);
366 
367  ret = !((r->n[9] == 0x3FFFFFUL) & ((r->n[8] & r->n[7] & r->n[6] & r->n[5] & r->n[4] & r->n[3] & r->n[2]) == 0x3FFFFFFUL) & ((r->n[1] + 0x40UL + ((r->n[0] + 0x3D1UL) >> 26)) > 0x3FFFFFFUL));
368 #ifdef VERIFY
369  r->magnitude = 1;
370  if (ret) {
371  r->normalized = 1;
372  secp256k1_fe_verify(r);
373  } else {
374  r->normalized = 0;
375  }
376 #endif
377  return ret;
378 }
379 
381 static void secp256k1_fe_get_b32(unsigned char *r, const secp256k1_fe *a) {
382 #ifdef VERIFY
383  VERIFY_CHECK(a->normalized);
384  secp256k1_fe_verify(a);
385 #endif
386  r[0] = (a->n[9] >> 14) & 0xff;
387  r[1] = (a->n[9] >> 6) & 0xff;
388  r[2] = ((a->n[9] & 0x3F) << 2) | ((a->n[8] >> 24) & 0x3);
389  r[3] = (a->n[8] >> 16) & 0xff;
390  r[4] = (a->n[8] >> 8) & 0xff;
391  r[5] = a->n[8] & 0xff;
392  r[6] = (a->n[7] >> 18) & 0xff;
393  r[7] = (a->n[7] >> 10) & 0xff;
394  r[8] = (a->n[7] >> 2) & 0xff;
395  r[9] = ((a->n[7] & 0x3) << 6) | ((a->n[6] >> 20) & 0x3f);
396  r[10] = (a->n[6] >> 12) & 0xff;
397  r[11] = (a->n[6] >> 4) & 0xff;
398  r[12] = ((a->n[6] & 0xf) << 4) | ((a->n[5] >> 22) & 0xf);
399  r[13] = (a->n[5] >> 14) & 0xff;
400  r[14] = (a->n[5] >> 6) & 0xff;
401  r[15] = ((a->n[5] & 0x3f) << 2) | ((a->n[4] >> 24) & 0x3);
402  r[16] = (a->n[4] >> 16) & 0xff;
403  r[17] = (a->n[4] >> 8) & 0xff;
404  r[18] = a->n[4] & 0xff;
405  r[19] = (a->n[3] >> 18) & 0xff;
406  r[20] = (a->n[3] >> 10) & 0xff;
407  r[21] = (a->n[3] >> 2) & 0xff;
408  r[22] = ((a->n[3] & 0x3) << 6) | ((a->n[2] >> 20) & 0x3f);
409  r[23] = (a->n[2] >> 12) & 0xff;
410  r[24] = (a->n[2] >> 4) & 0xff;
411  r[25] = ((a->n[2] & 0xf) << 4) | ((a->n[1] >> 22) & 0xf);
412  r[26] = (a->n[1] >> 14) & 0xff;
413  r[27] = (a->n[1] >> 6) & 0xff;
414  r[28] = ((a->n[1] & 0x3f) << 2) | ((a->n[0] >> 24) & 0x3);
415  r[29] = (a->n[0] >> 16) & 0xff;
416  r[30] = (a->n[0] >> 8) & 0xff;
417  r[31] = a->n[0] & 0xff;
418 }
419 
420 SECP256K1_INLINE static void secp256k1_fe_negate(secp256k1_fe *r, const secp256k1_fe *a, int m) {
421 #ifdef VERIFY
422  VERIFY_CHECK(a->magnitude <= m);
423  secp256k1_fe_verify(a);
424  VERIFY_CHECK(0x3FFFC2FUL * 2 * (m + 1) >= 0x3FFFFFFUL * 2 * m);
425  VERIFY_CHECK(0x3FFFFBFUL * 2 * (m + 1) >= 0x3FFFFFFUL * 2 * m);
426  VERIFY_CHECK(0x3FFFFFFUL * 2 * (m + 1) >= 0x3FFFFFFUL * 2 * m);
427  VERIFY_CHECK(0x03FFFFFUL * 2 * (m + 1) >= 0x03FFFFFUL * 2 * m);
428 #endif
429  r->n[0] = 0x3FFFC2FUL * 2 * (m + 1) - a->n[0];
430  r->n[1] = 0x3FFFFBFUL * 2 * (m + 1) - a->n[1];
431  r->n[2] = 0x3FFFFFFUL * 2 * (m + 1) - a->n[2];
432  r->n[3] = 0x3FFFFFFUL * 2 * (m + 1) - a->n[3];
433  r->n[4] = 0x3FFFFFFUL * 2 * (m + 1) - a->n[4];
434  r->n[5] = 0x3FFFFFFUL * 2 * (m + 1) - a->n[5];
435  r->n[6] = 0x3FFFFFFUL * 2 * (m + 1) - a->n[6];
436  r->n[7] = 0x3FFFFFFUL * 2 * (m + 1) - a->n[7];
437  r->n[8] = 0x3FFFFFFUL * 2 * (m + 1) - a->n[8];
438  r->n[9] = 0x03FFFFFUL * 2 * (m + 1) - a->n[9];
439 #ifdef VERIFY
440  r->magnitude = m + 1;
441  r->normalized = 0;
442  secp256k1_fe_verify(r);
443 #endif
444 }
445 
446 SECP256K1_INLINE static void secp256k1_fe_mul_int(secp256k1_fe *r, int a) {
447  r->n[0] *= a;
448  r->n[1] *= a;
449  r->n[2] *= a;
450  r->n[3] *= a;
451  r->n[4] *= a;
452  r->n[5] *= a;
453  r->n[6] *= a;
454  r->n[7] *= a;
455  r->n[8] *= a;
456  r->n[9] *= a;
457 #ifdef VERIFY
458  r->magnitude *= a;
459  r->normalized = 0;
460  secp256k1_fe_verify(r);
461 #endif
462 }
463 
464 SECP256K1_INLINE static void secp256k1_fe_add(secp256k1_fe *r, const secp256k1_fe *a) {
465 #ifdef VERIFY
466  secp256k1_fe_verify(a);
467 #endif
468  r->n[0] += a->n[0];
469  r->n[1] += a->n[1];
470  r->n[2] += a->n[2];
471  r->n[3] += a->n[3];
472  r->n[4] += a->n[4];
473  r->n[5] += a->n[5];
474  r->n[6] += a->n[6];
475  r->n[7] += a->n[7];
476  r->n[8] += a->n[8];
477  r->n[9] += a->n[9];
478 #ifdef VERIFY
479  r->magnitude += a->magnitude;
480  r->normalized = 0;
481  secp256k1_fe_verify(r);
482 #endif
483 }
484 
485 #if defined(USE_EXTERNAL_ASM)
486 
487 /* External assembler implementation */
488 void secp256k1_fe_mul_inner(uint32_t *r, const uint32_t *a, const uint32_t * SECP256K1_RESTRICT b);
489 void secp256k1_fe_sqr_inner(uint32_t *r, const uint32_t *a);
490 
491 #else
492 
493 #ifdef VERIFY
494 #define VERIFY_BITS(x, n) VERIFY_CHECK(((x) >> (n)) == 0)
495 #else
496 #define VERIFY_BITS(x, n) do { } while(0)
497 #endif
498 
499 SECP256K1_INLINE static void secp256k1_fe_mul_inner(uint32_t *r, const uint32_t *a, const uint32_t * SECP256K1_RESTRICT b) {
500  uint64_t c, d;
501  uint64_t u0, u1, u2, u3, u4, u5, u6, u7, u8;
502  uint32_t t9, t1, t0, t2, t3, t4, t5, t6, t7;
503  const uint32_t M = 0x3FFFFFFUL, R0 = 0x3D10UL, R1 = 0x400UL;
504 
505  VERIFY_BITS(a[0], 30);
506  VERIFY_BITS(a[1], 30);
507  VERIFY_BITS(a[2], 30);
508  VERIFY_BITS(a[3], 30);
509  VERIFY_BITS(a[4], 30);
510  VERIFY_BITS(a[5], 30);
511  VERIFY_BITS(a[6], 30);
512  VERIFY_BITS(a[7], 30);
513  VERIFY_BITS(a[8], 30);
514  VERIFY_BITS(a[9], 26);
515  VERIFY_BITS(b[0], 30);
516  VERIFY_BITS(b[1], 30);
517  VERIFY_BITS(b[2], 30);
518  VERIFY_BITS(b[3], 30);
519  VERIFY_BITS(b[4], 30);
520  VERIFY_BITS(b[5], 30);
521  VERIFY_BITS(b[6], 30);
522  VERIFY_BITS(b[7], 30);
523  VERIFY_BITS(b[8], 30);
524  VERIFY_BITS(b[9], 26);
525 
532  d = (uint64_t)a[0] * b[9]
533  + (uint64_t)a[1] * b[8]
534  + (uint64_t)a[2] * b[7]
535  + (uint64_t)a[3] * b[6]
536  + (uint64_t)a[4] * b[5]
537  + (uint64_t)a[5] * b[4]
538  + (uint64_t)a[6] * b[3]
539  + (uint64_t)a[7] * b[2]
540  + (uint64_t)a[8] * b[1]
541  + (uint64_t)a[9] * b[0];
542  /* VERIFY_BITS(d, 64); */
543  /* [d 0 0 0 0 0 0 0 0 0] = [p9 0 0 0 0 0 0 0 0 0] */
544  t9 = d & M; d >>= 26;
545  VERIFY_BITS(t9, 26);
546  VERIFY_BITS(d, 38);
547  /* [d t9 0 0 0 0 0 0 0 0 0] = [p9 0 0 0 0 0 0 0 0 0] */
548 
549  c = (uint64_t)a[0] * b[0];
550  VERIFY_BITS(c, 60);
551  /* [d t9 0 0 0 0 0 0 0 0 c] = [p9 0 0 0 0 0 0 0 0 p0] */
552  d += (uint64_t)a[1] * b[9]
553  + (uint64_t)a[2] * b[8]
554  + (uint64_t)a[3] * b[7]
555  + (uint64_t)a[4] * b[6]
556  + (uint64_t)a[5] * b[5]
557  + (uint64_t)a[6] * b[4]
558  + (uint64_t)a[7] * b[3]
559  + (uint64_t)a[8] * b[2]
560  + (uint64_t)a[9] * b[1];
561  VERIFY_BITS(d, 63);
562  /* [d t9 0 0 0 0 0 0 0 0 c] = [p10 p9 0 0 0 0 0 0 0 0 p0] */
563  u0 = d & M; d >>= 26; c += u0 * R0;
564  VERIFY_BITS(u0, 26);
565  VERIFY_BITS(d, 37);
566  VERIFY_BITS(c, 61);
567  /* [d u0 t9 0 0 0 0 0 0 0 0 c-u0*R0] = [p10 p9 0 0 0 0 0 0 0 0 p0] */
568  t0 = c & M; c >>= 26; c += u0 * R1;
569  VERIFY_BITS(t0, 26);
570  VERIFY_BITS(c, 37);
571  /* [d u0 t9 0 0 0 0 0 0 0 c-u0*R1 t0-u0*R0] = [p10 p9 0 0 0 0 0 0 0 0 p0] */
572  /* [d 0 t9 0 0 0 0 0 0 0 c t0] = [p10 p9 0 0 0 0 0 0 0 0 p0] */
573 
574  c += (uint64_t)a[0] * b[1]
575  + (uint64_t)a[1] * b[0];
576  VERIFY_BITS(c, 62);
577  /* [d 0 t9 0 0 0 0 0 0 0 c t0] = [p10 p9 0 0 0 0 0 0 0 p1 p0] */
578  d += (uint64_t)a[2] * b[9]
579  + (uint64_t)a[3] * b[8]
580  + (uint64_t)a[4] * b[7]
581  + (uint64_t)a[5] * b[6]
582  + (uint64_t)a[6] * b[5]
583  + (uint64_t)a[7] * b[4]
584  + (uint64_t)a[8] * b[3]
585  + (uint64_t)a[9] * b[2];
586  VERIFY_BITS(d, 63);
587  /* [d 0 t9 0 0 0 0 0 0 0 c t0] = [p11 p10 p9 0 0 0 0 0 0 0 p1 p0] */
588  u1 = d & M; d >>= 26; c += u1 * R0;
589  VERIFY_BITS(u1, 26);
590  VERIFY_BITS(d, 37);
591  VERIFY_BITS(c, 63);
592  /* [d u1 0 t9 0 0 0 0 0 0 0 c-u1*R0 t0] = [p11 p10 p9 0 0 0 0 0 0 0 p1 p0] */
593  t1 = c & M; c >>= 26; c += u1 * R1;
594  VERIFY_BITS(t1, 26);
595  VERIFY_BITS(c, 38);
596  /* [d u1 0 t9 0 0 0 0 0 0 c-u1*R1 t1-u1*R0 t0] = [p11 p10 p9 0 0 0 0 0 0 0 p1 p0] */
597  /* [d 0 0 t9 0 0 0 0 0 0 c t1 t0] = [p11 p10 p9 0 0 0 0 0 0 0 p1 p0] */
598 
599  c += (uint64_t)a[0] * b[2]
600  + (uint64_t)a[1] * b[1]
601  + (uint64_t)a[2] * b[0];
602  VERIFY_BITS(c, 62);
603  /* [d 0 0 t9 0 0 0 0 0 0 c t1 t0] = [p11 p10 p9 0 0 0 0 0 0 p2 p1 p0] */
604  d += (uint64_t)a[3] * b[9]
605  + (uint64_t)a[4] * b[8]
606  + (uint64_t)a[5] * b[7]
607  + (uint64_t)a[6] * b[6]
608  + (uint64_t)a[7] * b[5]
609  + (uint64_t)a[8] * b[4]
610  + (uint64_t)a[9] * b[3];
611  VERIFY_BITS(d, 63);
612  /* [d 0 0 t9 0 0 0 0 0 0 c t1 t0] = [p12 p11 p10 p9 0 0 0 0 0 0 p2 p1 p0] */
613  u2 = d & M; d >>= 26; c += u2 * R0;
614  VERIFY_BITS(u2, 26);
615  VERIFY_BITS(d, 37);
616  VERIFY_BITS(c, 63);
617  /* [d u2 0 0 t9 0 0 0 0 0 0 c-u2*R0 t1 t0] = [p12 p11 p10 p9 0 0 0 0 0 0 p2 p1 p0] */
618  t2 = c & M; c >>= 26; c += u2 * R1;
619  VERIFY_BITS(t2, 26);
620  VERIFY_BITS(c, 38);
621  /* [d u2 0 0 t9 0 0 0 0 0 c-u2*R1 t2-u2*R0 t1 t0] = [p12 p11 p10 p9 0 0 0 0 0 0 p2 p1 p0] */
622  /* [d 0 0 0 t9 0 0 0 0 0 c t2 t1 t0] = [p12 p11 p10 p9 0 0 0 0 0 0 p2 p1 p0] */
623 
624  c += (uint64_t)a[0] * b[3]
625  + (uint64_t)a[1] * b[2]
626  + (uint64_t)a[2] * b[1]
627  + (uint64_t)a[3] * b[0];
628  VERIFY_BITS(c, 63);
629  /* [d 0 0 0 t9 0 0 0 0 0 c t2 t1 t0] = [p12 p11 p10 p9 0 0 0 0 0 p3 p2 p1 p0] */
630  d += (uint64_t)a[4] * b[9]
631  + (uint64_t)a[5] * b[8]
632  + (uint64_t)a[6] * b[7]
633  + (uint64_t)a[7] * b[6]
634  + (uint64_t)a[8] * b[5]
635  + (uint64_t)a[9] * b[4];
636  VERIFY_BITS(d, 63);
637  /* [d 0 0 0 t9 0 0 0 0 0 c t2 t1 t0] = [p13 p12 p11 p10 p9 0 0 0 0 0 p3 p2 p1 p0] */
638  u3 = d & M; d >>= 26; c += u3 * R0;
639  VERIFY_BITS(u3, 26);
640  VERIFY_BITS(d, 37);
641  /* VERIFY_BITS(c, 64); */
642  /* [d u3 0 0 0 t9 0 0 0 0 0 c-u3*R0 t2 t1 t0] = [p13 p12 p11 p10 p9 0 0 0 0 0 p3 p2 p1 p0] */
643  t3 = c & M; c >>= 26; c += u3 * R1;
644  VERIFY_BITS(t3, 26);
645  VERIFY_BITS(c, 39);
646  /* [d u3 0 0 0 t9 0 0 0 0 c-u3*R1 t3-u3*R0 t2 t1 t0] = [p13 p12 p11 p10 p9 0 0 0 0 0 p3 p2 p1 p0] */
647  /* [d 0 0 0 0 t9 0 0 0 0 c t3 t2 t1 t0] = [p13 p12 p11 p10 p9 0 0 0 0 0 p3 p2 p1 p0] */
648 
649  c += (uint64_t)a[0] * b[4]
650  + (uint64_t)a[1] * b[3]
651  + (uint64_t)a[2] * b[2]
652  + (uint64_t)a[3] * b[1]
653  + (uint64_t)a[4] * b[0];
654  VERIFY_BITS(c, 63);
655  /* [d 0 0 0 0 t9 0 0 0 0 c t3 t2 t1 t0] = [p13 p12 p11 p10 p9 0 0 0 0 p4 p3 p2 p1 p0] */
656  d += (uint64_t)a[5] * b[9]
657  + (uint64_t)a[6] * b[8]
658  + (uint64_t)a[7] * b[7]
659  + (uint64_t)a[8] * b[6]
660  + (uint64_t)a[9] * b[5];
661  VERIFY_BITS(d, 62);
662  /* [d 0 0 0 0 t9 0 0 0 0 c t3 t2 t1 t0] = [p14 p13 p12 p11 p10 p9 0 0 0 0 p4 p3 p2 p1 p0] */
663  u4 = d & M; d >>= 26; c += u4 * R0;
664  VERIFY_BITS(u4, 26);
665  VERIFY_BITS(d, 36);
666  /* VERIFY_BITS(c, 64); */
667  /* [d u4 0 0 0 0 t9 0 0 0 0 c-u4*R0 t3 t2 t1 t0] = [p14 p13 p12 p11 p10 p9 0 0 0 0 p4 p3 p2 p1 p0] */
668  t4 = c & M; c >>= 26; c += u4 * R1;
669  VERIFY_BITS(t4, 26);
670  VERIFY_BITS(c, 39);
671  /* [d u4 0 0 0 0 t9 0 0 0 c-u4*R1 t4-u4*R0 t3 t2 t1 t0] = [p14 p13 p12 p11 p10 p9 0 0 0 0 p4 p3 p2 p1 p0] */
672  /* [d 0 0 0 0 0 t9 0 0 0 c t4 t3 t2 t1 t0] = [p14 p13 p12 p11 p10 p9 0 0 0 0 p4 p3 p2 p1 p0] */
673 
674  c += (uint64_t)a[0] * b[5]
675  + (uint64_t)a[1] * b[4]
676  + (uint64_t)a[2] * b[3]
677  + (uint64_t)a[3] * b[2]
678  + (uint64_t)a[4] * b[1]
679  + (uint64_t)a[5] * b[0];
680  VERIFY_BITS(c, 63);
681  /* [d 0 0 0 0 0 t9 0 0 0 c t4 t3 t2 t1 t0] = [p14 p13 p12 p11 p10 p9 0 0 0 p5 p4 p3 p2 p1 p0] */
682  d += (uint64_t)a[6] * b[9]
683  + (uint64_t)a[7] * b[8]
684  + (uint64_t)a[8] * b[7]
685  + (uint64_t)a[9] * b[6];
686  VERIFY_BITS(d, 62);
687  /* [d 0 0 0 0 0 t9 0 0 0 c t4 t3 t2 t1 t0] = [p15 p14 p13 p12 p11 p10 p9 0 0 0 p5 p4 p3 p2 p1 p0] */
688  u5 = d & M; d >>= 26; c += u5 * R0;
689  VERIFY_BITS(u5, 26);
690  VERIFY_BITS(d, 36);
691  /* VERIFY_BITS(c, 64); */
692  /* [d u5 0 0 0 0 0 t9 0 0 0 c-u5*R0 t4 t3 t2 t1 t0] = [p15 p14 p13 p12 p11 p10 p9 0 0 0 p5 p4 p3 p2 p1 p0] */
693  t5 = c & M; c >>= 26; c += u5 * R1;
694  VERIFY_BITS(t5, 26);
695  VERIFY_BITS(c, 39);
696  /* [d u5 0 0 0 0 0 t9 0 0 c-u5*R1 t5-u5*R0 t4 t3 t2 t1 t0] = [p15 p14 p13 p12 p11 p10 p9 0 0 0 p5 p4 p3 p2 p1 p0] */
697  /* [d 0 0 0 0 0 0 t9 0 0 c t5 t4 t3 t2 t1 t0] = [p15 p14 p13 p12 p11 p10 p9 0 0 0 p5 p4 p3 p2 p1 p0] */
698 
699  c += (uint64_t)a[0] * b[6]
700  + (uint64_t)a[1] * b[5]
701  + (uint64_t)a[2] * b[4]
702  + (uint64_t)a[3] * b[3]
703  + (uint64_t)a[4] * b[2]
704  + (uint64_t)a[5] * b[1]
705  + (uint64_t)a[6] * b[0];
706  VERIFY_BITS(c, 63);
707  /* [d 0 0 0 0 0 0 t9 0 0 c t5 t4 t3 t2 t1 t0] = [p15 p14 p13 p12 p11 p10 p9 0 0 p6 p5 p4 p3 p2 p1 p0] */
708  d += (uint64_t)a[7] * b[9]
709  + (uint64_t)a[8] * b[8]
710  + (uint64_t)a[9] * b[7];
711  VERIFY_BITS(d, 61);
712  /* [d 0 0 0 0 0 0 t9 0 0 c t5 t4 t3 t2 t1 t0] = [p16 p15 p14 p13 p12 p11 p10 p9 0 0 p6 p5 p4 p3 p2 p1 p0] */
713  u6 = d & M; d >>= 26; c += u6 * R0;
714  VERIFY_BITS(u6, 26);
715  VERIFY_BITS(d, 35);
716  /* VERIFY_BITS(c, 64); */
717  /* [d u6 0 0 0 0 0 0 t9 0 0 c-u6*R0 t5 t4 t3 t2 t1 t0] = [p16 p15 p14 p13 p12 p11 p10 p9 0 0 p6 p5 p4 p3 p2 p1 p0] */
718  t6 = c & M; c >>= 26; c += u6 * R1;
719  VERIFY_BITS(t6, 26);
720  VERIFY_BITS(c, 39);
721  /* [d u6 0 0 0 0 0 0 t9 0 c-u6*R1 t6-u6*R0 t5 t4 t3 t2 t1 t0] = [p16 p15 p14 p13 p12 p11 p10 p9 0 0 p6 p5 p4 p3 p2 p1 p0] */
722  /* [d 0 0 0 0 0 0 0 t9 0 c t6 t5 t4 t3 t2 t1 t0] = [p16 p15 p14 p13 p12 p11 p10 p9 0 0 p6 p5 p4 p3 p2 p1 p0] */
723 
724  c += (uint64_t)a[0] * b[7]
725  + (uint64_t)a[1] * b[6]
726  + (uint64_t)a[2] * b[5]
727  + (uint64_t)a[3] * b[4]
728  + (uint64_t)a[4] * b[3]
729  + (uint64_t)a[5] * b[2]
730  + (uint64_t)a[6] * b[1]
731  + (uint64_t)a[7] * b[0];
732  /* VERIFY_BITS(c, 64); */
733  VERIFY_CHECK(c <= 0x8000007C00000007ULL);
734  /* [d 0 0 0 0 0 0 0 t9 0 c t6 t5 t4 t3 t2 t1 t0] = [p16 p15 p14 p13 p12 p11 p10 p9 0 p7 p6 p5 p4 p3 p2 p1 p0] */
735  d += (uint64_t)a[8] * b[9]
736  + (uint64_t)a[9] * b[8];
737  VERIFY_BITS(d, 58);
738  /* [d 0 0 0 0 0 0 0 t9 0 c t6 t5 t4 t3 t2 t1 t0] = [p17 p16 p15 p14 p13 p12 p11 p10 p9 0 p7 p6 p5 p4 p3 p2 p1 p0] */
739  u7 = d & M; d >>= 26; c += u7 * R0;
740  VERIFY_BITS(u7, 26);
741  VERIFY_BITS(d, 32);
742  /* VERIFY_BITS(c, 64); */
743  VERIFY_CHECK(c <= 0x800001703FFFC2F7ULL);
744  /* [d u7 0 0 0 0 0 0 0 t9 0 c-u7*R0 t6 t5 t4 t3 t2 t1 t0] = [p17 p16 p15 p14 p13 p12 p11 p10 p9 0 p7 p6 p5 p4 p3 p2 p1 p0] */
745  t7 = c & M; c >>= 26; c += u7 * R1;
746  VERIFY_BITS(t7, 26);
747  VERIFY_BITS(c, 38);
748  /* [d u7 0 0 0 0 0 0 0 t9 c-u7*R1 t7-u7*R0 t6 t5 t4 t3 t2 t1 t0] = [p17 p16 p15 p14 p13 p12 p11 p10 p9 0 p7 p6 p5 p4 p3 p2 p1 p0] */
749  /* [d 0 0 0 0 0 0 0 0 t9 c t7 t6 t5 t4 t3 t2 t1 t0] = [p17 p16 p15 p14 p13 p12 p11 p10 p9 0 p7 p6 p5 p4 p3 p2 p1 p0] */
750 
751  c += (uint64_t)a[0] * b[8]
752  + (uint64_t)a[1] * b[7]
753  + (uint64_t)a[2] * b[6]
754  + (uint64_t)a[3] * b[5]
755  + (uint64_t)a[4] * b[4]
756  + (uint64_t)a[5] * b[3]
757  + (uint64_t)a[6] * b[2]
758  + (uint64_t)a[7] * b[1]
759  + (uint64_t)a[8] * b[0];
760  /* VERIFY_BITS(c, 64); */
761  VERIFY_CHECK(c <= 0x9000007B80000008ULL);
762  /* [d 0 0 0 0 0 0 0 0 t9 c t7 t6 t5 t4 t3 t2 t1 t0] = [p17 p16 p15 p14 p13 p12 p11 p10 p9 p8 p7 p6 p5 p4 p3 p2 p1 p0] */
763  d += (uint64_t)a[9] * b[9];
764  VERIFY_BITS(d, 57);
765  /* [d 0 0 0 0 0 0 0 0 t9 c t7 t6 t5 t4 t3 t2 t1 t0] = [p18 p17 p16 p15 p14 p13 p12 p11 p10 p9 p8 p7 p6 p5 p4 p3 p2 p1 p0] */
766  u8 = d & M; d >>= 26; c += u8 * R0;
767  VERIFY_BITS(u8, 26);
768  VERIFY_BITS(d, 31);
769  /* VERIFY_BITS(c, 64); */
770  VERIFY_CHECK(c <= 0x9000016FBFFFC2F8ULL);
771  /* [d u8 0 0 0 0 0 0 0 0 t9 c-u8*R0 t7 t6 t5 t4 t3 t2 t1 t0] = [p18 p17 p16 p15 p14 p13 p12 p11 p10 p9 p8 p7 p6 p5 p4 p3 p2 p1 p0] */
772 
773  r[3] = t3;
774  VERIFY_BITS(r[3], 26);
775  /* [d u8 0 0 0 0 0 0 0 0 t9 c-u8*R0 t7 t6 t5 t4 r3 t2 t1 t0] = [p18 p17 p16 p15 p14 p13 p12 p11 p10 p9 p8 p7 p6 p5 p4 p3 p2 p1 p0] */
776  r[4] = t4;
777  VERIFY_BITS(r[4], 26);
778  /* [d u8 0 0 0 0 0 0 0 0 t9 c-u8*R0 t7 t6 t5 r4 r3 t2 t1 t0] = [p18 p17 p16 p15 p14 p13 p12 p11 p10 p9 p8 p7 p6 p5 p4 p3 p2 p1 p0] */
779  r[5] = t5;
780  VERIFY_BITS(r[5], 26);
781  /* [d u8 0 0 0 0 0 0 0 0 t9 c-u8*R0 t7 t6 r5 r4 r3 t2 t1 t0] = [p18 p17 p16 p15 p14 p13 p12 p11 p10 p9 p8 p7 p6 p5 p4 p3 p2 p1 p0] */
782  r[6] = t6;
783  VERIFY_BITS(r[6], 26);
784  /* [d u8 0 0 0 0 0 0 0 0 t9 c-u8*R0 t7 r6 r5 r4 r3 t2 t1 t0] = [p18 p17 p16 p15 p14 p13 p12 p11 p10 p9 p8 p7 p6 p5 p4 p3 p2 p1 p0] */
785  r[7] = t7;
786  VERIFY_BITS(r[7], 26);
787  /* [d u8 0 0 0 0 0 0 0 0 t9 c-u8*R0 r7 r6 r5 r4 r3 t2 t1 t0] = [p18 p17 p16 p15 p14 p13 p12 p11 p10 p9 p8 p7 p6 p5 p4 p3 p2 p1 p0] */
788 
789  r[8] = c & M; c >>= 26; c += u8 * R1;
790  VERIFY_BITS(r[8], 26);
791  VERIFY_BITS(c, 39);
792  /* [d u8 0 0 0 0 0 0 0 0 t9+c-u8*R1 r8-u8*R0 r7 r6 r5 r4 r3 t2 t1 t0] = [p18 p17 p16 p15 p14 p13 p12 p11 p10 p9 p8 p7 p6 p5 p4 p3 p2 p1 p0] */
793  /* [d 0 0 0 0 0 0 0 0 0 t9+c r8 r7 r6 r5 r4 r3 t2 t1 t0] = [p18 p17 p16 p15 p14 p13 p12 p11 p10 p9 p8 p7 p6 p5 p4 p3 p2 p1 p0] */
794  c += d * R0 + t9;
795  VERIFY_BITS(c, 45);
796  /* [d 0 0 0 0 0 0 0 0 0 c-d*R0 r8 r7 r6 r5 r4 r3 t2 t1 t0] = [p18 p17 p16 p15 p14 p13 p12 p11 p10 p9 p8 p7 p6 p5 p4 p3 p2 p1 p0] */
797  r[9] = c & (M >> 4); c >>= 22; c += d * (R1 << 4);
798  VERIFY_BITS(r[9], 22);
799  VERIFY_BITS(c, 46);
800  /* [d 0 0 0 0 0 0 0 0 r9+((c-d*R1<<4)<<22)-d*R0 r8 r7 r6 r5 r4 r3 t2 t1 t0] = [p18 p17 p16 p15 p14 p13 p12 p11 p10 p9 p8 p7 p6 p5 p4 p3 p2 p1 p0] */
801  /* [d 0 0 0 0 0 0 0 -d*R1 r9+(c<<22)-d*R0 r8 r7 r6 r5 r4 r3 t2 t1 t0] = [p18 p17 p16 p15 p14 p13 p12 p11 p10 p9 p8 p7 p6 p5 p4 p3 p2 p1 p0] */
802  /* [r9+(c<<22) r8 r7 r6 r5 r4 r3 t2 t1 t0] = [p18 p17 p16 p15 p14 p13 p12 p11 p10 p9 p8 p7 p6 p5 p4 p3 p2 p1 p0] */
803 
804  d = c * (R0 >> 4) + t0;
805  VERIFY_BITS(d, 56);
806  /* [r9+(c<<22) r8 r7 r6 r5 r4 r3 t2 t1 d-c*R0>>4] = [p18 p17 p16 p15 p14 p13 p12 p11 p10 p9 p8 p7 p6 p5 p4 p3 p2 p1 p0] */
807  r[0] = d & M; d >>= 26;
808  VERIFY_BITS(r[0], 26);
809  VERIFY_BITS(d, 30);
810  /* [r9+(c<<22) r8 r7 r6 r5 r4 r3 t2 t1+d r0-c*R0>>4] = [p18 p17 p16 p15 p14 p13 p12 p11 p10 p9 p8 p7 p6 p5 p4 p3 p2 p1 p0] */
811  d += c * (R1 >> 4) + t1;
812  VERIFY_BITS(d, 53);
813  VERIFY_CHECK(d <= 0x10000003FFFFBFULL);
814  /* [r9+(c<<22) r8 r7 r6 r5 r4 r3 t2 d-c*R1>>4 r0-c*R0>>4] = [p18 p17 p16 p15 p14 p13 p12 p11 p10 p9 p8 p7 p6 p5 p4 p3 p2 p1 p0] */
815  /* [r9 r8 r7 r6 r5 r4 r3 t2 d r0] = [p18 p17 p16 p15 p14 p13 p12 p11 p10 p9 p8 p7 p6 p5 p4 p3 p2 p1 p0] */
816  r[1] = d & M; d >>= 26;
817  VERIFY_BITS(r[1], 26);
818  VERIFY_BITS(d, 27);
819  VERIFY_CHECK(d <= 0x4000000ULL);
820  /* [r9 r8 r7 r6 r5 r4 r3 t2+d r1 r0] = [p18 p17 p16 p15 p14 p13 p12 p11 p10 p9 p8 p7 p6 p5 p4 p3 p2 p1 p0] */
821  d += t2;
822  VERIFY_BITS(d, 27);
823  /* [r9 r8 r7 r6 r5 r4 r3 d r1 r0] = [p18 p17 p16 p15 p14 p13 p12 p11 p10 p9 p8 p7 p6 p5 p4 p3 p2 p1 p0] */
824  r[2] = d;
825  VERIFY_BITS(r[2], 27);
826  /* [r9 r8 r7 r6 r5 r4 r3 r2 r1 r0] = [p18 p17 p16 p15 p14 p13 p12 p11 p10 p9 p8 p7 p6 p5 p4 p3 p2 p1 p0] */
827 }
828 
829 SECP256K1_INLINE static void secp256k1_fe_sqr_inner(uint32_t *r, const uint32_t *a) {
830  uint64_t c, d;
831  uint64_t u0, u1, u2, u3, u4, u5, u6, u7, u8;
832  uint32_t t9, t0, t1, t2, t3, t4, t5, t6, t7;
833  const uint32_t M = 0x3FFFFFFUL, R0 = 0x3D10UL, R1 = 0x400UL;
834 
835  VERIFY_BITS(a[0], 30);
836  VERIFY_BITS(a[1], 30);
837  VERIFY_BITS(a[2], 30);
838  VERIFY_BITS(a[3], 30);
839  VERIFY_BITS(a[4], 30);
840  VERIFY_BITS(a[5], 30);
841  VERIFY_BITS(a[6], 30);
842  VERIFY_BITS(a[7], 30);
843  VERIFY_BITS(a[8], 30);
844  VERIFY_BITS(a[9], 26);
845 
851  d = (uint64_t)(a[0]*2) * a[9]
852  + (uint64_t)(a[1]*2) * a[8]
853  + (uint64_t)(a[2]*2) * a[7]
854  + (uint64_t)(a[3]*2) * a[6]
855  + (uint64_t)(a[4]*2) * a[5];
856  /* VERIFY_BITS(d, 64); */
857  /* [d 0 0 0 0 0 0 0 0 0] = [p9 0 0 0 0 0 0 0 0 0] */
858  t9 = d & M; d >>= 26;
859  VERIFY_BITS(t9, 26);
860  VERIFY_BITS(d, 38);
861  /* [d t9 0 0 0 0 0 0 0 0 0] = [p9 0 0 0 0 0 0 0 0 0] */
862 
863  c = (uint64_t)a[0] * a[0];
864  VERIFY_BITS(c, 60);
865  /* [d t9 0 0 0 0 0 0 0 0 c] = [p9 0 0 0 0 0 0 0 0 p0] */
866  d += (uint64_t)(a[1]*2) * a[9]
867  + (uint64_t)(a[2]*2) * a[8]
868  + (uint64_t)(a[3]*2) * a[7]
869  + (uint64_t)(a[4]*2) * a[6]
870  + (uint64_t)a[5] * a[5];
871  VERIFY_BITS(d, 63);
872  /* [d t9 0 0 0 0 0 0 0 0 c] = [p10 p9 0 0 0 0 0 0 0 0 p0] */
873  u0 = d & M; d >>= 26; c += u0 * R0;
874  VERIFY_BITS(u0, 26);
875  VERIFY_BITS(d, 37);
876  VERIFY_BITS(c, 61);
877  /* [d u0 t9 0 0 0 0 0 0 0 0 c-u0*R0] = [p10 p9 0 0 0 0 0 0 0 0 p0] */
878  t0 = c & M; c >>= 26; c += u0 * R1;
879  VERIFY_BITS(t0, 26);
880  VERIFY_BITS(c, 37);
881  /* [d u0 t9 0 0 0 0 0 0 0 c-u0*R1 t0-u0*R0] = [p10 p9 0 0 0 0 0 0 0 0 p0] */
882  /* [d 0 t9 0 0 0 0 0 0 0 c t0] = [p10 p9 0 0 0 0 0 0 0 0 p0] */
883 
884  c += (uint64_t)(a[0]*2) * a[1];
885  VERIFY_BITS(c, 62);
886  /* [d 0 t9 0 0 0 0 0 0 0 c t0] = [p10 p9 0 0 0 0 0 0 0 p1 p0] */
887  d += (uint64_t)(a[2]*2) * a[9]
888  + (uint64_t)(a[3]*2) * a[8]
889  + (uint64_t)(a[4]*2) * a[7]
890  + (uint64_t)(a[5]*2) * a[6];
891  VERIFY_BITS(d, 63);
892  /* [d 0 t9 0 0 0 0 0 0 0 c t0] = [p11 p10 p9 0 0 0 0 0 0 0 p1 p0] */
893  u1 = d & M; d >>= 26; c += u1 * R0;
894  VERIFY_BITS(u1, 26);
895  VERIFY_BITS(d, 37);
896  VERIFY_BITS(c, 63);
897  /* [d u1 0 t9 0 0 0 0 0 0 0 c-u1*R0 t0] = [p11 p10 p9 0 0 0 0 0 0 0 p1 p0] */
898  t1 = c & M; c >>= 26; c += u1 * R1;
899  VERIFY_BITS(t1, 26);
900  VERIFY_BITS(c, 38);
901  /* [d u1 0 t9 0 0 0 0 0 0 c-u1*R1 t1-u1*R0 t0] = [p11 p10 p9 0 0 0 0 0 0 0 p1 p0] */
902  /* [d 0 0 t9 0 0 0 0 0 0 c t1 t0] = [p11 p10 p9 0 0 0 0 0 0 0 p1 p0] */
903 
904  c += (uint64_t)(a[0]*2) * a[2]
905  + (uint64_t)a[1] * a[1];
906  VERIFY_BITS(c, 62);
907  /* [d 0 0 t9 0 0 0 0 0 0 c t1 t0] = [p11 p10 p9 0 0 0 0 0 0 p2 p1 p0] */
908  d += (uint64_t)(a[3]*2) * a[9]
909  + (uint64_t)(a[4]*2) * a[8]
910  + (uint64_t)(a[5]*2) * a[7]
911  + (uint64_t)a[6] * a[6];
912  VERIFY_BITS(d, 63);
913  /* [d 0 0 t9 0 0 0 0 0 0 c t1 t0] = [p12 p11 p10 p9 0 0 0 0 0 0 p2 p1 p0] */
914  u2 = d & M; d >>= 26; c += u2 * R0;
915  VERIFY_BITS(u2, 26);
916  VERIFY_BITS(d, 37);
917  VERIFY_BITS(c, 63);
918  /* [d u2 0 0 t9 0 0 0 0 0 0 c-u2*R0 t1 t0] = [p12 p11 p10 p9 0 0 0 0 0 0 p2 p1 p0] */
919  t2 = c & M; c >>= 26; c += u2 * R1;
920  VERIFY_BITS(t2, 26);
921  VERIFY_BITS(c, 38);
922  /* [d u2 0 0 t9 0 0 0 0 0 c-u2*R1 t2-u2*R0 t1 t0] = [p12 p11 p10 p9 0 0 0 0 0 0 p2 p1 p0] */
923  /* [d 0 0 0 t9 0 0 0 0 0 c t2 t1 t0] = [p12 p11 p10 p9 0 0 0 0 0 0 p2 p1 p0] */
924 
925  c += (uint64_t)(a[0]*2) * a[3]
926  + (uint64_t)(a[1]*2) * a[2];
927  VERIFY_BITS(c, 63);
928  /* [d 0 0 0 t9 0 0 0 0 0 c t2 t1 t0] = [p12 p11 p10 p9 0 0 0 0 0 p3 p2 p1 p0] */
929  d += (uint64_t)(a[4]*2) * a[9]
930  + (uint64_t)(a[5]*2) * a[8]
931  + (uint64_t)(a[6]*2) * a[7];
932  VERIFY_BITS(d, 63);
933  /* [d 0 0 0 t9 0 0 0 0 0 c t2 t1 t0] = [p13 p12 p11 p10 p9 0 0 0 0 0 p3 p2 p1 p0] */
934  u3 = d & M; d >>= 26; c += u3 * R0;
935  VERIFY_BITS(u3, 26);
936  VERIFY_BITS(d, 37);
937  /* VERIFY_BITS(c, 64); */
938  /* [d u3 0 0 0 t9 0 0 0 0 0 c-u3*R0 t2 t1 t0] = [p13 p12 p11 p10 p9 0 0 0 0 0 p3 p2 p1 p0] */
939  t3 = c & M; c >>= 26; c += u3 * R1;
940  VERIFY_BITS(t3, 26);
941  VERIFY_BITS(c, 39);
942  /* [d u3 0 0 0 t9 0 0 0 0 c-u3*R1 t3-u3*R0 t2 t1 t0] = [p13 p12 p11 p10 p9 0 0 0 0 0 p3 p2 p1 p0] */
943  /* [d 0 0 0 0 t9 0 0 0 0 c t3 t2 t1 t0] = [p13 p12 p11 p10 p9 0 0 0 0 0 p3 p2 p1 p0] */
944 
945  c += (uint64_t)(a[0]*2) * a[4]
946  + (uint64_t)(a[1]*2) * a[3]
947  + (uint64_t)a[2] * a[2];
948  VERIFY_BITS(c, 63);
949  /* [d 0 0 0 0 t9 0 0 0 0 c t3 t2 t1 t0] = [p13 p12 p11 p10 p9 0 0 0 0 p4 p3 p2 p1 p0] */
950  d += (uint64_t)(a[5]*2) * a[9]
951  + (uint64_t)(a[6]*2) * a[8]
952  + (uint64_t)a[7] * a[7];
953  VERIFY_BITS(d, 62);
954  /* [d 0 0 0 0 t9 0 0 0 0 c t3 t2 t1 t0] = [p14 p13 p12 p11 p10 p9 0 0 0 0 p4 p3 p2 p1 p0] */
955  u4 = d & M; d >>= 26; c += u4 * R0;
956  VERIFY_BITS(u4, 26);
957  VERIFY_BITS(d, 36);
958  /* VERIFY_BITS(c, 64); */
959  /* [d u4 0 0 0 0 t9 0 0 0 0 c-u4*R0 t3 t2 t1 t0] = [p14 p13 p12 p11 p10 p9 0 0 0 0 p4 p3 p2 p1 p0] */
960  t4 = c & M; c >>= 26; c += u4 * R1;
961  VERIFY_BITS(t4, 26);
962  VERIFY_BITS(c, 39);
963  /* [d u4 0 0 0 0 t9 0 0 0 c-u4*R1 t4-u4*R0 t3 t2 t1 t0] = [p14 p13 p12 p11 p10 p9 0 0 0 0 p4 p3 p2 p1 p0] */
964  /* [d 0 0 0 0 0 t9 0 0 0 c t4 t3 t2 t1 t0] = [p14 p13 p12 p11 p10 p9 0 0 0 0 p4 p3 p2 p1 p0] */
965 
966  c += (uint64_t)(a[0]*2) * a[5]
967  + (uint64_t)(a[1]*2) * a[4]
968  + (uint64_t)(a[2]*2) * a[3];
969  VERIFY_BITS(c, 63);
970  /* [d 0 0 0 0 0 t9 0 0 0 c t4 t3 t2 t1 t0] = [p14 p13 p12 p11 p10 p9 0 0 0 p5 p4 p3 p2 p1 p0] */
971  d += (uint64_t)(a[6]*2) * a[9]
972  + (uint64_t)(a[7]*2) * a[8];
973  VERIFY_BITS(d, 62);
974  /* [d 0 0 0 0 0 t9 0 0 0 c t4 t3 t2 t1 t0] = [p15 p14 p13 p12 p11 p10 p9 0 0 0 p5 p4 p3 p2 p1 p0] */
975  u5 = d & M; d >>= 26; c += u5 * R0;
976  VERIFY_BITS(u5, 26);
977  VERIFY_BITS(d, 36);
978  /* VERIFY_BITS(c, 64); */
979  /* [d u5 0 0 0 0 0 t9 0 0 0 c-u5*R0 t4 t3 t2 t1 t0] = [p15 p14 p13 p12 p11 p10 p9 0 0 0 p5 p4 p3 p2 p1 p0] */
980  t5 = c & M; c >>= 26; c += u5 * R1;
981  VERIFY_BITS(t5, 26);
982  VERIFY_BITS(c, 39);
983  /* [d u5 0 0 0 0 0 t9 0 0 c-u5*R1 t5-u5*R0 t4 t3 t2 t1 t0] = [p15 p14 p13 p12 p11 p10 p9 0 0 0 p5 p4 p3 p2 p1 p0] */
984  /* [d 0 0 0 0 0 0 t9 0 0 c t5 t4 t3 t2 t1 t0] = [p15 p14 p13 p12 p11 p10 p9 0 0 0 p5 p4 p3 p2 p1 p0] */
985 
986  c += (uint64_t)(a[0]*2) * a[6]
987  + (uint64_t)(a[1]*2) * a[5]
988  + (uint64_t)(a[2]*2) * a[4]
989  + (uint64_t)a[3] * a[3];
990  VERIFY_BITS(c, 63);
991  /* [d 0 0 0 0 0 0 t9 0 0 c t5 t4 t3 t2 t1 t0] = [p15 p14 p13 p12 p11 p10 p9 0 0 p6 p5 p4 p3 p2 p1 p0] */
992  d += (uint64_t)(a[7]*2) * a[9]
993  + (uint64_t)a[8] * a[8];
994  VERIFY_BITS(d, 61);
995  /* [d 0 0 0 0 0 0 t9 0 0 c t5 t4 t3 t2 t1 t0] = [p16 p15 p14 p13 p12 p11 p10 p9 0 0 p6 p5 p4 p3 p2 p1 p0] */
996  u6 = d & M; d >>= 26; c += u6 * R0;
997  VERIFY_BITS(u6, 26);
998  VERIFY_BITS(d, 35);
999  /* VERIFY_BITS(c, 64); */
1000  /* [d u6 0 0 0 0 0 0 t9 0 0 c-u6*R0 t5 t4 t3 t2 t1 t0] = [p16 p15 p14 p13 p12 p11 p10 p9 0 0 p6 p5 p4 p3 p2 p1 p0] */
1001  t6 = c & M; c >>= 26; c += u6 * R1;
1002  VERIFY_BITS(t6, 26);
1003  VERIFY_BITS(c, 39);
1004  /* [d u6 0 0 0 0 0 0 t9 0 c-u6*R1 t6-u6*R0 t5 t4 t3 t2 t1 t0] = [p16 p15 p14 p13 p12 p11 p10 p9 0 0 p6 p5 p4 p3 p2 p1 p0] */
1005  /* [d 0 0 0 0 0 0 0 t9 0 c t6 t5 t4 t3 t2 t1 t0] = [p16 p15 p14 p13 p12 p11 p10 p9 0 0 p6 p5 p4 p3 p2 p1 p0] */
1006 
1007  c += (uint64_t)(a[0]*2) * a[7]
1008  + (uint64_t)(a[1]*2) * a[6]
1009  + (uint64_t)(a[2]*2) * a[5]
1010  + (uint64_t)(a[3]*2) * a[4];
1011  /* VERIFY_BITS(c, 64); */
1012  VERIFY_CHECK(c <= 0x8000007C00000007ULL);
1013  /* [d 0 0 0 0 0 0 0 t9 0 c t6 t5 t4 t3 t2 t1 t0] = [p16 p15 p14 p13 p12 p11 p10 p9 0 p7 p6 p5 p4 p3 p2 p1 p0] */
1014  d += (uint64_t)(a[8]*2) * a[9];
1015  VERIFY_BITS(d, 58);
1016  /* [d 0 0 0 0 0 0 0 t9 0 c t6 t5 t4 t3 t2 t1 t0] = [p17 p16 p15 p14 p13 p12 p11 p10 p9 0 p7 p6 p5 p4 p3 p2 p1 p0] */
1017  u7 = d & M; d >>= 26; c += u7 * R0;
1018  VERIFY_BITS(u7, 26);
1019  VERIFY_BITS(d, 32);
1020  /* VERIFY_BITS(c, 64); */
1021  VERIFY_CHECK(c <= 0x800001703FFFC2F7ULL);
1022  /* [d u7 0 0 0 0 0 0 0 t9 0 c-u7*R0 t6 t5 t4 t3 t2 t1 t0] = [p17 p16 p15 p14 p13 p12 p11 p10 p9 0 p7 p6 p5 p4 p3 p2 p1 p0] */
1023  t7 = c & M; c >>= 26; c += u7 * R1;
1024  VERIFY_BITS(t7, 26);
1025  VERIFY_BITS(c, 38);
1026  /* [d u7 0 0 0 0 0 0 0 t9 c-u7*R1 t7-u7*R0 t6 t5 t4 t3 t2 t1 t0] = [p17 p16 p15 p14 p13 p12 p11 p10 p9 0 p7 p6 p5 p4 p3 p2 p1 p0] */
1027  /* [d 0 0 0 0 0 0 0 0 t9 c t7 t6 t5 t4 t3 t2 t1 t0] = [p17 p16 p15 p14 p13 p12 p11 p10 p9 0 p7 p6 p5 p4 p3 p2 p1 p0] */
1028 
1029  c += (uint64_t)(a[0]*2) * a[8]
1030  + (uint64_t)(a[1]*2) * a[7]
1031  + (uint64_t)(a[2]*2) * a[6]
1032  + (uint64_t)(a[3]*2) * a[5]
1033  + (uint64_t)a[4] * a[4];
1034  /* VERIFY_BITS(c, 64); */
1035  VERIFY_CHECK(c <= 0x9000007B80000008ULL);
1036  /* [d 0 0 0 0 0 0 0 0 t9 c t7 t6 t5 t4 t3 t2 t1 t0] = [p17 p16 p15 p14 p13 p12 p11 p10 p9 p8 p7 p6 p5 p4 p3 p2 p1 p0] */
1037  d += (uint64_t)a[9] * a[9];
1038  VERIFY_BITS(d, 57);
1039  /* [d 0 0 0 0 0 0 0 0 t9 c t7 t6 t5 t4 t3 t2 t1 t0] = [p18 p17 p16 p15 p14 p13 p12 p11 p10 p9 p8 p7 p6 p5 p4 p3 p2 p1 p0] */
1040  u8 = d & M; d >>= 26; c += u8 * R0;
1041  VERIFY_BITS(u8, 26);
1042  VERIFY_BITS(d, 31);
1043  /* VERIFY_BITS(c, 64); */
1044  VERIFY_CHECK(c <= 0x9000016FBFFFC2F8ULL);
1045  /* [d u8 0 0 0 0 0 0 0 0 t9 c-u8*R0 t7 t6 t5 t4 t3 t2 t1 t0] = [p18 p17 p16 p15 p14 p13 p12 p11 p10 p9 p8 p7 p6 p5 p4 p3 p2 p1 p0] */
1046 
1047  r[3] = t3;
1048  VERIFY_BITS(r[3], 26);
1049  /* [d u8 0 0 0 0 0 0 0 0 t9 c-u8*R0 t7 t6 t5 t4 r3 t2 t1 t0] = [p18 p17 p16 p15 p14 p13 p12 p11 p10 p9 p8 p7 p6 p5 p4 p3 p2 p1 p0] */
1050  r[4] = t4;
1051  VERIFY_BITS(r[4], 26);
1052  /* [d u8 0 0 0 0 0 0 0 0 t9 c-u8*R0 t7 t6 t5 r4 r3 t2 t1 t0] = [p18 p17 p16 p15 p14 p13 p12 p11 p10 p9 p8 p7 p6 p5 p4 p3 p2 p1 p0] */
1053  r[5] = t5;
1054  VERIFY_BITS(r[5], 26);
1055  /* [d u8 0 0 0 0 0 0 0 0 t9 c-u8*R0 t7 t6 r5 r4 r3 t2 t1 t0] = [p18 p17 p16 p15 p14 p13 p12 p11 p10 p9 p8 p7 p6 p5 p4 p3 p2 p1 p0] */
1056  r[6] = t6;
1057  VERIFY_BITS(r[6], 26);
1058  /* [d u8 0 0 0 0 0 0 0 0 t9 c-u8*R0 t7 r6 r5 r4 r3 t2 t1 t0] = [p18 p17 p16 p15 p14 p13 p12 p11 p10 p9 p8 p7 p6 p5 p4 p3 p2 p1 p0] */
1059  r[7] = t7;
1060  VERIFY_BITS(r[7], 26);
1061  /* [d u8 0 0 0 0 0 0 0 0 t9 c-u8*R0 r7 r6 r5 r4 r3 t2 t1 t0] = [p18 p17 p16 p15 p14 p13 p12 p11 p10 p9 p8 p7 p6 p5 p4 p3 p2 p1 p0] */
1062 
1063  r[8] = c & M; c >>= 26; c += u8 * R1;
1064  VERIFY_BITS(r[8], 26);
1065  VERIFY_BITS(c, 39);
1066  /* [d u8 0 0 0 0 0 0 0 0 t9+c-u8*R1 r8-u8*R0 r7 r6 r5 r4 r3 t2 t1 t0] = [p18 p17 p16 p15 p14 p13 p12 p11 p10 p9 p8 p7 p6 p5 p4 p3 p2 p1 p0] */
1067  /* [d 0 0 0 0 0 0 0 0 0 t9+c r8 r7 r6 r5 r4 r3 t2 t1 t0] = [p18 p17 p16 p15 p14 p13 p12 p11 p10 p9 p8 p7 p6 p5 p4 p3 p2 p1 p0] */
1068  c += d * R0 + t9;
1069  VERIFY_BITS(c, 45);
1070  /* [d 0 0 0 0 0 0 0 0 0 c-d*R0 r8 r7 r6 r5 r4 r3 t2 t1 t0] = [p18 p17 p16 p15 p14 p13 p12 p11 p10 p9 p8 p7 p6 p5 p4 p3 p2 p1 p0] */
1071  r[9] = c & (M >> 4); c >>= 22; c += d * (R1 << 4);
1072  VERIFY_BITS(r[9], 22);
1073  VERIFY_BITS(c, 46);
1074  /* [d 0 0 0 0 0 0 0 0 r9+((c-d*R1<<4)<<22)-d*R0 r8 r7 r6 r5 r4 r3 t2 t1 t0] = [p18 p17 p16 p15 p14 p13 p12 p11 p10 p9 p8 p7 p6 p5 p4 p3 p2 p1 p0] */
1075  /* [d 0 0 0 0 0 0 0 -d*R1 r9+(c<<22)-d*R0 r8 r7 r6 r5 r4 r3 t2 t1 t0] = [p18 p17 p16 p15 p14 p13 p12 p11 p10 p9 p8 p7 p6 p5 p4 p3 p2 p1 p0] */
1076  /* [r9+(c<<22) r8 r7 r6 r5 r4 r3 t2 t1 t0] = [p18 p17 p16 p15 p14 p13 p12 p11 p10 p9 p8 p7 p6 p5 p4 p3 p2 p1 p0] */
1077 
1078  d = c * (R0 >> 4) + t0;
1079  VERIFY_BITS(d, 56);
1080  /* [r9+(c<<22) r8 r7 r6 r5 r4 r3 t2 t1 d-c*R0>>4] = [p18 p17 p16 p15 p14 p13 p12 p11 p10 p9 p8 p7 p6 p5 p4 p3 p2 p1 p0] */
1081  r[0] = d & M; d >>= 26;
1082  VERIFY_BITS(r[0], 26);
1083  VERIFY_BITS(d, 30);
1084  /* [r9+(c<<22) r8 r7 r6 r5 r4 r3 t2 t1+d r0-c*R0>>4] = [p18 p17 p16 p15 p14 p13 p12 p11 p10 p9 p8 p7 p6 p5 p4 p3 p2 p1 p0] */
1085  d += c * (R1 >> 4) + t1;
1086  VERIFY_BITS(d, 53);
1087  VERIFY_CHECK(d <= 0x10000003FFFFBFULL);
1088  /* [r9+(c<<22) r8 r7 r6 r5 r4 r3 t2 d-c*R1>>4 r0-c*R0>>4] = [p18 p17 p16 p15 p14 p13 p12 p11 p10 p9 p8 p7 p6 p5 p4 p3 p2 p1 p0] */
1089  /* [r9 r8 r7 r6 r5 r4 r3 t2 d r0] = [p18 p17 p16 p15 p14 p13 p12 p11 p10 p9 p8 p7 p6 p5 p4 p3 p2 p1 p0] */
1090  r[1] = d & M; d >>= 26;
1091  VERIFY_BITS(r[1], 26);
1092  VERIFY_BITS(d, 27);
1093  VERIFY_CHECK(d <= 0x4000000ULL);
1094  /* [r9 r8 r7 r6 r5 r4 r3 t2+d r1 r0] = [p18 p17 p16 p15 p14 p13 p12 p11 p10 p9 p8 p7 p6 p5 p4 p3 p2 p1 p0] */
1095  d += t2;
1096  VERIFY_BITS(d, 27);
1097  /* [r9 r8 r7 r6 r5 r4 r3 d r1 r0] = [p18 p17 p16 p15 p14 p13 p12 p11 p10 p9 p8 p7 p6 p5 p4 p3 p2 p1 p0] */
1098  r[2] = d;
1099  VERIFY_BITS(r[2], 27);
1100  /* [r9 r8 r7 r6 r5 r4 r3 r2 r1 r0] = [p18 p17 p16 p15 p14 p13 p12 p11 p10 p9 p8 p7 p6 p5 p4 p3 p2 p1 p0] */
1101 }
1102 #endif
1103 
1104 static void secp256k1_fe_mul(secp256k1_fe *r, const secp256k1_fe *a, const secp256k1_fe * SECP256K1_RESTRICT b) {
1105 #ifdef VERIFY
1106  VERIFY_CHECK(a->magnitude <= 8);
1107  VERIFY_CHECK(b->magnitude <= 8);
1108  secp256k1_fe_verify(a);
1109  secp256k1_fe_verify(b);
1110  VERIFY_CHECK(r != b);
1111  VERIFY_CHECK(a != b);
1112 #endif
1113  secp256k1_fe_mul_inner(r->n, a->n, b->n);
1114 #ifdef VERIFY
1115  r->magnitude = 1;
1116  r->normalized = 0;
1117  secp256k1_fe_verify(r);
1118 #endif
1119 }
1120 
1121 static void secp256k1_fe_sqr(secp256k1_fe *r, const secp256k1_fe *a) {
1122 #ifdef VERIFY
1123  VERIFY_CHECK(a->magnitude <= 8);
1124  secp256k1_fe_verify(a);
1125 #endif
1126  secp256k1_fe_sqr_inner(r->n, a->n);
1127 #ifdef VERIFY
1128  r->magnitude = 1;
1129  r->normalized = 0;
1130  secp256k1_fe_verify(r);
1131 #endif
1132 }
1133 
1134 static SECP256K1_INLINE void secp256k1_fe_cmov(secp256k1_fe *r, const secp256k1_fe *a, int flag) {
1135  uint32_t mask0, mask1;
1136  SECP256K1_CHECKMEM_CHECK_VERIFY(r->n, sizeof(r->n));
1137  mask0 = flag + ~((uint32_t)0);
1138  mask1 = ~mask0;
1139  r->n[0] = (r->n[0] & mask0) | (a->n[0] & mask1);
1140  r->n[1] = (r->n[1] & mask0) | (a->n[1] & mask1);
1141  r->n[2] = (r->n[2] & mask0) | (a->n[2] & mask1);
1142  r->n[3] = (r->n[3] & mask0) | (a->n[3] & mask1);
1143  r->n[4] = (r->n[4] & mask0) | (a->n[4] & mask1);
1144  r->n[5] = (r->n[5] & mask0) | (a->n[5] & mask1);
1145  r->n[6] = (r->n[6] & mask0) | (a->n[6] & mask1);
1146  r->n[7] = (r->n[7] & mask0) | (a->n[7] & mask1);
1147  r->n[8] = (r->n[8] & mask0) | (a->n[8] & mask1);
1148  r->n[9] = (r->n[9] & mask0) | (a->n[9] & mask1);
1149 #ifdef VERIFY
1150  if (flag) {
1151  r->magnitude = a->magnitude;
1152  r->normalized = a->normalized;
1153  }
1154 #endif
1155 }
1156 
1157 static SECP256K1_INLINE void secp256k1_fe_half(secp256k1_fe *r) {
1158  uint32_t t0 = r->n[0], t1 = r->n[1], t2 = r->n[2], t3 = r->n[3], t4 = r->n[4],
1159  t5 = r->n[5], t6 = r->n[6], t7 = r->n[7], t8 = r->n[8], t9 = r->n[9];
1160  uint32_t one = (uint32_t)1;
1161  uint32_t mask = -(t0 & one) >> 6;
1162 
1163 #ifdef VERIFY
1164  secp256k1_fe_verify(r);
1165  VERIFY_CHECK(r->magnitude < 32);
1166 #endif
1167 
1168  /* Bounds analysis (over the rationals).
1169  *
1170  * Let m = r->magnitude
1171  * C = 0x3FFFFFFUL * 2
1172  * D = 0x03FFFFFUL * 2
1173  *
1174  * Initial bounds: t0..t8 <= C * m
1175  * t9 <= D * m
1176  */
1177 
1178  t0 += 0x3FFFC2FUL & mask;
1179  t1 += 0x3FFFFBFUL & mask;
1180  t2 += mask;
1181  t3 += mask;
1182  t4 += mask;
1183  t5 += mask;
1184  t6 += mask;
1185  t7 += mask;
1186  t8 += mask;
1187  t9 += mask >> 4;
1188 
1189  VERIFY_CHECK((t0 & one) == 0);
1190 
1191  /* t0..t8: added <= C/2
1192  * t9: added <= D/2
1193  *
1194  * Current bounds: t0..t8 <= C * (m + 1/2)
1195  * t9 <= D * (m + 1/2)
1196  */
1197 
1198  r->n[0] = (t0 >> 1) + ((t1 & one) << 25);
1199  r->n[1] = (t1 >> 1) + ((t2 & one) << 25);
1200  r->n[2] = (t2 >> 1) + ((t3 & one) << 25);
1201  r->n[3] = (t3 >> 1) + ((t4 & one) << 25);
1202  r->n[4] = (t4 >> 1) + ((t5 & one) << 25);
1203  r->n[5] = (t5 >> 1) + ((t6 & one) << 25);
1204  r->n[6] = (t6 >> 1) + ((t7 & one) << 25);
1205  r->n[7] = (t7 >> 1) + ((t8 & one) << 25);
1206  r->n[8] = (t8 >> 1) + ((t9 & one) << 25);
1207  r->n[9] = (t9 >> 1);
1208 
1209  /* t0..t8: shifted right and added <= C/4 + 1/2
1210  * t9: shifted right
1211  *
1212  * Current bounds: t0..t8 <= C * (m/2 + 1/2)
1213  * t9 <= D * (m/2 + 1/4)
1214  */
1215 
1216 #ifdef VERIFY
1217  /* Therefore the output magnitude (M) has to be set such that:
1218  * t0..t8: C * M >= C * (m/2 + 1/2)
1219  * t9: D * M >= D * (m/2 + 1/4)
1220  *
1221  * It suffices for all limbs that, for any input magnitude m:
1222  * M >= m/2 + 1/2
1223  *
1224  * and since we want the smallest such integer value for M:
1225  * M == floor(m/2) + 1
1226  */
1227  r->magnitude = (r->magnitude >> 1) + 1;
1228  r->normalized = 0;
1229  secp256k1_fe_verify(r);
1230 #endif
1231 }
1232 
1233 static SECP256K1_INLINE void secp256k1_fe_storage_cmov(secp256k1_fe_storage *r, const secp256k1_fe_storage *a, int flag) {
1234  uint32_t mask0, mask1;
1235  SECP256K1_CHECKMEM_CHECK_VERIFY(r->n, sizeof(r->n));
1236  mask0 = flag + ~((uint32_t)0);
1237  mask1 = ~mask0;
1238  r->n[0] = (r->n[0] & mask0) | (a->n[0] & mask1);
1239  r->n[1] = (r->n[1] & mask0) | (a->n[1] & mask1);
1240  r->n[2] = (r->n[2] & mask0) | (a->n[2] & mask1);
1241  r->n[3] = (r->n[3] & mask0) | (a->n[3] & mask1);
1242  r->n[4] = (r->n[4] & mask0) | (a->n[4] & mask1);
1243  r->n[5] = (r->n[5] & mask0) | (a->n[5] & mask1);
1244  r->n[6] = (r->n[6] & mask0) | (a->n[6] & mask1);
1245  r->n[7] = (r->n[7] & mask0) | (a->n[7] & mask1);
1246 }
1247 
1248 static void secp256k1_fe_to_storage(secp256k1_fe_storage *r, const secp256k1_fe *a) {
1249 #ifdef VERIFY
1250  VERIFY_CHECK(a->normalized);
1251 #endif
1252  r->n[0] = a->n[0] | a->n[1] << 26;
1253  r->n[1] = a->n[1] >> 6 | a->n[2] << 20;
1254  r->n[2] = a->n[2] >> 12 | a->n[3] << 14;
1255  r->n[3] = a->n[3] >> 18 | a->n[4] << 8;
1256  r->n[4] = a->n[4] >> 24 | a->n[5] << 2 | a->n[6] << 28;
1257  r->n[5] = a->n[6] >> 4 | a->n[7] << 22;
1258  r->n[6] = a->n[7] >> 10 | a->n[8] << 16;
1259  r->n[7] = a->n[8] >> 16 | a->n[9] << 10;
1260 }
1261 
1262 static SECP256K1_INLINE void secp256k1_fe_from_storage(secp256k1_fe *r, const secp256k1_fe_storage *a) {
1263  r->n[0] = a->n[0] & 0x3FFFFFFUL;
1264  r->n[1] = a->n[0] >> 26 | ((a->n[1] << 6) & 0x3FFFFFFUL);
1265  r->n[2] = a->n[1] >> 20 | ((a->n[2] << 12) & 0x3FFFFFFUL);
1266  r->n[3] = a->n[2] >> 14 | ((a->n[3] << 18) & 0x3FFFFFFUL);
1267  r->n[4] = a->n[3] >> 8 | ((a->n[4] << 24) & 0x3FFFFFFUL);
1268  r->n[5] = (a->n[4] >> 2) & 0x3FFFFFFUL;
1269  r->n[6] = a->n[4] >> 28 | ((a->n[5] << 4) & 0x3FFFFFFUL);
1270  r->n[7] = a->n[5] >> 22 | ((a->n[6] << 10) & 0x3FFFFFFUL);
1271  r->n[8] = a->n[6] >> 16 | ((a->n[7] << 16) & 0x3FFFFFFUL);
1272  r->n[9] = a->n[7] >> 10;
1273 #ifdef VERIFY
1274  r->magnitude = 1;
1275  r->normalized = 1;
1276  secp256k1_fe_verify(r);
1277 #endif
1278 }
1279 
1280 static void secp256k1_fe_from_signed30(secp256k1_fe *r, const secp256k1_modinv32_signed30 *a) {
1281  const uint32_t M26 = UINT32_MAX >> 6;
1282  const uint32_t a0 = a->v[0], a1 = a->v[1], a2 = a->v[2], a3 = a->v[3], a4 = a->v[4],
1283  a5 = a->v[5], a6 = a->v[6], a7 = a->v[7], a8 = a->v[8];
1284 
1285  /* The output from secp256k1_modinv32{_var} should be normalized to range [0,modulus), and
1286  * have limbs in [0,2^30). The modulus is < 2^256, so the top limb must be below 2^(256-30*8).
1287  */
1288  VERIFY_CHECK(a0 >> 30 == 0);
1289  VERIFY_CHECK(a1 >> 30 == 0);
1290  VERIFY_CHECK(a2 >> 30 == 0);
1291  VERIFY_CHECK(a3 >> 30 == 0);
1292  VERIFY_CHECK(a4 >> 30 == 0);
1293  VERIFY_CHECK(a5 >> 30 == 0);
1294  VERIFY_CHECK(a6 >> 30 == 0);
1295  VERIFY_CHECK(a7 >> 30 == 0);
1296  VERIFY_CHECK(a8 >> 16 == 0);
1297 
1298  r->n[0] = a0 & M26;
1299  r->n[1] = (a0 >> 26 | a1 << 4) & M26;
1300  r->n[2] = (a1 >> 22 | a2 << 8) & M26;
1301  r->n[3] = (a2 >> 18 | a3 << 12) & M26;
1302  r->n[4] = (a3 >> 14 | a4 << 16) & M26;
1303  r->n[5] = (a4 >> 10 | a5 << 20) & M26;
1304  r->n[6] = (a5 >> 6 | a6 << 24) & M26;
1305  r->n[7] = (a6 >> 2 ) & M26;
1306  r->n[8] = (a6 >> 28 | a7 << 2) & M26;
1307  r->n[9] = (a7 >> 24 | a8 << 6);
1308 
1309 #ifdef VERIFY
1310  r->magnitude = 1;
1311  r->normalized = 1;
1312  secp256k1_fe_verify(r);
1313 #endif
1314 }
1315 
1316 static void secp256k1_fe_to_signed30(secp256k1_modinv32_signed30 *r, const secp256k1_fe *a) {
1317  const uint32_t M30 = UINT32_MAX >> 2;
1318  const uint64_t a0 = a->n[0], a1 = a->n[1], a2 = a->n[2], a3 = a->n[3], a4 = a->n[4],
1319  a5 = a->n[5], a6 = a->n[6], a7 = a->n[7], a8 = a->n[8], a9 = a->n[9];
1320 
1321 #ifdef VERIFY
1322  VERIFY_CHECK(a->normalized);
1323 #endif
1324 
1325  r->v[0] = (a0 | a1 << 26) & M30;
1326  r->v[1] = (a1 >> 4 | a2 << 22) & M30;
1327  r->v[2] = (a2 >> 8 | a3 << 18) & M30;
1328  r->v[3] = (a3 >> 12 | a4 << 14) & M30;
1329  r->v[4] = (a4 >> 16 | a5 << 10) & M30;
1330  r->v[5] = (a5 >> 20 | a6 << 6) & M30;
1331  r->v[6] = (a6 >> 24 | a7 << 2
1332  | a8 << 28) & M30;
1333  r->v[7] = (a8 >> 2 | a9 << 24) & M30;
1334  r->v[8] = a9 >> 6;
1335 }
1336 
1337 static const secp256k1_modinv32_modinfo secp256k1_const_modinfo_fe = {
1338  {{-0x3D1, -4, 0, 0, 0, 0, 0, 0, 65536}},
1339  0x2DDACACFL
1340 };
1341 
1342 static void secp256k1_fe_inv(secp256k1_fe *r, const secp256k1_fe *x) {
1343  secp256k1_fe tmp;
1345 
1346  tmp = *x;
1347  secp256k1_fe_normalize(&tmp);
1348  secp256k1_fe_to_signed30(&s, &tmp);
1349  secp256k1_modinv32(&s, &secp256k1_const_modinfo_fe);
1350  secp256k1_fe_from_signed30(r, &s);
1351 
1352  VERIFY_CHECK(secp256k1_fe_normalizes_to_zero(r) == secp256k1_fe_normalizes_to_zero(&tmp));
1353 }
1354 
1355 static void secp256k1_fe_inv_var(secp256k1_fe *r, const secp256k1_fe *x) {
1356  secp256k1_fe tmp;
1358 
1359  tmp = *x;
1360  secp256k1_fe_normalize_var(&tmp);
1361  secp256k1_fe_to_signed30(&s, &tmp);
1362  secp256k1_modinv32_var(&s, &secp256k1_const_modinfo_fe);
1363  secp256k1_fe_from_signed30(r, &s);
1364 
1365  VERIFY_CHECK(secp256k1_fe_normalizes_to_zero(r) == secp256k1_fe_normalizes_to_zero(&tmp));
1366 }
1367 
1368 #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
unsigned int uint32_t
Definition: stdint.h:126
t3
Definition: pow225521.h:103
unsigned __int64 uint64_t
Definition: stdint.h:136
uint32_t n[10]
Definition: field_10x26.h:16
const GenericPointer< typename T::ValueType > T2 T::AllocatorType & a
Definition: pointer.h:1124
t2
Definition: pow22523.h:103
#define UINT32_MAX
Definition: stdint.h:188
#define VERIFY_BITS(x, n)
t1
Definition: pow22523.h:58
#define SECP256K1_CHECKMEM_CHECK_VERIFY(p, len)
Definition: checkmem.h:85
#define SECP256K1_RESTRICT
Definition: util.h:137
unsigned char u8
Definition: chacha_private.h:9