[apple/security.git] / libsecurity_apple_csp / open_ssl / bn / bn_add.c

/*
 * Copyright (c) 2000-2001 Apple Computer, Inc. All Rights Reserved.
 * 
 * The contents of this file constitute Original Code as defined in and are
 * subject to the Apple Public Source License Version 1.2 (the 'License').
 * You may not use this file except in compliance with the License. Please obtain
 * a copy of the License at http://www.apple.com/publicsource and read it before
 * using this file.
 * 
 * This Original Code and all software distributed under the License are
 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER EXPRESS
 * OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES, INCLUDING WITHOUT
 * LIMITATION, ANY WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR
 * PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT. Please see the License for the
 * specific language governing rights and limitations under the License.
 */


/* crypto/bn/bn_add.c */
/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
 * All rights reserved.
 *
 * This package is an SSL implementation written
 * by Eric Young (eay@cryptsoft.com).
 * The implementation was written so as to conform with Netscapes SSL.
 * 
 * This library is free for commercial and non-commercial use as long as
 * the following conditions are aheared to.  The following conditions
 * apply to all code found in this distribution, be it the RC4, RSA,
 * lhash, DES, etc., code; not just the SSL code.  The SSL documentation
 * included with this distribution is covered by the same copyright terms
 * except that the holder is Tim Hudson (tjh@cryptsoft.com).
 * 
 * Copyright remains Eric Young's, and as such any Copyright notices in
 * the code are not to be removed.
 * If this package is used in a product, Eric Young should be given attribution
 * as the author of the parts of the library used.
 * This can be in the form of a textual message at program startup or
 * in documentation (online or textual) provided with the package.
 * 
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 * 3. All advertising materials mentioning features or use of this software
 *    must display the following acknowledgement:
 *    "This product includes cryptographic software written by
 *     Eric Young (eay@cryptsoft.com)"
 *    The word 'cryptographic' can be left out if the rouines from the library
 *    being used are not cryptographic related :-).
 * 4. If you include any Windows specific code (or a derivative thereof) from 
 *    the apps directory (application code) you must include an acknowledgement:
 *    "This product includes software written by Tim Hudson (tjh@cryptsoft.com)"
 * 
 * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 * 
 * The licence and distribution terms for any publically available version or
 * derivative of this code cannot be changed.  i.e. this code cannot simply be
 * copied and put under another distribution licence
 * [including the GNU Public Licence.]
 */

#include <stdio.h>
#include "cryptlib.h"
#include "bn_lcl.h"

/* r can == a or b */
int BN_add(BIGNUM *r, const BIGNUM *a, const BIGNUM *b)
	{
	const BIGNUM *tmp;

	bn_check_top(a);
	bn_check_top(b);

	/*  a +  b	a+b
	 *  a + -b	a-b
	 * -a +  b	b-a
	 * -a + -b	-(a+b)
	 */
	if (a->neg ^ b->neg)
		{
		/* only one is negative */
		if (a->neg)
			{ tmp=a; a=b; b=tmp; }

		/* we are now a - b */

		if (BN_ucmp(a,b) < 0)
			{
			if (!BN_usub(r,b,a)) return(0);
			r->neg=1;
			}
		else
			{
			if (!BN_usub(r,a,b)) return(0);
			r->neg=0;
			}
		return(1);
		}

	if (a->neg) /* both are neg */
		r->neg=1;
	else
		r->neg=0;

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

/* unsigned add of b to a, r must be large enough */
int BN_uadd(BIGNUM *r, const BIGNUM *a, const BIGNUM *b)
	{
	register int i;
	int max,min;
	BN_ULONG *ap,*bp,*rp,carry,t1;
	const BIGNUM *tmp;

	bn_check_top(a);
	bn_check_top(b);

	if (a->top < b->top)
		{ tmp=a; a=b; b=tmp; }
	max=a->top;
	min=b->top;

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

	r->top=max;


	ap=a->d;
	bp=b->d;
	rp=r->d;
	carry=0;

	carry=bn_add_words(rp,ap,bp,min);
	rp+=min;
	ap+=min;
	bp+=min;
	i=min;

	if (carry)
		{
		while (i < max)
			{
			i++;
			t1= *(ap++);
			if ((*(rp++)=(t1+1)&BN_MASK2) >= t1)
				{
				carry=0;
				break;
				}
			}
		if ((i >= max) && carry)
			{
			*(rp++)=1;
			r->top++;
			}
		}
	if (rp != ap)
		{
		for (; i<max; i++)
			*(rp++)= *(ap++);
		}
	/* memcpy(rp,ap,sizeof(*ap)*(max-i));*/
	return(1);
	}

/* unsigned subtraction of b from a, a must be larger than b. */
int BN_usub(BIGNUM *r, const BIGNUM *a, const BIGNUM *b)
	{
	int max,min;
	register BN_ULONG t1,t2,*ap,*bp,*rp;
	int i,carry;
#if defined(IRIX_CC_BUG) && !defined(LINT)
	int dummy;
#endif

	bn_check_top(a);
	bn_check_top(b);

	if (a->top < b->top) /* hmm... should not be happening */
		{
		BNerr(BN_F_BN_USUB,BN_R_ARG2_LT_ARG3);
		return(0);
		}

	max=a->top;
	min=b->top;
	if (bn_wexpand(r,max) == NULL) return(0);

	ap=a->d;
	bp=b->d;
	rp=r->d;

#if 1
	carry=0;
	for (i=0; i<min; i++)
		{
		t1= *(ap++);
		t2= *(bp++);
		if (carry)
			{
			carry=(t1 <= t2);
			t1=(t1-t2-1)&BN_MASK2;
			}
		else
			{
			carry=(t1 < t2);
			t1=(t1-t2)&BN_MASK2;
			}
#if defined(IRIX_CC_BUG) && !defined(LINT)
		dummy=t1;
#endif
		*(rp++)=t1&BN_MASK2;
		}
#else
	carry=bn_sub_words(rp,ap,bp,min);
	ap+=min;
	bp+=min;
	rp+=min;
	i=min;
#endif
	if (carry) /* subtracted */
		{
		while (i < max)
			{
			i++;
			t1= *(ap++);
			t2=(t1-1)&BN_MASK2;
			*(rp++)=t2;
			if (t1 > t2) break;
			}
		}
#if 0
	memcpy(rp,ap,sizeof(*rp)*(max-i));
#else
	if (rp != ap)
		{
		for (;;)
			{
			if (i++ >= max) break;
			rp[0]=ap[0];
			if (i++ >= max) break;
			rp[1]=ap[1];
			if (i++ >= max) break;
			rp[2]=ap[2];
			if (i++ >= max) break;
			rp[3]=ap[3];
			rp+=4;
			ap+=4;
			}
		}
#endif

	r->top=max;
	bn_fix_top(r);
	return(1);
	}

int BN_sub(BIGNUM *r, const BIGNUM *a, const BIGNUM *b)
	{
	int max;
	int add=0,neg=0;
	const BIGNUM *tmp;

	bn_check_top(a);
	bn_check_top(b);

	/*  a -  b	a-b
	 *  a - -b	a+b
	 * -a -  b	-(a+b)
	 * -a - -b	b-a
	 */
	if (a->neg)
		{
		if (b->neg)
			{ tmp=a; a=b; b=tmp; }
		else
			{ add=1; neg=1; }
		}
	else
		{
		if (b->neg) { add=1; neg=0; }
		}

	if (add)
		{
		if (!BN_uadd(r,a,b)) return(0);
		r->neg=neg;
		return(1);
		}

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

	max=(a->top > b->top)?a->top:b->top;
	if (bn_wexpand(r,max) == NULL) return(0);
	if (BN_ucmp(a,b) < 0)
		{
		if (!BN_usub(r,b,a)) return(0);
		r->neg=1;
		}
	else
		{
		if (!BN_usub(r,a,b)) return(0);
		r->neg=0;
		}
	return(1);
	}
Commit	Line	Data
b1ab9ed8 A	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