]>
Commit | Line | Data |
---|---|---|
4f22f405 RS |
1 | /* |
2 | * Copyright 1995-2016 The OpenSSL Project Authors. All Rights Reserved. | |
d02b48c6 | 3 | * |
4f22f405 RS |
4 | * Licensed under the OpenSSL license (the "License"). You may not use |
5 | * this file except in compliance with the License. You can obtain a copy | |
6 | * in the file LICENSE in the source distribution or at | |
7 | * https://www.openssl.org/source/license.html | |
d02b48c6 RE |
8 | */ |
9 | ||
b39fc560 | 10 | #include "internal/cryptlib.h" |
d02b48c6 RE |
11 | #include "bn_lcl.h" |
12 | ||
13 | /* r can == a or b */ | |
dd8dec69 | 14 | int BN_add(BIGNUM *r, const BIGNUM *a, const BIGNUM *b) |
0f113f3e MC |
15 | { |
16 | const BIGNUM *tmp; | |
17 | int a_neg = a->neg, ret; | |
18 | ||
19 | bn_check_top(a); | |
20 | bn_check_top(b); | |
21 | ||
50e735f9 MC |
22 | /*- |
23 | * a + b a+b | |
24 | * a + -b a-b | |
25 | * -a + b b-a | |
26 | * -a + -b -(a+b) | |
27 | */ | |
0f113f3e MC |
28 | if (a_neg ^ b->neg) { |
29 | /* only one is negative */ | |
30 | if (a_neg) { | |
31 | tmp = a; | |
32 | a = b; | |
33 | b = tmp; | |
34 | } | |
35 | ||
36 | /* we are now a - b */ | |
37 | ||
38 | if (BN_ucmp(a, b) < 0) { | |
39 | if (!BN_usub(r, b, a)) | |
40 | return (0); | |
41 | r->neg = 1; | |
42 | } else { | |
43 | if (!BN_usub(r, a, b)) | |
44 | return (0); | |
45 | r->neg = 0; | |
46 | } | |
47 | return (1); | |
48 | } | |
49 | ||
50 | ret = BN_uadd(r, a, b); | |
51 | r->neg = a_neg; | |
52 | bn_check_top(r); | |
53 | return ret; | |
54 | } | |
d02b48c6 | 55 | |
380e145d | 56 | /* unsigned add of b to a */ |
84c15db5 | 57 | int BN_uadd(BIGNUM *r, const BIGNUM *a, const BIGNUM *b) |
0f113f3e MC |
58 | { |
59 | int max, min, dif; | |
60 | const BN_ULONG *ap, *bp; | |
61 | BN_ULONG *rp, carry, t1, t2; | |
62 | const BIGNUM *tmp; | |
63 | ||
64 | bn_check_top(a); | |
65 | bn_check_top(b); | |
66 | ||
67 | if (a->top < b->top) { | |
68 | tmp = a; | |
69 | a = b; | |
70 | b = tmp; | |
71 | } | |
72 | max = a->top; | |
73 | min = b->top; | |
74 | dif = max - min; | |
75 | ||
76 | if (bn_wexpand(r, max + 1) == NULL) | |
77 | return 0; | |
78 | ||
79 | r->top = max; | |
80 | ||
81 | ap = a->d; | |
82 | bp = b->d; | |
83 | rp = r->d; | |
84 | ||
85 | carry = bn_add_words(rp, ap, bp, min); | |
86 | rp += min; | |
87 | ap += min; | |
88 | bp += min; | |
89 | ||
90 | if (carry) { | |
91 | while (dif) { | |
92 | dif--; | |
93 | t1 = *(ap++); | |
94 | t2 = (t1 + 1) & BN_MASK2; | |
95 | *(rp++) = t2; | |
96 | if (t2) { | |
97 | carry = 0; | |
98 | break; | |
99 | } | |
100 | } | |
101 | if (carry) { | |
102 | /* carry != 0 => dif == 0 */ | |
103 | *rp = 1; | |
104 | r->top++; | |
105 | } | |
106 | } | |
107 | if (dif && rp != ap) | |
108 | while (dif--) | |
109 | /* copy remaining words if ap != rp */ | |
110 | *(rp++) = *(ap++); | |
111 | r->neg = 0; | |
112 | bn_check_top(r); | |
113 | return 1; | |
114 | } | |
dfeab068 RE |
115 | |
116 | /* unsigned subtraction of b from a, a must be larger than b. */ | |
84c15db5 | 117 | int BN_usub(BIGNUM *r, const BIGNUM *a, const BIGNUM *b) |
0f113f3e MC |
118 | { |
119 | int max, min, dif; | |
120 | register BN_ULONG t1, t2, *rp; | |
121 | register const BN_ULONG *ap, *bp; | |
122 | int i, carry; | |
dfeab068 | 123 | |
0f113f3e MC |
124 | bn_check_top(a); |
125 | bn_check_top(b); | |
dfeab068 | 126 | |
0f113f3e MC |
127 | max = a->top; |
128 | min = b->top; | |
129 | dif = max - min; | |
380e145d | 130 | |
0f113f3e MC |
131 | if (dif < 0) { /* hmm... should not be happening */ |
132 | BNerr(BN_F_BN_USUB, BN_R_ARG2_LT_ARG3); | |
133 | return (0); | |
134 | } | |
dfeab068 | 135 | |
0f113f3e MC |
136 | if (bn_wexpand(r, max) == NULL) |
137 | return (0); | |
dfeab068 | 138 | |
0f113f3e MC |
139 | ap = a->d; |
140 | bp = b->d; | |
141 | rp = r->d; | |
dfeab068 RE |
142 | |
143 | #if 1 | |
0f113f3e MC |
144 | carry = 0; |
145 | for (i = min; i != 0; i--) { | |
146 | t1 = *(ap++); | |
147 | t2 = *(bp++); | |
148 | if (carry) { | |
149 | carry = (t1 <= t2); | |
150 | t1 = (t1 - t2 - 1) & BN_MASK2; | |
151 | } else { | |
152 | carry = (t1 < t2); | |
153 | t1 = (t1 - t2) & BN_MASK2; | |
154 | } | |
155 | *(rp++) = t1 & BN_MASK2; | |
156 | } | |
dfeab068 | 157 | #else |
0f113f3e MC |
158 | carry = bn_sub_words(rp, ap, bp, min); |
159 | ap += min; | |
160 | bp += min; | |
161 | rp += min; | |
dfeab068 | 162 | #endif |
0f113f3e MC |
163 | if (carry) { /* subtracted */ |
164 | if (!dif) | |
165 | /* error: a < b */ | |
166 | return 0; | |
167 | while (dif) { | |
168 | dif--; | |
169 | t1 = *(ap++); | |
170 | t2 = (t1 - 1) & BN_MASK2; | |
171 | *(rp++) = t2; | |
172 | if (t1) | |
173 | break; | |
174 | } | |
175 | } | |
9f6795e7 | 176 | if (dif && ap != rp) |
9f040d6d | 177 | memcpy(rp, ap, sizeof(*rp) * dif); |
dfeab068 | 178 | |
0f113f3e MC |
179 | r->top = max; |
180 | r->neg = 0; | |
181 | bn_correct_top(r); | |
182 | return (1); | |
183 | } | |
dfeab068 | 184 | |
84c15db5 | 185 | int BN_sub(BIGNUM *r, const BIGNUM *a, const BIGNUM *b) |
0f113f3e MC |
186 | { |
187 | int max; | |
188 | int add = 0, neg = 0; | |
189 | const BIGNUM *tmp; | |
190 | ||
191 | bn_check_top(a); | |
192 | bn_check_top(b); | |
193 | ||
50e735f9 MC |
194 | /*- |
195 | * a - b a-b | |
196 | * a - -b a+b | |
197 | * -a - b -(a+b) | |
198 | * -a - -b b-a | |
199 | */ | |
0f113f3e MC |
200 | if (a->neg) { |
201 | if (b->neg) { | |
202 | tmp = a; | |
203 | a = b; | |
204 | b = tmp; | |
205 | } else { | |
206 | add = 1; | |
207 | neg = 1; | |
208 | } | |
209 | } else { | |
210 | if (b->neg) { | |
211 | add = 1; | |
212 | neg = 0; | |
213 | } | |
214 | } | |
215 | ||
216 | if (add) { | |
217 | if (!BN_uadd(r, a, b)) | |
218 | return (0); | |
219 | r->neg = neg; | |
220 | return (1); | |
221 | } | |
222 | ||
223 | /* We are actually doing a - b :-) */ | |
224 | ||
225 | max = (a->top > b->top) ? a->top : b->top; | |
226 | if (bn_wexpand(r, max) == NULL) | |
227 | return (0); | |
228 | if (BN_ucmp(a, b) < 0) { | |
229 | if (!BN_usub(r, b, a)) | |
230 | return (0); | |
231 | r->neg = 1; | |
232 | } else { | |
233 | if (!BN_usub(r, a, b)) | |
234 | return (0); | |
235 | r->neg = 0; | |
236 | } | |
237 | bn_check_top(r); | |
238 | return (1); | |
239 | } |