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