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