Electroneum
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 "checkmem.h"
11#include "util.h"
12#include "field.h"
13#include "modinv32_impl.h"
14
23
24#ifdef VERIFY
25static 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
53static 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
73static 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
128static 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
159static 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
215static 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
244static 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
296SECP256K1_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
307SECP256K1_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
316SECP256K1_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
324SECP256K1_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
335static 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
354static 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
381static 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
420SECP256K1_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
446SECP256K1_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
464SECP256K1_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 */
488void secp256k1_fe_mul_inner(uint32_t *r, const uint32_t *a, const uint32_t * SECP256K1_RESTRICT b);
489void 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
499SECP256K1_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
531
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
829SECP256K1_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
850
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
1104static 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
1121static 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
1134static 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
1157static 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
1233static 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
1248static 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
1262static 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
1280static 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
1316static 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
1337static const secp256k1_modinv32_modinfo secp256k1_const_modinfo_fe = {
1338 {{-0x3D1, -4, 0, 0, 0, 0, 0, 0, 65536}},
1339 0x2DDACACFL
1340};
1341
1342static void secp256k1_fe_inv(secp256k1_fe *r, const secp256k1_fe *x) {
1343 secp256k1_fe tmp;
1344 secp256k1_modinv32_signed30 s;
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
1355static void secp256k1_fe_inv_var(secp256k1_fe *r, const secp256k1_fe *x) {
1356 secp256k1_fe tmp;
1357 secp256k1_modinv32_signed30 s;
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 */
u8
unsigned char u8
Definition chacha_private.h:9
SECP256K1_CHECKMEM_CHECK_VERIFY
#define SECP256K1_CHECKMEM_CHECK_VERIFY(p, len)
Definition checkmem.h:85
VERIFY_CHECK
#define VERIFY_CHECK(cond)
Definition util.h:96
SECP256K1_RESTRICT
#define SECP256K1_RESTRICT
Definition util.h:137
VERIFY_BITS
#define VERIFY_BITS(x, n)
Definition field_10x26_impl.h:496
modinv32_impl.h
a
const GenericPointer< typename T::ValueType > T2 T::AllocatorType & a
Definition pointer.h:1124
t2
t2
Definition pow22523.h:103
t1
t1
Definition pow22523.h:58
t0
t0
Definition pow22523.h:53
t3
t3
Definition pow225521.h:103
SECP256K1_INLINE
#define SECP256K1_INLINE
Definition secp256k1.h:131
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_storage::n
uint32_t n[8]
Definition field_10x26.h:44
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:19
secp256k1_modinv32_signed30
Definition modinv32.h:15
secp256k1_modinv32_signed30::v
int32_t v[9]
Definition modinv32.h:16