|
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 |
|
65 /* The old slow way */ |
|
66 #if 0 |
|
67 EXPORT_C int BN_div(BIGNUM *dv, BIGNUM *rem, const BIGNUM *m, const BIGNUM *d, |
|
68 BN_CTX *ctx) |
|
69 { |
|
70 int i,nm,nd; |
|
71 int ret = 0; |
|
72 BIGNUM *D; |
|
73 |
|
74 bn_check_top(m); |
|
75 bn_check_top(d); |
|
76 if (BN_is_zero(d)) |
|
77 { |
|
78 BNerr(BN_F_BN_DIV,BN_R_DIV_BY_ZERO); |
|
79 return(0); |
|
80 } |
|
81 |
|
82 if (BN_ucmp(m,d) < 0) |
|
83 { |
|
84 if (rem != NULL) |
|
85 { if (BN_copy(rem,m) == NULL) return(0); } |
|
86 if (dv != NULL) BN_zero(dv); |
|
87 return(1); |
|
88 } |
|
89 |
|
90 BN_CTX_start(ctx); |
|
91 D = BN_CTX_get(ctx); |
|
92 if (dv == NULL) dv = BN_CTX_get(ctx); |
|
93 if (rem == NULL) rem = BN_CTX_get(ctx); |
|
94 if (D == NULL || dv == NULL || rem == NULL) |
|
95 goto end; |
|
96 |
|
97 nd=BN_num_bits(d); |
|
98 nm=BN_num_bits(m); |
|
99 if (BN_copy(D,d) == NULL) goto end; |
|
100 if (BN_copy(rem,m) == NULL) goto end; |
|
101 |
|
102 /* The next 2 are needed so we can do a dv->d[0]|=1 later |
|
103 * since BN_lshift1 will only work once there is a value :-) */ |
|
104 BN_zero(dv); |
|
105 bn_wexpand(dv,1); |
|
106 dv->top=1; |
|
107 |
|
108 if (!BN_lshift(D,D,nm-nd)) goto end; |
|
109 for (i=nm-nd; i>=0; i--) |
|
110 { |
|
111 if (!BN_lshift1(dv,dv)) goto end; |
|
112 if (BN_ucmp(rem,D) >= 0) |
|
113 { |
|
114 dv->d[0]|=1; |
|
115 if (!BN_usub(rem,rem,D)) goto end; |
|
116 } |
|
117 /* CAN IMPROVE (and have now :=) */ |
|
118 if (!BN_rshift1(D,D)) goto end; |
|
119 } |
|
120 rem->neg=BN_is_zero(rem)?0:m->neg; |
|
121 dv->neg=m->neg^d->neg; |
|
122 ret = 1; |
|
123 end: |
|
124 BN_CTX_end(ctx); |
|
125 return(ret); |
|
126 } |
|
127 |
|
128 #else |
|
129 |
|
130 #if !defined(OPENSSL_NO_ASM) && !defined(OPENSSL_NO_INLINE_ASM) \ |
|
131 && !defined(PEDANTIC) && !defined(BN_DIV3W) |
|
132 # if defined(__GNUC__) && __GNUC__>=2 |
|
133 # if defined(__i386) || defined (__i386__) |
|
134 /* |
|
135 * There were two reasons for implementing this template: |
|
136 * - GNU C generates a call to a function (__udivdi3 to be exact) |
|
137 * in reply to ((((BN_ULLONG)n0)<<BN_BITS2)|n1)/d0 (I fail to |
|
138 * understand why...); |
|
139 * - divl doesn't only calculate quotient, but also leaves |
|
140 * remainder in %edx which we can definitely use here:-) |
|
141 * |
|
142 * <appro@fy.chalmers.se> |
|
143 */ |
|
144 # define bn_div_words(n0,n1,d0) \ |
|
145 ({ asm volatile ( \ |
|
146 "divl %4" \ |
|
147 : "=a"(q), "=d"(rem) \ |
|
148 : "a"(n1), "d"(n0), "g"(d0) \ |
|
149 : "cc"); \ |
|
150 q; \ |
|
151 }) |
|
152 # define REMAINDER_IS_ALREADY_CALCULATED |
|
153 # elif defined(__x86_64) && defined(SIXTY_FOUR_BIT_LONG) |
|
154 /* |
|
155 * Same story here, but it's 128-bit by 64-bit division. Wow! |
|
156 * <appro@fy.chalmers.se> |
|
157 */ |
|
158 # define bn_div_words(n0,n1,d0) \ |
|
159 ({ asm volatile ( \ |
|
160 "divq %4" \ |
|
161 : "=a"(q), "=d"(rem) \ |
|
162 : "a"(n1), "d"(n0), "g"(d0) \ |
|
163 : "cc"); \ |
|
164 q; \ |
|
165 }) |
|
166 # define REMAINDER_IS_ALREADY_CALCULATED |
|
167 # endif /* __<cpu> */ |
|
168 # endif /* __GNUC__ */ |
|
169 #endif /* OPENSSL_NO_ASM */ |
|
170 |
|
171 |
|
172 /* BN_div[_no_branch] computes dv := num / divisor, rounding towards |
|
173 * zero, and sets up rm such that dv*divisor + rm = num holds. |
|
174 * Thus: |
|
175 * dv->neg == num->neg ^ divisor->neg (unless the result is zero) |
|
176 * rm->neg == num->neg (unless the remainder is zero) |
|
177 * If 'dv' or 'rm' is NULL, the respective value is not returned. |
|
178 */ |
|
179 static int BN_div_no_branch(BIGNUM *dv, BIGNUM *rm, const BIGNUM *num, |
|
180 const BIGNUM *divisor, BN_CTX *ctx); |
|
181 EXPORT_C int BN_div(BIGNUM *dv, BIGNUM *rm, const BIGNUM *num, const BIGNUM *divisor, |
|
182 BN_CTX *ctx) |
|
183 { |
|
184 int norm_shift,i,loop; |
|
185 BIGNUM *tmp,wnum,*snum,*sdiv,*res; |
|
186 BN_ULONG *resp,*wnump; |
|
187 BN_ULONG d0,d1; |
|
188 int num_n,div_n; |
|
189 if ((BN_get_flags(num, BN_FLG_CONSTTIME) != 0) || (BN_get_flags(divisor, BN_FLG_CONSTTIME) != 0)) |
|
190 { |
|
191 return BN_div_no_branch(dv, rm, num, divisor, ctx); |
|
192 } |
|
193 |
|
194 bn_check_top(dv); |
|
195 bn_check_top(rm); |
|
196 bn_check_top(num); |
|
197 bn_check_top(divisor); |
|
198 |
|
199 if (BN_is_zero(divisor)) |
|
200 { |
|
201 BNerr(BN_F_BN_DIV,BN_R_DIV_BY_ZERO); |
|
202 return(0); |
|
203 } |
|
204 |
|
205 if (BN_ucmp(num,divisor) < 0) |
|
206 { |
|
207 if (rm != NULL) |
|
208 { if (BN_copy(rm,num) == NULL) return(0); } |
|
209 if (dv != NULL) BN_zero(dv); |
|
210 return(1); |
|
211 } |
|
212 |
|
213 BN_CTX_start(ctx); |
|
214 tmp=BN_CTX_get(ctx); |
|
215 snum=BN_CTX_get(ctx); |
|
216 sdiv=BN_CTX_get(ctx); |
|
217 if (dv == NULL) |
|
218 res=BN_CTX_get(ctx); |
|
219 else res=dv; |
|
220 if (sdiv == NULL || res == NULL) goto err; |
|
221 |
|
222 /* First we normalise the numbers */ |
|
223 norm_shift=BN_BITS2-((BN_num_bits(divisor))%BN_BITS2); |
|
224 if (!(BN_lshift(sdiv,divisor,norm_shift))) goto err; |
|
225 sdiv->neg=0; |
|
226 norm_shift+=BN_BITS2; |
|
227 if (!(BN_lshift(snum,num,norm_shift))) goto err; |
|
228 snum->neg=0; |
|
229 div_n=sdiv->top; |
|
230 num_n=snum->top; |
|
231 loop=num_n-div_n; |
|
232 /* Lets setup a 'window' into snum |
|
233 * This is the part that corresponds to the current |
|
234 * 'area' being divided */ |
|
235 wnum.neg = 0; |
|
236 wnum.d = &(snum->d[loop]); |
|
237 wnum.top = div_n; |
|
238 /* only needed when BN_ucmp messes up the values between top and max */ |
|
239 wnum.dmax = snum->dmax - loop; /* so we don't step out of bounds */ |
|
240 |
|
241 /* Get the top 2 words of sdiv */ |
|
242 /* div_n=sdiv->top; */ |
|
243 d0=sdiv->d[div_n-1]; |
|
244 d1=(div_n == 1)?0:sdiv->d[div_n-2]; |
|
245 |
|
246 /* pointer to the 'top' of snum */ |
|
247 wnump= &(snum->d[num_n-1]); |
|
248 |
|
249 /* Setup to 'res' */ |
|
250 res->neg= (num->neg^divisor->neg); |
|
251 if (!bn_wexpand(res,(loop+1))) goto err; |
|
252 res->top=loop; |
|
253 resp= &(res->d[loop-1]); |
|
254 |
|
255 /* space for temp */ |
|
256 if (!bn_wexpand(tmp,(div_n+1))) goto err; |
|
257 |
|
258 if (BN_ucmp(&wnum,sdiv) >= 0) |
|
259 { |
|
260 /* If BN_DEBUG_RAND is defined BN_ucmp changes (via |
|
261 * bn_pollute) the const bignum arguments => |
|
262 * clean the values between top and max again */ |
|
263 bn_clear_top2max(&wnum); |
|
264 bn_sub_words(wnum.d, wnum.d, sdiv->d, div_n); |
|
265 *resp=1; |
|
266 } |
|
267 else |
|
268 res->top--; |
|
269 /* if res->top == 0 then clear the neg value otherwise decrease |
|
270 * the resp pointer */ |
|
271 if (res->top == 0) |
|
272 res->neg = 0; |
|
273 else |
|
274 resp--; |
|
275 |
|
276 for (i=0; i<loop-1; i++, wnump--, resp--) |
|
277 { |
|
278 BN_ULONG q,l0; |
|
279 /* the first part of the loop uses the top two words of |
|
280 * snum and sdiv to calculate a BN_ULONG q such that |
|
281 * | wnum - sdiv * q | < sdiv */ |
|
282 #if defined(BN_DIV3W) && !defined(OPENSSL_NO_ASM) |
|
283 BN_ULONG bn_div_3_words(BN_ULONG*,BN_ULONG,BN_ULONG); |
|
284 q=bn_div_3_words(wnump,d1,d0); |
|
285 #else |
|
286 BN_ULONG n0,n1,rem=0; |
|
287 |
|
288 n0=wnump[0]; |
|
289 n1=wnump[-1]; |
|
290 if (n0 == d0) |
|
291 q=BN_MASK2; |
|
292 else /* n0 < d0 */ |
|
293 { |
|
294 #ifdef BN_LLONG |
|
295 BN_ULLONG t2; |
|
296 |
|
297 #if defined(BN_LLONG) && defined(BN_DIV2W) && !defined(bn_div_words) |
|
298 q=(BN_ULONG)(((((BN_ULLONG)n0)<<BN_BITS2)|n1)/d0); |
|
299 #else |
|
300 q=bn_div_words(n0,n1,d0); |
|
301 #ifdef BN_DEBUG_LEVITTE |
|
302 fprintf(stderr,"DEBUG: bn_div_words(0x%08X,0x%08X,0x%08\ |
|
303 X) -> 0x%08X\n", |
|
304 n0, n1, d0, q); |
|
305 #endif |
|
306 #endif |
|
307 |
|
308 #ifndef REMAINDER_IS_ALREADY_CALCULATED |
|
309 /* |
|
310 * rem doesn't have to be BN_ULLONG. The least we |
|
311 * know it's less that d0, isn't it? |
|
312 */ |
|
313 rem=(n1-q*d0)&BN_MASK2; |
|
314 #endif |
|
315 t2=(BN_ULLONG)d1*q; |
|
316 |
|
317 for (;;) |
|
318 { |
|
319 if (t2 <= ((((BN_ULLONG)rem)<<BN_BITS2)|wnump[-2])) |
|
320 break; |
|
321 q--; |
|
322 rem += d0; |
|
323 if (rem < d0) break; /* don't let rem overflow */ |
|
324 t2 -= d1; |
|
325 } |
|
326 #else /* !BN_LLONG */ |
|
327 BN_ULONG t2l,t2h,ql,qh; |
|
328 |
|
329 q=bn_div_words(n0,n1,d0); |
|
330 #ifdef BN_DEBUG_LEVITTE |
|
331 fprintf(stderr,"DEBUG: bn_div_words(0x%08X,0x%08X,0x%08\ |
|
332 X) -> 0x%08X\n", |
|
333 n0, n1, d0, q); |
|
334 #endif |
|
335 #ifndef REMAINDER_IS_ALREADY_CALCULATED |
|
336 rem=(n1-q*d0)&BN_MASK2; |
|
337 #endif |
|
338 |
|
339 #if defined(BN_UMULT_LOHI) |
|
340 BN_UMULT_LOHI(t2l,t2h,d1,q); |
|
341 #elif defined(BN_UMULT_HIGH) |
|
342 t2l = d1 * q; |
|
343 t2h = BN_UMULT_HIGH(d1,q); |
|
344 #else |
|
345 t2l=LBITS(d1); t2h=HBITS(d1); |
|
346 ql =LBITS(q); qh =HBITS(q); |
|
347 mul64(t2l,t2h,ql,qh); /* t2=(BN_ULLONG)d1*q; */ |
|
348 #endif |
|
349 |
|
350 for (;;) |
|
351 { |
|
352 if ((t2h < rem) || |
|
353 ((t2h == rem) && (t2l <= wnump[-2]))) |
|
354 break; |
|
355 q--; |
|
356 rem += d0; |
|
357 if (rem < d0) break; /* don't let rem overflow */ |
|
358 if (t2l < d1) t2h--; t2l -= d1; |
|
359 } |
|
360 #endif /* !BN_LLONG */ |
|
361 } |
|
362 #endif /* !BN_DIV3W */ |
|
363 |
|
364 l0=bn_mul_words(tmp->d,sdiv->d,div_n,q); |
|
365 tmp->d[div_n]=l0; |
|
366 wnum.d--; |
|
367 /* ingore top values of the bignums just sub the two |
|
368 * BN_ULONG arrays with bn_sub_words */ |
|
369 if (bn_sub_words(wnum.d, wnum.d, tmp->d, div_n+1)) |
|
370 { |
|
371 /* Note: As we have considered only the leading |
|
372 * two BN_ULONGs in the calculation of q, sdiv * q |
|
373 * might be greater than wnum (but then (q-1) * sdiv |
|
374 * is less or equal than wnum) |
|
375 */ |
|
376 q--; |
|
377 if (bn_add_words(wnum.d, wnum.d, sdiv->d, div_n)) |
|
378 /* we can't have an overflow here (assuming |
|
379 * that q != 0, but if q == 0 then tmp is |
|
380 * zero anyway) */ |
|
381 (*wnump)++; |
|
382 } |
|
383 /* store part of the result */ |
|
384 *resp = q; |
|
385 } |
|
386 bn_correct_top(snum); |
|
387 if (rm != NULL) |
|
388 { |
|
389 /* Keep a copy of the neg flag in num because if rm==num |
|
390 * BN_rshift() will overwrite it. |
|
391 */ |
|
392 int neg = num->neg; |
|
393 BN_rshift(rm,snum,norm_shift); |
|
394 if (!BN_is_zero(rm)) |
|
395 rm->neg = neg; |
|
396 bn_check_top(rm); |
|
397 } |
|
398 BN_CTX_end(ctx); |
|
399 return(1); |
|
400 err: |
|
401 bn_check_top(rm); |
|
402 BN_CTX_end(ctx); |
|
403 return(0); |
|
404 } |
|
405 |
|
406 /* BN_div_no_branch is a special version of BN_div. It does not contain |
|
407 * branches that may leak sensitive information. |
|
408 */ |
|
409 static int BN_div_no_branch(BIGNUM *dv, BIGNUM *rm, const BIGNUM *num, |
|
410 const BIGNUM *divisor, BN_CTX *ctx) |
|
411 { |
|
412 int norm_shift,i,loop; |
|
413 BIGNUM *tmp,wnum,*snum,*sdiv,*res; |
|
414 BN_ULONG *resp,*wnump; |
|
415 BN_ULONG d0,d1; |
|
416 int num_n,div_n; |
|
417 |
|
418 bn_check_top(dv); |
|
419 bn_check_top(rm); |
|
420 bn_check_top(num); |
|
421 bn_check_top(divisor); |
|
422 |
|
423 if (BN_is_zero(divisor)) |
|
424 { |
|
425 BNerr(BN_F_BN_DIV_NO_BRANCH,BN_R_DIV_BY_ZERO); |
|
426 return(0); |
|
427 } |
|
428 |
|
429 BN_CTX_start(ctx); |
|
430 tmp=BN_CTX_get(ctx); |
|
431 snum=BN_CTX_get(ctx); |
|
432 sdiv=BN_CTX_get(ctx); |
|
433 if (dv == NULL) |
|
434 res=BN_CTX_get(ctx); |
|
435 else res=dv; |
|
436 if (sdiv == NULL || res == NULL) goto err; |
|
437 |
|
438 /* First we normalise the numbers */ |
|
439 norm_shift=BN_BITS2-((BN_num_bits(divisor))%BN_BITS2); |
|
440 if (!(BN_lshift(sdiv,divisor,norm_shift))) goto err; |
|
441 sdiv->neg=0; |
|
442 norm_shift+=BN_BITS2; |
|
443 if (!(BN_lshift(snum,num,norm_shift))) goto err; |
|
444 snum->neg=0; |
|
445 |
|
446 /* Since we don't know whether snum is larger than sdiv, |
|
447 * we pad snum with enough zeroes without changing its |
|
448 * value. |
|
449 */ |
|
450 if (snum->top <= sdiv->top+1) |
|
451 { |
|
452 if (bn_wexpand(snum, sdiv->top + 2) == NULL) goto err; |
|
453 for (i = snum->top; i < sdiv->top + 2; i++) snum->d[i] = 0; |
|
454 snum->top = sdiv->top + 2; |
|
455 } |
|
456 else |
|
457 { |
|
458 if (bn_wexpand(snum, snum->top + 1) == NULL) goto err; |
|
459 snum->d[snum->top] = 0; |
|
460 snum->top ++; |
|
461 } |
|
462 |
|
463 div_n=sdiv->top; |
|
464 num_n=snum->top; |
|
465 loop=num_n-div_n; |
|
466 /* Lets setup a 'window' into snum |
|
467 * This is the part that corresponds to the current |
|
468 * 'area' being divided */ |
|
469 wnum.neg = 0; |
|
470 wnum.d = &(snum->d[loop]); |
|
471 wnum.top = div_n; |
|
472 /* only needed when BN_ucmp messes up the values between top and max */ |
|
473 wnum.dmax = snum->dmax - loop; /* so we don't step out of bounds */ |
|
474 |
|
475 /* Get the top 2 words of sdiv */ |
|
476 /* div_n=sdiv->top; */ |
|
477 d0=sdiv->d[div_n-1]; |
|
478 d1=(div_n == 1)?0:sdiv->d[div_n-2]; |
|
479 |
|
480 /* pointer to the 'top' of snum */ |
|
481 wnump= &(snum->d[num_n-1]); |
|
482 |
|
483 /* Setup to 'res' */ |
|
484 res->neg= (num->neg^divisor->neg); |
|
485 if (!bn_wexpand(res,(loop+1))) goto err; |
|
486 res->top=loop-1; |
|
487 resp= &(res->d[loop-1]); |
|
488 |
|
489 /* space for temp */ |
|
490 if (!bn_wexpand(tmp,(div_n+1))) goto err; |
|
491 |
|
492 /* if res->top == 0 then clear the neg value otherwise decrease |
|
493 * the resp pointer */ |
|
494 if (res->top == 0) |
|
495 res->neg = 0; |
|
496 else |
|
497 resp--; |
|
498 |
|
499 for (i=0; i<loop-1; i++, wnump--, resp--) |
|
500 { |
|
501 BN_ULONG q,l0; |
|
502 /* the first part of the loop uses the top two words of |
|
503 * snum and sdiv to calculate a BN_ULONG q such that |
|
504 * | wnum - sdiv * q | < sdiv */ |
|
505 #if defined(BN_DIV3W) && !defined(OPENSSL_NO_ASM) |
|
506 BN_ULONG bn_div_3_words(BN_ULONG*,BN_ULONG,BN_ULONG); |
|
507 q=bn_div_3_words(wnump,d1,d0); |
|
508 #else |
|
509 BN_ULONG n0,n1,rem=0; |
|
510 |
|
511 n0=wnump[0]; |
|
512 n1=wnump[-1]; |
|
513 if (n0 == d0) |
|
514 q=BN_MASK2; |
|
515 else /* n0 < d0 */ |
|
516 { |
|
517 #ifdef BN_LLONG |
|
518 BN_ULLONG t2; |
|
519 |
|
520 #if defined(BN_LLONG) && defined(BN_DIV2W) && !defined(bn_div_words) |
|
521 q=(BN_ULONG)(((((BN_ULLONG)n0)<<BN_BITS2)|n1)/d0); |
|
522 #else |
|
523 q=bn_div_words(n0,n1,d0); |
|
524 #ifdef BN_DEBUG_LEVITTE |
|
525 fprintf(stderr,"DEBUG: bn_div_words(0x%08X,0x%08X,0x%08\ |
|
526 X) -> 0x%08X\n", |
|
527 n0, n1, d0, q); |
|
528 #endif |
|
529 #endif |
|
530 |
|
531 #ifndef REMAINDER_IS_ALREADY_CALCULATED |
|
532 /* |
|
533 * rem doesn't have to be BN_ULLONG. The least we |
|
534 * know it's less that d0, isn't it? |
|
535 */ |
|
536 rem=(n1-q*d0)&BN_MASK2; |
|
537 #endif |
|
538 t2=(BN_ULLONG)d1*q; |
|
539 |
|
540 for (;;) |
|
541 { |
|
542 if (t2 <= ((((BN_ULLONG)rem)<<BN_BITS2)|wnump[-2])) |
|
543 break; |
|
544 q--; |
|
545 rem += d0; |
|
546 if (rem < d0) break; /* don't let rem overflow */ |
|
547 t2 -= d1; |
|
548 } |
|
549 #else /* !BN_LLONG */ |
|
550 BN_ULONG t2l,t2h,ql,qh; |
|
551 |
|
552 q=bn_div_words(n0,n1,d0); |
|
553 #ifdef BN_DEBUG_LEVITTE |
|
554 fprintf(stderr,"DEBUG: bn_div_words(0x%08X,0x%08X,0x%08\ |
|
555 X) -> 0x%08X\n", |
|
556 n0, n1, d0, q); |
|
557 #endif |
|
558 #ifndef REMAINDER_IS_ALREADY_CALCULATED |
|
559 rem=(n1-q*d0)&BN_MASK2; |
|
560 #endif |
|
561 |
|
562 #if defined(BN_UMULT_LOHI) |
|
563 BN_UMULT_LOHI(t2l,t2h,d1,q); |
|
564 #elif defined(BN_UMULT_HIGH) |
|
565 t2l = d1 * q; |
|
566 t2h = BN_UMULT_HIGH(d1,q); |
|
567 #else |
|
568 t2l=LBITS(d1); t2h=HBITS(d1); |
|
569 ql =LBITS(q); qh =HBITS(q); |
|
570 mul64(t2l,t2h,ql,qh); /* t2=(BN_ULLONG)d1*q; */ |
|
571 #endif |
|
572 |
|
573 for (;;) |
|
574 { |
|
575 if ((t2h < rem) || |
|
576 ((t2h == rem) && (t2l <= wnump[-2]))) |
|
577 break; |
|
578 q--; |
|
579 rem += d0; |
|
580 if (rem < d0) break; /* don't let rem overflow */ |
|
581 if (t2l < d1) t2h--; t2l -= d1; |
|
582 } |
|
583 #endif /* !BN_LLONG */ |
|
584 } |
|
585 #endif /* !BN_DIV3W */ |
|
586 |
|
587 l0=bn_mul_words(tmp->d,sdiv->d,div_n,q); |
|
588 tmp->d[div_n]=l0; |
|
589 wnum.d--; |
|
590 /* ingore top values of the bignums just sub the two |
|
591 * BN_ULONG arrays with bn_sub_words */ |
|
592 if (bn_sub_words(wnum.d, wnum.d, tmp->d, div_n+1)) |
|
593 { |
|
594 /* Note: As we have considered only the leading |
|
595 * two BN_ULONGs in the calculation of q, sdiv * q |
|
596 * might be greater than wnum (but then (q-1) * sdiv |
|
597 * is less or equal than wnum) |
|
598 */ |
|
599 q--; |
|
600 if (bn_add_words(wnum.d, wnum.d, sdiv->d, div_n)) |
|
601 /* we can't have an overflow here (assuming |
|
602 * that q != 0, but if q == 0 then tmp is |
|
603 * zero anyway) */ |
|
604 (*wnump)++; |
|
605 } |
|
606 /* store part of the result */ |
|
607 *resp = q; |
|
608 } |
|
609 bn_correct_top(snum); |
|
610 if (rm != NULL) |
|
611 { |
|
612 /* Keep a copy of the neg flag in num because if rm==num |
|
613 * BN_rshift() will overwrite it. |
|
614 */ |
|
615 int neg = num->neg; |
|
616 BN_rshift(rm,snum,norm_shift); |
|
617 if (!BN_is_zero(rm)) |
|
618 rm->neg = neg; |
|
619 bn_check_top(rm); |
|
620 } |
|
621 bn_correct_top(res); |
|
622 BN_CTX_end(ctx); |
|
623 return(1); |
|
624 err: |
|
625 bn_check_top(rm); |
|
626 BN_CTX_end(ctx); |
|
627 return(0); |
|
628 } |
|
629 |
|
630 #endif |