Changeset View
Changeset View
Standalone View
Standalone View
src/secp256k1/src/ecmult_impl.h
| Show First 20 Lines • Show All 1,105 Lines • ▼ Show 20 Lines | for (point_idx = 0; point_idx < n_points; point_idx++) { | ||||
| /* r += scalar*point */ | /* r += scalar*point */ | ||||
| secp256k1_gej_set_ge(&pointj, &point); | secp256k1_gej_set_ge(&pointj, &point); | ||||
| secp256k1_ecmult(ctx, &tmpj, &pointj, &scalar, NULL); | secp256k1_ecmult(ctx, &tmpj, &pointj, &scalar, NULL); | ||||
| secp256k1_gej_add_var(r, r, &tmpj, NULL); | secp256k1_gej_add_var(r, r, &tmpj, NULL); | ||||
| } | } | ||||
| return 1; | return 1; | ||||
| } | } | ||||
| /* Compute the number of batches and the batch size given the maximum batch size and the | |||||
| * total number of points */ | |||||
| static int secp256k1_ecmult_multi_batch_size_helper(size_t *n_batches, size_t *n_batch_points, size_t max_n_batch_points, size_t n) { | |||||
| if (max_n_batch_points == 0) { | |||||
| return 0; | |||||
| } | |||||
| if (max_n_batch_points > ECMULT_MAX_POINTS_PER_BATCH) { | |||||
| max_n_batch_points = ECMULT_MAX_POINTS_PER_BATCH; | |||||
| } | |||||
| if (n == 0) { | |||||
| *n_batches = 0; | |||||
| *n_batch_points = 0; | |||||
| return 1; | |||||
| } | |||||
| /* Compute ceil(n/max_n_batch_points) and ceil(n/n_batches) */ | |||||
| *n_batches = 1 + (n - 1) / max_n_batch_points; | |||||
| *n_batch_points = 1 + (n - 1) / *n_batches; | |||||
| return 1; | |||||
| } | |||||
| typedef int (*secp256k1_ecmult_multi_func)(const secp256k1_ecmult_context*, secp256k1_scratch*, secp256k1_gej*, const secp256k1_scalar*, secp256k1_ecmult_multi_callback cb, void*, size_t); | typedef int (*secp256k1_ecmult_multi_func)(const secp256k1_ecmult_context*, secp256k1_scratch*, secp256k1_gej*, const secp256k1_scalar*, secp256k1_ecmult_multi_callback cb, void*, size_t); | ||||
| static int secp256k1_ecmult_multi_var(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) { | static int secp256k1_ecmult_multi_var(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) { | ||||
| size_t i; | size_t i; | ||||
| int (*f)(const secp256k1_ecmult_context*, secp256k1_scratch*, secp256k1_gej*, const secp256k1_scalar*, secp256k1_ecmult_multi_callback cb, void*, size_t, size_t); | int (*f)(const secp256k1_ecmult_context*, secp256k1_scratch*, secp256k1_gej*, const secp256k1_scalar*, secp256k1_ecmult_multi_callback cb, void*, size_t, size_t); | ||||
| size_t max_points; | |||||
| size_t n_batches; | size_t n_batches; | ||||
| size_t n_batch_points; | size_t n_batch_points; | ||||
| secp256k1_gej_set_infinity(r); | secp256k1_gej_set_infinity(r); | ||||
| if (inp_g_sc == NULL && n == 0) { | if (inp_g_sc == NULL && n == 0) { | ||||
| return 1; | return 1; | ||||
| } else if (n == 0) { | } else if (n == 0) { | ||||
| secp256k1_scalar szero; | secp256k1_scalar szero; | ||||
| secp256k1_scalar_set_int(&szero, 0); | secp256k1_scalar_set_int(&szero, 0); | ||||
| secp256k1_ecmult(ctx, r, r, &szero, inp_g_sc); | secp256k1_ecmult(ctx, r, r, &szero, inp_g_sc); | ||||
| return 1; | return 1; | ||||
| } | } | ||||
| if (scratch == NULL) { | if (scratch == NULL) { | ||||
| return secp256k1_ecmult_multi_simple_var(ctx, r, inp_g_sc, cb, cbdata, n); | return secp256k1_ecmult_multi_simple_var(ctx, r, inp_g_sc, cb, cbdata, n); | ||||
| } | } | ||||
| max_points = secp256k1_pippenger_max_points(scratch); | /* Compute the batch sizes for pippenger given a scratch space. If it's greater than a threshold | ||||
| if (max_points == 0) { | * use pippenger. Otherwise use strauss */ | ||||
| if (!secp256k1_ecmult_multi_batch_size_helper(&n_batches, &n_batch_points, secp256k1_pippenger_max_points(scratch), n)) { | |||||
| return 0; | return 0; | ||||
| } else if (max_points > ECMULT_MAX_POINTS_PER_BATCH) { | |||||
| max_points = ECMULT_MAX_POINTS_PER_BATCH; | |||||
| } | } | ||||
| n_batches = (n+max_points-1)/max_points; | |||||
| n_batch_points = (n+n_batches-1)/n_batches; | |||||
| if (n_batch_points >= ECMULT_PIPPENGER_THRESHOLD) { | if (n_batch_points >= ECMULT_PIPPENGER_THRESHOLD) { | ||||
| f = secp256k1_ecmult_pippenger_batch; | f = secp256k1_ecmult_pippenger_batch; | ||||
| } else { | } else { | ||||
| max_points = secp256k1_strauss_max_points(scratch); | if (!secp256k1_ecmult_multi_batch_size_helper(&n_batches, &n_batch_points, secp256k1_strauss_max_points(scratch), n)) { | ||||
| if (max_points == 0) { | |||||
| return 0; | return 0; | ||||
| } | } | ||||
| n_batches = (n+max_points-1)/max_points; | |||||
| n_batch_points = (n+n_batches-1)/n_batches; | |||||
| f = secp256k1_ecmult_strauss_batch; | f = secp256k1_ecmult_strauss_batch; | ||||
| } | } | ||||
| for(i = 0; i < n_batches; i++) { | for(i = 0; i < n_batches; i++) { | ||||
| size_t nbp = n < n_batch_points ? n : n_batch_points; | size_t nbp = n < n_batch_points ? n : n_batch_points; | ||||
| size_t offset = n_batch_points*i; | size_t offset = n_batch_points*i; | ||||
| secp256k1_gej tmp; | secp256k1_gej tmp; | ||||
| if (!f(ctx, scratch, &tmp, i == 0 ? inp_g_sc : NULL, cb, cbdata, nbp, offset)) { | if (!f(ctx, scratch, &tmp, i == 0 ? inp_g_sc : NULL, cb, cbdata, nbp, offset)) { | ||||
| return 0; | return 0; | ||||
| } | } | ||||
| secp256k1_gej_add_var(r, r, &tmp, NULL); | secp256k1_gej_add_var(r, r, &tmp, NULL); | ||||
| n -= nbp; | n -= nbp; | ||||
| } | } | ||||
| return 1; | return 1; | ||||
| } | } | ||||
| #endif /* SECP256K1_ECMULT_IMPL_H */ | #endif /* SECP256K1_ECMULT_IMPL_H */ | ||||