Add combined conditional add-or-subtract

3 files changed, 41 insertions, 5 deletions

diff --git a/src/lib/math/mp/mp_core.cpp b/src/lib/math/mp/mp_core.cpp
index 9f2999929..2ae65e508 100644
--- a/src/lib/math/mp/mp_core.cpp
+++ b/src/lib/math/mp/mp_core.cpp
@@ -92,6 +92,34 @@ word bigint_cnd_sub(word cnd, word x[], const word y[], size_t size)
    return carry & mask;
    }
 
+void bigint_cnd_addsub(word mask, word x[], const word y[], size_t size)
+   {
+   const size_t blocks = size - (size % 8);
+
+   word carry = 0;
+   word borrow = 0;
+
+   word t0[8] = { 0 };
+   word t1[8] = { 0 };
+
+   for(size_t i = 0; i != blocks; i += 8)
+      {
+      carry = word8_add3(t0, x + i, y + i, carry);
+      borrow = word8_sub3(t1, x + i, y + i, borrow);
+
+      for(size_t j = 0; j != 8; ++j)
+         x[i+j] = CT::select(mask, t0[j], t1[j]);
+      }
+
+   for(size_t i = blocks; i != size; ++i)
+      {
+      const word a = word_add(x[i], y[i], &carry);
+      const word s = word_sub(x[i], y[i], &borrow);
+
+      x[i] = CT::select(mask, a, s);
+      }
+   }
+
 void bigint_cnd_abs(word cnd, word x[], size_t size)
    {
    const word mask = CT::expand_mask(cnd);
diff --git a/src/lib/math/mp/mp_core.h b/src/lib/math/mp/mp_core.h
index 9d8ad84db..9430c3753 100644
--- a/src/lib/math/mp/mp_core.h
+++ b/src/lib/math/mp/mp_core.h
@@ -27,20 +27,29 @@ BOTAN_TEST_API
 void bigint_cnd_swap(word cnd, word x[], word y[], size_t size);
 
 /*
-* If cond > 0 adds x[0:size] to y[0:size] and returns carry
+* If cond > 0 adds x[0:size] and y[0:size] and returns carry
 * Runs in constant time
 */
 BOTAN_TEST_API
 word bigint_cnd_add(word cnd, word x[], const word y[], size_t size);
 
 /*
-* If cond > 0 subs x[0:size] to y[0:size] and returns borrow
+* If cond > 0 subtracts x[0:size] and y[0:size] and returns borrow
 * Runs in constant time
 */
 BOTAN_TEST_API
 word bigint_cnd_sub(word cnd, word x[], const word y[], size_t size);
 
 /*
+* Equivalent to
+*   bigint_cnd_add( mask, x, y, size);
+*   bigint_cnd_sub(~mask, x, y, size);
+*
+* Mask must be either 0 or all 1 bits
+*/
+void bigint_cnd_addsub(word mask, word x[], const word y[], size_t size);
+
+/*
 * 2s complement absolute value
 * If cond > 0 sets x to ~x + 1
 * Runs in constant time
diff --git a/src/lib/math/mp/mp_karat.cpp b/src/lib/math/mp/mp_karat.cpp
index 27ae349ef..69e2ae665 100644
--- a/src/lib/math/mp/mp_karat.cpp
+++ b/src/lib/math/mp/mp_karat.cpp
@@ -140,10 +140,9 @@ void karatsuba_mul(word z[], const word x[], const word y[], size_t N,
 
    clear_mem(workspace + N, N2);
 
-   const word is_negative = CT::expand_mask<word>(cmp0 != cmp1);
+   const word neg_mask = CT::is_equal<word>(cmp0, cmp1);
 
-   bigint_cnd_sub(is_negative,  z + N2, workspace, 2*N-N2);
-   bigint_cnd_add(~is_negative, z + N2, workspace, 2*N-N2);
+   bigint_cnd_addsub(neg_mask, z + N2, workspace, 2*N-N2);
    }
 
 /*