]>
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 | ||
84c15db5 | 10 | #include <openssl/bn.h> |
b39fc560 | 11 | #include "internal/cryptlib.h" |
d02b48c6 RE |
12 | #include "bn_lcl.h" |
13 | ||
14 | /* The old slow way */ | |
4a6222d7 | 15 | #if 0 |
0bde1089 | 16 | int BN_div(BIGNUM *dv, BIGNUM *rem, const BIGNUM *m, const BIGNUM *d, |
0f113f3e MC |
17 | BN_CTX *ctx) |
18 | { | |
19 | int i, nm, nd; | |
20 | int ret = 0; | |
21 | BIGNUM *D; | |
22 | ||
23 | bn_check_top(m); | |
24 | bn_check_top(d); | |
25 | if (BN_is_zero(d)) { | |
26 | BNerr(BN_F_BN_DIV, BN_R_DIV_BY_ZERO); | |
27 | return (0); | |
28 | } | |
29 | ||
30 | if (BN_ucmp(m, d) < 0) { | |
31 | if (rem != NULL) { | |
32 | if (BN_copy(rem, m) == NULL) | |
33 | return (0); | |
34 | } | |
35 | if (dv != NULL) | |
36 | BN_zero(dv); | |
37 | return (1); | |
38 | } | |
39 | ||
40 | BN_CTX_start(ctx); | |
41 | D = BN_CTX_get(ctx); | |
42 | if (dv == NULL) | |
43 | dv = BN_CTX_get(ctx); | |
44 | if (rem == NULL) | |
45 | rem = BN_CTX_get(ctx); | |
46 | if (D == NULL || dv == NULL || rem == NULL) | |
47 | goto end; | |
48 | ||
49 | nd = BN_num_bits(d); | |
50 | nm = BN_num_bits(m); | |
51 | if (BN_copy(D, d) == NULL) | |
52 | goto end; | |
53 | if (BN_copy(rem, m) == NULL) | |
54 | goto end; | |
55 | ||
56 | /* | |
57 | * The next 2 are needed so we can do a dv->d[0]|=1 later since | |
58 | * BN_lshift1 will only work once there is a value :-) | |
59 | */ | |
60 | BN_zero(dv); | |
61 | if (bn_wexpand(dv, 1) == NULL) | |
62 | goto end; | |
63 | dv->top = 1; | |
64 | ||
65 | if (!BN_lshift(D, D, nm - nd)) | |
66 | goto end; | |
67 | for (i = nm - nd; i >= 0; i--) { | |
68 | if (!BN_lshift1(dv, dv)) | |
69 | goto end; | |
70 | if (BN_ucmp(rem, D) >= 0) { | |
71 | dv->d[0] |= 1; | |
72 | if (!BN_usub(rem, rem, D)) | |
73 | goto end; | |
74 | } | |
d02b48c6 | 75 | /* CAN IMPROVE (and have now :=) */ |
0f113f3e MC |
76 | if (!BN_rshift1(D, D)) |
77 | goto end; | |
78 | } | |
79 | rem->neg = BN_is_zero(rem) ? 0 : m->neg; | |
80 | dv->neg = m->neg ^ d->neg; | |
81 | ret = 1; | |
9b141126 | 82 | end: |
0f113f3e MC |
83 | BN_CTX_end(ctx); |
84 | return (ret); | |
85 | } | |
d02b48c6 RE |
86 | |
87 | #else | |
88 | ||
0f113f3e | 89 | # if !defined(OPENSSL_NO_ASM) && !defined(OPENSSL_NO_INLINE_ASM) \ |
cf1b7d96 | 90 | && !defined(PEDANTIC) && !defined(BN_DIV3W) |
0f113f3e MC |
91 | # if defined(__GNUC__) && __GNUC__>=2 |
92 | # if defined(__i386) || defined (__i386__) | |
c80fd6b2 | 93 | /*- |
4a6222d7 UM |
94 | * There were two reasons for implementing this template: |
95 | * - GNU C generates a call to a function (__udivdi3 to be exact) | |
96 | * in reply to ((((BN_ULLONG)n0)<<BN_BITS2)|n1)/d0 (I fail to | |
97 | * understand why...); | |
98 | * - divl doesn't only calculate quotient, but also leaves | |
99 | * remainder in %edx which we can definitely use here:-) | |
100 | * | |
0f113f3e | 101 | * <appro@fy.chalmers.se> |
4a6222d7 | 102 | */ |
0f113f3e MC |
103 | # undef bn_div_words |
104 | # define bn_div_words(n0,n1,d0) \ | |
105 | ({ asm volatile ( \ | |
106 | "divl %4" \ | |
107 | : "=a"(q), "=d"(rem) \ | |
108 | : "a"(n1), "d"(n0), "g"(d0) \ | |
109 | : "cc"); \ | |
110 | q; \ | |
111 | }) | |
112 | # define REMAINDER_IS_ALREADY_CALCULATED | |
113 | # elif defined(__x86_64) && defined(SIXTY_FOUR_BIT_LONG) | |
2f98abbc AP |
114 | /* |
115 | * Same story here, but it's 128-bit by 64-bit division. Wow! | |
0f113f3e | 116 | * <appro@fy.chalmers.se> |
2f98abbc | 117 | */ |
0f113f3e MC |
118 | # undef bn_div_words |
119 | # define bn_div_words(n0,n1,d0) \ | |
120 | ({ asm volatile ( \ | |
121 | "divq %4" \ | |
122 | : "=a"(q), "=d"(rem) \ | |
123 | : "a"(n1), "d"(n0), "g"(d0) \ | |
124 | : "cc"); \ | |
125 | q; \ | |
126 | }) | |
127 | # define REMAINDER_IS_ALREADY_CALCULATED | |
128 | # endif /* __<cpu> */ | |
129 | # endif /* __GNUC__ */ | |
130 | # endif /* OPENSSL_NO_ASM */ | |
78a0c1f1 | 131 | |
1d97c843 TH |
132 | /*- |
133 | * BN_div computes dv := num / divisor, rounding towards | |
55525742 | 134 | * zero, and sets up rm such that dv*divisor + rm = num holds. |
78a0c1f1 BM |
135 | * Thus: |
136 | * dv->neg == num->neg ^ divisor->neg (unless the result is zero) | |
137 | * rm->neg == num->neg (unless the remainder is zero) | |
138 | * If 'dv' or 'rm' is NULL, the respective value is not returned. | |
139 | */ | |
84c15db5 | 140 | int BN_div(BIGNUM *dv, BIGNUM *rm, const BIGNUM *num, const BIGNUM *divisor, |
0f113f3e MC |
141 | BN_CTX *ctx) |
142 | { | |
143 | int norm_shift, i, loop; | |
144 | BIGNUM *tmp, wnum, *snum, *sdiv, *res; | |
145 | BN_ULONG *resp, *wnump; | |
146 | BN_ULONG d0, d1; | |
147 | int num_n, div_n; | |
148 | int no_branch = 0; | |
149 | ||
150 | /* | |
151 | * Invalid zero-padding would have particularly bad consequences so don't | |
152 | * just rely on bn_check_top() here (bn_check_top() works only for | |
153 | * BN_DEBUG builds) | |
154 | */ | |
155 | if ((num->top > 0 && num->d[num->top - 1] == 0) || | |
156 | (divisor->top > 0 && divisor->d[divisor->top - 1] == 0)) { | |
157 | BNerr(BN_F_BN_DIV, BN_R_NOT_INITIALIZED); | |
158 | return 0; | |
159 | } | |
160 | ||
161 | bn_check_top(num); | |
162 | bn_check_top(divisor); | |
163 | ||
164 | if ((BN_get_flags(num, BN_FLG_CONSTTIME) != 0) | |
165 | || (BN_get_flags(divisor, BN_FLG_CONSTTIME) != 0)) { | |
166 | no_branch = 1; | |
167 | } | |
168 | ||
169 | bn_check_top(dv); | |
170 | bn_check_top(rm); | |
171 | /*- bn_check_top(num); *//* | |
172 | * 'num' has been checked already | |
173 | */ | |
174 | /*- bn_check_top(divisor); *//* | |
175 | * 'divisor' has been checked already | |
176 | */ | |
177 | ||
178 | if (BN_is_zero(divisor)) { | |
179 | BNerr(BN_F_BN_DIV, BN_R_DIV_BY_ZERO); | |
180 | return (0); | |
181 | } | |
182 | ||
183 | if (!no_branch && BN_ucmp(num, divisor) < 0) { | |
184 | if (rm != NULL) { | |
185 | if (BN_copy(rm, num) == NULL) | |
186 | return (0); | |
187 | } | |
188 | if (dv != NULL) | |
189 | BN_zero(dv); | |
190 | return (1); | |
191 | } | |
192 | ||
193 | BN_CTX_start(ctx); | |
194 | tmp = BN_CTX_get(ctx); | |
195 | snum = BN_CTX_get(ctx); | |
196 | sdiv = BN_CTX_get(ctx); | |
197 | if (dv == NULL) | |
198 | res = BN_CTX_get(ctx); | |
199 | else | |
200 | res = dv; | |
201 | if (sdiv == NULL || res == NULL || tmp == NULL || snum == NULL) | |
202 | goto err; | |
203 | ||
204 | /* First we normalise the numbers */ | |
205 | norm_shift = BN_BITS2 - ((BN_num_bits(divisor)) % BN_BITS2); | |
206 | if (!(BN_lshift(sdiv, divisor, norm_shift))) | |
207 | goto err; | |
208 | sdiv->neg = 0; | |
209 | norm_shift += BN_BITS2; | |
210 | if (!(BN_lshift(snum, num, norm_shift))) | |
211 | goto err; | |
212 | snum->neg = 0; | |
213 | ||
214 | if (no_branch) { | |
215 | /* | |
216 | * Since we don't know whether snum is larger than sdiv, we pad snum | |
217 | * with enough zeroes without changing its value. | |
218 | */ | |
219 | if (snum->top <= sdiv->top + 1) { | |
220 | if (bn_wexpand(snum, sdiv->top + 2) == NULL) | |
221 | goto err; | |
222 | for (i = snum->top; i < sdiv->top + 2; i++) | |
223 | snum->d[i] = 0; | |
224 | snum->top = sdiv->top + 2; | |
225 | } else { | |
226 | if (bn_wexpand(snum, snum->top + 1) == NULL) | |
227 | goto err; | |
228 | snum->d[snum->top] = 0; | |
229 | snum->top++; | |
230 | } | |
231 | } | |
232 | ||
233 | div_n = sdiv->top; | |
234 | num_n = snum->top; | |
235 | loop = num_n - div_n; | |
236 | /* | |
237 | * Lets setup a 'window' into snum This is the part that corresponds to | |
238 | * the current 'area' being divided | |
239 | */ | |
240 | wnum.neg = 0; | |
241 | wnum.d = &(snum->d[loop]); | |
242 | wnum.top = div_n; | |
243 | /* | |
244 | * only needed when BN_ucmp messes up the values between top and max | |
245 | */ | |
246 | wnum.dmax = snum->dmax - loop; /* so we don't step out of bounds */ | |
247 | ||
248 | /* Get the top 2 words of sdiv */ | |
249 | /* div_n=sdiv->top; */ | |
250 | d0 = sdiv->d[div_n - 1]; | |
251 | d1 = (div_n == 1) ? 0 : sdiv->d[div_n - 2]; | |
252 | ||
253 | /* pointer to the 'top' of snum */ | |
254 | wnump = &(snum->d[num_n - 1]); | |
255 | ||
256 | /* Setup to 'res' */ | |
257 | res->neg = (num->neg ^ divisor->neg); | |
258 | if (!bn_wexpand(res, (loop + 1))) | |
259 | goto err; | |
260 | res->top = loop - no_branch; | |
261 | resp = &(res->d[loop - 1]); | |
262 | ||
263 | /* space for temp */ | |
264 | if (!bn_wexpand(tmp, (div_n + 1))) | |
265 | goto err; | |
266 | ||
267 | if (!no_branch) { | |
268 | if (BN_ucmp(&wnum, sdiv) >= 0) { | |
269 | /* | |
270 | * If BN_DEBUG_RAND is defined BN_ucmp changes (via bn_pollute) | |
271 | * the const bignum arguments => clean the values between top and | |
272 | * max again | |
273 | */ | |
274 | bn_clear_top2max(&wnum); | |
275 | bn_sub_words(wnum.d, wnum.d, sdiv->d, div_n); | |
276 | *resp = 1; | |
277 | } else | |
278 | res->top--; | |
279 | } | |
280 | ||
281 | /* | |
282 | * if res->top == 0 then clear the neg value otherwise decrease the resp | |
283 | * pointer | |
284 | */ | |
285 | if (res->top == 0) | |
286 | res->neg = 0; | |
287 | else | |
288 | resp--; | |
289 | ||
290 | for (i = 0; i < loop - 1; i++, wnump--, resp--) { | |
291 | BN_ULONG q, l0; | |
292 | /* | |
293 | * the first part of the loop uses the top two words of snum and sdiv | |
294 | * to calculate a BN_ULONG q such that | wnum - sdiv * q | < sdiv | |
295 | */ | |
296 | # if defined(BN_DIV3W) && !defined(OPENSSL_NO_ASM) | |
297 | BN_ULONG bn_div_3_words(BN_ULONG *, BN_ULONG, BN_ULONG); | |
298 | q = bn_div_3_words(wnump, d1, d0); | |
299 | # else | |
300 | BN_ULONG n0, n1, rem = 0; | |
301 | ||
302 | n0 = wnump[0]; | |
303 | n1 = wnump[-1]; | |
304 | if (n0 == d0) | |
305 | q = BN_MASK2; | |
306 | else { /* n0 < d0 */ | |
307 | ||
308 | # ifdef BN_LLONG | |
309 | BN_ULLONG t2; | |
310 | ||
311 | # if defined(BN_LLONG) && defined(BN_DIV2W) && !defined(bn_div_words) | |
312 | q = (BN_ULONG)(((((BN_ULLONG) n0) << BN_BITS2) | n1) / d0); | |
313 | # else | |
314 | q = bn_div_words(n0, n1, d0); | |
0f113f3e MC |
315 | # endif |
316 | ||
317 | # ifndef REMAINDER_IS_ALREADY_CALCULATED | |
318 | /* | |
319 | * rem doesn't have to be BN_ULLONG. The least we | |
320 | * know it's less that d0, isn't it? | |
321 | */ | |
322 | rem = (n1 - q * d0) & BN_MASK2; | |
323 | # endif | |
324 | t2 = (BN_ULLONG) d1 *q; | |
325 | ||
326 | for (;;) { | |
327 | if (t2 <= ((((BN_ULLONG) rem) << BN_BITS2) | wnump[-2])) | |
328 | break; | |
329 | q--; | |
330 | rem += d0; | |
331 | if (rem < d0) | |
332 | break; /* don't let rem overflow */ | |
333 | t2 -= d1; | |
334 | } | |
335 | # else /* !BN_LLONG */ | |
336 | BN_ULONG t2l, t2h; | |
337 | ||
338 | q = bn_div_words(n0, n1, d0); | |
0f113f3e MC |
339 | # ifndef REMAINDER_IS_ALREADY_CALCULATED |
340 | rem = (n1 - q * d0) & BN_MASK2; | |
341 | # endif | |
342 | ||
343 | # if defined(BN_UMULT_LOHI) | |
344 | BN_UMULT_LOHI(t2l, t2h, d1, q); | |
345 | # elif defined(BN_UMULT_HIGH) | |
346 | t2l = d1 * q; | |
347 | t2h = BN_UMULT_HIGH(d1, q); | |
348 | # else | |
349 | { | |
350 | BN_ULONG ql, qh; | |
351 | t2l = LBITS(d1); | |
352 | t2h = HBITS(d1); | |
353 | ql = LBITS(q); | |
354 | qh = HBITS(q); | |
355 | mul64(t2l, t2h, ql, qh); /* t2=(BN_ULLONG)d1*q; */ | |
356 | } | |
357 | # endif | |
358 | ||
359 | for (;;) { | |
360 | if ((t2h < rem) || ((t2h == rem) && (t2l <= wnump[-2]))) | |
361 | break; | |
362 | q--; | |
363 | rem += d0; | |
364 | if (rem < d0) | |
365 | break; /* don't let rem overflow */ | |
366 | if (t2l < d1) | |
367 | t2h--; | |
368 | t2l -= d1; | |
369 | } | |
370 | # endif /* !BN_LLONG */ | |
371 | } | |
372 | # endif /* !BN_DIV3W */ | |
373 | ||
374 | l0 = bn_mul_words(tmp->d, sdiv->d, div_n, q); | |
375 | tmp->d[div_n] = l0; | |
376 | wnum.d--; | |
377 | /* | |
378 | * ingore top values of the bignums just sub the two BN_ULONG arrays | |
379 | * with bn_sub_words | |
380 | */ | |
381 | if (bn_sub_words(wnum.d, wnum.d, tmp->d, div_n + 1)) { | |
382 | /* | |
383 | * Note: As we have considered only the leading two BN_ULONGs in | |
384 | * the calculation of q, sdiv * q might be greater than wnum (but | |
385 | * then (q-1) * sdiv is less or equal than wnum) | |
386 | */ | |
387 | q--; | |
388 | if (bn_add_words(wnum.d, wnum.d, sdiv->d, div_n)) | |
389 | /* | |
390 | * we can't have an overflow here (assuming that q != 0, but | |
391 | * if q == 0 then tmp is zero anyway) | |
392 | */ | |
393 | (*wnump)++; | |
394 | } | |
395 | /* store part of the result */ | |
396 | *resp = q; | |
397 | } | |
398 | bn_correct_top(snum); | |
399 | if (rm != NULL) { | |
400 | /* | |
401 | * Keep a copy of the neg flag in num because if rm==num BN_rshift() | |
402 | * will overwrite it. | |
403 | */ | |
404 | int neg = num->neg; | |
405 | BN_rshift(rm, snum, norm_shift); | |
406 | if (!BN_is_zero(rm)) | |
407 | rm->neg = neg; | |
408 | bn_check_top(rm); | |
409 | } | |
410 | if (no_branch) | |
411 | bn_correct_top(res); | |
412 | BN_CTX_end(ctx); | |
413 | return (1); | |
414 | err: | |
415 | bn_check_top(rm); | |
416 | BN_CTX_end(ctx); | |
417 | return (0); | |
418 | } | |
d02b48c6 | 419 | #endif |