Bitcoin ABC 0.26.3
P2P Digital Currency
Loading...
Searching...
No Matches
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
18SECP256K1_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 += (c & M) * R; c >>= 52;
53 VERIFY_BITS(d, 115);
54 VERIFY_BITS(c, 60);
55 /* [c 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 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 0 0 0 0 d t3 0 0 0] = [p8 0 0 0 p4 p3 0 0 0] */
68 d += c * R;
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 += (d & M) * R; d >>= 52;
133 VERIFY_BITS(c, 115);
134 VERIFY_BITS(d, 62);
135 /* [d 0 0 0 t4 t3 c r1 r0] = [p8 p7 p6 p5 p4 p3 p2 p1 p0] */
136
137 /* [d 0 0 0 t4 t3 c r1 r0] = [p8 p7 p6 p5 p4 p3 p2 p1 p0] */
138 r[2] = c & M; c >>= 52;
139 VERIFY_BITS(r[2], 52);
140 VERIFY_BITS(c, 63);
141 /* [d 0 0 0 t4 t3+c r2 r1 r0] = [p8 p7 p6 p5 p4 p3 p2 p1 p0] */
142 c += d * R + t3;
143 VERIFY_BITS(c, 100);
144 /* [t4 c r2 r1 r0] = [p8 p7 p6 p5 p4 p3 p2 p1 p0] */
145 r[3] = c & M; c >>= 52;
146 VERIFY_BITS(r[3], 52);
147 VERIFY_BITS(c, 48);
148 /* [t4+c r3 r2 r1 r0] = [p8 p7 p6 p5 p4 p3 p2 p1 p0] */
149 c += t4;
150 VERIFY_BITS(c, 49);
151 /* [c r3 r2 r1 r0] = [p8 p7 p6 p5 p4 p3 p2 p1 p0] */
152 r[4] = c;
153 VERIFY_BITS(r[4], 49);
154 /* [r4 r3 r2 r1 r0] = [p8 p7 p6 p5 p4 p3 p2 p1 p0] */
155}
156
157SECP256K1_INLINE static void secp256k1_fe_sqr_inner(uint64_t *r, const uint64_t *a) {
158 uint128_t c, d;
159 uint64_t a0 = a[0], a1 = a[1], a2 = a[2], a3 = a[3], a4 = a[4];
160 int64_t t3, t4, tx, u0;
161 const uint64_t M = 0xFFFFFFFFFFFFFULL, R = 0x1000003D10ULL;
162
163 VERIFY_BITS(a[0], 56);
164 VERIFY_BITS(a[1], 56);
165 VERIFY_BITS(a[2], 56);
166 VERIFY_BITS(a[3], 56);
167 VERIFY_BITS(a[4], 52);
168
174 d = (uint128_t)(a0*2) * a3
175 + (uint128_t)(a1*2) * a2;
176 VERIFY_BITS(d, 114);
177 /* [d 0 0 0] = [p3 0 0 0] */
178 c = (uint128_t)a4 * a4;
179 VERIFY_BITS(c, 112);
180 /* [c 0 0 0 0 d 0 0 0] = [p8 0 0 0 0 p3 0 0 0] */
181 d += (c & M) * R; c >>= 52;
182 VERIFY_BITS(d, 115);
183 VERIFY_BITS(c, 60);
184 /* [c 0 0 0 0 0 d 0 0 0] = [p8 0 0 0 0 p3 0 0 0] */
185 t3 = d & M; d >>= 52;
186 VERIFY_BITS(t3, 52);
187 VERIFY_BITS(d, 63);
188 /* [c 0 0 0 0 d t3 0 0 0] = [p8 0 0 0 0 p3 0 0 0] */
189
190 a4 *= 2;
191 d += (uint128_t)a0 * a4
192 + (uint128_t)(a1*2) * a3
193 + (uint128_t)a2 * a2;
194 VERIFY_BITS(d, 115);
195 /* [c 0 0 0 0 d t3 0 0 0] = [p8 0 0 0 p4 p3 0 0 0] */
196 d += c * R;
197 VERIFY_BITS(d, 116);
198 /* [d t3 0 0 0] = [p8 0 0 0 p4 p3 0 0 0] */
199 t4 = d & M; d >>= 52;
200 VERIFY_BITS(t4, 52);
201 VERIFY_BITS(d, 64);
202 /* [d t4 t3 0 0 0] = [p8 0 0 0 p4 p3 0 0 0] */
203 tx = (t4 >> 48); t4 &= (M >> 4);
204 VERIFY_BITS(tx, 4);
205 VERIFY_BITS(t4, 48);
206 /* [d t4+(tx<<48) t3 0 0 0] = [p8 0 0 0 p4 p3 0 0 0] */
207
208 c = (uint128_t)a0 * a0;
209 VERIFY_BITS(c, 112);
210 /* [d t4+(tx<<48) t3 0 0 c] = [p8 0 0 0 p4 p3 0 0 p0] */
211 d += (uint128_t)a1 * a4
212 + (uint128_t)(a2*2) * a3;
213 VERIFY_BITS(d, 114);
214 /* [d t4+(tx<<48) t3 0 0 c] = [p8 0 0 p5 p4 p3 0 0 p0] */
215 u0 = d & M; d >>= 52;
216 VERIFY_BITS(u0, 52);
217 VERIFY_BITS(d, 62);
218 /* [d u0 t4+(tx<<48) t3 0 0 c] = [p8 0 0 p5 p4 p3 0 0 p0] */
219 /* [d 0 t4+(tx<<48)+(u0<<52) t3 0 0 c] = [p8 0 0 p5 p4 p3 0 0 p0] */
220 u0 = (u0 << 4) | tx;
221 VERIFY_BITS(u0, 56);
222 /* [d 0 t4+(u0<<48) t3 0 0 c] = [p8 0 0 p5 p4 p3 0 0 p0] */
223 c += (uint128_t)u0 * (R >> 4);
224 VERIFY_BITS(c, 113);
225 /* [d 0 t4 t3 0 0 c] = [p8 0 0 p5 p4 p3 0 0 p0] */
226 r[0] = c & M; c >>= 52;
227 VERIFY_BITS(r[0], 52);
228 VERIFY_BITS(c, 61);
229 /* [d 0 t4 t3 0 c r0] = [p8 0 0 p5 p4 p3 0 0 p0] */
230
231 a0 *= 2;
232 c += (uint128_t)a0 * a1;
233 VERIFY_BITS(c, 114);
234 /* [d 0 t4 t3 0 c r0] = [p8 0 0 p5 p4 p3 0 p1 p0] */
235 d += (uint128_t)a2 * a4
236 + (uint128_t)a3 * a3;
237 VERIFY_BITS(d, 114);
238 /* [d 0 t4 t3 0 c r0] = [p8 0 p6 p5 p4 p3 0 p1 p0] */
239 c += (d & M) * R; d >>= 52;
240 VERIFY_BITS(c, 115);
241 VERIFY_BITS(d, 62);
242 /* [d 0 0 t4 t3 0 c r0] = [p8 0 p6 p5 p4 p3 0 p1 p0] */
243 r[1] = c & M; c >>= 52;
244 VERIFY_BITS(r[1], 52);
245 VERIFY_BITS(c, 63);
246 /* [d 0 0 t4 t3 c r1 r0] = [p8 0 p6 p5 p4 p3 0 p1 p0] */
247
248 c += (uint128_t)a0 * a2
249 + (uint128_t)a1 * a1;
250 VERIFY_BITS(c, 114);
251 /* [d 0 0 t4 t3 c r1 r0] = [p8 0 p6 p5 p4 p3 p2 p1 p0] */
252 d += (uint128_t)a3 * a4;
253 VERIFY_BITS(d, 114);
254 /* [d 0 0 t4 t3 c r1 r0] = [p8 p7 p6 p5 p4 p3 p2 p1 p0] */
255 c += (d & M) * R; d >>= 52;
256 VERIFY_BITS(c, 115);
257 VERIFY_BITS(d, 62);
258 /* [d 0 0 0 t4 t3 c r1 r0] = [p8 p7 p6 p5 p4 p3 p2 p1 p0] */
259 r[2] = c & M; c >>= 52;
260 VERIFY_BITS(r[2], 52);
261 VERIFY_BITS(c, 63);
262 /* [d 0 0 0 t4 t3+c r2 r1 r0] = [p8 p7 p6 p5 p4 p3 p2 p1 p0] */
263
264 c += d * R + t3;
265 VERIFY_BITS(c, 100);
266 /* [t4 c r2 r1 r0] = [p8 p7 p6 p5 p4 p3 p2 p1 p0] */
267 r[3] = c & M; c >>= 52;
268 VERIFY_BITS(r[3], 52);
269 VERIFY_BITS(c, 48);
270 /* [t4+c r3 r2 r1 r0] = [p8 p7 p6 p5 p4 p3 p2 p1 p0] */
271 c += t4;
272 VERIFY_BITS(c, 49);
273 /* [c r3 r2 r1 r0] = [p8 p7 p6 p5 p4 p3 p2 p1 p0] */
274 r[4] = c;
275 VERIFY_BITS(r[4], 49);
276 /* [r4 r3 r2 r1 r0] = [p8 p7 p6 p5 p4 p3 p2 p1 p0] */
277}
278
279#endif /* SECP256K1_FIELD_INNER5X52_IMPL_H */
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
VERIFY_BITS
#define VERIFY_BITS(x, n)
Definition field_5x52_int128_impl.h:15
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:157
GetRand
T GetRand(T nMax=std::numeric_limits< T >::max()) noexcept
Generate a uniform random integer of type T in the range [0..nMax) nMax defaults to std::numeric_limi...
Definition random.h:85
VERIFY_CHECK
#define VERIFY_CHECK(cond)
Definition util.h:68
SECP256K1_RESTRICT
#define SECP256K1_RESTRICT
Definition util.h:158
SECP256K1_INLINE
#define SECP256K1_INLINE
Definition secp256k1.h:127
Generated on Sat Nov 23 2024 02:38:00 for Bitcoin ABC by doxygen 1.9.8