1 /* $OpenBSD: bn_add.c,v 1.26 2023/07/08 12:21:58 beck Exp $ */
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 <assert.h>
60 #include <limits.h>
61 #include <stdio.h>
62
63 #include <openssl/err.h>
64
65 #include "bn_arch.h"
66 #include "bn_local.h"
67 #include "bn_internal.h"
68
69 /*
70 * bn_add_words() computes (carry:r[i]) = a[i] + b[i] + carry, where a and b
71 * are both arrays of words. Any carry resulting from the addition is returned.
72 */
73 #ifndef HAVE_BN_ADD_WORDS
74 BN_ULONG
bn_add_words(BN_ULONG * r,const BN_ULONG * a,const BN_ULONG * b,int n)75 bn_add_words(BN_ULONG *r, const BN_ULONG *a, const BN_ULONG *b, int n)
76 {
77 BN_ULONG carry = 0;
78
79 assert(n >= 0);
80 if (n <= 0)
81 return 0;
82
83 while (n & ~3) {
84 bn_qwaddqw(a[3], a[2], a[1], a[0], b[3], b[2], b[1], b[0],
85 carry, &carry, &r[3], &r[2], &r[1], &r[0]);
86 a += 4;
87 b += 4;
88 r += 4;
89 n -= 4;
90 }
91 while (n) {
92 bn_addw_addw(a[0], b[0], carry, &carry, &r[0]);
93 a++;
94 b++;
95 r++;
96 n--;
97 }
98 return carry;
99 }
100 #endif
101
102 /*
103 * bn_add() computes (carry:r[i]) = a[i] + b[i] + carry, where a and b are both
104 * arrays of words (r may be the same as a or b). The length of a and b may
105 * differ, while r must be at least max(a_len, b_len) in length. Any carry
106 * resulting from the addition is returned.
107 */
108 #ifndef HAVE_BN_ADD
109 BN_ULONG
bn_add(BN_ULONG * r,int r_len,const BN_ULONG * a,int a_len,const BN_ULONG * b,int b_len)110 bn_add(BN_ULONG *r, int r_len, const BN_ULONG *a, int a_len, const BN_ULONG *b,
111 int b_len)
112 {
113 int min_len, diff_len;
114 BN_ULONG carry = 0;
115
116 if ((min_len = a_len) > b_len)
117 min_len = b_len;
118
119 diff_len = a_len - b_len;
120
121 carry = bn_add_words(r, a, b, min_len);
122
123 a += min_len;
124 b += min_len;
125 r += min_len;
126
127 /* XXX - consider doing four at a time to match bn_add_words(). */
128 while (diff_len < 0) {
129 /* Compute r[0] = 0 + b[0] + carry. */
130 bn_addw(b[0], carry, &carry, &r[0]);
131 diff_len++;
132 b++;
133 r++;
134 }
135
136 /* XXX - consider doing four at a time to match bn_add_words(). */
137 while (diff_len > 0) {
138 /* Compute r[0] = a[0] + 0 + carry. */
139 bn_addw(a[0], carry, &carry, &r[0]);
140 diff_len--;
141 a++;
142 r++;
143 }
144
145 return carry;
146 }
147 #endif
148
149 /*
150 * bn_sub_words() computes (borrow:r[i]) = a[i] - b[i] - borrow, where a and b
151 * are both arrays of words. Any borrow resulting from the subtraction is
152 * returned.
153 */
154 #ifndef HAVE_BN_SUB_WORDS
155 BN_ULONG
bn_sub_words(BN_ULONG * r,const BN_ULONG * a,const BN_ULONG * b,int n)156 bn_sub_words(BN_ULONG *r, const BN_ULONG *a, const BN_ULONG *b, int n)
157 {
158 BN_ULONG borrow = 0;
159
160 assert(n >= 0);
161 if (n <= 0)
162 return 0;
163
164 while (n & ~3) {
165 bn_qwsubqw(a[3], a[2], a[1], a[0], b[3], b[2], b[1], b[0],
166 borrow, &borrow, &r[3], &r[2], &r[1], &r[0]);
167 a += 4;
168 b += 4;
169 r += 4;
170 n -= 4;
171 }
172 while (n) {
173 bn_subw_subw(a[0], b[0], borrow, &borrow, &r[0]);
174 a++;
175 b++;
176 r++;
177 n--;
178 }
179 return borrow;
180 }
181 #endif
182
183 /*
184 * bn_sub() computes (borrow:r[i]) = a[i] - b[i] - borrow, where a and b are both
185 * arrays of words (r may be the same as a or b). The length of a and b may
186 * differ, while r must be at least max(a_len, b_len) in length. Any borrow
187 * resulting from the subtraction is returned.
188 */
189 #ifndef HAVE_BN_SUB
190 BN_ULONG
bn_sub(BN_ULONG * r,int r_len,const BN_ULONG * a,int a_len,const BN_ULONG * b,int b_len)191 bn_sub(BN_ULONG *r, int r_len, const BN_ULONG *a, int a_len, const BN_ULONG *b,
192 int b_len)
193 {
194 int min_len, diff_len;
195 BN_ULONG borrow = 0;
196
197 if ((min_len = a_len) > b_len)
198 min_len = b_len;
199
200 diff_len = a_len - b_len;
201
202 borrow = bn_sub_words(r, a, b, min_len);
203
204 a += min_len;
205 b += min_len;
206 r += min_len;
207
208 /* XXX - consider doing four at a time to match bn_sub_words. */
209 while (diff_len < 0) {
210 /* Compute r[0] = 0 - b[0] - borrow. */
211 bn_subw(0 - b[0], borrow, &borrow, &r[0]);
212 diff_len++;
213 b++;
214 r++;
215 }
216
217 /* XXX - consider doing four at a time to match bn_sub_words. */
218 while (diff_len > 0) {
219 /* Compute r[0] = a[0] - 0 - borrow. */
220 bn_subw(a[0], borrow, &borrow, &r[0]);
221 diff_len--;
222 a++;
223 r++;
224 }
225
226 return borrow;
227 }
228 #endif
229
230 int
BN_uadd(BIGNUM * r,const BIGNUM * a,const BIGNUM * b)231 BN_uadd(BIGNUM *r, const BIGNUM *a, const BIGNUM *b)
232 {
233 BN_ULONG carry;
234 int rn;
235
236 if ((rn = a->top) < b->top)
237 rn = b->top;
238 if (rn == INT_MAX)
239 return 0;
240 if (!bn_wexpand(r, rn + 1))
241 return 0;
242
243 carry = bn_add(r->d, rn, a->d, a->top, b->d, b->top);
244 r->d[rn] = carry;
245
246 r->top = rn + (carry & 1);
247 r->neg = 0;
248
249 return 1;
250 }
251 LCRYPTO_ALIAS(BN_uadd);
252
253 int
BN_usub(BIGNUM * r,const BIGNUM * a,const BIGNUM * b)254 BN_usub(BIGNUM *r, const BIGNUM *a, const BIGNUM *b)
255 {
256 BN_ULONG borrow;
257 int rn;
258
259 if (a->top < b->top) {
260 BNerror(BN_R_ARG2_LT_ARG3);
261 return 0;
262 }
263 rn = a->top;
264
265 if (!bn_wexpand(r, rn))
266 return 0;
267
268 borrow = bn_sub(r->d, rn, a->d, a->top, b->d, b->top);
269 if (borrow > 0) {
270 BNerror(BN_R_ARG2_LT_ARG3);
271 return 0;
272 }
273
274 r->top = rn;
275 r->neg = 0;
276
277 bn_correct_top(r);
278
279 return 1;
280 }
281 LCRYPTO_ALIAS(BN_usub);
282
283 int
BN_add(BIGNUM * r,const BIGNUM * a,const BIGNUM * b)284 BN_add(BIGNUM *r, const BIGNUM *a, const BIGNUM *b)
285 {
286 int ret, r_neg;
287
288 if (a->neg == b->neg) {
289 r_neg = a->neg;
290 ret = BN_uadd(r, a, b);
291 } else {
292 int cmp = BN_ucmp(a, b);
293
294 if (cmp > 0) {
295 r_neg = a->neg;
296 ret = BN_usub(r, a, b);
297 } else if (cmp < 0) {
298 r_neg = b->neg;
299 ret = BN_usub(r, b, a);
300 } else {
301 r_neg = 0;
302 BN_zero(r);
303 ret = 1;
304 }
305 }
306
307 BN_set_negative(r, r_neg);
308
309 return ret;
310 }
311 LCRYPTO_ALIAS(BN_add);
312
313 int
BN_sub(BIGNUM * r,const BIGNUM * a,const BIGNUM * b)314 BN_sub(BIGNUM *r, const BIGNUM *a, const BIGNUM *b)
315 {
316 int ret, r_neg;
317
318 if (a->neg != b->neg) {
319 r_neg = a->neg;
320 ret = BN_uadd(r, a, b);
321 } else {
322 int cmp = BN_ucmp(a, b);
323
324 if (cmp > 0) {
325 r_neg = a->neg;
326 ret = BN_usub(r, a, b);
327 } else if (cmp < 0) {
328 r_neg = !b->neg;
329 ret = BN_usub(r, b, a);
330 } else {
331 r_neg = 0;
332 BN_zero(r);
333 ret = 1;
334 }
335 }
336
337 BN_set_negative(r, r_neg);
338
339 return ret;
340 }
341 LCRYPTO_ALIAS(BN_sub);
342