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