[thirdparty/openssl.git] / crypto / bn / bn_div.c

/* crypto/bn/bn_div.c */
/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
 * All rights reserved.
 *
 * This package is an SSL implementation written
 * by Eric Young (eay@cryptsoft.com).
 * The implementation was written so as to conform with Netscapes SSL.
 * 
 * This library is free for commercial and non-commercial use as long as
 * the following conditions are aheared to.  The following conditions
 * apply to all code found in this distribution, be it the RC4, RSA,
 * lhash, DES, etc., code; not just the SSL code.  The SSL documentation
 * included with this distribution is covered by the same copyright terms
 * except that the holder is Tim Hudson (tjh@cryptsoft.com).
 * 
 * Copyright remains Eric Young's, and as such any Copyright notices in
 * the code are not to be removed.
 * If this package is used in a product, Eric Young should be given attribution
 * as the author of the parts of the library used.
 * This can be in the form of a textual message at program startup or
 * in documentation (online or textual) provided with the package.
 * 
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 * 3. All advertising materials mentioning features or use of this software
 *    must display the following acknowledgement:
 *    "This product includes cryptographic software written by
 *     Eric Young (eay@cryptsoft.com)"
 *    The word 'cryptographic' can be left out if the rouines from the library
 *    being used are not cryptographic related :-).
 * 4. If you include any Windows specific code (or a derivative thereof) from 
 *    the apps directory (application code) you must include an acknowledgement:
 *    "This product includes software written by Tim Hudson (tjh@cryptsoft.com)"
 * 
 * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 * 
 * The licence and distribution terms for any publically available version or
 * derivative of this code cannot be changed.  i.e. this code cannot simply be
 * copied and put under another distribution licence
 * [including the GNU Public Licence.]
 */

#include <stdio.h>
#include "cryptlib.h"
#include "bn_lcl.h"

/* The old slow way */
#if 0
int BN_div(dv, rem, m, d,ctx)
BIGNUM *dv;
BIGNUM *rem;
BIGNUM *m;
BIGNUM *d;
BN_CTX *ctx;
	{
	int i,nm,nd;
	BIGNUM *D;

	if (BN_is_zero(d))
		{
		BNerr(BN_F_BN_DIV,BN_R_DIV_BY_ZERO);
		return(0);
		}

	if (BN_ucmp(m,d) < 0)
		{
		if (rem != NULL)
			{ if (BN_copy(rem,m) == NULL) return(0); }
		if (dv != NULL) BN_zero(dv);
		return(1);
		}

	D=ctx->bn[ctx->tos];
	if (dv == NULL) dv=ctx->bn[ctx->tos+1];
	if (rem == NULL) rem=ctx->bn[ctx->tos+2];

	nd=BN_num_bits(d);
	nm=BN_num_bits(m);
	if (BN_copy(D,d) == NULL) return(0);
	if (BN_copy(rem,m) == NULL) return(0);

	/* The next 2 are needed so we can do a dv->d[0]|=1 later
	 * since BN_lshift1 will only work once there is a value :-) */
	BN_zero(dv);
	dv->top=1;

	if (!BN_lshift(D,D,nm-nd)) return(0);
	for (i=nm-nd; i>=0; i--)
		{
		if (!BN_lshift1(dv,dv)) return(0);
		if (BN_ucmp(rem,D) >= 0)
			{
			dv->d[0]|=1;
			bn_qsub(rem,rem,D);
			}
/* CAN IMPROVE (and have now :=) */
		if (!BN_rshift1(D,D)) return(0);
		}
	rem->neg=BN_is_zero(rem)?0:m->neg;
	dv->neg=m->neg^d->neg;
	return(1);
	}

#else

int BN_div(dv, rm, num, divisor,ctx)
BIGNUM *dv;
BIGNUM *rm;
BIGNUM *num;
BIGNUM *divisor;
BN_CTX *ctx;
	{
	int norm_shift,i,j,loop;
	BIGNUM *tmp,wnum,*snum,*sdiv,*res;
	BN_ULONG *resp,*wnump;
	BN_ULONG d0,d1;
	int num_n,div_n;

	if (BN_is_zero(divisor))
		{
		BNerr(BN_F_BN_DIV,BN_R_DIV_BY_ZERO);
		return(0);
		}

	if (BN_ucmp(num,divisor) < 0)
		{
		if (rm != NULL)
			{ if (BN_copy(rm,num) == NULL) return(0); }
		if (dv != NULL) BN_zero(dv);
		return(1);
		}

	tmp=ctx->bn[ctx->tos]; 
	tmp->neg=0;
	snum=ctx->bn[ctx->tos+1];
	sdiv=ctx->bn[ctx->tos+2];
	if (dv == NULL)
		res=ctx->bn[ctx->tos+3];
	else	res=dv;

	/* First we normalise the numbers */
	norm_shift=BN_BITS2-((BN_num_bits(divisor))%BN_BITS2);
	BN_lshift(sdiv,divisor,norm_shift);
	sdiv->neg=0;
	norm_shift+=BN_BITS2;
	BN_lshift(snum,num,norm_shift);
	snum->neg=0;
	div_n=sdiv->top;
	num_n=snum->top;
	loop=num_n-div_n;

	/* Lets setup a 'window' into snum
	 * This is the part that corresponds to the current
	 * 'area' being divided */
	wnum.d=	 &(snum->d[loop]);
	wnum.top= div_n;
	wnum.max= snum->max; /* a bit of a lie */
	wnum.neg= 0;

	/* Get the top 2 words of sdiv */
	/* i=sdiv->top; */
	d0=sdiv->d[div_n-1];
	d1=(div_n == 1)?0:sdiv->d[div_n-2];

	/* pointer to the 'top' of snum */
	wnump= &(snum->d[num_n-1]);

	/* Setup to 'res' */
	res->neg= (num->neg^divisor->neg);
	res->top=loop;
	if (!bn_wexpand(res,(loop+1))) goto err;
	resp= &(res->d[loop-1]);

	/* space for temp */
	if (!bn_wexpand(tmp,(div_n+1))) goto err;

	if (BN_ucmp(&wnum,sdiv) >= 0)
		{
		bn_qsub(&wnum,&wnum,sdiv);
		*resp=1;
		res->d[res->top-1]=1;
		}
	else
		res->top--;
	resp--;

	for (i=0; i<loop-1; i++)
		{
		BN_ULONG q,n0,n1;
		BN_ULONG l0;

		wnum.d--; wnum.top++;
		n0=wnump[0];
		n1=wnump[-1];
		if (n0 == d0)
			q=BN_MASK2;
		else
			q=bn_div64(n0,n1,d0);
		{
#ifdef BN_LLONG
		BN_ULLONG t1,t2,rem;
		t1=((BN_ULLONG)n0<<BN_BITS2)|n1;
		for (;;)
			{
			t2=(BN_ULLONG)d1*q;
			rem=t1-(BN_ULLONG)q*d0;
			if ((rem>>BN_BITS2) ||
				(t2 <= ((BN_ULLONG)(rem<<BN_BITS2)+wnump[-2])))
				break;
			q--;
			}
#else
		BN_ULONG t1l,t1h,t2l,t2h,t3l,t3h,ql,qh,t3t;
		t1h=n0;
		t1l=n1;
		for (;;)
			{
			t2l=LBITS(d1); t2h=HBITS(d1);
			ql =LBITS(q);  qh =HBITS(q);
			mul64(t2l,t2h,ql,qh); /* t2=(BN_ULLONG)d1*q; */

			t3t=LBITS(d0); t3h=HBITS(d0);
			mul64(t3t,t3h,ql,qh); /* t3=t1-(BN_ULLONG)q*d0; */
			t3l=(t1l-t3t)&BN_MASK2;
			if (t3l > t1l) t3h++;
			t3h=(t1h-t3h)&BN_MASK2;

			/*if ((t3>>BN_BITS2) ||
				(t2 <= ((t3<<BN_BITS2)+wnump[-2])))
				break; */
			if (t3h) break;
			if (t2h < t3l) break;
			if ((t2h == t3l) && (t2l <= wnump[-2])) break;

			q--;
			}
#endif
		}
		l0=bn_mul_words(tmp->d,sdiv->d,div_n,q);
		tmp->d[div_n]=l0;
		for (j=div_n+1; j>0; j--)
			if (tmp->d[j-1]) break;
		tmp->top=j;

		j=wnum.top;
		BN_sub(&wnum,&wnum,tmp);

		snum->top=snum->top+wnum.top-j;

		if (wnum.neg)
			{
			q--;
			j=wnum.top;
			BN_add(&wnum,&wnum,sdiv);
			snum->top+=wnum.top-j;
			}
		*(resp--)=q;
		wnump--;
		}
	if (rm != NULL)
		{
		BN_rshift(rm,snum,norm_shift);
		rm->neg=num->neg;
		}
	return(1);
err:
	return(0);
	}

#endif
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.
	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 "cryptlib.h"
	61	#include "bn_lcl.h"
	62
	63	/* The old slow way */
	64	#if 0
	65	int BN_div(dv, rem, m, d,ctx)
	66	BIGNUM *dv;
67	BIGNUM *rem;
68	BIGNUM *m;
69	BIGNUM *d;
70	BN_CTX *ctx;
71	{
72	int i,nm,nd;
73	BIGNUM *D;
74
75	if (BN_is_zero(d))
76	{
77	BNerr(BN_F_BN_DIV,BN_R_DIV_BY_ZERO);
78	return(0);
79	}
80
81	if (BN_ucmp(m,d) < 0)
82	{
83	if (rem != NULL)
84	{ if (BN_copy(rem,m) == NULL) return(0); }
85	if (dv != NULL) BN_zero(dv);
86	return(1);
87	}
88
89	D=ctx->bn[ctx->tos];
90	if (dv == NULL) dv=ctx->bn[ctx->tos+1];
91	if (rem == NULL) rem=ctx->bn[ctx->tos+2];
92
93	nd=BN_num_bits(d);
94	nm=BN_num_bits(m);
95	if (BN_copy(D,d) == NULL) return(0);
96	if (BN_copy(rem,m) == NULL) return(0);
97
98	/* The next 2 are needed so we can do a dv->d[0]\|=1 later
99	* since BN_lshift1 will only work once there is a value :-) */
100	BN_zero(dv);
101	dv->top=1;
102
103	if (!BN_lshift(D,D,nm-nd)) return(0);
104	for (i=nm-nd; i>=0; i--)
105	{
106	if (!BN_lshift1(dv,dv)) return(0);
107	if (BN_ucmp(rem,D) >= 0)
108	{
109	dv->d[0]\|=1;
110	bn_qsub(rem,rem,D);
111	}
112	/* CAN IMPROVE (and have now :=) */
113	if (!BN_rshift1(D,D)) return(0);
114	}
115	rem->neg=BN_is_zero(rem)?0:m->neg;
116	dv->neg=m->neg^d->neg;
117	return(1);
118	}
119
120	#else
121
122	int BN_div(dv, rm, num, divisor,ctx)
123	BIGNUM *dv;
124	BIGNUM *rm;
125	BIGNUM *num;
126	BIGNUM *divisor;
127	BN_CTX *ctx;
128	{
129	int norm_shift,i,j,loop;
130	BIGNUM tmp,wnum,snum,sdiv,res;
131	BN_ULONG resp,wnump;
132	BN_ULONG d0,d1;
133	int num_n,div_n;
134
58964a49	135	if (BN_is_zero(divisor))
d02b48c6 RE	136	{
	137	BNerr(BN_F_BN_DIV,BN_R_DIV_BY_ZERO);
	138	return(0);
	139	}
	140
	141	if (BN_ucmp(num,divisor) < 0)
	142	{
	143	if (rm != NULL)
	144	{ if (BN_copy(rm,num) == NULL) return(0); }
	145	if (dv != NULL) BN_zero(dv);
	146	return(1);
	147	}
	148
	149	tmp=ctx->bn[ctx->tos];
	150	tmp->neg=0;
	151	snum=ctx->bn[ctx->tos+1];
	152	sdiv=ctx->bn[ctx->tos+2];
	153	if (dv == NULL)
	154	res=ctx->bn[ctx->tos+3];
	155	else res=dv;
	156
	157	/* First we normalise the numbers */
	158	norm_shift=BN_BITS2-((BN_num_bits(divisor))%BN_BITS2);
	159	BN_lshift(sdiv,divisor,norm_shift);
	160	sdiv->neg=0;
	161	norm_shift+=BN_BITS2;
	162	BN_lshift(snum,num,norm_shift);
	163	snum->neg=0;
	164	div_n=sdiv->top;
	165	num_n=snum->top;
	166	loop=num_n-div_n;
	167
	168	/* Lets setup a 'window' into snum
	169	* This is the part that corresponds to the current
	170	* 'area' being divided */
	171	wnum.d= &(snum->d[loop]);
	172	wnum.top= div_n;
	173	wnum.max= snum->max; /* a bit of a lie */
	174	wnum.neg= 0;
	175
	176	/* Get the top 2 words of sdiv */
	177	/* i=sdiv->top; */
	178	d0=sdiv->d[div_n-1];
	179	d1=(div_n == 1)?0:sdiv->d[div_n-2];
	180
	181	/* pointer to the 'top' of snum */
	182	wnump= &(snum->d[num_n-1]);
	183
	184	/* Setup to 'res' */
	185	res->neg= (num->neg^divisor->neg);
	186	res->top=loop;
58964a49	187	if (!bn_wexpand(res,(loop+1))) goto err;
d02b48c6 RE	188	resp= &(res->d[loop-1]);
	189
	190	/* space for temp */
58964a49	191	if (!bn_wexpand(tmp,(div_n+1))) goto err;
d02b48c6 RE	192
	193	if (BN_ucmp(&wnum,sdiv) >= 0)
	194	{
	195	bn_qsub(&wnum,&wnum,sdiv);
	196	*resp=1;
	197	res->d[res->top-1]=1;
	198	}
	199	else
	200	res->top--;
	201	resp--;
	202
	203	for (i=0; i<loop-1; i++)
	204	{
	205	BN_ULONG q,n0,n1;
	206	BN_ULONG l0;
	207
	208	wnum.d--; wnum.top++;
	209	n0=wnump[0];
	210	n1=wnump[-1];
	211	if (n0 == d0)
	212	q=BN_MASK2;
	213	else
	214	q=bn_div64(n0,n1,d0);
	215	{
	216	#ifdef BN_LLONG
	217	BN_ULLONG t1,t2,rem;
	218	t1=((BN_ULLONG)n0<<BN_BITS2)\|n1;
	219	for (;;)
	220	{
	221	t2=(BN_ULLONG)d1*q;
	222	rem=t1-(BN_ULLONG)q*d0;
	223	if ((rem>>BN_BITS2) \|\|
	224	(t2 <= ((BN_ULLONG)(rem<<BN_BITS2)+wnump[-2])))
	225	break;
	226	q--;
	227	}
	228	#else
	229	BN_ULONG t1l,t1h,t2l,t2h,t3l,t3h,ql,qh,t3t;
	230	t1h=n0;
	231	t1l=n1;
	232	for (;;)
	233	{
	234	t2l=LBITS(d1); t2h=HBITS(d1);
	235	ql =LBITS(q); qh =HBITS(q);
	236	mul64(t2l,t2h,ql,qh); /* t2=(BN_ULLONG)d1q; /
	237
	238	t3t=LBITS(d0); t3h=HBITS(d0);
	239	mul64(t3t,t3h,ql,qh); /* t3=t1-(BN_ULLONG)qd0; /
58964a49	240	t3l=(t1l-t3t)&BN_MASK2;
d02b48c6	241	if (t3l > t1l) t3h++;
58964a49	242	t3h=(t1h-t3h)&BN_MASK2;
d02b48c6 RE	243
	244	/*if ((t3>>BN_BITS2) \|\|
	245	(t2 <= ((t3<<BN_BITS2)+wnump[-2])))
	246	break; */
	247	if (t3h) break;
	248	if (t2h < t3l) break;
	249	if ((t2h == t3l) && (t2l <= wnump[-2])) break;
	250
	251	q--;
	252	}
	253	#endif
	254	}
58964a49	255	l0=bn_mul_words(tmp->d,sdiv->d,div_n,q);
d02b48c6 RE	256	tmp->d[div_n]=l0;
	257	for (j=div_n+1; j>0; j--)
	258	if (tmp->d[j-1]) break;
	259	tmp->top=j;
	260
	261	j=wnum.top;
	262	BN_sub(&wnum,&wnum,tmp);
	263
	264	snum->top=snum->top+wnum.top-j;
	265
	266	if (wnum.neg)
	267	{
	268	q--;
	269	j=wnum.top;
	270	BN_add(&wnum,&wnum,sdiv);
	271	snum->top+=wnum.top-j;
	272	}
	273	*(resp--)=q;
	274	wnump--;
	275	}
	276	if (rm != NULL)
	277	{
	278	BN_rshift(rm,snum,norm_shift);
	279	rm->neg=num->neg;
	280	}
	281	return(1);
	282	err:
	283	return(0);
	284	}
	285
	286	#endif