1 /* $OpenBSD: bn_add.c,v 1.13 2018/07/23 18:07:21 tb 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 <stdio.h>
60
61 #include <openssl/err.h>
62
63 #include "bn_lcl.h"
64
65 int
BN_add(BIGNUM * r,const BIGNUM * a,const BIGNUM * b)66 BN_add(BIGNUM *r, const BIGNUM *a, const BIGNUM *b)
67 {
68 int ret, r_neg;
69
70 bn_check_top(a);
71 bn_check_top(b);
72
73 if (a->neg == b->neg) {
74 r_neg = a->neg;
75 ret = BN_uadd(r, a, b);
76 } else {
77 int cmp = BN_ucmp(a, b);
78
79 if (cmp > 0) {
80 r_neg = a->neg;
81 ret = BN_usub(r, a, b);
82 } else if (cmp < 0) {
83 r_neg = b->neg;
84 ret = BN_usub(r, b, a);
85 } else {
86 r_neg = 0;
87 BN_zero(r);
88 ret = 1;
89 }
90 }
91
92 r->neg = r_neg;
93 bn_check_top(r);
94 return ret;
95 }
96
97 int
BN_uadd(BIGNUM * r,const BIGNUM * a,const BIGNUM * b)98 BN_uadd(BIGNUM *r, const BIGNUM *a, const BIGNUM *b)
99 {
100 int max, min, dif;
101 const BN_ULONG *ap, *bp;
102 BN_ULONG *rp, carry, t1, t2;
103
104 bn_check_top(a);
105 bn_check_top(b);
106
107 if (a->top < b->top) {
108 const BIGNUM *tmp;
109
110 tmp = a;
111 a = b;
112 b = tmp;
113 }
114 max = a->top;
115 min = b->top;
116 dif = max - min;
117
118 if (bn_wexpand(r, max + 1) == NULL)
119 return 0;
120
121 r->top = max;
122
123 ap = a->d;
124 bp = b->d;
125 rp = r->d;
126
127 carry = bn_add_words(rp, ap, bp, min);
128 rp += min;
129 ap += min;
130
131 while (dif) {
132 dif--;
133 t1 = *(ap++);
134 t2 = (t1 + carry) & BN_MASK2;
135 *(rp++) = t2;
136 carry &= (t2 == 0);
137 }
138 *rp = carry;
139 r->top += carry;
140
141 r->neg = 0;
142 bn_check_top(r);
143 return 1;
144 }
145
146 int
BN_usub(BIGNUM * r,const BIGNUM * a,const BIGNUM * b)147 BN_usub(BIGNUM *r, const BIGNUM *a, const BIGNUM *b)
148 {
149 int max, min, dif;
150 const BN_ULONG *ap, *bp;
151 BN_ULONG t1, t2, borrow, *rp;
152
153 bn_check_top(a);
154 bn_check_top(b);
155
156 max = a->top;
157 min = b->top;
158 dif = max - min;
159
160 if (dif < 0) {
161 BNerror(BN_R_ARG2_LT_ARG3);
162 return 0;
163 }
164
165 if (bn_wexpand(r, max) == NULL)
166 return 0;
167
168 ap = a->d;
169 bp = b->d;
170 rp = r->d;
171
172 borrow = bn_sub_words(rp, ap, bp, min);
173 ap += min;
174 rp += min;
175
176 while (dif) {
177 dif--;
178 t1 = *(ap++);
179 t2 = (t1 - borrow) & BN_MASK2;
180 *(rp++) = t2;
181 borrow &= (t1 == 0);
182 }
183
184 while (max > 0 && *--rp == 0)
185 max--;
186
187 r->top = max;
188 r->neg = 0;
189 bn_correct_top(r);
190 return 1;
191 }
192
193 int
BN_sub(BIGNUM * r,const BIGNUM * a,const BIGNUM * b)194 BN_sub(BIGNUM *r, const BIGNUM *a, const BIGNUM *b)
195 {
196 int ret, r_neg;
197
198 bn_check_top(a);
199 bn_check_top(b);
200
201 if (a->neg != b->neg) {
202 r_neg = a->neg;
203 ret = BN_uadd(r, a, b);
204 } else {
205 int cmp = BN_ucmp(a, b);
206
207 if (cmp > 0) {
208 r_neg = a->neg;
209 ret = BN_usub(r, a, b);
210 } else if (cmp < 0) {
211 r_neg = !b->neg;
212 ret = BN_usub(r, b, a);
213 } else {
214 r_neg = 0;
215 BN_zero(r);
216 ret = 1;
217 }
218 }
219
220 r->neg = r_neg;
221 bn_check_top(r);
222 return ret;
223 }
224