summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--src/lib/libcrypto/bn/bn_add.c224
1 files changed, 67 insertions, 157 deletions
diff --git a/src/lib/libcrypto/bn/bn_add.c b/src/lib/libcrypto/bn/bn_add.c
index 2e82d280ec..048a136b95 100644
--- a/src/lib/libcrypto/bn/bn_add.c
+++ b/src/lib/libcrypto/bn/bn_add.c
@@ -1,4 +1,4 @@
1/* $OpenBSD: bn_add.c,v 1.12 2018/06/10 19:38:19 tb Exp $ */ 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) 2/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
3 * All rights reserved. 3 * All rights reserved.
4 * 4 *
@@ -62,61 +62,51 @@
62 62
63#include "bn_lcl.h" 63#include "bn_lcl.h"
64 64
65/* r can == a or b */
66int 65int
67BN_add(BIGNUM *r, const BIGNUM *a, const BIGNUM *b) 66BN_add(BIGNUM *r, const BIGNUM *a, const BIGNUM *b)
68{ 67{
69 const BIGNUM *tmp; 68 int ret, r_neg;
70 int a_neg = a->neg, ret;
71 69
72 bn_check_top(a); 70 bn_check_top(a);
73 bn_check_top(b); 71 bn_check_top(b);
74 72
75 /* a + b a+b 73 if (a->neg == b->neg) {
76 * a + -b a-b 74 r_neg = a->neg;
77 * -a + b b-a 75 ret = BN_uadd(r, a, b);
78 * -a + -b -(a+b) 76 } else {
79 */ 77 int cmp = BN_ucmp(a, b);
80 if (a_neg ^ b->neg) { 78
81 /* only one is negative */ 79 if (cmp > 0) {
82 if (a_neg) { 80 r_neg = a->neg;
83 tmp = a; 81 ret = BN_usub(r, a, b);
84 a = b; 82 } else if (cmp < 0) {
85 b = tmp; 83 r_neg = b->neg;
86 } 84 ret = BN_usub(r, b, a);
87
88 /* we are now a - b */
89
90 if (BN_ucmp(a, b) < 0) {
91 if (!BN_usub(r, b, a))
92 return (0);
93 r->neg = 1;
94 } else { 85 } else {
95 if (!BN_usub(r, a, b)) 86 r_neg = 0;
96 return (0); 87 BN_zero(r);
97 r->neg = 0; 88 ret = 1;
98 } 89 }
99 return (1);
100 } 90 }
101 91
102 ret = BN_uadd(r, a, b); 92 r->neg = r_neg;
103 r->neg = a_neg;
104 bn_check_top(r); 93 bn_check_top(r);
105 return ret; 94 return ret;
106} 95}
107 96
108/* unsigned add of b to a */
109int 97int
110BN_uadd(BIGNUM *r, const BIGNUM *a, const BIGNUM *b) 98BN_uadd(BIGNUM *r, const BIGNUM *a, const BIGNUM *b)
111{ 99{
112 int max, min, dif; 100 int max, min, dif;
113 BN_ULONG *ap, *bp, *rp, carry, t1, t2; 101 const BN_ULONG *ap, *bp;
114 const BIGNUM *tmp; 102 BN_ULONG *rp, carry, t1, t2;
115 103
116 bn_check_top(a); 104 bn_check_top(a);
117 bn_check_top(b); 105 bn_check_top(b);
118 106
119 if (a->top < b->top) { 107 if (a->top < b->top) {
108 const BIGNUM *tmp;
109
120 tmp = a; 110 tmp = a;
121 a = b; 111 a = b;
122 b = tmp; 112 b = tmp;
@@ -137,41 +127,28 @@ BN_uadd(BIGNUM *r, const BIGNUM *a, const BIGNUM *b)
137 carry = bn_add_words(rp, ap, bp, min); 127 carry = bn_add_words(rp, ap, bp, min);
138 rp += min; 128 rp += min;
139 ap += min; 129 ap += min;
140 bp += min; 130
141 131 while (dif) {
142 if (carry) { 132 dif--;
143 while (dif) { 133 t1 = *(ap++);
144 dif--; 134 t2 = (t1 + carry) & BN_MASK2;
145 t1 = *(ap++); 135 *(rp++) = t2;
146 t2 = (t1 + 1) & BN_MASK2; 136 carry &= (t2 == 0);
147 *(rp++) = t2;
148 if (t2) {
149 carry = 0;
150 break;
151 }
152 }
153 if (carry) {
154 /* carry != 0 => dif == 0 */
155 *rp = 1;
156 r->top++;
157 }
158 } 137 }
159 if (dif && rp != ap) 138 *rp = carry;
160 while (dif--) 139 r->top += carry;
161 /* copy remaining words if ap != rp */ 140
162 *(rp++) = *(ap++);
163 r->neg = 0; 141 r->neg = 0;
164 bn_check_top(r); 142 bn_check_top(r);
165 return 1; 143 return 1;
166} 144}
167 145
168/* unsigned subtraction of b from a, a must be larger than b. */
169int 146int
170BN_usub(BIGNUM *r, const BIGNUM *a, const BIGNUM *b) 147BN_usub(BIGNUM *r, const BIGNUM *a, const BIGNUM *b)
171{ 148{
172 int max, min, dif; 149 int max, min, dif;
173 BN_ULONG t1, t2, *ap, *bp, *rp; 150 const BN_ULONG *ap, *bp;
174 int i, carry; 151 BN_ULONG t1, t2, borrow, *rp;
175 152
176 bn_check_top(a); 153 bn_check_top(a);
177 bn_check_top(b); 154 bn_check_top(b);
@@ -180,134 +157,67 @@ BN_usub(BIGNUM *r, const BIGNUM *a, const BIGNUM *b)
180 min = b->top; 157 min = b->top;
181 dif = max - min; 158 dif = max - min;
182 159
183 if (dif < 0) /* hmm... should not be happening */ 160 if (dif < 0) {
184 {
185 BNerror(BN_R_ARG2_LT_ARG3); 161 BNerror(BN_R_ARG2_LT_ARG3);
186 return (0); 162 return 0;
187 } 163 }
188 164
189 if (bn_wexpand(r, max) == NULL) 165 if (bn_wexpand(r, max) == NULL)
190 return (0); 166 return 0;
191 167
192 ap = a->d; 168 ap = a->d;
193 bp = b->d; 169 bp = b->d;
194 rp = r->d; 170 rp = r->d;
195 171
196#if 1 172 borrow = bn_sub_words(rp, ap, bp, min);
197 carry = 0;
198 for (i = min; i != 0; i--) {
199 t1= *(ap++);
200 t2= *(bp++);
201 if (carry) {
202 carry = (t1 <= t2);
203 t1 = (t1 - t2 - 1)&BN_MASK2;
204 } else {
205 carry = (t1 < t2);
206 t1 = (t1 - t2)&BN_MASK2;
207 }
208 *(rp++) = t1&BN_MASK2;
209 }
210#else
211 carry = bn_sub_words(rp, ap, bp, min);
212 ap += min; 173 ap += min;
213 bp += min;
214 rp += min; 174 rp += min;
215#endif 175
216 if (carry) /* subtracted */ 176 while (dif) {
217 { 177 dif--;
218 if (!dif) 178 t1 = *(ap++);
219 /* error: a < b */ 179 t2 = (t1 - borrow) & BN_MASK2;
220 return 0; 180 *(rp++) = t2;
221 while (dif) { 181 borrow &= (t1 == 0);
222 dif--;
223 t1 = *(ap++);
224 t2 = (t1 - 1)&BN_MASK2;
225 *(rp++) = t2;
226 if (t1)
227 break;
228 }
229 }
230#if 0
231 memcpy(rp, ap, sizeof(*rp)*(max - i));
232#else
233 if (rp != ap) {
234 for (;;) {
235 if (!dif--)
236 break;
237 rp[0] = ap[0];
238 if (!dif--)
239 break;
240 rp[1] = ap[1];
241 if (!dif--)
242 break;
243 rp[2] = ap[2];
244 if (!dif--)
245 break;
246 rp[3] = ap[3];
247 rp += 4;
248 ap += 4;
249 }
250 } 182 }
251#endif 183
184 while (max > 0 && *--rp == 0)
185 max--;
252 186
253 r->top = max; 187 r->top = max;
254 r->neg = 0; 188 r->neg = 0;
255 bn_correct_top(r); 189 bn_correct_top(r);
256 return (1); 190 return 1;
257} 191}
258 192
259int 193int
260BN_sub(BIGNUM *r, const BIGNUM *a, const BIGNUM *b) 194BN_sub(BIGNUM *r, const BIGNUM *a, const BIGNUM *b)
261{ 195{
262 int max; 196 int ret, r_neg;
263 int add = 0, neg = 0;
264 const BIGNUM *tmp;
265 197
266 bn_check_top(a); 198 bn_check_top(a);
267 bn_check_top(b); 199 bn_check_top(b);
268 200
269 /* a - b a-b 201 if (a->neg != b->neg) {
270 * a - -b a+b 202 r_neg = a->neg;
271 * -a - b -(a+b) 203 ret = BN_uadd(r, a, b);
272 * -a - -b b-a
273 */
274 if (a->neg) {
275 if (b->neg) {
276 tmp = a;
277 a = b;
278 b = tmp;
279 } else {
280 add = 1;
281 neg = 1;
282 }
283 } else { 204 } else {
284 if (b->neg) { 205 int cmp = BN_ucmp(a, b);
285 add = 1; 206
286 neg = 0; 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;
287 } 217 }
288 } 218 }
289 219
290 if (add) { 220 r->neg = r_neg;
291 if (!BN_uadd(r, a, b))
292 return (0);
293 r->neg = neg;
294 return (1);
295 }
296
297 /* We are actually doing a - b :-) */
298
299 max = (a->top > b->top) ? a->top : b->top;
300 if (bn_wexpand(r, max) == NULL)
301 return (0);
302 if (BN_ucmp(a, b) < 0) {
303 if (!BN_usub(r, b, a))
304 return (0);
305 r->neg = 1;
306 } else {
307 if (!BN_usub(r, a, b))
308 return (0);
309 r->neg = 0;
310 }
311 bn_check_top(r); 221 bn_check_top(r);
312 return (1); 222 return ret;
313} 223}
generated by cgit v1.2.3-55-g6feb (git 2.39.1) at 2025-03-20 11:11:10 +0000