Follow-ups to making all tables fully static

sipa commented at 7:42 pm on December 17, 2021: contributor

This PR implements a number of changes to follow up after merging #988:

Naming consistency:
- All precomputed table files now have name precomputed_*.*
- All source files related to the creation of the precomputed table files have name precompute_*.*.
- All source files related to the computation of tables (whether they go in precomputed files or not) have name *_compute_table.*.
Make the tables for exhaustive tests be computed at runtime rather than compile time (this was already the case for ecmult_gen, but not ecmult). This is a preparation for the next point, as the alternative would be to have separate precomputed libraries for the exhaustive tests and other binaries.
Moves the actual tables to separate precomputed_*.c files, which are compiled only once as part of a new libsecp256k1_precomputed.la, included where relevant. The corresponding precomputed_*.h file are normal source files.

Retry of #1041.

Rename gen_ecmult_gen_static_prec_table -> precompute_ecmult_gen bae77685eb

Rename gen_ecmult_static_pre_g -> precompute_ecmult f95b8106d0

Rename ecmult_gen_static_prec_table -> precomputed_ecmult_gen 7cf47f72bc

Rename ecmult_static_pre_g -> precomputed_ecmult 075252c1b7

Rename ecmult_gen_prec -> ecmult_gen_compute_table 725370c3f2

sipa force-pushed on Dec 17, 2021

in src/precompute_ecmult.c:45 in e8801ea4e3 outdated

46+        secp256k1_ge_to_storage(&table[j], &ge);
47+    }
48+}
49+
50+/* Like secp256k1_ecmult_compute_table, but one for both gen and gen*2^128. */
51+static void secp256k1_ecmult_compute_two_tables(secp256k1_ge_storage* table, secp256k1_ge_storage* table_128, int window_g, const secp256k1_ge* gen) {

real-or-random commented at 9:52 am on December 18, 2021:

Now that this is called “compute” consistently, you could also rename the corresponding function for ecmult_gen (where I arbitrarily choose “create” instead of “compute”). Then it will be eve more consistent. (In hindsight I spent too much time on naming in PR when anyway the new names suggested here are better. :))

sipa commented at 9:13 pm on December 18, 2021:

Done, added a commit to do so.

in src/tests_exhaustive.c:396 in 1379be4190 outdated

389@@ -389,8 +390,10 @@ int main(int argc, char** argv) {
390         printf("running tests for core %lu (out of [0..%lu])\n", (unsigned long)this_core, (unsigned long)num_cores - 1);
391     }
392 
393-    /* Recreate the ecmult_gen table using the right generator (as selected via EXHAUSTIVE_TEST_ORDER) */
394+    /* Recreate the ecmult{,_gen} tables using the right generator (as selected via EXHAUSTIVE_TEST_ORDER) */
395     secp256k1_ecmult_gen_create_prec_table(&secp256k1_ecmult_gen_prec_table[0][0], &secp256k1_ge_const_g, ECMULT_GEN_PREC_BITS);
396+    secp256k1_ecmult_compute_two_tables(secp256k1_pre_g, secp256k1_pre_g_128, WINDOW_G, &secp256k1_ge_const_g);
397+

real-or-random commented at 9:58 am on December 18, 2021:

Just for curiosity: I haven’t read the tests in detail now but is there a simple reason why the exhaustive tests worked with the wrong ecmult tables but not with the wrong ecmult_gen tables? The existence of known-output tests?

nit: no need to add a second newline here

sipa commented at 9:16 pm on December 18, 2021:

The existing ecmult tables (from #956) contain separate tables for the exhaustive test case. So they’re not using wrong tables.

The problem is that this approach isn’t really compatible with the separately-compiled .c file with tables, unless there is a separately-compiled module for (each) exhaustive test generator. So instead I’m modifying the code to use the same approach for ecmult as ecmult_gen does since #988.

real-or-random commented at 10:10 am on December 18, 2021: contributor

ACK mod nits

real-or-random commented at 10:13 am on December 18, 2021: contributor

I think so far it was in theory possible to use libsecp by just including the secp256k1.c file, i.e., by including the source instead of linking binaries. I assume this is not a use case we care about (and I don’t expect anyone to do this) but I would like to draw attention to this.

Rename function secp256k1_ecmult_gen_{create_prec -> compute}_table 31feab053b

Split ecmult table computation and printing fc1bf9f15f

Move ecmult table computation code to separate file e458ec26d6

Compute ecmult tables at runtime for tests_exhaustive 38cd84a0cb

Simplify precompute_ecmult_print_* bb36331412

Split off .c file from precomputed_ecmult_gen.h 1a6691adae

Split off .c file from precomputed_ecmult.h 19d96e15f9

Cleanup preprocessor indentation in precompute{,d}_ecmult{,_gen} c45386d994

Fix c++ build e05da9e480

sipa force-pushed on Dec 18, 2021

sipa commented at 9:18 pm on December 18, 2021: contributor

@real-or-random Good to point that out, but I don’t think it’s really a concern. I think we should preserve (and improve) the ability to build without a complex build/config system around it, but whether that involves building one or two modules isn’t the end of the world. If there is actual desire for that, it wouldn’t be hard to make src/precomputed_ecmult_{,gen_}.h include the corresponding .c file.

in src/ecmult_compute_table.h:10 in e05da9e480

 5+ *****************************************************************************************************/
 6+
 7+#ifndef SECP256K1_ECMULT_COMPUTE_TABLE_H
 8+#define SECP256K1_ECMULT_COMPUTE_TABLE_H
 9+
10+/* Construct table of all odd multiples of gen in range 1..(2**(window_g-1)-1). */

jonasnick commented at 9:36 pm on December 18, 2021:

window_g-2?

sipa commented at 9:38 pm on December 18, 2021:

ECMULT_TABLE_SIZE(w) is (1L << ((w)-2)). But that’s just the size of the table, not the range. As the entries are two apart (only odd values), I think the range extends to 2^(w-1)-1.

jonasnick commented at 9:36 pm on December 18, 2021: contributor

otherwise looks good

jonasnick commented at 10:02 am on December 19, 2021: contributor

ACK e05da9e480de34129a170510a311abb204eefeb3

real-or-random commented at 10:21 am on December 20, 2021: contributor

ACK e05da9e480de34129a170510a311abb204eefeb3

real-or-random merged this on Dec 20, 2021

real-or-random closed this on Dec 20, 2021

real-or-random cross-referenced this on Dec 20, 2021 from issue Tracking issue for manual (non-autotools) builds by real-or-random

real-or-random cross-referenced this on Dec 21, 2021 from issue Make all source and header files self-contained by real-or-random

jonasnick cross-referenced this on Jan 2, 2022 from issue Sync Upstream by jonasnick

real-or-random referenced this in commit 21e2d65b79 on Jan 5, 2022

real-or-random cross-referenced this on Jan 7, 2022 from issue Better lowmemory feature with precomputed ECMULT by devrandom

real-or-random cross-referenced this on Jan 17, 2022 from issue Further changes after making tables static by real-or-random

dhruv referenced this in commit 6f7e395acc on Jan 26, 2022

hebasto referenced this in commit 065b6dbf9d on Jan 30, 2022

hebasto referenced this in commit f2c5ecd0a1 on Jan 30, 2022

hebasto referenced this in commit 91e4c6fa32 on Jan 30, 2022

hebasto commented at 1:29 am on January 30, 2022: member

It looks like this change breaks building Bitcoin Core with MSVC:

0...
1     Creating library C:\Users\ContainerAdministrator\AppData\Local\Temp\cirrus-ci-build\build_msvc\x64\Release\bitcoind.lib and object C:\Users\ContainerAdministrator\AppData\Local\Temp\cirrus-ci-build\build_msvc\x64\Release\bitcoind.exp
2libsecp256k1.lib(secp256k1.obj) : error LNK2019: unresolved external symbol secp256k1_pre_g referenced in function secp256k1_ecmult_strauss_wnaf [C:\Users\ContainerAdministrator\AppData\Local\Temp\cirrus-ci-build\build_msvc\bitcoind\bitcoind.vcxproj]
3libsecp256k1.lib(secp256k1.obj) : error LNK2019: unresolved external symbol secp256k1_pre_g_128 referenced in function secp256k1_ecmult_strauss_wnaf [C:\Users\ContainerAdministrator\AppData\Local\Temp\cirrus-ci-build\build_msvc\bitcoind\bitcoind.vcxproj]
4libsecp256k1.lib(secp256k1.obj) : error LNK2019: unresolved external symbol secp256k1_ecmult_gen_prec_table referenced in function secp256k1_ecmult_gen [C:\Users\ContainerAdministrator\AppData\Local\Temp\cirrus-ci-build\build_msvc\bitcoind\bitcoind.vcxproj]
5C:\Users\ContainerAdministrator\AppData\Local\Temp\cirrus-ci-build\build_msvc\x64\Release\bitcoind.exe : fatal error LNK1120: 3 unresolved externals [C:\Users\ContainerAdministrator\AppData\Local\Temp\cirrus-ci-build\build_msvc\bitcoind\bitcoind.vcxproj]

in Makefile.am:70 in e05da9e480

63@@ -60,12 +64,17 @@ noinst_HEADERS += contrib/lax_der_parsing.c
64 noinst_HEADERS += contrib/lax_der_privatekey_parsing.h
65 noinst_HEADERS += contrib/lax_der_privatekey_parsing.c
66 
67+PRECOMPUTED_LIB = libsecp256k1_precomputed.la
68+noinst_LTLIBRARIES = $(PRECOMPUTED_LIB)
69+libsecp256k1_precomputed_la_SOURCES =  src/precomputed_ecmult.c src/precomputed_ecmult_gen.c
70+libsecp256k1_precomputed_la_CPPFLAGS = $(SECP_INCLUDES)

real-or-random commented at 4:26 pm on January 30, 2022:

@hebasto This is because we now have a separate compilation unit for the precomputed tables. So Core needs to tell MSVC to build libsecp256k1_precomputed separately and link it to the library.

But I have no idea about the required changes to https://github.com/bitcoin/bitcoin/blob/master/build_msvc/libsecp256k1/libsecp256k1.vcxproj that would be equivalent to this automake snippet.

If this is anyway maintained within the Bitcoin Core org, maybe we should move the vcxproj file to this repo in the future. This will help us add MSVC builds to the CI here.

hebasto commented at 8:48 pm on January 30, 2022:

@sipsorcery

Could you look into this?

sipsorcery commented at 8:25 pm on January 31, 2022:

@hebasto inlcuding the new precompute .c files in the libsecp25k1.vcxproj got the build working for me.

0  <ItemGroup>
1    <ClCompile Include="..\..\src\secp256k1\src\precomputed_ecmult.c" />
2    <ClCompile Include="..\..\src\secp256k1\src\precomputed_ecmult_gen.c" />
3    <ClCompile Include="..\..\src\secp256k1\src\precompute_ecmult.c" />
4    <ClCompile Include="..\..\src\secp256k1\src\precompute_ecmult_gen.c" />
5    <ClCompile Include="..\..\src\secp256k1\src\secp256k1.c" />
6  </ItemGroup>

hebasto commented at 9:09 pm on January 31, 2022:

@sipsorcery

Thanks! It works flawlessly.

real-or-random commented at 12:08 pm on February 1, 2022:

@sipsorcery That works but it’s too much: You don’t need the precompute_ files, the precomputed files should be enough.

Also, this will then recompile the precomputed_ files every time, which makes recompilation somewhat slower than what we have in our Makefile. (This was the reason why we introduced the libsecp256k1_precomputed as a separate object.) But yeah, this only affects compilation time, so it’s probably not worth to optimize the vcxproj for this.

edit: Oh, now I see that @sipa already replied in https://github.com/bitcoin/bitcoin/pull/23432#issuecomment-1026218707.

hebasto cross-referenced this on Jan 31, 2022 from issue BIP324: CKey encode/decode to elligator-swift by dhruv

dhruv referenced this in commit 139d4b881e on Feb 1, 2022

fanquake referenced this in commit 8f8631d826 on Mar 17, 2022

fanquake referenced this in commit 4bb1d7e62a on Mar 17, 2022

fanquake referenced this in commit 465d05253a on Mar 30, 2022

stratospher referenced this in commit 4d5afc9767 on Apr 3, 2022

stratospher referenced this in commit 5b18493cfa on Apr 3, 2022

fanquake referenced this in commit afb7a6fe06 on Apr 6, 2022

gwillen referenced this in commit 35d6112a72 on May 25, 2022

patricklodder referenced this in commit 21badcf9d2 on Jul 25, 2022

patricklodder referenced this in commit 03002a9013 on Jul 28, 2022

janus referenced this in commit 3a0652a777 on Aug 4, 2022

hebasto commented at 11:58 am on March 13, 2023: member

@sipa

During reviewing of the current master branch, I’ve noticed that extern "C" {...} guarded by #ifdef __cplusplus were added to non-public headers in the commit e05da9e480de34129a170510a311abb204eefeb3 “Fix c++ build”.

But I cannot see any scenario where those headers, i.e., src/precomputed_ecmult.h and src/precomputed_ecmult_gen.h, are processed by a C++ compiler.

FWIW, no issues are observed when compiling Bitcoin Core after removal of extern "C" {...} from the mentioned headers.

Did I miss something?

real-or-random commented at 4:49 am on March 26, 2023: contributor

But I cannot see any scenario where those headers, i.e., src/precomputed_ecmult.h and src/precomputed_ecmult_gen.h, are processed by a C++ compiler.

I haven’t checked, but maybe those will would be relevant when compiling the precomputed compilation unit with a C compiler but the rest with a C++ compiler? But why should anyone do this? ping @sipa

str4d referenced this in commit 522190d5c3 on Apr 21, 2023

vmta referenced this in commit e1120c94a1 on Jun 4, 2023

vmta referenced this in commit 8f03457eed on Jul 1, 2023

Follow-ups to making all tables fully static #1042