bn_div.c revision e915367e40b579d18ac13c9c58c15fec614d9890
5619558151f1aa4249b3ead979e76876e29278b6Bob Halley#include "../rename.h"
a7038d1a0513c8e804937ebc95fc9cb3a46c04f5Mark Andrews/* crypto/bn/bn_div.c */
40f53fa8d9c6a4fc38c0014495e7a42b08f52481David Lawrence/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
5619558151f1aa4249b3ead979e76876e29278b6Bob Halley * All rights reserved.
5619558151f1aa4249b3ead979e76876e29278b6Bob Halley *
5619558151f1aa4249b3ead979e76876e29278b6Bob Halley * This package is an SSL implementation written
40f53fa8d9c6a4fc38c0014495e7a42b08f52481David Lawrence * by Eric Young (eay@cryptsoft.com).
15a44745412679c30a6d022733925af70a38b715David Lawrence * The implementation was written so as to conform with Netscapes SSL.
15a44745412679c30a6d022733925af70a38b715David Lawrence *
15a44745412679c30a6d022733925af70a38b715David Lawrence * This library is free for commercial and non-commercial use as long as
15a44745412679c30a6d022733925af70a38b715David Lawrence * the following conditions are aheared to. The following conditions
15a44745412679c30a6d022733925af70a38b715David Lawrence * apply to all code found in this distribution, be it the RC4, RSA,
15a44745412679c30a6d022733925af70a38b715David Lawrence * lhash, DES, etc., code; not just the SSL code. The SSL documentation
15a44745412679c30a6d022733925af70a38b715David Lawrence * included with this distribution is covered by the same copyright terms
15a44745412679c30a6d022733925af70a38b715David Lawrence * except that the holder is Tim Hudson (tjh@cryptsoft.com).
5619558151f1aa4249b3ead979e76876e29278b6Bob Halley *
5619558151f1aa4249b3ead979e76876e29278b6Bob Halley * Copyright remains Eric Young's, and as such any Copyright notices in
35541328a8c18ba1f984300dfe30ec8713c90031Mark Andrews * the code are not to be removed.
9c3531d72aeaad6c5f01efe6a1c82023e1379e4dDavid Lawrence * If this package is used in a product, Eric Young should be given attribution
110d1702731f42dd620879c1d765ebe91f3920ceMichael Graff * as the author of the parts of the library used.
110d1702731f42dd620879c1d765ebe91f3920ceMichael Graff * This can be in the form of a textual message at program startup or
c3b708aaf1bb0a118e0e11befa1b732acfb1d079Bob Halley * in documentation (online or textual) provided with the package.
5619558151f1aa4249b3ead979e76876e29278b6Bob Halley *
1a69a1a78cfaa86f3b68bbc965232b7876d4da2aDavid Lawrence * Redistribution and use in source and binary forms, with or without
def8e47c688e2480a4539d69c3d1a0a28a7c0550Mark Andrews * modification, are permitted provided that the following conditions
364a82f7c25b62967678027043425201a5e5171aBob Halley * are met:
5619558151f1aa4249b3ead979e76876e29278b6Bob Halley * 1. Redistributions of source code must retain the copyright
1a69a1a78cfaa86f3b68bbc965232b7876d4da2aDavid Lawrence * notice, this list of conditions and the following disclaimer.
8dfa9caeec8e68db0c937e347a3d6629e7627d54Bob Halley * 2. Redistributions in binary form must reproduce the above copyright
54f959d12b5a1f9315fbf6a776c6d349316e9686Bob Halley * notice, this list of conditions and the following disclaimer in the
5619558151f1aa4249b3ead979e76876e29278b6Bob Halley * documentation and/or other materials provided with the distribution.
52637f592f705ca93fadc218e403fd55e8ce4aeaMark Andrews * 3. All advertising materials mentioning features or use of this software
5619558151f1aa4249b3ead979e76876e29278b6Bob Halley * must display the following acknowledgement:
5619558151f1aa4249b3ead979e76876e29278b6Bob Halley * "This product includes cryptographic software written by
5619558151f1aa4249b3ead979e76876e29278b6Bob Halley * Eric Young (eay@cryptsoft.com)"
5619558151f1aa4249b3ead979e76876e29278b6Bob Halley * The word 'cryptographic' can be left out if the rouines from the library
5619558151f1aa4249b3ead979e76876e29278b6Bob Halley * being used are not cryptographic related :-).
5619558151f1aa4249b3ead979e76876e29278b6Bob Halley * 4. If you include any Windows specific code (or a derivative thereof) from
5619558151f1aa4249b3ead979e76876e29278b6Bob Halley * the apps directory (application code) you must include an acknowledgement:
5619558151f1aa4249b3ead979e76876e29278b6Bob Halley * "This product includes software written by Tim Hudson (tjh@cryptsoft.com)"
5619558151f1aa4249b3ead979e76876e29278b6Bob Halley *
5619558151f1aa4249b3ead979e76876e29278b6Bob Halley * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND
078d49b63324f01d98301ee21671abee0c41fcdeBob Halley * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
5619558151f1aa4249b3ead979e76876e29278b6Bob Halley * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
5619558151f1aa4249b3ead979e76876e29278b6Bob Halley * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
904a5734375869ffb504ed8cde6b68cafadb6d64Bob Halley * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
5619558151f1aa4249b3ead979e76876e29278b6Bob Halley * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
5619558151f1aa4249b3ead979e76876e29278b6Bob Halley * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
ca67883a666bdf314d3da958d5195e7215b1f797Bob Halley * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
732e0731dec1922747bb3b3147cf2c3d16b22eaaBob Halley * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
b12f0228b32775ee688ed21ddbf3a116c1adfb43Michael Graff * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
61fb42c4ef45d88e115bd769c30c4f36b461870bMark Andrews * SUCH DAMAGE.
5619558151f1aa4249b3ead979e76876e29278b6Bob Halley *
5619558151f1aa4249b3ead979e76876e29278b6Bob Halley * The licence and distribution terms for any publically available version or
5619558151f1aa4249b3ead979e76876e29278b6Bob Halley * derivative of this code cannot be changed. i.e. this code cannot simply be
80b782f356f0692c11b4e52e8dd46ec41704e5a2Mark Andrews * copied and put under another distribution licence
e496615043400500492fa7b891c515c8e7cb7d08Bob Halley * [including the GNU Public Licence.]
35541328a8c18ba1f984300dfe30ec8713c90031Mark Andrews */
5619558151f1aa4249b3ead979e76876e29278b6Bob Halley
5619558151f1aa4249b3ead979e76876e29278b6Bob Halley#include <stdio.h>
5619558151f1aa4249b3ead979e76876e29278b6Bob Halley#include <openssl/bn.h>
5619558151f1aa4249b3ead979e76876e29278b6Bob Halley#include "cryptlib.h"
5619558151f1aa4249b3ead979e76876e29278b6Bob Halley#include "bn_lcl.h"
5619558151f1aa4249b3ead979e76876e29278b6Bob Halley
5619558151f1aa4249b3ead979e76876e29278b6Bob Halley/* The old slow way */
5619558151f1aa4249b3ead979e76876e29278b6Bob Halley#if 0
5619558151f1aa4249b3ead979e76876e29278b6Bob Halleyint BN_div(BIGNUM *dv, BIGNUM *rem, const BIGNUM *m, const BIGNUM *d,
078d49b63324f01d98301ee21671abee0c41fcdeBob Halley BN_CTX *ctx)
5619558151f1aa4249b3ead979e76876e29278b6Bob Halley {
40f53fa8d9c6a4fc38c0014495e7a42b08f52481David Lawrence int i,nm,nd;
5619558151f1aa4249b3ead979e76876e29278b6Bob Halley int ret = 0;
5619558151f1aa4249b3ead979e76876e29278b6Bob Halley BIGNUM *D;
904a5734375869ffb504ed8cde6b68cafadb6d64Bob Halley
5619558151f1aa4249b3ead979e76876e29278b6Bob Halley bn_check_top(m);
5619558151f1aa4249b3ead979e76876e29278b6Bob Halley bn_check_top(d);
ca67883a666bdf314d3da958d5195e7215b1f797Bob Halley if (BN_is_zero(d))
732e0731dec1922747bb3b3147cf2c3d16b22eaaBob Halley {
b12f0228b32775ee688ed21ddbf3a116c1adfb43Michael Graff BNerr(BN_F_BN_DIV,BN_R_DIV_BY_ZERO);
61fb42c4ef45d88e115bd769c30c4f36b461870bMark Andrews return(0);
5619558151f1aa4249b3ead979e76876e29278b6Bob Halley }
5619558151f1aa4249b3ead979e76876e29278b6Bob Halley
5619558151f1aa4249b3ead979e76876e29278b6Bob Halley if (BN_ucmp(m,d) < 0)
80b782f356f0692c11b4e52e8dd46ec41704e5a2Mark Andrews {
e496615043400500492fa7b891c515c8e7cb7d08Bob Halley if (rem != NULL)
5619558151f1aa4249b3ead979e76876e29278b6Bob Halley { if (BN_copy(rem,m) == NULL) return(0); }
5619558151f1aa4249b3ead979e76876e29278b6Bob Halley if (dv != NULL) BN_zero(dv);
5619558151f1aa4249b3ead979e76876e29278b6Bob Halley return(1);
5619558151f1aa4249b3ead979e76876e29278b6Bob Halley }
5619558151f1aa4249b3ead979e76876e29278b6Bob Halley
5619558151f1aa4249b3ead979e76876e29278b6Bob Halley BN_CTX_start(ctx);
2cd0c38115b1efb043ed3104c0d08e51ceade0d7Bob Halley D = BN_CTX_get(ctx);
5619558151f1aa4249b3ead979e76876e29278b6Bob Halley if (dv == NULL) dv = BN_CTX_get(ctx);
5619558151f1aa4249b3ead979e76876e29278b6Bob Halley if (rem == NULL) rem = BN_CTX_get(ctx);
078d49b63324f01d98301ee21671abee0c41fcdeBob Halley if (D == NULL || dv == NULL || rem == NULL)
0180ccf72c79b98eb8ee5abbb7331aec6951dd9fBob Halley goto end;
5619558151f1aa4249b3ead979e76876e29278b6Bob Halley
5619558151f1aa4249b3ead979e76876e29278b6Bob Halley nd=BN_num_bits(d);
5619558151f1aa4249b3ead979e76876e29278b6Bob Halley nm=BN_num_bits(m);
5619558151f1aa4249b3ead979e76876e29278b6Bob Halley if (BN_copy(D,d) == NULL) goto end;
904a5734375869ffb504ed8cde6b68cafadb6d64Bob Halley if (BN_copy(rem,m) == NULL) goto end;
5619558151f1aa4249b3ead979e76876e29278b6Bob Halley
5619558151f1aa4249b3ead979e76876e29278b6Bob Halley /* The next 2 are needed so we can do a dv->d[0]|=1 later
ca67883a666bdf314d3da958d5195e7215b1f797Bob Halley * since BN_lshift1 will only work once there is a value :-) */
732e0731dec1922747bb3b3147cf2c3d16b22eaaBob Halley BN_zero(dv);
b12f0228b32775ee688ed21ddbf3a116c1adfb43Michael Graff bn_wexpand(dv,1);
61fb42c4ef45d88e115bd769c30c4f36b461870bMark Andrews dv->top=1;
5619558151f1aa4249b3ead979e76876e29278b6Bob Halley
5619558151f1aa4249b3ead979e76876e29278b6Bob Halley if (!BN_lshift(D,D,nm-nd)) goto end;
5619558151f1aa4249b3ead979e76876e29278b6Bob Halley for (i=nm-nd; i>=0; i--)
80b782f356f0692c11b4e52e8dd46ec41704e5a2Mark Andrews {
e496615043400500492fa7b891c515c8e7cb7d08Bob Halley if (!BN_lshift1(dv,dv)) goto end;
35541328a8c18ba1f984300dfe30ec8713c90031Mark Andrews if (BN_ucmp(rem,D) >= 0)
5619558151f1aa4249b3ead979e76876e29278b6Bob Halley {
5619558151f1aa4249b3ead979e76876e29278b6Bob Halley dv->d[0]|=1;
28640d1da26d561f4137122fe64e9e8cc08bf11eBob Halley if (!BN_usub(rem,rem,D)) goto end;
28640d1da26d561f4137122fe64e9e8cc08bf11eBob Halley }
28640d1da26d561f4137122fe64e9e8cc08bf11eBob Halley/* CAN IMPROVE (and have now :=) */
28640d1da26d561f4137122fe64e9e8cc08bf11eBob Halley if (!BN_rshift1(D,D)) goto end;
28640d1da26d561f4137122fe64e9e8cc08bf11eBob Halley }
40f53fa8d9c6a4fc38c0014495e7a42b08f52481David Lawrence rem->neg=BN_is_zero(rem)?0:m->neg;
28640d1da26d561f4137122fe64e9e8cc08bf11eBob Halley dv->neg=m->neg^d->neg;
28640d1da26d561f4137122fe64e9e8cc08bf11eBob Halley ret = 1;
28640d1da26d561f4137122fe64e9e8cc08bf11eBob Halley end:
28640d1da26d561f4137122fe64e9e8cc08bf11eBob Halley BN_CTX_end(ctx);
28640d1da26d561f4137122fe64e9e8cc08bf11eBob Halley return(ret);
28640d1da26d561f4137122fe64e9e8cc08bf11eBob Halley }
28640d1da26d561f4137122fe64e9e8cc08bf11eBob Halley
28640d1da26d561f4137122fe64e9e8cc08bf11eBob Halley#else
bf345589ce0b0b64533d4566e4992a0e63aac6f5Bob Halley
bf345589ce0b0b64533d4566e4992a0e63aac6f5Bob Halley#if !defined(NO_ASM) && !defined(NO_INLINE_ASM) && !defined(PEDANTIC) && !defined(BN_DIV3W)
e02884167b7c969b56413f76c48c3802c4dca14dAndreas Gustafsson# if defined(__GNUC__) && __GNUC__>=2
bf345589ce0b0b64533d4566e4992a0e63aac6f5Bob Halley# if defined(__i386)
bf345589ce0b0b64533d4566e4992a0e63aac6f5Bob Halley /*
3ddd814a97de1d152ba0913c592d6e6dc83d38a6Michael Graff * There were two reasons for implementing this template:
bf345589ce0b0b64533d4566e4992a0e63aac6f5Bob Halley * - GNU C generates a call to a function (__udivdi3 to be exact)
e02884167b7c969b56413f76c48c3802c4dca14dAndreas Gustafsson * in reply to ((((BN_ULLONG)n0)<<BN_BITS2)|n1)/d0 (I fail to
e02884167b7c969b56413f76c48c3802c4dca14dAndreas Gustafsson * understand why...);
419590499823ce15b5d2ad4fe71eaf04bd5a86c0Michael Graff * - divl doesn't only calculate quotient, but also leaves
bf345589ce0b0b64533d4566e4992a0e63aac6f5Bob Halley * remainder in %edx which we can definitely use here:-)
bf345589ce0b0b64533d4566e4992a0e63aac6f5Bob Halley *
bf345589ce0b0b64533d4566e4992a0e63aac6f5Bob Halley * <appro@fy.chalmers.se>
bf345589ce0b0b64533d4566e4992a0e63aac6f5Bob Halley */
bf345589ce0b0b64533d4566e4992a0e63aac6f5Bob Halley# define bn_div_words(n0,n1,d0) \
bf345589ce0b0b64533d4566e4992a0e63aac6f5Bob Halley ({ asm volatile ( \
bf345589ce0b0b64533d4566e4992a0e63aac6f5Bob Halley "divl %4" \
e02884167b7c969b56413f76c48c3802c4dca14dAndreas Gustafsson : "=a"(q), "=d"(rem) \
e02884167b7c969b56413f76c48c3802c4dca14dAndreas Gustafsson : "a"(n1), "d"(n0), "g"(d0) \
e02884167b7c969b56413f76c48c3802c4dca14dAndreas Gustafsson : "cc"); \
bf345589ce0b0b64533d4566e4992a0e63aac6f5Bob Halley q; \
bf345589ce0b0b64533d4566e4992a0e63aac6f5Bob Halley })
bf345589ce0b0b64533d4566e4992a0e63aac6f5Bob Halley# define REMAINDER_IS_ALREADY_CALCULATED
1c724c986de1449e3b2f1eeae4c724dc0d97603cBob Halley# endif /* __<cpu> */
1c724c986de1449e3b2f1eeae4c724dc0d97603cBob Halley# endif /* __GNUC__ */
1c724c986de1449e3b2f1eeae4c724dc0d97603cBob Halley#endif /* NO_ASM */
1c724c986de1449e3b2f1eeae4c724dc0d97603cBob Halley
1c724c986de1449e3b2f1eeae4c724dc0d97603cBob Halleyint BN_div(BIGNUM *dv, BIGNUM *rm, const BIGNUM *num, const BIGNUM *divisor,
7837d146219db7a85a4b444a9cdf6602254a4f75Bob Halley BN_CTX *ctx)
7837d146219db7a85a4b444a9cdf6602254a4f75Bob Halley {
7837d146219db7a85a4b444a9cdf6602254a4f75Bob Halley int norm_shift,i,j,loop;
7837d146219db7a85a4b444a9cdf6602254a4f75Bob Halley BIGNUM *tmp,wnum,*snum,*sdiv,*res;
7837d146219db7a85a4b444a9cdf6602254a4f75Bob Halley BN_ULONG *resp,*wnump;
e02884167b7c969b56413f76c48c3802c4dca14dAndreas Gustafsson BN_ULONG d0,d1;
7837d146219db7a85a4b444a9cdf6602254a4f75Bob Halley int num_n,div_n;
7837d146219db7a85a4b444a9cdf6602254a4f75Bob Halley
7837d146219db7a85a4b444a9cdf6602254a4f75Bob Halley bn_check_top(num);
7837d146219db7a85a4b444a9cdf6602254a4f75Bob Halley bn_check_top(divisor);
7837d146219db7a85a4b444a9cdf6602254a4f75Bob Halley
bf345589ce0b0b64533d4566e4992a0e63aac6f5Bob Halley if (BN_is_zero(divisor))
bf345589ce0b0b64533d4566e4992a0e63aac6f5Bob Halley {
bf345589ce0b0b64533d4566e4992a0e63aac6f5Bob Halley BNerr(BN_F_BN_DIV,BN_R_DIV_BY_ZERO);
bf345589ce0b0b64533d4566e4992a0e63aac6f5Bob Halley return(0);
1c724c986de1449e3b2f1eeae4c724dc0d97603cBob Halley }
732e0731dec1922747bb3b3147cf2c3d16b22eaaBob Halley
35541328a8c18ba1f984300dfe30ec8713c90031Mark Andrews if (BN_ucmp(num,divisor) < 0)
35541328a8c18ba1f984300dfe30ec8713c90031Mark Andrews {
35541328a8c18ba1f984300dfe30ec8713c90031Mark Andrews if (rm != NULL)
bf345589ce0b0b64533d4566e4992a0e63aac6f5Bob Halley { if (BN_copy(rm,num) == NULL) return(0); }
bf345589ce0b0b64533d4566e4992a0e63aac6f5Bob Halley if (dv != NULL) BN_zero(dv);
bf345589ce0b0b64533d4566e4992a0e63aac6f5Bob Halley return(1);
bf345589ce0b0b64533d4566e4992a0e63aac6f5Bob Halley }
bf345589ce0b0b64533d4566e4992a0e63aac6f5Bob Halley
bf345589ce0b0b64533d4566e4992a0e63aac6f5Bob Halley BN_CTX_start(ctx);
bf345589ce0b0b64533d4566e4992a0e63aac6f5Bob Halley tmp=BN_CTX_get(ctx);
bf345589ce0b0b64533d4566e4992a0e63aac6f5Bob Halley tmp->neg=0;
bf345589ce0b0b64533d4566e4992a0e63aac6f5Bob Halley snum=BN_CTX_get(ctx);
bf345589ce0b0b64533d4566e4992a0e63aac6f5Bob Halley sdiv=BN_CTX_get(ctx);
bf345589ce0b0b64533d4566e4992a0e63aac6f5Bob Halley if (dv == NULL)
bf345589ce0b0b64533d4566e4992a0e63aac6f5Bob Halley res=BN_CTX_get(ctx);
bf345589ce0b0b64533d4566e4992a0e63aac6f5Bob Halley else res=dv;
bf345589ce0b0b64533d4566e4992a0e63aac6f5Bob Halley if (res == NULL) goto err;
bf345589ce0b0b64533d4566e4992a0e63aac6f5Bob Halley
bf345589ce0b0b64533d4566e4992a0e63aac6f5Bob Halley /* First we normalise the numbers */
bf345589ce0b0b64533d4566e4992a0e63aac6f5Bob Halley norm_shift=BN_BITS2-((BN_num_bits(divisor))%BN_BITS2);
bf345589ce0b0b64533d4566e4992a0e63aac6f5Bob Halley BN_lshift(sdiv,divisor,norm_shift);
bf345589ce0b0b64533d4566e4992a0e63aac6f5Bob Halley sdiv->neg=0;
bf345589ce0b0b64533d4566e4992a0e63aac6f5Bob Halley norm_shift+=BN_BITS2;
bf345589ce0b0b64533d4566e4992a0e63aac6f5Bob Halley BN_lshift(snum,num,norm_shift);
7837d146219db7a85a4b444a9cdf6602254a4f75Bob Halley snum->neg=0;
7837d146219db7a85a4b444a9cdf6602254a4f75Bob Halley div_n=sdiv->top;
7837d146219db7a85a4b444a9cdf6602254a4f75Bob Halley num_n=snum->top;
7837d146219db7a85a4b444a9cdf6602254a4f75Bob Halley loop=num_n-div_n;
7837d146219db7a85a4b444a9cdf6602254a4f75Bob Halley
7837d146219db7a85a4b444a9cdf6602254a4f75Bob Halley /* Lets setup a 'window' into snum
7837d146219db7a85a4b444a9cdf6602254a4f75Bob Halley * This is the part that corresponds to the current
7837d146219db7a85a4b444a9cdf6602254a4f75Bob Halley * 'area' being divided */
7837d146219db7a85a4b444a9cdf6602254a4f75Bob Halley BN_init(&wnum);
7837d146219db7a85a4b444a9cdf6602254a4f75Bob Halley wnum.d= &(snum->d[loop]);
7837d146219db7a85a4b444a9cdf6602254a4f75Bob Halley wnum.top= div_n;
7837d146219db7a85a4b444a9cdf6602254a4f75Bob Halley wnum.max= snum->max+1; /* a bit of a lie */
7837d146219db7a85a4b444a9cdf6602254a4f75Bob Halley
1c724c986de1449e3b2f1eeae4c724dc0d97603cBob Halley /* Get the top 2 words of sdiv */
1c724c986de1449e3b2f1eeae4c724dc0d97603cBob Halley /* i=sdiv->top; */
1c724c986de1449e3b2f1eeae4c724dc0d97603cBob Halley d0=sdiv->d[div_n-1];
1c724c986de1449e3b2f1eeae4c724dc0d97603cBob Halley d1=(div_n == 1)?0:sdiv->d[div_n-2];
1c724c986de1449e3b2f1eeae4c724dc0d97603cBob Halley
1c724c986de1449e3b2f1eeae4c724dc0d97603cBob Halley /* pointer to the 'top' of snum */
1c724c986de1449e3b2f1eeae4c724dc0d97603cBob Halley wnump= &(snum->d[num_n-1]);
1c724c986de1449e3b2f1eeae4c724dc0d97603cBob Halley
1c724c986de1449e3b2f1eeae4c724dc0d97603cBob Halley /* Setup to 'res' */
1c724c986de1449e3b2f1eeae4c724dc0d97603cBob Halley res->neg= (num->neg^divisor->neg);
1c724c986de1449e3b2f1eeae4c724dc0d97603cBob Halley if (!bn_wexpand(res,(loop+1))) goto err;
40f53fa8d9c6a4fc38c0014495e7a42b08f52481David Lawrence res->top=loop;
1c724c986de1449e3b2f1eeae4c724dc0d97603cBob Halley resp= &(res->d[loop-1]);
1c724c986de1449e3b2f1eeae4c724dc0d97603cBob Halley
1c724c986de1449e3b2f1eeae4c724dc0d97603cBob Halley /* space for temp */
3ddd814a97de1d152ba0913c592d6e6dc83d38a6Michael Graff if (!bn_wexpand(tmp,(div_n+1))) goto err;
5619558151f1aa4249b3ead979e76876e29278b6Bob Halley
5619558151f1aa4249b3ead979e76876e29278b6Bob Halley if (BN_ucmp(&wnum,sdiv) >= 0)
5619558151f1aa4249b3ead979e76876e29278b6Bob Halley {
5619558151f1aa4249b3ead979e76876e29278b6Bob Halley if (!BN_usub(&wnum,&wnum,sdiv)) goto err;
5619558151f1aa4249b3ead979e76876e29278b6Bob Halley *resp=1;
5619558151f1aa4249b3ead979e76876e29278b6Bob Halley res->d[res->top-1]=1;
078d49b63324f01d98301ee21671abee0c41fcdeBob Halley }
0180ccf72c79b98eb8ee5abbb7331aec6951dd9fBob Halley else
5619558151f1aa4249b3ead979e76876e29278b6Bob Halley res->top--;
5619558151f1aa4249b3ead979e76876e29278b6Bob Halley resp--;
5619558151f1aa4249b3ead979e76876e29278b6Bob Halley
5619558151f1aa4249b3ead979e76876e29278b6Bob Halley for (i=0; i<loop-1; i++)
3ddd814a97de1d152ba0913c592d6e6dc83d38a6Michael Graff {
5619558151f1aa4249b3ead979e76876e29278b6Bob Halley BN_ULONG q,l0;
5619558151f1aa4249b3ead979e76876e29278b6Bob Halley#ifdef BN_DIV3W
5619558151f1aa4249b3ead979e76876e29278b6Bob Halley q=bn_div_3_words(wnump,d1,d0);
5619558151f1aa4249b3ead979e76876e29278b6Bob Halley#else
5619558151f1aa4249b3ead979e76876e29278b6Bob Halley BN_ULONG n0,n1,rem=0;
5619558151f1aa4249b3ead979e76876e29278b6Bob Halley
078d49b63324f01d98301ee21671abee0c41fcdeBob Halley n0=wnump[0];
0180ccf72c79b98eb8ee5abbb7331aec6951dd9fBob Halley n1=wnump[-1];
5619558151f1aa4249b3ead979e76876e29278b6Bob Halley if (n0 == d0)
5619558151f1aa4249b3ead979e76876e29278b6Bob Halley q=BN_MASK2;
5619558151f1aa4249b3ead979e76876e29278b6Bob Halley else /* n0 < d0 */
5619558151f1aa4249b3ead979e76876e29278b6Bob Halley {
5619558151f1aa4249b3ead979e76876e29278b6Bob Halley#ifdef BN_LLONG
5619558151f1aa4249b3ead979e76876e29278b6Bob Halley BN_ULLONG t2;
5619558151f1aa4249b3ead979e76876e29278b6Bob Halley
5619558151f1aa4249b3ead979e76876e29278b6Bob Halley#if defined(BN_LLONG) && defined(BN_DIV2W) && !defined(bn_div_words)
5619558151f1aa4249b3ead979e76876e29278b6Bob Halley q=(BN_ULONG)(((((BN_ULLONG)n0)<<BN_BITS2)|n1)/d0);
5619558151f1aa4249b3ead979e76876e29278b6Bob Halley#else
5619558151f1aa4249b3ead979e76876e29278b6Bob Halley q=bn_div_words(n0,n1,d0);
078d49b63324f01d98301ee21671abee0c41fcdeBob Halley#endif
0180ccf72c79b98eb8ee5abbb7331aec6951dd9fBob Halley
5619558151f1aa4249b3ead979e76876e29278b6Bob Halley#ifndef REMAINDER_IS_ALREADY_CALCULATED
5619558151f1aa4249b3ead979e76876e29278b6Bob Halley /*
5619558151f1aa4249b3ead979e76876e29278b6Bob Halley * rem doesn't have to be BN_ULLONG. The least we
5619558151f1aa4249b3ead979e76876e29278b6Bob Halley * know it's less that d0, isn't it?
c3b708aaf1bb0a118e0e11befa1b732acfb1d079Bob Halley */
c3b708aaf1bb0a118e0e11befa1b732acfb1d079Bob Halley rem=(n1-q*d0)&BN_MASK2;
2dd99c098ca162f985b7ef3c8142a964ad8281aeMark Andrews#endif
40f53fa8d9c6a4fc38c0014495e7a42b08f52481David Lawrence t2=(BN_ULLONG)d1*q;
febaa091847ab004f40500cc475a819f2c73fcddAndreas Gustafsson
febaa091847ab004f40500cc475a819f2c73fcddAndreas Gustafsson for (;;)
febaa091847ab004f40500cc475a819f2c73fcddAndreas Gustafsson {
febaa091847ab004f40500cc475a819f2c73fcddAndreas Gustafsson if (t2 <= ((((BN_ULLONG)rem)<<BN_BITS2)|wnump[-2]))
febaa091847ab004f40500cc475a819f2c73fcddAndreas Gustafsson break;
febaa091847ab004f40500cc475a819f2c73fcddAndreas Gustafsson q--;
febaa091847ab004f40500cc475a819f2c73fcddAndreas Gustafsson rem += d0;
febaa091847ab004f40500cc475a819f2c73fcddAndreas Gustafsson if (rem < d0) break; /* don't let rem overflow */
febaa091847ab004f40500cc475a819f2c73fcddAndreas Gustafsson t2 -= d1;
febaa091847ab004f40500cc475a819f2c73fcddAndreas Gustafsson }
febaa091847ab004f40500cc475a819f2c73fcddAndreas Gustafsson#else /* !BN_LLONG */
c3b708aaf1bb0a118e0e11befa1b732acfb1d079Bob Halley BN_ULONG t2l,t2h,ql,qh;
03f91269f5453bcbd924910ef85a8f8496cf2661Mark Andrews
03f91269f5453bcbd924910ef85a8f8496cf2661Mark Andrews q=bn_div_words(n0,n1,d0);
03f91269f5453bcbd924910ef85a8f8496cf2661Mark Andrews#ifndef REMAINDER_IS_ALREADY_CALCULATED
03f91269f5453bcbd924910ef85a8f8496cf2661Mark Andrews rem=(n1-q*d0)&BN_MASK2;
84185d19c7a9ef1ac23cc6236c8773697d4efeb1Brian Wellington#endif
84185d19c7a9ef1ac23cc6236c8773697d4efeb1Brian Wellington
5619558151f1aa4249b3ead979e76876e29278b6Bob Halley#ifdef BN_UMULT_HIGH
88a6fef4944a00d8350ffd8b64ef58c694b8335eMark Andrews t2l = d1 * q;
76883e8cee593f45c65b0936e5d6e8f778d6e3efMichael Graff t2h = BN_UMULT_HIGH(d1,q);
3ddd814a97de1d152ba0913c592d6e6dc83d38a6Michael Graff#else
2dd99c098ca162f985b7ef3c8142a964ad8281aeMark Andrews t2l=LBITS(d1); t2h=HBITS(d1);
8af4b7042d84e0699f7c1de306526098030b74a9Mark Andrews ql =LBITS(q); qh =HBITS(q);
69be7837c920fac5c71a73e8fad586f9a2711e96Michael Graff mul64(t2l,t2h,ql,qh); /* t2=(BN_ULLONG)d1*q; */
bf345589ce0b0b64533d4566e4992a0e63aac6f5Bob Halley#endif
c3b708aaf1bb0a118e0e11befa1b732acfb1d079Bob Halley
c3b708aaf1bb0a118e0e11befa1b732acfb1d079Bob Halley for (;;)
febaa091847ab004f40500cc475a819f2c73fcddAndreas Gustafsson {
5619558151f1aa4249b3ead979e76876e29278b6Bob Halley if ((t2h < rem) ||
03f91269f5453bcbd924910ef85a8f8496cf2661Mark Andrews ((t2h == rem) && (t2l <= wnump[-2])))
03f91269f5453bcbd924910ef85a8f8496cf2661Mark Andrews break;
5619558151f1aa4249b3ead979e76876e29278b6Bob Halley q--;
5619558151f1aa4249b3ead979e76876e29278b6Bob Halley rem += d0;
5619558151f1aa4249b3ead979e76876e29278b6Bob Halley if (rem < d0) break; /* don't let rem overflow */
5619558151f1aa4249b3ead979e76876e29278b6Bob Halley if (t2l < d1) t2h--; t2l -= d1;
5619558151f1aa4249b3ead979e76876e29278b6Bob Halley }
54f959d12b5a1f9315fbf6a776c6d349316e9686Bob Halley#endif /* !BN_LLONG */
ccbfddc70ef38263daca312d29bb8c5077e24785Bob Halley }
febaa091847ab004f40500cc475a819f2c73fcddAndreas Gustafsson#endif /* !BN_DIV3W */
54f959d12b5a1f9315fbf6a776c6d349316e9686Bob Halley
c3b708aaf1bb0a118e0e11befa1b732acfb1d079Bob Halley l0=bn_mul_words(tmp->d,sdiv->d,div_n,q);
89d8adb6663b13435ff9ae1eb53e45da7fa79275Bob Halley wnum.d--; wnum.top++;
bf345589ce0b0b64533d4566e4992a0e63aac6f5Bob Halley tmp->d[div_n]=l0;
c3b708aaf1bb0a118e0e11befa1b732acfb1d079Bob Halley for (j=div_n+1; j>0; j--)
89d8adb6663b13435ff9ae1eb53e45da7fa79275Bob Halley if (tmp->d[j-1]) break;
419590499823ce15b5d2ad4fe71eaf04bd5a86c0Michael Graff tmp->top=j;
8dfa9caeec8e68db0c937e347a3d6629e7627d54Bob Halley
8dfa9caeec8e68db0c937e347a3d6629e7627d54Bob Halley j=wnum.top;
8dfa9caeec8e68db0c937e347a3d6629e7627d54Bob Halley BN_sub(&wnum,&wnum,tmp);
8dfa9caeec8e68db0c937e347a3d6629e7627d54Bob Halley
b2ca6fd3a8293440b4d263723525396059cf2400Brian Wellington snum->top=snum->top+wnum.top-j;
b2ca6fd3a8293440b4d263723525396059cf2400Brian Wellington
b2ca6fd3a8293440b4d263723525396059cf2400Brian Wellington if (wnum.neg)
b2ca6fd3a8293440b4d263723525396059cf2400Brian Wellington {
84185d19c7a9ef1ac23cc6236c8773697d4efeb1Brian Wellington q--;
89d8adb6663b13435ff9ae1eb53e45da7fa79275Bob Halley j=wnum.top;
c3b708aaf1bb0a118e0e11befa1b732acfb1d079Bob Halley BN_add(&wnum,&wnum,sdiv);
bf345589ce0b0b64533d4566e4992a0e63aac6f5Bob Halley snum->top+=wnum.top-j;
419590499823ce15b5d2ad4fe71eaf04bd5a86c0Michael Graff }
419590499823ce15b5d2ad4fe71eaf04bd5a86c0Michael Graff *(resp--)=q;
419590499823ce15b5d2ad4fe71eaf04bd5a86c0Michael Graff wnump--;
bf345589ce0b0b64533d4566e4992a0e63aac6f5Bob Halley }
bf345589ce0b0b64533d4566e4992a0e63aac6f5Bob Halley if (rm != NULL)
bf345589ce0b0b64533d4566e4992a0e63aac6f5Bob Halley {
febaa091847ab004f40500cc475a819f2c73fcddAndreas Gustafsson BN_rshift(rm,snum,norm_shift);
febaa091847ab004f40500cc475a819f2c73fcddAndreas Gustafsson rm->neg=num->neg;
febaa091847ab004f40500cc475a819f2c73fcddAndreas Gustafsson }
febaa091847ab004f40500cc475a819f2c73fcddAndreas Gustafsson BN_CTX_end(ctx);
febaa091847ab004f40500cc475a819f2c73fcddAndreas Gustafsson return(1);
febaa091847ab004f40500cc475a819f2c73fcddAndreas Gustafssonerr:
febaa091847ab004f40500cc475a819f2c73fcddAndreas Gustafsson BN_CTX_end(ctx);
febaa091847ab004f40500cc475a819f2c73fcddAndreas Gustafsson return(0);
2dd99c098ca162f985b7ef3c8142a964ad8281aeMark Andrews }
febaa091847ab004f40500cc475a819f2c73fcddAndreas Gustafsson
93d6dfaf66258337985427c86181f01fc51f0bb4Mark Andrews#endif
febaa091847ab004f40500cc475a819f2c73fcddAndreas Gustafsson
febaa091847ab004f40500cc475a819f2c73fcddAndreas Gustafsson/* rem != m */
febaa091847ab004f40500cc475a819f2c73fcddAndreas Gustafssonint BN_mod(BIGNUM *rem, const BIGNUM *m, const BIGNUM *d, BN_CTX *ctx)
febaa091847ab004f40500cc475a819f2c73fcddAndreas Gustafsson {
febaa091847ab004f40500cc475a819f2c73fcddAndreas Gustafsson#if 0 /* The old slow way */
febaa091847ab004f40500cc475a819f2c73fcddAndreas Gustafsson int i,nm,nd;
febaa091847ab004f40500cc475a819f2c73fcddAndreas Gustafsson BIGNUM *dv;
febaa091847ab004f40500cc475a819f2c73fcddAndreas Gustafsson
febaa091847ab004f40500cc475a819f2c73fcddAndreas Gustafsson if (BN_ucmp(m,d) < 0)
febaa091847ab004f40500cc475a819f2c73fcddAndreas Gustafsson return((BN_copy(rem,m) == NULL)?0:1);
febaa091847ab004f40500cc475a819f2c73fcddAndreas Gustafsson
febaa091847ab004f40500cc475a819f2c73fcddAndreas Gustafsson BN_CTX_start(ctx);
febaa091847ab004f40500cc475a819f2c73fcddAndreas Gustafsson dv=BN_CTX_get(ctx);
febaa091847ab004f40500cc475a819f2c73fcddAndreas Gustafsson
febaa091847ab004f40500cc475a819f2c73fcddAndreas Gustafsson if (!BN_copy(rem,m)) goto err;
febaa091847ab004f40500cc475a819f2c73fcddAndreas Gustafsson
2dd99c098ca162f985b7ef3c8142a964ad8281aeMark Andrews nm=BN_num_bits(rem);
c3b708aaf1bb0a118e0e11befa1b732acfb1d079Bob Halley nd=BN_num_bits(d);
febaa091847ab004f40500cc475a819f2c73fcddAndreas Gustafsson if (!BN_lshift(dv,d,nm-nd)) goto err;
c3b708aaf1bb0a118e0e11befa1b732acfb1d079Bob Halley for (i=nm-nd; i>=0; i--)
2dd99c098ca162f985b7ef3c8142a964ad8281aeMark Andrews {
c3b708aaf1bb0a118e0e11befa1b732acfb1d079Bob Halley if (BN_cmp(rem,dv) >= 0)
2dd99c098ca162f985b7ef3c8142a964ad8281aeMark Andrews {
c3b708aaf1bb0a118e0e11befa1b732acfb1d079Bob Halley if (!BN_sub(rem,rem,dv)) goto err;
2dd99c098ca162f985b7ef3c8142a964ad8281aeMark Andrews }
febaa091847ab004f40500cc475a819f2c73fcddAndreas Gustafsson if (!BN_rshift1(dv,dv)) goto err;
febaa091847ab004f40500cc475a819f2c73fcddAndreas Gustafsson }
febaa091847ab004f40500cc475a819f2c73fcddAndreas Gustafsson BN_CTX_end(ctx);
febaa091847ab004f40500cc475a819f2c73fcddAndreas Gustafsson return(1);
febaa091847ab004f40500cc475a819f2c73fcddAndreas Gustafsson err:
2dd99c098ca162f985b7ef3c8142a964ad8281aeMark Andrews BN_CTX_end(ctx);
2dd99c098ca162f985b7ef3c8142a964ad8281aeMark Andrews return(0);
2dd99c098ca162f985b7ef3c8142a964ad8281aeMark Andrews#else
2dd99c098ca162f985b7ef3c8142a964ad8281aeMark Andrews return(BN_div(NULL,rem,m,d,ctx));
2dd99c098ca162f985b7ef3c8142a964ad8281aeMark Andrews#endif
2dd99c098ca162f985b7ef3c8142a964ad8281aeMark Andrews }
def8e47c688e2480a4539d69c3d1a0a28a7c0550Mark Andrews
def8e47c688e2480a4539d69c3d1a0a28a7c0550Mark Andrews