ecmult_impl.h File Reference

#include <string.h>
#include <stdint.h>
#include "group.h"
#include "scalar.h"
#include "ecmult.h"

Include dependency graph for ecmult_impl.h:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
struct	secp256k1_strauss_point_state
struct	secp256k1_strauss_state
struct	secp256k1_pippenger_point_state
struct	secp256k1_pippenger_state

Macros
#define	WINDOW_A   5
#define	WINDOW_G   16
	larger numbers may result in slightly better performance, at the cost of exponentially larger precomputed tables. More...
#define	WNAF_BITS   256
#define	WNAF_SIZE_BITS(bits, w)   (((bits) + (w) - 1) / (w))
#define	WNAF_SIZE(w)   WNAF_SIZE_BITS(WNAF_BITS, w)
#define	ECMULT_TABLE_SIZE(w)   (1 << ((w)-2))
	The number of entries a table with precomputed multiples needs to have. More...
#define	PIPPENGER_SCRATCH_OBJECTS   6
#define	STRAUSS_SCRATCH_OBJECTS   6
#define	PIPPENGER_MAX_BUCKET_WINDOW   12
#define	ECMULT_PIPPENGER_THRESHOLD   160
#define	ECMULT_MAX_POINTS_PER_BATCH   10000000
#define	ECMULT_TABLE_GET_GE(r, pre, n, w)
	The following two macro retrieves a particular odd multiple from a table of precomputed multiples. More...
#define	ECMULT_TABLE_GET_GE_STORAGE(r, pre, n, w)

Typedefs
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)

Functions
static void	secp256k1_ecmult_odd_multiples_table (int n, secp256k1_gej *prej, secp256k1_fe *zr, const secp256k1_gej *a)
	Fill a table 'prej' with precomputed odd multiples of a. More...
static void	secp256k1_ecmult_odd_multiples_table_globalz_windowa (secp256k1_ge *pre, secp256k1_fe *globalz, const secp256k1_gej *a)
	Fill a table 'pre' with precomputed odd multiples of a. More...
static void	secp256k1_ecmult_odd_multiples_table_storage_var (const int n, secp256k1_ge_storage *pre, const secp256k1_gej *a)
static void	secp256k1_ecmult_context_init (secp256k1_ecmult_context *ctx)
static void	secp256k1_ecmult_context_build (secp256k1_ecmult_context *ctx, const secp256k1_callback *cb)
static void	secp256k1_ecmult_context_clone (secp256k1_ecmult_context *dst, const secp256k1_ecmult_context *src, const secp256k1_callback *cb)
static int	secp256k1_ecmult_context_is_built (const secp256k1_ecmult_context *ctx)
static void	secp256k1_ecmult_context_clear (secp256k1_ecmult_context *ctx)
static int	secp256k1_ecmult_wnaf (int *wnaf, int len, const secp256k1_scalar *a, int w)
	Convert a number to WNAF notation. More...
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)
static void	secp256k1_ecmult (const secp256k1_ecmult_context *ctx, secp256k1_gej *r, const secp256k1_gej *a, const secp256k1_scalar *na, const secp256k1_scalar *ng)
static size_t	secp256k1_strauss_scratch_size (size_t n_points)
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)
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)
static size_t	secp256k1_strauss_max_points (secp256k1_scratch *scratch)
static int	secp256k1_wnaf_fixed (int *wnaf, const secp256k1_scalar *s, int w)
	Convert a number to WNAF notation. More...
static int	secp256k1_ecmult_pippenger_wnaf (secp256k1_gej *buckets, int bucket_window, struct secp256k1_pippenger_state *state, secp256k1_gej *r, const secp256k1_scalar *sc, const secp256k1_ge *pt, size_t num)
static int	secp256k1_pippenger_bucket_window (size_t n)
	Returns optimal bucket_window (number of bits of a scalar represented by a set of buckets) for a given number of points. More...
static size_t	secp256k1_pippenger_bucket_window_inv (int bucket_window)
	Returns the maximum optimal number of points for a bucket_window. More...
static size_t	secp256k1_pippenger_scratch_size (size_t n_points, int bucket_window)
	Returns the scratch size required for a given number of points (excluding base point G) without considering alignment. More...
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_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)
static size_t	secp256k1_pippenger_max_points (secp256k1_scratch *scratch)
	Returns the maximum number of points in addition to G that can be used with a given scratch space. More...
static int	secp256k1_ecmult_multi_simple_var (const secp256k1_ecmult_context *ctx, secp256k1_gej *r, const secp256k1_scalar *inp_g_sc, secp256k1_ecmult_multi_callback cb, void *cbdata, size_t n_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)
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)

Macro Definition Documentation

ECMULT_MAX_POINTS_PER_BATCH

#define ECMULT_MAX_POINTS_PER_BATCH   10000000

Definition at line 72 of file ecmult_impl.h.

Referenced by secp256k1_ecmult_multi_batch_size_helper(), and test_ecmult_multi_batch_size_helper().

ECMULT_PIPPENGER_THRESHOLD

#define ECMULT_PIPPENGER_THRESHOLD   160

Definition at line 66 of file ecmult_impl.h.

Referenced by secp256k1_ecmult_multi_var(), and test_ecmult_multi_batching().

ECMULT_TABLE_GET_GE

#define ECMULT_TABLE_GET_GE	(		r,
			pre,
			n,
			w
	)

Value:

do { \
    VERIFY_CHECK(((n) & 1) == 1); \
    VERIFY_CHECK((n) >= -((1 << ((w)-1)) - 1)); \
    VERIFY_CHECK((n) <=  ((1 << ((w)-1)) - 1)); \
    if ((n) > 0) { \
        *(r) = (pre)[((n)-1)/2]; \
    } else { \
        *(r) = (pre)[(-(n)-1)/2]; \
        secp256k1_fe_negate(&((r)->y), &((r)->y), 1); \
    } \
} while(0)

The following two macro retrieves a particular odd multiple from a table of precomputed multiples.

Definition at line 273 of file ecmult_impl.h.

Referenced by secp256k1_ecmult_strauss_wnaf().

ECMULT_TABLE_GET_GE_STORAGE

#define ECMULT_TABLE_GET_GE_STORAGE	(		r,
			pre,
			n,
			w
	)

Value:

do { \
    VERIFY_CHECK(((n) & 1) == 1); \
    VERIFY_CHECK((n) >= -((1 << ((w)-1)) - 1)); \
    VERIFY_CHECK((n) <=  ((1 << ((w)-1)) - 1)); \
    if ((n) > 0) { \
        secp256k1_ge_from_storage((r), &(pre)[((n)-1)/2]); \
    } else { \
        secp256k1_ge_from_storage((r), &(pre)[(-(n)-1)/2]); \
        secp256k1_fe_negate(&((r)->y), &((r)->y), 1); \
    } \
} while(0)

Definition at line 285 of file ecmult_impl.h.

Referenced by secp256k1_ecmult_strauss_wnaf().

ECMULT_TABLE_SIZE

#define ECMULT_TABLE_SIZE

(

w

)

(1 << ((w)-2))

The number of entries a table with precomputed multiples needs to have.

Definition at line 54 of file ecmult_impl.h.

Referenced by secp256k1_ecmult(), secp256k1_ecmult_const(), secp256k1_ecmult_context_build(), secp256k1_ecmult_context_clone(), secp256k1_ecmult_odd_multiples_table_globalz_windowa(), secp256k1_ecmult_pippenger_wnaf(), secp256k1_ecmult_strauss_batch(), secp256k1_ecmult_strauss_wnaf(), and secp256k1_strauss_scratch_size().

PIPPENGER_MAX_BUCKET_WINDOW

#define PIPPENGER_MAX_BUCKET_WINDOW   12

Definition at line 60 of file ecmult_impl.h.

Referenced by secp256k1_pippenger_bucket_window(), secp256k1_pippenger_bucket_window_inv(), secp256k1_pippenger_max_points(), test_ecmult_multi_pippenger_max_points(), and test_secp256k1_pippenger_bucket_window_inv().

PIPPENGER_SCRATCH_OBJECTS

#define PIPPENGER_SCRATCH_OBJECTS   6

Definition at line 57 of file ecmult_impl.h.

Referenced by secp256k1_ecmult_pippenger_batch(), secp256k1_pippenger_max_points(), test_ecmult_multi_batching(), and test_ecmult_multi_pippenger_max_points().

STRAUSS_SCRATCH_OBJECTS

#define STRAUSS_SCRATCH_OBJECTS   6

Definition at line 58 of file ecmult_impl.h.

Referenced by main(), run_ecmult_multi_tests(), secp256k1_ecmult_strauss_batch(), secp256k1_strauss_max_points(), and test_ecmult_multi_batching().

WINDOW_A

#define WINDOW_A   5

Definition at line 33 of file ecmult_impl.h.

Referenced by bench_ecmult_wnaf(), bench_wnaf_const(), secp256k1_ecmult(), secp256k1_ecmult_const(), secp256k1_ecmult_odd_multiples_table_globalz_windowa(), secp256k1_ecmult_strauss_batch(), secp256k1_ecmult_strauss_wnaf(), and secp256k1_strauss_scratch_size().

WINDOW_G

#define WINDOW_G   16

larger numbers may result in slightly better performance, at the cost of exponentially larger precomputed tables.

One table for window size 16: 1.375 MiB.

Definition at line 41 of file ecmult_impl.h.

Referenced by secp256k1_ecmult_context_build(), secp256k1_ecmult_context_clone(), and secp256k1_ecmult_strauss_wnaf().

WNAF_BITS

#define WNAF_BITS   256

Definition at line 48 of file ecmult_impl.h.

Referenced by secp256k1_wnaf_fixed().

WNAF_SIZE

#define WNAF_SIZE

(

w

)

WNAF_SIZE_BITS(WNAF_BITS, w)

Definition at line 51 of file ecmult_impl.h.

Referenced by secp256k1_ecmult_const(), secp256k1_ecmult_pippenger_batch(), secp256k1_ecmult_pippenger_wnaf(), secp256k1_pippenger_max_points(), secp256k1_pippenger_scratch_size(), secp256k1_wnaf_fixed(), test_fixed_wnaf(), test_fixed_wnaf_small(), and test_fixed_wnaf_small_helper().

WNAF_SIZE_BITS

#define WNAF_SIZE_BITS	(		bits,
			w
	)		(((bits) + (w) - 1) / (w))

Definition at line 50 of file ecmult_impl.h.

Referenced by secp256k1_ecmult_const(), secp256k1_wnaf_const(), and test_constant_wnaf().

Typedef Documentation

secp256k1_ecmult_multi_func

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)

Definition at line 1134 of file ecmult_impl.h.

Function Documentation

secp256k1_ecmult()

static void secp256k1_ecmult ( const secp256k1_ecmult_context *  ctx, secp256k1_gej *  r, const secp256k1_gej *  a, const secp256k1_scalar *  na, const secp256k1_scalar *  ng  )

static

Definition at line 600 of file ecmult_impl.h.

References ctx, ECMULT_TABLE_SIZE, secp256k1_strauss_state::pre_a, secp256k1_strauss_state::prej, secp256k1_strauss_state::ps, secp256k1_ecmult_strauss_wnaf(), WINDOW_A, and secp256k1_strauss_state::zr.

Referenced by secp256k1_ecmult_multi_simple_var(), and secp256k1_ecmult_multi_var().

secp256k1_ecmult_context_build()

static void secp256k1_ecmult_context_build ( secp256k1_ecmult_context *  ctx, const secp256k1_callback *  cb  )

static

Definition at line 304 of file ecmult_impl.h.

References checked_malloc(), ctx, ECMULT_TABLE_SIZE, secp256k1_ecmult_odd_multiples_table_storage_var(), secp256k1_ge_const_g, secp256k1_gej_double_var(), secp256k1_gej_set_ge(), and WINDOW_G.

secp256k1_ecmult_context_clear()

static void secp256k1_ecmult_context_clear ( secp256k1_ecmult_context *  ctx )

static

Definition at line 360 of file ecmult_impl.h.

References ctx, and secp256k1_ecmult_context_init().

secp256k1_ecmult_context_clone()

static void secp256k1_ecmult_context_clone ( secp256k1_ecmult_context *  dst, const secp256k1_ecmult_context *  src, const secp256k1_callback *  cb  )

static

Definition at line 336 of file ecmult_impl.h.

References checked_malloc(), ECMULT_TABLE_SIZE, memcpy(), secp256k1_ecmult_context::pre_g, and WINDOW_G.

secp256k1_ecmult_context_init()

static void secp256k1_ecmult_context_init ( secp256k1_ecmult_context *  ctx )

static

Definition at line 297 of file ecmult_impl.h.

References ctx.

Referenced by secp256k1_ecmult_context_clear().

secp256k1_ecmult_context_is_built()

static int secp256k1_ecmult_context_is_built ( const secp256k1_ecmult_context *  ctx )

static

Definition at line 356 of file ecmult_impl.h.

References ctx.

secp256k1_ecmult_multi_batch_size_helper()

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  )

static

Definition at line 1116 of file ecmult_impl.h.

References ECMULT_MAX_POINTS_PER_BATCH.

Referenced by secp256k1_ecmult_multi_var(), and test_ecmult_multi_batch_size_helper().

secp256k1_ecmult_multi_simple_var()

static int secp256k1_ecmult_multi_simple_var ( const secp256k1_ecmult_context *  ctx, secp256k1_gej *  r, const secp256k1_scalar *  inp_g_sc, secp256k1_ecmult_multi_callback  cb, void *  cbdata, size_t  n_points  )

static

Definition at line 1089 of file ecmult_impl.h.

References ctx, secp256k1_ecmult(), secp256k1_gej_add_var(), secp256k1_gej_set_ge(), secp256k1_gej_set_infinity(), and secp256k1_scalar_set_int().

Referenced by secp256k1_ecmult_multi_var().

secp256k1_ecmult_multi_var()

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

Definition at line 1135 of file ecmult_impl.h.

References ctx, ECMULT_PIPPENGER_THRESHOLD, secp256k1_ecmult(), secp256k1_ecmult_multi_batch_size_helper(), secp256k1_ecmult_multi_simple_var(), secp256k1_ecmult_pippenger_batch(), secp256k1_ecmult_strauss_batch(), secp256k1_gej_add_var(), secp256k1_gej_set_infinity(), secp256k1_pippenger_max_points(), secp256k1_scalar_set_int(), and secp256k1_strauss_max_points().

secp256k1_ecmult_odd_multiples_table()

static void secp256k1_ecmult_odd_multiples_table ( int  n, secp256k1_gej *  prej, secp256k1_fe *  zr, const secp256k1_gej *  a  )

static

Fill a table 'prej' with precomputed odd multiples of a.

Prej will contain the values [1*a,3*a,...,(2*n-1)*a], so it space for n values. zr[0] will contain prej[0].z / a.z. The other zr[i] values = prej[i].z / prej[i-1].z. Prej's Z values are undefined, except for the last value.

Definition at line 80 of file ecmult_impl.h.

References secp256k1_ge::infinity, secp256k1_gej::infinity, secp256k1_fe_mul(), secp256k1_ge_set_gej_zinv(), secp256k1_gej_add_ge_var(), secp256k1_gej_double_var(), VERIFY_CHECK, secp256k1_ge::x, secp256k1_gej::x, secp256k1_ge::y, secp256k1_gej::y, and secp256k1_gej::z.

Referenced by secp256k1_ecmult_odd_multiples_table_globalz_windowa(), and secp256k1_ecmult_strauss_wnaf().

secp256k1_ecmult_odd_multiples_table_globalz_windowa()

static void secp256k1_ecmult_odd_multiples_table_globalz_windowa ( secp256k1_ge *  pre, secp256k1_fe *  globalz, const secp256k1_gej *  a  )

static

Fill a table 'pre' with precomputed odd multiples of a.

There are two versions of this function:

• secp256k1_ecmult_odd_multiples_table_globalz_windowa which brings its resulting point set to a single constant Z denominator, stores the X and Y coordinates as ge_storage points in pre, and stores the global Z in rz. It only operates on tables sized for WINDOW_A wnaf multiples.
• secp256k1_ecmult_odd_multiples_table_storage_var, which converts its resulting point set to actually affine points, and stores those in pre. It operates on tables of any size, but uses heap-allocated temporaries.

To compute a*P + b*G, we compute a table for P using the first function, and for G using the second (which requires an inverse, but it only needs to happen once).

Definition at line 130 of file ecmult_impl.h.

References ECMULT_TABLE_SIZE, secp256k1_ecmult_odd_multiples_table(), secp256k1_ge_globalz_set_table_gej(), and WINDOW_A.

Referenced by secp256k1_ecmult_const().

secp256k1_ecmult_odd_multiples_table_storage_var()

static void secp256k1_ecmult_odd_multiples_table_storage_var ( const int  n, secp256k1_ge_storage *  pre, const secp256k1_gej *  a  )

static

Definition at line 140 of file ecmult_impl.h.

References secp256k1_ge::infinity, secp256k1_gej::infinity, secp256k1_fe_add(), secp256k1_fe_inv_var(), secp256k1_fe_mul(), secp256k1_fe_negate(), secp256k1_fe_normalize_var(), secp256k1_fe_sqr(), secp256k1_fe_to_storage(), secp256k1_ge_from_storage(), secp256k1_ge_set_gej_zinv(), secp256k1_ge_to_storage(), secp256k1_gej_add_ge_var(), secp256k1_gej_double_var(), VERIFY_CHECK, secp256k1_ge::x, secp256k1_gej::x, secp256k1_ge::y, secp256k1_gej::y, and secp256k1_gej::z.

Referenced by secp256k1_ecmult_context_build().

secp256k1_ecmult_pippenger_batch()

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

Definition at line 966 of file ecmult_impl.h.

References ctx, PIPPENGER_SCRATCH_OBJECTS, secp256k1_pippenger_state::ps, secp256k1_ecmult_pippenger_wnaf(), secp256k1_ge_const_g, secp256k1_gej_clear(), secp256k1_gej_set_infinity(), secp256k1_pippenger_bucket_window(), secp256k1_pippenger_scratch_size(), secp256k1_scalar_clear(), secp256k1_scratch_alloc(), secp256k1_scratch_allocate_frame(), secp256k1_scratch_deallocate_frame(), secp256k1_pippenger_point_state::skew_na, secp256k1_pippenger_state::wnaf_na, and WNAF_SIZE.

Referenced by secp256k1_ecmult_multi_var(), and secp256k1_ecmult_pippenger_batch_single().

secp256k1_ecmult_pippenger_batch_single()

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  )

static

Definition at line 1042 of file ecmult_impl.h.

References secp256k1_ecmult_pippenger_batch().

Referenced by main(), and run_ecmult_multi_tests().

secp256k1_ecmult_pippenger_wnaf()

static int secp256k1_ecmult_pippenger_wnaf ( secp256k1_gej *  buckets, int  bucket_window, struct secp256k1_pippenger_state *  state, secp256k1_gej *  r, const secp256k1_scalar *  sc, const secp256k1_ge *  pt, size_t  num  )

static

Definition at line 763 of file ecmult_impl.h.

References ECMULT_TABLE_SIZE, secp256k1_pippenger_point_state::input_pos, secp256k1_pippenger_state::ps, secp256k1_ge_is_infinity(), secp256k1_ge_neg(), secp256k1_gej_add_ge_var(), secp256k1_gej_add_var(), secp256k1_gej_double_var(), secp256k1_gej_set_infinity(), secp256k1_scalar_is_zero(), secp256k1_wnaf_fixed(), secp256k1_pippenger_point_state::skew_na, secp256k1_pippenger_state::wnaf_na, and WNAF_SIZE.

Referenced by secp256k1_ecmult_pippenger_batch().

secp256k1_ecmult_strauss_batch()

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  )

static

Definition at line 629 of file ecmult_impl.h.

References ctx, ECMULT_TABLE_SIZE, secp256k1_strauss_state::pre_a, secp256k1_strauss_state::prej, secp256k1_strauss_state::ps, secp256k1_ecmult_strauss_wnaf(), secp256k1_gej_set_ge(), secp256k1_gej_set_infinity(), secp256k1_scratch_alloc(), secp256k1_scratch_allocate_frame(), secp256k1_scratch_deallocate_frame(), secp256k1_strauss_scratch_size(), STRAUSS_SCRATCH_OBJECTS, WINDOW_A, and secp256k1_strauss_state::zr.

Referenced by secp256k1_ecmult_multi_var(), and secp256k1_ecmult_strauss_batch_single().

secp256k1_ecmult_strauss_batch_single()

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  )

static

Definition at line 669 of file ecmult_impl.h.

References secp256k1_ecmult_strauss_batch().

Referenced by main(), and run_ecmult_multi_tests().

secp256k1_ecmult_strauss_wnaf()

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  )

static

Definition at line 450 of file ecmult_impl.h.

References immer::detail::rbts::bits, secp256k1_strauss_point_state::bits_na, ctx, ECMULT_TABLE_GET_GE, ECMULT_TABLE_GET_GE_STORAGE, ECMULT_TABLE_SIZE, secp256k1_gej::infinity, secp256k1_strauss_point_state::input_pos, secp256k1_strauss_state::pre_a, secp256k1_strauss_state::prej, secp256k1_strauss_state::ps, secp256k1_ecmult_odd_multiples_table(), secp256k1_ecmult_wnaf(), secp256k1_fe_mul(), secp256k1_fe_normalize_var(), secp256k1_fe_set_int(), secp256k1_ge_globalz_set_table_gej(), secp256k1_gej_add_ge_var(), secp256k1_gej_add_zinv_var(), secp256k1_gej_double_var(), secp256k1_gej_is_infinity(), secp256k1_gej_rescale(), secp256k1_gej_set_infinity(), secp256k1_scalar_is_zero(), secp256k1_scalar_split_128(), VERIFY_CHECK, WINDOW_A, WINDOW_G, secp256k1_strauss_point_state::wnaf_na, secp256k1_gej::z, and secp256k1_strauss_state::zr.

Referenced by secp256k1_ecmult(), and secp256k1_ecmult_strauss_batch().

secp256k1_ecmult_wnaf()

static int secp256k1_ecmult_wnaf ( int *  wnaf, int  len, const secp256k1_scalar *  a, int  w  )

static

Convert a number to WNAF notation.

The number becomes represented by sum(2^i * wnaf[i], i=0..bits), with the following guarantees:

• each wnaf[i] is either 0, or an odd integer between -(1<<(w-1) - 1) and (1<<(w-1) - 1)
• two non-zero entries in wnaf are separated by at least w-1 zeroes.
• the number of set values in wnaf is returned. This number is at most 256, and at most one more than the number of bits in the (absolute value) of the input.

Definition at line 375 of file ecmult_impl.h.

References CHECK, secp256k1_scalar_get_bits(), secp256k1_scalar_get_bits_var(), secp256k1_scalar_negate(), and VERIFY_CHECK.

Referenced by bench_ecmult_wnaf(), secp256k1_ecmult_strauss_wnaf(), and test_wnaf().

secp256k1_pippenger_bucket_window()

static int secp256k1_pippenger_bucket_window ( size_t  n )

static

Returns optimal bucket_window (number of bits of a scalar represented by a set of buckets) for a given number of points.

Definition at line 844 of file ecmult_impl.h.

References PIPPENGER_MAX_BUCKET_WINDOW.

Referenced by secp256k1_ecmult_pippenger_batch(), test_ecmult_multi_batching(), test_ecmult_multi_pippenger_max_points(), and test_secp256k1_pippenger_bucket_window_inv().

secp256k1_pippenger_bucket_window_inv()

static size_t secp256k1_pippenger_bucket_window_inv ( int  bucket_window )

static

Returns the maximum optimal number of points for a bucket_window.

Definition at line 901 of file ecmult_impl.h.

References PIPPENGER_MAX_BUCKET_WINDOW.

Referenced by secp256k1_pippenger_max_points(), test_ecmult_multi_pippenger_max_points(), and test_secp256k1_pippenger_bucket_window_inv().

secp256k1_pippenger_max_points()

static size_t secp256k1_pippenger_max_points ( secp256k1_scratch *  scratch )

static

Returns the maximum number of points in addition to G that can be used with a given scratch space.

The function ensures that fewer points may also be used.

Definition at line 1051 of file ecmult_impl.h.

References PIPPENGER_MAX_BUCKET_WINDOW, PIPPENGER_SCRATCH_OBJECTS, secp256k1_pippenger_bucket_window_inv(), secp256k1_scratch_max_allocation(), and WNAF_SIZE.

Referenced by secp256k1_ecmult_multi_var(), and test_ecmult_multi_pippenger_max_points().

secp256k1_pippenger_scratch_size()

static size_t secp256k1_pippenger_scratch_size ( size_t  n_points, int  bucket_window  )

static

Returns the scratch size required for a given number of points (excluding base point G) without considering alignment.

Definition at line 956 of file ecmult_impl.h.

References WNAF_SIZE.

Referenced by secp256k1_ecmult_pippenger_batch(), test_ecmult_multi_batching(), and test_ecmult_multi_pippenger_max_points().

secp256k1_strauss_max_points()

static size_t secp256k1_strauss_max_points ( secp256k1_scratch *  scratch )

static

Definition at line 673 of file ecmult_impl.h.

References secp256k1_scratch_max_allocation(), secp256k1_strauss_scratch_size(), and STRAUSS_SCRATCH_OBJECTS.

Referenced by secp256k1_ecmult_multi_var().

secp256k1_strauss_scratch_size()

static size_t secp256k1_strauss_scratch_size ( size_t  n_points )

static

Definition at line 620 of file ecmult_impl.h.

References ECMULT_TABLE_SIZE, and WINDOW_A.

Referenced by main(), run_ecmult_multi_tests(), secp256k1_ecmult_strauss_batch(), secp256k1_strauss_max_points(), and test_ecmult_multi_batching().

secp256k1_wnaf_fixed()

static int secp256k1_wnaf_fixed ( int *  wnaf, const secp256k1_scalar *  s, int  w  )

static

Convert a number to WNAF notation.

The number becomes represented by sum(2^{wi} * wnaf[i], i=0..WNAF_SIZE(w)+1) - return_val. It has the following guarantees:

• each wnaf[i] is either 0 or an odd integer between -(1 << w) and (1 << w)
• the number of words set is always WNAF_SIZE(w)
• the returned skew is 0 or 1

Definition at line 684 of file ecmult_impl.h.

References secp256k1_scalar_get_bits_var(), secp256k1_scalar_is_even(), secp256k1_scalar_is_zero(), WNAF_BITS, and WNAF_SIZE.

Referenced by secp256k1_ecmult_pippenger_wnaf(), test_fixed_wnaf(), and test_fixed_wnaf_small().