bench_internal.c
1 /*********************************************************************** 2 * Copyright (c) 2014-2015 Pieter Wuille * 3 * Distributed under the MIT software license, see the accompanying * 4 * file COPYING or https://www.opensource.org/licenses/mit-license.php.* 5 ***********************************************************************/ 6 #include <stdio.h> 7 #include <stdlib.h> 8 9 #include "secp256k1.c" 10 #include "../include/secp256k1.h" 11 12 #include "assumptions.h" 13 #include "util.h" 14 #include "hash_impl.h" 15 #include "field_impl.h" 16 #include "group_impl.h" 17 #include "scalar_impl.h" 18 #include "ecmult_impl.h" 19 #include "bench.h" 20 21 static void help(const char *executable_path, int default_iters) { 22 printf("Benchmarks various internal routines.\n"); 23 printf("\n"); 24 printf("The default number of iterations for each benchmark is %d. This can be\n", default_iters); 25 printf("customized using the SECP256K1_BENCH_ITERS environment variable.\n"); 26 printf("\n"); 27 printf("Usage: %s [args]\n", executable_path); 28 printf("By default, all benchmarks will be run.\n"); 29 printf("args:\n"); 30 printf(" help : display this help and exit\n"); 31 printf(" scalar : all scalar operations (add, half, inverse, mul, negate, split)\n"); 32 printf(" field : all field operations (half, inverse, issquare, mul, normalize, sqr, sqrt)\n"); 33 printf(" group : all group operations (add, double, to_affine)\n"); 34 printf(" ecmult : all point multiplication operations (ecmult_wnaf) \n"); 35 printf(" hash : all hash algorithms (hmac, rng6979, sha256)\n"); 36 printf(" context : all context object operations (context_create)\n"); 37 printf("\n"); 38 } 39 40 typedef struct { 41 const secp256k1_context* ctx; 42 secp256k1_scalar scalar[2]; 43 secp256k1_fe fe[4]; 44 secp256k1_ge ge[2]; 45 secp256k1_gej gej[2]; 46 unsigned char data[64]; 47 int wnaf[256]; 48 } bench_inv; 49 50 static void bench_setup(void* arg) { 51 bench_inv *data = (bench_inv*)arg; 52 53 static const unsigned char init[4][32] = { 54 /* Initializer for scalar[0], fe[0], first half of data, the X coordinate of ge[0], 55 and the (implied affine) X coordinate of gej[0]. */ 56 { 57 0x02, 0x03, 0x05, 0x07, 0x0b, 0x0d, 0x11, 0x13, 58 0x17, 0x1d, 0x1f, 0x25, 0x29, 0x2b, 0x2f, 0x35, 59 0x3b, 0x3d, 0x43, 0x47, 0x49, 0x4f, 0x53, 0x59, 60 0x61, 0x65, 0x67, 0x6b, 0x6d, 0x71, 0x7f, 0x83 61 }, 62 /* Initializer for scalar[1], fe[1], first half of data, the X coordinate of ge[1], 63 and the (implied affine) X coordinate of gej[1]. */ 64 { 65 0x82, 0x83, 0x85, 0x87, 0x8b, 0x8d, 0x81, 0x83, 66 0x97, 0xad, 0xaf, 0xb5, 0xb9, 0xbb, 0xbf, 0xc5, 67 0xdb, 0xdd, 0xe3, 0xe7, 0xe9, 0xef, 0xf3, 0xf9, 68 0x11, 0x15, 0x17, 0x1b, 0x1d, 0xb1, 0xbf, 0xd3 69 }, 70 /* Initializer for fe[2] and the Z coordinate of gej[0]. */ 71 { 72 0x3d, 0x2d, 0xef, 0xf4, 0x25, 0x98, 0x4f, 0x5d, 73 0xe2, 0xca, 0x5f, 0x41, 0x3f, 0x3f, 0xce, 0x44, 74 0xaa, 0x2c, 0x53, 0x8a, 0xc6, 0x59, 0x1f, 0x38, 75 0x38, 0x23, 0xe4, 0x11, 0x27, 0xc6, 0xa0, 0xe7 76 }, 77 /* Initializer for fe[3] and the Z coordinate of gej[1]. */ 78 { 79 0xbd, 0x21, 0xa5, 0xe1, 0x13, 0x50, 0x73, 0x2e, 80 0x52, 0x98, 0xc8, 0x9e, 0xab, 0x00, 0xa2, 0x68, 81 0x43, 0xf5, 0xd7, 0x49, 0x80, 0x72, 0xa7, 0xf3, 82 0xd7, 0x60, 0xe6, 0xab, 0x90, 0x92, 0xdf, 0xc5 83 } 84 }; 85 86 /* Customize context if needed */ 87 data->ctx = secp256k1_context_static; 88 89 secp256k1_scalar_set_b32(&data->scalar[0], init[0], NULL); 90 secp256k1_scalar_set_b32(&data->scalar[1], init[1], NULL); 91 secp256k1_fe_set_b32_limit(&data->fe[0], init[0]); 92 secp256k1_fe_set_b32_limit(&data->fe[1], init[1]); 93 secp256k1_fe_set_b32_limit(&data->fe[2], init[2]); 94 secp256k1_fe_set_b32_limit(&data->fe[3], init[3]); 95 CHECK(secp256k1_ge_set_xo_var(&data->ge[0], &data->fe[0], 0)); 96 CHECK(secp256k1_ge_set_xo_var(&data->ge[1], &data->fe[1], 1)); 97 secp256k1_gej_set_ge(&data->gej[0], &data->ge[0]); 98 secp256k1_gej_rescale(&data->gej[0], &data->fe[2]); 99 secp256k1_gej_set_ge(&data->gej[1], &data->ge[1]); 100 secp256k1_gej_rescale(&data->gej[1], &data->fe[3]); 101 memcpy(data->data, init[0], 32); 102 memcpy(data->data + 32, init[1], 32); 103 } 104 105 static void bench_scalar_add(void* arg, int iters) { 106 int i, j = 0; 107 bench_inv *data = (bench_inv*)arg; 108 109 for (i = 0; i < iters; i++) { 110 j += secp256k1_scalar_add(&data->scalar[0], &data->scalar[0], &data->scalar[1]); 111 } 112 CHECK(j <= iters); 113 } 114 115 static void bench_scalar_negate(void* arg, int iters) { 116 int i; 117 bench_inv *data = (bench_inv*)arg; 118 119 for (i = 0; i < iters; i++) { 120 secp256k1_scalar_negate(&data->scalar[0], &data->scalar[0]); 121 } 122 } 123 124 static void bench_scalar_half(void* arg, int iters) { 125 int i; 126 bench_inv *data = (bench_inv*)arg; 127 secp256k1_scalar s = data->scalar[0]; 128 129 for (i = 0; i < iters; i++) { 130 secp256k1_scalar_half(&s, &s); 131 } 132 133 data->scalar[0] = s; 134 } 135 136 static void bench_scalar_mul(void* arg, int iters) { 137 int i; 138 bench_inv *data = (bench_inv*)arg; 139 140 for (i = 0; i < iters; i++) { 141 secp256k1_scalar_mul(&data->scalar[0], &data->scalar[0], &data->scalar[1]); 142 } 143 } 144 145 static void bench_scalar_split(void* arg, int iters) { 146 int i, j = 0; 147 bench_inv *data = (bench_inv*)arg; 148 secp256k1_scalar tmp; 149 150 for (i = 0; i < iters; i++) { 151 secp256k1_scalar_split_lambda(&tmp, &data->scalar[1], &data->scalar[0]); 152 j += secp256k1_scalar_add(&data->scalar[0], &tmp, &data->scalar[1]); 153 } 154 CHECK(j <= iters); 155 } 156 157 static void bench_scalar_inverse(void* arg, int iters) { 158 int i, j = 0; 159 bench_inv *data = (bench_inv*)arg; 160 161 for (i = 0; i < iters; i++) { 162 secp256k1_scalar_inverse(&data->scalar[0], &data->scalar[0]); 163 j += secp256k1_scalar_add(&data->scalar[0], &data->scalar[0], &data->scalar[1]); 164 } 165 CHECK(j <= iters); 166 } 167 168 static void bench_scalar_inverse_var(void* arg, int iters) { 169 int i, j = 0; 170 bench_inv *data = (bench_inv*)arg; 171 172 for (i = 0; i < iters; i++) { 173 secp256k1_scalar_inverse_var(&data->scalar[0], &data->scalar[0]); 174 j += secp256k1_scalar_add(&data->scalar[0], &data->scalar[0], &data->scalar[1]); 175 } 176 CHECK(j <= iters); 177 } 178 179 static void bench_field_half(void* arg, int iters) { 180 int i; 181 bench_inv *data = (bench_inv*)arg; 182 183 for (i = 0; i < iters; i++) { 184 secp256k1_fe_half(&data->fe[0]); 185 } 186 } 187 188 static void bench_field_normalize(void* arg, int iters) { 189 int i; 190 bench_inv *data = (bench_inv*)arg; 191 192 for (i = 0; i < iters; i++) { 193 secp256k1_fe_normalize(&data->fe[0]); 194 } 195 } 196 197 static void bench_field_normalize_weak(void* arg, int iters) { 198 int i; 199 bench_inv *data = (bench_inv*)arg; 200 201 for (i = 0; i < iters; i++) { 202 secp256k1_fe_normalize_weak(&data->fe[0]); 203 } 204 } 205 206 static void bench_field_mul(void* arg, int iters) { 207 int i; 208 bench_inv *data = (bench_inv*)arg; 209 210 for (i = 0; i < iters; i++) { 211 secp256k1_fe_mul(&data->fe[0], &data->fe[0], &data->fe[1]); 212 } 213 } 214 215 static void bench_field_sqr(void* arg, int iters) { 216 int i; 217 bench_inv *data = (bench_inv*)arg; 218 219 for (i = 0; i < iters; i++) { 220 secp256k1_fe_sqr(&data->fe[0], &data->fe[0]); 221 } 222 } 223 224 static void bench_field_inverse(void* arg, int iters) { 225 int i; 226 bench_inv *data = (bench_inv*)arg; 227 228 for (i = 0; i < iters; i++) { 229 secp256k1_fe_inv(&data->fe[0], &data->fe[0]); 230 secp256k1_fe_add(&data->fe[0], &data->fe[1]); 231 } 232 } 233 234 static void bench_field_inverse_var(void* arg, int iters) { 235 int i; 236 bench_inv *data = (bench_inv*)arg; 237 238 for (i = 0; i < iters; i++) { 239 secp256k1_fe_inv_var(&data->fe[0], &data->fe[0]); 240 secp256k1_fe_add(&data->fe[0], &data->fe[1]); 241 } 242 } 243 244 static void bench_field_sqrt(void* arg, int iters) { 245 int i, j = 0; 246 bench_inv *data = (bench_inv*)arg; 247 secp256k1_fe t; 248 249 for (i = 0; i < iters; i++) { 250 t = data->fe[0]; 251 j += secp256k1_fe_sqrt(&data->fe[0], &t); 252 secp256k1_fe_add(&data->fe[0], &data->fe[1]); 253 } 254 CHECK(j <= iters); 255 } 256 257 static void bench_field_is_square_var(void* arg, int iters) { 258 int i, j = 0; 259 bench_inv *data = (bench_inv*)arg; 260 secp256k1_fe t = data->fe[0]; 261 262 for (i = 0; i < iters; i++) { 263 j += secp256k1_fe_is_square_var(&t); 264 secp256k1_fe_add(&t, &data->fe[1]); 265 secp256k1_fe_normalize_var(&t); 266 } 267 CHECK(j <= iters); 268 } 269 270 static void bench_group_double_var(void* arg, int iters) { 271 int i; 272 bench_inv *data = (bench_inv*)arg; 273 274 for (i = 0; i < iters; i++) { 275 secp256k1_gej_double_var(&data->gej[0], &data->gej[0], NULL); 276 } 277 } 278 279 static void bench_group_add_var(void* arg, int iters) { 280 int i; 281 bench_inv *data = (bench_inv*)arg; 282 283 for (i = 0; i < iters; i++) { 284 secp256k1_gej_add_var(&data->gej[0], &data->gej[0], &data->gej[1], NULL); 285 } 286 } 287 288 static void bench_group_add_affine(void* arg, int iters) { 289 int i; 290 bench_inv *data = (bench_inv*)arg; 291 292 for (i = 0; i < iters; i++) { 293 secp256k1_gej_add_ge(&data->gej[0], &data->gej[0], &data->ge[1]); 294 } 295 } 296 297 static void bench_group_add_affine_var(void* arg, int iters) { 298 int i; 299 bench_inv *data = (bench_inv*)arg; 300 301 for (i = 0; i < iters; i++) { 302 secp256k1_gej_add_ge_var(&data->gej[0], &data->gej[0], &data->ge[1], NULL); 303 } 304 } 305 306 static void bench_group_add_zinv_var(void* arg, int iters) { 307 int i; 308 bench_inv *data = (bench_inv*)arg; 309 310 for (i = 0; i < iters; i++) { 311 secp256k1_gej_add_zinv_var(&data->gej[0], &data->gej[0], &data->ge[1], &data->gej[0].y); 312 } 313 } 314 315 static void bench_group_to_affine_var(void* arg, int iters) { 316 int i; 317 bench_inv *data = (bench_inv*)arg; 318 319 for (i = 0; i < iters; ++i) { 320 secp256k1_ge_set_gej_var(&data->ge[1], &data->gej[0]); 321 /* Use the output affine X/Y coordinates to vary the input X/Y/Z coordinates. 322 Note that the resulting coordinates will generally not correspond to a point 323 on the curve, but this is not a problem for the code being benchmarked here. 324 Adding and normalizing have less overhead than EC operations (which could 325 guarantee the point remains on the curve). */ 326 secp256k1_fe_add(&data->gej[0].x, &data->ge[1].y); 327 secp256k1_fe_add(&data->gej[0].y, &data->fe[2]); 328 secp256k1_fe_add(&data->gej[0].z, &data->ge[1].x); 329 secp256k1_fe_normalize_var(&data->gej[0].x); 330 secp256k1_fe_normalize_var(&data->gej[0].y); 331 secp256k1_fe_normalize_var(&data->gej[0].z); 332 } 333 } 334 335 static void bench_ecmult_wnaf(void* arg, int iters) { 336 int i, bits = 0, overflow = 0; 337 bench_inv *data = (bench_inv*)arg; 338 339 for (i = 0; i < iters; i++) { 340 bits += secp256k1_ecmult_wnaf(data->wnaf, 256, &data->scalar[0], WINDOW_A); 341 overflow += secp256k1_scalar_add(&data->scalar[0], &data->scalar[0], &data->scalar[1]); 342 } 343 CHECK(overflow >= 0); 344 CHECK(bits <= 256*iters); 345 } 346 347 static void bench_sha256(void* arg, int iters) { 348 int i; 349 bench_inv *data = (bench_inv*)arg; 350 secp256k1_sha256 sha; 351 const secp256k1_hash_ctx *hash_ctx = secp256k1_get_hash_context(data->ctx); 352 353 for (i = 0; i < iters; i++) { 354 secp256k1_sha256_initialize(&sha); 355 secp256k1_sha256_write(hash_ctx, &sha, data->data, 32); 356 secp256k1_sha256_finalize(hash_ctx, &sha, data->data); 357 } 358 } 359 360 static void bench_hmac_sha256(void* arg, int iters) { 361 int i; 362 bench_inv *data = (bench_inv*)arg; 363 secp256k1_hmac_sha256 hmac; 364 const secp256k1_hash_ctx *hash_ctx = secp256k1_get_hash_context(data->ctx); 365 366 for (i = 0; i < iters; i++) { 367 secp256k1_hmac_sha256_initialize(hash_ctx, &hmac, data->data, 32); 368 secp256k1_hmac_sha256_write(hash_ctx, &hmac, data->data, 32); 369 secp256k1_hmac_sha256_finalize(hash_ctx, &hmac, data->data); 370 } 371 } 372 373 static void bench_rfc6979_hmac_sha256(void* arg, int iters) { 374 int i; 375 bench_inv *data = (bench_inv*)arg; 376 secp256k1_rfc6979_hmac_sha256 rng; 377 const secp256k1_hash_ctx *hash_ctx = secp256k1_get_hash_context(data->ctx); 378 379 for (i = 0; i < iters; i++) { 380 secp256k1_rfc6979_hmac_sha256_initialize(hash_ctx, &rng, data->data, 64); 381 secp256k1_rfc6979_hmac_sha256_generate(hash_ctx, &rng, data->data, 32); 382 } 383 } 384 385 static void bench_context(void* arg, int iters) { 386 int i; 387 (void)arg; 388 for (i = 0; i < iters; i++) { 389 secp256k1_context_destroy(secp256k1_context_create(SECP256K1_CONTEXT_NONE)); 390 } 391 } 392 393 int main(int argc, char **argv) { 394 bench_inv data; 395 int d = argc == 1; /* default */ 396 int default_iters = 20000; 397 int iters = get_iters(default_iters); 398 if (iters == 0) { 399 help(argv[0], default_iters); 400 return EXIT_FAILURE; 401 } 402 403 if (argc > 1) { 404 if (have_flag(argc, argv, "-h") 405 || have_flag(argc, argv, "--help") 406 || have_flag(argc, argv, "help")) { 407 help(argv[0], default_iters); 408 return EXIT_SUCCESS; 409 } 410 } 411 412 print_output_table_header_row(); 413 414 if (d || have_flag(argc, argv, "scalar") || have_flag(argc, argv, "half")) run_benchmark("scalar_half", bench_scalar_half, bench_setup, NULL, &data, 10, iters*100); 415 if (d || have_flag(argc, argv, "scalar") || have_flag(argc, argv, "add")) run_benchmark("scalar_add", bench_scalar_add, bench_setup, NULL, &data, 10, iters*100); 416 if (d || have_flag(argc, argv, "scalar") || have_flag(argc, argv, "negate")) run_benchmark("scalar_negate", bench_scalar_negate, bench_setup, NULL, &data, 10, iters*100); 417 if (d || have_flag(argc, argv, "scalar") || have_flag(argc, argv, "mul")) run_benchmark("scalar_mul", bench_scalar_mul, bench_setup, NULL, &data, 10, iters*10); 418 if (d || have_flag(argc, argv, "scalar") || have_flag(argc, argv, "split")) run_benchmark("scalar_split", bench_scalar_split, bench_setup, NULL, &data, 10, iters); 419 if (d || have_flag(argc, argv, "scalar") || have_flag(argc, argv, "inverse")) run_benchmark("scalar_inverse", bench_scalar_inverse, bench_setup, NULL, &data, 10, iters); 420 if (d || have_flag(argc, argv, "scalar") || have_flag(argc, argv, "inverse")) run_benchmark("scalar_inverse_var", bench_scalar_inverse_var, bench_setup, NULL, &data, 10, iters); 421 422 if (d || have_flag(argc, argv, "field") || have_flag(argc, argv, "half")) run_benchmark("field_half", bench_field_half, bench_setup, NULL, &data, 10, iters*100); 423 if (d || have_flag(argc, argv, "field") || have_flag(argc, argv, "normalize")) run_benchmark("field_normalize", bench_field_normalize, bench_setup, NULL, &data, 10, iters*100); 424 if (d || have_flag(argc, argv, "field") || have_flag(argc, argv, "normalize")) run_benchmark("field_normalize_weak", bench_field_normalize_weak, bench_setup, NULL, &data, 10, iters*100); 425 if (d || have_flag(argc, argv, "field") || have_flag(argc, argv, "sqr")) run_benchmark("field_sqr", bench_field_sqr, bench_setup, NULL, &data, 10, iters*10); 426 if (d || have_flag(argc, argv, "field") || have_flag(argc, argv, "mul")) run_benchmark("field_mul", bench_field_mul, bench_setup, NULL, &data, 10, iters*10); 427 if (d || have_flag(argc, argv, "field") || have_flag(argc, argv, "inverse")) run_benchmark("field_inverse", bench_field_inverse, bench_setup, NULL, &data, 10, iters); 428 if (d || have_flag(argc, argv, "field") || have_flag(argc, argv, "inverse")) run_benchmark("field_inverse_var", bench_field_inverse_var, bench_setup, NULL, &data, 10, iters); 429 if (d || have_flag(argc, argv, "field") || have_flag(argc, argv, "issquare")) run_benchmark("field_is_square_var", bench_field_is_square_var, bench_setup, NULL, &data, 10, iters); 430 if (d || have_flag(argc, argv, "field") || have_flag(argc, argv, "sqrt")) run_benchmark("field_sqrt", bench_field_sqrt, bench_setup, NULL, &data, 10, iters); 431 432 if (d || have_flag(argc, argv, "group") || have_flag(argc, argv, "double")) run_benchmark("group_double_var", bench_group_double_var, bench_setup, NULL, &data, 10, iters*10); 433 if (d || have_flag(argc, argv, "group") || have_flag(argc, argv, "add")) run_benchmark("group_add_var", bench_group_add_var, bench_setup, NULL, &data, 10, iters*10); 434 if (d || have_flag(argc, argv, "group") || have_flag(argc, argv, "add")) run_benchmark("group_add_affine", bench_group_add_affine, bench_setup, NULL, &data, 10, iters*10); 435 if (d || have_flag(argc, argv, "group") || have_flag(argc, argv, "add")) run_benchmark("group_add_affine_var", bench_group_add_affine_var, bench_setup, NULL, &data, 10, iters*10); 436 if (d || have_flag(argc, argv, "group") || have_flag(argc, argv, "add")) run_benchmark("group_add_zinv_var", bench_group_add_zinv_var, bench_setup, NULL, &data, 10, iters*10); 437 if (d || have_flag(argc, argv, "group") || have_flag(argc, argv, "to_affine")) run_benchmark("group_to_affine_var", bench_group_to_affine_var, bench_setup, NULL, &data, 10, iters); 438 439 if (d || have_flag(argc, argv, "ecmult") || have_flag(argc, argv, "wnaf")) run_benchmark("ecmult_wnaf", bench_ecmult_wnaf, bench_setup, NULL, &data, 10, iters); 440 441 if (d || have_flag(argc, argv, "hash") || have_flag(argc, argv, "sha256")) run_benchmark("hash_sha256", bench_sha256, bench_setup, NULL, &data, 10, iters); 442 if (d || have_flag(argc, argv, "hash") || have_flag(argc, argv, "hmac")) run_benchmark("hash_hmac_sha256", bench_hmac_sha256, bench_setup, NULL, &data, 10, iters); 443 if (d || have_flag(argc, argv, "hash") || have_flag(argc, argv, "rng6979")) run_benchmark("hash_rfc6979_hmac_sha256", bench_rfc6979_hmac_sha256, bench_setup, NULL, &data, 10, iters); 444 445 if (d || have_flag(argc, argv, "context")) run_benchmark("context_create", bench_context, bench_setup, NULL, &data, 10, iters); 446 447 return EXIT_SUCCESS; 448 }