OLD | NEW |
| (Empty) |
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 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 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 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 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 | |
OLD | NEW |