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;
219 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;
227 r->
d[0] =
t & nonzero;
t >>= 32;
229 r->
d[1] =
t & nonzero;
t >>= 32;
231 r->
d[2] =
t & nonzero;
t >>= 32;
233 r->
d[3] =
t & nonzero;
t >>= 32;
235 r->
d[4] =
t & nonzero;
t >>= 32;
237 r->
d[5] =
t & nonzero;
t >>= 32;
239 r->
d[6] =
t & nonzero;
t >>= 32;
241 r->
d[7] =
t & nonzero;
261 uint32_t mask = -(uint32_t)(a->
d[0] & 1U);
262 uint64_t
t = (uint32_t)((a->
d[0] >> 1) | (a->
d[1] << 31));
266 r->
d[0] =
t;
t >>= 32;
267 t += (uint32_t)((a->
d[1] >> 1) | (a->
d[2] << 31));
269 r->
d[1] =
t;
t >>= 32;
270 t += (uint32_t)((a->
d[2] >> 1) | (a->
d[3] << 31));
272 r->
d[2] =
t;
t >>= 32;
273 t += (uint32_t)((a->
d[3] >> 1) | (a->
d[4] << 31));
275 r->
d[3] =
t;
t >>= 32;
276 t += (uint32_t)((a->
d[4] >> 1) | (a->
d[5] << 31));
278 r->
d[4] =
t;
t >>= 32;
279 t += (uint32_t)((a->
d[5] >> 1) | (a->
d[6] << 31));
281 r->
d[5] =
t;
t >>= 32;
282 t += (uint32_t)((a->
d[6] >> 1) | (a->
d[7] << 31));
284 r->
d[6] =
t;
t >>= 32;
297 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;
323 volatile int vflag = flag;
324 uint32_t mask = -vflag;
326 uint64_t
t = (uint64_t)(r->
d[0] ^ mask) + ((
SECP256K1_N_0 + 1) & mask);
329 r->
d[0] =
t & nonzero;
t >>= 32;
331 r->
d[1] =
t & nonzero;
t >>= 32;
333 r->
d[2] =
t & nonzero;
t >>= 32;
335 r->
d[3] =
t & nonzero;
t >>= 32;
337 r->
d[4] =
t & nonzero;
t >>= 32;
339 r->
d[5] =
t & nonzero;
t >>= 32;
341 r->
d[6] =
t & nonzero;
t >>= 32;
343 r->
d[7] =
t & nonzero;
346 return 2 * (mask == 0) - 1;
353 #define muladd(a,b) { \
356 uint64_t t = (uint64_t)a * b; \
364 VERIFY_CHECK((c1 >= th) || (c2 != 0)); \
368 #define muladd_fast(a,b) { \
371 uint64_t t = (uint64_t)a * b; \
378 VERIFY_CHECK(c1 >= th); \
382 #define sumadd(a) { \
391 #define sumadd_fast(a) { \
394 VERIFY_CHECK((c1 != 0) | (c0 >= (a))); \
395 VERIFY_CHECK(c2 == 0); \
399 #define extract(n) { \
407 #define extract_fast(n) { \
411 VERIFY_CHECK(c2 == 0); \
416 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];
417 uint32_t m0, m1, m2, m3, m4, m5, m6, m7, m8, m9, m10, m11, m12;
418 uint32_t p0, p1, p2, p3, p4, p5, p6, p7, p8;
425 c0 = l[0]; c1 = 0; c2 = 0;
490 c0 = m0; c1 = 0; c2 = 0;
536 r->
d[0] = c & 0xFFFFFFFFUL; c >>= 32;
538 r->
d[1] = c & 0xFFFFFFFFUL; c >>= 32;
540 r->
d[2] = c & 0xFFFFFFFFUL; c >>= 32;
542 r->
d[3] = c & 0xFFFFFFFFUL; c >>= 32;
543 c += p4 + (uint64_t)p8;
544 r->
d[4] = c & 0xFFFFFFFFUL; c >>= 32;
546 r->
d[5] = c & 0xFFFFFFFFUL; c >>= 32;
548 r->
d[6] = c & 0xFFFFFFFFUL; c >>= 32;
550 r->
d[7] = c & 0xFFFFFFFFUL; c >>= 32;
558 uint32_t c0 = 0, c1 = 0, c2 = 0;
690 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;
695 unsigned int shiftlimbs;
696 unsigned int shiftlow;
697 unsigned int shifthigh;
703 shiftlimbs = shift >> 5;
704 shiftlow = shift & 0x1F;
705 shifthigh = 32 - shiftlow;
706 r->
d[0] = shift < 512 ? (l[0 + shiftlimbs] >> shiftlow | (shift < 480 && shiftlow ? (l[1 + shiftlimbs] << shifthigh) : 0)) : 0;
707 r->
d[1] = shift < 480 ? (l[1 + shiftlimbs] >> shiftlow | (shift < 448 && shiftlow ? (l[2 + shiftlimbs] << shifthigh) : 0)) : 0;
708 r->
d[2] = shift < 448 ? (l[2 + shiftlimbs] >> shiftlow | (shift < 416 && shiftlow ? (l[3 + shiftlimbs] << shifthigh) : 0)) : 0;
709 r->
d[3] = shift < 416 ? (l[3 + shiftlimbs] >> shiftlow | (shift < 384 && shiftlow ? (l[4 + shiftlimbs] << shifthigh) : 0)) : 0;
710 r->
d[4] = shift < 384 ? (l[4 + shiftlimbs] >> shiftlow | (shift < 352 && shiftlow ? (l[5 + shiftlimbs] << shifthigh) : 0)) : 0;
711 r->
d[5] = shift < 352 ? (l[5 + shiftlimbs] >> shiftlow | (shift < 320 && shiftlow ? (l[6 + shiftlimbs] << shifthigh) : 0)) : 0;
712 r->
d[6] = shift < 320 ? (l[6 + shiftlimbs] >> shiftlow | (shift < 288 && shiftlow ? (l[7 + shiftlimbs] << shifthigh) : 0)) : 0;
713 r->
d[7] = shift < 288 ? (l[7 + shiftlimbs] >> shiftlow) : 0;
720 uint32_t mask0, mask1;
721 volatile int vflag = flag;
725 mask0 = vflag + ~((uint32_t)0);
727 r->
d[0] = (r->
d[0] & mask0) | (a->
d[0] & mask1);
728 r->
d[1] = (r->
d[1] & mask0) | (a->
d[1] & mask1);
729 r->
d[2] = (r->
d[2] & mask0) | (a->
d[2] & mask1);
730 r->
d[3] = (r->
d[3] & mask0) | (a->
d[3] & mask1);
731 r->
d[4] = (r->
d[4] & mask0) | (a->
d[4] & mask1);
732 r->
d[5] = (r->
d[5] & mask0) | (a->
d[5] & mask1);
733 r->
d[6] = (r->
d[6] & mask0) | (a->
d[6] & mask1);
734 r->
d[7] = (r->
d[7] & mask0) | (a->
d[7] & mask1);
740 const uint32_t a0 = a->
v[0], a1 = a->
v[1], a2 = a->
v[2], a3 = a->
v[3], a4 = a->
v[4],
741 a5 = a->
v[5], a6 = a->
v[6], a7 = a->
v[7], a8 = a->
v[8];
756 r->
d[0] = a0 | a1 << 30;
757 r->
d[1] = a1 >> 2 | a2 << 28;
758 r->
d[2] = a2 >> 4 | a3 << 26;
759 r->
d[3] = a3 >> 6 | a4 << 24;
760 r->
d[4] = a4 >> 8 | a5 << 22;
761 r->
d[5] = a5 >> 10 | a6 << 20;
762 r->
d[6] = a6 >> 12 | a7 << 18;
763 r->
d[7] = a7 >> 14 | a8 << 16;
769 const uint32_t M30 = UINT32_MAX >> 2;
770 const uint32_t a0 = a->
d[0], a1 = a->
d[1], a2 = a->
d[2], a3 = a->
d[3],
771 a4 = a->
d[4], a5 = a->
d[5], a6 = a->
d[6], a7 = a->
d[7];
775 r->
v[1] = (a0 >> 30 | a1 << 2) & M30;
776 r->
v[2] = (a1 >> 28 | a2 << 4) & M30;
777 r->
v[3] = (a2 >> 26 | a3 << 6) & M30;
778 r->
v[4] = (a3 >> 24 | a4 << 8) & M30;
779 r->
v[5] = (a4 >> 22 | a5 << 10) & M30;
780 r->
v[6] = (a5 >> 20 | a6 << 12) & M30;
781 r->
v[7] = (a6 >> 18 | a7 << 14) & M30;
786 {{0x10364141L, 0x3F497A33L, 0x348A03BBL, 0x2BB739ABL, -0x146L, 0, 0, 0, 65536}},
823 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)
#define SECP256K1_SCALAR_VERIFY(r)
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.