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 "openssl_mods.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 |
|
---|
68 | bn_check_top(a);
|
---|
69 | bn_check_top(b);
|
---|
70 |
|
---|
71 | /* a + b a+b
|
---|
72 | * a + -b a-b
|
---|
73 | * -a + b b-a
|
---|
74 | * -a + -b -(a+b)
|
---|
75 | */
|
---|
76 | if (a->neg ^ b->neg)
|
---|
77 | {
|
---|
78 | /* only one is negative */
|
---|
79 | if (a->neg)
|
---|
80 | { tmp=a; a=b; b=tmp; }
|
---|
81 |
|
---|
82 | /* we are now a - b */
|
---|
83 |
|
---|
84 | if (BN_ucmp(a,b) < 0)
|
---|
85 | {
|
---|
86 | if (!BN_usub(r,b,a)) return(0);
|
---|
87 | r->neg=1;
|
---|
88 | }
|
---|
89 | else
|
---|
90 | {
|
---|
91 | if (!BN_usub(r,a,b)) return(0);
|
---|
92 | r->neg=0;
|
---|
93 | }
|
---|
94 | return(1);
|
---|
95 | }
|
---|
96 |
|
---|
97 | if (a->neg) /* both are neg */
|
---|
98 | r->neg=1;
|
---|
99 | else
|
---|
100 | r->neg=0;
|
---|
101 |
|
---|
102 | if (!BN_uadd(r,a,b)) return(0);
|
---|
103 | return(1);
|
---|
104 | }
|
---|
105 |
|
---|
106 | /* unsigned add of b to a, r must be large enough */
|
---|
107 | int BN_uadd(BIGNUM *r, const BIGNUM *a, const BIGNUM *b)
|
---|
108 | {
|
---|
109 | register int i;
|
---|
110 | int max,min;
|
---|
111 | BN_ULONG *ap,*bp,*rp,carry,t1;
|
---|
112 | const BIGNUM *tmp;
|
---|
113 |
|
---|
114 | bn_check_top(a);
|
---|
115 | bn_check_top(b);
|
---|
116 |
|
---|
117 | if (a->top < b->top)
|
---|
118 | { tmp=a; a=b; b=tmp; }
|
---|
119 | max=a->top;
|
---|
120 | min=b->top;
|
---|
121 |
|
---|
122 | if (bn_wexpand(r,max+1) == NULL)
|
---|
123 | return(0);
|
---|
124 |
|
---|
125 | r->top=max;
|
---|
126 |
|
---|
127 |
|
---|
128 | ap=a->d;
|
---|
129 | bp=b->d;
|
---|
130 | rp=r->d;
|
---|
131 | carry=0;
|
---|
132 |
|
---|
133 | carry=bn_add_words(rp,ap,bp,min);
|
---|
134 | rp+=min;
|
---|
135 | ap+=min;
|
---|
136 | bp+=min;
|
---|
137 | i=min;
|
---|
138 |
|
---|
139 | if (carry)
|
---|
140 | {
|
---|
141 | while (i < max)
|
---|
142 | {
|
---|
143 | i++;
|
---|
144 | t1= *(ap++);
|
---|
145 | if ((*(rp++)=(t1+1)&BN_MASK2) >= t1)
|
---|
146 | {
|
---|
147 | carry=0;
|
---|
148 | break;
|
---|
149 | }
|
---|
150 | }
|
---|
151 | if ((i >= max) && carry)
|
---|
152 | {
|
---|
153 | *(rp++)=1;
|
---|
154 | r->top++;
|
---|
155 | }
|
---|
156 | }
|
---|
157 | if (rp != ap)
|
---|
158 | {
|
---|
159 | for (; i<max; i++)
|
---|
160 | *(rp++)= *(ap++);
|
---|
161 | }
|
---|
162 | /* memcpy(rp,ap,sizeof(*ap)*(max-i));*/
|
---|
163 | return(1);
|
---|
164 | }
|
---|
165 |
|
---|
166 | /* unsigned subtraction of b from a, a must be larger than b. */
|
---|
167 | int BN_usub(BIGNUM *r, const BIGNUM *a, const BIGNUM *b)
|
---|
168 | {
|
---|
169 | int max,min;
|
---|
170 | register BN_ULONG t1,t2,*ap,*bp,*rp;
|
---|
171 | int i,carry;
|
---|
172 | #if defined(IRIX_CC_BUG) && !defined(LINT)
|
---|
173 | int dummy;
|
---|
174 | #endif
|
---|
175 |
|
---|
176 | bn_check_top(a);
|
---|
177 | bn_check_top(b);
|
---|
178 |
|
---|
179 | if (a->top < b->top) /* hmm... should not be happening */
|
---|
180 | {
|
---|
181 | return(0);
|
---|
182 | }
|
---|
183 |
|
---|
184 | max=a->top;
|
---|
185 | min=b->top;
|
---|
186 | if (bn_wexpand(r,max) == NULL) return(0);
|
---|
187 |
|
---|
188 | ap=a->d;
|
---|
189 | bp=b->d;
|
---|
190 | rp=r->d;
|
---|
191 |
|
---|
192 | #if 1
|
---|
193 | carry=0;
|
---|
194 | for (i=0; i<min; i++)
|
---|
195 | {
|
---|
196 | t1= *(ap++);
|
---|
197 | t2= *(bp++);
|
---|
198 | if (carry)
|
---|
199 | {
|
---|
200 | carry=(t1 <= t2);
|
---|
201 | t1=(t1-t2-1)&BN_MASK2;
|
---|
202 | }
|
---|
203 | else
|
---|
204 | {
|
---|
205 | carry=(t1 < t2);
|
---|
206 | t1=(t1-t2)&BN_MASK2;
|
---|
207 | }
|
---|
208 | #if defined(IRIX_CC_BUG) && !defined(LINT)
|
---|
209 | dummy=t1;
|
---|
210 | #endif
|
---|
211 | *(rp++)=t1&BN_MASK2;
|
---|
212 | }
|
---|
213 | #else
|
---|
214 | carry=bn_sub_words(rp,ap,bp,min);
|
---|
215 | ap+=min;
|
---|
216 | bp+=min;
|
---|
217 | rp+=min;
|
---|
218 | i=min;
|
---|
219 | #endif
|
---|
220 | if (carry) /* subtracted */
|
---|
221 | {
|
---|
222 | while (i < max)
|
---|
223 | {
|
---|
224 | i++;
|
---|
225 | t1= *(ap++);
|
---|
226 | t2=(t1-1)&BN_MASK2;
|
---|
227 | *(rp++)=t2;
|
---|
228 | if (t1 > t2) break;
|
---|
229 | }
|
---|
230 | }
|
---|
231 | #if 0
|
---|
232 | memcpy(rp,ap,sizeof(*rp)*(max-i));
|
---|
233 | #else
|
---|
234 | if (rp != ap)
|
---|
235 | {
|
---|
236 | for (;;)
|
---|
237 | {
|
---|
238 | if (i++ >= max) break;
|
---|
239 | rp[0]=ap[0];
|
---|
240 | if (i++ >= max) break;
|
---|
241 | rp[1]=ap[1];
|
---|
242 | if (i++ >= max) break;
|
---|
243 | rp[2]=ap[2];
|
---|
244 | if (i++ >= max) break;
|
---|
245 | rp[3]=ap[3];
|
---|
246 | rp+=4;
|
---|
247 | ap+=4;
|
---|
248 | }
|
---|
249 | }
|
---|
250 | #endif
|
---|
251 |
|
---|
252 | r->top=max;
|
---|
253 | bn_fix_top(r);
|
---|
254 | return(1);
|
---|
255 | }
|
---|
256 |
|
---|
257 | int BN_sub(BIGNUM *r, const BIGNUM *a, const BIGNUM *b)
|
---|
258 | {
|
---|
259 | int max;
|
---|
260 | int add=0,neg=0;
|
---|
261 | const BIGNUM *tmp;
|
---|
262 |
|
---|
263 | bn_check_top(a);
|
---|
264 | bn_check_top(b);
|
---|
265 |
|
---|
266 | /* a - b a-b
|
---|
267 | * a - -b a+b
|
---|
268 | * -a - b -(a+b)
|
---|
269 | * -a - -b b-a
|
---|
270 | */
|
---|
271 | if (a->neg)
|
---|
272 | {
|
---|
273 | if (b->neg)
|
---|
274 | { tmp=a; a=b; b=tmp; }
|
---|
275 | else
|
---|
276 | { add=1; neg=1; }
|
---|
277 | }
|
---|
278 | else
|
---|
279 | {
|
---|
280 | if (b->neg) { add=1; neg=0; }
|
---|
281 | }
|
---|
282 |
|
---|
283 | if (add)
|
---|
284 | {
|
---|
285 | if (!BN_uadd(r,a,b)) return(0);
|
---|
286 | r->neg=neg;
|
---|
287 | return(1);
|
---|
288 | }
|
---|
289 |
|
---|
290 | /* We are actually doing a - b :-) */
|
---|
291 |
|
---|
292 | max=(a->top > b->top)?a->top:b->top;
|
---|
293 | if (bn_wexpand(r,max) == NULL) return(0);
|
---|
294 | if (BN_ucmp(a,b) < 0)
|
---|
295 | {
|
---|
296 | if (!BN_usub(r,b,a)) return(0);
|
---|
297 | r->neg=1;
|
---|
298 | }
|
---|
299 | else
|
---|
300 | {
|
---|
301 | if (!BN_usub(r,a,b)) return(0);
|
---|
302 | r->neg=0;
|
---|
303 | }
|
---|
304 | return(1);
|
---|
305 | }
|
---|
306 |
|
---|