Side channel silent karatsuba / mpn_addmul_2 karatsuba

[Torbjörn Granlund]

"Marco Bodrato" <bodrato at mail.dm.unipi.it> writes:

  Found it:
  https://gmplib.org/list-archives/gmp-devel/2016-December/004502.html

  It used -1, and has an if (in the "Next message (by thread)", Niels
  suggested how to remove it). Funny code :-)

Here is my code for halfword x halfword.  It evaluates in 0, +1, and
infinity.  (I non-obvious property here is that e1hc can become
"negative" but that works just fine.)

void
karascs (ulong p[2], ulong u, ulong v)
{
  ulong a = u >> 32;
  ulong b = u & 0xfffffffful;
  ulong c = v >> 32;
  ulong d = v & 0xfffffffful;

  ulong e0 = b * d;
  ulong ei = a * c;
  ulong e1 =   ((a + b) & 0xfffffffful) * ((c + d) & 0xfffffffful);
  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;

  ulong g = e1 + (e0 >> 32);
  e1hc -= (g < e0);
  g -= e0;
  e1hc -= (g < ei);
  g -= ei;

  p[0] = (g << 32) | (e0 & 0xfffffffful);
  ei += (g >> 32) + e1h + (e1hc << 32);
  p[1] = ei;
}

  Do you think that something alike could be translated to asm and be of
  some use on any arch? But that naive code used the half x half -> full
  register multiplication, you would use the reg x reg -> double-reg one,
  right?

Yes, mp_limb_t[2] x mp_limb_t[2] -> mp_limb_t[4].

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