src/third_party/boringssl/src/crypto/bn/add.c

   1 /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
   2  * All rights reserved.
   3  *
   4  * This package is an SSL implementation written
   5  * by Eric Young (eay@cryptsoft.com).
   6  * The implementation was written so as to conform with Netscapes SSL.
   7  *
   8  * This library is free for commercial and non-commercial use as long as
   9  * the following conditions are aheared to.  The following conditions
  10  * apply to all code found in this distribution, be it the RC4, RSA,
  11  * lhash, DES, etc., code; not just the SSL code.  The SSL documentation
  12  * included with this distribution is covered by the same copyright terms
  13  * except that the holder is Tim Hudson (tjh@cryptsoft.com).
  14  *
  15  * Copyright remains Eric Young's, and as such any Copyright notices in
  16  * the code are not to be removed.
  17  * If this package is used in a product, Eric Young should be given attribution
  18  * as the author of the parts of the library used.
  19  * This can be in the form of a textual message at program startup or
  20  * in documentation (online or textual) provided with the package.
  21  *
  22  * Redistribution and use in source and binary forms, with or without
  23  * modification, are permitted provided that the following conditions
  24  * are met:
  25  * 1. Redistributions of source code must retain the copyright
  26  *    notice, this list of conditions and the following disclaimer.
  27  * 2. Redistributions in binary form must reproduce the above copyright
  28  *    notice, this list of conditions and the following disclaimer in the
  29  *    documentation and/or other materials provided with the distribution.
  30  * 3. All advertising materials mentioning features or use of this software
  31  *    must display the following acknowledgement:
  32  *    "This product includes cryptographic software written by
  33  *     Eric Young (eay@cryptsoft.com)"
  34  *    The word 'cryptographic' can be left out if the rouines from the library
  35  *    being used are not cryptographic related :-).
  36  * 4. If you include any Windows specific code (or a derivative thereof) from
  37  *    the apps directory (application code) you must include an acknowledgement:
  38  *    "This product includes software written by Tim Hudson (tjh@cryptsoft.com)"
  39  *
  40  * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND
  41  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  42  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  43  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
  44  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  45  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  46  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  47  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  48  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  49  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  50  * SUCH DAMAGE.
  51  *
  52  * The licence and distribution terms for any publically available version or
  53  * derivative of this code cannot be changed.  i.e. this code cannot simply be
  54  * copied and put under another distribution licence
  55  * [including the GNU Public Licence.] */
  56
  57 #include <openssl/bn.h>
  58
  59 #include <openssl/err.h>
  60 #include <openssl/mem.h>
  61
  62 #include "internal.h"
  63
  64
  65 int BN_add(BIGNUM *r, const BIGNUM *a, const BIGNUM *b) {
  66   const BIGNUM *tmp;
  67   int a_neg = a->neg, ret;
  68
  69   /*  a +  b    a+b
  70    *  a + -b    a-b
  71    * -a +  b    b-a
  72    * -a + -b    -(a+b)
  73    */
  74   if (a_neg ^ b->neg) {
  75     /* only one is negative */
  76     if (a_neg) {
  77       tmp = a;
  78       a = b;
  79       b = tmp;
  80     }
  81
  82     /* we are now a - b */
  83     if (BN_ucmp(a, b) < 0) {
  84       if (!BN_usub(r, b, a)) {
  85         return 0;
  86       }
  87       r->neg = 1;
  88     } else {
  89       if (!BN_usub(r, a, b)) {
  90         return 0;
  91       }
  92       r->neg = 0;
  93     }
  94     return 1;
  95   }
  96
  97   ret = BN_uadd(r, a, b);
  98   r->neg = a_neg;
  99   return ret;
 100 }
 101
 102 int BN_uadd(BIGNUM *r, const BIGNUM *a, const BIGNUM *b) {
 103   int max, min, dif;
 104   BN_ULONG *ap, *bp, *rp, carry, t1, t2;
 105   const BIGNUM *tmp;
 106
 107   if (a->top < b->top) {
 108     tmp = a;
 109     a = b;
 110     b = tmp;
 111   }
 112   max = a->top;
 113   min = b->top;
 114   dif = max - min;
 115
 116   if (bn_wexpand(r, max + 1) == NULL) {
 117     return 0;
 118   }
 119
 120   r->top = max;
 121
 122   ap = a->d;
 123   bp = b->d;
 124   rp = r->d;
 125
 126   carry = bn_add_words(rp, ap, bp, min);
 127   rp += min;
 128   ap += min;
 129   bp += min;
 130
 131   if (carry) {
 132     while (dif) {
 133       dif--;
 134       t1 = *(ap++);
 135       t2 = (t1 + 1) & BN_MASK2;
 136       *(rp++) = t2;
 137       if (t2) {
 138         carry = 0;
 139         break;
 140       }
 141     }
 142     if (carry) {
 143       /* carry != 0 => dif == 0 */
 144       *rp = 1;
 145       r->top++;
 146     }
 147   }
 148
 149   if (dif && rp != ap) {
 150     while (dif--) {
 151       /* copy remaining words if ap != rp */
 152       *(rp++) = *(ap++);
 153     }
 154   }
 155
 156   r->neg = 0;
 157   return 1;
 158 }
 159
 160 int BN_add_word(BIGNUM *a, BN_ULONG w) {
 161   BN_ULONG l;
 162   int i;
 163
 164   w &= BN_MASK2;
 165
 166   /* degenerate case: w is zero */
 167   if (!w) {
 168     return 1;
 169   }
 170
 171   /* degenerate case: a is zero */
 172   if (BN_is_zero(a)) {
 173     return BN_set_word(a, w);
 174   }
 175
 176   /* handle 'a' when negative */
 177   if (a->neg) {
 178     a->neg = 0;
 179     i = BN_sub_word(a, w);
 180     if (!BN_is_zero(a)) {
 181       a->neg = !(a->neg);
 182     }
 183     return i;
 184   }
 185
 186   for (i = 0; w != 0 && i < a->top; i++) {
 187     a->d[i] = l = (a->d[i] + w) & BN_MASK2;
 188     w = (w > l) ? 1 : 0;
 189   }
 190
 191   if (w && i == a->top) {
 192     if (bn_wexpand(a, a->top + 1) == NULL) {
 193       return 0;
 194     }
 195     a->top++;
 196     a->d[i] = w;
 197   }
 198
 199   return 1;
 200 }
 201
 202 int BN_sub(BIGNUM *r, const BIGNUM *a, const BIGNUM *b) {
 203   int max;
 204   int add = 0, neg = 0;
 205   const BIGNUM *tmp;
 206
 207   /*  a -  b    a-b
 208    *  a - -b    a+b
 209    * -a -  b    -(a+b)
 210    * -a - -b    b-a
 211    */
 212   if (a->neg) {
 213     if (b->neg) {
 214       tmp = a;
 215       a = b;
 216       b = tmp;
 217     } else {
 218       add = 1;
 219       neg = 1;
 220     }
 221   } else {
 222     if (b->neg) {
 223       add = 1;
 224       neg = 0;
 225     }
 226   }
 227
 228   if (add) {
 229     if (!BN_uadd(r, a, b)) {
 230       return 0;
 231     }
 232
 233     r->neg = neg;
 234     return 1;
 235   }
 236
 237   /* We are actually doing a - b :-) */
 238
 239   max = (a->top > b->top) ? a->top : b->top;
 240   if (bn_wexpand(r, max) == NULL) {
 241     return 0;
 242   }
 243
 244   if (BN_ucmp(a, b) < 0) {
 245     if (!BN_usub(r, b, a)) {
 246       return 0;
 247     }
 248     r->neg = 1;
 249   } else {
 250     if (!BN_usub(r, a, b)) {
 251       return 0;
 252     }
 253     r->neg = 0;
 254   }
 255
 256   return 1;
 257 }
 258
 259 int BN_usub(BIGNUM *r, const BIGNUM *a, const BIGNUM *b) {
 260   int max, min, dif;
 261   register BN_ULONG t1, t2, *ap, *bp, *rp;
 262   int i, carry;
 263
 264   max = a->top;
 265   min = b->top;
 266   dif = max - min;
 267
 268   if (dif < 0) /* hmm... should not be happening */
 269   {
 270     OPENSSL_PUT_ERROR(BN, BN_usub, BN_R_ARG2_LT_ARG3);
 271     return 0;
 272   }
 273
 274   if (bn_wexpand(r, max) == NULL) {
 275     return 0;
 276   }
 277
 278   ap = a->d;
 279   bp = b->d;
 280   rp = r->d;
 281
 282   carry = 0;
 283   for (i = min; i != 0; i--) {
 284     t1 = *(ap++);
 285     t2 = *(bp++);
 286     if (carry) {
 287       carry = (t1 <= t2);
 288       t1 = (t1 - t2 - 1) & BN_MASK2;
 289     } else {
 290       carry = (t1 < t2);
 291       t1 = (t1 - t2) & BN_MASK2;
 292     }
 293     *(rp++) = t1 & BN_MASK2;
 294   }
 295
 296   if (carry) /* subtracted */
 297   {
 298     if (!dif) {
 299       /* error: a < b */
 300       return 0;
 301     }
 302
 303     while (dif) {
 304       dif--;
 305       t1 = *(ap++);
 306       t2 = (t1 - 1) & BN_MASK2;
 307       *(rp++) = t2;
 308       if (t1) {
 309         break;
 310       }
 311     }
 312   }
 313
 314   if (rp != ap) {
 315     for (;;) {
 316       if (!dif--) {
 317         break;
 318       }
 319       rp[0] = ap[0];
 320       if (!dif--) {
 321         break;
 322       }
 323       rp[1] = ap[1];
 324       if (!dif--) {
 325         break;
 326       }
 327       rp[2] = ap[2];
 328       if (!dif--) {
 329         break;
 330       }
 331       rp[3] = ap[3];
 332       rp += 4;
 333       ap += 4;
 334     }
 335   }
 336
 337   r->top = max;
 338   r->neg = 0;
 339   bn_correct_top(r);
 340
 341   return 1;
 342 }
 343
 344 int BN_sub_word(BIGNUM *a, BN_ULONG w) {
 345   int i;
 346
 347   w &= BN_MASK2;
 348
 349   /* degenerate case: w is zero */
 350   if (!w) {
 351     return 1;
 352   }
 353
 354   /* degenerate case: a is zero */
 355   if (BN_is_zero(a)) {
 356     i = BN_set_word(a, w);
 357     if (i != 0) {
 358       BN_set_negative(a, 1);
 359     }
 360     return i;
 361   }
 362
 363   /* handle 'a' when negative */
 364   if (a->neg) {
 365     a->neg = 0;
 366     i = BN_add_word(a, w);
 367     a->neg = 1;
 368     return i;
 369   }
 370
 371   if ((a->top == 1) && (a->d[0] < w)) {
 372     a->d[0] = w - a->d[0];
 373     a->neg = 1;
 374     return 1;
 375   }
 376
 377   i = 0;
 378   for (;;) {
 379     if (a->d[i] >= w) {
 380       a->d[i] -= w;
 381       break;
 382     } else {
 383       a->d[i] = (a->d[i] - w) & BN_MASK2;
 384       i++;
 385       w = 1;
 386     }
 387   }
 388
 389   if ((a->d[i] == 0) && (i == (a->top - 1))) {
 390     a->top--;
 391   }
 392
 393   return 1;
 394 }