1 /* crypto/bn/bn_add.c */

     2 /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)

     3  * All rights reserved.

     4  *

     5  * This package is an SSL implementation written

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

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

     8  * 

     9  * This library is free for commercial and non-commercial use as long as

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

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

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

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

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

    15  * 

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

    17  * the code are not to be removed.

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

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

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

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

    22  * 

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

    24  * modification, are permitted provided that the following conditions

    25  * are met:

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

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

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

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

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

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

    32  *    must display the following acknowledgement:

    33  *    "This product includes cryptographic software written by

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

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

    36  *    being used are not cryptographic related :-).

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

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

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

    40  * 

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

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

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

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

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

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

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

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

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

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

    51  * SUCH DAMAGE.

    52  * 

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

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

    55  * copied and put under another distribution licence

    56  * [including the GNU Public Licence.]

    57  */

    58 

    59 #include <stdio.h>

    60 #include "cryptlib.h"

    61 #include "bn_lcl.h"

    62 

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

    64 EXPORT_C int BN_add(BIGNUM *r, const BIGNUM *a, const BIGNUM *b)

    65 	{

    66 	const BIGNUM *tmp;

    67 	int a_neg = a->neg, ret;

    68 

    69 	bn_check_top(a);

    70 	bn_check_top(b);

    71 

    72 	/*  a +  b	a+b

    73 	 *  a + -b	a-b

    74 	 * -a +  b	b-a

    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 	ret = BN_uadd(r,a,b);

    99 	r->neg = a_neg;

   100 	bn_check_top(r);

   101 	return ret;

   102 	}

   103 

   104 /* unsigned add of b to a */

   105 EXPORT_C int BN_uadd(BIGNUM *r, const BIGNUM *a, const BIGNUM *b)

   106 	{

   107 	int max,min,dif;

   108 	BN_ULONG *ap,*bp,*rp,carry,t1,t2;

   109 	const BIGNUM *tmp;

   110 

   111 	bn_check_top(a);

   112 	bn_check_top(b);

   113 

   114 	if (a->top < b->top)

   115 		{ tmp=a; a=b; b=tmp; }

   116 	max = a->top;

   117 	min = b->top;

   118 	dif = max - min;

   119 

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

   121 		return 0;

   122 

   123 	r->top=max;

   124 

   125 

   126 	ap=a->d;

   127 	bp=b->d;

   128 	rp=r->d;

   129 

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

   131 	rp+=min;

   132 	ap+=min;

   133 	bp+=min;

   134 

   135 	if (carry)

   136 		{

   137 		while (dif)

   138 			{

   139 			dif--;

   140 			t1 = *(ap++);

   141 			t2 = (t1+1) & BN_MASK2;

   142 			*(rp++) = t2;

   143 			if (t2)

   144 				{

   145 				carry=0;

   146 				break;

   147 				}

   148 			}

   149 		if (carry)

   150 			{

   151 			/* carry != 0 => dif == 0 */

   152 			*rp = 1;

   153 			r->top++;

   154 			}

   155 		}

   156 	if (dif && rp != ap)

   157 		while (dif--)

   158 			/* copy remaining words if ap != rp */

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

   160 	r->neg = 0;

   161 	bn_check_top(r);

   162 	return 1;

   163 	}

   164 

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

   166 EXPORT_C int BN_usub(BIGNUM *r, const BIGNUM *a, const BIGNUM *b)

   167 	{

   168 	int max,min,dif;

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

   170 	int i,carry;

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

   172 	int dummy;

   173 #endif

   174 

   175 	bn_check_top(a);

   176 	bn_check_top(b);

   177 

   178 	max = a->top;

   179 	min = b->top;

   180 	dif = max - min;

   181 

   182 	if (dif < 0)	/* hmm... should not be happening */

   183 		{

   184 		BNerr(BN_F_BN_USUB,BN_R_ARG2_LT_ARG3);

   185 		return(0);

   186 		}

   187 

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

   189 

   190 	ap=a->d;

   191 	bp=b->d;

   192 	rp=r->d;

   193 

   194 #if 1

   195 	carry=0;

   196 	for (i = min; i != 0; i--)

   197 		{

   198 		t1= *(ap++);

   199 		t2= *(bp++);

   200 		if (carry)

   201 			{

   202 			carry=(t1 <= t2);

   203 			t1=(t1-t2-1)&BN_MASK2;

   204 			}

   205 		else

   206 			{

   207 			carry=(t1 < t2);

   208 			t1=(t1-t2)&BN_MASK2;

   209 			}

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

   211 		dummy=t1;

   212 #endif

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

   214 		}

   215 #else

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

   217 	ap+=min;

   218 	bp+=min;

   219 	rp+=min;

   220 #endif

   221 	if (carry) /* subtracted */

   222 		{

   223 		if (!dif)

   224 			/* error: a < b */

   225 			return 0;

   226 		while (dif)

   227 			{

   228 			dif--;

   229 			t1 = *(ap++);

   230 			t2 = (t1-1)&BN_MASK2;

   231 			*(rp++) = t2;

   232 			if (t1)

   233 				break;

   234 			}

   235 		}

   236 #if 0

   237 	memcpy(rp,ap,sizeof(*rp)*(max-i));

   238 #else

   239 	if (rp != ap)

   240 		{

   241 		for (;;)

   242 			{

   243 			if (!dif--) break;

   244 			rp[0]=ap[0];

   245 			if (!dif--) break;

   246 			rp[1]=ap[1];

   247 			if (!dif--) break;

   248 			rp[2]=ap[2];

   249 			if (!dif--) break;

   250 			rp[3]=ap[3];

   251 			rp+=4;

   252 			ap+=4;

   253 			}

   254 		}

   255 #endif

   256 

   257 	r->top=max;

   258 	r->neg=0;

   259 	bn_correct_top(r);

   260 	return(1);

   261 	}

   262 

   263 EXPORT_C int BN_sub(BIGNUM *r, const BIGNUM *a, const BIGNUM *b)

   264 	{

   265 	int max;

   266 	int add=0,neg=0;

   267 	const BIGNUM *tmp;

   268 

   269 	bn_check_top(a);

   270 	bn_check_top(b);

   271 

   272 	/*  a -  b	a-b

   273 	 *  a - -b	a+b

   274 	 * -a -  b	-(a+b)

   275 	 * -a - -b	b-a

   276 	 */

   277 	if (a->neg)

   278 		{

   279 		if (b->neg)

   280 			{ tmp=a; a=b; b=tmp; }

   281 		else

   282 			{ add=1; neg=1; }

   283 		}

   284 	else

   285 		{

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

   287 		}

   288 

   289 	if (add)

   290 		{

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

   292 		r->neg=neg;

   293 		return(1);

   294 		}

   295 

   296 	/* We are actually doing a - b :-) */

   297 

   298 	max=(a->top > b->top)?a->top:b->top;

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

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

   301 		{

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

   303 		r->neg=1;

   304 		}

   305 	else

   306 		{

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

   308 		r->neg=0;

   309 		}

   310 	bn_check_top(r);

   311 	return(1);

   312 	}

   313