7 #ifndef SECP256K1_SCALAR_REPR_IMPL_H
8 #define SECP256K1_SCALAR_REPR_IMPL_H
16 #define SECP256K1_N_0 ((uint64_t)0xBFD25E8CD0364141ULL)
17 #define SECP256K1_N_1 ((uint64_t)0xBAAEDCE6AF48A03BULL)
18 #define SECP256K1_N_2 ((uint64_t)0xFFFFFFFFFFFFFFFEULL)
19 #define SECP256K1_N_3 ((uint64_t)0xFFFFFFFFFFFFFFFFULL)
22 #define SECP256K1_N_C_0 (~SECP256K1_N_0 + 1)
23 #define SECP256K1_N_C_1 (~SECP256K1_N_1)
24 #define SECP256K1_N_C_2 (1)
27 #define SECP256K1_N_H_0 ((uint64_t)0xDFE92F46681B20A0ULL)
28 #define SECP256K1_N_H_1 ((uint64_t)0x5D576E7357A4501DULL)
29 #define SECP256K1_N_H_2 ((uint64_t)0xFFFFFFFFFFFFFFFFULL)
30 #define SECP256K1_N_H_3 ((uint64_t)0x7FFFFFFFFFFFFFFFULL)
52 return (a->
d[offset >> 6] >> (offset & 0x3F)) & ((((uint64_t)1) <<
count) - 1);
60 if ((offset +
count - 1) >> 6 == offset >> 6) {
64 return ((a->
d[offset >> 6] >> (offset & 0x3F)) | (a->
d[(offset >> 6) + 1] << (64 - (offset & 0x3F)))) & ((((uint64_t)1) <<
count) - 1);
128 volatile int vflag = flag;
132 bit += ((uint32_t) vflag - 1) & 0x100;
176 return (a->
d[0] | a->
d[1] | a->
d[2] | a->
d[3]) == 0;
215 uint64_t mask = -(uint64_t)(a->
d[0] & 1U);
244 return ((a->
d[0] ^ 1) | a->
d[1] | a->
d[2] | a->
d[3]) == 0;
264 volatile int vflag = flag;
265 uint64_t mask = -vflag;
284 return 2 * (mask == 0) - 1;
290 #define muladd(a,b) { \
293 secp256k1_uint128 t; \
294 secp256k1_u128_mul(&t, a, b); \
295 th = secp256k1_u128_hi_u64(&t); \
296 tl = secp256k1_u128_to_u64(&t); \
302 VERIFY_CHECK((c1 >= th) || (c2 != 0)); \
306 #define muladd_fast(a,b) { \
309 secp256k1_uint128 t; \
310 secp256k1_u128_mul(&t, a, b); \
311 th = secp256k1_u128_hi_u64(&t); \
312 tl = secp256k1_u128_to_u64(&t); \
317 VERIFY_CHECK(c1 >= th); \
321 #define sumadd(a) { \
330 #define sumadd_fast(a) { \
333 VERIFY_CHECK((c1 != 0) | (c0 >= (a))); \
334 VERIFY_CHECK(c2 == 0); \
338 #define extract(n) { \
346 #define extract_fast(n) { \
350 VERIFY_CHECK(c2 == 0); \
354 #ifdef USE_ASM_X86_64
356 uint64_t m0, m1, m2, m3, m4, m5, m6;
357 uint64_t p0, p1, p2, p3, p4;
360 __asm__ __volatile__(
362 "movq 32(%%rsi), %%r11\n"
363 "movq 40(%%rsi), %%r12\n"
364 "movq 48(%%rsi), %%r13\n"
365 "movq 56(%%rsi), %%r14\n"
367 "movq 0(%%rsi), %%r8\n"
369 "xorq %%r10, %%r10\n"
379 "addq 8(%%rsi), %%r9\n"
385 "adcq %%rdx, %%r10\n"
391 "adcq %%rdx, %%r10\n"
397 "addq 16(%%rsi), %%r10\n"
403 "addq %%rax, %%r10\n"
409 "addq %%rax, %%r10\n"
413 "addq %%r11, %%r10\n"
418 "xorq %%r10, %%r10\n"
420 "addq 24(%%rsi), %%r8\n"
446 "adcq %%rdx, %%r10\n"
455 "addq %%r14, %%r10\n"
461 :
"=&g"(m0),
"=&g"(m1),
"=&g"(m2),
"=g"(m3),
"=g"(m4),
"=g"(m5),
"=g"(m6)
463 :
"rax",
"rdx",
"r8",
"r9",
"r10",
"r11",
"r12",
"r13",
"r14",
"cc");
474 __asm__ __volatile__(
482 "xorq %%r10, %%r10\n"
498 "adcq %%rdx, %%r10\n"
504 "adcq %%rdx, %%r10\n"
516 "addq %%rax, %%r10\n"
522 "addq %%rax, %%r10\n"
526 "addq %%r11, %%r10\n"
548 :
"=&g"(p0),
"=&g"(p1),
"=&g"(p2),
"=g"(p3),
"=g"(p4)
550 :
"rax",
"rdx",
"r8",
"r9",
"r10",
"r11",
"r12",
"r13",
"cc");
559 __asm__ __volatile__(
569 "movq %%rax, 0(%q6)\n"
582 "movq %%r8, 8(%q6)\n"
591 "movq %%r9, 16(%q6)\n"
597 "movq %%r8, 24(%q6)\n"
602 :
"rax",
"rdx",
"r8",
"r9",
"r10",
"cc",
"memory");
609 uint64_t c, c0, c1, c2;
610 uint64_t n0 = l[4], n1 = l[5], n2 = l[6], n3 = l[7];
611 uint64_t m0, m1, m2, m3, m4, m5;
613 uint64_t p0, p1, p2, p3;
618 c0 = l[0]; c1 = 0; c2 = 0;
645 c0 = m0; c1 = 0; c2 = 0;
685 #ifdef USE_ASM_X86_64
686 const uint64_t *pb = b->
d;
687 __asm__ __volatile__(
689 "movq 0(%%rdi), %%r15\n"
690 "movq 8(%%rdi), %%rbx\n"
691 "movq 16(%%rdi), %%rcx\n"
692 "movq 0(%%rdx), %%r11\n"
693 "movq 8(%%rdx), %%r12\n"
694 "movq 16(%%rdx), %%r13\n"
695 "movq 24(%%rdx), %%r14\n"
697 "movq %%r15, %%rax\n"
700 "movq %%rax, 0(%%rsi)\n"
704 "xorq %%r10, %%r10\n"
706 "movq %%r15, %%rax\n"
712 "movq %%rbx, %%rax\n"
718 "movq %%r8, 8(%%rsi)\n"
721 "movq %%r15, %%rax\n"
724 "adcq %%rdx, %%r10\n"
727 "movq %%rbx, %%rax\n"
730 "adcq %%rdx, %%r10\n"
733 "movq %%rcx, %%rax\n"
736 "adcq %%rdx, %%r10\n"
739 "movq %%r9, 16(%%rsi)\n"
742 "movq %%r15, %%rax\n"
744 "addq %%rax, %%r10\n"
748 "movq 24(%%rdi), %%r15\n"
750 "movq %%rbx, %%rax\n"
752 "addq %%rax, %%r10\n"
756 "movq %%rcx, %%rax\n"
758 "addq %%rax, %%r10\n"
762 "movq %%r15, %%rax\n"
764 "addq %%rax, %%r10\n"
768 "movq %%r10, 24(%%rsi)\n"
769 "xorq %%r10, %%r10\n"
771 "movq %%rbx, %%rax\n"
777 "movq %%rcx, %%rax\n"
783 "movq %%r15, %%rax\n"
789 "movq %%r8, 32(%%rsi)\n"
792 "movq %%rcx, %%rax\n"
795 "adcq %%rdx, %%r10\n"
798 "movq %%r15, %%rax\n"
801 "adcq %%rdx, %%r10\n"
804 "movq %%r9, 40(%%rsi)\n"
806 "movq %%r15, %%rax\n"
808 "addq %%rax, %%r10\n"
811 "movq %%r10, 48(%%rsi)\n"
813 "movq %%r8, 56(%%rsi)\n"
816 :
"rax",
"rbx",
"rcx",
"r8",
"r9",
"r10",
"r11",
"r12",
"r13",
"r14",
"r15",
"cc",
"memory");
822 uint64_t c0 = 0, c1 = 0;
892 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;
897 unsigned int shiftlimbs;
898 unsigned int shiftlow;
899 unsigned int shifthigh;
905 shiftlimbs = shift >> 6;
906 shiftlow = shift & 0x3F;
907 shifthigh = 64 - shiftlow;
908 r->
d[0] = shift < 512 ? (l[0 + shiftlimbs] >> shiftlow | (shift < 448 && shiftlow ? (l[1 + shiftlimbs] << shifthigh) : 0)) : 0;
909 r->
d[1] = shift < 448 ? (l[1 + shiftlimbs] >> shiftlow | (shift < 384 && shiftlow ? (l[2 + shiftlimbs] << shifthigh) : 0)) : 0;
910 r->
d[2] = shift < 384 ? (l[2 + shiftlimbs] >> shiftlow | (shift < 320 && shiftlow ? (l[3 + shiftlimbs] << shifthigh) : 0)) : 0;
911 r->
d[3] = shift < 320 ? (l[3 + shiftlimbs] >> shiftlow) : 0;
918 uint64_t mask0, mask1;
919 volatile int vflag = flag;
923 mask0 = vflag + ~((uint64_t)0);
925 r->
d[0] = (r->
d[0] & mask0) | (a->
d[0] & mask1);
926 r->
d[1] = (r->
d[1] & mask0) | (a->
d[1] & mask1);
927 r->
d[2] = (r->
d[2] & mask0) | (a->
d[2] & mask1);
928 r->
d[3] = (r->
d[3] & mask0) | (a->
d[3] & mask1);
934 const uint64_t a0 = a->
v[0], a1 = a->
v[1], a2 = a->
v[2], a3 = a->
v[3], a4 = a->
v[4];
945 r->
d[0] = a0 | a1 << 62;
946 r->
d[1] = a1 >> 2 | a2 << 60;
947 r->
d[2] = a2 >> 4 | a3 << 58;
948 r->
d[3] = a3 >> 6 | a4 << 56;
954 const uint64_t M62 = UINT64_MAX >> 2;
955 const uint64_t a0 = a->
d[0], a1 = a->
d[1], a2 = a->
d[2], a3 = a->
d[3];
959 r->
v[1] = (a0 >> 62 | a1 << 2) & M62;
960 r->
v[2] = (a1 >> 60 | a2 << 4) & M62;
961 r->
v[3] = (a2 >> 58 | a3 << 6) & M62;
966 {{0x3FD25E8CD0364141LL, 0x2ABB739ABD2280EELL, -0x15LL, 0, 256}},
1003 return !(a->
d[0] & 1);
#define SECP256K1_CHECKMEM_MSAN_DEFINE(p, len)
#define SECP256K1_CHECKMEM_CHECK_VERIFY(p, len)
static SECP256K1_INLINE uint64_t secp256k1_u128_hi_u64(const secp256k1_uint128 *a)
static SECP256K1_INLINE void secp256k1_u128_from_u64(secp256k1_uint128 *r, uint64_t a)
static SECP256K1_INLINE void secp256k1_u128_rshift(secp256k1_uint128 *r, unsigned int n)
static SECP256K1_INLINE void secp256k1_u128_accum_u64(secp256k1_uint128 *r, uint64_t a)
static SECP256K1_INLINE void secp256k1_u128_accum_mul(secp256k1_uint128 *r, uint64_t a, uint64_t b)
static SECP256K1_INLINE uint64_t secp256k1_u128_to_u64(const secp256k1_uint128 *a)
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)
#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 64 bits of (c0,c1,c2) into n, and left shift the number 64 bits.
static void secp256k1_scalar_set_b32(secp256k1_scalar *r, const unsigned char *b32, int *overflow)
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)
static void secp256k1_scalar_reduce_512(secp256k1_scalar *r, const uint64_t *l)
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_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 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)
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 SECP256K1_INLINE int secp256k1_scalar_reduce(secp256k1_scalar *r, unsigned int 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_mul_512(uint64_t *l8, const secp256k1_scalar *a, const secp256k1_scalar *b)
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 SECP256K1_INLINE void secp256k1_write_be64(unsigned char *p, uint64_t x)
#define VERIFY_CHECK(cond)
static SECP256K1_INLINE uint64_t secp256k1_read_be64(const unsigned char *p)
A scalar modulo the group order of the secp256k1 curve.