Changeset View
Changeset View
Standalone View
Standalone View
src/secp256k1/src/bench_ecmult.c
Show All 12 Lines | |||||
#include "field_impl.h" | #include "field_impl.h" | ||||
#include "group_impl.h" | #include "group_impl.h" | ||||
#include "scalar_impl.h" | #include "scalar_impl.h" | ||||
#include "ecmult_impl.h" | #include "ecmult_impl.h" | ||||
#include "bench.h" | #include "bench.h" | ||||
#include "secp256k1.c" | #include "secp256k1.c" | ||||
#define POINTS 32768 | #define POINTS 32768 | ||||
#define ITERS 10000 | |||||
typedef struct { | typedef struct { | ||||
/* Setup once in advance */ | /* Setup once in advance */ | ||||
secp256k1_context* ctx; | secp256k1_context* ctx; | ||||
secp256k1_scratch_space* scratch; | secp256k1_scratch_space* scratch; | ||||
secp256k1_scalar* scalars; | secp256k1_scalar* scalars; | ||||
secp256k1_ge* pubkeys; | secp256k1_ge* pubkeys; | ||||
secp256k1_scalar* seckeys; | secp256k1_scalar* seckeys; | ||||
Show All 20 Lines | if (idx == 0) { | ||||
*ge = secp256k1_ge_const_g; | *ge = secp256k1_ge_const_g; | ||||
} else { | } else { | ||||
*sc = data->scalars[(data->offset1 + idx) % POINTS]; | *sc = data->scalars[(data->offset1 + idx) % POINTS]; | ||||
*ge = data->pubkeys[(data->offset2 + idx - 1) % POINTS]; | *ge = data->pubkeys[(data->offset2 + idx - 1) % POINTS]; | ||||
} | } | ||||
return 1; | return 1; | ||||
} | } | ||||
static void bench_ecmult(void* arg) { | static void bench_ecmult(void* arg, int iters) { | ||||
bench_data* data = (bench_data*)arg; | bench_data* data = (bench_data*)arg; | ||||
size_t count = data->count; | |||||
int includes_g = data->includes_g; | int includes_g = data->includes_g; | ||||
size_t iters = 1 + ITERS / count; | int iter; | ||||
size_t iter; | int count = data->count; | ||||
iters = iters / data->count; | |||||
for (iter = 0; iter < iters; ++iter) { | for (iter = 0; iter < iters; ++iter) { | ||||
data->ecmult_multi(&data->ctx->error_callback, &data->ctx->ecmult_ctx, data->scratch, &data->output[iter], data->includes_g ? &data->scalars[data->offset1] : NULL, bench_callback, arg, count - includes_g); | data->ecmult_multi(&data->ctx->error_callback, &data->ctx->ecmult_ctx, data->scratch, &data->output[iter], data->includes_g ? &data->scalars[data->offset1] : NULL, bench_callback, arg, count - includes_g); | ||||
data->offset1 = (data->offset1 + count) % POINTS; | data->offset1 = (data->offset1 + count) % POINTS; | ||||
data->offset2 = (data->offset2 + count - 1) % POINTS; | data->offset2 = (data->offset2 + count - 1) % POINTS; | ||||
} | } | ||||
} | } | ||||
static void bench_ecmult_setup(void* arg) { | static void bench_ecmult_setup(void* arg) { | ||||
bench_data* data = (bench_data*)arg; | bench_data* data = (bench_data*)arg; | ||||
data->offset1 = (data->count * 0x537b7f6f + 0x8f66a481) % POINTS; | data->offset1 = (data->count * 0x537b7f6f + 0x8f66a481) % POINTS; | ||||
data->offset2 = (data->count * 0x7f6f537b + 0x6a1a8f49) % POINTS; | data->offset2 = (data->count * 0x7f6f537b + 0x6a1a8f49) % POINTS; | ||||
} | } | ||||
static void bench_ecmult_teardown(void* arg) { | static void bench_ecmult_teardown(void* arg, int iters) { | ||||
bench_data* data = (bench_data*)arg; | bench_data* data = (bench_data*)arg; | ||||
size_t iters = 1 + ITERS / data->count; | int iter; | ||||
size_t iter; | iters = iters / data->count; | ||||
/* Verify the results in teardown, to avoid doing comparisons while benchmarking. */ | /* Verify the results in teardown, to avoid doing comparisons while benchmarking. */ | ||||
for (iter = 0; iter < iters; ++iter) { | for (iter = 0; iter < iters; ++iter) { | ||||
secp256k1_gej tmp; | secp256k1_gej tmp; | ||||
secp256k1_gej_add_var(&tmp, &data->output[iter], &data->expected_output[iter], NULL); | secp256k1_gej_add_var(&tmp, &data->output[iter], &data->expected_output[iter], NULL); | ||||
CHECK(secp256k1_gej_is_infinity(&tmp)); | CHECK(secp256k1_gej_is_infinity(&tmp)); | ||||
} | } | ||||
} | } | ||||
static void generate_scalar(uint32_t num, secp256k1_scalar* scalar) { | static void generate_scalar(uint32_t num, secp256k1_scalar* scalar) { | ||||
secp256k1_sha256 sha256; | secp256k1_sha256 sha256; | ||||
unsigned char c[11] = {'e', 'c', 'm', 'u', 'l', 't', 0, 0, 0, 0}; | unsigned char c[11] = {'e', 'c', 'm', 'u', 'l', 't', 0, 0, 0, 0}; | ||||
unsigned char buf[32]; | unsigned char buf[32]; | ||||
int overflow = 0; | int overflow = 0; | ||||
c[6] = num; | c[6] = num; | ||||
c[7] = num >> 8; | c[7] = num >> 8; | ||||
c[8] = num >> 16; | c[8] = num >> 16; | ||||
c[9] = num >> 24; | c[9] = num >> 24; | ||||
secp256k1_sha256_initialize(&sha256); | secp256k1_sha256_initialize(&sha256); | ||||
secp256k1_sha256_write(&sha256, c, sizeof(c)); | secp256k1_sha256_write(&sha256, c, sizeof(c)); | ||||
secp256k1_sha256_finalize(&sha256, buf); | secp256k1_sha256_finalize(&sha256, buf); | ||||
secp256k1_scalar_set_b32(scalar, buf, &overflow); | secp256k1_scalar_set_b32(scalar, buf, &overflow); | ||||
CHECK(!overflow); | CHECK(!overflow); | ||||
} | } | ||||
static void run_test(bench_data* data, size_t count, int includes_g) { | static void run_test(bench_data* data, size_t count, int includes_g, int num_iters) { | ||||
char str[32]; | char str[32]; | ||||
static const secp256k1_scalar zero = SECP256K1_SCALAR_CONST(0, 0, 0, 0, 0, 0, 0, 0); | static const secp256k1_scalar zero = SECP256K1_SCALAR_CONST(0, 0, 0, 0, 0, 0, 0, 0); | ||||
size_t iters = 1 + ITERS / count; | size_t iters = 1 + num_iters / count; | ||||
size_t iter; | size_t iter; | ||||
data->count = count; | data->count = count; | ||||
data->includes_g = includes_g; | data->includes_g = includes_g; | ||||
/* Compute (the negation of) the expected results directly. */ | /* Compute (the negation of) the expected results directly. */ | ||||
data->offset1 = (data->count * 0x537b7f6f + 0x8f66a481) % POINTS; | data->offset1 = (data->count * 0x537b7f6f + 0x8f66a481) % POINTS; | ||||
data->offset2 = (data->count * 0x7f6f537b + 0x6a1a8f49) % POINTS; | data->offset2 = (data->count * 0x7f6f537b + 0x6a1a8f49) % POINTS; | ||||
for (iter = 0; iter < iters; ++iter) { | for (iter = 0; iter < iters; ++iter) { | ||||
secp256k1_scalar tmp; | secp256k1_scalar tmp; | ||||
secp256k1_scalar total = data->scalars[(data->offset1++) % POINTS]; | secp256k1_scalar total = data->scalars[(data->offset1++) % POINTS]; | ||||
size_t i = 0; | size_t i = 0; | ||||
for (i = 0; i + 1 < count; ++i) { | for (i = 0; i + 1 < count; ++i) { | ||||
secp256k1_scalar_mul(&tmp, &data->seckeys[(data->offset2++) % POINTS], &data->scalars[(data->offset1++) % POINTS]); | secp256k1_scalar_mul(&tmp, &data->seckeys[(data->offset2++) % POINTS], &data->scalars[(data->offset1++) % POINTS]); | ||||
secp256k1_scalar_add(&total, &total, &tmp); | secp256k1_scalar_add(&total, &total, &tmp); | ||||
} | } | ||||
secp256k1_scalar_negate(&total, &total); | secp256k1_scalar_negate(&total, &total); | ||||
secp256k1_ecmult(&data->ctx->ecmult_ctx, &data->expected_output[iter], NULL, &zero, &total); | secp256k1_ecmult(&data->ctx->ecmult_ctx, &data->expected_output[iter], NULL, &zero, &total); | ||||
} | } | ||||
/* Run the benchmark. */ | /* Run the benchmark. */ | ||||
sprintf(str, includes_g ? "ecmult_%ig" : "ecmult_%i", (int)count); | sprintf(str, includes_g ? "ecmult_%ig" : "ecmult_%i", (int)count); | ||||
run_benchmark(str, bench_ecmult, bench_ecmult_setup, bench_ecmult_teardown, data, 10, count * (1 + ITERS / count)); | run_benchmark(str, bench_ecmult, bench_ecmult_setup, bench_ecmult_teardown, data, 10, count * iters); | ||||
} | } | ||||
int main(int argc, char **argv) { | int main(int argc, char **argv) { | ||||
bench_data data; | bench_data data; | ||||
int i, p; | int i, p; | ||||
secp256k1_gej* pubkeys_gej; | secp256k1_gej* pubkeys_gej; | ||||
size_t scratch_size; | size_t scratch_size; | ||||
int iters = get_iters(10000); | |||||
data.ctx = secp256k1_context_create(SECP256K1_CONTEXT_SIGN | SECP256K1_CONTEXT_VERIFY); | data.ctx = secp256k1_context_create(SECP256K1_CONTEXT_SIGN | SECP256K1_CONTEXT_VERIFY); | ||||
scratch_size = secp256k1_strauss_scratch_size(POINTS) + STRAUSS_SCRATCH_OBJECTS*16; | scratch_size = secp256k1_strauss_scratch_size(POINTS) + STRAUSS_SCRATCH_OBJECTS*16; | ||||
data.scratch = secp256k1_scratch_space_create(data.ctx, scratch_size); | data.scratch = secp256k1_scratch_space_create(data.ctx, scratch_size); | ||||
data.ecmult_multi = secp256k1_ecmult_multi_var; | data.ecmult_multi = secp256k1_ecmult_multi_var; | ||||
if (argc > 1) { | if (argc > 1) { | ||||
if(have_flag(argc, argv, "pippenger_wnaf")) { | if(have_flag(argc, argv, "pippenger_wnaf")) { | ||||
printf("Using pippenger_wnaf:\n"); | printf("Using pippenger_wnaf:\n"); | ||||
Show All 12 Lines | if (argc > 1) { | ||||
return 1; | return 1; | ||||
} | } | ||||
} | } | ||||
/* Allocate stuff */ | /* Allocate stuff */ | ||||
data.scalars = malloc(sizeof(secp256k1_scalar) * POINTS); | data.scalars = malloc(sizeof(secp256k1_scalar) * POINTS); | ||||
data.seckeys = malloc(sizeof(secp256k1_scalar) * POINTS); | data.seckeys = malloc(sizeof(secp256k1_scalar) * POINTS); | ||||
data.pubkeys = malloc(sizeof(secp256k1_ge) * POINTS); | data.pubkeys = malloc(sizeof(secp256k1_ge) * POINTS); | ||||
data.expected_output = malloc(sizeof(secp256k1_gej) * (ITERS + 1)); | data.expected_output = malloc(sizeof(secp256k1_gej) * (iters + 1)); | ||||
data.output = malloc(sizeof(secp256k1_gej) * (ITERS + 1)); | data.output = malloc(sizeof(secp256k1_gej) * (iters + 1)); | ||||
/* Generate a set of scalars, and private/public keypairs. */ | /* Generate a set of scalars, and private/public keypairs. */ | ||||
pubkeys_gej = malloc(sizeof(secp256k1_gej) * POINTS); | pubkeys_gej = malloc(sizeof(secp256k1_gej) * POINTS); | ||||
secp256k1_gej_set_ge(&pubkeys_gej[0], &secp256k1_ge_const_g); | secp256k1_gej_set_ge(&pubkeys_gej[0], &secp256k1_ge_const_g); | ||||
secp256k1_scalar_set_int(&data.seckeys[0], 1); | secp256k1_scalar_set_int(&data.seckeys[0], 1); | ||||
for (i = 0; i < POINTS; ++i) { | for (i = 0; i < POINTS; ++i) { | ||||
generate_scalar(i, &data.scalars[i]); | generate_scalar(i, &data.scalars[i]); | ||||
if (i) { | if (i) { | ||||
secp256k1_gej_double_var(&pubkeys_gej[i], &pubkeys_gej[i - 1], NULL); | secp256k1_gej_double_var(&pubkeys_gej[i], &pubkeys_gej[i - 1], NULL); | ||||
secp256k1_scalar_add(&data.seckeys[i], &data.seckeys[i - 1], &data.seckeys[i - 1]); | secp256k1_scalar_add(&data.seckeys[i], &data.seckeys[i - 1], &data.seckeys[i - 1]); | ||||
} | } | ||||
} | } | ||||
secp256k1_ge_set_all_gej_var(data.pubkeys, pubkeys_gej, POINTS); | secp256k1_ge_set_all_gej_var(data.pubkeys, pubkeys_gej, POINTS); | ||||
free(pubkeys_gej); | free(pubkeys_gej); | ||||
for (i = 1; i <= 8; ++i) { | for (i = 1; i <= 8; ++i) { | ||||
run_test(&data, i, 1); | run_test(&data, i, 1, iters); | ||||
} | } | ||||
/* This is disabled with low count of iterations because the loop runs 77 times even with iters=1 | |||||
* and the higher it goes the longer the computation takes(more points) | |||||
* So we don't run this benchmark with low iterations to prevent slow down */ | |||||
if (iters > 2) { | |||||
for (p = 0; p <= 11; ++p) { | for (p = 0; p <= 11; ++p) { | ||||
for (i = 9; i <= 16; ++i) { | for (i = 9; i <= 16; ++i) { | ||||
run_test(&data, i << p, 1); | run_test(&data, i << p, 1, iters); | ||||
} | } | ||||
} | } | ||||
} | |||||
if (data.scratch != NULL) { | if (data.scratch != NULL) { | ||||
secp256k1_scratch_space_destroy(data.ctx, data.scratch); | secp256k1_scratch_space_destroy(data.ctx, data.scratch); | ||||
} | } | ||||
secp256k1_context_destroy(data.ctx); | secp256k1_context_destroy(data.ctx); | ||||
free(data.scalars); | free(data.scalars); | ||||
free(data.pubkeys); | free(data.pubkeys); | ||||
free(data.seckeys); | free(data.seckeys); | ||||
free(data.output); | free(data.output); | ||||
free(data.expected_output); | free(data.expected_output); | ||||
return(0); | return(0); | ||||
} | } |