Side channel silent karatsuba / mpn_addmul_2 karatsuba

[Marco Bodrato]

Ciao,

Il Ven, 14 Dicembre 2018 8:43 am, Torbjörn Granlund ha scritto:
> Here is my code for halfword x halfword.  It evaluates in 0, +1, and

It's a clean code.

> infinity.  (I non-obvious property here is that e1hc can become
> "negative" but that works just fine.)

Yes, in that case ((g >> 32) + e1h)>>32 will be non-zero, so that the
expression ((g >> 32) + e1h + (e1hc << 32)) will give at most a 33 bit
result. Right?

>   ulong e1ha =-((a + b) >> 32)          & ((c + d) & 0xfffffffful);
>   ulong e1hb = ((a + b) & 0xfffffffful) &-((c + d) >> 32);
>   ulong e1hc = ((a + b) >> 32)          & ((c + d) >> 32);
>   ulong e1h = e1ha + e1hb;

when moing from half- to full-word, the carry of e1h will be added to e1hc

>   ei += (g >> 32) + e1h + (e1hc << 32);

and here e1hc will get also the carry from (g >> 32) + e1h ... after that
the value of e1hc will not be "negative" any more :-)

For fullwords there will be more carries to be handled, but choosing the
+1 evaluation seems a good choice.

Ĝis,
m

-- 
http://bodrato.it/