Clean up our disgusting implementations of BN_{,u}{add,sub}(), following

changes made in OpenSSL by Davide Galassi and others, so that one can
actually follow what is going on. There is no performance impact from
this change as the code still does essentially the same thing. There's
a ton of work still to be done to make the BN code less terrible.

ok jsing, kn

1 files changed, 67 insertions, 157 deletions

diff --git a/src/lib/libcrypto/bn/bn_add.c b/src/lib/libcrypto/bn/bn_add.c
index 2e82d280ec..048a136b95 100644
--- a/src/lib/libcrypto/bn/bn_add.c
+++ b/src/lib/libcrypto/bn/bn_add.c
@@ -1,4 +1,4 @@
-/* $OpenBSD: bn_add.c,v 1.12 2018/06/10 19:38:19 tb Exp $ */
+/* $OpenBSD: bn_add.c,v 1.13 2018/07/23 18:07:21 tb Exp $ */
 /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
  * All rights reserved.
  *
@@ -62,61 +62,51 @@
 
 #include "bn_lcl.h"
 
-/* r can == a or b */
 int
 BN_add(BIGNUM *r, const BIGNUM *a, const BIGNUM *b)
 {
-        const BIGNUM *tmp;
-        int a_neg = a->neg, ret;
+        int ret, r_neg;
 
         bn_check_top(a);
         bn_check_top(b);
 
-        /*  a +  b      a+b
-         *  a + -b      a-b
-         * -a +  b      b-a
-         * -a + -b      -(a+b)
-         */
-        if (a_neg ^ b->neg) {
-                /* only one is negative */
-                if (a_neg) {
-                        tmp = a;
-                        a = b;
-                        b = tmp;
-                }
-
-                /* we are now a - b */
-
-                if (BN_ucmp(a, b) < 0) {
-                        if (!BN_usub(r, b, a))
-                                return (0);
-                        r->neg = 1;
+        if (a->neg == b->neg) {
+                r_neg = a->neg;
+                ret = BN_uadd(r, a, b);
+        } else {
+                int cmp = BN_ucmp(a, b);
+
+                if (cmp > 0) {
+                        r_neg = a->neg;
+                        ret = BN_usub(r, a, b);
+                } else if (cmp < 0) {
+                        r_neg = b->neg;
+                        ret = BN_usub(r, b, a);
                 } else {
-                        if (!BN_usub(r, a, b))
-                                return (0);
-                        r->neg = 0;
+                        r_neg = 0;
+                        BN_zero(r);
+                        ret = 1;
                 }
-                return (1);
         }
 
-        ret = BN_uadd(r, a, b);
-        r->neg = a_neg;
+        r->neg = r_neg;
         bn_check_top(r);
         return ret;
 }
 
-/* unsigned add of b to a */
 int
 BN_uadd(BIGNUM *r, const BIGNUM *a, const BIGNUM *b)
 {
         int max, min, dif;
-        BN_ULONG *ap, *bp, *rp, carry, t1, t2;
-        const BIGNUM *tmp;
+        const BN_ULONG *ap, *bp;
+        BN_ULONG *rp, carry, t1, t2;
 
         bn_check_top(a);
         bn_check_top(b);
 
         if (a->top < b->top) {
+                const BIGNUM *tmp;
+
                 tmp = a;
                 a = b;
                 b = tmp;
@@ -137,41 +127,28 @@ BN_uadd(BIGNUM *r, const BIGNUM *a, const BIGNUM *b)
         carry = bn_add_words(rp, ap, bp, min);
         rp += min;
         ap += min;
-        bp += min;
-
-        if (carry) {
-                while (dif) {
-                        dif--;
-                        t1 = *(ap++);
-                        t2 = (t1 + 1) & BN_MASK2;
-                        *(rp++) = t2;
-                        if (t2) {
-                                carry = 0;
-                                break;
-                        }
-                }
-                if (carry) {
-                        /* carry != 0 => dif == 0 */
-                        *rp = 1;
-                        r->top++;
-                }
+
+        while (dif) {
+                dif--;
+                t1 = *(ap++);
+                t2 = (t1 + carry) & BN_MASK2;
+                *(rp++) = t2;
+                carry &= (t2 == 0);
         }
-        if (dif && rp != ap)
-                while (dif--)
-                        /* copy remaining words if ap != rp */
-                        *(rp++) = *(ap++);
+        *rp = carry;
+        r->top += carry;
+
         r->neg = 0;
         bn_check_top(r);
         return 1;
 }
 
-/* unsigned subtraction of b from a, a must be larger than b. */
 int
 BN_usub(BIGNUM *r, const BIGNUM *a, const BIGNUM *b)
 {
         int max, min, dif;
-        BN_ULONG t1, t2, *ap, *bp, *rp;
-        int i, carry;
+        const BN_ULONG *ap, *bp;
+        BN_ULONG t1, t2, borrow, *rp;
 
         bn_check_top(a);
         bn_check_top(b);
@@ -180,134 +157,67 @@ BN_usub(BIGNUM *r, const BIGNUM *a, const BIGNUM *b)
         min = b->top;
         dif = max - min;
 
-        if (dif < 0)    /* hmm... should not be happening */
-        {
+        if (dif < 0) {
                 BNerror(BN_R_ARG2_LT_ARG3);
-                return (0);
+                return 0;
         }
 
         if (bn_wexpand(r, max) == NULL)
-                return (0);
+                return 0;
 
         ap = a->d;
         bp = b->d;
         rp = r->d;
 
-#if 1
-        carry = 0;
-        for (i = min; i != 0; i--) {
-                t1= *(ap++);
-                t2= *(bp++);
-                if (carry) {
-                        carry = (t1 <= t2);
-                        t1 = (t1 - t2 - 1)&BN_MASK2;
-                } else {
-                        carry = (t1 < t2);
-                        t1 = (t1 - t2)&BN_MASK2;
-                }
-                *(rp++) = t1&BN_MASK2;
-        }
-#else
-        carry = bn_sub_words(rp, ap, bp, min);
+        borrow = bn_sub_words(rp, ap, bp, min);
         ap += min;
-        bp += min;
         rp += min;
-#endif
-        if (carry) /* subtracted */
-        {
-                if (!dif)
-                        /* error: a < b */
-                        return 0;
-                while (dif) {
-                        dif--;
-                        t1 = *(ap++);
-                        t2 = (t1 - 1)&BN_MASK2;
-                        *(rp++) = t2;
-                        if (t1)
-                                break;
-                }
-        }
-#if 0
-        memcpy(rp, ap, sizeof(*rp)*(max - i));
-#else
-        if (rp != ap) {
-                for (;;) {
-                        if (!dif--)
-                                break;
-                        rp[0] = ap[0];
-                        if (!dif--)
-                                break;
-                        rp[1] = ap[1];
-                        if (!dif--)
-                                break;
-                        rp[2] = ap[2];
-                        if (!dif--)
-                                break;
-                        rp[3] = ap[3];
-                        rp += 4;
-                        ap += 4;
-                }
+
+        while (dif) {
+                dif--;
+                t1 = *(ap++);
+                t2 = (t1 - borrow) & BN_MASK2;
+                *(rp++) = t2;
+                borrow &= (t1 == 0);
         }
-#endif
+
+        while (max > 0 && *--rp == 0)
+                max--;
 
         r->top = max;
         r->neg = 0;
         bn_correct_top(r);
-        return (1);
+        return 1;
 }
 
 int
 BN_sub(BIGNUM *r, const BIGNUM *a, const BIGNUM *b)
 {
-        int max;
-        int add = 0, neg = 0;
-        const BIGNUM *tmp;
+        int ret, r_neg;
 
         bn_check_top(a);
         bn_check_top(b);
 
-        /*  a -  b      a-b
-         *  a - -b      a+b
-         * -a -  b      -(a+b)
-         * -a - -b      b-a
-         */
-        if (a->neg) {
-                if (b->neg) {
-                        tmp = a;
-                        a = b;
-                        b = tmp;
-                } else {
-                        add = 1;
-                        neg = 1;
-                }
+        if (a->neg != b->neg) {
+                r_neg = a->neg;
+                ret = BN_uadd(r, a, b);
         } else {
-                if (b->neg) {
-                        add = 1;
-                        neg = 0;
+                int cmp = BN_ucmp(a, b);
+
+                if (cmp > 0) {
+                        r_neg = a->neg;
+                        ret = BN_usub(r, a, b);
+                } else if (cmp < 0) {
+                        r_neg = !b->neg;
+                        ret = BN_usub(r, b, a);
+                } else {
+                        r_neg = 0;
+                        BN_zero(r);
+                        ret = 1;
                 }
         }
 
-        if (add) {
-                if (!BN_uadd(r, a, b))
-                        return (0);
-                r->neg = neg;
-                return (1);
-        }
-
-        /* We are actually doing a - b :-) */
-
-        max = (a->top > b->top) ? a->top : b->top;
-        if (bn_wexpand(r, max) == NULL)
-                return (0);
-        if (BN_ucmp(a, b) < 0) {
-                if (!BN_usub(r, b, a))
-                        return (0);
-                r->neg = 1;
-        } else {
-                if (!BN_usub(r, a, b))
-                        return (0);
-                r->neg = 0;
-        }
+        r->neg = r_neg;
         bn_check_top(r);
-        return (1);
+        return ret;
 }