Our current implementations of BN_{,u}{add,sub}() are plain disgusting.
OpenSSL cleaned this up quite a bit recently -- still under
'(the "License")' -- and now you can actually follow what is going on.
There should be no performance impact from this change, the code is
doing essentially the same thing, just in a more orderly way.
For review, note that are two pairs of functions, BN_{add,sub}() and
BN_{uadd,usub}() which have similar changes. I recommend just applying
the diff and looking at the resulting file, the new functions are
pretty obvious.
Index: bn/bn_add.c
===================================================================
RCS file: /var/cvs/src/lib/libcrypto/bn/bn_add.c,v
retrieving revision 1.12
diff -u -p -r1.12 bn_add.c
--- bn/bn_add.c 10 Jun 2018 19:38:19 -0000 1.12
+++ bn/bn_add.c 11 Jul 2018 04:45:16 -0000
@@ -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 (a->neg == b->neg) {
+ r_neg = a->neg;
+ ret = BN_uadd(r, a, b);
+ } else {
+ int cmp = BN_ucmp(a, b);
- if (BN_ucmp(a, b) < 0) {
- if (!BN_usub(r, b, a))
- return (0);
- r->neg = 1;
+ 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, cons
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, cons
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 (add) {
- if (!BN_uadd(r, a, b))
- return (0);
- r->neg = neg;
- return (1);
+ 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;
+ }
}
- /* 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;
}
