Implementations for scalar without data-dependent branches #77

pull sipa wants to merge 1 commits into bitcoin-core:master from sipa:scalarc changing 10 files +1194 −57

sipa commented at 11:29 AM on October 29, 2014: contributor

No description provided.
sipa force-pushed on Oct 29, 2014
sipa force-pushed on Oct 29, 2014
sipa force-pushed on Oct 29, 2014
sipa commented at 4:12 PM on October 29, 2014: contributor

The code generated by the __int128 based version contains jumps :(
gmaxwell commented at 11:04 PM on October 29, 2014: contributor

The jmps are from the uint128_t comparisons. (I inquired in the GCC channel, ... Seems GCC needs but doesn't have specialized code for x86_64 to generate the (almost certantly faster) branchless version. of course I got the expected finger wagging about ever expecting to get constant time behavior from compiled code :) ).

Hopefully we can just union uint128_t and two int64_t and construct the comparison manually without resorting to assembly.
sipa force-pushed on Oct 30, 2014
sipa renamed this:
~~Constant-time scalar implementation~~
Implementations for scalar without data-dependent branches
on Oct 30, 2014
sipa commented at 1:57 PM on October 30, 2014: contributor

Rebased on top of #79, and reworked the accumulators to avoid comparisons on double-register integers. Both the 8x32 version on x86 and the 4x64 version on x86_64 now compile to code without jumps.
sipa force-pushed on Oct 31, 2014
sipa commented at 9:05 AM on October 31, 2014: contributor

@gmaxwell added some more
sipa force-pushed on Oct 31, 2014
sipa force-pushed on Nov 3, 2014
Implementations for scalar without data-dependent branches. 1d52a8b155
sipa force-pushed on Nov 4, 2014
gmaxwell commented at 11:37 PM on November 4, 2014: contributor

ACK.
sipa merged this on Nov 5, 2014
sipa closed this on Nov 5, 2014
sipa referenced this in commit 985fd63a73 on Nov 5, 2014

Contributors

sipa

gmaxwell

Linked (view graph)

#81 Use Montgomery multiplications in scalar inverses