gcc emits -Warray-bounds warnings

[hebasto]

While compiling the bitcoin master branch (bitcoin/bitcoin@80c8a02) having the following warnings:

$ gcc --version
gcc (Ubuntu 9.3.0-17ubuntu1~20.04) 9.3.0
Copyright (C) 2019 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

$ make > /dev/null
In file included from src/secp256k1.c:16:
src/ecmult_impl.h: In function ‘secp256k1_ecmult’:
src/ecmult_impl.h:496:48: warning: array subscript [1, 268435456] is outside array bounds of ‘struct secp256k1_strauss_point_state[1]’ [-Warray-bounds]
  496 |             secp256k1_gej tmp = a[state->ps[np].input_pos];
      |                                   ~~~~~~~~~~~~~^~~~~~~~~~
src/ecmult_impl.h:565:42: note: while referencing ‘ps’
  565 |     struct secp256k1_strauss_point_state ps[1];
      |                                          ^~
src/ecmult_impl.h:502:139: warning: array subscript [1, 268435456] is outside array bounds of ‘struct secp256k1_strauss_point_state[1]’ [-Warray-bounds]
  502 |             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));
      |                                                                                                                              ~~~~~~~~~~~~~^~~~~~~~~~
src/ecmult_impl.h:565:42: note: while referencing ‘ps’
  565 |     struct secp256k1_strauss_point_state ps[1];
      |                                          ^~

[elichai]

This looks like a false positive.
on line 574 we pass num=1 then according to the loop on 460 no will also be 1 when the loop ends.
then on line 495 the loop will never enter because the np = 1; np < no condition is false (1<1)

[real-or-random]

Yes, I think that's a false positive... I've seen this one too. It's gone on GCC 10 (tested with 10.2), even with -Warray-bounds=2. Should we do something about his?

What's not great however is the other call to secp256k1_ecmult_strauss_wnaf: (This is currently unused dead code for future applications, so this is not at all an issue currently):

secp256k1/src/ecmult_impl.h

Line 615 in c6b6b8f

secp256k1_ecmult_strauss_wnaf(ctx, &state, r, n_points, points, scalars, inp_g_sc);

Here we pass an unsigned size_t n_points as the 4th argument (int num) to secp256k1_ecmult_strauss_wnaf. I suggest we change all the counter variables inside secp256k1_ecmult_strauss_wnaf to size_t. Apparently we do this in the corresponding code for pippenger but not here. See around

secp256k1/src/ecmult_impl.h

Line 715 in c6b6b8f

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

[gmaxwell]

IIRC it's trivial to get rid of by refactoring the loop into a do while... sorry, I noticed this months ago (its only in compilers I don't usually use and only happens with endo enabled) and talked to sipa about it but neither of us opened a pull request. (I had a patch in a pastebin, but it expired...)

[real-or-random]

There's a small chance that this is related to #839.

@hebasto Can you check if the warning disappears with this PR?

[real-or-random]

IIRC it's trivial to get rid of by refactoring the loop into a do while... sorry, I noticed this months ago (its only in compilers I don't usually use and only happens with endo enabled) and talked to sipa about it but neither of us opened a pull request. (I had a patch in a pastebin, but it expired...)

Are you talking about his loop?

secp256k1/src/ecmult_impl.h

Line 495 in c6b6b8f

for (np = 1; np < no; ++np) {

It's not clear to me do refactor this into a do while.

[sipa]

It's not clear to me do refactor this into a do while.

This works for me:

diff --git a/src/ecmult_impl.h b/src/ecmult_impl.h
index 057a69c..c474fc3 100644
--- a/src/ecmult_impl.h
+++ b/src/ecmult_impl.h
@@ -491,15 +491,14 @@ static void secp256k1_ecmult_strauss_wnaf(const secp256k1_ecmult_context *ctx, c
      */
     if (no > 0) {
         /* Compute the odd multiples in Jacobian form. */
-        secp256k1_ecmult_odd_multiples_table(ECMULT_TABLE_SIZE(WINDOW_A), state->prej, state->zr, &a[state->ps[0].input_pos]);
-        for (np = 1; np < no; ++np) {
+        for (np = 0; np < no; ++np) {
             secp256k1_gej tmp = a[state->ps[np].input_pos];
 #ifdef VERIFY
-            secp256k1_fe_normalize_var(&(state->prej[(np - 1) * ECMULT_TABLE_SIZE(WINDOW_A) + ECMULT_TABLE_SIZE(WINDOW_A) - 1].z));
+            if (np) secp256k1_fe_normalize_var(&(state->prej[(np - 1) * ECMULT_TABLE_SIZE(WINDOW_A) + ECMULT_TABLE_SIZE(WINDOW_A) - 1].z));
 #endif
-            secp256k1_gej_rescale(&tmp, &(state->prej[(np - 1) * ECMULT_TABLE_SIZE(WINDOW_A) + ECMULT_TABLE_SIZE(WINDOW_A) - 1].z));
+            if (np) secp256k1_gej_rescale(&tmp, &(state->prej[(np - 1) * ECMULT_TABLE_SIZE(WINDOW_A) + ECMULT_TABLE_SIZE(WINDOW_A) - 1].z));
             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);
-            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));
+            if (np) 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));
         }
         /* Bring them to the same Z denominator. */
         secp256k1_ge_globalz_set_table_gej(ECMULT_TABLE_SIZE(WINDOW_A) * no, state->pre_a, &Z, state->prej, state->zr);

#841 also silences the warning for me. Sorry for not pointing this out earlier, I had been seeing that since a few months, but forgot about it as it only triggered when the endomorphism was enabled.

[hebasto]

This works for me:

--- a/src/secp256k1/src/ecmult_impl.h
+++ b/src/secp256k1/src/ecmult_impl.h
@@ -491,15 +491,14 @@ static void secp256k1_ecmult_strauss_wnaf(const secp256k1_ecmult_context *ctx, c
      */
     if (no > 0) {
         /* Compute the odd multiples in Jacobian form. */
-        secp256k1_ecmult_odd_multiples_table(ECMULT_TABLE_SIZE(WINDOW_A), state->prej, state->zr, &a[state->ps[0].input_pos]);
-        for (np = 1; np < no; ++np) {
+        for (np = 0; np < no; ++np) {
             secp256k1_gej tmp = a[state->ps[np].input_pos];
 #ifdef VERIFY
-            secp256k1_fe_normalize_var(&(state->prej[(np - 1) * ECMULT_TABLE_SIZE(WINDOW_A) + ECMULT_TABLE_SIZE(WINDOW_A) - 1].z));
+            if (np) secp256k1_fe_normalize_var(&(state->prej[(np - 1) * ECMULT_TABLE_SIZE(WINDOW_A) + ECMULT_TABLE_SIZE(WINDOW_A) - 1].z));
 #endif
-            secp256k1_gej_rescale(&tmp, &(state->prej[(np - 1) * ECMULT_TABLE_SIZE(WINDOW_A) + ECMULT_TABLE_SIZE(WINDOW_A) - 1].z));
+            if (np) secp256k1_gej_rescale(&tmp, &(state->prej[(np - 1) * ECMULT_TABLE_SIZE(WINDOW_A) + ECMULT_TABLE_SIZE(WINDOW_A) - 1].z));
             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);
-            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));
+            if (np) 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));
         }
         /* Bring them to the same Z denominator. */
         secp256k1_ge_globalz_set_table_gej(ECMULT_TABLE_SIZE(WINDOW_A) * no, state->pre_a, &Z, state->prej, state->zr);

$ make > /dev/null
# no warnings :)

[hebasto]

@real-or-random

There's a small chance that this is related to #839.

@hebasto Can you check if the warning disappears with this PR?

#839 seems actively developing now. Let's wait for a bit more stable state, at least until the next morning in my tz :)

[gmaxwell]

uhg. please don't litter the function with conditionals to suppress an outright spurious warning.

[sipa]

@gmaxwell I'm trying to remember what the "simple fix" is we had a few months ago, but I don't think it works without the conditionals. In any case, #841 seems like a much better and simpler change.

[gmaxwell]

I thought it just had one (around the whole block), but perhaps not-- perhaps I didn't like it either and thats why it didn't get PRed. :)