Before:
- a separate Word element allocation of the underlying Vector<Word> was
necessary for every new word in a multi-word shift
- two additional temporary UnsignedBigInteger buffers were allocated
and passed through, including in downstream calls (e.g. Multiplication)
- an additional allocation and word shift for the carry
- FIXME note seems to point to some of these issues
After:
- main change is in LibCrypto/BigInt/Algorithms/BitwiseOperations.cpp
- one single allocation per call, using shift_left_by_n_words
- only the input "number" and "output" need to be allocated by the
caller
- downstream calls are adapted not to allocate or pass temporary
buffers
- noticeable performance improvement when running TestBigInteger:
0.41-0.42s (before) to 0.28-0.29s (after) Intel Core i9 laptop
Bonus: remove unused variables from UnsignedBigInteger::divided_by
- These were likely cut-and-paste artifacts from
UnsignedBigInteger::multiplied_by; not caught by "unused-varible".
NOTE: making this change in a separate commit than shift_right, even if
it touches the same file BitwiseOperations.cpp since:
- it is a "bonus" addition: not necessary for fixing the shift_right
bug, but logically unrelated to the shift_right code
- it brings a chain of downstream interface modifications (7 files),
unrelated to shift_right
This adds a thin wrapper to LibCrypto for generating cryptographically
secure random values and replaces current usages of PRNG within
LibCrypto as well.
The previous implementation of `ModularInverse` was flaky and did not
compute the correct value in many occasions, especially with big numbers
like in RSA.
Also added a bunch of tests with big numbers.
These changes are arbitrarily divided into multiple commits to make it
easier to find potentially introduced bugs with git bisect.Everything:
The modifications in this commit were automatically made using the
following command:
find . -name '*.cpp' -exec sed -i -E 's/dbg\(\) << ("[^"{]*");/dbgln\(\1\);/' {} \;
If they use up so much stack space, contain (sometimes several) loops, and take
a noticable amount of time anyway, then 'inline' is probably going to be ignored
by the compiler anyway.
