7#ifndef SECP256K1_SCALAR_REPR_IMPL_H
8#define SECP256K1_SCALAR_REPR_IMPL_H
15#define SECP256K1_N_0 ((uint32_t)0xD0364141UL)
16#define SECP256K1_N_1 ((uint32_t)0xBFD25E8CUL)
17#define SECP256K1_N_2 ((uint32_t)0xAF48A03BUL)
18#define SECP256K1_N_3 ((uint32_t)0xBAAEDCE6UL)
19#define SECP256K1_N_4 ((uint32_t)0xFFFFFFFEUL)
20#define SECP256K1_N_5 ((uint32_t)0xFFFFFFFFUL)
21#define SECP256K1_N_6 ((uint32_t)0xFFFFFFFFUL)
22#define SECP256K1_N_7 ((uint32_t)0xFFFFFFFFUL)
25#define SECP256K1_N_C_0 (~SECP256K1_N_0 + 1)
26#define SECP256K1_N_C_1 (~SECP256K1_N_1)
27#define SECP256K1_N_C_2 (~SECP256K1_N_2)
28#define SECP256K1_N_C_3 (~SECP256K1_N_3)
29#define SECP256K1_N_C_4 (1)
32#define SECP256K1_N_H_0 ((uint32_t)0x681B20A0UL)
33#define SECP256K1_N_H_1 ((uint32_t)0xDFE92F46UL)
34#define SECP256K1_N_H_2 ((uint32_t)0x57A4501DUL)
35#define SECP256K1_N_H_3 ((uint32_t)0x5D576E73UL)
36#define SECP256K1_N_H_4 ((uint32_t)0xFFFFFFFFUL)
37#define SECP256K1_N_H_5 ((uint32_t)0xFFFFFFFFUL)
38#define SECP256K1_N_H_6 ((uint32_t)0xFFFFFFFFUL)
39#define SECP256K1_N_H_7 ((uint32_t)0x7FFFFFFFUL)
69 return (a->
d[offset >> 5] >> (offset & 0x1F)) & ((1 <<
count) - 1);
77 if ((offset +
count - 1) >> 5 == offset >> 5) {
81 return ((a->
d[offset >> 5] >> (offset & 0x1F)) | (a->
d[(offset >> 5) + 1] << (32 - (offset & 0x1F)))) & ((((uint32_t)1) <<
count) - 1);
108 r->
d[0] = t & 0xFFFFFFFFUL; t >>= 32;
110 r->
d[1] = t & 0xFFFFFFFFUL; t >>= 32;
112 r->
d[2] = t & 0xFFFFFFFFUL; t >>= 32;
114 r->
d[3] = t & 0xFFFFFFFFUL; t >>= 32;
116 r->
d[4] = t & 0xFFFFFFFFUL; t >>= 32;
117 t += (uint64_t)r->
d[5];
118 r->
d[5] = t & 0xFFFFFFFFUL; t >>= 32;
119 t += (uint64_t)r->
d[6];
120 r->
d[6] = t & 0xFFFFFFFFUL; t >>= 32;
121 t += (uint64_t)r->
d[7];
122 r->
d[7] = t & 0xFFFFFFFFUL;
130 uint64_t t = (uint64_t)a->
d[0] + b->
d[0];
134 r->
d[0] = t & 0xFFFFFFFFULL; t >>= 32;
135 t += (uint64_t)a->
d[1] + b->
d[1];
136 r->
d[1] = t & 0xFFFFFFFFULL; t >>= 32;
137 t += (uint64_t)a->
d[2] + b->
d[2];
138 r->
d[2] = t & 0xFFFFFFFFULL; t >>= 32;
139 t += (uint64_t)a->
d[3] + b->
d[3];
140 r->
d[3] = t & 0xFFFFFFFFULL; t >>= 32;
141 t += (uint64_t)a->
d[4] + b->
d[4];
142 r->
d[4] = t & 0xFFFFFFFFULL; t >>= 32;
143 t += (uint64_t)a->
d[5] + b->
d[5];
144 r->
d[5] = t & 0xFFFFFFFFULL; t >>= 32;
145 t += (uint64_t)a->
d[6] + b->
d[6];
146 r->
d[6] = t & 0xFFFFFFFFULL; t >>= 32;
147 t += (uint64_t)a->
d[7] + b->
d[7];
148 r->
d[7] = t & 0xFFFFFFFFULL; t >>= 32;
159 volatile int vflag = flag;
163 bit += ((uint32_t) vflag - 1) & 0x100;
164 t = (uint64_t)r->
d[0] + (((uint32_t)((bit >> 5) == 0)) << (bit & 0x1F));
165 r->
d[0] = t & 0xFFFFFFFFULL; t >>= 32;
166 t += (uint64_t)r->
d[1] + (((uint32_t)((bit >> 5) == 1)) << (bit & 0x1F));
167 r->
d[1] = t & 0xFFFFFFFFULL; t >>= 32;
168 t += (uint64_t)r->
d[2] + (((uint32_t)((bit >> 5) == 2)) << (bit & 0x1F));
169 r->
d[2] = t & 0xFFFFFFFFULL; t >>= 32;
170 t += (uint64_t)r->
d[3] + (((uint32_t)((bit >> 5) == 3)) << (bit & 0x1F));
171 r->
d[3] = t & 0xFFFFFFFFULL; t >>= 32;
172 t += (uint64_t)r->
d[4] + (((uint32_t)((bit >> 5) == 4)) << (bit & 0x1F));
173 r->
d[4] = t & 0xFFFFFFFFULL; t >>= 32;
174 t += (uint64_t)r->
d[5] + (((uint32_t)((bit >> 5) == 5)) << (bit & 0x1F));
175 r->
d[5] = t & 0xFFFFFFFFULL; t >>= 32;
176 t += (uint64_t)r->
d[6] + (((uint32_t)((bit >> 5) == 6)) << (bit & 0x1F));
177 r->
d[6] = t & 0xFFFFFFFFULL; t >>= 32;
178 t += (uint64_t)r->
d[7] + (((uint32_t)((bit >> 5) == 7)) << (bit & 0x1F));
179 r->
d[7] = t & 0xFFFFFFFFULL;
221 return (a->
d[0] | a->
d[1] | a->
d[2] | a->
d[3] | a->
d[4] | a->
d[5] | a->
d[6] | a->
d[7]) == 0;
229 r->
d[0] = t & nonzero; t >>= 32;
231 r->
d[1] = t & nonzero; t >>= 32;
233 r->
d[2] = t & nonzero; t >>= 32;
235 r->
d[3] = t & nonzero; t >>= 32;
237 r->
d[4] = t & nonzero; t >>= 32;
239 r->
d[5] = t & nonzero; t >>= 32;
241 r->
d[6] = t & nonzero; t >>= 32;
243 r->
d[7] = t & nonzero;
263 uint32_t mask = -(uint32_t)(a->
d[0] & 1U);
264 uint64_t t = (uint32_t)((a->
d[0] >> 1) | (a->
d[1] << 31));
268 r->
d[0] = t; t >>= 32;
269 t += (uint32_t)((a->
d[1] >> 1) | (a->
d[2] << 31));
271 r->
d[1] = t; t >>= 32;
272 t += (uint32_t)((a->
d[2] >> 1) | (a->
d[3] << 31));
274 r->
d[2] = t; t >>= 32;
275 t += (uint32_t)((a->
d[3] >> 1) | (a->
d[4] << 31));
277 r->
d[3] = t; t >>= 32;
278 t += (uint32_t)((a->
d[4] >> 1) | (a->
d[5] << 31));
280 r->
d[4] = t; t >>= 32;
281 t += (uint32_t)((a->
d[5] >> 1) | (a->
d[6] << 31));
283 r->
d[5] = t; t >>= 32;
284 t += (uint32_t)((a->
d[6] >> 1) | (a->
d[7] << 31));
286 r->
d[6] = t; t >>= 32;
300 return ((a->
d[0] ^ 1) | a->
d[1] | a->
d[2] | a->
d[3] | a->
d[4] | a->
d[5] | a->
d[6] | a->
d[7]) == 0;
326 volatile int vflag = flag;
327 uint32_t mask = -vflag;
329 uint64_t t = (uint64_t)(r->
d[0] ^ mask) + ((
SECP256K1_N_0 + 1) & mask);
332 r->
d[0] = t & nonzero; t >>= 32;
334 r->
d[1] = t & nonzero; t >>= 32;
336 r->
d[2] = t & nonzero; t >>= 32;
338 r->
d[3] = t & nonzero; t >>= 32;
340 r->
d[4] = t & nonzero; t >>= 32;
342 r->
d[5] = t & nonzero; t >>= 32;
344 r->
d[6] = t & nonzero; t >>= 32;
346 r->
d[7] = t & nonzero;
349 return 2 * (mask == 0) - 1;
356#define muladd(a,b) { \
359 uint64_t t = (uint64_t)a * b; \
367 VERIFY_CHECK((c1 >= th) || (c2 != 0)); \
371#define muladd_fast(a,b) { \
374 uint64_t t = (uint64_t)a * b; \
381 VERIFY_CHECK(c1 >= th); \
394#define sumadd_fast(a) { \
397 VERIFY_CHECK((c1 != 0) | (c0 >= (a))); \
398 VERIFY_CHECK(c2 == 0); \
402#define extract(n) { \
410#define extract_fast(n) { \
414 VERIFY_CHECK(c2 == 0); \
419 uint32_t n0 = l[8], n1 = l[9], n2 = l[10], n3 = l[11], n4 = l[12], n5 = l[13], n6 = l[14], n7 = l[15];
420 uint32_t m0, m1, m2, m3, m4, m5, m6, m7, m8, m9, m10, m11, m12;
421 uint32_t p0, p1, p2, p3, p4, p5, p6, p7, p8;
428 c0 = l[0]; c1 = 0; c2 = 0;
493 c0 = m0; c1 = 0; c2 = 0;
539 r->
d[0] = c & 0xFFFFFFFFUL; c >>= 32;
541 r->
d[1] = c & 0xFFFFFFFFUL; c >>= 32;
543 r->
d[2] = c & 0xFFFFFFFFUL; c >>= 32;
545 r->
d[3] = c & 0xFFFFFFFFUL; c >>= 32;
546 c += p4 + (uint64_t)p8;
547 r->
d[4] = c & 0xFFFFFFFFUL; c >>= 32;
549 r->
d[5] = c & 0xFFFFFFFFUL; c >>= 32;
551 r->
d[6] = c & 0xFFFFFFFFUL; c >>= 32;
553 r->
d[7] = c & 0xFFFFFFFFUL; c >>= 32;
561 uint32_t c0 = 0, c1 = 0, c2 = 0;
693 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]) | (a->
d[4] ^ b->
d[4]) | (a->
d[5] ^ b->
d[5]) | (a->
d[6] ^ b->
d[6]) | (a->
d[7] ^ b->
d[7])) == 0;
698 unsigned int shiftlimbs;
699 unsigned int shiftlow;
700 unsigned int shifthigh;
706 shiftlimbs = shift >> 5;
707 shiftlow = shift & 0x1F;
708 shifthigh = 32 - shiftlow;
709 r->
d[0] = shift < 512 ? (l[0 + shiftlimbs] >> shiftlow | (shift < 480 && shiftlow ? (l[1 + shiftlimbs] << shifthigh) : 0)) : 0;
710 r->
d[1] = shift < 480 ? (l[1 + shiftlimbs] >> shiftlow | (shift < 448 && shiftlow ? (l[2 + shiftlimbs] << shifthigh) : 0)) : 0;
711 r->
d[2] = shift < 448 ? (l[2 + shiftlimbs] >> shiftlow | (shift < 416 && shiftlow ? (l[3 + shiftlimbs] << shifthigh) : 0)) : 0;
712 r->
d[3] = shift < 416 ? (l[3 + shiftlimbs] >> shiftlow | (shift < 384 && shiftlow ? (l[4 + shiftlimbs] << shifthigh) : 0)) : 0;
713 r->
d[4] = shift < 384 ? (l[4 + shiftlimbs] >> shiftlow | (shift < 352 && shiftlow ? (l[5 + shiftlimbs] << shifthigh) : 0)) : 0;
714 r->
d[5] = shift < 352 ? (l[5 + shiftlimbs] >> shiftlow | (shift < 320 && shiftlow ? (l[6 + shiftlimbs] << shifthigh) : 0)) : 0;
715 r->
d[6] = shift < 320 ? (l[6 + shiftlimbs] >> shiftlow | (shift < 288 && shiftlow ? (l[7 + shiftlimbs] << shifthigh) : 0)) : 0;
716 r->
d[7] = shift < 288 ? (l[7 + shiftlimbs] >> shiftlow) : 0;
723 uint32_t mask0, mask1;
724 volatile int vflag = flag;
728 mask0 = vflag + ~((uint32_t)0);
730 r->
d[0] = (r->
d[0] & mask0) | (a->
d[0] & mask1);
731 r->
d[1] = (r->
d[1] & mask0) | (a->
d[1] & mask1);
732 r->
d[2] = (r->
d[2] & mask0) | (a->
d[2] & mask1);
733 r->
d[3] = (r->
d[3] & mask0) | (a->
d[3] & mask1);
734 r->
d[4] = (r->
d[4] & mask0) | (a->
d[4] & mask1);
735 r->
d[5] = (r->
d[5] & mask0) | (a->
d[5] & mask1);
736 r->
d[6] = (r->
d[6] & mask0) | (a->
d[6] & mask1);
737 r->
d[7] = (r->
d[7] & mask0) | (a->
d[7] & mask1);
743 const uint32_t a0 = a->
v[0], a1 = a->
v[1], a2 = a->
v[2], a3 = a->
v[3], a4 = a->
v[4],
744 a5 = a->
v[5], a6 = a->
v[6], a7 = a->
v[7], a8 = a->
v[8];
759 r->
d[0] = a0 | a1 << 30;
760 r->
d[1] = a1 >> 2 | a2 << 28;
761 r->
d[2] = a2 >> 4 | a3 << 26;
762 r->
d[3] = a3 >> 6 | a4 << 24;
763 r->
d[4] = a4 >> 8 | a5 << 22;
764 r->
d[5] = a5 >> 10 | a6 << 20;
765 r->
d[6] = a6 >> 12 | a7 << 18;
766 r->
d[7] = a7 >> 14 | a8 << 16;
772 const uint32_t M30 = UINT32_MAX >> 2;
773 const uint32_t a0 = a->
d[0], a1 = a->
d[1], a2 = a->
d[2], a3 = a->
d[3],
774 a4 = a->
d[4], a5 = a->
d[5], a6 = a->
d[6], a7 = a->
d[7];
778 r->
v[1] = (a0 >> 30 | a1 << 2) & M30;
779 r->
v[2] = (a1 >> 28 | a2 << 4) & M30;
780 r->
v[3] = (a2 >> 26 | a3 << 6) & M30;
781 r->
v[4] = (a3 >> 24 | a4 << 8) & M30;
782 r->
v[5] = (a4 >> 22 | a5 << 10) & M30;
783 r->
v[6] = (a5 >> 20 | a6 << 12) & M30;
784 r->
v[7] = (a6 >> 18 | a7 << 14) & M30;
789 {{0x10364141L, 0x3F497A33L, 0x348A03BBL, 0x2BB739ABL, -0x146L, 0, 0, 0, 65536}},
830 return !(a->
d[0] & 1);
#define SECP256K1_CHECKMEM_CHECK_VERIFY(p, len)
static void secp256k1_modinv32_var(secp256k1_modinv32_signed30 *x, const secp256k1_modinv32_modinfo *modinfo)
static void secp256k1_modinv32(secp256k1_modinv32_signed30 *x, const secp256k1_modinv32_modinfo *modinfo)
static void secp256k1_scalar_verify(const secp256k1_scalar *r)
Check invariants on a scalar (no-op unless VERIFY is enabled).
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)
static void secp256k1_scalar_half(secp256k1_scalar *r, const secp256k1_scalar *a)
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 32 bits of (c0,c1,c2) into n, and left shift the number 32 bits.
static void secp256k1_scalar_set_b32(secp256k1_scalar *r, const unsigned char *b32, int *overflow)
static void secp256k1_scalar_mul_512(uint32_t *l, const secp256k1_scalar *a, const secp256k1_scalar *b)
static void secp256k1_scalar_inverse_var(secp256k1_scalar *r, const secp256k1_scalar *x)
#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)
static SECP256K1_INLINE void secp256k1_scalar_set_int(secp256k1_scalar *r, unsigned int v)
static void secp256k1_scalar_inverse(secp256k1_scalar *r, const secp256k1_scalar *x)
static SECP256K1_INLINE void secp256k1_scalar_cmov(secp256k1_scalar *r, const secp256k1_scalar *a, int flag)
#define extract_fast(n)
Extract the lowest 32 bits of (c0,c1,c2) into n, and left shift the number 32 bits.
#define muladd(a, b)
Add a*b to the number defined by (c0,c1,c2).
static void secp256k1_scalar_reduce_512(secp256k1_scalar *r, const uint32_t *l)
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)
static const secp256k1_modinv32_modinfo secp256k1_const_modinfo_scalar
static SECP256K1_INLINE int secp256k1_scalar_reduce(secp256k1_scalar *r, uint32_t overflow)
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)
static void secp256k1_scalar_from_signed30(secp256k1_scalar *r, const secp256k1_modinv32_signed30 *a)
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 void secp256k1_scalar_to_signed30(secp256k1_modinv32_signed30 *r, const secp256k1_scalar *a)
static SECP256K1_INLINE uint32_t secp256k1_read_be32(const unsigned char *p)
static SECP256K1_INLINE void secp256k1_write_be32(unsigned char *p, uint32_t x)
#define VERIFY_CHECK(cond)
A scalar modulo the group order of the secp256k1 curve.