Page MenuHomePhabricator
Differential D4991 Diff 15589 src/secp256k1/src/ecmult_impl.h

Changeset View

Standalone View

View Options

src/secp256k1/src/ecmult_impl.h

Show First 20 Lines • Show All 954 Lines • ▼ Show 20 Lines
*/ */
static size_t secp256k1_pippenger_scratch_size(size_t n_points, int bucket_window) { static size_t secp256k1_pippenger_scratch_size(size_t n_points, int bucket_window) {
#ifdef USE_ENDOMORPHISM #ifdef USE_ENDOMORPHISM
size_t entries = 2*n_points + 2; size_t entries = 2*n_points + 2;
#else #else
size_t entries = n_points + 1; size_t entries = n_points + 1;
#endif #endif
size_t entry_size = sizeof(secp256k1_ge) + sizeof(secp256k1_scalar) + sizeof(struct secp256k1_pippenger_point_state) + (WNAF_SIZE(bucket_window+1)+1)*sizeof(int); size_t entry_size = sizeof(secp256k1_ge) + sizeof(secp256k1_scalar) + sizeof(struct secp256k1_pippenger_point_state) + (WNAF_SIZE(bucket_window+1)+1)*sizeof(int);
return ((1<<bucket_window) * sizeof(secp256k1_gej) + sizeof(struct secp256k1_pippenger_state) + entries * entry_size); return (sizeof(secp256k1_gej) << bucket_window) + sizeof(struct secp256k1_pippenger_state) + entries * entry_size;
} }
static int secp256k1_ecmult_pippenger_batch(const secp256k1_ecmult_context *ctx, secp256k1_scratch *scratch, secp256k1_gej *r, const secp256k1_scalar *inp_g_sc, secp256k1_ecmult_multi_callback cb, void *cbdata, size_t n_points, size_t cb_offset) { static int secp256k1_ecmult_pippenger_batch(const secp256k1_ecmult_context *ctx, secp256k1_scratch *scratch, secp256k1_gej *r, const secp256k1_scalar *inp_g_sc, secp256k1_ecmult_multi_callback cb, void *cbdata, size_t n_points, size_t cb_offset) {
/* Use 2(n+1) with the endomorphism, n+1 without, when calculating batch /* Use 2(n+1) with the endomorphism, n+1 without, when calculating batch
* sizes. The reason for +1 is that we add the G scalar to the list of * sizes. The reason for +1 is that we add the G scalar to the list of
* other scalars. */ * other scalars. */
#ifdef USE_ENDOMORPHISM #ifdef USE_ENDOMORPHISM
size_t entries = 2*n_points + 2; size_t entries = 2*n_points + 2;
Show All 19 Lines#endif
if (!secp256k1_scratch_allocate_frame(scratch, secp256k1_pippenger_scratch_size(n_points, bucket_window), PIPPENGER_SCRATCH_OBJECTS)) { if (!secp256k1_scratch_allocate_frame(scratch, secp256k1_pippenger_scratch_size(n_points, bucket_window), PIPPENGER_SCRATCH_OBJECTS)) {
return 0; return 0;
} }
points = (secp256k1_ge *) secp256k1_scratch_alloc(scratch, entries * sizeof(*points)); points = (secp256k1_ge *) secp256k1_scratch_alloc(scratch, entries * sizeof(*points));
scalars = (secp256k1_scalar *) secp256k1_scratch_alloc(scratch, entries * sizeof(*scalars)); scalars = (secp256k1_scalar *) secp256k1_scratch_alloc(scratch, entries * sizeof(*scalars));
state_space = (struct secp256k1_pippenger_state *) secp256k1_scratch_alloc(scratch, sizeof(*state_space)); state_space = (struct secp256k1_pippenger_state *) secp256k1_scratch_alloc(scratch, sizeof(*state_space));
state_space->ps = (struct secp256k1_pippenger_point_state *) secp256k1_scratch_alloc(scratch, entries * sizeof(*state_space->ps)); state_space->ps = (struct secp256k1_pippenger_point_state *) secp256k1_scratch_alloc(scratch, entries * sizeof(*state_space->ps));
state_space->wnaf_na = (int *) secp256k1_scratch_alloc(scratch, entries*(WNAF_SIZE(bucket_window+1)) * sizeof(int)); state_space->wnaf_na = (int *) secp256k1_scratch_alloc(scratch, entries*(WNAF_SIZE(bucket_window+1)) * sizeof(int));
buckets = (secp256k1_gej *) secp256k1_scratch_alloc(scratch, (1<<bucket_window) * sizeof(*buckets)); buckets = (secp256k1_gej *) secp256k1_scratch_alloc(scratch, sizeof(*buckets) << bucket_window);
if (inp_g_sc != NULL) { if (inp_g_sc != NULL) {
scalars[0] = *inp_g_sc; scalars[0] = *inp_g_sc;
points[0] = secp256k1_ge_const_g; points[0] = secp256k1_ge_const_g;
idx++; idx++;
#ifdef USE_ENDOMORPHISM #ifdef USE_ENDOMORPHISM
secp256k1_ecmult_endo_split(&scalars[0], &scalars[1], &points[0], &points[1]); secp256k1_ecmult_endo_split(&scalars[0], &scalars[1], &points[0], &points[1]);
idx++; idx++;
▲ Show 20 Lines • Show All 50 Lines • ▼ Show 20 Lines for (bucket_window = 1; bucket_window <= PIPPENGER_MAX_BUCKET_WINDOW; bucket_window++) {
size_t max_points = secp256k1_pippenger_bucket_window_inv(bucket_window); size_t max_points = secp256k1_pippenger_bucket_window_inv(bucket_window);
size_t space_for_points; size_t space_for_points;
size_t space_overhead; size_t space_overhead;
size_t entry_size = sizeof(secp256k1_ge) + sizeof(secp256k1_scalar) + sizeof(struct secp256k1_pippenger_point_state) + (WNAF_SIZE(bucket_window+1)+1)*sizeof(int); size_t entry_size = sizeof(secp256k1_ge) + sizeof(secp256k1_scalar) + sizeof(struct secp256k1_pippenger_point_state) + (WNAF_SIZE(bucket_window+1)+1)*sizeof(int);
#ifdef USE_ENDOMORPHISM #ifdef USE_ENDOMORPHISM
entry_size = 2*entry_size; entry_size = 2*entry_size;
#endif #endif
space_overhead = ((1<<bucket_window) * sizeof(secp256k1_gej) + entry_size + sizeof(struct secp256k1_pippenger_state)); space_overhead = (sizeof(secp256k1_gej) << bucket_window) + entry_size + sizeof(struct secp256k1_pippenger_state);
if (space_overhead > max_alloc) { if (space_overhead > max_alloc) {
break; break;
} }
space_for_points = max_alloc - space_overhead; space_for_points = max_alloc - space_overhead;
n_points = space_for_points/entry_size; n_points = space_for_points/entry_size;
n_points = n_points > max_points ? max_points : n_points; n_points = n_points > max_points ? max_points : n_points;
if (n_points > res) { if (n_points > res) {
▲ Show 20 Lines • Show All 107 Lines • Show Last 20 Lines