Bitcoin ABC  0.28.12
P2P Digital Currency
scalar_4x64_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_SCALAR_REPR_IMPL_H
8 #define SECP256K1_SCALAR_REPR_IMPL_H
9 
10 #include "modinv64_impl.h"
11 
12 /* Limbs of the secp256k1 order. */
13 #define SECP256K1_N_0 ((uint64_t)0xBFD25E8CD0364141ULL)
14 #define SECP256K1_N_1 ((uint64_t)0xBAAEDCE6AF48A03BULL)
15 #define SECP256K1_N_2 ((uint64_t)0xFFFFFFFFFFFFFFFEULL)
16 #define SECP256K1_N_3 ((uint64_t)0xFFFFFFFFFFFFFFFFULL)
17 
18 /* Limbs of 2^256 minus the secp256k1 order. */
19 #define SECP256K1_N_C_0 (~SECP256K1_N_0 + 1)
20 #define SECP256K1_N_C_1 (~SECP256K1_N_1)
21 #define SECP256K1_N_C_2 (1)
22 
23 /* Limbs of half the secp256k1 order. */
24 #define SECP256K1_N_H_0 ((uint64_t)0xDFE92F46681B20A0ULL)
25 #define SECP256K1_N_H_1 ((uint64_t)0x5D576E7357A4501DULL)
26 #define SECP256K1_N_H_2 ((uint64_t)0xFFFFFFFFFFFFFFFFULL)
27 #define SECP256K1_N_H_3 ((uint64_t)0x7FFFFFFFFFFFFFFFULL)
28 
30  r->d[0] = 0;
31  r->d[1] = 0;
32  r->d[2] = 0;
33  r->d[3] = 0;
34 }
35 
37  r->d[0] = v;
38  r->d[1] = 0;
39  r->d[2] = 0;
40  r->d[3] = 0;
41 }
42 
43 SECP256K1_INLINE static unsigned int secp256k1_scalar_get_bits(const secp256k1_scalar *a, unsigned int offset, unsigned int count) {
44  VERIFY_CHECK((offset + count - 1) >> 6 == offset >> 6);
45  return (a->d[offset >> 6] >> (offset & 0x3F)) & ((((uint64_t)1) << count) - 1);
46 }
47 
48 SECP256K1_INLINE static unsigned int secp256k1_scalar_get_bits_var(const secp256k1_scalar *a, unsigned int offset, unsigned int count) {
49  VERIFY_CHECK(count < 32);
50  VERIFY_CHECK(offset + count <= 256);
51  if ((offset + count - 1) >> 6 == offset >> 6) {
52  return secp256k1_scalar_get_bits(a, offset, count);
53  } else {
54  VERIFY_CHECK((offset >> 6) + 1 < 4);
55  return ((a->d[offset >> 6] >> (offset & 0x3F)) | (a->d[(offset >> 6) + 1] << (64 - (offset & 0x3F)))) & ((((uint64_t)1) << count) - 1);
56  }
57 }
58 
60  int yes = 0;
61  int no = 0;
62  no |= (a->d[3] < SECP256K1_N_3); /* No need for a > check. */
63  no |= (a->d[2] < SECP256K1_N_2);
64  yes |= (a->d[2] > SECP256K1_N_2) & ~no;
65  no |= (a->d[1] < SECP256K1_N_1);
66  yes |= (a->d[1] > SECP256K1_N_1) & ~no;
67  yes |= (a->d[0] >= SECP256K1_N_0) & ~no;
68  return yes;
69 }
70 
71 SECP256K1_INLINE static int secp256k1_scalar_reduce(secp256k1_scalar *r, unsigned int overflow) {
72  uint128_t t;
73  VERIFY_CHECK(overflow <= 1);
74  t = (uint128_t)r->d[0] + overflow * SECP256K1_N_C_0;
75  r->d[0] = t & 0xFFFFFFFFFFFFFFFFULL; t >>= 64;
76  t += (uint128_t)r->d[1] + overflow * SECP256K1_N_C_1;
77  r->d[1] = t & 0xFFFFFFFFFFFFFFFFULL; t >>= 64;
78  t += (uint128_t)r->d[2] + overflow * SECP256K1_N_C_2;
79  r->d[2] = t & 0xFFFFFFFFFFFFFFFFULL; t >>= 64;
80  t += (uint64_t)r->d[3];
81  r->d[3] = t & 0xFFFFFFFFFFFFFFFFULL;
82  return overflow;
83 }
84 
86  int overflow;
87  uint128_t t = (uint128_t)a->d[0] + b->d[0];
88  r->d[0] = t & 0xFFFFFFFFFFFFFFFFULL; t >>= 64;
89  t += (uint128_t)a->d[1] + b->d[1];
90  r->d[1] = t & 0xFFFFFFFFFFFFFFFFULL; t >>= 64;
91  t += (uint128_t)a->d[2] + b->d[2];
92  r->d[2] = t & 0xFFFFFFFFFFFFFFFFULL; t >>= 64;
93  t += (uint128_t)a->d[3] + b->d[3];
94  r->d[3] = t & 0xFFFFFFFFFFFFFFFFULL; t >>= 64;
95  overflow = t + secp256k1_scalar_check_overflow(r);
96  VERIFY_CHECK(overflow == 0 || overflow == 1);
97  secp256k1_scalar_reduce(r, overflow);
98  return overflow;
99 }
100 
101 static void secp256k1_scalar_cadd_bit(secp256k1_scalar *r, unsigned int bit, int flag) {
102  uint128_t t;
103  VERIFY_CHECK(bit < 256);
104  bit += ((uint32_t) flag - 1) & 0x100; /* forcing (bit >> 6) > 3 makes this a noop */
105  t = (uint128_t)r->d[0] + (((uint64_t)((bit >> 6) == 0)) << (bit & 0x3F));
106  r->d[0] = t & 0xFFFFFFFFFFFFFFFFULL; t >>= 64;
107  t += (uint128_t)r->d[1] + (((uint64_t)((bit >> 6) == 1)) << (bit & 0x3F));
108  r->d[1] = t & 0xFFFFFFFFFFFFFFFFULL; t >>= 64;
109  t += (uint128_t)r->d[2] + (((uint64_t)((bit >> 6) == 2)) << (bit & 0x3F));
110  r->d[2] = t & 0xFFFFFFFFFFFFFFFFULL; t >>= 64;
111  t += (uint128_t)r->d[3] + (((uint64_t)((bit >> 6) == 3)) << (bit & 0x3F));
112  r->d[3] = t & 0xFFFFFFFFFFFFFFFFULL;
113 #ifdef VERIFY
114  VERIFY_CHECK((t >> 64) == 0);
116 #endif
117 }
118 
119 static void secp256k1_scalar_set_b32(secp256k1_scalar *r, const unsigned char *b32, int *overflow) {
120  int over;
121  r->d[0] = (uint64_t)b32[31] | (uint64_t)b32[30] << 8 | (uint64_t)b32[29] << 16 | (uint64_t)b32[28] << 24 | (uint64_t)b32[27] << 32 | (uint64_t)b32[26] << 40 | (uint64_t)b32[25] << 48 | (uint64_t)b32[24] << 56;
122  r->d[1] = (uint64_t)b32[23] | (uint64_t)b32[22] << 8 | (uint64_t)b32[21] << 16 | (uint64_t)b32[20] << 24 | (uint64_t)b32[19] << 32 | (uint64_t)b32[18] << 40 | (uint64_t)b32[17] << 48 | (uint64_t)b32[16] << 56;
123  r->d[2] = (uint64_t)b32[15] | (uint64_t)b32[14] << 8 | (uint64_t)b32[13] << 16 | (uint64_t)b32[12] << 24 | (uint64_t)b32[11] << 32 | (uint64_t)b32[10] << 40 | (uint64_t)b32[9] << 48 | (uint64_t)b32[8] << 56;
124  r->d[3] = (uint64_t)b32[7] | (uint64_t)b32[6] << 8 | (uint64_t)b32[5] << 16 | (uint64_t)b32[4] << 24 | (uint64_t)b32[3] << 32 | (uint64_t)b32[2] << 40 | (uint64_t)b32[1] << 48 | (uint64_t)b32[0] << 56;
126  if (overflow) {
127  *overflow = over;
128  }
129 }
130 
131 static void secp256k1_scalar_get_b32(unsigned char *bin, const secp256k1_scalar* a) {
132  bin[0] = a->d[3] >> 56; bin[1] = a->d[3] >> 48; bin[2] = a->d[3] >> 40; bin[3] = a->d[3] >> 32; bin[4] = a->d[3] >> 24; bin[5] = a->d[3] >> 16; bin[6] = a->d[3] >> 8; bin[7] = a->d[3];
133  bin[8] = a->d[2] >> 56; bin[9] = a->d[2] >> 48; bin[10] = a->d[2] >> 40; bin[11] = a->d[2] >> 32; bin[12] = a->d[2] >> 24; bin[13] = a->d[2] >> 16; bin[14] = a->d[2] >> 8; bin[15] = a->d[2];
134  bin[16] = a->d[1] >> 56; bin[17] = a->d[1] >> 48; bin[18] = a->d[1] >> 40; bin[19] = a->d[1] >> 32; bin[20] = a->d[1] >> 24; bin[21] = a->d[1] >> 16; bin[22] = a->d[1] >> 8; bin[23] = a->d[1];
135  bin[24] = a->d[0] >> 56; bin[25] = a->d[0] >> 48; bin[26] = a->d[0] >> 40; bin[27] = a->d[0] >> 32; bin[28] = a->d[0] >> 24; bin[29] = a->d[0] >> 16; bin[30] = a->d[0] >> 8; bin[31] = a->d[0];
136 }
137 
139  return (a->d[0] | a->d[1] | a->d[2] | a->d[3]) == 0;
140 }
141 
143  uint64_t nonzero = 0xFFFFFFFFFFFFFFFFULL * (secp256k1_scalar_is_zero(a) == 0);
144  uint128_t t = (uint128_t)(~a->d[0]) + SECP256K1_N_0 + 1;
145  r->d[0] = t & nonzero; t >>= 64;
146  t += (uint128_t)(~a->d[1]) + SECP256K1_N_1;
147  r->d[1] = t & nonzero; t >>= 64;
148  t += (uint128_t)(~a->d[2]) + SECP256K1_N_2;
149  r->d[2] = t & nonzero; t >>= 64;
150  t += (uint128_t)(~a->d[3]) + SECP256K1_N_3;
151  r->d[3] = t & nonzero;
152 }
153 
155  return ((a->d[0] ^ 1) | a->d[1] | a->d[2] | a->d[3]) == 0;
156 }
157 
159  int yes = 0;
160  int no = 0;
161  no |= (a->d[3] < SECP256K1_N_H_3);
162  yes |= (a->d[3] > SECP256K1_N_H_3) & ~no;
163  no |= (a->d[2] < SECP256K1_N_H_2) & ~yes; /* No need for a > check. */
164  no |= (a->d[1] < SECP256K1_N_H_1) & ~yes;
165  yes |= (a->d[1] > SECP256K1_N_H_1) & ~no;
166  yes |= (a->d[0] > SECP256K1_N_H_0) & ~no;
167  return yes;
168 }
169 
171  /* If we are flag = 0, mask = 00...00 and this is a no-op;
172  * if we are flag = 1, mask = 11...11 and this is identical to secp256k1_scalar_negate */
173  uint64_t mask = !flag - 1;
174  uint64_t nonzero = (secp256k1_scalar_is_zero(r) != 0) - 1;
175  uint128_t t = (uint128_t)(r->d[0] ^ mask) + ((SECP256K1_N_0 + 1) & mask);
176  r->d[0] = t & nonzero; t >>= 64;
177  t += (uint128_t)(r->d[1] ^ mask) + (SECP256K1_N_1 & mask);
178  r->d[1] = t & nonzero; t >>= 64;
179  t += (uint128_t)(r->d[2] ^ mask) + (SECP256K1_N_2 & mask);
180  r->d[2] = t & nonzero; t >>= 64;
181  t += (uint128_t)(r->d[3] ^ mask) + (SECP256K1_N_3 & mask);
182  r->d[3] = t & nonzero;
183  return 2 * (mask == 0) - 1;
184 }
185 
186 /* Inspired by the macros in OpenSSL's crypto/bn/asm/x86_64-gcc.c. */
187 
189 #define muladd(a,b) { \
190  uint64_t tl, th; \
191  { \
192  uint128_t t = (uint128_t)a * b; \
193  th = t >> 64; /* at most 0xFFFFFFFFFFFFFFFE */ \
194  tl = t; \
195  } \
196  c0 += tl; /* overflow is handled on the next line */ \
197  th += (c0 < tl); /* at most 0xFFFFFFFFFFFFFFFF */ \
198  c1 += th; /* overflow is handled on the next line */ \
199  c2 += (c1 < th); /* never overflows by contract (verified in the next line) */ \
200  VERIFY_CHECK((c1 >= th) || (c2 != 0)); \
201 }
202 
204 #define muladd_fast(a,b) { \
205  uint64_t tl, th; \
206  { \
207  uint128_t t = (uint128_t)a * b; \
208  th = t >> 64; /* at most 0xFFFFFFFFFFFFFFFE */ \
209  tl = t; \
210  } \
211  c0 += tl; /* overflow is handled on the next line */ \
212  th += (c0 < tl); /* at most 0xFFFFFFFFFFFFFFFF */ \
213  c1 += th; /* never overflows by contract (verified in the next line) */ \
214  VERIFY_CHECK(c1 >= th); \
215 }
216 
218 #define sumadd(a) { \
219  unsigned int over; \
220  c0 += (a); /* overflow is handled on the next line */ \
221  over = (c0 < (a)); \
222  c1 += over; /* overflow is handled on the next line */ \
223  c2 += (c1 < over); /* never overflows by contract */ \
224 }
225 
227 #define sumadd_fast(a) { \
228  c0 += (a); /* overflow is handled on the next line */ \
229  c1 += (c0 < (a)); /* never overflows by contract (verified the next line) */ \
230  VERIFY_CHECK((c1 != 0) | (c0 >= (a))); \
231  VERIFY_CHECK(c2 == 0); \
232 }
233 
235 #define extract(n) { \
236  (n) = c0; \
237  c0 = c1; \
238  c1 = c2; \
239  c2 = 0; \
240 }
241 
243 #define extract_fast(n) { \
244  (n) = c0; \
245  c0 = c1; \
246  c1 = 0; \
247  VERIFY_CHECK(c2 == 0); \
248 }
249 
250 static void secp256k1_scalar_reduce_512(secp256k1_scalar *r, const uint64_t *l) {
251 #ifdef USE_ASM_X86_64
252  /* Reduce 512 bits into 385. */
253  uint64_t m0, m1, m2, m3, m4, m5, m6;
254  uint64_t p0, p1, p2, p3, p4;
255  uint64_t c;
256 
257  __asm__ __volatile__(
258  /* Preload. */
259  "movq 32(%%rsi), %%r11\n"
260  "movq 40(%%rsi), %%r12\n"
261  "movq 48(%%rsi), %%r13\n"
262  "movq 56(%%rsi), %%r14\n"
263  /* Initialize r8,r9,r10 */
264  "movq 0(%%rsi), %%r8\n"
265  "xorq %%r9, %%r9\n"
266  "xorq %%r10, %%r10\n"
267  /* (r8,r9) += n0 * c0 */
268  "movq %8, %%rax\n"
269  "mulq %%r11\n"
270  "addq %%rax, %%r8\n"
271  "adcq %%rdx, %%r9\n"
272  /* extract m0 */
273  "movq %%r8, %q0\n"
274  "xorq %%r8, %%r8\n"
275  /* (r9,r10) += l1 */
276  "addq 8(%%rsi), %%r9\n"
277  "adcq $0, %%r10\n"
278  /* (r9,r10,r8) += n1 * c0 */
279  "movq %8, %%rax\n"
280  "mulq %%r12\n"
281  "addq %%rax, %%r9\n"
282  "adcq %%rdx, %%r10\n"
283  "adcq $0, %%r8\n"
284  /* (r9,r10,r8) += n0 * c1 */
285  "movq %9, %%rax\n"
286  "mulq %%r11\n"
287  "addq %%rax, %%r9\n"
288  "adcq %%rdx, %%r10\n"
289  "adcq $0, %%r8\n"
290  /* extract m1 */
291  "movq %%r9, %q1\n"
292  "xorq %%r9, %%r9\n"
293  /* (r10,r8,r9) += l2 */
294  "addq 16(%%rsi), %%r10\n"
295  "adcq $0, %%r8\n"
296  "adcq $0, %%r9\n"
297  /* (r10,r8,r9) += n2 * c0 */
298  "movq %8, %%rax\n"
299  "mulq %%r13\n"
300  "addq %%rax, %%r10\n"
301  "adcq %%rdx, %%r8\n"
302  "adcq $0, %%r9\n"
303  /* (r10,r8,r9) += n1 * c1 */
304  "movq %9, %%rax\n"
305  "mulq %%r12\n"
306  "addq %%rax, %%r10\n"
307  "adcq %%rdx, %%r8\n"
308  "adcq $0, %%r9\n"
309  /* (r10,r8,r9) += n0 */
310  "addq %%r11, %%r10\n"
311  "adcq $0, %%r8\n"
312  "adcq $0, %%r9\n"
313  /* extract m2 */
314  "movq %%r10, %q2\n"
315  "xorq %%r10, %%r10\n"
316  /* (r8,r9,r10) += l3 */
317  "addq 24(%%rsi), %%r8\n"
318  "adcq $0, %%r9\n"
319  "adcq $0, %%r10\n"
320  /* (r8,r9,r10) += n3 * c0 */
321  "movq %8, %%rax\n"
322  "mulq %%r14\n"
323  "addq %%rax, %%r8\n"
324  "adcq %%rdx, %%r9\n"
325  "adcq $0, %%r10\n"
326  /* (r8,r9,r10) += n2 * c1 */
327  "movq %9, %%rax\n"
328  "mulq %%r13\n"
329  "addq %%rax, %%r8\n"
330  "adcq %%rdx, %%r9\n"
331  "adcq $0, %%r10\n"
332  /* (r8,r9,r10) += n1 */
333  "addq %%r12, %%r8\n"
334  "adcq $0, %%r9\n"
335  "adcq $0, %%r10\n"
336  /* extract m3 */
337  "movq %%r8, %q3\n"
338  "xorq %%r8, %%r8\n"
339  /* (r9,r10,r8) += n3 * c1 */
340  "movq %9, %%rax\n"
341  "mulq %%r14\n"
342  "addq %%rax, %%r9\n"
343  "adcq %%rdx, %%r10\n"
344  "adcq $0, %%r8\n"
345  /* (r9,r10,r8) += n2 */
346  "addq %%r13, %%r9\n"
347  "adcq $0, %%r10\n"
348  "adcq $0, %%r8\n"
349  /* extract m4 */
350  "movq %%r9, %q4\n"
351  /* (r10,r8) += n3 */
352  "addq %%r14, %%r10\n"
353  "adcq $0, %%r8\n"
354  /* extract m5 */
355  "movq %%r10, %q5\n"
356  /* extract m6 */
357  "movq %%r8, %q6\n"
358  : "=g"(m0), "=g"(m1), "=g"(m2), "=g"(m3), "=g"(m4), "=g"(m5), "=g"(m6)
359  : "S"(l), "i"(SECP256K1_N_C_0), "i"(SECP256K1_N_C_1)
360  : "rax", "rdx", "r8", "r9", "r10", "r11", "r12", "r13", "r14", "cc");
361 
362  /* Reduce 385 bits into 258. */
363  __asm__ __volatile__(
364  /* Preload */
365  "movq %q9, %%r11\n"
366  "movq %q10, %%r12\n"
367  "movq %q11, %%r13\n"
368  /* Initialize (r8,r9,r10) */
369  "movq %q5, %%r8\n"
370  "xorq %%r9, %%r9\n"
371  "xorq %%r10, %%r10\n"
372  /* (r8,r9) += m4 * c0 */
373  "movq %12, %%rax\n"
374  "mulq %%r11\n"
375  "addq %%rax, %%r8\n"
376  "adcq %%rdx, %%r9\n"
377  /* extract p0 */
378  "movq %%r8, %q0\n"
379  "xorq %%r8, %%r8\n"
380  /* (r9,r10) += m1 */
381  "addq %q6, %%r9\n"
382  "adcq $0, %%r10\n"
383  /* (r9,r10,r8) += m5 * c0 */
384  "movq %12, %%rax\n"
385  "mulq %%r12\n"
386  "addq %%rax, %%r9\n"
387  "adcq %%rdx, %%r10\n"
388  "adcq $0, %%r8\n"
389  /* (r9,r10,r8) += m4 * c1 */
390  "movq %13, %%rax\n"
391  "mulq %%r11\n"
392  "addq %%rax, %%r9\n"
393  "adcq %%rdx, %%r10\n"
394  "adcq $0, %%r8\n"
395  /* extract p1 */
396  "movq %%r9, %q1\n"
397  "xorq %%r9, %%r9\n"
398  /* (r10,r8,r9) += m2 */
399  "addq %q7, %%r10\n"
400  "adcq $0, %%r8\n"
401  "adcq $0, %%r9\n"
402  /* (r10,r8,r9) += m6 * c0 */
403  "movq %12, %%rax\n"
404  "mulq %%r13\n"
405  "addq %%rax, %%r10\n"
406  "adcq %%rdx, %%r8\n"
407  "adcq $0, %%r9\n"
408  /* (r10,r8,r9) += m5 * c1 */
409  "movq %13, %%rax\n"
410  "mulq %%r12\n"
411  "addq %%rax, %%r10\n"
412  "adcq %%rdx, %%r8\n"
413  "adcq $0, %%r9\n"
414  /* (r10,r8,r9) += m4 */
415  "addq %%r11, %%r10\n"
416  "adcq $0, %%r8\n"
417  "adcq $0, %%r9\n"
418  /* extract p2 */
419  "movq %%r10, %q2\n"
420  /* (r8,r9) += m3 */
421  "addq %q8, %%r8\n"
422  "adcq $0, %%r9\n"
423  /* (r8,r9) += m6 * c1 */
424  "movq %13, %%rax\n"
425  "mulq %%r13\n"
426  "addq %%rax, %%r8\n"
427  "adcq %%rdx, %%r9\n"
428  /* (r8,r9) += m5 */
429  "addq %%r12, %%r8\n"
430  "adcq $0, %%r9\n"
431  /* extract p3 */
432  "movq %%r8, %q3\n"
433  /* (r9) += m6 */
434  "addq %%r13, %%r9\n"
435  /* extract p4 */
436  "movq %%r9, %q4\n"
437  : "=&g"(p0), "=&g"(p1), "=&g"(p2), "=g"(p3), "=g"(p4)
438  : "g"(m0), "g"(m1), "g"(m2), "g"(m3), "g"(m4), "g"(m5), "g"(m6), "i"(SECP256K1_N_C_0), "i"(SECP256K1_N_C_1)
439  : "rax", "rdx", "r8", "r9", "r10", "r11", "r12", "r13", "cc");
440 
441  /* Reduce 258 bits into 256. */
442  __asm__ __volatile__(
443  /* Preload */
444  "movq %q5, %%r10\n"
445  /* (rax,rdx) = p4 * c0 */
446  "movq %7, %%rax\n"
447  "mulq %%r10\n"
448  /* (rax,rdx) += p0 */
449  "addq %q1, %%rax\n"
450  "adcq $0, %%rdx\n"
451  /* extract r0 */
452  "movq %%rax, 0(%q6)\n"
453  /* Move to (r8,r9) */
454  "movq %%rdx, %%r8\n"
455  "xorq %%r9, %%r9\n"
456  /* (r8,r9) += p1 */
457  "addq %q2, %%r8\n"
458  "adcq $0, %%r9\n"
459  /* (r8,r9) += p4 * c1 */
460  "movq %8, %%rax\n"
461  "mulq %%r10\n"
462  "addq %%rax, %%r8\n"
463  "adcq %%rdx, %%r9\n"
464  /* Extract r1 */
465  "movq %%r8, 8(%q6)\n"
466  "xorq %%r8, %%r8\n"
467  /* (r9,r8) += p4 */
468  "addq %%r10, %%r9\n"
469  "adcq $0, %%r8\n"
470  /* (r9,r8) += p2 */
471  "addq %q3, %%r9\n"
472  "adcq $0, %%r8\n"
473  /* Extract r2 */
474  "movq %%r9, 16(%q6)\n"
475  "xorq %%r9, %%r9\n"
476  /* (r8,r9) += p3 */
477  "addq %q4, %%r8\n"
478  "adcq $0, %%r9\n"
479  /* Extract r3 */
480  "movq %%r8, 24(%q6)\n"
481  /* Extract c */
482  "movq %%r9, %q0\n"
483  : "=g"(c)
484  : "g"(p0), "g"(p1), "g"(p2), "g"(p3), "g"(p4), "D"(r), "i"(SECP256K1_N_C_0), "i"(SECP256K1_N_C_1)
485  : "rax", "rdx", "r8", "r9", "r10", "cc", "memory");
486 #else
487  uint128_t c;
488  uint64_t c0, c1, c2;
489  uint64_t n0 = l[4], n1 = l[5], n2 = l[6], n3 = l[7];
490  uint64_t m0, m1, m2, m3, m4, m5;
491  uint32_t m6;
492  uint64_t p0, p1, p2, p3;
493  uint32_t p4;
494 
495  /* Reduce 512 bits into 385. */
496  /* m[0..6] = l[0..3] + n[0..3] * SECP256K1_N_C. */
497  c0 = l[0]; c1 = 0; c2 = 0;
499  extract_fast(m0);
500  sumadd_fast(l[1]);
501  muladd(n1, SECP256K1_N_C_0);
502  muladd(n0, SECP256K1_N_C_1);
503  extract(m1);
504  sumadd(l[2]);
505  muladd(n2, SECP256K1_N_C_0);
506  muladd(n1, SECP256K1_N_C_1);
507  sumadd(n0);
508  extract(m2);
509  sumadd(l[3]);
510  muladd(n3, SECP256K1_N_C_0);
511  muladd(n2, SECP256K1_N_C_1);
512  sumadd(n1);
513  extract(m3);
514  muladd(n3, SECP256K1_N_C_1);
515  sumadd(n2);
516  extract(m4);
517  sumadd_fast(n3);
518  extract_fast(m5);
519  VERIFY_CHECK(c0 <= 1);
520  m6 = c0;
521 
522  /* Reduce 385 bits into 258. */
523  /* p[0..4] = m[0..3] + m[4..6] * SECP256K1_N_C. */
524  c0 = m0; c1 = 0; c2 = 0;
526  extract_fast(p0);
527  sumadd_fast(m1);
528  muladd(m5, SECP256K1_N_C_0);
529  muladd(m4, SECP256K1_N_C_1);
530  extract(p1);
531  sumadd(m2);
532  muladd(m6, SECP256K1_N_C_0);
533  muladd(m5, SECP256K1_N_C_1);
534  sumadd(m4);
535  extract(p2);
536  sumadd_fast(m3);
538  sumadd_fast(m5);
539  extract_fast(p3);
540  p4 = c0 + m6;
541  VERIFY_CHECK(p4 <= 2);
542 
543  /* Reduce 258 bits into 256. */
544  /* r[0..3] = p[0..3] + p[4] * SECP256K1_N_C. */
545  c = p0 + (uint128_t)SECP256K1_N_C_0 * p4;
546  r->d[0] = c & 0xFFFFFFFFFFFFFFFFULL; c >>= 64;
547  c += p1 + (uint128_t)SECP256K1_N_C_1 * p4;
548  r->d[1] = c & 0xFFFFFFFFFFFFFFFFULL; c >>= 64;
549  c += p2 + (uint128_t)p4;
550  r->d[2] = c & 0xFFFFFFFFFFFFFFFFULL; c >>= 64;
551  c += p3;
552  r->d[3] = c & 0xFFFFFFFFFFFFFFFFULL; c >>= 64;
553 #endif
554 
555  /* Final reduction of r. */
557 }
558 
559 static void secp256k1_scalar_mul_512(uint64_t l[8], const secp256k1_scalar *a, const secp256k1_scalar *b) {
560 #ifdef USE_ASM_X86_64
561  const uint64_t *pb = b->d;
562  __asm__ __volatile__(
563  /* Preload */
564  "movq 0(%%rdi), %%r15\n"
565  "movq 8(%%rdi), %%rbx\n"
566  "movq 16(%%rdi), %%rcx\n"
567  "movq 0(%%rdx), %%r11\n"
568  "movq 8(%%rdx), %%r12\n"
569  "movq 16(%%rdx), %%r13\n"
570  "movq 24(%%rdx), %%r14\n"
571  /* (rax,rdx) = a0 * b0 */
572  "movq %%r15, %%rax\n"
573  "mulq %%r11\n"
574  /* Extract l0 */
575  "movq %%rax, 0(%%rsi)\n"
576  /* (r8,r9,r10) = (rdx) */
577  "movq %%rdx, %%r8\n"
578  "xorq %%r9, %%r9\n"
579  "xorq %%r10, %%r10\n"
580  /* (r8,r9,r10) += a0 * b1 */
581  "movq %%r15, %%rax\n"
582  "mulq %%r12\n"
583  "addq %%rax, %%r8\n"
584  "adcq %%rdx, %%r9\n"
585  "adcq $0, %%r10\n"
586  /* (r8,r9,r10) += a1 * b0 */
587  "movq %%rbx, %%rax\n"
588  "mulq %%r11\n"
589  "addq %%rax, %%r8\n"
590  "adcq %%rdx, %%r9\n"
591  "adcq $0, %%r10\n"
592  /* Extract l1 */
593  "movq %%r8, 8(%%rsi)\n"
594  "xorq %%r8, %%r8\n"
595  /* (r9,r10,r8) += a0 * b2 */
596  "movq %%r15, %%rax\n"
597  "mulq %%r13\n"
598  "addq %%rax, %%r9\n"
599  "adcq %%rdx, %%r10\n"
600  "adcq $0, %%r8\n"
601  /* (r9,r10,r8) += a1 * b1 */
602  "movq %%rbx, %%rax\n"
603  "mulq %%r12\n"
604  "addq %%rax, %%r9\n"
605  "adcq %%rdx, %%r10\n"
606  "adcq $0, %%r8\n"
607  /* (r9,r10,r8) += a2 * b0 */
608  "movq %%rcx, %%rax\n"
609  "mulq %%r11\n"
610  "addq %%rax, %%r9\n"
611  "adcq %%rdx, %%r10\n"
612  "adcq $0, %%r8\n"
613  /* Extract l2 */
614  "movq %%r9, 16(%%rsi)\n"
615  "xorq %%r9, %%r9\n"
616  /* (r10,r8,r9) += a0 * b3 */
617  "movq %%r15, %%rax\n"
618  "mulq %%r14\n"
619  "addq %%rax, %%r10\n"
620  "adcq %%rdx, %%r8\n"
621  "adcq $0, %%r9\n"
622  /* Preload a3 */
623  "movq 24(%%rdi), %%r15\n"
624  /* (r10,r8,r9) += a1 * b2 */
625  "movq %%rbx, %%rax\n"
626  "mulq %%r13\n"
627  "addq %%rax, %%r10\n"
628  "adcq %%rdx, %%r8\n"
629  "adcq $0, %%r9\n"
630  /* (r10,r8,r9) += a2 * b1 */
631  "movq %%rcx, %%rax\n"
632  "mulq %%r12\n"
633  "addq %%rax, %%r10\n"
634  "adcq %%rdx, %%r8\n"
635  "adcq $0, %%r9\n"
636  /* (r10,r8,r9) += a3 * b0 */
637  "movq %%r15, %%rax\n"
638  "mulq %%r11\n"
639  "addq %%rax, %%r10\n"
640  "adcq %%rdx, %%r8\n"
641  "adcq $0, %%r9\n"
642  /* Extract l3 */
643  "movq %%r10, 24(%%rsi)\n"
644  "xorq %%r10, %%r10\n"
645  /* (r8,r9,r10) += a1 * b3 */
646  "movq %%rbx, %%rax\n"
647  "mulq %%r14\n"
648  "addq %%rax, %%r8\n"
649  "adcq %%rdx, %%r9\n"
650  "adcq $0, %%r10\n"
651  /* (r8,r9,r10) += a2 * b2 */
652  "movq %%rcx, %%rax\n"
653  "mulq %%r13\n"
654  "addq %%rax, %%r8\n"
655  "adcq %%rdx, %%r9\n"
656  "adcq $0, %%r10\n"
657  /* (r8,r9,r10) += a3 * b1 */
658  "movq %%r15, %%rax\n"
659  "mulq %%r12\n"
660  "addq %%rax, %%r8\n"
661  "adcq %%rdx, %%r9\n"
662  "adcq $0, %%r10\n"
663  /* Extract l4 */
664  "movq %%r8, 32(%%rsi)\n"
665  "xorq %%r8, %%r8\n"
666  /* (r9,r10,r8) += a2 * b3 */
667  "movq %%rcx, %%rax\n"
668  "mulq %%r14\n"
669  "addq %%rax, %%r9\n"
670  "adcq %%rdx, %%r10\n"
671  "adcq $0, %%r8\n"
672  /* (r9,r10,r8) += a3 * b2 */
673  "movq %%r15, %%rax\n"
674  "mulq %%r13\n"
675  "addq %%rax, %%r9\n"
676  "adcq %%rdx, %%r10\n"
677  "adcq $0, %%r8\n"
678  /* Extract l5 */
679  "movq %%r9, 40(%%rsi)\n"
680  /* (r10,r8) += a3 * b3 */
681  "movq %%r15, %%rax\n"
682  "mulq %%r14\n"
683  "addq %%rax, %%r10\n"
684  "adcq %%rdx, %%r8\n"
685  /* Extract l6 */
686  "movq %%r10, 48(%%rsi)\n"
687  /* Extract l7 */
688  "movq %%r8, 56(%%rsi)\n"
689  : "+d"(pb)
690  : "S"(l), "D"(a->d)
691  : "rax", "rbx", "rcx", "r8", "r9", "r10", "r11", "r12", "r13", "r14", "r15", "cc", "memory");
692 #else
693  /* 160 bit accumulator. */
694  uint64_t c0 = 0, c1 = 0;
695  uint32_t c2 = 0;
696 
697  /* l[0..7] = a[0..3] * b[0..3]. */
698  muladd_fast(a->d[0], b->d[0]);
699  extract_fast(l[0]);
700  muladd(a->d[0], b->d[1]);
701  muladd(a->d[1], b->d[0]);
702  extract(l[1]);
703  muladd(a->d[0], b->d[2]);
704  muladd(a->d[1], b->d[1]);
705  muladd(a->d[2], b->d[0]);
706  extract(l[2]);
707  muladd(a->d[0], b->d[3]);
708  muladd(a->d[1], b->d[2]);
709  muladd(a->d[2], b->d[1]);
710  muladd(a->d[3], b->d[0]);
711  extract(l[3]);
712  muladd(a->d[1], b->d[3]);
713  muladd(a->d[2], b->d[2]);
714  muladd(a->d[3], b->d[1]);
715  extract(l[4]);
716  muladd(a->d[2], b->d[3]);
717  muladd(a->d[3], b->d[2]);
718  extract(l[5]);
719  muladd_fast(a->d[3], b->d[3]);
720  extract_fast(l[6]);
721  VERIFY_CHECK(c1 == 0);
722  l[7] = c0;
723 #endif
724 }
725 
726 #undef sumadd
727 #undef sumadd_fast
728 #undef muladd
729 #undef muladd_fast
730 #undef extract
731 #undef extract_fast
732 
734  uint64_t l[8];
735  secp256k1_scalar_mul_512(l, a, b);
737 }
738 
740  int ret;
741  VERIFY_CHECK(n > 0);
742  VERIFY_CHECK(n < 16);
743  ret = r->d[0] & ((1 << n) - 1);
744  r->d[0] = (r->d[0] >> n) + (r->d[1] << (64 - n));
745  r->d[1] = (r->d[1] >> n) + (r->d[2] << (64 - n));
746  r->d[2] = (r->d[2] >> n) + (r->d[3] << (64 - n));
747  r->d[3] = (r->d[3] >> n);
748  return ret;
749 }
750 
752  r1->d[0] = k->d[0];
753  r1->d[1] = k->d[1];
754  r1->d[2] = 0;
755  r1->d[3] = 0;
756  r2->d[0] = k->d[2];
757  r2->d[1] = k->d[3];
758  r2->d[2] = 0;
759  r2->d[3] = 0;
760 }
761 
763  return ((a->d[0] ^ b->d[0]) | (a->d[1] ^ b->d[1]) | (a->d[2] ^ b->d[2]) | (a->d[3] ^ b->d[3])) == 0;
764 }
765 
767  uint64_t l[8];
768  unsigned int shiftlimbs;
769  unsigned int shiftlow;
770  unsigned int shifthigh;
771  VERIFY_CHECK(shift >= 256);
772  secp256k1_scalar_mul_512(l, a, b);
773  shiftlimbs = shift >> 6;
774  shiftlow = shift & 0x3F;
775  shifthigh = 64 - shiftlow;
776  r->d[0] = shift < 512 ? (l[0 + shiftlimbs] >> shiftlow | (shift < 448 && shiftlow ? (l[1 + shiftlimbs] << shifthigh) : 0)) : 0;
777  r->d[1] = shift < 448 ? (l[1 + shiftlimbs] >> shiftlow | (shift < 384 && shiftlow ? (l[2 + shiftlimbs] << shifthigh) : 0)) : 0;
778  r->d[2] = shift < 384 ? (l[2 + shiftlimbs] >> shiftlow | (shift < 320 && shiftlow ? (l[3 + shiftlimbs] << shifthigh) : 0)) : 0;
779  r->d[3] = shift < 320 ? (l[3 + shiftlimbs] >> shiftlow) : 0;
780  secp256k1_scalar_cadd_bit(r, 0, (l[(shift - 1) >> 6] >> ((shift - 1) & 0x3f)) & 1);
781 }
782 
784  uint64_t mask0, mask1;
785  VG_CHECK_VERIFY(r->d, sizeof(r->d));
786  mask0 = flag + ~((uint64_t)0);
787  mask1 = ~mask0;
788  r->d[0] = (r->d[0] & mask0) | (a->d[0] & mask1);
789  r->d[1] = (r->d[1] & mask0) | (a->d[1] & mask1);
790  r->d[2] = (r->d[2] & mask0) | (a->d[2] & mask1);
791  r->d[3] = (r->d[3] & mask0) | (a->d[3] & mask1);
792 }
793 
795  const uint64_t a0 = a->v[0], a1 = a->v[1], a2 = a->v[2], a3 = a->v[3], a4 = a->v[4];
796 
797  /* The output from secp256k1_modinv64{_var} should be normalized to range [0,modulus), and
798  * have limbs in [0,2^62). The modulus is < 2^256, so the top limb must be below 2^(256-62*4).
799  */
800  VERIFY_CHECK(a0 >> 62 == 0);
801  VERIFY_CHECK(a1 >> 62 == 0);
802  VERIFY_CHECK(a2 >> 62 == 0);
803  VERIFY_CHECK(a3 >> 62 == 0);
804  VERIFY_CHECK(a4 >> 8 == 0);
805 
806  r->d[0] = a0 | a1 << 62;
807  r->d[1] = a1 >> 2 | a2 << 60;
808  r->d[2] = a2 >> 4 | a3 << 58;
809  r->d[3] = a3 >> 6 | a4 << 56;
810 
811 #ifdef VERIFY
813 #endif
814 }
815 
817  const uint64_t M62 = UINT64_MAX >> 2;
818  const uint64_t a0 = a->d[0], a1 = a->d[1], a2 = a->d[2], a3 = a->d[3];
819 
820 #ifdef VERIFY
822 #endif
823 
824  r->v[0] = a0 & M62;
825  r->v[1] = (a0 >> 62 | a1 << 2) & M62;
826  r->v[2] = (a1 >> 60 | a2 << 4) & M62;
827  r->v[3] = (a2 >> 58 | a3 << 6) & M62;
828  r->v[4] = a3 >> 56;
829 }
830 
832  {{0x3FD25E8CD0364141LL, 0x2ABB739ABD2280EELL, -0x15LL, 0, 256}},
833  0x34F20099AA774EC1LL
834 };
835 
838 #ifdef VERIFY
839  int zero_in = secp256k1_scalar_is_zero(x);
840 #endif
844 
845 #ifdef VERIFY
846  VERIFY_CHECK(secp256k1_scalar_is_zero(r) == zero_in);
847 #endif
848 }
849 
852 #ifdef VERIFY
853  int zero_in = secp256k1_scalar_is_zero(x);
854 #endif
858 
859 #ifdef VERIFY
860  VERIFY_CHECK(secp256k1_scalar_is_zero(r) == zero_in);
861 #endif
862 }
863 
865  return !(a->d[0] & 1);
866 }
867 
868 #endif /* SECP256K1_SCALAR_REPR_IMPL_H */
static void secp256k1_modinv64(secp256k1_modinv64_signed62 *x, const secp256k1_modinv64_modinfo *modinfo)
static void secp256k1_modinv64_var(secp256k1_modinv64_signed62 *x, const secp256k1_modinv64_modinfo *modinfo)
static SECP256K1_INLINE int secp256k1_scalar_is_even(const secp256k1_scalar *a)
static SECP256K1_INLINE int secp256k1_scalar_check_overflow(const secp256k1_scalar *a)
static SECP256K1_INLINE void secp256k1_scalar_mul_shift_var(secp256k1_scalar *r, const secp256k1_scalar *a, const secp256k1_scalar *b, unsigned int shift)
#define SECP256K1_N_3
static void secp256k1_scalar_split_128(secp256k1_scalar *r1, secp256k1_scalar *r2, const secp256k1_scalar *k)
static SECP256K1_INLINE unsigned int secp256k1_scalar_get_bits_var(const secp256k1_scalar *a, unsigned int offset, unsigned int count)
static SECP256K1_INLINE void secp256k1_scalar_clear(secp256k1_scalar *r)
#define extract(n)
Extract the lowest 64 bits of (c0,c1,c2) into n, and left shift the number 64 bits.
#define SECP256K1_N_C_2
static void secp256k1_scalar_set_b32(secp256k1_scalar *r, const unsigned char *b32, int *overflow)
#define SECP256K1_N_C_1
static void secp256k1_scalar_inverse_var(secp256k1_scalar *r, const secp256k1_scalar *x)
static const secp256k1_modinv64_modinfo secp256k1_const_modinfo_scalar
#define sumadd_fast(a)
Add a to the number defined by (c0,c1).
static void secp256k1_scalar_get_b32(unsigned char *bin, const secp256k1_scalar *a)
#define SECP256K1_N_1
static void secp256k1_scalar_reduce_512(secp256k1_scalar *r, const uint64_t *l)
#define SECP256K1_N_2
#define SECP256K1_N_H_2
static void secp256k1_scalar_from_signed62(secp256k1_scalar *r, const secp256k1_modinv64_signed62 *a)
static SECP256K1_INLINE void secp256k1_scalar_set_int(secp256k1_scalar *r, unsigned int v)
static void secp256k1_scalar_mul_512(uint64_t l[8], const secp256k1_scalar *a, const secp256k1_scalar *b)
static void secp256k1_scalar_inverse(secp256k1_scalar *r, const secp256k1_scalar *x)
#define SECP256K1_N_C_0
static SECP256K1_INLINE void secp256k1_scalar_cmov(secp256k1_scalar *r, const secp256k1_scalar *a, int flag)
#define extract_fast(n)
Extract the lowest 64 bits of (c0,c1,c2) into n, and left shift the number 64 bits.
#define muladd(a, b)
Add a*b to the number defined by (c0,c1,c2).
static void secp256k1_scalar_to_signed62(secp256k1_modinv64_signed62 *r, const secp256k1_scalar *a)
#define SECP256K1_N_H_0
static SECP256K1_INLINE int secp256k1_scalar_eq(const secp256k1_scalar *a, const secp256k1_scalar *b)
static int secp256k1_scalar_add(secp256k1_scalar *r, const secp256k1_scalar *a, const secp256k1_scalar *b)
#define sumadd(a)
Add a to the number defined by (c0,c1,c2).
static int secp256k1_scalar_cond_negate(secp256k1_scalar *r, int flag)
static void secp256k1_scalar_mul(secp256k1_scalar *r, const secp256k1_scalar *a, const secp256k1_scalar *b)
#define SECP256K1_N_H_1
static SECP256K1_INLINE int secp256k1_scalar_reduce(secp256k1_scalar *r, unsigned int overflow)
#define SECP256K1_N_0
static void secp256k1_scalar_negate(secp256k1_scalar *r, const secp256k1_scalar *a)
static SECP256K1_INLINE int secp256k1_scalar_is_zero(const secp256k1_scalar *a)
static int secp256k1_scalar_is_high(const secp256k1_scalar *a)
static SECP256K1_INLINE unsigned int secp256k1_scalar_get_bits(const secp256k1_scalar *a, unsigned int offset, unsigned int count)
#define SECP256K1_N_H_3
static void secp256k1_scalar_cadd_bit(secp256k1_scalar *r, unsigned int bit, int flag)
#define muladd_fast(a, b)
Add a*b to the number defined by (c0,c1).
static SECP256K1_INLINE int secp256k1_scalar_is_one(const secp256k1_scalar *a)
static int secp256k1_scalar_shr_int(secp256k1_scalar *r, int n)
#define VG_CHECK_VERIFY(x, y)
Definition: util.h:88
#define VERIFY_CHECK(cond)
Definition: util.h:68
#define SECP256K1_INLINE
Definition: secp256k1.h:124
A scalar modulo the group order of the secp256k1 curve.
Definition: scalar_4x64.h:13
uint64_t d[4]
Definition: scalar_4x64.h:14
static int count
Definition: tests.c:31