crypto/bn/bn_add.c

   1 /*
   2  * Copyright 1995-2016 The OpenSSL Project Authors. All Rights Reserved.
   3  *
   4  * Licensed under the OpenSSL license (the "License").  You may not use
   5  * this file except in compliance with the License.  You can obtain a copy
   6  * in the file LICENSE in the source distribution or at
   7  * https://www.openssl.org/source/license.html
   8  */
   9
  10 #include "internal/cryptlib.h"
  11 #include "bn_lcl.h"
  12
  13 /* r can == a or b */
  14 int BN_add(BIGNUM *r, const BIGNUM *a, const BIGNUM *b)
  15 {
  16     const BIGNUM *tmp;
  17     int a_neg = a->neg, ret;
  18
  19     bn_check_top(a);
  20     bn_check_top(b);
  21
  22     /*-
  23      *  a +  b      a+b
  24      *  a + -b      a-b
  25      * -a +  b      b-a
  26      * -a + -b      -(a+b)
  27      */
  28     if (a_neg ^ b->neg) {
  29         /* only one is negative */
  30         if (a_neg) {
  31             tmp = a;
  32             a = b;
  33             b = tmp;
  34         }
  35
  36         /* we are now a - b */
  37
  38         if (BN_ucmp(a, b) < 0) {
  39             if (!BN_usub(r, b, a))
  40                 return (0);
  41             r->neg = 1;
  42         } else {
  43             if (!BN_usub(r, a, b))
  44                 return (0);
  45             r->neg = 0;
  46         }
  47         return (1);
  48     }
  49
  50     ret = BN_uadd(r, a, b);
  51     r->neg = a_neg;
  52     bn_check_top(r);
  53     return ret;
  54 }
  55
  56 /* unsigned add of b to a */
  57 int BN_uadd(BIGNUM *r, const BIGNUM *a, const BIGNUM *b)
  58 {
  59     int max, min, dif;
  60     const BN_ULONG *ap, *bp;
  61     BN_ULONG *rp, carry, t1, t2;
  62     const BIGNUM *tmp;
  63
  64     bn_check_top(a);
  65     bn_check_top(b);
  66
  67     if (a->top < b->top) {
  68         tmp = a;
  69         a = b;
  70         b = tmp;
  71     }
  72     max = a->top;
  73     min = b->top;
  74     dif = max - min;
  75
  76     if (bn_wexpand(r, max + 1) == NULL)
  77         return 0;
  78
  79     r->top = max;
  80
  81     ap = a->d;
  82     bp = b->d;
  83     rp = r->d;
  84
  85     carry = bn_add_words(rp, ap, bp, min);
  86     rp += min;
  87     ap += min;
  88     bp += min;
  89
  90     if (carry) {
  91         while (dif) {
  92             dif--;
  93             t1 = *(ap++);
  94             t2 = (t1 + 1) & BN_MASK2;
  95             *(rp++) = t2;
  96             if (t2) {
  97                 carry = 0;
  98                 break;
  99             }
 100         }
 101         if (carry) {
 102             /* carry != 0 => dif == 0 */
 103             *rp = 1;
 104             r->top++;
 105         }
 106     }
 107     if (dif && rp != ap)
 108         while (dif--)
 109             /* copy remaining words if ap != rp */
 110             *(rp++) = *(ap++);
 111     r->neg = 0;
 112     bn_check_top(r);
 113     return 1;
 114 }
 115
 116 /* unsigned subtraction of b from a, a must be larger than b. */
 117 int BN_usub(BIGNUM *r, const BIGNUM *a, const BIGNUM *b)
 118 {
 119     int max, min, dif;
 120     register BN_ULONG t1, t2, *rp;
 121     register const BN_ULONG *ap, *bp;
 122     int i, carry;
 123
 124     bn_check_top(a);
 125     bn_check_top(b);
 126
 127     max = a->top;
 128     min = b->top;
 129     dif = max - min;
 130
 131     if (dif < 0) {              /* hmm... should not be happening */
 132         BNerr(BN_F_BN_USUB, BN_R_ARG2_LT_ARG3);
 133         return (0);
 134     }
 135
 136     if (bn_wexpand(r, max) == NULL)
 137         return (0);
 138
 139     ap = a->d;
 140     bp = b->d;
 141     rp = r->d;
 142
 143 #if 1
 144     carry = 0;
 145     for (i = min; i != 0; i--) {
 146         t1 = *(ap++);
 147         t2 = *(bp++);
 148         if (carry) {
 149             carry = (t1 <= t2);
 150             t1 = (t1 - t2 - 1) & BN_MASK2;
 151         } else {
 152             carry = (t1 < t2);
 153             t1 = (t1 - t2) & BN_MASK2;
 154         }
 155         *(rp++) = t1 & BN_MASK2;
 156     }
 157 #else
 158     carry = bn_sub_words(rp, ap, bp, min);
 159     ap += min;
 160     bp += min;
 161     rp += min;
 162 #endif
 163     if (carry) {                /* subtracted */
 164         if (!dif)
 165             /* error: a < b */
 166             return 0;
 167         while (dif) {
 168             dif--;
 169             t1 = *(ap++);
 170             t2 = (t1 - 1) & BN_MASK2;
 171             *(rp++) = t2;
 172             if (t1)
 173                 break;
 174         }
 175     }
 176     if (dif && ap != rp)
 177         memcpy(rp, ap, sizeof(*rp) * dif);
 178
 179     r->top = max;
 180     r->neg = 0;
 181     bn_correct_top(r);
 182     return (1);
 183 }
 184
 185 int BN_sub(BIGNUM *r, const BIGNUM *a, const BIGNUM *b)
 186 {
 187     int max;
 188     int add = 0, neg = 0;
 189     const BIGNUM *tmp;
 190
 191     bn_check_top(a);
 192     bn_check_top(b);
 193
 194     /*-
 195      *  a -  b      a-b
 196      *  a - -b      a+b
 197      * -a -  b      -(a+b)
 198      * -a - -b      b-a
 199      */
 200     if (a->neg) {
 201         if (b->neg) {
 202             tmp = a;
 203             a = b;
 204             b = tmp;
 205         } else {
 206             add = 1;
 207             neg = 1;
 208         }
 209     } else {
 210         if (b->neg) {
 211             add = 1;
 212             neg = 0;
 213         }
 214     }
 215
 216     if (add) {
 217         if (!BN_uadd(r, a, b))
 218             return (0);
 219         r->neg = neg;
 220         return (1);
 221     }
 222
 223     /* We are actually doing a - b :-) */
 224
 225     max = (a->top > b->top) ? a->top : b->top;
 226     if (bn_wexpand(r, max) == NULL)
 227         return (0);
 228     if (BN_ucmp(a, b) < 0) {
 229         if (!BN_usub(r, b, a))
 230             return (0);
 231         r->neg = 1;
 232     } else {
 233         if (!BN_usub(r, a, b))
 234             return (0);
 235         r->neg = 0;
 236     }
 237     bn_check_top(r);
 238     return (1);
 239 }