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