search

rdubois-crypto / FreshCryptoLib

Cryptographic Primitives for Blockchain Systems (solidity, cairo, C and rust)
MIT License
125 stars 22 forks source link

Optimize Skipping of 0-bits In mulmuladd #50

Open nlordell opened 9 months ago

nlordell commented 9 months ago

When investigating the mulmuladd issue, I noticed that at the start of the function, we have a loop to skip index for leading 0s in both u and v.

Currently, it was computing the a value 0bXY (where X bit being set indicates that v{index} is set, and Y bit indicates that u{index} is set) and storing it to a temporary variable (T4) for checking if the leading bit was 0 or not. This PR changes the logic to store it directly to the zz variable instead of having it be recomputed after the loop finishes.

At first, this was implemented by changing the condition of the loop to "is either v{index} or u{index} set?" but computing zz directly should be slightly better on average (if we assume even bit distribution, there is only a 25% chance this will save gas).

Also, eq(X, 0) -> iszero(X) for slightly smaller code and less gas used.

What is the best way to benchmark the difference?

mmv08 commented 9 months ago

What is the best way to benchmark the difference?

Not sure about the project's benchmarking conventions, but perhaps you can run the tests with the --gas-report flag. More on it here: https://book.getfoundry.sh/forge/gas-reports

rdubois-crypto commented 9 months ago

Could you ensure linting and rebase with previous PR to ensure CI's OK?

For the rest OK for me.

nlordell commented 8 months ago

@rdubois-crypto - should be rebased to latest master.