Improve checks at top of _fe_negate methods #816

1. 
   peterdettman commented at 7:37 am on September 14, 2020: contributor

   In 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.
2. 
   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.

3. 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
4. 
   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?

5. 
   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) and m = 2048 (for 5x52), but I think this is OK / expected because the magnitude of the result will be m + 1, so the final fe_verify check would have failed anyway. Maybe it’s worth explicitly adding an extra check that m isn’t too big, but I don’t have a strong opinion about this.

6. peterdettman force-pushed on Dec 6, 2021
7. 
   peterdettman commented at 4:19 am on December 6, 2021: contributor

   @real-or-random Rebased.
8. 
   robot-dreams commented at 4:12 pm on December 6, 2021: contributor

   ACK 3e03435ba36f07ef956d4bfb71a3fa580ce29326, no difference aside from rebase
9. Improve checks at top of _fe_negate methods 515e7953ca
10. peterdettman force-pushed on Dec 21, 2021
11. 
    sipa commented at 0:26 am on December 22, 2021: contributor

    utACK 515e7953cab4eb3be063fa3991e4e0663d3f04ae
12. 
    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)

13. real-or-random merged this on Dec 22, 2021
14. real-or-random closed this on Dec 22, 2021

    ---

15. real-or-random referenced this in commit 0b83b203e1 on Dec 22, 2021
16. jonasnick cross-referenced this on Jan 2, 2022 from issue Sync Upstream by jonasnick
17. real-or-random referenced this in commit 21e2d65b79 on Jan 5, 2022
18. dhruv referenced this in commit 6f7e395acc on Jan 26, 2022
19. hebasto referenced this in commit 065b6dbf9d on Jan 30, 2022
20. robot-dreams cross-referenced this on Jan 31, 2022 from issue Abstract out and merge all the magnitude/normalized logic by sipa
21. dhruv referenced this in commit 139d4b881e on Feb 1, 2022
22. fanquake referenced this in commit 8f8631d826 on Mar 17, 2022
23. fanquake referenced this in commit 4bb1d7e62a on Mar 17, 2022
24. fanquake referenced this in commit 465d05253a on Mar 30, 2022
25. stratospher referenced this in commit 4d5afc9767 on Apr 3, 2022
26. stratospher referenced this in commit 5b18493cfa on Apr 3, 2022
27. fanquake referenced this in commit afb7a6fe06 on Apr 6, 2022
28. gwillen referenced this in commit 35d6112a72 on May 25, 2022
29. patricklodder referenced this in commit 21badcf9d2 on Jul 25, 2022
30. patricklodder referenced this in commit 03002a9013 on Jul 28, 2022
31. janus referenced this in commit 3a0652a777 on Aug 4, 2022
32. str4d referenced this in commit 522190d5c3 on Apr 21, 2023
33. vmta referenced this in commit e1120c94a1 on Jun 4, 2023
34. vmta referenced this in commit 8f03457eed on Jul 1, 2023

Contributors
peterdettman robot-dreams real-or-random sipa