src/ecmult_impl.h

   1 /*****************************************************************************
   2  * Copyright (c) 2013, 2014, 2017 Pieter Wuille, Andrew Poelstra, Jonas Nick *
   3  * Distributed under the MIT software license, see the accompanying          *
   4  * file COPYING or http://www.opensource.org/licenses/mit-license.php.       *
   5  *****************************************************************************/
   6
   7 #ifndef SECP256K1_ECMULT_IMPL_H
   8 #define SECP256K1_ECMULT_IMPL_H
   9
  10 #include <string.h>
  11 #include <stdint.h>
  12
  13 #include "group.h"
  14 #include "scalar.h"
  15 #include "ecmult.h"
  16
  17 #if defined(EXHAUSTIVE_TEST_ORDER)
  18 /* We need to lower these values for exhaustive tests because
  19  * the tables cannot have infinities in them (this breaks the
  20  * affine-isomorphism stuff which tracks z-ratios) */
  21 #  if EXHAUSTIVE_TEST_ORDER > 128
  22 #    define WINDOW_A 5
  23 #    define WINDOW_G 8
  24 #  elif EXHAUSTIVE_TEST_ORDER > 8
  25 #    define WINDOW_A 4
  26 #    define WINDOW_G 4
  27 #  else
  28 #    define WINDOW_A 2
  29 #    define WINDOW_G 2
  30 #  endif
  31 #else
  32 /* optimal for 128-bit and 256-bit exponents. */
  33 #define WINDOW_A 5
  34 /** larger numbers may result in slightly better performance, at the cost of
  35     exponentially larger precomputed tables. */
  36 #ifdef USE_ENDOMORPHISM
  37 /** Two tables for window size 15: 1.375 MiB. */
  38 #define WINDOW_G 15
  39 #else
  40 /** One table for window size 16: 1.375 MiB. */
  41 #define WINDOW_G 16
  42 #endif
  43 #endif
  44
  45 #ifdef USE_ENDOMORPHISM
  46     #define WNAF_BITS 128
  47 #else
  48     #define WNAF_BITS 256
  49 #endif
  50 #define WNAF_SIZE(w) ((WNAF_BITS + (w) - 1) / (w))
  51
  52 /** The number of entries a table with precomputed multiples needs to have. */
  53 #define ECMULT_TABLE_SIZE(w) (1 << ((w)-2))
  54
  55 /* The number of objects allocated on the scratch space for ecmult_multi algorithms */
  56 #define PIPPENGER_SCRATCH_OBJECTS 6
  57 #define STRAUSS_SCRATCH_OBJECTS 6
  58
  59 #define PIPPENGER_MAX_BUCKET_WINDOW 12
  60
  61 /* Minimum number of points for which pippenger_wnaf is faster than strauss wnaf */
  62 #ifdef USE_ENDOMORPHISM
  63     #define ECMULT_PIPPENGER_THRESHOLD 88
  64 #else
  65     #define ECMULT_PIPPENGER_THRESHOLD 160
  66 #endif
  67
  68 #ifdef USE_ENDOMORPHISM
  69     #define ECMULT_MAX_POINTS_PER_BATCH 5000000
  70 #else
  71     #define ECMULT_MAX_POINTS_PER_BATCH 10000000
  72 #endif
  73
  74 /** Fill a table 'prej' with precomputed odd multiples of a. Prej will contain
  75  *  the values [1*a,3*a,...,(2*n-1)*a], so it space for n values. zr[0] will
  76  *  contain prej[0].z / a.z. The other zr[i] values = prej[i].z / prej[i-1].z.
  77  *  Prej's Z values are undefined, except for the last value.
  78  */
  79 static void secp256k1_ecmult_odd_multiples_table(int n, secp256k1_gej *prej, secp256k1_fe *zr, const secp256k1_gej *a) {
  80     secp256k1_gej d;
  81     secp256k1_ge a_ge, d_ge;
  82     int i;
  83
  84     VERIFY_CHECK(!a->infinity);
  85
  86     secp256k1_gej_double_var(&d, a, NULL);
  87
  88     /*
  89      * Perform the additions on an isomorphism where 'd' is affine: drop the z coordinate
  90      * of 'd', and scale the 1P starting value's x/y coordinates without changing its z.
  91      */
  92     d_ge.x = d.x;
  93     d_ge.y = d.y;
  94     d_ge.infinity = 0;
  95
  96     secp256k1_ge_set_gej_zinv(&a_ge, a, &d.z);
  97     prej[0].x = a_ge.x;
  98     prej[0].y = a_ge.y;
  99     prej[0].z = a->z;
 100     prej[0].infinity = 0;
 101
 102     zr[0] = d.z;
 103     for (i = 1; i < n; i++) {
 104         secp256k1_gej_add_ge_var(&prej[i], &prej[i-1], &d_ge, &zr[i]);
 105     }
 106
 107     /*
 108      * Each point in 'prej' has a z coordinate too small by a factor of 'd.z'. Only
 109      * the final point's z coordinate is actually used though, so just update that.
 110      */
 111     secp256k1_fe_mul(&prej[n-1].z, &prej[n-1].z, &d.z);
 112 }
 113
 114 /** Fill a table 'pre' with precomputed odd multiples of a.
 115  *
 116  *  There are two versions of this function:
 117  *  - secp256k1_ecmult_odd_multiples_table_globalz_windowa which brings its
 118  *    resulting point set to a single constant Z denominator, stores the X and Y
 119  *    coordinates as ge_storage points in pre, and stores the global Z in rz.
 120  *    It only operates on tables sized for WINDOW_A wnaf multiples.
 121  *  - secp256k1_ecmult_odd_multiples_table_storage_var, which converts its
 122  *    resulting point set to actually affine points, and stores those in pre.
 123  *    It operates on tables of any size, but uses heap-allocated temporaries.
 124  *
 125  *  To compute a*P + b*G, we compute a table for P using the first function,
 126  *  and for G using the second (which requires an inverse, but it only needs to
 127  *  happen once).
 128  */
 129 static void secp256k1_ecmult_odd_multiples_table_globalz_windowa(secp256k1_ge *pre, secp256k1_fe *globalz, const secp256k1_gej *a) {
 130     secp256k1_gej prej[ECMULT_TABLE_SIZE(WINDOW_A)];
 131     secp256k1_fe zr[ECMULT_TABLE_SIZE(WINDOW_A)];
 132
 133     /* Compute the odd multiples in Jacobian form. */
 134     secp256k1_ecmult_odd_multiples_table(ECMULT_TABLE_SIZE(WINDOW_A), prej, zr, a);
 135     /* Bring them to the same Z denominator. */
 136     secp256k1_ge_globalz_set_table_gej(ECMULT_TABLE_SIZE(WINDOW_A), pre, globalz, prej, zr);
 137 }
 138
 139 static void secp256k1_ecmult_odd_multiples_table_storage_var(int n, secp256k1_ge_storage *pre, const secp256k1_gej *a, const secp256k1_callback *cb) {
 140     secp256k1_gej *prej = (secp256k1_gej*)checked_malloc(cb, sizeof(secp256k1_gej) * n);
 141     secp256k1_ge *prea = (secp256k1_ge*)checked_malloc(cb, sizeof(secp256k1_ge) * n);
 142     secp256k1_fe *zr = (secp256k1_fe*)checked_malloc(cb, sizeof(secp256k1_fe) * n);
 143     int i;
 144
 145     /* Compute the odd multiples in Jacobian form. */
 146     secp256k1_ecmult_odd_multiples_table(n, prej, zr, a);
 147     /* Convert them in batch to affine coordinates. */
 148     secp256k1_ge_set_table_gej_var(prea, prej, zr, n);
 149     /* Convert them to compact storage form. */
 150     for (i = 0; i < n; i++) {
 151         secp256k1_ge_to_storage(&pre[i], &prea[i]);
 152     }
 153
 154     free(prea);
 155     free(prej);
 156     free(zr);
 157 }
 158
 159 /** The following two macro retrieves a particular odd multiple from a table
 160  *  of precomputed multiples. */
 161 #define ECMULT_TABLE_GET_GE(r,pre,n,w) do { \
 162     VERIFY_CHECK(((n) & 1) == 1); \
 163     VERIFY_CHECK((n) >= -((1 << ((w)-1)) - 1)); \
 164     VERIFY_CHECK((n) <=  ((1 << ((w)-1)) - 1)); \
 165     if ((n) > 0) { \
 166         *(r) = (pre)[((n)-1)/2]; \
 167     } else { \
 168         secp256k1_ge_neg((r), &(pre)[(-(n)-1)/2]); \
 169     } \
 170 } while(0)
 171
 172 #define ECMULT_TABLE_GET_GE_STORAGE(r,pre,n,w) do { \
 173     VERIFY_CHECK(((n) & 1) == 1); \
 174     VERIFY_CHECK((n) >= -((1 << ((w)-1)) - 1)); \
 175     VERIFY_CHECK((n) <=  ((1 << ((w)-1)) - 1)); \
 176     if ((n) > 0) { \
 177         secp256k1_ge_from_storage((r), &(pre)[((n)-1)/2]); \
 178     } else { \
 179         secp256k1_ge_from_storage((r), &(pre)[(-(n)-1)/2]); \
 180         secp256k1_ge_neg((r), (r)); \
 181     } \
 182 } while(0)
 183
 184 static void secp256k1_ecmult_context_init(secp256k1_ecmult_context *ctx) {
 185     ctx->pre_g = NULL;
 186 #ifdef USE_ENDOMORPHISM
 187     ctx->pre_g_128 = NULL;
 188 #endif
 189 }
 190
 191 static void secp256k1_ecmult_context_build(secp256k1_ecmult_context *ctx, const secp256k1_callback *cb) {
 192     secp256k1_gej gj;
 193
 194     if (ctx->pre_g != NULL) {
 195         return;
 196     }
 197
 198     /* get the generator */
 199     secp256k1_gej_set_ge(&gj, &secp256k1_ge_const_g);
 200
 201     ctx->pre_g = (secp256k1_ge_storage (*)[])checked_malloc(cb, sizeof((*ctx->pre_g)[0]) * ECMULT_TABLE_SIZE(WINDOW_G));
 202
 203     /* precompute the tables with odd multiples */
 204     secp256k1_ecmult_odd_multiples_table_storage_var(ECMULT_TABLE_SIZE(WINDOW_G), *ctx->pre_g, &gj, cb);
 205
 206 #ifdef USE_ENDOMORPHISM
 207     {
 208         secp256k1_gej g_128j;
 209         int i;
 210
 211         ctx->pre_g_128 = (secp256k1_ge_storage (*)[])checked_malloc(cb, sizeof((*ctx->pre_g_128)[0]) * ECMULT_TABLE_SIZE(WINDOW_G));
 212
 213         /* calculate 2^128*generator */
 214         g_128j = gj;
 215         for (i = 0; i < 128; i++) {
 216             secp256k1_gej_double_var(&g_128j, &g_128j, NULL);
 217         }
 218         secp256k1_ecmult_odd_multiples_table_storage_var(ECMULT_TABLE_SIZE(WINDOW_G), *ctx->pre_g_128, &g_128j, cb);
 219     }
 220 #endif
 221 }
 222
 223 static void secp256k1_ecmult_context_clone(secp256k1_ecmult_context *dst,
 224                                            const secp256k1_ecmult_context *src, const secp256k1_callback *cb) {
 225     if (src->pre_g == NULL) {
 226         dst->pre_g = NULL;
 227     } else {
 228         size_t size = sizeof((*dst->pre_g)[0]) * ECMULT_TABLE_SIZE(WINDOW_G);
 229         dst->pre_g = (secp256k1_ge_storage (*)[])checked_malloc(cb, size);
 230         memcpy(dst->pre_g, src->pre_g, size);
 231     }
 232 #ifdef USE_ENDOMORPHISM
 233     if (src->pre_g_128 == NULL) {
 234         dst->pre_g_128 = NULL;
 235     } else {
 236         size_t size = sizeof((*dst->pre_g_128)[0]) * ECMULT_TABLE_SIZE(WINDOW_G);
 237         dst->pre_g_128 = (secp256k1_ge_storage (*)[])checked_malloc(cb, size);
 238         memcpy(dst->pre_g_128, src->pre_g_128, size);
 239     }
 240 #endif
 241 }
 242
 243 static int secp256k1_ecmult_context_is_built(const secp256k1_ecmult_context *ctx) {
 244     return ctx->pre_g != NULL;
 245 }
 246
 247 static void secp256k1_ecmult_context_clear(secp256k1_ecmult_context *ctx) {
 248     free(ctx->pre_g);
 249 #ifdef USE_ENDOMORPHISM
 250     free(ctx->pre_g_128);
 251 #endif
 252     secp256k1_ecmult_context_init(ctx);
 253 }
 254
 255 /** Convert a number to WNAF notation. The number becomes represented by sum(2^i * wnaf[i], i=0..bits),
 256  *  with the following guarantees:
 257  *  - each wnaf[i] is either 0, or an odd integer between -(1<<(w-1) - 1) and (1<<(w-1) - 1)
 258  *  - two non-zero entries in wnaf are separated by at least w-1 zeroes.
 259  *  - the number of set values in wnaf is returned. This number is at most 256, and at most one more
 260  *    than the number of bits in the (absolute value) of the input.
 261  */
 262 static int secp256k1_ecmult_wnaf(int *wnaf, int len, const secp256k1_scalar *a, int w) {
 263     secp256k1_scalar s = *a;
 264     int last_set_bit = -1;
 265     int bit = 0;
 266     int sign = 1;
 267     int carry = 0;
 268
 269     VERIFY_CHECK(wnaf != NULL);
 270     VERIFY_CHECK(0 <= len && len <= 256);
 271     VERIFY_CHECK(a != NULL);
 272     VERIFY_CHECK(2 <= w && w <= 31);
 273
 274     memset(wnaf, 0, len * sizeof(wnaf[0]));
 275
 276     if (secp256k1_scalar_get_bits(&s, 255, 1)) {
 277         secp256k1_scalar_negate(&s, &s);
 278         sign = -1;
 279     }
 280
 281     while (bit < len) {
 282         int now;
 283         int word;
 284         if (secp256k1_scalar_get_bits(&s, bit, 1) == (unsigned int)carry) {
 285             bit++;
 286             continue;
 287         }
 288
 289         now = w;
 290         if (now > len - bit) {
 291             now = len - bit;
 292         }
 293
 294         word = secp256k1_scalar_get_bits_var(&s, bit, now) + carry;
 295
 296         carry = (word >> (w-1)) & 1;
 297         word -= carry << w;
 298
 299         wnaf[bit] = sign * word;
 300         last_set_bit = bit;
 301
 302         bit += now;
 303     }
 304 #ifdef VERIFY
 305     CHECK(carry == 0);
 306     while (bit < 256) {
 307         CHECK(secp256k1_scalar_get_bits(&s, bit++, 1) == 0);
 308     }
 309 #endif
 310     return last_set_bit + 1;
 311 }
 312
 313 struct secp256k1_strauss_point_state {
 314 #ifdef USE_ENDOMORPHISM
 315     secp256k1_scalar na_1, na_lam;
 316     int wnaf_na_1[130];
 317     int wnaf_na_lam[130];
 318     int bits_na_1;
 319     int bits_na_lam;
 320 #else
 321     int wnaf_na[256];
 322     int bits_na;
 323 #endif
 324     size_t input_pos;
 325 };
 326
 327 struct secp256k1_strauss_state {
 328     secp256k1_gej* prej;
 329     secp256k1_fe* zr;
 330     secp256k1_ge* pre_a;
 331 #ifdef USE_ENDOMORPHISM
 332     secp256k1_ge* pre_a_lam;
 333 #endif
 334     struct secp256k1_strauss_point_state* ps;
 335 };
 336
 337 static void secp256k1_ecmult_strauss_wnaf(const secp256k1_ecmult_context *ctx, const struct secp256k1_strauss_state *state, secp256k1_gej *r, int num, const secp256k1_gej *a, const secp256k1_scalar *na, const secp256k1_scalar *ng) {
 338     secp256k1_ge tmpa;
 339     secp256k1_fe Z;
 340 #ifdef USE_ENDOMORPHISM
 341     /* Splitted G factors. */
 342     secp256k1_scalar ng_1, ng_128;
 343     int wnaf_ng_1[129];
 344     int bits_ng_1 = 0;
 345     int wnaf_ng_128[129];
 346     int bits_ng_128 = 0;
 347 #else
 348     int wnaf_ng[256];
 349     int bits_ng = 0;
 350 #endif
 351     int i;
 352     int bits = 0;
 353     int np;
 354     int no = 0;
 355
 356     for (np = 0; np < num; ++np) {
 357         if (secp256k1_scalar_is_zero(&na[np]) || secp256k1_gej_is_infinity(&a[np])) {
 358             continue;
 359         }
 360         state->ps[no].input_pos = np;
 361 #ifdef USE_ENDOMORPHISM
 362         /* split na into na_1 and na_lam (where na = na_1 + na_lam*lambda, and na_1 and na_lam are ~128 bit) */
 363         secp256k1_scalar_split_lambda(&state->ps[no].na_1, &state->ps[no].na_lam, &na[np]);
 364
 365         /* build wnaf representation for na_1 and na_lam. */
 366         state->ps[no].bits_na_1   = secp256k1_ecmult_wnaf(state->ps[no].wnaf_na_1,   130, &state->ps[no].na_1,   WINDOW_A);
 367         state->ps[no].bits_na_lam = secp256k1_ecmult_wnaf(state->ps[no].wnaf_na_lam, 130, &state->ps[no].na_lam, WINDOW_A);
 368         VERIFY_CHECK(state->ps[no].bits_na_1 <= 130);
 369         VERIFY_CHECK(state->ps[no].bits_na_lam <= 130);
 370         if (state->ps[no].bits_na_1 > bits) {
 371             bits = state->ps[no].bits_na_1;
 372         }
 373         if (state->ps[no].bits_na_lam > bits) {
 374             bits = state->ps[no].bits_na_lam;
 375         }
 376 #else
 377         /* build wnaf representation for na. */
 378         state->ps[no].bits_na     = secp256k1_ecmult_wnaf(state->ps[no].wnaf_na,     256, &na[np],      WINDOW_A);
 379         if (state->ps[no].bits_na > bits) {
 380             bits = state->ps[no].bits_na;
 381         }
 382 #endif
 383         ++no;
 384     }
 385
 386     /* Calculate odd multiples of a.
 387      * All multiples are brought to the same Z 'denominator', which is stored
 388      * in Z. Due to secp256k1' isomorphism we can do all operations pretending
 389      * that the Z coordinate was 1, use affine addition formulae, and correct
 390      * the Z coordinate of the result once at the end.
 391      * The exception is the precomputed G table points, which are actually
 392      * affine. Compared to the base used for other points, they have a Z ratio
 393      * of 1/Z, so we can use secp256k1_gej_add_zinv_var, which uses the same
 394      * isomorphism to efficiently add with a known Z inverse.
 395      */
 396     if (no > 0) {
 397         /* Compute the odd multiples in Jacobian form. */
 398         secp256k1_ecmult_odd_multiples_table(ECMULT_TABLE_SIZE(WINDOW_A), state->prej, state->zr, &a[state->ps[0].input_pos]);
 399         for (np = 1; np < no; ++np) {
 400             secp256k1_gej tmp = a[state->ps[np].input_pos];
 401 #ifdef VERIFY
 402             secp256k1_fe_normalize_var(&(state->prej[(np - 1) * ECMULT_TABLE_SIZE(WINDOW_A) + ECMULT_TABLE_SIZE(WINDOW_A) - 1].z));
 403 #endif
 404             secp256k1_gej_rescale(&tmp, &(state->prej[(np - 1) * ECMULT_TABLE_SIZE(WINDOW_A) + ECMULT_TABLE_SIZE(WINDOW_A) - 1].z));
 405             secp256k1_ecmult_odd_multiples_table(ECMULT_TABLE_SIZE(WINDOW_A), state->prej + np * ECMULT_TABLE_SIZE(WINDOW_A), state->zr + np * ECMULT_TABLE_SIZE(WINDOW_A), &tmp);
 406             secp256k1_fe_mul(state->zr + np * ECMULT_TABLE_SIZE(WINDOW_A), state->zr + np * ECMULT_TABLE_SIZE(WINDOW_A), &(a[state->ps[np].input_pos].z));
 407         }
 408         /* Bring them to the same Z denominator. */
 409         secp256k1_ge_globalz_set_table_gej(ECMULT_TABLE_SIZE(WINDOW_A) * no, state->pre_a, &Z, state->prej, state->zr);
 410     } else {
 411         secp256k1_fe_set_int(&Z, 1);
 412     }
 413
 414 #ifdef USE_ENDOMORPHISM
 415     for (np = 0; np < no; ++np) {
 416         for (i = 0; i < ECMULT_TABLE_SIZE(WINDOW_A); i++) {
 417             secp256k1_ge_mul_lambda(&state->pre_a_lam[np * ECMULT_TABLE_SIZE(WINDOW_A) + i], &state->pre_a[np * ECMULT_TABLE_SIZE(WINDOW_A) + i]);
 418         }
 419     }
 420
 421     if (ng) {
 422         /* split ng into ng_1 and ng_128 (where gn = gn_1 + gn_128*2^128, and gn_1 and gn_128 are ~128 bit) */
 423         secp256k1_scalar_split_128(&ng_1, &ng_128, ng);
 424
 425         /* Build wnaf representation for ng_1 and ng_128 */
 426         bits_ng_1   = secp256k1_ecmult_wnaf(wnaf_ng_1,   129, &ng_1,   WINDOW_G);
 427         bits_ng_128 = secp256k1_ecmult_wnaf(wnaf_ng_128, 129, &ng_128, WINDOW_G);
 428         if (bits_ng_1 > bits) {
 429             bits = bits_ng_1;
 430         }
 431         if (bits_ng_128 > bits) {
 432             bits = bits_ng_128;
 433         }
 434     }
 435 #else
 436     if (ng) {
 437         bits_ng     = secp256k1_ecmult_wnaf(wnaf_ng,     256, ng,      WINDOW_G);
 438         if (bits_ng > bits) {
 439             bits = bits_ng;
 440         }
 441     }
 442 #endif
 443
 444     secp256k1_gej_set_infinity(r);
 445
 446     for (i = bits - 1; i >= 0; i--) {
 447         int n;
 448         secp256k1_gej_double_var(r, r, NULL);
 449 #ifdef USE_ENDOMORPHISM
 450         for (np = 0; np < no; ++np) {
 451             if (i < state->ps[np].bits_na_1 && (n = state->ps[np].wnaf_na_1[i])) {
 452                 ECMULT_TABLE_GET_GE(&tmpa, state->pre_a + np * ECMULT_TABLE_SIZE(WINDOW_A), n, WINDOW_A);
 453                 secp256k1_gej_add_ge_var(r, r, &tmpa, NULL);
 454             }
 455             if (i < state->ps[np].bits_na_lam && (n = state->ps[np].wnaf_na_lam[i])) {
 456                 ECMULT_TABLE_GET_GE(&tmpa, state->pre_a_lam + np * ECMULT_TABLE_SIZE(WINDOW_A), n, WINDOW_A);
 457                 secp256k1_gej_add_ge_var(r, r, &tmpa, NULL);
 458             }
 459         }
 460         if (i < bits_ng_1 && (n = wnaf_ng_1[i])) {
 461             ECMULT_TABLE_GET_GE_STORAGE(&tmpa, *ctx->pre_g, n, WINDOW_G);
 462             secp256k1_gej_add_zinv_var(r, r, &tmpa, &Z);
 463         }
 464         if (i < bits_ng_128 && (n = wnaf_ng_128[i])) {
 465             ECMULT_TABLE_GET_GE_STORAGE(&tmpa, *ctx->pre_g_128, n, WINDOW_G);
 466             secp256k1_gej_add_zinv_var(r, r, &tmpa, &Z);
 467         }
 468 #else
 469         for (np = 0; np < no; ++np) {
 470             if (i < state->ps[np].bits_na && (n = state->ps[np].wnaf_na[i])) {
 471                 ECMULT_TABLE_GET_GE(&tmpa, state->pre_a + np * ECMULT_TABLE_SIZE(WINDOW_A), n, WINDOW_A);
 472                 secp256k1_gej_add_ge_var(r, r, &tmpa, NULL);
 473             }
 474         }
 475         if (i < bits_ng && (n = wnaf_ng[i])) {
 476             ECMULT_TABLE_GET_GE_STORAGE(&tmpa, *ctx->pre_g, n, WINDOW_G);
 477             secp256k1_gej_add_zinv_var(r, r, &tmpa, &Z);
 478         }
 479 #endif
 480     }
 481
 482     if (!r->infinity) {
 483         secp256k1_fe_mul(&r->z, &r->z, &Z);
 484     }
 485 }
 486
 487 static void secp256k1_ecmult(const secp256k1_ecmult_context *ctx, secp256k1_gej *r, const secp256k1_gej *a, const secp256k1_scalar *na, const secp256k1_scalar *ng) {
 488     secp256k1_gej prej[ECMULT_TABLE_SIZE(WINDOW_A)];
 489     secp256k1_fe zr[ECMULT_TABLE_SIZE(WINDOW_A)];
 490     secp256k1_ge pre_a[ECMULT_TABLE_SIZE(WINDOW_A)];
 491     struct secp256k1_strauss_point_state ps[1];
 492 #ifdef USE_ENDOMORPHISM
 493     secp256k1_ge pre_a_lam[ECMULT_TABLE_SIZE(WINDOW_A)];
 494 #endif
 495     struct secp256k1_strauss_state state;
 496
 497     state.prej = prej;
 498     state.zr = zr;
 499     state.pre_a = pre_a;
 500 #ifdef USE_ENDOMORPHISM
 501     state.pre_a_lam = pre_a_lam;
 502 #endif
 503     state.ps = ps;
 504     secp256k1_ecmult_strauss_wnaf(ctx, &state, r, 1, a, na, ng);
 505 }
 506
 507 static size_t secp256k1_strauss_scratch_size(size_t n_points) {
 508 #ifdef USE_ENDOMORPHISM
 509     static const size_t point_size = (2 * sizeof(secp256k1_ge) + sizeof(secp256k1_gej) + sizeof(secp256k1_fe)) * ECMULT_TABLE_SIZE(WINDOW_A) + sizeof(struct secp256k1_strauss_point_state) + sizeof(secp256k1_gej) + sizeof(secp256k1_scalar);
 510 #else
 511     static const size_t point_size = (sizeof(secp256k1_ge) + sizeof(secp256k1_gej) + sizeof(secp256k1_fe)) * ECMULT_TABLE_SIZE(WINDOW_A) + sizeof(struct secp256k1_strauss_point_state) + sizeof(secp256k1_gej) + sizeof(secp256k1_scalar);
 512 #endif
 513     return n_points*point_size;
 514 }
 515
 516 static int secp256k1_ecmult_strauss_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) {
 517     secp256k1_gej* points;
 518     secp256k1_scalar* scalars;
 519     struct secp256k1_strauss_state state;
 520     size_t i;
 521
 522     secp256k1_gej_set_infinity(r);
 523     if (inp_g_sc == NULL && n_points == 0) {
 524         return 1;
 525     }
 526
 527     if (!secp256k1_scratch_resize(scratch, secp256k1_strauss_scratch_size(n_points), STRAUSS_SCRATCH_OBJECTS)) {
 528         return 0;
 529     }
 530     secp256k1_scratch_reset(scratch);
 531     points = (secp256k1_gej*)secp256k1_scratch_alloc(scratch, n_points * sizeof(secp256k1_gej));
 532     scalars = (secp256k1_scalar*)secp256k1_scratch_alloc(scratch, n_points * sizeof(secp256k1_scalar));
 533     state.prej = (secp256k1_gej*)secp256k1_scratch_alloc(scratch, n_points * ECMULT_TABLE_SIZE(WINDOW_A) * sizeof(secp256k1_gej));
 534     state.zr = (secp256k1_fe*)secp256k1_scratch_alloc(scratch, n_points * ECMULT_TABLE_SIZE(WINDOW_A) * sizeof(secp256k1_fe));
 535 #ifdef USE_ENDOMORPHISM
 536     state.pre_a = (secp256k1_ge*)secp256k1_scratch_alloc(scratch, n_points * 2 * ECMULT_TABLE_SIZE(WINDOW_A) * sizeof(secp256k1_ge));
 537     state.pre_a_lam = state.pre_a + n_points * ECMULT_TABLE_SIZE(WINDOW_A);
 538 #else
 539     state.pre_a = (secp256k1_ge*)secp256k1_scratch_alloc(scratch, n_points * ECMULT_TABLE_SIZE(WINDOW_A) * sizeof(secp256k1_ge));
 540 #endif
 541     state.ps = (struct secp256k1_strauss_point_state*)secp256k1_scratch_alloc(scratch, n_points * sizeof(struct secp256k1_strauss_point_state));
 542
 543     for (i = 0; i < n_points; i++) {
 544         secp256k1_ge point;
 545         if (!cb(&scalars[i], &point, i+cb_offset, cbdata)) return 0;
 546         secp256k1_gej_set_ge(&points[i], &point);
 547     }
 548     secp256k1_ecmult_strauss_wnaf(ctx, &state, r, n_points, points, scalars, inp_g_sc);
 549     return 1;
 550 }
 551
 552 /* Wrapper for secp256k1_ecmult_multi_func interface */
 553 static int secp256k1_ecmult_strauss_batch_single(const secp256k1_ecmult_context *actx, secp256k1_scratch *scratch, secp256k1_gej *r, const secp256k1_scalar *inp_g_sc, secp256k1_ecmult_multi_callback cb, void *cbdata, size_t n) {
 554     return secp256k1_ecmult_strauss_batch(actx, scratch, r, inp_g_sc, cb, cbdata, n, 0);
 555 }
 556
 557 static size_t secp256k1_strauss_max_points(secp256k1_scratch *scratch) {
 558     return secp256k1_scratch_max_allocation(scratch, STRAUSS_SCRATCH_OBJECTS) / secp256k1_strauss_scratch_size(1);
 559 }
 560
 561 /** Convert a number to WNAF notation.
 562  *  The number becomes represented by sum(2^{wi} * wnaf[i], i=0..WNAF_SIZE(w)+1) - return_val.
 563  *  It has the following guarantees:
 564  *  - each wnaf[i] is either 0 or an odd integer between -(1 << w) and (1 << w)
 565  *  - the number of words set is always WNAF_SIZE(w)
 566  *  - the returned skew is 0 or 1
 567  */
 568 static int secp256k1_wnaf_fixed(int *wnaf, const secp256k1_scalar *s, int w) {
 569     int skew = 0;
 570     int pos = 1;
 571     const secp256k1_scalar *work = s;
 572
 573     if (secp256k1_scalar_is_zero(s)) {
 574         for (pos = 0; pos < WNAF_SIZE(w); pos++) {
 575             wnaf[pos] = 0;
 576         }
 577         return 0;
 578     }
 579
 580     if (secp256k1_scalar_is_even(s)) {
 581         skew = 1;
 582     }
 583
 584     wnaf[0] = secp256k1_scalar_get_bits_var(work, 0, w) + skew;
 585
 586     while (pos * w < WNAF_BITS) {
 587         int now = w;
 588         int val;
 589         if (now + pos * w > WNAF_BITS) {
 590             now = WNAF_BITS - pos * w;
 591         }
 592         val = secp256k1_scalar_get_bits_var(work, pos * w, now);
 593         if ((val & 1) == 0) {
 594             wnaf[pos - 1] -= (1 << w);
 595             wnaf[pos] = (val + 1);
 596         } else {
 597             wnaf[pos] = val;
 598         }
 599         /* Set a coefficient to zero if it is 1 or -1 and the proceeding digit
 600          * is strictly negative or strictly positive respectively. Only change
 601          * coefficients at previous positions because above code assumes that
 602          * wnaf[pos - 1] is odd.
 603          */
 604         if (pos >= 2 && ((wnaf[pos - 1] == 1 && wnaf[pos - 2] < 0) || (wnaf[pos - 1] == -1 && wnaf[pos - 2] > 0))) {
 605             if (wnaf[pos - 1] == 1) {
 606                 wnaf[pos - 2] += 1 << w;
 607             } else {
 608                 wnaf[pos - 2] -= 1 << w;
 609             }
 610             wnaf[pos - 1] = 0;
 611         }
 612         ++pos;
 613     }
 614     VERIFY_CHECK(pos == WNAF_SIZE(w));
 615
 616     return skew;
 617 }
 618
 619 struct secp256k1_pippenger_point_state {
 620     int skew_na;
 621     size_t input_pos;
 622 };
 623
 624 struct secp256k1_pippenger_state {
 625     int *wnaf_na;
 626     struct secp256k1_pippenger_point_state* ps;
 627 };
 628
 629 /*
 630  * pippenger_wnaf computes the result of a multi-point multiplication as
 631  * follows: The scalars are brought into wnaf with n_wnaf elements each. Then
 632  * for every i < n_wnaf, first each point is added to a "bucket" corresponding
 633  * to the point's wnaf[i]. Second, the buckets are added together such that
 634  * r += 1*bucket[0] + 3*bucket[1] + 5*bucket[2] + ...
 635  */
 636 static int secp256k1_ecmult_pippenger_wnaf(secp256k1_gej *buckets, int bucket_window, struct secp256k1_pippenger_state *state, secp256k1_gej *r, secp256k1_scalar *sc, secp256k1_ge *pt, size_t num) {
 637     size_t n_wnaf = WNAF_SIZE(bucket_window+1);
 638     size_t np;
 639     size_t no = 0;
 640     int i;
 641     int j;
 642
 643     for (np = 0; np < num; ++np) {
 644         if (secp256k1_scalar_is_zero(&sc[np]) || secp256k1_ge_is_infinity(&pt[np])) {
 645             continue;
 646         }
 647         state->ps[no].input_pos = np;
 648         state->ps[no].skew_na = secp256k1_wnaf_fixed(&state->wnaf_na[no*n_wnaf], &sc[np], bucket_window+1);
 649         no++;
 650     }
 651     secp256k1_gej_set_infinity(r);
 652
 653     if (no == 0) {
 654         return 1;
 655     }
 656
 657     for (i = n_wnaf - 1; i >= 0; i--) {
 658         secp256k1_gej running_sum;
 659
 660         for(j = 0; j < ECMULT_TABLE_SIZE(bucket_window+2); j++) {
 661             secp256k1_gej_set_infinity(&buckets[j]);
 662         }
 663
 664         for (np = 0; np < no; ++np) {
 665             int n = state->wnaf_na[np*n_wnaf + i];
 666             struct secp256k1_pippenger_point_state point_state = state->ps[np];
 667             secp256k1_ge tmp;
 668             int idx;
 669
 670             if (i == 0) {
 671                 /* correct for wnaf skew */
 672                 int skew = point_state.skew_na;
 673                 if (skew) {
 674                     secp256k1_ge_neg(&tmp, &pt[point_state.input_pos]);
 675                     secp256k1_gej_add_ge_var(&buckets[0], &buckets[0], &tmp, NULL);
 676                 }
 677             }
 678             if (n > 0) {
 679                 idx = (n - 1)/2;
 680                 secp256k1_gej_add_ge_var(&buckets[idx], &buckets[idx], &pt[point_state.input_pos], NULL);
 681             } else if (n < 0) {
 682                 idx = -(n + 1)/2;
 683                 secp256k1_ge_neg(&tmp, &pt[point_state.input_pos]);
 684                 secp256k1_gej_add_ge_var(&buckets[idx], &buckets[idx], &tmp, NULL);
 685             }
 686         }
 687
 688         for(j = 0; j < bucket_window; j++) {
 689             secp256k1_gej_double_var(r, r, NULL);
 690         }
 691
 692         secp256k1_gej_set_infinity(&running_sum);
 693         /* Accumulate the sum: bucket[0] + 3*bucket[1] + 5*bucket[2] + 7*bucket[3] + ...
 694          *                   = bucket[0] +   bucket[1] +   bucket[2] +   bucket[3] + ...
 695          *                   +         2 *  (bucket[1] + 2*bucket[2] + 3*bucket[3] + ...)
 696          * using an intermediate running sum:
 697          * running_sum = bucket[0] +   bucket[1] +   bucket[2] + ...
 698          *
 699          * The doubling is done implicitly by deferring the final window doubling (of 'r').
 700          */
 701         for(j = ECMULT_TABLE_SIZE(bucket_window+2) - 1; j > 0; j--) {
 702             secp256k1_gej_add_var(&running_sum, &running_sum, &buckets[j], NULL);
 703             secp256k1_gej_add_var(r, r, &running_sum, NULL);
 704         }
 705
 706         secp256k1_gej_add_var(&running_sum, &running_sum, &buckets[0], NULL);
 707         secp256k1_gej_double_var(r, r, NULL);
 708         secp256k1_gej_add_var(r, r, &running_sum, NULL);
 709     }
 710     return 1;
 711 }
 712
 713 /**
 714  * Returns optimal bucket_window (number of bits of a scalar represented by a
 715  * set of buckets) for a given number of points.
 716  */
 717 static int secp256k1_pippenger_bucket_window(size_t n) {
 718 #ifdef USE_ENDOMORPHISM
 719     if (n <= 1) {
 720         return 1;
 721     } else if (n <= 4) {
 722         return 2;
 723     } else if (n <= 20) {
 724         return 3;
 725     } else if (n <= 57) {
 726         return 4;
 727     } else if (n <= 136) {
 728         return 5;
 729     } else if (n <= 235) {
 730         return 6;
 731     } else if (n <= 1260) {
 732         return 7;
 733     } else if (n <= 4420) {
 734         return 9;
 735     } else if (n <= 7880) {
 736         return 10;
 737     } else if (n <= 16050) {
 738         return 11;
 739     } else {
 740         return PIPPENGER_MAX_BUCKET_WINDOW;
 741     }
 742 #else
 743     if (n <= 1) {
 744         return 1;
 745     } else if (n <= 11) {
 746         return 2;
 747     } else if (n <= 45) {
 748         return 3;
 749     } else if (n <= 100) {
 750         return 4;
 751     } else if (n <= 275) {
 752         return 5;
 753     } else if (n <= 625) {
 754         return 6;
 755     } else if (n <= 1850) {
 756         return 7;
 757     } else if (n <= 3400) {
 758         return 8;
 759     } else if (n <= 9630) {
 760         return 9;
 761     } else if (n <= 17900) {
 762         return 10;
 763     } else if (n <= 32800) {
 764         return 11;
 765     } else {
 766         return PIPPENGER_MAX_BUCKET_WINDOW;
 767     }
 768 #endif
 769 }
 770
 771 /**
 772  * Returns the maximum optimal number of points for a bucket_window.
 773  */
 774 static size_t secp256k1_pippenger_bucket_window_inv(int bucket_window) {
 775     switch(bucket_window) {
 776 #ifdef USE_ENDOMORPHISM
 777         case 1: return 1;
 778         case 2: return 4;
 779         case 3: return 20;
 780         case 4: return 57;
 781         case 5: return 136;
 782         case 6: return 235;
 783         case 7: return 1260;
 784         case 8: return 1260;
 785         case 9: return 4420;
 786         case 10: return 7880;
 787         case 11: return 16050;
 788         case PIPPENGER_MAX_BUCKET_WINDOW: return SIZE_MAX;
 789 #else
 790         case 1: return 1;
 791         case 2: return 11;
 792         case 3: return 45;
 793         case 4: return 100;
 794         case 5: return 275;
 795         case 6: return 625;
 796         case 7: return 1850;
 797         case 8: return 3400;
 798         case 9: return 9630;
 799         case 10: return 17900;
 800         case 11: return 32800;
 801         case PIPPENGER_MAX_BUCKET_WINDOW: return SIZE_MAX;
 802 #endif
 803     }
 804     return 0;
 805 }
 806
 807
 808 #ifdef USE_ENDOMORPHISM
 809 SECP256K1_INLINE static void secp256k1_ecmult_endo_split(secp256k1_scalar *s1, secp256k1_scalar *s2, secp256k1_ge *p1, secp256k1_ge *p2) {
 810     secp256k1_scalar tmp = *s1;
 811     secp256k1_scalar_split_lambda(s1, s2, &tmp);
 812     secp256k1_ge_mul_lambda(p2, p1);
 813
 814     if (secp256k1_scalar_is_high(s1)) {
 815         secp256k1_scalar_negate(s1, s1);
 816         secp256k1_ge_neg(p1, p1);
 817     }
 818     if (secp256k1_scalar_is_high(s2)) {
 819         secp256k1_scalar_negate(s2, s2);
 820         secp256k1_ge_neg(p2, p2);
 821     }
 822 }
 823 #endif
 824
 825 /**
 826  * Returns the scratch size required for a given number of points (excluding
 827  * base point G) without considering alignment.
 828  */
 829 static size_t secp256k1_pippenger_scratch_size(size_t n_points, int bucket_window) {
 830 #ifdef USE_ENDOMORPHISM
 831     size_t entries = 2*n_points + 2;
 832 #else
 833     size_t entries = n_points + 1;
 834 #endif
 835     size_t entry_size = sizeof(secp256k1_ge) + sizeof(secp256k1_scalar) + sizeof(struct secp256k1_pippenger_point_state) + (WNAF_SIZE(bucket_window+1)+1)*sizeof(int);
 836     return ((1<<bucket_window) * sizeof(secp256k1_gej) + sizeof(struct secp256k1_pippenger_state) + entries * entry_size);
 837 }
 838
 839 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) {
 840     /* Use 2(n+1) with the endomorphism, n+1 without, when calculating batch
 841      * sizes. The reason for +1 is that we add the G scalar to the list of
 842      * other scalars. */
 843 #ifdef USE_ENDOMORPHISM
 844     size_t entries = 2*n_points + 2;
 845 #else
 846     size_t entries = n_points + 1;
 847 #endif
 848     secp256k1_ge *points;
 849     secp256k1_scalar *scalars;
 850     secp256k1_gej *buckets;
 851     struct secp256k1_pippenger_state *state_space;
 852     size_t idx = 0;
 853     size_t point_idx = 0;
 854     int i, j;
 855     int bucket_window;
 856
 857     (void)ctx;
 858     secp256k1_gej_set_infinity(r);
 859     if (inp_g_sc == NULL && n_points == 0) {
 860         return 1;
 861     }
 862
 863     bucket_window = secp256k1_pippenger_bucket_window(n_points);
 864     if (!secp256k1_scratch_resize(scratch, secp256k1_pippenger_scratch_size(n_points, bucket_window), PIPPENGER_SCRATCH_OBJECTS)) {
 865         return 0;
 866     }
 867     secp256k1_scratch_reset(scratch);
 868     points = (secp256k1_ge *) secp256k1_scratch_alloc(scratch, entries * sizeof(*points));
 869     scalars = (secp256k1_scalar *) secp256k1_scratch_alloc(scratch, entries * sizeof(*scalars));
 870     state_space = (struct secp256k1_pippenger_state *) secp256k1_scratch_alloc(scratch, sizeof(*state_space));
 871     state_space->ps = (struct secp256k1_pippenger_point_state *) secp256k1_scratch_alloc(scratch, entries * sizeof(*state_space->ps));
 872     state_space->wnaf_na = (int *) secp256k1_scratch_alloc(scratch, entries*(WNAF_SIZE(bucket_window+1)) * sizeof(int));
 873     buckets = (secp256k1_gej *) secp256k1_scratch_alloc(scratch, (1<<bucket_window) * sizeof(*buckets));
 874
 875     if (inp_g_sc != NULL) {
 876         scalars[0] = *inp_g_sc;
 877         points[0] = secp256k1_ge_const_g;
 878         idx++;
 879 #ifdef USE_ENDOMORPHISM
 880         secp256k1_ecmult_endo_split(&scalars[0], &scalars[1], &points[0], &points[1]);
 881         idx++;
 882 #endif
 883     }
 884
 885     while (point_idx < n_points) {
 886         if (!cb(&scalars[idx], &points[idx], point_idx + cb_offset, cbdata)) {
 887             return 0;
 888         }
 889         idx++;
 890 #ifdef USE_ENDOMORPHISM
 891         secp256k1_ecmult_endo_split(&scalars[idx - 1], &scalars[idx], &points[idx - 1], &points[idx]);
 892         idx++;
 893 #endif
 894         point_idx++;
 895     }
 896
 897     secp256k1_ecmult_pippenger_wnaf(buckets, bucket_window, state_space, r, scalars, points, idx);
 898
 899     /* Clear data */
 900     for(i = 0; (size_t)i < idx; i++) {
 901         secp256k1_scalar_clear(&scalars[i]);
 902         state_space->ps[i].skew_na = 0;
 903         for(j = 0; j < WNAF_SIZE(bucket_window+1); j++) {
 904             state_space->wnaf_na[i * WNAF_SIZE(bucket_window+1) + j] = 0;
 905         }
 906     }
 907     for(i = 0; i < 1<<bucket_window; i++) {
 908         secp256k1_gej_clear(&buckets[i]);
 909     }
 910     return 1;
 911 }
 912
 913 /* Wrapper for secp256k1_ecmult_multi_func interface */
 914 static int secp256k1_ecmult_pippenger_batch_single(const secp256k1_ecmult_context *actx, secp256k1_scratch *scratch, secp256k1_gej *r, const secp256k1_scalar *inp_g_sc, secp256k1_ecmult_multi_callback cb, void *cbdata, size_t n) {
 915     return secp256k1_ecmult_pippenger_batch(actx, scratch, r, inp_g_sc, cb, cbdata, n, 0);
 916 }
 917
 918 /**
 919  * Returns the maximum number of points in addition to G that can be used with
 920  * a given scratch space. The function ensures that fewer points may also be
 921  * used.
 922  */
 923 static size_t secp256k1_pippenger_max_points(secp256k1_scratch *scratch) {
 924     size_t max_alloc = secp256k1_scratch_max_allocation(scratch, PIPPENGER_SCRATCH_OBJECTS);
 925     int bucket_window;
 926     size_t res = 0;
 927
 928     for (bucket_window = 1; bucket_window <= PIPPENGER_MAX_BUCKET_WINDOW; bucket_window++) {
 929         size_t n_points;
 930         size_t max_points = secp256k1_pippenger_bucket_window_inv(bucket_window);
 931         size_t space_for_points;
 932         size_t space_overhead;
 933         size_t entry_size = sizeof(secp256k1_ge) + sizeof(secp256k1_scalar) + sizeof(struct secp256k1_pippenger_point_state) + (WNAF_SIZE(bucket_window+1)+1)*sizeof(int);
 934
 935 #ifdef USE_ENDOMORPHISM
 936         entry_size = 2*entry_size;
 937 #endif
 938         space_overhead = ((1<<bucket_window) * sizeof(secp256k1_gej) + entry_size + sizeof(struct secp256k1_pippenger_state));
 939         if (space_overhead > max_alloc) {
 940             break;
 941         }
 942         space_for_points = max_alloc - space_overhead;
 943
 944         n_points = space_for_points/entry_size;
 945         n_points = n_points > max_points ? max_points : n_points;
 946         if (n_points > res) {
 947             res = n_points;
 948         }
 949         if (n_points < max_points) {
 950             /* A larger bucket_window may support even more points. But if we
 951              * would choose that then the caller couldn't safely use any number
 952              * smaller than what this function returns */
 953             break;
 954         }
 955     }
 956     return res;
 957 }
 958
 959 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);
 960 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) {
 961     size_t i;
 962
 963     int (*f)(const secp256k1_ecmult_context*, secp256k1_scratch*, secp256k1_gej*, const secp256k1_scalar*, secp256k1_ecmult_multi_callback cb, void*, size_t, size_t);
 964     size_t max_points;
 965     size_t n_batches;
 966     size_t n_batch_points;
 967
 968     secp256k1_gej_set_infinity(r);
 969     if (inp_g_sc == NULL && n == 0) {
 970         return 1;
 971     } else if (n == 0) {
 972         secp256k1_scalar szero;
 973         secp256k1_scalar_set_int(&szero, 0);
 974         secp256k1_ecmult(ctx, r, r, &szero, inp_g_sc);
 975         return 1;
 976     }
 977
 978     max_points = secp256k1_pippenger_max_points(scratch);
 979     if (max_points == 0) {
 980         return 0;
 981     } else if (max_points > ECMULT_MAX_POINTS_PER_BATCH) {
 982         max_points = ECMULT_MAX_POINTS_PER_BATCH;
 983     }
 984     n_batches = (n+max_points-1)/max_points;
 985     n_batch_points = (n+n_batches-1)/n_batches;
 986
 987     if (n_batch_points >= ECMULT_PIPPENGER_THRESHOLD) {
 988         f = secp256k1_ecmult_pippenger_batch;
 989     } else {
 990         max_points = secp256k1_strauss_max_points(scratch);
 991         if (max_points == 0) {
 992             return 0;
 993         }
 994         n_batches = (n+max_points-1)/max_points;
 995         n_batch_points = (n+n_batches-1)/n_batches;
 996         f = secp256k1_ecmult_strauss_batch;
 997     }
 998     for(i = 0; i < n_batches; i++) {
 999         size_t nbp = n < n_batch_points ? n : n_batch_points;
1000         size_t offset = n_batch_points*i;
1001         secp256k1_gej tmp;
1002         if (!f(ctx, scratch, &tmp, i == 0 ? inp_g_sc : NULL, cb, cbdata, nbp, offset)) {
1003             return 0;
1004         }
1005         secp256k1_gej_add_var(r, r, &tmp, NULL);
1006         n -= nbp;
1007     }
1008     return 1;
1009 }
1010
1011 #endif /* SECP256K1_ECMULT_IMPL_H */