Squashed 'src/secp256k1/' changes from 50cc6ab..1897b8e

1897b8e Merge pull request #229
efc571c Add simple testcases for signing with rfc6979 extra entropy.
1573a10 Add ability to pass extra entropy to rfc6979
3087bc4 Merge pull request #228
d9b9f11 Merge pull request #218
0065a8f Eliminate multiple-returns from secp256k1.c.
354ffa3 Make secp256k1_ec_pubkey_create reject oversized secrets.
27bc131 Silence some warnings from pedantic static analysis tools, improve compatibility with C++.
3b7ea63 Merge pull request #221
f789c5b Merge pull request #215
4bc273b Merge pull request #222
137a8ec Merge pull request #216
7c3771d Disable overlength-strings warnings.
8956111 use 128-bit hex seed
02efd06 Use RFC6979 for test PRNGs
ae55e85 Use faster byteswapping and avoid alignment-increasing casts.
443cd4b Get rid of hex format and some binary conversions
0bada0e Merge #214: Improve signing API documentation & specification
8030d7c Improve signing API documentation & specification
7b2fc1c Merge #213: Removed gotos, which are hard to trace and maintain.
11690d3 Removed gotos, which are hard to trace and maintain.
122a1ec Merge pull request #205
035406d Merge pull request #206
2d4cd53 Merge pull request #161
34b898d Additional comments for the testing PRNG and a seeding fix.
6efd6e7 Some comments explaining some of the constants in the code.
ffccfd2 x86_64 assembly optimization for scalar_4x64
67cbdf0 Merge pull request #207
039723d Benchmarks for all internal operations
6cc8425 Include a comment on secp256k1_ecdsa_sign explaining low-s.
f88343f Merge pull request #203
d61e899 Add group operation counts
2473f17 Merge pull request #202
b5bbce6 Some readme updates, e.g. removal of the GMP field.
f0d851e Merge pull request #201
a0ea884 Merge pull request #200
f735446 Convert the rest of the codebase to C89.
bf2e1ac Convert tests to C89. (also fixes a use of bare "inline" in field)
fc8285f Merge pull request #199
fff412e Merge pull request #197
4be8d6f Centralize the definition of uint128_t and use it uniformly.
d9543c9 Switch scalar code to C89.
fcc48c4 Remove the non-storage cmov
55422b6 Switch ecmult_gen to use storage types
41f8455 Use group element storage type in EC multiplications
e68d720 Add group element storage type
ff889f7 Field storage type
7137be8 Merge pull request #196
0768bd5 Get rid of variable-length hex string conversions
e84e761 Merge pull request #195
792bcdb Covert several more files to C89.
45cdf44 Merge pull request #193
17db09e Merge pull request #194
402878a fix ifdef/ifndef
25b35c7 Convert field code to strict C89 (+ long long, +__int128)
3627437 C89 nits and dead code removal.
a9f350d Merge pull request #191
4732d26 Convert the field/group/ecdsa constant initialization to static consts
19f3e76 Remove unused secp256k1_fe_inner_{start, stop} functions
f1ebfe3 Convert the scalar constant initialization to static consts

git-subtree-dir: src/secp256k1
git-subtree-split: 1897b8e90bbbdcd919427c9a8ae35b420e919d8f

1 files changed, 56 insertions, 26 deletions

diff --git a/src/field_5x52_impl.h b/src/field_5x52_impl.h
index 4db9e6f5ff..2f9c8704a8 100644
--- a/src/field_5x52_impl.h
+++ b/src/field_5x52_impl.h
@@ -30,13 +30,11 @@
  *  output.
  */
 
-static void secp256k1_fe_inner_start(void) {}
-static void secp256k1_fe_inner_stop(void) {}
-
 #ifdef VERIFY
 static void secp256k1_fe_verify(const secp256k1_fe_t *a) {
     const uint64_t *d = a->n;
     int m = a->normalized ? 1 : 2 * a->magnitude, r = 1;
+   /* secp256k1 'p' value defined in "Standards for Efficient Cryptography" (SEC2) 2.7.1. */
     r &= (d[0] <= 0xFFFFFFFFFFFFFULL * m);
     r &= (d[1] <= 0xFFFFFFFFFFFFFULL * m);
     r &= (d[2] <= 0xFFFFFFFFFFFFFULL * m);
@@ -62,8 +60,8 @@ static void secp256k1_fe_normalize(secp256k1_fe_t *r) {
     uint64_t t0 = r->n[0], t1 = r->n[1], t2 = r->n[2], t3 = r->n[3], t4 = r->n[4];
 
     /* Reduce t4 at the start so there will be at most a single carry from the first pass */
-    uint64_t x = t4 >> 48; t4 &= 0x0FFFFFFFFFFFFULL;
     uint64_t m;
+    uint64_t x = t4 >> 48; t4 &= 0x0FFFFFFFFFFFFULL;
 
     /* The first pass ensures the magnitude is 1, ... */
     t0 += x * 0x1000003D1ULL;
@@ -129,8 +127,8 @@ static void secp256k1_fe_normalize_var(secp256k1_fe_t *r) {
     uint64_t t0 = r->n[0], t1 = r->n[1], t2 = r->n[2], t3 = r->n[3], t4 = r->n[4];
 
     /* Reduce t4 at the start so there will be at most a single carry from the first pass */
-    uint64_t x = t4 >> 48; t4 &= 0x0FFFFFFFFFFFFULL;
     uint64_t m;
+    uint64_t x = t4 >> 48; t4 &= 0x0FFFFFFFFFFFFULL;
 
     /* The first pass ensures the magnitude is 1, ... */
     t0 += x * 0x1000003D1ULL;
@@ -172,12 +170,12 @@ static void secp256k1_fe_normalize_var(secp256k1_fe_t *r) {
 static int secp256k1_fe_normalizes_to_zero(secp256k1_fe_t *r) {
     uint64_t t0 = r->n[0], t1 = r->n[1], t2 = r->n[2], t3 = r->n[3], t4 = r->n[4];
 
-    /* Reduce t4 at the start so there will be at most a single carry from the first pass */
-    uint64_t x = t4 >> 48; t4 &= 0x0FFFFFFFFFFFFULL;
-
     /* z0 tracks a possible raw value of 0, z1 tracks a possible raw value of P */
     uint64_t z0, z1;
 
+    /* Reduce t4 at the start so there will be at most a single carry from the first pass */
+    uint64_t x = t4 >> 48; t4 &= 0x0FFFFFFFFFFFFULL;
+
     /* The first pass ensures the magnitude is 1, ... */
     t0 += x * 0x1000003D1ULL;
     t1 += (t0 >> 52); t0 &= 0xFFFFFFFFFFFFFULL; z0  = t0; z1  = t0 ^ 0x1000003D0ULL;
@@ -193,22 +191,31 @@ static int secp256k1_fe_normalizes_to_zero(secp256k1_fe_t *r) {
 }
 
 static int secp256k1_fe_normalizes_to_zero_var(secp256k1_fe_t *r) {
-    uint64_t t0 = r->n[0], t4 = r->n[4];
+    uint64_t t0, t1, t2, t3, t4;
+    uint64_t z0, z1;
+    uint64_t x;
+
+    t0 = r->n[0];
+    t4 = r->n[4];
 
     /* Reduce t4 at the start so there will be at most a single carry from the first pass */
-    uint64_t x = t4 >> 48;
+    x = t4 >> 48;
 
     /* The first pass ensures the magnitude is 1, ... */
     t0 += x * 0x1000003D1ULL;
 
     /* z0 tracks a possible raw value of 0, z1 tracks a possible raw value of P */
-    uint64_t z0 = t0 & 0xFFFFFFFFFFFFFULL, z1 = z0 ^ 0x1000003D0ULL;
+    z0 = t0 & 0xFFFFFFFFFFFFFULL;
+    z1 = z0 ^ 0x1000003D0ULL;
 
     /* Fast return path should catch the majority of cases */
     if ((z0 != 0ULL) & (z1 != 0xFFFFFFFFFFFFFULL))
         return 0;
 
-    uint64_t t1 = r->n[1], t2 = r->n[2], t3 = r->n[3];
+    t1 = r->n[1];
+    t2 = r->n[2];
+    t3 = r->n[3];
+
     t4 &= 0x0FFFFFFFFFFFFULL;
 
     t1 += (t0 >> 52); t0  = z0;
@@ -234,11 +241,11 @@ SECP256K1_INLINE static void secp256k1_fe_set_int(secp256k1_fe_t *r, int a) {
 }
 
 SECP256K1_INLINE static int secp256k1_fe_is_zero(const secp256k1_fe_t *a) {
+    const uint64_t *t = a->n;
 #ifdef VERIFY
     VERIFY_CHECK(a->normalized);
     secp256k1_fe_verify(a);
 #endif
-    const uint64_t *t = a->n;
     return (t[0] | t[1] | t[2] | t[3] | t[4]) == 0;
 }
 
@@ -251,23 +258,25 @@ SECP256K1_INLINE static int secp256k1_fe_is_odd(const secp256k1_fe_t *a) {
 }
 
 SECP256K1_INLINE static void secp256k1_fe_clear(secp256k1_fe_t *a) {
+    int i;
 #ifdef VERIFY
     a->magnitude = 0;
     a->normalized = 1;
 #endif
-    for (int i=0; i<5; i++) {
+    for (i=0; i<5; i++) {
         a->n[i] = 0;
     }
 }
 
 static int secp256k1_fe_cmp_var(const secp256k1_fe_t *a, const secp256k1_fe_t *b) {
+    int i;
 #ifdef VERIFY
     VERIFY_CHECK(a->normalized);
     VERIFY_CHECK(b->normalized);
     secp256k1_fe_verify(a);
     secp256k1_fe_verify(b);
 #endif
-    for (int i = 4; i >= 0; i--) {
+    for (i = 4; i >= 0; i--) {
         if (a->n[i] > b->n[i]) return 1;
         if (a->n[i] < b->n[i]) return -1;
     }
@@ -275,9 +284,11 @@ static int secp256k1_fe_cmp_var(const secp256k1_fe_t *a, const secp256k1_fe_t *b
 }
 
 static int secp256k1_fe_set_b32(secp256k1_fe_t *r, const unsigned char *a) {
+    int i;
     r->n[0] = r->n[1] = r->n[2] = r->n[3] = r->n[4] = 0;
-    for (int i=0; i<32; i++) {
-        for (int j=0; j<2; j++) {
+    for (i=0; i<32; i++) {
+        int j;
+        for (j=0; j<2; j++) {
             int limb = (8*i+4*j)/52;
             int shift = (8*i+4*j)%52;
             r->n[limb] |= (uint64_t)((a[31-i] >> (4*j)) & 0xF) << shift;
@@ -296,13 +307,15 @@ static int secp256k1_fe_set_b32(secp256k1_fe_t *r, const unsigned char *a) {
 
 /** Convert a field element to a 32-byte big endian value. Requires the input to be normalized */
 static void secp256k1_fe_get_b32(unsigned char *r, const secp256k1_fe_t *a) {
+    int i;
 #ifdef VERIFY
     VERIFY_CHECK(a->normalized);
     secp256k1_fe_verify(a);
 #endif
-    for (int i=0; i<32; i++) {
+    for (i=0; i<32; i++) {
+        int j;
         int c = 0;
-        for (int j=0; j<2; j++) {
+        for (j=0; j<2; j++) {
             int limb = (8*i+4*j)/52;
             int shift = (8*i+4*j)%52;
             c |= ((a->n[limb] >> shift) & 0xF) << (4 * j);
@@ -386,18 +399,35 @@ static void secp256k1_fe_sqr(secp256k1_fe_t *r, const secp256k1_fe_t *a) {
 #endif
 }
 
-static void secp256k1_fe_cmov(secp256k1_fe_t *r, const secp256k1_fe_t *a, int flag) {
-    uint64_t mask0 = flag + ~((uint64_t)0), mask1 = ~mask0;
+static SECP256K1_INLINE void secp256k1_fe_storage_cmov(secp256k1_fe_storage_t *r, const secp256k1_fe_storage_t *a, int flag) {
+    uint64_t mask0, mask1;
+    mask0 = flag + ~((uint64_t)0);
+    mask1 = ~mask0;
     r->n[0] = (r->n[0] & mask0) | (a->n[0] & mask1);
     r->n[1] = (r->n[1] & mask0) | (a->n[1] & mask1);
     r->n[2] = (r->n[2] & mask0) | (a->n[2] & mask1);
     r->n[3] = (r->n[3] & mask0) | (a->n[3] & mask1);
-    r->n[4] = (r->n[4] & mask0) | (a->n[4] & mask1);
+}
+
+static void secp256k1_fe_to_storage(secp256k1_fe_storage_t *r, const secp256k1_fe_t *a) {
 #ifdef VERIFY
-    if (flag) {
-        r->magnitude = a->magnitude;
-        r->normalized = a->normalized;
-    }
+    VERIFY_CHECK(a->normalized);
+#endif
+    r->n[0] = a->n[0] | a->n[1] << 52;
+    r->n[1] = a->n[1] >> 12 | a->n[2] << 40;
+    r->n[2] = a->n[2] >> 24 | a->n[3] << 28;
+    r->n[3] = a->n[3] >> 36 | a->n[4] << 16;
+}
+
+static SECP256K1_INLINE void secp256k1_fe_from_storage(secp256k1_fe_t *r, const secp256k1_fe_storage_t *a) {
+    r->n[0] = a->n[0] & 0xFFFFFFFFFFFFFULL;
+    r->n[1] = a->n[0] >> 52 | ((a->n[1] << 12) & 0xFFFFFFFFFFFFFULL);
+    r->n[2] = a->n[1] >> 40 | ((a->n[2] << 24) & 0xFFFFFFFFFFFFFULL);
+    r->n[3] = a->n[2] >> 28 | ((a->n[3] << 36) & 0xFFFFFFFFFFFFFULL);
+    r->n[4] = a->n[3] >> 16;
+#ifdef VERIFY
+    r->magnitude = 1;
+    r->normalized = 1;
 #endif
 }