Page MenuHomePhabricator
Differential D7597 Diff 23858 src/secp256k1/src/scalar_4x64_impl.h

Changeset View

Standalone View

View Options

src/secp256k1/src/scalar_4x64_impl.h

Show First 20 Lines • Show All 186 Lines • ▼ Show 20 Lines
#define muladd(a,b) { \ #define muladd(a,b) { \
uint64_t tl, th; \ uint64_t tl, th; \
{ \ { \
uint128_t t = (uint128_t)a * b; \ uint128_t t = (uint128_t)a * b; \
th = t >> 64; /* at most 0xFFFFFFFFFFFFFFFE */ \ th = t >> 64; /* at most 0xFFFFFFFFFFFFFFFE */ \
tl = t; \ tl = t; \
} \ } \
c0 += tl; /* overflow is handled on the next line */ \ c0 += tl; /* overflow is handled on the next line */ \
th += (c0 < tl) ? 1 : 0; /* at most 0xFFFFFFFFFFFFFFFF */ \ th += (c0 < tl); /* at most 0xFFFFFFFFFFFFFFFF */ \
c1 += th; /* overflow is handled on the next line */ \ c1 += th; /* overflow is handled on the next line */ \
c2 += (c1 < th) ? 1 : 0; /* never overflows by contract (verified in the next line) */ \ c2 += (c1 < th); /* never overflows by contract (verified in the next line) */ \
VERIFY_CHECK((c1 >= th) || (c2 != 0)); \ VERIFY_CHECK((c1 >= th) || (c2 != 0)); \
} }
/** Add a*b to the number defined by (c0,c1). c1 must never overflow. */ /** Add a*b to the number defined by (c0,c1). c1 must never overflow. */
#define muladd_fast(a,b) { \ #define muladd_fast(a,b) { \
uint64_t tl, th; \ uint64_t tl, th; \
{ \ { \
uint128_t t = (uint128_t)a * b; \ uint128_t t = (uint128_t)a * b; \
th = t >> 64; /* at most 0xFFFFFFFFFFFFFFFE */ \ th = t >> 64; /* at most 0xFFFFFFFFFFFFFFFE */ \
tl = t; \ tl = t; \
} \ } \
c0 += tl; /* overflow is handled on the next line */ \ c0 += tl; /* overflow is handled on the next line */ \
th += (c0 < tl) ? 1 : 0; /* at most 0xFFFFFFFFFFFFFFFF */ \ th += (c0 < tl); /* at most 0xFFFFFFFFFFFFFFFF */ \
c1 += th; /* never overflows by contract (verified in the next line) */ \ c1 += th; /* never overflows by contract (verified in the next line) */ \
VERIFY_CHECK(c1 >= th); \ VERIFY_CHECK(c1 >= th); \
} }
/** Add 2*a*b to the number defined by (c0,c1,c2). c2 must never overflow. */ /** Add 2*a*b to the number defined by (c0,c1,c2). c2 must never overflow. */
#define muladd2(a,b) { \ #define muladd2(a,b) { \
uint64_t tl, th, th2, tl2; \ uint64_t tl, th, th2, tl2; \
{ \ { \
uint128_t t = (uint128_t)a * b; \ uint128_t t = (uint128_t)a * b; \
th = t >> 64; /* at most 0xFFFFFFFFFFFFFFFE */ \ th = t >> 64; /* at most 0xFFFFFFFFFFFFFFFE */ \
tl = t; \ tl = t; \
} \ } \
th2 = th + th; /* at most 0xFFFFFFFFFFFFFFFE (in case th was 0x7FFFFFFFFFFFFFFF) */ \ th2 = th + th; /* at most 0xFFFFFFFFFFFFFFFE (in case th was 0x7FFFFFFFFFFFFFFF) */ \
c2 += (th2 < th) ? 1 : 0; /* never overflows by contract (verified the next line) */ \ c2 += (th2 < th); /* never overflows by contract (verified the next line) */ \
VERIFY_CHECK((th2 >= th) || (c2 != 0)); \ VERIFY_CHECK((th2 >= th) || (c2 != 0)); \
tl2 = tl + tl; /* at most 0xFFFFFFFFFFFFFFFE (in case the lowest 63 bits of tl were 0x7FFFFFFFFFFFFFFF) */ \ tl2 = tl + tl; /* at most 0xFFFFFFFFFFFFFFFE (in case the lowest 63 bits of tl were 0x7FFFFFFFFFFFFFFF) */ \
th2 += (tl2 < tl) ? 1 : 0; /* at most 0xFFFFFFFFFFFFFFFF */ \ th2 += (tl2 < tl); /* at most 0xFFFFFFFFFFFFFFFF */ \
c0 += tl2; /* overflow is handled on the next line */ \ c0 += tl2; /* overflow is handled on the next line */ \
th2 += (c0 < tl2) ? 1 : 0; /* second overflow is handled on the next line */ \ th2 += (c0 < tl2); /* second overflow is handled on the next line */ \
c2 += (c0 < tl2) & (th2 == 0); /* never overflows by contract (verified the next line) */ \ c2 += (c0 < tl2) & (th2 == 0); /* never overflows by contract (verified the next line) */ \
VERIFY_CHECK((c0 >= tl2) || (th2 != 0) || (c2 != 0)); \ VERIFY_CHECK((c0 >= tl2) || (th2 != 0) || (c2 != 0)); \
c1 += th2; /* overflow is handled on the next line */ \ c1 += th2; /* overflow is handled on the next line */ \
c2 += (c1 < th2) ? 1 : 0; /* never overflows by contract (verified the next line) */ \ c2 += (c1 < th2); /* never overflows by contract (verified the next line) */ \
VERIFY_CHECK((c1 >= th2) || (c2 != 0)); \ VERIFY_CHECK((c1 >= th2) || (c2 != 0)); \
} }
/** Add a to the number defined by (c0,c1,c2). c2 must never overflow. */ /** Add a to the number defined by (c0,c1,c2). c2 must never overflow. */
#define sumadd(a) { \ #define sumadd(a) { \
unsigned int over; \ unsigned int over; \
c0 += (a); /* overflow is handled on the next line */ \ c0 += (a); /* overflow is handled on the next line */ \
over = (c0 < (a)) ? 1 : 0; \ over = (c0 < (a)); \
c1 += over; /* overflow is handled on the next line */ \ c1 += over; /* overflow is handled on the next line */ \
c2 += (c1 < over) ? 1 : 0; /* never overflows by contract */ \ c2 += (c1 < over); /* never overflows by contract */ \
} }
/** Add a to the number defined by (c0,c1). c1 must never overflow, c2 must be zero. */ /** Add a to the number defined by (c0,c1). c1 must never overflow, c2 must be zero. */
#define sumadd_fast(a) { \ #define sumadd_fast(a) { \
c0 += (a); /* overflow is handled on the next line */ \ c0 += (a); /* overflow is handled on the next line */ \
c1 += (c0 < (a)) ? 1 : 0; /* never overflows by contract (verified the next line) */ \ c1 += (c0 < (a)); /* never overflows by contract (verified the next line) */ \
VERIFY_CHECK((c1 != 0) | (c0 >= (a))); \ VERIFY_CHECK((c1 != 0) | (c0 >= (a))); \
VERIFY_CHECK(c2 == 0); \ VERIFY_CHECK(c2 == 0); \
} }
/** Extract the lowest 64 bits of (c0,c1,c2) into n, and left shift the number 64 bits. */ /** Extract the lowest 64 bits of (c0,c1,c2) into n, and left shift the number 64 bits. */
#define extract(n) { \ #define extract(n) { \
(n) = c0; \ (n) = c0; \
c0 = c1; \ c0 = c1; \
▲ Show 20 Lines • Show All 703 Lines • Show Last 20 Lines