1  //FIXME Not checked on threadsafety yet; after checking please remove this line


2  /* crypto/bn/bn_add.c */


3  /* Copyright (C) 19951998 Eric Young (eay@cryptsoft.com)


4  * All rights reserved.


5  *


6  * This package is an SSL implementation written


7  * by Eric Young (eay@cryptsoft.com).


8  * The implementation was written so as to conform with Netscapes SSL.


9  *


10  * This library is free for commercial and noncommercial use as long as


11  * the following conditions are aheared to. The following conditions


12  * apply to all code found in this distribution, be it the RC4, RSA,


13  * lhash, DES, etc., code; not just the SSL code. The SSL documentation


14  * included with this distribution is covered by the same copyright terms


15  * except that the holder is Tim Hudson (tjh@cryptsoft.com).


16  *


17  * Copyright remains Eric Young's, and as such any Copyright notices in


18  * the code are not to be removed.


19  * If this package is used in a product, Eric Young should be given attribution


20  * as the author of the parts of the library used.


21  * This can be in the form of a textual message at program startup or


22  * in documentation (online or textual) provided with the package.


23  *


24  * Redistribution and use in source and binary forms, with or without


25  * modification, are permitted provided that the following conditions


26  * are met:


27  * 1. Redistributions of source code must retain the copyright


28  * notice, this list of conditions and the following disclaimer.


29  * 2. Redistributions in binary form must reproduce the above copyright


30  * notice, this list of conditions and the following disclaimer in the


31  * documentation and/or other materials provided with the distribution.


32  * 3. All advertising materials mentioning features or use of this software


33  * must display the following acknowledgement:


34  * "This product includes cryptographic software written by


35  * Eric Young (eay@cryptsoft.com)"


36  * The word 'cryptographic' can be left out if the rouines from the library


37  * being used are not cryptographic related :).


38  * 4. If you include any Windows specific code (or a derivative thereof) from


39  * the apps directory (application code) you must include an acknowledgement:


40  * "This product includes software written by Tim Hudson (tjh@cryptsoft.com)"


41  *


42  * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND


43  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE


44  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE


45  * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE


46  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL


47  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS


48  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)


49  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT


50  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY


51  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF


52  * SUCH DAMAGE.


53  *


54  * The licence and distribution terms for any publically available version or


55  * derivative of this code cannot be changed. i.e. this code cannot simply be


56  * copied and put under another distribution licence


57  * [including the GNU Public Licence.]


58  */


59 


60  #include <stdio.h>


61  #include "openssl_mods.h"


62  #include "bn_lcl.h"


63 


64  /* r can == a or b */


65  int BN_add(BIGNUM *r, const BIGNUM *a, const BIGNUM *b)


66  {


67  const BIGNUM *tmp;


68 


69  bn_check_top(a);


70  bn_check_top(b);


71 


72  /* a + b a+b


73  * a + b ab


74  * a + b ba


75  * a + b (a+b)


76  */


77  if (a>neg ^ b>neg)


78  {


79  /* only one is negative */


80  if (a>neg)


81  { tmp=a; a=b; b=tmp; }


82 


83  /* we are now a  b */


84 


85  if (BN_ucmp(a,b) < 0)


86  {


87  if (!BN_usub(r,b,a)) return(0);


88  r>neg=1;


89  }


90  else


91  {


92  if (!BN_usub(r,a,b)) return(0);


93  r>neg=0;


94  }


95  return(1);


96  }


97 


98  if (a>neg) /* both are neg */


99  r>neg=1;


100  else


101  r>neg=0;


102 


103  if (!BN_uadd(r,a,b)) return(0);


104  return(1);


105  }


106 


107  /* unsigned add of b to a, r must be large enough */


108  int BN_uadd(BIGNUM *r, const BIGNUM *a, const BIGNUM *b)


109  {


110  register int i;


111  int max,min;


112  BN_ULONG *ap,*bp,*rp,carry,t1;


113  const BIGNUM *tmp;


114 


115  bn_check_top(a);


116  bn_check_top(b);


117 


118  if (a>top < b>top)


119  { tmp=a; a=b; b=tmp; }


120  max=a>top;


121  min=b>top;


122 


123  if (bn_wexpand(r,max+1) == NULL)


124  return(0);


125 


126  r>top=max;


127 


128 


129  ap=a>d;


130  bp=b>d;


131  rp=r>d;


132  carry=0;


133 


134  carry=bn_add_words(rp,ap,bp,min);


135  rp+=min;


136  ap+=min;


137  bp+=min;


138  i=min;


139 


140  if (carry)


141  {


142  while (i < max)


143  {


144  i++;


145  t1= *(ap++);


146  if ((*(rp++)=(t1+1)&BN_MASK2) >= t1)


147  {


148  carry=0;


149  break;


150  }


151  }


152  if ((i >= max) && carry)


153  {


154  *(rp++)=1;


155  r>top++;


156  }


157  }


158  if (rp != ap)


159  {


160  for (; i<max; i++)


161  *(rp++)= *(ap++);


162  }


163  /* memcpy(rp,ap,sizeof(*ap)*(maxi));*/


164  return(1);


165  }


166 


167  /* unsigned subtraction of b from a, a must be larger than b. */


168  int BN_usub(BIGNUM *r, const BIGNUM *a, const BIGNUM *b)


169  {


170  int max,min;


171  register BN_ULONG t1,t2,*ap,*bp,*rp;


172  int i,carry;


173  #if defined(IRIX_CC_BUG) && !defined(LINT)


174  int dummy;


175  #endif


176 


177  bn_check_top(a);


178  bn_check_top(b);


179 


180  if (a>top < b>top) /* hmm... should not be happening */


181  {


182  return(0);


183  }


184 


185  max=a>top;


186  min=b>top;


187  if (bn_wexpand(r,max) == NULL) return(0);


188 


189  ap=a>d;


190  bp=b>d;


191  rp=r>d;


192 


193  #if 1


194  carry=0;


195  for (i=0; i<min; i++)


196  {


197  t1= *(ap++);


198  t2= *(bp++);


199  if (carry)


200  {


201  carry=(t1 <= t2);


202  t1=(t1t21)&BN_MASK2;


203  }


204  else


205  {


206  carry=(t1 < t2);


207  t1=(t1t2)&BN_MASK2;


208  }


209  #if defined(IRIX_CC_BUG) && !defined(LINT)


210  dummy=t1;


211  #endif


212  *(rp++)=t1&BN_MASK2;


213  }


214  #else


215  carry=bn_sub_words(rp,ap,bp,min);


216  ap+=min;


217  bp+=min;


218  rp+=min;


219  i=min;


220  #endif


221  if (carry) /* subtracted */


222  {


223  while (i < max)


224  {


225  i++;


226  t1= *(ap++);


227  t2=(t11)&BN_MASK2;


228  *(rp++)=t2;


229  if (t1 > t2) break;


230  }


231  }


232  #if 0


233  memcpy(rp,ap,sizeof(*rp)*(maxi));


234  #else


235  if (rp != ap)


236  {


237  for (;;)


238  {


239  if (i++ >= max) break;


240  rp[0]=ap[0];


241  if (i++ >= max) break;


242  rp[1]=ap[1];


243  if (i++ >= max) break;


244  rp[2]=ap[2];


245  if (i++ >= max) break;


246  rp[3]=ap[3];


247  rp+=4;


248  ap+=4;


249  }


250  }


251  #endif


252 


253  r>top=max;


254  bn_fix_top(r);


255  return(1);


256  }


257 


258  int BN_sub(BIGNUM *r, const BIGNUM *a, const BIGNUM *b)


259  {


260  int max;


261  int add=0,neg=0;


262  const BIGNUM *tmp;


263 


264  bn_check_top(a);


265  bn_check_top(b);


266 


267  /* a  b ab


268  * a  b a+b


269  * a  b (a+b)


270  * a  b ba


271  */


272  if (a>neg)


273  {


274  if (b>neg)


275  { tmp=a; a=b; b=tmp; }


276  else


277  { add=1; neg=1; }


278  }


279  else


280  {


281  if (b>neg) { add=1; neg=0; }


282  }


283 


284  if (add)


285  {


286  if (!BN_uadd(r,a,b)) return(0);


287  r>neg=neg;


288  return(1);


289  }


290 


291  /* We are actually doing a  b :) */


292 


293  max=(a>top > b>top)?a>top:b>top;


294  if (bn_wexpand(r,max) == NULL) return(0);


295  if (BN_ucmp(a,b) < 0)


296  {


297  if (!BN_usub(r,b,a)) return(0);


298  r>neg=1;


299  }


300  else


301  {


302  if (!BN_usub(r,a,b)) return(0);


303  r>neg=0;


304  }


305  return(1);


306  }


307 

