Merge pull request bitcoin#138

sipa · sipa · commit 17288069fbb4 · 2014-12-07T13:19:21.000+01:00
a5759c5 Check return value of malloc (Pieter Wuille) 2b9388b Remove unused secp256k1_fe_inv_all (Pieter Wuille) f461b76 Allocate precomputation arrays on the heap (Pieter Wuille)
diff --git a/src/ecdsa_impl.h b/src/ecdsa_impl.h
@@ -27,7 +27,7 @@ static void secp256k1_ecdsa_start(void) {
         return;
 
     /* Allocate. */
-    secp256k1_ecdsa_consts_t *ret = (secp256k1_ecdsa_consts_t*)malloc(sizeof(secp256k1_ecdsa_consts_t));
+    secp256k1_ecdsa_consts_t *ret = (secp256k1_ecdsa_consts_t*)checked_malloc(sizeof(secp256k1_ecdsa_consts_t));
 
     static const unsigned char order[] = {
         0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,
diff --git a/src/ecmult_gen_impl.h b/src/ecmult_gen_impl.h
@@ -34,7 +34,7 @@ static void secp256k1_ecmult_gen_start(void) {
         return;
 
     /* Allocate the precomputation table. */
-    secp256k1_ecmult_gen_consts_t *ret = (secp256k1_ecmult_gen_consts_t*)malloc(sizeof(secp256k1_ecmult_gen_consts_t));
+    secp256k1_ecmult_gen_consts_t *ret = (secp256k1_ecmult_gen_consts_t*)checked_malloc(sizeof(secp256k1_ecmult_gen_consts_t));
 
     /* get the generator */
     const secp256k1_ge_t *g = &secp256k1_ge_consts->g;
diff --git a/src/ecmult_impl.h b/src/ecmult_impl.h
@@ -43,13 +43,14 @@ static void secp256k1_ecmult_table_precomp_gej_var(secp256k1_gej_t *pre, const s
 
 static void secp256k1_ecmult_table_precomp_ge_var(secp256k1_ge_t *pre, const secp256k1_gej_t *a, int w) {
     const int table_size = 1 << (w-2);
-    secp256k1_gej_t prej[table_size];
+    secp256k1_gej_t *prej = checked_malloc(sizeof(secp256k1_gej_t) * table_size);
     prej[0] = *a;
     secp256k1_gej_t d; secp256k1_gej_double_var(&d, a);
     for (int i=1; i<table_size; i++) {
         secp256k1_gej_add_var(&prej[i], &d, &prej[i-1]);
     }
     secp256k1_ge_set_all_gej_var(table_size, pre, prej);
+    free(prej);
 }
 
 /** The number of entries a table with precomputed multiples needs to have. */
@@ -85,7 +86,7 @@ static void secp256k1_ecmult_start(void) {
         return;
 
     /* Allocate the precomputation table. */
-    secp256k1_ecmult_consts_t *ret = (secp256k1_ecmult_consts_t*)malloc(sizeof(secp256k1_ecmult_consts_t));
+    secp256k1_ecmult_consts_t *ret = (secp256k1_ecmult_consts_t*)checked_malloc(sizeof(secp256k1_ecmult_consts_t));
 
     /* get the generator */
     const secp256k1_ge_t *g = &secp256k1_ge_consts->g;
diff --git a/src/field.h b/src/field.h
@@ -105,9 +105,6 @@ static void secp256k1_fe_inv_var(secp256k1_fe_t *r, const secp256k1_fe_t *a);
 /** Calculate the (modular) inverses of a batch of field elements. Requires the inputs' magnitudes to be
  *  at most 8. The output magnitudes are 1 (but not guaranteed to be normalized). The inputs and
  *  outputs must not overlap in memory. */
-static void secp256k1_fe_inv_all(size_t len, secp256k1_fe_t r[len], const secp256k1_fe_t a[len]);
-
-/** Potentially faster version of secp256k1_fe_inv_all, without constant-time guarantee. */
 static void secp256k1_fe_inv_all_var(size_t len, secp256k1_fe_t r[len], const secp256k1_fe_t a[len]);
 
 /** Convert a field element to a hexadecimal string. */
diff --git a/src/field_impl.h b/src/field_impl.h
@@ -218,30 +218,6 @@ static void secp256k1_fe_inv_var(secp256k1_fe_t *r, const secp256k1_fe_t *a) {
 #endif
 }
 
-static void secp256k1_fe_inv_all(size_t len, secp256k1_fe_t r[len], const secp256k1_fe_t a[len]) {
-    if (len < 1)
-        return;
-
-    VERIFY_CHECK((r + len <= a) || (a + len <= r));
-
-    r[0] = a[0];
-
-    size_t i = 0;
-    while (++i < len) {
-        secp256k1_fe_mul(&r[i], &r[i - 1], &a[i]);
-    }
-
-    secp256k1_fe_t u; secp256k1_fe_inv(&u, &r[--i]);
-
-    while (i > 0) {
-        int j = i--;
-        secp256k1_fe_mul(&r[j], &r[i], &u);
-        secp256k1_fe_mul(&u, &u, &a[j]);
-    }
-
-    r[0] = u;
-}
-
 static void secp256k1_fe_inv_all_var(size_t len, secp256k1_fe_t r[len], const secp256k1_fe_t a[len]) {
     if (len < 1)
         return;
@@ -277,7 +253,7 @@ static void secp256k1_fe_start(void) {
 #endif
     if (secp256k1_fe_consts == NULL) {
         secp256k1_fe_inner_start();
-        secp256k1_fe_consts_t *ret = (secp256k1_fe_consts_t*)malloc(sizeof(secp256k1_fe_consts_t));
+        secp256k1_fe_consts_t *ret = (secp256k1_fe_consts_t*)checked_malloc(sizeof(secp256k1_fe_consts_t));
 #ifndef USE_NUM_NONE
         secp256k1_num_set_bin(&ret->p, secp256k1_fe_consts_p, sizeof(secp256k1_fe_consts_p));
 #endif
diff --git a/src/group_impl.h b/src/group_impl.h
@@ -85,15 +85,16 @@ static void secp256k1_ge_set_gej_var(secp256k1_ge_t *r, secp256k1_gej_t *a) {
 
 static void secp256k1_ge_set_all_gej_var(size_t len, secp256k1_ge_t r[len], const secp256k1_gej_t a[len]) {
     size_t count = 0;
-    secp256k1_fe_t az[len];
+    secp256k1_fe_t *az = checked_malloc(sizeof(secp256k1_fe_t) * len);
     for (size_t i=0; i<len; i++) {
         if (!a[i].infinity) {
             az[count++] = a[i].z;
         }
     }
 
-    secp256k1_fe_t azi[count];
+    secp256k1_fe_t *azi = checked_malloc(sizeof(secp256k1_fe_t) * count);
     secp256k1_fe_inv_all_var(count, azi, az);
+    free(az);
 
     count = 0;
     for (size_t i=0; i<len; i++) {
@@ -106,6 +107,7 @@ static void secp256k1_ge_set_all_gej_var(size_t len, secp256k1_ge_t r[len], cons
             secp256k1_fe_mul(&r[i].y, &a[i].y, &zi3);
         }
     }
+    free(azi);
 }
 
 static void secp256k1_gej_set_infinity(secp256k1_gej_t *r) {
@@ -433,7 +435,7 @@ static void secp256k1_ge_start(void) {
     };
 #endif
     if (secp256k1_ge_consts == NULL) {
-        secp256k1_ge_consts_t *ret = (secp256k1_ge_consts_t*)malloc(sizeof(secp256k1_ge_consts_t));
+        secp256k1_ge_consts_t *ret = (secp256k1_ge_consts_t*)checked_malloc(sizeof(secp256k1_ge_consts_t));
 #ifdef USE_ENDOMORPHISM
         VERIFY_CHECK(secp256k1_fe_set_b32(&ret->beta, secp256k1_ge_consts_beta));
 #endif
diff --git a/src/scalar_impl.h b/src/scalar_impl.h
@@ -40,7 +40,7 @@ static void secp256k1_scalar_start(void) {
         return;
 
     /* Allocate. */
-    secp256k1_scalar_consts_t *ret = (secp256k1_scalar_consts_t*)malloc(sizeof(secp256k1_scalar_consts_t));
+    secp256k1_scalar_consts_t *ret = (secp256k1_scalar_consts_t*)checked_malloc(sizeof(secp256k1_scalar_consts_t));
 
 #ifndef USE_NUM_NONE
     static const unsigned char secp256k1_scalar_consts_order[] = {
diff --git a/src/tests.c b/src/tests.c
@@ -498,23 +498,6 @@ void run_field_inv_var(void) {
     }
 }
 
-void run_field_inv_all(void) {
-    secp256k1_fe_t x[16], xi[16], xii[16];
-    /* Check it's safe to call for 0 elements */
-    secp256k1_fe_inv_all(0, xi, x);
-    for (int i=0; i<count; i++) {
-        size_t len = (secp256k1_rand32() & 15) + 1;
-        for (size_t j=0; j<len; j++)
-            random_fe_non_zero(&x[j]);
-        secp256k1_fe_inv_all(len, xi, x);
-        for (size_t j=0; j<len; j++)
-            CHECK(check_fe_inverse(&x[j], &xi[j]));
-        secp256k1_fe_inv_all(len, xii, xi);
-        for (size_t j=0; j<len; j++)
-            CHECK(check_fe_equal(&x[j], &xii[j]));
-    }
-}
-
 void run_field_inv_all_var(void) {
     secp256k1_fe_t x[16], xi[16], xii[16];
     /* Check it's safe to call for 0 elements */
@@ -1185,7 +1168,6 @@ int main(int argc, char **argv) {
     /* field tests */
     run_field_inv();
     run_field_inv_var();
-    run_field_inv_all();
     run_field_inv_all_var();
     run_sqr();
     run_sqrt();
diff --git a/src/util.h b/src/util.h
@@ -61,6 +61,12 @@
 #define VERIFY_CHECK(cond) do { (void)(cond); } while(0)
 #endif
 
+static inline void *checked_malloc(size_t size) {
+    void *ret = malloc(size);
+    CHECK(ret != NULL);
+    return ret;
+}
+
 /* Macro for restrict, when available and not in a VERIFY build. */
 #if defined(SECP256K1_BUILD) && defined(VERIFY)
 # define SECP256K1_RESTRICT
