Differential D4879 Diff 15323 src/secp256k1/src/ecmult_impl.h

Changeset View

Standalone View

src/secp256k1/src/ecmult_impl.h

Show First 20 Lines • Show All 557 Lines • ▼ Show 20 Lines	static size_t secp256k1_strauss_max_points(secp256k1_scratch *scratch) {
return secp256k1_scratch_max_allocation(scratch, STRAUSS_SCRATCH_OBJECTS) / secp256k1_strauss_scratch_size(1);		return secp256k1_scratch_max_allocation(scratch, STRAUSS_SCRATCH_OBJECTS) / secp256k1_strauss_scratch_size(1);
}		}

/** Convert a number to WNAF notation.		/** Convert a number to WNAF notation.
* The number becomes represented by sum(2^{wi} * wnaf[i], i=0..WNAF_SIZE(w)+1) - return_val.		* The number becomes represented by sum(2^{wi} * wnaf[i], i=0..WNAF_SIZE(w)+1) - return_val.
* It has the following guarantees:		* It has the following guarantees:
* - each wnaf[i] is either 0 or an odd integer between -(1 << w) and (1 << w)		* - each wnaf[i] is either 0 or an odd integer between -(1 << w) and (1 << w)
* - the number of words set is always WNAF_SIZE(w)		* - the number of words set is always WNAF_SIZE(w)
* - the returned skew is 0 without endomorphism, or 0 or 1 with endomorphism		* - the returned skew is 0 or 1
*/		*/
static int secp256k1_wnaf_fixed(int wnaf, const secp256k1_scalar s, int w) {		static int secp256k1_wnaf_fixed(int wnaf, const secp256k1_scalar s, int w) {
int sign = 0;
int skew = 0;		int skew = 0;
int pos = 1;		int pos;
#ifndef USE_ENDOMORPHISM		int max_pos;
secp256k1_scalar neg_s;		int last_w;
#endif
const secp256k1_scalar *work = s;		const secp256k1_scalar *work = s;

if (secp256k1_scalar_is_zero(s)) {		if (secp256k1_scalar_is_zero(s)) {
while (pos * w < WNAF_BITS) {		for (pos = 0; pos < WNAF_SIZE(w); pos++) {
wnaf[pos] = 0;		wnaf[pos] = 0;
++pos;
}		}
return 0;		return 0;
}		}

if (secp256k1_scalar_is_even(s)) {		if (secp256k1_scalar_is_even(s)) {
#ifdef USE_ENDOMORPHISM
skew = 1;		skew = 1;
#else
secp256k1_scalar_negate(&neg_s, s);
work = &neg_s;
sign = -1;
#endif
}		}

wnaf[0] = (secp256k1_scalar_get_bits_var(work, 0, w) + skew + sign) ^ sign;		wnaf[0] = secp256k1_scalar_get_bits_var(work, 0, w) + skew;
		/* Compute last window size. Relevant when window size doesn't divide the
while (pos * w < WNAF_BITS) {		* number of bits in the scalar */
int now = w;		last_w = WNAF_BITS - (WNAF_SIZE(w) - 1) * w;
int val;
if (now + pos * w > WNAF_BITS) {		/* Store the position of the first nonzero word in max_pos to allow
now = WNAF_BITS - pos * w;		* skipping leading zeros when calculating the wnaf. */
		for (pos = WNAF_SIZE(w) - 1; pos > 0; pos--) {
		int val = secp256k1_scalar_get_bits_var(work, pos * w, pos == WNAF_SIZE(w)-1 ? last_w : w);
		if(val != 0) {
		break;
}		}
val = secp256k1_scalar_get_bits_var(work, pos * w, now);		wnaf[pos] = 0;
		}
		max_pos = pos;
		pos = 1;

		while (pos <= max_pos) {
		int val = secp256k1_scalar_get_bits_var(work, pos * w, pos == WNAF_SIZE(w)-1 ? last_w : w);
if ((val & 1) == 0) {		if ((val & 1) == 0) {
wnaf[pos - 1] -= ((1 << w) + sign) ^ sign;		wnaf[pos - 1] -= (1 << w);
wnaf[pos] = (val + 1 + sign) ^ sign;		wnaf[pos] = (val + 1);
		} else {
		wnaf[pos] = val;
		}
		/* Set a coefficient to zero if it is 1 or -1 and the proceeding digit
		* is strictly negative or strictly positive respectively. Only change
		* coefficients at previous positions because above code assumes that
		* wnaf[pos - 1] is odd.
		*/
		if (pos >= 2 && ((wnaf[pos - 1] == 1 && wnaf[pos - 2] < 0) \|\| (wnaf[pos - 1] == -1 && wnaf[pos - 2] > 0))) {
		if (wnaf[pos - 1] == 1) {
		wnaf[pos - 2] += 1 << w;
} else {		} else {
wnaf[pos] = (val + sign) ^ sign;		wnaf[pos - 2] -= 1 << w;
		}
		wnaf[pos - 1] = 0;
}		}
++pos;		++pos;
}		}
VERIFY_CHECK(pos == WNAF_SIZE(w));

return skew;		return skew;
}		}

struct secp256k1_pippenger_point_state {		struct secp256k1_pippenger_point_state {
int skew_na;		int skew_na;
size_t input_pos;		size_t input_pos;
};		};
Show All 39 Lines	for (i = n_wnaf - 1; i >= 0; i--) {
}		}

for (np = 0; np < no; ++np) {		for (np = 0; np < no; ++np) {
int n = state->wnaf_na[np*n_wnaf + i];		int n = state->wnaf_na[np*n_wnaf + i];
struct secp256k1_pippenger_point_state point_state = state->ps[np];		struct secp256k1_pippenger_point_state point_state = state->ps[np];
secp256k1_ge tmp;		secp256k1_ge tmp;
int idx;		int idx;

#ifdef USE_ENDOMORPHISM
if (i == 0) {		if (i == 0) {
/* correct for wnaf skew */		/* correct for wnaf skew */
int skew = point_state.skew_na;		int skew = point_state.skew_na;
if (skew) {		if (skew) {
secp256k1_ge_neg(&tmp, &pt[point_state.input_pos]);		secp256k1_ge_neg(&tmp, &pt[point_state.input_pos]);
secp256k1_gej_add_ge_var(&buckets[0], &buckets[0], &tmp, NULL);		secp256k1_gej_add_ge_var(&buckets[0], &buckets[0], &tmp, NULL);
}		}
}		}
#endif
if (n > 0) {		if (n > 0) {
idx = (n - 1)/2;		idx = (n - 1)/2;
secp256k1_gej_add_ge_var(&buckets[idx], &buckets[idx], &pt[point_state.input_pos], NULL);		secp256k1_gej_add_ge_var(&buckets[idx], &buckets[idx], &pt[point_state.input_pos], NULL);
} else if (n < 0) {		} else if (n < 0) {
idx = -(n + 1)/2;		idx = -(n + 1)/2;
secp256k1_ge_neg(&tmp, &pt[point_state.input_pos]);		secp256k1_ge_neg(&tmp, &pt[point_state.input_pos]);
secp256k1_gej_add_ge_var(&buckets[idx], &buckets[idx], &tmp, NULL);		secp256k1_gej_add_ge_var(&buckets[idx], &buckets[idx], &tmp, NULL);
}		}
▲ Show 20 Lines • Show All 326 Lines • Show Last 20 Lines