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