WIP WIP WIP 5x64 field representation #967

1. 
   sipa commented at 0:25 am on July 24, 2021: contributor

   This swaps out the 5x52 field with a 5x64 one, including both inline and external x86_64 asm code (by @kn-cs).

   I’m just opening this to see if it doesn’t break anything on the various platforms we have.

2. sipa force-pushed on Jul 24, 2021
3. sipa force-pushed on Jul 24, 2021
4. sipa force-pushed on Jul 25, 2021
5. sipa force-pushed on Aug 5, 2021
6. sipa force-pushed on Aug 5, 2021
7. sipa force-pushed on Aug 5, 2021
8. sipa force-pushed on Aug 23, 2021
9. sipa force-pushed on Aug 23, 2021
10. Add 'precomputed' normalization level e85c6f67b4
11. Start using precomputed field operations fbe87294ff
12. Switch to 5x64 field representation f23d556aef
13. Add inline x86_64 asm for 5x64 field e82eb9655e
14. Add optimized asm for aarch64 and x86_64 a57e05b252
15. Test extra asm f7d4565f8d
16. sipa force-pushed on Aug 24, 2021
17. 
    sipa commented at 7:57 pm on October 17, 2021: contributor

    So to give an idea of the status here:

    • The code works, is generally a speedup, and is unlikely to change much; if it does, it’s probably restricted to just better asm code
    • There is an issue on macOS to figure out (linking fails; I wonder if the asm/linker detect platform-specific instructions, and need some kind of magic runtime detection annotation?)
    • As is, this PR removes the old 5x52 representation. That may be undesirable, as at least on some (uncommon) platforms, the new code is (slightly) slower. This may be even more the case with #810 merged now.
    • It’s an open question how this is supposed to be reviewed or otherwise gained confidence in. I know there are formal methods of proving semantics of asm code, but I don’t have experience with them. An alternative is adding lots of high-level description to the asm code to make it readable.
    • This PR leaves the decision on which repr/impl to use up to the ./configure step. That’s useful in some settings, and enough to enable testing, but not what we want for normal production usage. I’m fine with that, but perhaps people want a clearer plan on how runtime autodetection etc would work before proceeding?
18. 
    real-or-random commented at 12:24 pm on October 18, 2021: contributor

    There is an issue on macOS to figure out (linking fails; I wonder if the asm/linker detect platform-specific instructions, and need some kind of magic runtime detection annotation?)

    According to the CI output, it’s the assembler that fails because it does not like the .type directive. A shot in the dark is to simply remove them on MacOS (indicators: https://github.com/briansmith/ring/issues/312#issuecomment-274581871 and https://code.woboq.org/llvm/compiler-rt/lib/builtins/assembly.h.html). I think if you rename .s to .S you can use the C preprocessor with things like #ifdef __APPLE__.

19. elichai cross-referenced this on Nov 3, 2021 from issue New context API by real-or-random
20. sipa cross-referenced this on Jan 1, 2022 from issue Try a non-uniform group law (e.g., for ecmult_gen)? by real-or-random
21. sipa cross-referenced this on Jan 3, 2022 from issue Separate magnitude/normalization/... checking/propagation from implementations by sipa
22. sipa cross-referenced this on Jan 29, 2022 from issue Abstract out and merge all the magnitude/normalized logic by sipa
23. sipa referenced this in commit c63ec88ebf on May 11, 2023
24. sipa cross-referenced this on May 23, 2023 from issue fiat-crypto + CryptOpt tracking issue by real-or-random

Contributors
sipa real-or-random