Bitcoin Core  22.99.0
P2P Digital Currency
field_5x52_int128_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_INNER5X52_IMPL_H
8 #define SECP256K1_FIELD_INNER5X52_IMPL_H
9 
10 #include <stdint.h>
11 
12 #ifdef VERIFY
13 #define VERIFY_BITS(x, n) VERIFY_CHECK(((x) >> (n)) == 0)
14 #else
15 #define VERIFY_BITS(x, n) do { } while(0)
16 #endif
17 
18 SECP256K1_INLINE static void secp256k1_fe_mul_inner(uint64_t *r, const uint64_t *a, const uint64_t * SECP256K1_RESTRICT b) {
19  uint128_t c, d;
20  uint64_t t3, t4, tx, u0;
21  uint64_t a0 = a[0], a1 = a[1], a2 = a[2], a3 = a[3], a4 = a[4];
22  const uint64_t M = 0xFFFFFFFFFFFFFULL, R = 0x1000003D10ULL;
23 
24  VERIFY_BITS(a[0], 56);
25  VERIFY_BITS(a[1], 56);
26  VERIFY_BITS(a[2], 56);
27  VERIFY_BITS(a[3], 56);
28  VERIFY_BITS(a[4], 52);
29  VERIFY_BITS(b[0], 56);
30  VERIFY_BITS(b[1], 56);
31  VERIFY_BITS(b[2], 56);
32  VERIFY_BITS(b[3], 56);
33  VERIFY_BITS(b[4], 52);
34  VERIFY_CHECK(r != b);
35  VERIFY_CHECK(a != b);
36 
37  /* [... a b c] is a shorthand for ... + a<<104 + b<<52 + c<<0 mod n.
38  * for 0 <= x <= 4, px is a shorthand for sum(a[i]*b[x-i], i=0..x).
39  * for 4 <= x <= 8, px is a shorthand for sum(a[i]*b[x-i], i=(x-4)..4)
40  * Note that [x 0 0 0 0 0] = [x*R].
41  */
42 
43  d = (uint128_t)a0 * b[3]
44  + (uint128_t)a1 * b[2]
45  + (uint128_t)a2 * b[1]
46  + (uint128_t)a3 * b[0];
47  VERIFY_BITS(d, 114);
48  /* [d 0 0 0] = [p3 0 0 0] */
49  c = (uint128_t)a4 * b[4];
50  VERIFY_BITS(c, 112);
51  /* [c 0 0 0 0 d 0 0 0] = [p8 0 0 0 0 p3 0 0 0] */
52  d += (uint128_t)R * (uint64_t)c; c >>= 64;
53  VERIFY_BITS(d, 115);
54  VERIFY_BITS(c, 48);
55  /* [(c<<12) 0 0 0 0 0 d 0 0 0] = [p8 0 0 0 0 p3 0 0 0] */
56  t3 = d & M; d >>= 52;
57  VERIFY_BITS(t3, 52);
58  VERIFY_BITS(d, 63);
59  /* [(c<<12) 0 0 0 0 d t3 0 0 0] = [p8 0 0 0 0 p3 0 0 0] */
60 
61  d += (uint128_t)a0 * b[4]
62  + (uint128_t)a1 * b[3]
63  + (uint128_t)a2 * b[2]
64  + (uint128_t)a3 * b[1]
65  + (uint128_t)a4 * b[0];
66  VERIFY_BITS(d, 115);
67  /* [(c<<12) 0 0 0 0 d t3 0 0 0] = [p8 0 0 0 p4 p3 0 0 0] */
68  d += (uint128_t)(R << 12) * (uint64_t)c;
69  VERIFY_BITS(d, 116);
70  /* [d t3 0 0 0] = [p8 0 0 0 p4 p3 0 0 0] */
71  t4 = d & M; d >>= 52;
72  VERIFY_BITS(t4, 52);
73  VERIFY_BITS(d, 64);
74  /* [d t4 t3 0 0 0] = [p8 0 0 0 p4 p3 0 0 0] */
75  tx = (t4 >> 48); t4 &= (M >> 4);
76  VERIFY_BITS(tx, 4);
77  VERIFY_BITS(t4, 48);
78  /* [d t4+(tx<<48) t3 0 0 0] = [p8 0 0 0 p4 p3 0 0 0] */
79 
80  c = (uint128_t)a0 * b[0];
81  VERIFY_BITS(c, 112);
82  /* [d t4+(tx<<48) t3 0 0 c] = [p8 0 0 0 p4 p3 0 0 p0] */
83  d += (uint128_t)a1 * b[4]
84  + (uint128_t)a2 * b[3]
85  + (uint128_t)a3 * b[2]
86  + (uint128_t)a4 * b[1];
87  VERIFY_BITS(d, 115);
88  /* [d t4+(tx<<48) t3 0 0 c] = [p8 0 0 p5 p4 p3 0 0 p0] */
89  u0 = d & M; d >>= 52;
90  VERIFY_BITS(u0, 52);
91  VERIFY_BITS(d, 63);
92  /* [d u0 t4+(tx<<48) t3 0 0 c] = [p8 0 0 p5 p4 p3 0 0 p0] */
93  /* [d 0 t4+(tx<<48)+(u0<<52) t3 0 0 c] = [p8 0 0 p5 p4 p3 0 0 p0] */
94  u0 = (u0 << 4) | tx;
95  VERIFY_BITS(u0, 56);
96  /* [d 0 t4+(u0<<48) t3 0 0 c] = [p8 0 0 p5 p4 p3 0 0 p0] */
97  c += (uint128_t)u0 * (R >> 4);
98  VERIFY_BITS(c, 115);
99  /* [d 0 t4 t3 0 0 c] = [p8 0 0 p5 p4 p3 0 0 p0] */
100  r[0] = c & M; c >>= 52;
101  VERIFY_BITS(r[0], 52);
102  VERIFY_BITS(c, 61);
103  /* [d 0 t4 t3 0 c r0] = [p8 0 0 p5 p4 p3 0 0 p0] */
104 
105  c += (uint128_t)a0 * b[1]
106  + (uint128_t)a1 * b[0];
107  VERIFY_BITS(c, 114);
108  /* [d 0 t4 t3 0 c r0] = [p8 0 0 p5 p4 p3 0 p1 p0] */
109  d += (uint128_t)a2 * b[4]
110  + (uint128_t)a3 * b[3]
111  + (uint128_t)a4 * b[2];
112  VERIFY_BITS(d, 114);
113  /* [d 0 t4 t3 0 c r0] = [p8 0 p6 p5 p4 p3 0 p1 p0] */
114  c += (d & M) * R; d >>= 52;
115  VERIFY_BITS(c, 115);
116  VERIFY_BITS(d, 62);
117  /* [d 0 0 t4 t3 0 c r0] = [p8 0 p6 p5 p4 p3 0 p1 p0] */
118  r[1] = c & M; c >>= 52;
119  VERIFY_BITS(r[1], 52);
120  VERIFY_BITS(c, 63);
121  /* [d 0 0 t4 t3 c r1 r0] = [p8 0 p6 p5 p4 p3 0 p1 p0] */
122 
123  c += (uint128_t)a0 * b[2]
124  + (uint128_t)a1 * b[1]
125  + (uint128_t)a2 * b[0];
126  VERIFY_BITS(c, 114);
127  /* [d 0 0 t4 t3 c r1 r0] = [p8 0 p6 p5 p4 p3 p2 p1 p0] */
128  d += (uint128_t)a3 * b[4]
129  + (uint128_t)a4 * b[3];
130  VERIFY_BITS(d, 114);
131  /* [d 0 0 t4 t3 c t1 r0] = [p8 p7 p6 p5 p4 p3 p2 p1 p0] */
132  c += (uint128_t)R * (uint64_t)d; d >>= 64;
133  VERIFY_BITS(c, 115);
134  VERIFY_BITS(d, 50);
135  /* [(d<<12) 0 0 0 t4 t3 c r1 r0] = [p8 p7 p6 p5 p4 p3 p2 p1 p0] */
136 
137  r[2] = c & M; c >>= 52;
138  VERIFY_BITS(r[2], 52);
139  VERIFY_BITS(c, 63);
140  /* [(d<<12) 0 0 0 t4 t3+c r2 r1 r0] = [p8 p7 p6 p5 p4 p3 p2 p1 p0] */
141  c += (uint128_t)(R << 12) * (uint64_t)d + t3;
142  VERIFY_BITS(c, 100);
143  /* [t4 c r2 r1 r0] = [p8 p7 p6 p5 p4 p3 p2 p1 p0] */
144  r[3] = c & M; c >>= 52;
145  VERIFY_BITS(r[3], 52);
146  VERIFY_BITS(c, 48);
147  /* [t4+c r3 r2 r1 r0] = [p8 p7 p6 p5 p4 p3 p2 p1 p0] */
148  c += t4;
149  VERIFY_BITS(c, 49);
150  /* [c r3 r2 r1 r0] = [p8 p7 p6 p5 p4 p3 p2 p1 p0] */
151  r[4] = c;
152  VERIFY_BITS(r[4], 49);
153  /* [r4 r3 r2 r1 r0] = [p8 p7 p6 p5 p4 p3 p2 p1 p0] */
154 }
155 
156 SECP256K1_INLINE static void secp256k1_fe_sqr_inner(uint64_t *r, const uint64_t *a) {
157  uint128_t c, d;
158  uint64_t a0 = a[0], a1 = a[1], a2 = a[2], a3 = a[3], a4 = a[4];
159  int64_t t3, t4, tx, u0;
160  const uint64_t M = 0xFFFFFFFFFFFFFULL, R = 0x1000003D10ULL;
161 
162  VERIFY_BITS(a[0], 56);
163  VERIFY_BITS(a[1], 56);
164  VERIFY_BITS(a[2], 56);
165  VERIFY_BITS(a[3], 56);
166  VERIFY_BITS(a[4], 52);
167 
173  d = (uint128_t)(a0*2) * a3
174  + (uint128_t)(a1*2) * a2;
175  VERIFY_BITS(d, 114);
176  /* [d 0 0 0] = [p3 0 0 0] */
177  c = (uint128_t)a4 * a4;
178  VERIFY_BITS(c, 112);
179  /* [c 0 0 0 0 d 0 0 0] = [p8 0 0 0 0 p3 0 0 0] */
180  d += (uint128_t)R * (uint64_t)c; c >>= 64;
181  VERIFY_BITS(d, 115);
182  VERIFY_BITS(c, 48);
183  /* [(c<<12) 0 0 0 0 0 d 0 0 0] = [p8 0 0 0 0 p3 0 0 0] */
184  t3 = d & M; d >>= 52;
185  VERIFY_BITS(t3, 52);
186  VERIFY_BITS(d, 63);
187  /* [(c<<12) 0 0 0 0 d t3 0 0 0] = [p8 0 0 0 0 p3 0 0 0] */
188 
189  a4 *= 2;
190  d += (uint128_t)a0 * a4
191  + (uint128_t)(a1*2) * a3
192  + (uint128_t)a2 * a2;
193  VERIFY_BITS(d, 115);
194  /* [(c<<12) 0 0 0 0 d t3 0 0 0] = [p8 0 0 0 p4 p3 0 0 0] */
195  d += (uint128_t)(R << 12) * (uint64_t)c;
196  VERIFY_BITS(d, 116);
197  /* [d t3 0 0 0] = [p8 0 0 0 p4 p3 0 0 0] */
198  t4 = d & M; d >>= 52;
199  VERIFY_BITS(t4, 52);
200  VERIFY_BITS(d, 64);
201  /* [d t4 t3 0 0 0] = [p8 0 0 0 p4 p3 0 0 0] */
202  tx = (t4 >> 48); t4 &= (M >> 4);
203  VERIFY_BITS(tx, 4);
204  VERIFY_BITS(t4, 48);
205  /* [d t4+(tx<<48) t3 0 0 0] = [p8 0 0 0 p4 p3 0 0 0] */
206 
207  c = (uint128_t)a0 * a0;
208  VERIFY_BITS(c, 112);
209  /* [d t4+(tx<<48) t3 0 0 c] = [p8 0 0 0 p4 p3 0 0 p0] */
210  d += (uint128_t)a1 * a4
211  + (uint128_t)(a2*2) * a3;
212  VERIFY_BITS(d, 114);
213  /* [d t4+(tx<<48) t3 0 0 c] = [p8 0 0 p5 p4 p3 0 0 p0] */
214  u0 = d & M; d >>= 52;
215  VERIFY_BITS(u0, 52);
216  VERIFY_BITS(d, 62);
217  /* [d u0 t4+(tx<<48) t3 0 0 c] = [p8 0 0 p5 p4 p3 0 0 p0] */
218  /* [d 0 t4+(tx<<48)+(u0<<52) t3 0 0 c] = [p8 0 0 p5 p4 p3 0 0 p0] */
219  u0 = (u0 << 4) | tx;
220  VERIFY_BITS(u0, 56);
221  /* [d 0 t4+(u0<<48) t3 0 0 c] = [p8 0 0 p5 p4 p3 0 0 p0] */
222  c += (uint128_t)u0 * (R >> 4);
223  VERIFY_BITS(c, 113);
224  /* [d 0 t4 t3 0 0 c] = [p8 0 0 p5 p4 p3 0 0 p0] */
225  r[0] = c & M; c >>= 52;
226  VERIFY_BITS(r[0], 52);
227  VERIFY_BITS(c, 61);
228  /* [d 0 t4 t3 0 c r0] = [p8 0 0 p5 p4 p3 0 0 p0] */
229 
230  a0 *= 2;
231  c += (uint128_t)a0 * a1;
232  VERIFY_BITS(c, 114);
233  /* [d 0 t4 t3 0 c r0] = [p8 0 0 p5 p4 p3 0 p1 p0] */
234  d += (uint128_t)a2 * a4
235  + (uint128_t)a3 * a3;
236  VERIFY_BITS(d, 114);
237  /* [d 0 t4 t3 0 c r0] = [p8 0 p6 p5 p4 p3 0 p1 p0] */
238  c += (d & M) * R; d >>= 52;
239  VERIFY_BITS(c, 115);
240  VERIFY_BITS(d, 62);
241  /* [d 0 0 t4 t3 0 c r0] = [p8 0 p6 p5 p4 p3 0 p1 p0] */
242  r[1] = c & M; c >>= 52;
243  VERIFY_BITS(r[1], 52);
244  VERIFY_BITS(c, 63);
245  /* [d 0 0 t4 t3 c r1 r0] = [p8 0 p6 p5 p4 p3 0 p1 p0] */
246 
247  c += (uint128_t)a0 * a2
248  + (uint128_t)a1 * a1;
249  VERIFY_BITS(c, 114);
250  /* [d 0 0 t4 t3 c r1 r0] = [p8 0 p6 p5 p4 p3 p2 p1 p0] */
251  d += (uint128_t)a3 * a4;
252  VERIFY_BITS(d, 114);
253  /* [d 0 0 t4 t3 c r1 r0] = [p8 p7 p6 p5 p4 p3 p2 p1 p0] */
254  c += (uint128_t)R * (uint64_t)d; d >>= 64;
255  VERIFY_BITS(c, 115);
256  VERIFY_BITS(d, 50);
257  /* [(d<<12) 0 0 0 t4 t3 c r1 r0] = [p8 p7 p6 p5 p4 p3 p2 p1 p0] */
258  r[2] = c & M; c >>= 52;
259  VERIFY_BITS(r[2], 52);
260  VERIFY_BITS(c, 63);
261  /* [(d<<12) 0 0 0 t4 t3+c r2 r1 r0] = [p8 p7 p6 p5 p4 p3 p2 p1 p0] */
262 
263  c += (uint128_t)(R << 12) * (uint64_t)d + t3;
264  VERIFY_BITS(c, 100);
265  /* [t4 c r2 r1 r0] = [p8 p7 p6 p5 p4 p3 p2 p1 p0] */
266  r[3] = c & M; c >>= 52;
267  VERIFY_BITS(r[3], 52);
268  VERIFY_BITS(c, 48);
269  /* [t4+c r3 r2 r1 r0] = [p8 p7 p6 p5 p4 p3 p2 p1 p0] */
270  c += t4;
271  VERIFY_BITS(c, 49);
272  /* [c r3 r2 r1 r0] = [p8 p7 p6 p5 p4 p3 p2 p1 p0] */
273  r[4] = c;
274  VERIFY_BITS(r[4], 49);
275  /* [r4 r3 r2 r1 r0] = [p8 p7 p6 p5 p4 p3 p2 p1 p0] */
276 }
277 
278 #endif /* SECP256K1_FIELD_INNER5X52_IMPL_H */
VERIFY_CHECK
#define VERIFY_CHECK(cond)
Definition: util.h:95
ByteUnit::M
@ M
SECP256K1_RESTRICT
#define SECP256K1_RESTRICT
Definition: util.h:155
secp256k1_fe_mul_inner
static SECP256K1_INLINE void secp256k1_fe_mul_inner(uint64_t *r, const uint64_t *a, const uint64_t *SECP256K1_RESTRICT b)
Definition: field_5x52_int128_impl.h:18
secp256k1_fe_sqr_inner
static SECP256K1_INLINE void secp256k1_fe_sqr_inner(uint64_t *r, const uint64_t *a)
Definition: field_5x52_int128_impl.h:156
VERIFY_BITS
#define VERIFY_BITS(x, n)
Definition: field_5x52_int128_impl.h:15
SECP256K1_INLINE
#define SECP256K1_INLINE
Definition: secp256k1.h:127