Differential D9410 Diff 28163 src/secp256k1/src/modinv64_impl.h

Changeset View

Standalone View

src/secp256k1/src/modinv64_impl.h

Show First 20 Lines • Show All 214 Lines • ▼ Show 20 Lines
* f0: bottom limb of initial f		* f0: bottom limb of initial f
* g0: bottom limb of initial g		* g0: bottom limb of initial g
* Output: t: transition matrix		* Output: t: transition matrix
* Return: final eta		* Return: final eta
*		*
* Implements the divsteps_n_matrix_var function from the explanation.		* Implements the divsteps_n_matrix_var function from the explanation.
*/		*/
static int64_t secp256k1_modinv64_divsteps_62_var(int64_t eta, uint64_t f0, uint64_t g0, secp256k1_modinv64_trans2x2 *t) {		static int64_t secp256k1_modinv64_divsteps_62_var(int64_t eta, uint64_t f0, uint64_t g0, secp256k1_modinv64_trans2x2 *t) {
/* inv256[i] = -(2i+1)^-1 (mod 256) /
static const uint8_t inv256[128] = {
0xFF, 0x55, 0x33, 0x49, 0xC7, 0x5D, 0x3B, 0x11, 0x0F, 0xE5, 0xC3, 0x59,
0xD7, 0xED, 0xCB, 0x21, 0x1F, 0x75, 0x53, 0x69, 0xE7, 0x7D, 0x5B, 0x31,
0x2F, 0x05, 0xE3, 0x79, 0xF7, 0x0D, 0xEB, 0x41, 0x3F, 0x95, 0x73, 0x89,
0x07, 0x9D, 0x7B, 0x51, 0x4F, 0x25, 0x03, 0x99, 0x17, 0x2D, 0x0B, 0x61,
0x5F, 0xB5, 0x93, 0xA9, 0x27, 0xBD, 0x9B, 0x71, 0x6F, 0x45, 0x23, 0xB9,
0x37, 0x4D, 0x2B, 0x81, 0x7F, 0xD5, 0xB3, 0xC9, 0x47, 0xDD, 0xBB, 0x91,
0x8F, 0x65, 0x43, 0xD9, 0x57, 0x6D, 0x4B, 0xA1, 0x9F, 0xF5, 0xD3, 0xE9,
0x67, 0xFD, 0xDB, 0xB1, 0xAF, 0x85, 0x63, 0xF9, 0x77, 0x8D, 0x6B, 0xC1,
0xBF, 0x15, 0xF3, 0x09, 0x87, 0x1D, 0xFB, 0xD1, 0xCF, 0xA5, 0x83, 0x19,
0x97, 0xAD, 0x8B, 0xE1, 0xDF, 0x35, 0x13, 0x29, 0xA7, 0x3D, 0x1B, 0xF1,
0xEF, 0xC5, 0xA3, 0x39, 0xB7, 0xCD, 0xAB, 0x01
};

/* Transformation matrix; see comments in secp256k1_modinv64_divsteps_62. */		/* Transformation matrix; see comments in secp256k1_modinv64_divsteps_62. */
uint64_t u = 1, v = 0, q = 0, r = 1;		uint64_t u = 1, v = 0, q = 0, r = 1;
uint64_t f = f0, g = g0, m;		uint64_t f = f0, g = g0, m;
uint32_t w;		uint32_t w;
int i = 62, limit, zeros;		int i = 62, limit, zeros;

for (;;) {		for (;;) {
/* Use a sentinel bit to count zeros only up to i. */		/* Use a sentinel bit to count zeros only up to i. */
Show All 14 Lines	for (;;) {
VERIFY_CHECK(eta >= -745 && eta <= 745);		VERIFY_CHECK(eta >= -745 && eta <= 745);
/* If eta is negative, negate it and replace f,g with g,-f. */		/* If eta is negative, negate it and replace f,g with g,-f. */
if (eta < 0) {		if (eta < 0) {
uint64_t tmp;		uint64_t tmp;
eta = -eta;		eta = -eta;
tmp = f; f = g; g = -tmp;		tmp = f; f = g; g = -tmp;
tmp = u; u = q; q = -tmp;		tmp = u; u = q; q = -tmp;
tmp = v; v = r; r = -tmp;		tmp = v; v = r; r = -tmp;
}		/* Use a formula to cancel out up to 6 bits of g. Also, no more than i can be cancelled
/* eta is now >= 0. In what follows we're going to cancel out the bottom bits of g. No more		* out (as we'd be done before that point), and no more than eta+1 can be done as its
* than i can be cancelled out (as we'd be done before that point), and no more than eta+1		* will flip again once that happens. */
* can be done as its sign will flip once that happens. */
limit = ((int)eta + 1) > i ? i : ((int)eta + 1);		limit = ((int)eta + 1) > i ? i : ((int)eta + 1);
/* m is a mask for the bottom min(limit, 8) bits (our table only supports 8 bits). */
VERIFY_CHECK(limit > 0 && limit <= 62);		VERIFY_CHECK(limit > 0 && limit <= 62);
m = (UINT64_MAX >> (64 - limit)) & 255U;		/* m is a mask for the bottom min(limit, 6) bits. */
/* Find what multiple of f must be added to g to cancel its bottom min(limit, 8) bits. */		m = (UINT64_MAX >> (64 - limit)) & 63U;
w = (g * inv256[(f >> 1) & 127]) & m;		/* Find what multiple of f must be added to g to cancel its bottom min(limit, 6)
/* Do so. */		* bits. */
		w = (f * g * (f * f - 2)) & m;
		} else {
		/* In this branch, use a simpler formula that only lets us cancel up to 4 bits of g, as
		* eta tends to be smaller here. */
		limit = ((int)eta + 1) > i ? i : ((int)eta + 1);
		VERIFY_CHECK(limit > 0 && limit <= 62);
		/* m is a mask for the bottom min(limit, 4) bits. */
		m = (UINT64_MAX >> (64 - limit)) & 15U;
		/* Find what multiple of f must be added to g to cancel its bottom min(limit, 4)
		* bits. */
		w = f + (((f + 1) & 4) << 1);
		w = (-w * g) & m;
		}
g += f * w;		g += f * w;
q += u * w;		q += u * w;
r += v * w;		r += v * w;
VERIFY_CHECK((g & m) == 0);		VERIFY_CHECK((g & m) == 0);
}		}
/* Return data in t and return value. */		/* Return data in t and return value. */
t->u = (int64_t)u;		t->u = (int64_t)u;
t->v = (int64_t)v;		t->v = (int64_t)v;
▲ Show 20 Lines • Show All 258 Lines • Show Last 20 Lines