AppleCSP/open_ssl/bn/bn_add.c

   1 /*
   2  * Copyright (c) 2000-2001 Apple Computer, Inc. All Rights Reserved.
   3  *
   4  * The contents of this file constitute Original Code as defined in and are
   5  * subject to the Apple Public Source License Version 1.2 (the 'License').
   6  * You may not use this file except in compliance with the License. Please obtain
   7  * a copy of the License at http://www.apple.com/publicsource and read it before
   8  * using this file.
   9  *
  10  * This Original Code and all software distributed under the License are
  11  * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER EXPRESS
  12  * OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES, INCLUDING WITHOUT
  13  * LIMITATION, ANY WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR
  14  * PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT. Please see the License for the
  15  * specific language governing rights and limitations under the License.
  16  */
  17
  18
  19 /* crypto/bn/bn_add.c */
  20 /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
  21  * All rights reserved.
  22  *
  23  * This package is an SSL implementation written
  24  * by Eric Young (eay@cryptsoft.com).
  25  * The implementation was written so as to conform with Netscapes SSL.
  26  *
  27  * This library is free for commercial and non-commercial use as long as
  28  * the following conditions are aheared to.  The following conditions
  29  * apply to all code found in this distribution, be it the RC4, RSA,
  30  * lhash, DES, etc., code; not just the SSL code.  The SSL documentation
  31  * included with this distribution is covered by the same copyright terms
  32  * except that the holder is Tim Hudson (tjh@cryptsoft.com).
  33  *
  34  * Copyright remains Eric Young's, and as such any Copyright notices in
  35  * the code are not to be removed.
  36  * If this package is used in a product, Eric Young should be given attribution
  37  * as the author of the parts of the library used.
  38  * This can be in the form of a textual message at program startup or
  39  * in documentation (online or textual) provided with the package.
  40  *
  41  * Redistribution and use in source and binary forms, with or without
  42  * modification, are permitted provided that the following conditions
  43  * are met:
  44  * 1. Redistributions of source code must retain the copyright
  45  *    notice, this list of conditions and the following disclaimer.
  46  * 2. Redistributions in binary form must reproduce the above copyright
  47  *    notice, this list of conditions and the following disclaimer in the
  48  *    documentation and/or other materials provided with the distribution.
  49  * 3. All advertising materials mentioning features or use of this software
  50  *    must display the following acknowledgement:
  51  *    "This product includes cryptographic software written by
  52  *     Eric Young (eay@cryptsoft.com)"
  53  *    The word 'cryptographic' can be left out if the rouines from the library
  54  *    being used are not cryptographic related :-).
  55  * 4. If you include any Windows specific code (or a derivative thereof) from
  56  *    the apps directory (application code) you must include an acknowledgement:
  57  *    "This product includes software written by Tim Hudson (tjh@cryptsoft.com)"
  58  *
  59  * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND
  60  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  61  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  62  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
  63  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  64  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  65  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  66  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  67  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  68  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  69  * SUCH DAMAGE.
  70  *
  71  * The licence and distribution terms for any publically available version or
  72  * derivative of this code cannot be changed.  i.e. this code cannot simply be
  73  * copied and put under another distribution licence
  74  * [including the GNU Public Licence.]
  75  */
  76
  77 #include <stdio.h>
  78 #include "cryptlib.h"
  79 #include "bn_lcl.h"
  80
  81 /* r can == a or b */
  82 int BN_add(BIGNUM *r, const BIGNUM *a, const BIGNUM *b)
  83         {
  84         const BIGNUM *tmp;
  85
  86         bn_check_top(a);
  87         bn_check_top(b);
  88
  89         /*  a +  b      a+b
  90          *  a + -b      a-b
  91          * -a +  b      b-a
  92          * -a + -b      -(a+b)
  93          */
  94         if (a->neg ^ b->neg)
  95                 {
  96                 /* only one is negative */
  97                 if (a->neg)
  98                         { tmp=a; a=b; b=tmp; }
  99
 100                 /* we are now a - b */
 101
 102                 if (BN_ucmp(a,b) < 0)
 103                         {
 104                         if (!BN_usub(r,b,a)) return(0);
 105                         r->neg=1;
 106                         }
 107                 else
 108                         {
 109                         if (!BN_usub(r,a,b)) return(0);
 110                         r->neg=0;
 111                         }
 112                 return(1);
 113                 }
 114
 115         if (a->neg) /* both are neg */
 116                 r->neg=1;
 117         else
 118                 r->neg=0;
 119
 120         if (!BN_uadd(r,a,b)) return(0);
 121         return(1);
 122         }
 123
 124 /* unsigned add of b to a, r must be large enough */
 125 int BN_uadd(BIGNUM *r, const BIGNUM *a, const BIGNUM *b)
 126         {
 127         register int i;
 128         int max,min;
 129         BN_ULONG *ap,*bp,*rp,carry,t1;
 130         const BIGNUM *tmp;
 131
 132         bn_check_top(a);
 133         bn_check_top(b);
 134
 135         if (a->top < b->top)
 136                 { tmp=a; a=b; b=tmp; }
 137         max=a->top;
 138         min=b->top;
 139
 140         if (bn_wexpand(r,max+1) == NULL)
 141                 return(0);
 142
 143         r->top=max;
 144
 145
 146         ap=a->d;
 147         bp=b->d;
 148         rp=r->d;
 149         carry=0;
 150
 151         carry=bn_add_words(rp,ap,bp,min);
 152         rp+=min;
 153         ap+=min;
 154         bp+=min;
 155         i=min;
 156
 157         if (carry)
 158                 {
 159                 while (i < max)
 160                         {
 161                         i++;
 162                         t1= *(ap++);
 163                         if ((*(rp++)=(t1+1)&BN_MASK2) >= t1)
 164                                 {
 165                                 carry=0;
 166                                 break;
 167                                 }
 168                         }
 169                 if ((i >= max) && carry)
 170                         {
 171                         *(rp++)=1;
 172                         r->top++;
 173                         }
 174                 }
 175         if (rp != ap)
 176                 {
 177                 for (; i<max; i++)
 178                         *(rp++)= *(ap++);
 179                 }
 180         /* memcpy(rp,ap,sizeof(*ap)*(max-i));*/
 181         return(1);
 182         }
 183
 184 /* unsigned subtraction of b from a, a must be larger than b. */
 185 int BN_usub(BIGNUM *r, const BIGNUM *a, const BIGNUM *b)
 186         {
 187         int max,min;
 188         register BN_ULONG t1,t2,*ap,*bp,*rp;
 189         int i,carry;
 190 #if defined(IRIX_CC_BUG) && !defined(LINT)
 191         int dummy;
 192 #endif
 193
 194         bn_check_top(a);
 195         bn_check_top(b);
 196
 197         if (a->top < b->top) /* hmm... should not be happening */
 198                 {
 199                 BNerr(BN_F_BN_USUB,BN_R_ARG2_LT_ARG3);
 200                 return(0);
 201                 }
 202
 203         max=a->top;
 204         min=b->top;
 205         if (bn_wexpand(r,max) == NULL) return(0);
 206
 207         ap=a->d;
 208         bp=b->d;
 209         rp=r->d;
 210
 211 #if 1
 212         carry=0;
 213         for (i=0; i<min; i++)
 214                 {
 215                 t1= *(ap++);
 216                 t2= *(bp++);
 217                 if (carry)
 218                         {
 219                         carry=(t1 <= t2);
 220                         t1=(t1-t2-1)&BN_MASK2;
 221                         }
 222                 else
 223                         {
 224                         carry=(t1 < t2);
 225                         t1=(t1-t2)&BN_MASK2;
 226                         }
 227 #if defined(IRIX_CC_BUG) && !defined(LINT)
 228                 dummy=t1;
 229 #endif
 230                 *(rp++)=t1&BN_MASK2;
 231                 }
 232 #else
 233         carry=bn_sub_words(rp,ap,bp,min);
 234         ap+=min;
 235         bp+=min;
 236         rp+=min;
 237         i=min;
 238 #endif
 239         if (carry) /* subtracted */
 240                 {
 241                 while (i < max)
 242                         {
 243                         i++;
 244                         t1= *(ap++);
 245                         t2=(t1-1)&BN_MASK2;
 246                         *(rp++)=t2;
 247                         if (t1 > t2) break;
 248                         }
 249                 }
 250 #if 0
 251         memcpy(rp,ap,sizeof(*rp)*(max-i));
 252 #else
 253         if (rp != ap)
 254                 {
 255                 for (;;)
 256                         {
 257                         if (i++ >= max) break;
 258                         rp[0]=ap[0];
 259                         if (i++ >= max) break;
 260                         rp[1]=ap[1];
 261                         if (i++ >= max) break;
 262                         rp[2]=ap[2];
 263                         if (i++ >= max) break;
 264                         rp[3]=ap[3];
 265                         rp+=4;
 266                         ap+=4;
 267                         }
 268                 }
 269 #endif
 270
 271         r->top=max;
 272         bn_fix_top(r);
 273         return(1);
 274         }
 275
 276 int BN_sub(BIGNUM *r, const BIGNUM *a, const BIGNUM *b)
 277         {
 278         int max;
 279         int add=0,neg=0;
 280         const BIGNUM *tmp;
 281
 282         bn_check_top(a);
 283         bn_check_top(b);
 284
 285         /*  a -  b      a-b
 286          *  a - -b      a+b
 287          * -a -  b      -(a+b)
 288          * -a - -b      b-a
 289          */
 290         if (a->neg)
 291                 {
 292                 if (b->neg)
 293                         { tmp=a; a=b; b=tmp; }
 294                 else
 295                         { add=1; neg=1; }
 296                 }
 297         else
 298                 {
 299                 if (b->neg) { add=1; neg=0; }
 300                 }
 301
 302         if (add)
 303                 {
 304                 if (!BN_uadd(r,a,b)) return(0);
 305                 r->neg=neg;
 306                 return(1);
 307                 }
 308
 309         /* We are actually doing a - b :-) */
 310
 311         max=(a->top > b->top)?a->top:b->top;
 312         if (bn_wexpand(r,max) == NULL) return(0);
 313         if (BN_ucmp(a,b) < 0)
 314                 {
 315                 if (!BN_usub(r,b,a)) return(0);
 316                 r->neg=1;
 317                 }
 318         else
 319                 {
 320                 if (!BN_usub(r,a,b)) return(0);
 321                 r->neg=0;
 322                 }
 323         return(1);
 324         }
 325