Running mpn_add_n at less than 1 cycle/limb

[Torbjörn Granlund]

Marc Glisse <marc.glisse at inria.fr> writes:

  Why though?
  Applications that use GMP for crypto in a way where side-channel
  attacks make sense are probably a small minority of all GMP uses, so
  that penalizes all the others. And for the applications that care,
  mpn_sec_* sends a much clearer message about the guarantees provided
  by the function. In most cases, mpn_add_n and mpn_sec_add_n would just
  point to the same code, which should have minimal impact on the size
  of the library.

I think you have a strong point.

It would be cool to code up a modern (i.e., not Pentium4-tailored)
mpn_add_n which breaks the dependency chain between blocks of limbs.

I suppose 4-limb blocks would be a start, and that one every 4th limb
checks if a plain add and the adc from the previous block yield
different carry-out, and if they do, jump to a fixup function (or use
cmov, perhaps).

I think one would need one add and four adc per such 4/limb block.  The
add would be for the top limb of the previous 4/limb block.

The handling of one limb needs at a minimum a load (aka mov from
memory), and adc from memory, and a store (aka mov to memory).  If we
have 4-way instruction issue, we would need >0.75 cycles/limb, and with
6-way issue we sould need >0.6 cycles/limb.  Of course, the code for
checking for a rippling carry (perhaps cmp+jCC or perhaps just a cmovz)
as well as loop control add some overhead.

It is pretty cool that we could add more than 1 limb pair per cycle on
an arch where add-with-carry need one cycle.

Perhaps we could similarly speed up the really important loops, i.e.,
mpn_addmul_[k] on CPUs with good mul/mulx thoughput?


-- 
Torbjörn
Please encrypt, key id 0xC8601622