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