Fix secp256k1_ge_set_table_gej_var parameter order
[secp256k1.git] / src / ecmult_impl.h
index ef2e7ec6b9be7c125f966bd1d5b2b9af17f058bc..f5e65138b8b23945545bb5395c1eecba6792139b 100644 (file)
@@ -32,9 +32,9 @@
  *  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.
  */
-static void secp256k1_ecmult_odd_multiples_table(int n, secp256k1_gej_t *prej, secp256k1_fe_t *zr, const secp256k1_gej_t *a) {
-    secp256k1_gej_t d;
-    secp256k1_ge_t a_ge, d_ge;
+static void secp256k1_ecmult_odd_multiples_table(int n, secp256k1_gej *prej, secp256k1_fe *zr, const secp256k1_gej *a) {
+    secp256k1_gej d;
+    secp256k1_ge a_ge, d_ge;
     int i;
 
     VERIFY_CHECK(!a->infinity);
@@ -82,9 +82,9 @@ static void secp256k1_ecmult_odd_multiples_table(int n, secp256k1_gej_t *prej, s
  *  and for G using the second (which requires an inverse, but it only needs to
  *  happen once).
  */
-static void secp256k1_ecmult_odd_multiples_table_globalz_windowa(secp256k1_ge_t *pre, secp256k1_fe_t *globalz, const secp256k1_gej_t *a) {
-    secp256k1_gej_t prej[ECMULT_TABLE_SIZE(WINDOW_A)];
-    secp256k1_fe_t zr[ECMULT_TABLE_SIZE(WINDOW_A)];
+static void secp256k1_ecmult_odd_multiples_table_globalz_windowa(secp256k1_ge *pre, secp256k1_fe *globalz, const secp256k1_gej *a) {
+    secp256k1_gej prej[ECMULT_TABLE_SIZE(WINDOW_A)];
+    secp256k1_fe zr[ECMULT_TABLE_SIZE(WINDOW_A)];
 
     /* Compute the odd multiples in Jacobian form. */
     secp256k1_ecmult_odd_multiples_table(ECMULT_TABLE_SIZE(WINDOW_A), prej, zr, a);
@@ -92,16 +92,16 @@ static void secp256k1_ecmult_odd_multiples_table_globalz_windowa(secp256k1_ge_t
     secp256k1_ge_globalz_set_table_gej(ECMULT_TABLE_SIZE(WINDOW_A), pre, globalz, prej, zr);
 }
 
-static void secp256k1_ecmult_odd_multiples_table_storage_var(int n, secp256k1_ge_storage_t *pre, const secp256k1_gej_t *a) {
-    secp256k1_gej_t *prej = checked_malloc(sizeof(secp256k1_gej_t) * n);
-    secp256k1_ge_t *prea = checked_malloc(sizeof(secp256k1_ge_t) * n);
-    secp256k1_fe_t *zr = checked_malloc(sizeof(secp256k1_fe_t) * n);
+static void secp256k1_ecmult_odd_multiples_table_storage_var(int n, secp256k1_ge_storage *pre, const secp256k1_gej *a, const secp256k1_callback *cb) {
+    secp256k1_gej *prej = (secp256k1_gej*)checked_malloc(cb, sizeof(secp256k1_gej) * n);
+    secp256k1_ge *prea = (secp256k1_ge*)checked_malloc(cb, sizeof(secp256k1_ge) * n);
+    secp256k1_fe *zr = (secp256k1_fe*)checked_malloc(cb, sizeof(secp256k1_fe) * n);
     int i;
 
     /* Compute the odd multiples in Jacobian form. */
     secp256k1_ecmult_odd_multiples_table(n, prej, zr, a);
     /* Convert them in batch to affine coordinates. */
-    secp256k1_ge_set_table_gej_var(n, prea, prej, zr);
+    secp256k1_ge_set_table_gej_var(prea, prej, zr, n);
     /* Convert them to compact storage form. */
     for (i = 0; i < n; i++) {
         secp256k1_ge_to_storage(&pre[i], &prea[i]);
@@ -137,15 +137,15 @@ static void secp256k1_ecmult_odd_multiples_table_storage_var(int n, secp256k1_ge
     } \
 } while(0)
 
-static void secp256k1_ecmult_context_init(secp256k1_ecmult_context_t *ctx) {
+static void secp256k1_ecmult_context_init(secp256k1_ecmult_context *ctx) {
     ctx->pre_g = NULL;
 #ifdef USE_ENDOMORPHISM
     ctx->pre_g_128 = NULL;
 #endif
 }
 
-static void secp256k1_ecmult_context_build(secp256k1_ecmult_context_t *ctx) {
-    secp256k1_gej_t gj;
+static void secp256k1_ecmult_context_build(secp256k1_ecmult_context *ctx, const secp256k1_callback *cb) {
+    secp256k1_gej gj;
 
     if (ctx->pre_g != NULL) {
         return;
@@ -154,35 +154,35 @@ static void secp256k1_ecmult_context_build(secp256k1_ecmult_context_t *ctx) {
     /* get the generator */
     secp256k1_gej_set_ge(&gj, &secp256k1_ge_const_g);
 
-    ctx->pre_g = (secp256k1_ge_storage_t (*)[])checked_malloc(sizeof((*ctx->pre_g)[0]) * ECMULT_TABLE_SIZE(WINDOW_G));
+    ctx->pre_g = (secp256k1_ge_storage (*)[])checked_malloc(cb, sizeof((*ctx->pre_g)[0]) * ECMULT_TABLE_SIZE(WINDOW_G));
 
     /* precompute the tables with odd multiples */
-    secp256k1_ecmult_odd_multiples_table_storage_var(ECMULT_TABLE_SIZE(WINDOW_G), *ctx->pre_g, &gj);
+    secp256k1_ecmult_odd_multiples_table_storage_var(ECMULT_TABLE_SIZE(WINDOW_G), *ctx->pre_g, &gj, cb);
 
 #ifdef USE_ENDOMORPHISM
     {
-        secp256k1_gej_t g_128j;
+        secp256k1_gej g_128j;
         int i;
 
-        ctx->pre_g_128 = (secp256k1_ge_storage_t (*)[])checked_malloc(sizeof((*ctx->pre_g_128)[0]) * ECMULT_TABLE_SIZE(WINDOW_G));
+        ctx->pre_g_128 = (secp256k1_ge_storage (*)[])checked_malloc(cb, sizeof((*ctx->pre_g_128)[0]) * ECMULT_TABLE_SIZE(WINDOW_G));
 
         /* calculate 2^128*generator */
         g_128j = gj;
         for (i = 0; i < 128; i++) {
             secp256k1_gej_double_var(&g_128j, &g_128j, NULL);
         }
-        secp256k1_ecmult_odd_multiples_table_storage_var(ECMULT_TABLE_SIZE(WINDOW_G), *ctx->pre_g_128, &g_128j);
+        secp256k1_ecmult_odd_multiples_table_storage_var(ECMULT_TABLE_SIZE(WINDOW_G), *ctx->pre_g_128, &g_128j, cb);
     }
 #endif
 }
 
-static void secp256k1_ecmult_context_clone(secp256k1_ecmult_context_t *dst,
-                                           const secp256k1_ecmult_context_t *src) {
+static void secp256k1_ecmult_context_clone(secp256k1_ecmult_context *dst,
+                                           const secp256k1_ecmult_context *src, const secp256k1_callback *cb) {
     if (src->pre_g == NULL) {
         dst->pre_g = NULL;
     } else {
         size_t size = sizeof((*dst->pre_g)[0]) * ECMULT_TABLE_SIZE(WINDOW_G);
-        dst->pre_g = (secp256k1_ge_storage_t (*)[])checked_malloc(size);
+        dst->pre_g = (secp256k1_ge_storage (*)[])checked_malloc(cb, size);
         memcpy(dst->pre_g, src->pre_g, size);
     }
 #ifdef USE_ENDOMORPHISM
@@ -190,17 +190,17 @@ static void secp256k1_ecmult_context_clone(secp256k1_ecmult_context_t *dst,
         dst->pre_g_128 = NULL;
     } else {
         size_t size = sizeof((*dst->pre_g_128)[0]) * ECMULT_TABLE_SIZE(WINDOW_G);
-        dst->pre_g_128 = (secp256k1_ge_storage_t (*)[])checked_malloc(size);
+        dst->pre_g_128 = (secp256k1_ge_storage (*)[])checked_malloc(cb, size);
         memcpy(dst->pre_g_128, src->pre_g_128, size);
     }
 #endif
 }
 
-static int secp256k1_ecmult_context_is_built(const secp256k1_ecmult_context_t *ctx) {
+static int secp256k1_ecmult_context_is_built(const secp256k1_ecmult_context *ctx) {
     return ctx->pre_g != NULL;
 }
 
-static void secp256k1_ecmult_context_clear(secp256k1_ecmult_context_t *ctx) {
+static void secp256k1_ecmult_context_clear(secp256k1_ecmult_context *ctx) {
     free(ctx->pre_g);
 #ifdef USE_ENDOMORPHISM
     free(ctx->pre_g_128);
@@ -213,21 +213,28 @@ static void secp256k1_ecmult_context_clear(secp256k1_ecmult_context_t *ctx) {
  *  - 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.
+ *    than the number of bits in the (absolute value) of the input.
  */
-static int secp256k1_ecmult_wnaf(int *wnaf, const secp256k1_scalar_t *a, int w) {
-    secp256k1_scalar_t s = *a;
-    int set_bits = 0;
+static int secp256k1_ecmult_wnaf(int *wnaf, int len, const secp256k1_scalar *a, int w) {
+    secp256k1_scalar s = *a;
+    int last_set_bit = -1;
     int bit = 0;
     int sign = 1;
     int carry = 0;
 
+    VERIFY_CHECK(wnaf != NULL);
+    VERIFY_CHECK(0 <= len && len <= 256);
+    VERIFY_CHECK(a != NULL);
+    VERIFY_CHECK(2 <= w && w <= 31);
+
+    memset(wnaf, 0, len * sizeof(wnaf[0]));
+
     if (secp256k1_scalar_get_bits(&s, 255, 1)) {
         secp256k1_scalar_negate(&s, &s);
         sign = -1;
     }
 
-    while (bit < 256) {
+    while (bit < len) {
         int now;
         int word;
         if (secp256k1_scalar_get_bits(&s, bit, 1) == (unsigned int)carry) {
@@ -236,8 +243,8 @@ static int secp256k1_ecmult_wnaf(int *wnaf, const secp256k1_scalar_t *a, int w)
         }
 
         now = w;
-        if (now > 256 - bit) {
-            now = 256 - bit;
+        if (now > len - bit) {
+            now = len - bit;
         }
 
         word = secp256k1_scalar_get_bits_var(&s, bit, now) + carry;
@@ -245,25 +252,29 @@ static int secp256k1_ecmult_wnaf(int *wnaf, const secp256k1_scalar_t *a, int w)
         carry = (word >> (w-1)) & 1;
         word -= carry << w;
 
-        while (set_bits < bit) {
-            wnaf[set_bits++] = 0;
-        }
-        wnaf[set_bits++] = sign * word;
+        wnaf[bit] = sign * word;
+        last_set_bit = bit;
+
         bit += now;
     }
-    VERIFY_CHECK(carry == 0);
-    return set_bits;
+#ifdef VERIFY
+    CHECK(carry == 0);
+    while (bit < 256) {
+        CHECK(secp256k1_scalar_get_bits(&s, bit++, 1) == 0);
+    } 
+#endif
+    return last_set_bit + 1;
 }
 
-static void secp256k1_ecmult(const secp256k1_ecmult_context_t *ctx, secp256k1_gej_t *r, const secp256k1_gej_t *a, const secp256k1_scalar_t *na, const secp256k1_scalar_t *ng) {
-    secp256k1_ge_t pre_a[ECMULT_TABLE_SIZE(WINDOW_A)];
-    secp256k1_ge_t tmpa;
-    secp256k1_fe_t Z;
+static void secp256k1_ecmult(const secp256k1_ecmult_context *ctx, secp256k1_gej *r, const secp256k1_gej *a, const secp256k1_scalar *na, const secp256k1_scalar *ng) {
+    secp256k1_ge pre_a[ECMULT_TABLE_SIZE(WINDOW_A)];
+    secp256k1_ge tmpa;
+    secp256k1_fe Z;
 #ifdef USE_ENDOMORPHISM
-    secp256k1_ge_t pre_a_lam[ECMULT_TABLE_SIZE(WINDOW_A)];
-    secp256k1_scalar_t na_1, na_lam;
+    secp256k1_ge pre_a_lam[ECMULT_TABLE_SIZE(WINDOW_A)];
+    secp256k1_scalar na_1, na_lam;
     /* Splitted G factors. */
-    secp256k1_scalar_t ng_1, ng_128;
+    secp256k1_scalar ng_1, ng_128;
     int wnaf_na_1[130];
     int wnaf_na_lam[130];
     int bits_na_1;
@@ -275,7 +286,7 @@ static void secp256k1_ecmult(const secp256k1_ecmult_context_t *ctx, secp256k1_ge
 #else
     int wnaf_na[256];
     int bits_na;
-    int wnaf_ng[257];
+    int wnaf_ng[256];
     int bits_ng;
 #endif
     int i;
@@ -283,11 +294,11 @@ static void secp256k1_ecmult(const secp256k1_ecmult_context_t *ctx, secp256k1_ge
 
 #ifdef USE_ENDOMORPHISM
     /* split na into na_1 and na_lam (where na = na_1 + na_lam*lambda, and na_1 and na_lam are ~128 bit) */
-    secp256k1_scalar_split_lambda_var(&na_1, &na_lam, na);
+    secp256k1_scalar_split_lambda(&na_1, &na_lam, na);
 
     /* build wnaf representation for na_1 and na_lam. */
-    bits_na_1   = secp256k1_ecmult_wnaf(wnaf_na_1,   &na_1,   WINDOW_A);
-    bits_na_lam = secp256k1_ecmult_wnaf(wnaf_na_lam, &na_lam, WINDOW_A);
+    bits_na_1   = secp256k1_ecmult_wnaf(wnaf_na_1,   130, &na_1,   WINDOW_A);
+    bits_na_lam = secp256k1_ecmult_wnaf(wnaf_na_lam, 130, &na_lam, WINDOW_A);
     VERIFY_CHECK(bits_na_1 <= 130);
     VERIFY_CHECK(bits_na_lam <= 130);
     bits = bits_na_1;
@@ -296,7 +307,7 @@ static void secp256k1_ecmult(const secp256k1_ecmult_context_t *ctx, secp256k1_ge
     }
 #else
     /* build wnaf representation for na. */
-    bits_na     = secp256k1_ecmult_wnaf(wnaf_na,     na,      WINDOW_A);
+    bits_na     = secp256k1_ecmult_wnaf(wnaf_na,     256, na,      WINDOW_A);
     bits = bits_na;
 #endif
 
@@ -321,8 +332,8 @@ static void secp256k1_ecmult(const secp256k1_ecmult_context_t *ctx, secp256k1_ge
     secp256k1_scalar_split_128(&ng_1, &ng_128, ng);
 
     /* Build wnaf representation for ng_1 and ng_128 */
-    bits_ng_1   = secp256k1_ecmult_wnaf(wnaf_ng_1,   &ng_1,   WINDOW_G);
-    bits_ng_128 = secp256k1_ecmult_wnaf(wnaf_ng_128, &ng_128, WINDOW_G);
+    bits_ng_1   = secp256k1_ecmult_wnaf(wnaf_ng_1,   129, &ng_1,   WINDOW_G);
+    bits_ng_128 = secp256k1_ecmult_wnaf(wnaf_ng_128, 129, &ng_128, WINDOW_G);
     if (bits_ng_1 > bits) {
         bits = bits_ng_1;
     }
@@ -330,7 +341,7 @@ static void secp256k1_ecmult(const secp256k1_ecmult_context_t *ctx, secp256k1_ge
         bits = bits_ng_128;
     }
 #else
-    bits_ng     = secp256k1_ecmult_wnaf(wnaf_ng,     ng,      WINDOW_G);
+    bits_ng     = secp256k1_ecmult_wnaf(wnaf_ng,     256, ng,      WINDOW_G);
     if (bits_ng > bits) {
         bits = bits_ng;
     }
This page took 0.037622 seconds and 4 git commands to generate.