Improve checks at top of _fe_negate methods #816
pull peterdettman wants to merge 1 commits into bitcoin-core:master from peterdettman:fe_negate_checks changing 2 files +7 −0-
peterdettman commented at 7:37 am on September 14, 2020: contributorIn theory we could have a single static assertion that would ensure all of these are always true (for any magnitude up to the limit), but I think this small redundancy is clearer.
-
robot-dreams commented at 5:17 pm on December 3, 2021: contributor
ACK b06de0a9ee5af6f83821cb227ea3aba014f6d4ab
I ran a script to confirm that the field_10x26 check holds for all magnitudes in [0, 31], and that the field_5x52 check holds for all magnitudes in [0, 2047].
I also looked at the implementation of
fe_verify
to make sure the RHS of each check is indeed the largest possible value of the corresponding limb (given the magnitude m).Since there was no CI run for this change, I rebased onto 49f608de474a89e5c742830c8ff5ac8978b5796a and ran
make check
—all tests passed locally. -
robot-dreams cross-referenced this on Dec 3, 2021 from issue doc: Fix upper bounds + cleanup in field_5x52_impl.h comment by robot-dreams
-
real-or-random commented at 10:44 am on December 5, 2021: contributor
I ran a script to confirm that the field_10x26 check holds for all magnitudes in [0, 31], and that the field_5x52 check holds for all magnitudes in [0, 2047].
Do you think it would make sense to post this here for other reviewers to check or even have this in the repo?
Since there was no CI run for this change, I rebased onto 49f608d and ran make check—all tests passed locally.
I tried to trigger manually but it didn’t work (https://cirrus-ci.com/build/5109653131493376). @peterdettman Can you rebase this on master so we get a CI run?
-
robot-dreams commented at 5:20 pm on December 5, 2021: contributor
Sure, here you go! It’s pretty straightforward—all I did was make sure that for every magnitude in the range, (1) the value doesn’t overflow the word size, and (2) the inequality holds.
0UINT32_MAX = (1 << 32) - 1 1UINT64_MAX = (1 << 64) - 1 2 3M_MAX_10x26 = 32 4M_MAX_5x52 = 2048 5 6def verify_ge_32(a, b): 7 assert a <= UINT32_MAX 8 assert b <= UINT32_MAX 9 assert a >= b 10 11def verify_ge_64(a, b): 12 assert a <= UINT64_MAX 13 assert b <= UINT64_MAX 14 assert a >= b 15 16for m in range(0, M_MAX_10x26): 17 verify_ge_32(0x3FFFC2F * 2 * (m + 1), 0x3FFFFFF * 2 * m); 18 verify_ge_32(0x3FFFFBF * 2 * (m + 1), 0x3FFFFFF * 2 * m); 19 verify_ge_32(0x3FFFFFF * 2 * (m + 1), 0x3FFFFFF * 2 * m); 20 verify_ge_32(0x03FFFFF * 2 * (m + 1), 0x03FFFFF * 2 * m); 21 22for m in range(0, M_MAX_5x52): 23 verify_ge_64(0xFFFFEFFFFFC2F * 2 * (m + 1), 0xFFFFFFFFFFFFF * 2 * m); 24 verify_ge_64(0xFFFFFFFFFFFFF * 2 * (m + 1), 0xFFFFFFFFFFFFF * 2 * m); 25 verify_ge_64(0x0FFFFFFFFFFFF * 2 * (m + 1), 0x0FFFFFFFFFFFF * 2 * m);
Note: The checks would fail at the “endpoints”
m = 32
(for 10x26) andm = 2048
(for 5x52), but I think this is OK / expected because the magnitude of the result will bem + 1
, so the finalfe_verify
check would have failed anyway. Maybe it’s worth explicitly adding an extra check thatm
isn’t too big, but I don’t have a strong opinion about this. -
peterdettman force-pushed on Dec 6, 2021
-
peterdettman commented at 4:19 am on December 6, 2021: contributor@real-or-random Rebased.
-
robot-dreams commented at 4:12 pm on December 6, 2021: contributorACK 3e03435ba36f07ef956d4bfb71a3fa580ce29326, no difference aside from rebase
-
Improve checks at top of _fe_negate methods 515e7953ca
-
peterdettman force-pushed on Dec 21, 2021
-
sipa commented at 0:26 am on December 22, 2021: contributorutACK 515e7953cab4eb3be063fa3991e4e0663d3f04ae
-
real-or-random commented at 9:43 am on December 22, 2021: contributor
ACK 515e7953cab4eb3be063fa3991e4e0663d3f04ae bounds hold by inspection and by robot-dreams’s script
I was a little bit skeptical that this will increase the running time of the tests but it doesn’t make a difference on my machine. I had that thought because I recently noticed that
fe_verify
makes up for about 15% of the default./tests 64
. I tried to optimize it but I failed to find a faster variant. (@peterdettman if you’re in the mood… :D) -
real-or-random merged this on Dec 22, 2021
-
real-or-random closed this on Dec 22, 2021
-
real-or-random referenced this in commit 0b83b203e1 on Dec 22, 2021
-
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
-
dhruv referenced this in commit 6f7e395acc on Jan 26, 2022
-
hebasto referenced this in commit 065b6dbf9d on Jan 30, 2022
-
robot-dreams cross-referenced this on Jan 31, 2022 from issue Abstract out and merge all the magnitude/normalized logic by sipa
-
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
-
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
This is a metadata mirror of the GitHub repository bitcoin-core/secp256k1. This site is not affiliated with GitHub. Content is generated from a GitHub metadata backup.
generated: 2024-10-30 05:15 UTC
More mirrored repositories can be found on mirror.b10c.me